Least Squares

2017-03-01

4 minute read

math , optimization

要理解 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{equation} \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} \end{equation} $$

$$ (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 $$

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