Least Squares

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

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

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

Example

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

$$E(a,b)=\sum _{i=1}^n(y_i-(a{x}_i+b){)}^2$$

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

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

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

$$\frac{\partial E}{\partial a}=0,\frac{\partial E}{\partial b}=0$$

$$\frac{\partial E}{\partial a}=\sum _{i=1}^{n}2(y_i-(a{x}_i+b))\cdot (-x_i)\frac{\partial E}{\partial b}=\sum _{i=1}^{n}2(y_i-(a{x}_i+b))\cdot 1$$

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

$$\left(\begin{array}{c}a\\ b\end{array}\right)={\left(\begin{array}{cc}\sum x_i^2& \sum x_i\\ \sum x_i& \sum 1\end{array}\right)}^{-1}\left(\begin{array}{c}\sum x_i{y}_i\\ \sum y_i\end{array}\right)$$

$$(X^{T}X)\beta =X^{T}y$$

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

Weighted least squares 则可以表达为

$$(X^{T}WX)\beta =X^{T}Wy$$

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

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

$$\frac{\partial E}{\partial {\beta }_j}=2\sum _i{r}_i\frac{\partial r_i}{\partial {\beta }_j},j=1,\cdots ,k,i=1,\cdots ,n$$

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

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

$${\beta }_j\approx {\beta }_j^{t+1}={\beta }_j^t+\mathrm{\Delta }{\beta }_j$$

$t$是迭代次数， $\mathrm{\Delta }{\beta }_j$ 是一个 shift vector， 然后每一步迭代的时候，用一阶泰勒展开来线性化 。

$$f(x_i,\beta )\approx f(x_i,{\beta }^t)+\sum _j\frac{\partial f(x_i,{\beta }^t)}{\partial {\beta }_j}({\beta }_j-{\beta }_j^t)\approx f(x_i,{\beta }^t)+\sum _j{J}_{ij}\mathrm{\Delta }{\beta }_j$$

$J$ 是 Jacobian，

这个情况下， 设 $\mathrm{\Delta }{y}_i=y_i-f(x_i,{\beta }^k)$

residual 可以写成

$$r_i=y_i-f(x_i,\beta )=(y_i-f(x_i,{\beta }^t))+(f(x_i,{\beta }^t)-f(x_i,\beta ))=\mathrm{\Delta }{y}_i-\sum _{s=1}^k{J}_{is}\mathrm{\Delta }{\beta }_s$$

代入梯度方程

$$\sum _i{r}_i\frac{\partial r_i}{\partial {\beta }_j}=\sum _i(\mathrm{\Delta }{y}_i-\sum _{s=1}^k{J}_{is}\mathrm{\Delta }{\beta }_s)J_{ij}$$

这些梯度方程可以变形为

$$\sum _i\sum _s{J}_{ij}{J}_{is}\mathrm{\Delta }{\beta }_s=\sum _i{J}_{ij}\mathrm{\Delta }{y}_i$$

写成矩阵形式就是

$$(J^{T}J)\mathrm{\Delta }\beta =J^T\mathrm{\Delta }y$$

Weighted sum 形式

$$(J^{T}WJ)\mathrm{\Delta }\beta =J^{T}W\mathrm{\Delta }y$$

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