GAMES102.刘利刚.01.数据拟合(Data Fitting)(02)

• https://www.bilibili.com/video/BV1NA411E7Yr

数据拟合

函数拟合问题

• 输入：一些观察（采样）的数据点 $\{x_i,y_i{\}}_{i=0}^n$
• 输出：你和数据点的函数 $y=f(x)$，并用于预测

image-20210723165053604

• 这样的拟合函数有无穷个

拟合函数的好坏评价

分段线性插值函数

• $y=f_1(x)$

• 数据误差为 0
• 函数性质不够好
  • 只有 $C^0$ 连续，不光滑
    • 一阶导数不连续
    • 数值计算很麻烦

光滑插值函数

• $y=f_2(x)$

• 数据误差为 0
• 可能被 “差数据” 带歪，导致函数性质不好、预测不可靠
  • 噪声，outliers（游离点）

逼近拟合函数

• $y=f_3(x)$

• 数据误差不为 0，但是足够小
• 能够抵抗一些 “差数据” 的影响

选择什么拟合函数

• 应用驱动，除非知道数据的先验，找到一个合适的拟合函数时一个比较复杂的过程
  • 先验：领域知识
• 大部分的实际应用问题
  • 可建模为：找一个映射/变换/函数
  • 输入不一样、变量不一样、维数不一样
• 三步曲方法论：
  • 到哪找？
    • 确定某个函数集合/空间
  • 找哪个？
    • 度量哪个函数是好的 “最好” 的
  • 怎么找？
    • 求解或优化：不同的优化方法与技巧，既要快、又要好 ···

数据拟合的方法论

• 到哪找？
  • 确定函数的表达形式（函数集、空间）
    • $L=span\{b_0(x),\cdots ,b_n(x)\}$
  • 待定基函数的组合系数（求解变量）
    • $f_{\lambda }(x)=\sum _{k=0}^n{\lambda }_i{b}_i(x)$
• 找哪个？
  • 优化模型（最小化问题）
    • 能量项 = 误差项 + 正则项
    • 正则项
      • $\int |f^{″}{|}^2\mathrm{d}x$ 度量光滑性
      • $\int \Vert \mathrm{\nabla }f\Vert \mathrm{d}x$ 弧长尽量小
  • 统计模型、规划模型 ···
• 怎么找？
  • 求解误差函数的驻点（导数为 0 之处）
  • 转化为系数的方程组
    • 如果是欠定的（有无穷多组解），则修正模型
      • 改进/增加 各种正则项：Lasso、岭回归、系数正则项 ···
      • 返回修改模型
  • 如果时非凸的、欠定的则变成难解问题

函数插值定义

• $f(x)$ 为定义在区间 $[a,b]$ 上的函数，$x_0,x_1,\cdots ,x_n$ 为区间上 $n+1$ 个互不相同的点，$\mathrm{\Phi }$ 为给定的某一函数类
• 求 $\mathrm{\Phi }$ 上的函数 $\varphi (x)$，满足：

$$\varphi (x_i)=f(x_i),i=0,\cdots ,n$$

• 则称 $\varphi (x)$ 为 $f(x)$ 关于节点 $x_0,x_1,\cdots ,x_n$ 在 $\mathrm{\Phi }$ 上的插值函数
• 称 $x_0,x_1,\cdots ,x_n$ 为插值节点
• 称 $(x_i,f(x_i))$为插值点

多项式插值

多项式插值定理

• 若 $x_i$ 两两不同，则对任意给定的 $y_i$，存在唯一的次数至多是 $n$ 次的多项式 $p_n$，使得 $p_n(x_i)=y_i,i=0,\cdots ,n$
• 证明如下：范德蒙德行列式不为 0

技巧1：构造插值问题的通用解

• 如果每次都需要求解方程组，则比较麻烦
• 预先构造插值问题的通用解
• 给定 $n+1$ 个点 $\{(x_0,y_0),\cdots ,(x_n,y_n)\}$，寻找一组次数为 $n$ 的多项式基函数 $l_i$ 使得

