Processing math: 11%

[ML Notes] 线性回归:Normal Equation

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}