线性最小二乘法推导

代数形式

最小二乘法在中学时讲过。有一些散点有线性的趋势,用一个一次函数去拟合,使得差距最小化。

假设数据点为 $(x_1, y_1), (x_2, y_2),\dots,(x_m, y_m)$ ,使用如下一次函数去拟合:

$$ y = w_1 x + w_0 $$

对于 $x_i$ ,采用上述函数计算出的结果记为 $\hat{y_i}$ ,即:

$$ \hat{y_i} = w_1 x_i+w_0 $$

定义差距为:

$$ \sum_{i=1}^m (y_i - \hat{y_i})^2 $$

现需要最小化这个差距。显然,上式为关于 $w\_0$ 和 $w\_1$ 的函数(损失函数)。为了方便,将 $\sum\limits\_{i=1}^m$ 简记为 $\sum$ ,记:

$$ \begin{split} f(w_0, w_1) &= \sum (y_i - \hat{y_i})^2 \\ &= \sum (y_i - (w_1 x_i + w_0))^2 \\ &= \sum (y_i^2 - 2y_ix_iw_1 - 2y_iw_0 + x_i^2w_1^2 + w_0^2 + 2x_iw_0w_1) \\ \end{split} $$

分别对 $w_0, w_1$ 求偏导:

$$ \begin{split} \frac {\partial f} {\partial w_0} &= \sum (-2y_i + 2w_0 + 2x_iw_1) \\ &= -2 \sum {y_i} + 2mw_0 + 2w_1 \sum {x_i} \\ \frac {\partial f} {\partial w_1} &= \sum (-2x_iy_i + 2x_i^2w_1 + 2w_0x_i) \\ &= -2\sum{x_iy_i} + 2w_1\sum {x_i^2} + 2w_0\sum {x_i} \\ \end{split} $$

令:

$$ \begin{split} \frac {\partial f} {\partial w_0} &= 0 \\ \frac {\partial f} {\partial w_1} &= 0 \\ \end{split} $$

得:

$$ \begin{split} mw_0 + w_1\sum{x_i} &= \sum{y_i} \\ w_1\sum{x_i^2} + w_0\sum{x_i} &= \sum{x_i}{y_i} \\ \end{split} $$

联立上面两式可得:

$$ \begin{split} w_0 &= \frac {\sum{x_i}\sum{x_i y_i} - \sum{y_i}\sum{x_i^2}} {(\sum{x_i})^2 - m\sum{x_i^2}} \\ w_1 &= \frac {\sum{x_i}\sum{y_i} - m\sum{x_i y_i}} {(\sum{x_i})^2 - m\sum{x_i^2}} \\ \end{split} $$

注意, $\sum{x_i^2} \ne (\sum{x_i})^2$ ,计算时要细心。

矩阵形式

记 $\mathbf{X}$ 为 $m\times n$ 的矩阵,表示有 $m$ 个样本点,特征维数为 $n$ 维; $\mathbf{y}$ 为 $m$ 维列向量,表示这 $m$ 个样本点的实际值; $\mathbf{\hat{y}}$ 为 $m$ 维列向量,表示这 $m$ 个样本点的估计值; $\mathbf{w}$ 为 $n$ 维列向量,且:

$$ \mathbf{\hat{y}} = \mathbf{X}\mathbf{w} $$

则:

$$ \mathbf{y} - \mathbf{\hat{y}} = \mathbf{y} - \mathbf{X}\mathbf{w} $$

上式的结果是一个列向量,而我们需要的是其平方和。根据矩阵乘法的定义,损失函数为:

$$ f(\mathbf{w}) = (\mathbf{y} - \mathbf{X}\mathbf{w})^{\rm T}(\mathbf{y} - \mathbf{X}\mathbf{w}) $$

现要求 $\frac {\partial f} {\partial \mathbf{w}}$ ,可 $\mathbf{w}$ 是个向量呀,这个该怎么求呢?

预备知识

【实数值函数对向量求导】

$$ \frac {\partial f} {\partial \mathbf{x}} = \begin{bmatrix} \frac{\partial f}{x_1} & \frac{\partial f}{x_2} & \dots & \frac{\partial f}{x_n} \\ \end{bmatrix} $$

其中, $\mathbf{x}= \left[x_1, x_2, \dots, x_n\right]^{\rm T}$ 为 $n$ 维列向量, $f$ 是 $\mathbf{x}$ 上 $\Re^n \to \Re$ 的函数(也就是, $f$ 的输入是 $n$ 维列向量,输出是实数)

【向量值函数对向量求导】

$$ \frac {\partial \mathbf{y}} {\partial \mathbf{x}} = \begin{bmatrix} \frac{\partial{y_1}}{\partial x_1} & \frac{\partial{y_1}}{\partial x_2} & \dots & \frac{\partial{y_1}}{\partial x_n} \\ \frac{\partial{y_2}}{\partial x_1} & \frac{\partial{y_2}}{\partial x_2} & \dots & \frac{\partial{y_2}}{\partial x_n} \\ \vdots & \vdots & \ddots & \vdots \\ \frac{\partial{y_m}}{\partial x_1} & \frac{\partial{y_m}}{\partial x_2} & \dots & \frac{\partial{y_m}}{\partial x_n} \\ \end{bmatrix} $$

即:

$$ (\frac {\partial \mathbf{y}} {\partial \mathbf{x}})_{ij} = \frac{\partial{y_i}}{\partial x_j} $$

其中, $\mathbf{x}= \left[x_1, x_2, \dots, x_n\right]^{\rm T}$ 为 $n$ 维列向量, $\mathbf{y}$ 是定义在 $\mathbf{x}$ 上 $\Re^n \to \Re^m$ 的函数(也就是, $\mathbf{y}$ 的输入是 $n$ 维列向量,输出是 $m$ 维列向量),上面的矩阵称为雅可比(Jacobi)矩阵