$$l_i(x_j)=\{\begin{array}{rl}& 1,\mathrm{if}i=j\\ & 0,\mathrm{if}i\ne j\end{array}$$

• 插值问题的解为

$$P(x)=y_0{l}_0(x)+y_1{l}_1(x)+\cdots +y_n{l}_n(x)=\sum _{i=0}^n{y}_i{l}_i(x)$$

怎么计算多项式 $l_i(x)$

• $n$ 阶多项式，且有以下 $n$ 个根

$$x_0,x_1,\cdots ,x_{i-1},x_{i+1},\cdots ,x_n$$

• 故可表示为

$$\begin{array}{rl}{l}_i(x)& =C_i(x-x_0)(x-x_1)\cdots (x-x_{i-1})(x-x_{i+1})\cdots (x-x_n)\\ & =C_i\prod _{i=0\wedge j\ne i}^n(x-x_j)\end{array}$$

• 由 $l_i(x_i)=1$ 可以得到

$$1=C_i\prod _{i=0\wedge j\ne i}^n(x_i-x_j)\Rightarrow C_i={\displaystyle \frac{1}{\prod _{i=0\wedge j\ne i}^n(x_i-x_j)}}$$

• 最终的多项式基函数为

$$l_i(x)={\displaystyle \frac{\prod _{i=0\wedge j\ne i}^n(x-x_j)}{\prod _{i=0\wedge j\ne i}^n(x_i-x_j)}}$$

• $l_i(x)$ 被称为拉格朗日多项式

技巧2：更方便的求解表达

• Newton 插值：具有相同 “导数”（差商）的多项式构造（n 阶 Taylor 展开）

差商定义

• 一阶差商

$$f[x_0,x_1]={\displaystyle \frac{f(x_1)-f(x_0)}{x_1-x_0}}$$

• k 阶差商
  • 设 $\{x_0,x_1,\cdots ,x_n\}$ 互不相同，$f(x)$ 关于 $\{x_0,x_1,\cdots ,x_n\}$ 的 k 阶差商如下

$$f[x_0,\cdots ,x_k]={\displaystyle \frac{f[x_1,\cdots ,x_k]-f[x_0,\cdots ,x_{k-1}]}{x_k-x_0}}$$

• 所以 Newton 插值多项式表示为

$$N_n(x)=f(x_0)+f[x_0,x_1](x-x_0)+\cdots +f[x_0,\cdots ,x_n](x-x_0)\cdots (x-x_{n-1})$$

• 有一点巧妙

多项式插值存在的问题

• 系数矩阵稠密
• 依赖于基函数选取，矩阵可能病态，导致难于求解（求逆）

病态矩阵举例

• 对于扰动很敏感
• 对于如下方程组

$$\{\begin{array}{rl}& x_1+0.5x_2=1.5\\ & 0.667x_1+0.333x_2=1\end{array}\Rightarrow \{\begin{array}{rl}& x_1=1\\ & x_2=1\end{array}$$

• 对等式右边进行扰动 0.001

$$\{\begin{array}{rl}& x_1+0.5x_2=1.5\\ & 0.667x_1+0.333x_2=0.999\end{array}\Rightarrow \{\begin{array}{rl}& x_1=0\\ & x_2=3\end{array}$$

• 对系数矩阵进行扰动 0.001

$$\{\begin{array}{rl}& x_1+0.5x_2=1.5\\ & 0.667x_1+0.334x_2=1\end{array}\Rightarrow \{\begin{array}{rl}& x_1=2\\ & x_2=-1\end{array}$$

病态问题

• 输入数据的细微变化导致输出（解）的剧烈变化
• 将线性方程看成直线（超平面）
  • 当系统病态时，直线变为近似平行
  • 求解（即直线求交）变得困难、不精确

矩阵条件数

• 通过矩阵条件数刻画病态程度

$${\kappa }_2(A)={\displaystyle \frac{\underset{x\ne 0}{max}{\displaystyle \frac{\Vert Ax\Vert }{\Vert x\Vert }}}{\underset{x\ne 0}{min}{\displaystyle \frac{\Vert Ax\Vert }{\Vert x\Vert }}}}$$

• 等于最大特征值和最小特征值之间比例
• 条件数大意味着基元之间有太多相关性

多项式插值问题是病态的

• 对于等距分布的数据点 $x_i$，范德蒙矩阵的条件数随着数据点数 $n$ 呈指数级增长
  • 多项式最高次数为 $n-1$

幂函数带来的问题

• 幂（单项式）函数基
  • 幂函数之间差别随着次数增加而减小
  • 不同幂函数之间唯一差别为增长速度（$x^i$ 比 $x^{i-1}$ 增长快）

• 单项式
  • 从左往右
  • 首先常数 1 主宰
  • 接着 $x$ 增长最快
  • 接着 $x^2$ 增长最快
  • ···

• 趋势
  • 好的基函数一般需要系数交替
  • 互相抵消问题

解决方法

• 使用正交多项式基
• 如何获得？
  • Gram‐Schmidt 正交化

多项式插值结果

• 振荡（龙格 Runge）现象和对插值点数的高度敏感性

结论

• 多项式插值不稳定
  • 控制点的微小变化可导致完全不同的结果
• 振荡（Runge）现象
  • 多项式随着插值点数（可以是细微）增加而摆动
• 需要更好的基函数来做插值
  • Bernstein 基函数
  • 分片多项式

多项式逼近

为什么逼近

• 数据点含噪声、outliers 等
• 更紧凑的表达
• 计算简单、更稳定

最小二乘逼近

逼近问题

• 给定一组线性无关的连续函数集合 $B=\{b_1,\cdots ,b_n\}$ 和一组节点 $\{(x_1,y_1),\cdots ,(x_m,y_m)\}$
  • 其中 $m\ge n$
• 在 B 张成空间中那个函数 $f\in span\{B\}$ 对节点的逼近最好
• 示例：给定一组点，找到最佳逼近的线性函数
• 怎么定义 “最佳逼近”？

最小二乘逼近

$$\underset{f\in span\{B\}}{\arg min}\sum _{j=1}^m(f(x_j)-y_j{)}^2$$

• 系数 ${\lambda }_1,\cdots ,{\lambda }_n$

$$M=\left(\begin{array}{rl}{b}_1(x_1)& \cdots b_n(x_1)\\ \cdots & \cdots \cdots \\ b_1(x_n)& \cdots b_n(x_n)\end{array}\right)$$

• 转化

$$\begin{array}{rl}\sum _{j=1}^m(f(x_j)-y_j{)}^2& =\sum _{j=1}^m(\sum _{i=1}^n{\lambda }_i{b}_i(x_j)-y_j{)}^2\\ & =(M\lambda -y{)}^T(M\lambda -y)\\ & ={\lambda }^T{M}^{T}M\lambda -y^{T}M\lambda -{\lambda }^T{M}^{T}y+y^{T}y\\ & ={\lambda }^T{M}^{T}M\lambda -2y^{T}M\lambda +y^{T}y\end{array}$$

求解

• 怎么求 $\lambda$
• 关于 $\lambda$ 的二次多项式

$${\lambda }^T{M}^{T}M\lambda -2y^{T}M\lambda +y^{T}y$$

• 法方程，最小解满足
  • 求导即可

$$M^{T}M\lambda =y^{T}M$$

• 转化为最小化二次目标函数
  • 最小化二次目标函数 $x^{T}Ax+b^{T}x+c$
  • 充要条件：$2Ax=-b$

函数空间及基函数

为什么用多项式

• 易于计算，表现良好，光滑
• 稠密性与完备性
  • 表达能力足够
  • 维尔斯特拉斯定理 （Weierstrass）

维尔斯特拉斯定理

• 令 $f$ 为闭区间 $[a,b]$ 上的任意连续函数，则对任意给定的 $ϵ$，存在 $n$ 会让多项式 $P_n$ 满足

$$|f(x)-P_n(x)|<ϵ,\mathrm{\forall }x\in [a,b]$$

• 定理只证明了存在性，未给出多项式
• 实际应用中 $n$ 需要通过尝试确定

伯恩斯坦多项式

• 用 Bernstein 多项式做逼近
• 对 $[0,1]$ 区间上任意连续函数 $f(x)$ 和任意正整数 $n$，以下不等式对所有的 $x\in [0,1]$ 成立

$$|f(x)-B_n(f,x)|<{\displaystyle \frac{9}{4}}{m}_{f,n}$$

• $m_{f,n}$ 如下

$$m_{f,n}=\mathrm{lower}\mathrm{upper}\mathrm{bound}|f(y_1)-f(y_2)|$$

$$y_1,y_2\in [0,1]\wedge |y_1-y_2|<{\displaystyle \frac{1}{\sqrt{n}}}$$

• $B_n(f,x)$ 如下，其中 $x_j={\displaystyle \frac{j}{n}}$ 为 $[0,1]$ 上的等距采样点

$$B_n(f,x)=\sum _{j=0}^{n}f(x_j)b_{n,j}(x)$$

• 伯恩斯坦多项式如下

$$b_{n,j}=(\genfrac{}{}{0ex}{}{n}{j})x_j(1-x{)}^{n-j}$$

• 不同次数的伯恩斯坦多项式的基空间

• 矩阵：不同的基函数空间的变换

用 Bernstein 多项式做逼近

• Bernstein 基函数的良好性质：非常好的几何意义！
  • 正性、权性（和为1）$\to$ 凸包性
    • $b_{n,j}>0$（非边界）
    • $\sum _j{b}_{n,j}(x)=1$
  • 变差缩减性
  • 递归线性求解方法
  • 细分性
  • ···
• Bernstein多项式逼近示例
  • 逼近结果优秀
  • 需要高阶
• 丰富的理论：CAGD 课程（计算机辅助几何设计）

Bernstein 函数

$$B_n(f,x)=\sum _{j=0}^{n}f({\displaystyle \frac{j}{n}})b_{n,j}(x)$$

• 蓝色为采样点，红色线为 Bernstein 多项式拟合出来的结果
• 当 $n\to \mathrm{\infty }$，即采样点足够多的时候，$B_n(f,x)$ 一致收敛到 $f(x)$

两种观点

• 代数观点
  • 权性
  • 把 $f({\displaystyle \frac{i}{n}})$ 看作是一系列的点，$b_{n,f}(x)$ 对其进行加权，得到新的点
• 几何观点
  • $b_{n,f}(x)$ 是一系列的函数，使用系数 $f({\displaystyle \frac{i}{n}})$ 去组合它，得到新的函数
• 这两种观点可以用于之后的交互式设计控制顶点、曲线的设计

RBF 函数插值/逼近

• 低维中叫高斯函数

高斯函数

• Gauss
• 两个参数：均值 $\mu$，方差 $\sigma$

$$g_{\mu ,\sigma }(x)={\displaystyle \frac{1}{\sqrt{2\pi }}}\exp (-{\displaystyle \frac{(x-\mu {)}^2}{2{\sigma }^2}})$$

• 几何意义
  • $\mu$：位置
  • $\sigma$：支集宽度

• 标准高斯函数

$$g_{0,1}={\displaystyle \frac{1}{\sqrt{2\pi }}}\exp (-{\displaystyle \frac{x^2}{2}})$$

• 不同均值和方差的高斯函数都线性无关
  • 可以作为一组基函数

RRF 函数拟合

• RBF 函数

$$f(x)=b_0+\sum _{i=1}^n{b}_i{g}_i(x)$$

• 一个通用的方法
  • 给定一些采样点，在这些采样点的周围放置一些基函数
  • 待定系数，求导得出结果

• 一些问题
  • 需要人为选取 $\mu ,\sigma$

• 怎么控制选取 $\mu ,\sigma$
  • 能否将 $\sigma ,\mu$ 一起来优化？
    • 可以的

从另一个角度来看拟合函数

Guass 拟合函数

• 一般 Gauss 函数表达为标准 Gauss 函数的形式

$$\begin{array}{rl}{g}_{\mu ,\sigma }(x)& ={\displaystyle \frac{1}{\sqrt{2\pi }}}\exp (-{\displaystyle \frac{(x-\mu {)}^2}{2{\sigma }^2}})\\ & ={\displaystyle \frac{1}{\sqrt{2\pi }}}\exp (-{\displaystyle \frac{1}{2}}{({\displaystyle \frac{x}{\sigma }}-{\displaystyle \frac{\mu }{\sigma }})}^2)\\ & =g_{0,1}({\displaystyle \frac{1}{\sigma }}x-{\displaystyle \frac{\mu }{\sigma }})\\ & =g_{0,1}(ax+b)\end{array}$$

• 将上面的函数进行转化
  • 此时可以同时优化 $\mu ,\sigma$

$$f(x)=b_0+\sum _{i=1}^n{b}_i{g}_i(x)$$

$$f(x)={\omega }_0+\sum _{i=1}^n{\omega }_i{g}_{0,1}(a_{i}x+b_i)$$

• 基函数是由一个基本函数通过平移和伸缩变换而来的

• 理论上可以证明：$a_i,b_i$ 足够多，上述多项式也能逼近所有的函数

换个方式看函数：神经网络

• 将Gauss函数看成网络
  • $(x,1)$ 是齐次坐标的用法，可以把平移也结合进去

• 这就是 RBF 网络
• $n$ 对应隐层结点个数，激活函数是标准高斯函数

抽象：神经元

RBF 神经网络

• 高维情形：RBF (Radial Basis Function)，径向基函数
• 一种特殊的 BP 网络
  • 优化：BP 算法
    • 反向传播
• 核函数思想
• Gauss 函数的特性：拟局部性
• 求 $a_i,b_i$时候需要求导，结果是非线性非凸的，很难求出极值
  • 落入局部极值
  • 初值选取很重要
• 神经网络就是一个函数

思考：激活函数的选择

• 启发：由一个简单的函数通过（仿射）变换构造出一组基函数，张成一个函数空间
• 表达能力是否足够强：是否完备/稠密的？

高维情形：多元函数

• 每一个神经元的输入是 $(x_1,\cdots ,x_n)$ 的齐次坐标 $(x_1,\cdots ,x_n,1)$
  • 变量的多个分量的线性组合： $g_{0,1}(a_i^1{x}_1+\cdots +a_n^i{x}_n+b_i)$
• 单隐层神经网络函数

$$f(x_1,\cdots ,x_n)={\omega }_0+\sum _{i=1}^n{w}_i{g}_{0,1}(a_i^1{x}_1+\cdots +a_n^i{x}_n+b_i)$$

多层神经网络

• 单层

• 多层
  • 线性函数和非线性函数的多重复合

用神经网络函数来拟合数据

• 回归问题
• Regression problem:
  • Input: Given training set (x1, y1), (x2, y2), (x3, y3 ),...
  • Output: Adjust parameters $\theta$ (for every node) to make: $h(x_i)\approx y_i$

万能逼近定理：自由度足够多

• 与传统拟合一样存在同样的问题：函数个数如何选?
  • 调参

使用深度学习的方法

• 问题建模
  • 理解问题、问题分解（多个映射级联）、…
• 找哪个？
  • 损失函数、各种 Penalty、正则项、…
• 到哪找？
  • 神经网络函数、网络简化、···
• 怎么找？
  • 优化方法（BP方法）
  • 初始值、参数、···
• 调参：有耐心、有直觉、···