跳到主要内容

线性最小二乘法推导

· 阅读需 6 分钟

代数形式​

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

假设数据点为 (x1,y1),(x2,y2),…,(xm,ym)(x_1, y_1), (x_2, y_2),\dots,(x_m, y_m) ，使用如下一次函数去拟合：

y=w1x+w0y = w_1 x + w_0

对于 xix_i ，采用上述函数计算出的结果记为 yi^\hat{y_i} ，即：

yi^=w1xi+w0\hat{y_i} = w_1 x_i+w_0

定义差距为：

∑i=1m(yi−yi^)2\sum_{i=1}^m (y_i - \hat{y_i})^2

现需要最小化这个差距。显然，上式为关于 w_0w\_0 和 w_1w\_1 的函数（损失函数）。为了方便，将 ∑_i=1m\sum\limits\_{i=1}^m 简记为 ∑\sum ，记：

f(w0,w1)=∑(yi−yi^)2=∑(yi−(w1xi+w0))2=∑(yi2−2yixiw1−2yiw0+xi2w12+w02+2xiw0w1)\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}

分别对 w0,w1w_0, w_1 求偏导：

∂f∂w0=∑(−2yi+2w0+2xiw1)=−2∑yi+2mw0+2w1∑xi∂f∂w1=∑(−2xiyi+2xi2w1+2w0xi)=−2∑xiyi+2w1∑xi2+2w0∑xi\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}

令：

∂f∂w0=0∂f∂w1=0\begin{split} \frac {\partial f} {\partial w_0} &= 0 \\ \frac {\partial f} {\partial w_1} &= 0 \\ \end{split}

得：

mw0+w1∑xi=∑yiw1∑xi2+w0∑xi=∑xiyi\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}

联立上面两式可得：

w0=∑xi∑xiyi−∑yi∑xi2(∑xi)2−m∑xi2w1=∑xi∑yi−m∑xiyi(∑xi)2−m∑xi2\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}

注意， ∑xi2≠(∑xi)2\sum{x_i^2} \ne (\sum{x_i})^2 ，计算时要细心。

矩阵形式​

记 X\mathbf{X} 为 m×nm\times n 的矩阵，表示有 mm 个样本点，特征维数为 nn 维； y\mathbf{y} 为 mm 维列向量，表示这 mm 个样本点的实际值； y^\mathbf{\hat{y}} 为 mm 维列向量，表示这 mm 个样本点的估计值； w\mathbf{w} 为 nn 维列向量，且：

y^=Xw\mathbf{\hat{y}} = \mathbf{X}\mathbf{w}

则：

y−y^=y−Xw\mathbf{y} - \mathbf{\hat{y}} = \mathbf{y} - \mathbf{X}\mathbf{w}

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

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

现要求 ∂f∂w\frac {\partial f} {\partial \mathbf{w}} ，可 w\mathbf{w} 是个向量呀，这个该怎么求呢？

预备知识​

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

∂f∂x=[∂fx1∂fx2…∂fxn]\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}

其中， x=[x1,x2,…,xn]T\mathbf{x}= \left[x_1, x_2, \dots, x_n\right]^{\rm T} 为 nn 维列向量， ff 是 x\mathbf{x} 上 ℜn→ℜ\Re^n \to \Re 的函数（也就是， ff 的输入是 nn 维列向量，输出是实数）

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

∂y∂x=[∂y1∂x1∂y1∂x2…∂y1∂xn∂y2∂x1∂y2∂x2…∂y2∂xn⋮⋮⋱⋮∂ym∂x1∂ym∂x2…∂ym∂xn]\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}

即：

(∂y∂x)ij=∂yi∂xj(\frac {\partial \mathbf{y}} {\partial \mathbf{x}})_{ij} = \frac{\partial{y_i}}{\partial x_j}

其中， x=[x1,x2,…,xn]T\mathbf{x}= \left[x_1, x_2, \dots, x_n\right]^{\rm T} 为 nn 维列向量， y\mathbf{y} 是定义在 x\mathbf{x} 上 ℜn→ℜm\Re^n \to \Re^m 的函数（也就是， y\mathbf{y} 的输入是 nn 维列向量，输出是 mm 维列向量），上面的矩阵称为雅可比（Jacobi）矩阵。

【链式求导】

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

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

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

计算过程​

记 u(w)=y−Xw\mathbf{u(\mathbf{w})} = \mathbf{y} - \mathbf{X}\mathbf{w} ，则：

f=uTu=∑iui2\begin{split} f &= \mathbf{u}^{\rm T} \mathbf{u} \\ &= \sum\nolimits_i {u_i^2} \\ \end{split} ∂f∂u=[∂∑iui2∂u1∂∑iui2∂u2…∂∑iui2∂ui]=[2u12u2…2ui]=2[u1u2…ui]=2uT\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} u=y−Xw=[y1y2⋮ym]−[x11x12…x1nx21x22…x2n⋮⋮⋱⋮xm1xm2…xmn][w1w2⋮wn]=[y1−∑x1iwiy2−∑x2iwi⋮ym−∑xmiwi]\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} (∂u∂w)ij=∂ui∂wj=∂(yi−(xi1w1+xi2w2+⋯+xinwn))∂wj=−xij\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} ∂u∂w=−X\frac{\partial \mathbf{u}}{\partial \mathbf{w}} = - \mathbf{X}

使用链式求导：

∂f∂w=∂f∂u∂u∂w=2uT(−X)=−2(y−Xw)TX=−2(yT−(Xw)T)X=−2(yT−wTXT)X=−2(yTX−wTXTX)\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}

令：

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

得：

wTXTX=yTX\mathbf{w}^{\rm T}\mathbf{X}^{\rm T}\mathbf{X} = \mathbf{y}^{\rm T}\mathbf{X}

若 XTX\mathbf{X}^{\rm T}\mathbf{X} 可逆，则两边同时右乘 (XTX)−1(\mathbf{X}^{\rm T}\mathbf{X})^{-1} ，得：

wT=yTX(XTX)−1\mathbf{w}^{\rm T} = \mathbf{y}^{\rm T}\mathbf{X}(\mathbf{X}^{\rm T}\mathbf{X})^{-1}

两边同时转置：

w=(yTX(XTX)−1)T=((XTX)−1)TXT(yT)T=((XTX)T)−1XTy=(XT(XT)T)−1XTy=(XTX)−1XTy\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}