Lecture 02 数据拟合
-
假定：仅函数形式，一般曲线（非函数形式）后续再讲
\(f:R^1\rightarrow R^1\\y=f(x)\)
函数拟合问题
- 输入：一些观察（采样）的数据点的数据点\(\{x_i,y_i\}_{i=0}^n\)
- 输出：拟合数据点的函数\(y=f(x)\)，并用于观测
拟合函数的“好坏”
- 分段线性插值函数\(y=f_1(x)\)
- 数据误差为0
- 函数性质不够好：只有\(C^0\)连续，不光滑（数值计算），不可求导
- 光滑插值函数\(y=f_2(x)\)
- 数据误差为0
- 可能被“差数据”（噪声、outliers）带歪，导致函数性质不好、预测不可靠
- 逼近拟合误差\(y=f_3(x)\)
- 数据误差不为0，但足够小
求拟合函数：应用驱动
-
大部分的实际应用问题
- 可建模为：找一个映射/变换/函数
- 输入不一样、变量不一样、维数不一样
-
三部曲方法论：
-
到哪找？
-
确定某个函数集合/空间
-
确定函数的表达形式（函数集、空间）\(L=span\{b_0(x),...,b_n(x)\}\)
-
待定基函数的组合系数（求解变量）\(f_\lambda(x)=\sum_{k=0}^n\lambda_ib_i(x)\)
\(f由待定系数\lambda=\begin{pmatrix}\lambda_1\\...\\\lambda_n \end{pmatrix}确定\)
-
-
找哪个？
- 度量哪个函数是好多/“最好”的
- 优化模型（最小化问题）
- 能量项=data term 误差项 + 正则项
- 统计模型、规划模型
-
怎么找？
- 求解或优化：不同的优化方法与技巧，既要快、又要好
- 求解误差函数的驻点（导数为0之处）
- 转化为系数的方程组
- 如果是欠定的（有无穷多解），则修正模型
- 改进/增加各种正则项：Lasso、岭回归、稀疏正则项
- 返回修改模型
- 如果是欠定的（有无穷多解），则修正模型
-
多项式插值定理
定理：若\(x_i\)两两不同，则对任意给定的\(y_i\)，存在唯一的次数至多是\(n\)次的多项式\(p_n\)，使得\(p_n(x_i)=y_i, i=0,...,n\)
技巧1：构造插值问题的通用解
-
给的那个\(n+1\)个点\(\{(x_0,y_0),...,(x_n.y_n)\}\)，寻找一组次数为\(n\)的多项式基函数\(l_i\)使得\(l_i(x_j)=\begin{cases}1,若i=j\\ 0,若i\ne j \end{cases}\)
-
插值问题的解为：
\(P(x)=y_0l_0(x)+y_1l_1(x)+...+y_nl_n(x)=\sum_{i=0}^ny_il_i(x)\)
那么就可以预先计算不同\(x\)取值下的\(l\)，然后组合起来
-
怎么计算多项式\(l_i(x)\)？拉格朗日多项式
\(l_i(x)=\frac{\prod_{j\ne i}(x-x_j)}{\prod_{j\ne i}(x_i-x_j)}\)
技巧2：更方便的求解表达
Newton插值：具有相同“导数”（差商）的多项式构造（n阶Taylor展开）
Newton插值多项式表达为：
\(N_n(x)=f(x_0)+f[x_0,x_1](x-x_0)+...+f[x_0,x_1,...,x_n](x-x_0)...(x-x_{n-1})\)
前面做些预计算，将差商存起来
多项式插值存在的问题
-
系统矩阵稠密
求解慢
-
依赖于基函数选取，矩阵可能病态，导致难于求解（求逆）
-
对方程右边项或矩阵系数轻微扰动，求解结果与正解偏差巨大
-
矩阵条件数
刻画矩阵的病态程度
\(k_2(A)=\frac{\underset{x\ne 0}{max}\frac{\lVert Ax\rVert}{\lVert x\rVert}}{\underset{x\ne 0}{min}\frac{\lVert Ax\rVert}{\lVert x\rVert}}\)
- 等于最大特征值和最小特征值之间比例
- 条件数大意味着基元之间有太多相关性，系统不稳定
-
-
幂（单项式）函数基
- 幂函数之间差别随着次数增加而减小
- 不同幂函数之间唯一差别为增长速度(\(x^i比x^{i-1}增长快\))
-
趋势
- 好的基函数一般需要系数交替
- 互相抵消问题
-
解决方法：正交多项式基
- 能够互相抵消
- Gram-Schmidt正交化
-
Runge 龙格现象
多项式随着插值点数增加（可以是细微）而摆动
振荡现象和对插值点数的高度敏感性
总结
- 多项式插值不稳定
- 控制点的微小变化可导致完全不同的结果
- 振荡（Runge）现象
- 多项式随着插值点数增加（可以是细微）而摆动
- 需要更好的基函数来做插值
- Bernstein基函数
- 分片多项式
多项式逼近
为什么逼近
- 数据点含噪声、outliers等
- 更紧凑的表达
- 计算简单、更稳定
最小二乘逼近
-
逼近问题
- 给定一组线性无关的连续函数集合\(B=\{b_1,...,b_n\}\)和一组节点\(\{(x_1,y_1),...,(x_m,y_m)\}\)，其中\(m>n\)
- 在B张成空间中哪个函数\(f\in span(B)对结点逼近最好\)？
- 怎么定义“最佳逼近”
-
最小二乘逼近
\(\underset{f\in span(B)}{argmin}\sum_{j=1}^m(f(x_j)-y_j)^2\)
要求表达式极小值，这个表达式可以看作是基函数系数\(\lambda_1,...,\lambda_n\)的函数，也就是要对其求偏导为0，于是就有了从\(\lambda_1\)到\(\lambda_n\)的方程组
于是\(\sum_{j=1}^m(f(x_j)-y_j)^2 = \sum_{j=1}^m(\sum_{i=1}^n\lambda_ib_i(x_j)-y_j)^2\\ = (M\lambda-y)^T(M\lambda-y)\\ = \lambda^TM^TM\lambda-y^TM\lambda-\lambda^TM^Ty+y^Ty\\ = \lambda^TM^TM\lambda-2y^TM\lambda+y^Ty\)
其中\(M=\begin{pmatrix}b_i(x_1)& ... & b_n(x_1)\\... & ... & ...\\ b_1(x_m) & ... & b_n(x_m) \end{pmatrix}\)
-
求解
-
关于\(\lambda\)的二次多项式
\(\lambda^TM^TM\lambda-2y^TM\lambda+y^Ty\)
-
法方程
-
最小解满足
\(M^TM\lambda=M^Ty\)
-
-
提示
- 最小化二次目标函数\(x^TAx+b^Tx+c\)
- 充分必要条件:\(2Ax=-b\)
-
函数空间及基函数
为什么用多项式？
-
易于计算，表现良好，光滑，...
-
稠密选哪个与完备性：表达能力足够
-
Weierstrass定理证明了多项式的存在
-
Weierstrass只证明了存在性，未给出多项式
-
用Bernstein多项式做逼近
-
回忆伯恩斯坦多项式
伯恩斯坦多项式相当于对1自己的\(n\)阶展开，因此从图上可以看到，任意时间\(t\)，画一条竖线，四个竖线交点的值相加等于\(1\)，图中是3阶展开
图中是各阶的Bernstein多项式（从0阶开始）
-
Bernstein基函数的良好性质：非常好的集合意义！
- 正性（每个基函数都大于0）、权性（和为1）\(\rightarrow\)凸包性
- 变差缩减性
- 递归线性求解方法
- 细分性
- ...
-
Bernstein多项式逼近示例
- 逼近结果优秀（500阶逼近都没有龙格现象）
- 需要高阶
-
关于Bernstein函数
-
\(B_n(f,x)=\sum_{j=0}^nf(\frac{i}{n}b_{n,j}(x))\)
-
两种观点
几何观点、代数观点
图中示例蓝点为\(f(\frac{i}{n})\)，用Bernstein基组合得到左侧\(B_n(f,x)\)（红色函数上对应点），只要采样点足够密，组合出来的函数依次收敛到\(f(x)\)，会越来越靠近真实的函数
- 代数观点：将\(f(\frac{i}{n})\)视为集合，用右边的系数组合它（因为有权性，可以视为加权 ），得到函数
- 几何观点：用一系列系数(\(f(\frac{i}n)\))去组合基函数得到函数
-
-
-
RBF函数插值/逼近
RBF在高维中叫的多，在低维中一般叫Gauss函数
-
Gauss函数
-
两个参数：均值\(\mu\)，方差\(\sigma\)
\(g_{\mu,\sigma}(x)=\frac{1}{\sqrt{2\pi}} e^{-\frac{(x-\mu)^2}{2\sigma^2}}\)
另一种形式\(g_{\mu,\sigma}(x)=\frac{1}{\sqrt{2\pi}\sigma} e^{-\frac{(x-\mu)^2}{2\sigma^2}}\)，分母多了个\(\sigma\)，是为了归一化，使得高斯面积积分为1，变成一个概率函数
-
几何意义：
- 均值\(\mu\)：位置
- 方差\(\sigma\)：支集宽度（胖瘦）
-
不同均值和方差的Gauss都线性无关
- 那么就可以张成一个空间，组合起来表达函数
-
-
RBF函数拟合
-
RBF函数
\(f(x)=b_0+\sum_{i=1}^nb_ig_i(x)\)
对其求导可以得到\(b_i\)的方程
-
方法
将基函数组合起来表达一个函数
-
原因
-
\(\mu\)和\(\sigma\)可以一起优化
-
Gauss拟合函数
将一般Gauss表达为标准Gauss函数的形式（\(\mu\)为0，\(\sigma\)为1）
\(g_{\mu,\sigma}(x)=\frac{1}{\sqrt{2\pi}}e^{-\frac{(x-\mu)^2}{2\sigma^2}}\\ = \frac{1}{\sqrt{2\pi}}e^{2\frac{1}{2}(\frac{x}{\sigma}-\frac{\mu}{\sigma})^2} = g_{0,1}(ax+b)\)
其中\(a=\frac{x}{\sigma},b=-\frac{\mu}{\sigma}\)
那么\(f(x)=b_0+\sum_{i=1}^nb_ig_i(x)\\\downarrow\\f(x)=\omega_o+\sum_{i=1}^n\omega_ig_{0,1}(a_ix+b_i)\)
这里的基函数是由一个基本函数（标准Gauss）通过平移和伸缩变换而来的（仿射变换）
-
-
将Gauss函数看出网络
\(f(x)=\omega_o+\sum_{i=1}^n\omega_ig_{0,1}(a_ix+b_i)\)
将\(x\)看作两维\((x,1)\)（齐次坐标），\(\begin{pmatrix}x\\1\end{pmatrix}\)乘上\(\begin{pmatrix}a_i & b_i\end{pmatrix}\)，将不同\(x\)与不同\(a_i,b_i\)(网络线上的权)，组合起来，得到要求的函数
- 公式中的\(n\)不知道有多少，\(n\)对应的是网络中的结点数，这是一个调节的参数
- 这个网络也叫RBF网络
-
RBF神经网络
-
高维情况：RBF （Radial Basis Function），径向基函数
-
一种特殊的BP网络
-
优化：BP算法
非凸非线性的函数求不出全局极小值，只能找到局部极小值
选择好的初值，找到一个还不错的极小值还是可以的
如果有物理意义，找物理意义对应的初值
-
-
核函数思想
-
Gauss函数的特性：拟局部性
-
-