[ML Notes] 线性回归:Normal Equation
Contents [show]
1. 基本形式
线性回归的形式为一系列特征的线性组合
f(x)=w0+w1x1+w2x2+⋯+wnxn
其中 xi 为特征,wi 为参数。w0 为偏置,w1,w2,…,wn 为对应特征的权重。
令
\boldsymbol{w} = \begin{bmatrix} w_0 \\ w_1 \\ w_2 \\ \vdots \\ w_n \end{bmatrix}, \; \boldsymbol{x} = \begin{bmatrix} 1 \\ x_1 \\ x_2 \\ \vdots \\ x_n \end{bmatrix}
则式 (1) 可以写为
f(\boldsymbol{x}) = \boldsymbol{w}^\mathrm{T} \boldsymbol{x} \tag{2}
对于式 (2) 所示的模型,希望能找到合适的参数 \boldsymbol{w},使得预测值 f(\boldsymbol{x}) 和真实值 y 间的差别最小。选择 \boldsymbol{w} 的关键在于如何衡量 f(\boldsymbol{x}) 和 y 之间的差别,即预测误差带来的损失。如定义损失为误差的平方和或均方误差,代价函数可以定义为
J(\boldsymbol{w}) =\frac{1}{2} \sum_{i=1}^m \big( y^{(i)} – f(\boldsymbol{x}^{(i)}) \big)^2 \tag{3}
其中 m 为样例总数,\boldsymbol{x}^{(i)} 和 y^{(i)} 分别为第 i 个样例的特征和标签。
记
X = \begin{bmatrix} — \big( \boldsymbol{x}^{(1)}\big)^\mathrm{T} — \\ — \big( \boldsymbol{x}^{(2)}\big)^\mathrm{T} — \\ \vdots \\ — \big( \boldsymbol{x}^{(m)}\big)^\mathrm{T} — \\ \end{bmatrix} , \; \boldsymbol{y} = \begin{bmatrix} y^{(1)} \\ y^{(2)} \\ \vdots \\ y^{(m)} \end{bmatrix}
此时模型可以写为
\boldsymbol{f}(X) = \begin{bmatrix} \big( \boldsymbol{x}^{(1)} \big)^\mathrm{T} \boldsymbol{w} \\ \big( \boldsymbol{x}^{(2)} \big)^\mathrm{T} \boldsymbol{w} \\ \vdots \\ \big( \boldsymbol{x}^{(m)}\big)^\mathrm{T} \boldsymbol{w} \end{bmatrix} = X \boldsymbol{w} \tag{4}
于是
\boldsymbol{y} – \boldsymbol f(X) = \boldsymbol{y} – X \boldsymbol{w}
故式 (3) 也可以写为
J(\boldsymbol{w}) = \frac{1}{2} ||\boldsymbol{y} – X \boldsymbol{w}||_2^2 = \frac{1}{2} (\boldsymbol{y} – X \boldsymbol{w})^\mathrm{T} (\boldsymbol{y} – X \boldsymbol{w}) \tag{5}
基于均方误差最小化对模型参数进行求解的方法称为最小二乘法(least square method)。
2. Normal Equation
结合以下规则
- 对 \mathbb{R}^n 中的向量 \boldsymbol{a} 和 \boldsymbol{b},有 \boldsymbol{a}^\mathrm{T}\boldsymbol{b} = \boldsymbol{b}^\mathrm{T}\boldsymbol{a};
- 对 f: \mathbb{R}^n \rightarrow \mathbb{R} 的函数 f(\boldsymbol{x}) = \boldsymbol{a}^\mathrm{T} \boldsymbol{x},有 \nabla f(\boldsymbol{x}) = \boldsymbol{a};
- 对 g: \mathbb{R}^n \rightarrow \mathbb{R} 的函数 g(\boldsymbol{x}) = \boldsymbol{x}^\mathrm{T} \boldsymbol{A} \boldsymbol{x},其中 \boldsymbol{A} 为 n \times n 的对称矩阵, 有 \nabla g(\boldsymbol{x}) = 2 \boldsymbol{A} \boldsymbol{x}。
计算式 (4) 关于 w 的梯度,可得
\begin{aligned} \nabla_{\boldsymbol{w}} J &= \nabla_{\boldsymbol{w}} \frac{1}{2} (\boldsymbol{y} – X \boldsymbol{w})^\mathrm{T} (\boldsymbol{y} – X \boldsymbol{w}) \\ &= \frac{1}{2} \nabla_{\boldsymbol{w}} \Big( \boldsymbol{y}^\mathrm{T}\boldsymbol{y} – \boldsymbol{y}^\mathrm{T}X\boldsymbol{w} – (X\boldsymbol{w})^\mathrm{T}\boldsymbol{y} + (X\boldsymbol{w})^\mathrm{T}X\boldsymbol{w} \Big) \\ &= \frac{1}{2} \nabla_{\boldsymbol{w}} \Big( \boldsymbol{y}^\mathrm{T}\boldsymbol{y} – 2 \boldsymbol{y}^\mathrm{T}X\boldsymbol{w} + \boldsymbol{w}^\mathrm{T}X^\mathrm{T}X\boldsymbol{w} \Big) \\ &= \frac{1}{2} (-2 X^\mathrm{T}\boldsymbol{y} + 2 X^\mathrm{T}X \boldsymbol{w}) \\ &= X^\mathrm{T}X \boldsymbol{w} – X^\mathrm{T}\boldsymbol{y} \end{aligned}
令 \nabla_{\boldsymbol{w}} J = 0,有
X^\mathrm{T}X \boldsymbol{w} – X^\mathrm{T}\boldsymbol{y} = 0
X^\mathrm{T}X \boldsymbol{w} = X^\mathrm{T}\boldsymbol{y}
当 X^\mathrm{T} X 可逆,可以解得
\boldsymbol{w} = (X^\mathrm{T}X)^{-1} X^\mathrm{T}\boldsymbol{y} \tag{6}