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 - (ax_i+b))^2
$$

这个式子的本质是 当$a,b$是一个很好的 fitting 参数的时候,均值应该很小可以省略掉,那么 $E(a,b)$ 其实就是 $y_i - (ax_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-(ax_i+b))\cdot (-x_i) \ \frac{\partial E}{\partial b} = \sum_{i=1}^n 2(y_i-(ax_i+b))\cdot 1
$$

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

$$
\begin{pmatrix}
a \ b
\end{pmatrix}
=
{\begin{pmatrix}
\sum x_i^2 & \sum x_i \ \sum x_i & \sum 1
\end{pmatrix}}^{-1}
\begin{pmatrix}
\sum x_iy_i \ \sum y_i
\end{pmatrix}
$$

$$
(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 W X) \beta = X^T W y
$$

这里 $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} + \Delta\beta_j
$$

$t$是迭代次数, $ \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}\Delta \beta_j
$$

$J$ 是 Jacobian,

这个情况下, 设 $\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)) \
= \Delta y_i - \sum_{s=1}^{k}J_{is}\Delta \beta_s
$$

代入梯度方程

$$
\sum_i r_i \frac{\partial r_i}{\partial \beta_j} = \sum_i (\Delta y_i - \sum_{s=1}^{k}J_{is}\Delta \beta_s) J_{ij}
$$

这些梯度方程可以变形为

$$
\sum_i \sum_s J_{ij} J_{is} \Delta \beta_s = \sum_i J_{ij} \Delta y_i
$$

写成矩阵形式就是

$$
(J^T J) \Delta \beta = J^T \Delta y
$$

Weighted sum 形式

$$
(J^TW J) \Delta \beta = J^T W\Delta y
$$

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