【链式求导】

设 $\mathbf{x}$ 为列向量,复合函数 $\mathbf{h(\mathbf{x}) = \mathbf{f(\mathbf{g(\mathbf{x})})}}$ ,其中向量值函数(也就是函数的值域是向量)$\mathbf{f(\mathbf{g})}$ 和 $\mathbf{g(\mathbf{x})}$ 均可微,则:

$$ \mathbf{h}^\prime(\mathbf{x}) = \mathbf{f}^\prime(\mathbf{g(\mathbf{x})})\mathbf{g}^\prime(\mathbf{x}) $$

和代数形式的链式求导类似。

计算过程

记 $\mathbf{u(\mathbf{w})} = \mathbf{y} - \mathbf{X}\mathbf{w}$ ,则:

$$ \begin{split} f &= \mathbf{u}^{\rm T} \mathbf{u} \\ &= \sum\nolimits_i {u_i^2} \\ \end{split} $$

$$ \begin{split} \frac {\partial f} {\partial \mathbf{u}} &= \begin{bmatrix} \frac {\partial {\sum\nolimits_i {u_i^2}}} {\partial {u_1}} & \frac {\partial {\sum\nolimits_i {u_i^2}}} {\partial {u_2}} & \dots & \frac {\partial {\sum\nolimits_i {u_i^2}}} {\partial {u_i}} \\ \end{bmatrix} \\ &= \begin{bmatrix} 2u_1 & 2u_2 & \dots & 2u_i \end{bmatrix} \\ &= 2 \begin{bmatrix} u_1 & u_2 & \dots & u_i \end{bmatrix} = 2 \mathbf{u}^{\rm T}\\ \end{split} $$

$$ \begin{split} \mathbf{u} &= \mathbf{y} - \mathbf{X}\mathbf{w} \\ &= \begin{bmatrix} y_1 \\ y_2 \\ \vdots \\ y_m \\ \end{bmatrix} - \begin{bmatrix} x_{11} & x_{12} & \dots & x_{1n} \\ x_{21} & x_{22} & \dots & x_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ x_{m1} & x_{m2} & \dots & x_{mn} \\ \end{bmatrix} \begin{bmatrix} w_1 \\ w_2 \\ \vdots \\ w_n \\ \end{bmatrix} \\ &= \begin{bmatrix} y_1 - \sum {x_{1i}w_i} \\ y_2 - \sum {x_{2i}w_i} \\ \vdots \\ y_m - \sum {x_{mi}w_i} \\ \end{bmatrix} \\ \end{split} $$

$$ \begin{split} (\frac{\partial {\mathbf{u}}}{\partial {\mathbf{w}}})_{ij} &= \frac{\partial u_i}{\partial w_j} \\ &= \frac{\partial (y_i - (x_{i1}w_1 + x_{i2}w_2 + \dots + x_{in}w_n))}{\partial w_j} \\ &= -x_{ij} \end{split} $$

$$ \frac{\partial \mathbf{u}}{\partial \mathbf{w}} = - \mathbf{X} $$

使用链式求导:

$$ \begin{split} \frac {\partial f} {\partial {\mathbf{w}}} &= \frac {\partial f} {\partial \mathbf{u}} \frac {\partial \mathbf{u}} {\partial \mathbf{w}} \\ &= 2 \mathbf{u}^{\rm T} (- \mathbf{X}) \\ &= -2(\mathbf{y} - \mathbf{X}\mathbf{w})^{\rm T}\mathbf{X} \\ &= -2 (\mathbf{y}^{\rm T} - (\mathbf{X}\mathbf{w})^{\rm T})\mathbf{X} \\ &= -2 (\mathbf{y}^{\rm T} - \mathbf{w}^{\rm T}\mathbf{X}^{\rm T}) \mathbf{X} \\ &= -2 (\mathbf{y}^{\rm T}\mathbf{X} - \mathbf{w}^{\rm T}\mathbf{X}^{\rm T}\mathbf{X}) \end{split} $$

令:

$$ \frac{\partial f}{\partial \mathbf{w}} = \mathbf{0} $$

得:

$$ \mathbf{w}^{\rm T}\mathbf{X}^{\rm T}\mathbf{X} = \mathbf{y}^{\rm T}\mathbf{X} $$

若 $\mathbf{X}^{\rm T}\mathbf{X}$ 可逆,则两边同时右乘 $(\mathbf{X}^{\rm T}\mathbf{X})^{-1}$ ,得:

$$ \mathbf{w}^{\rm T} = \mathbf{y}^{\rm T}\mathbf{X}(\mathbf{X}^{\rm T}\mathbf{X})^{-1} $$

两边同时转置:

$$ \begin{split} \mathbf{w} &= (\mathbf{y}^{\rm T}\mathbf{X}(\mathbf{X}^{\rm T}\mathbf{X})^{-1})^{\rm T} \\ &= ((\mathbf{X}^{\rm T}\mathbf{X})^{-1})^{\rm T}\mathbf{X}^{\rm T}(\mathbf{y}^{\rm T})^{\rm T} \\ &= ((\mathbf{X}^{\rm T}\mathbf{X})^{\rm T})^{-1}\mathbf{X}^{\rm T}\mathbf{y} \\ &= (\mathbf{X}^{\rm T}(\mathbf{X}^{\rm T})^{\rm T})^{-1}\mathbf{X}^{\rm T}\mathbf{y} \\ &= (\mathbf{X}^{\rm T}\mathbf{X})^{-1}\mathbf{X}^{\rm T}\mathbf{y} \\ \end{split} $$

AI

上一篇 解决Dia在Linux上的输入法问题
下一篇 向量微积分基础

添加新评论

*
*