Least Squares

algorithm


要理解least squares,我们决定通过一个最简单的例子,那就是一元线性拟合

我们观测到了$n$对值$(x_i,y_i), i = 1, \cdots, n$

我们现在用找到一条直线来拟合这堆数据 $y = ax + b $

Example

最小二乘的表示形式是 一个 error表达式

这个式子的本质是 当$a,b$是一个很好的fitting参数的时候,均值应该很小可以省略掉,那么 $E(a,b)$ 其实就是 $y_i - (ax_i+b)$ 的方差的$n$倍

我们的优化目标其实就是最小这个error,这样暗含的就是你找出了一组参数拟合了一个model,在和目标值的error的分布上,是0均值,最小方差的。

求解的方法很简单就是对参数$a$和$b$当作未知数来求导,这里一阶导数为0的时候必定是极值,单变量的时候 梯度gradient 就是导数。

这里可以写成$a,b$ 行列式形式

where $X = [x^k, x^k-1, \cdots, x^0]$, $k$ is the order. here $k=1$. 这里的$\beta$就是我们的coefficient, 有时候也叫做estimator

Weighted least squares 则可以表达为

这里 $f(x, \beta)$ 如果是 non linear 则 是 非线性的最小二乘

设 $r_i$ 为 residual, 则 梯度方程

这样一组equations没有 closed form的解。

因此用iteration的方法来调整参数

$t$是迭代次数, $ \Delta\beta_j$ 是一个 shift vector, 然后每一步迭代的时候,用一阶泰勒展开来线性化 。

$J$ 是Jacobian,

这个情况下, 设 $\Delta y_i = y_i - f(x_i, \beta^k)$

residual 可以写成

代入梯度方程

这些梯度方程可以变形为

写成矩阵形式就是

Weighted sum 形式

这也是高斯牛顿迭代法的基本思想,用泰勒级数展开去近似的代替非线性模型,然后通过多次迭代修正系数来逼近。