[ML Notes] 线性回归:Normal Equation

1. 基本形式

  线性回归的形式为一系列特征的线性组合

$$
f(x) = w_0 + w_1 x_1 + w_2 x_2 + \cdots + w_n x_n \tag{1}
$$

其中 $x_i$ 为特征,$w_i$ 为参数。$w_0$ 为偏置,$w_1, w_2, \dots, w_n$ 为对应特征的权重。

  令

$$
\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$ 个样例的特征和标签。

  记

$$
\boldsymbol{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}(\boldsymbol{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}
= \boldsymbol{X} \boldsymbol{w} \tag{4}
$$

于是

$$
\boldsymbol{y} – \boldsymbol f(\boldsymbol{X})
= \boldsymbol{y} – \boldsymbol{X} \boldsymbol{w}
= \begin{bmatrix}
y^{(1)} \\
\vdots \\
y^{(m)}
\end{bmatrix}
– \begin{bmatrix}
\big( \boldsymbol{x}^{(1)} \big)^\mathrm{T} \boldsymbol{w} \\
\vdots \\
\big( \boldsymbol{x}^{(m)}\big)^\mathrm{T} \boldsymbol{w}
\end{bmatrix}
= \begin{bmatrix}
y^{(1)} – f(\boldsymbol{x}^{(1)}) \\
\vdots \\
y^{(m)} – f(\boldsymbol{x}^{(m)})
\end{bmatrix}
$$

故式 $(3)$ 也可以写为

$$
J(\boldsymbol{w}) = \frac{1}{2} ||\boldsymbol{y} – \boldsymbol{X} \boldsymbol{w}||_2^2 = \frac{1}{2} (\boldsymbol{y} – \boldsymbol{X} \boldsymbol{w})^\mathrm{T} (\boldsymbol{y} – \boldsymbol{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} – \boldsymbol{X} \boldsymbol{w})^\mathrm{T} (\boldsymbol{y} – \boldsymbol{X} \boldsymbol{w}) \\
&= \frac{1}{2} \nabla_{\boldsymbol{w}} \Big( \boldsymbol{y}^\mathrm{T}\boldsymbol{y} – \boldsymbol{y}^\mathrm{T}\boldsymbol{X}\boldsymbol{w} – (\boldsymbol{X}\boldsymbol{w})^\mathrm{T}\boldsymbol{y} + (\boldsymbol{X}\boldsymbol{w})^\mathrm{T}\boldsymbol{X}\boldsymbol{w} \Big) \\
&= \frac{1}{2} \nabla_{\boldsymbol{w}} \Big( -\boldsymbol{y}^\mathrm{T}\boldsymbol{X}\boldsymbol{w} – \boldsymbol{y}^\mathrm{T}\boldsymbol{X}\boldsymbol{w} + \boldsymbol{w}^\mathrm{T}(\boldsymbol{X}^\mathrm{T}\boldsymbol{X})\boldsymbol{w} \Big) \\
&= \frac{1}{2} \nabla_{\boldsymbol{w}} \Big( \boldsymbol{w}^\mathrm{T}(\boldsymbol{X}^\mathrm{T}\boldsymbol{X})\boldsymbol{w} – 2 \boldsymbol{y}^\mathrm{T}\boldsymbol{X}\boldsymbol{w} \Big) \\
&= \frac{1}{2} (2 \boldsymbol{X}^\mathrm{T}\boldsymbol{X} \boldsymbol{w} – 2 \boldsymbol{X}^\mathrm{T}\boldsymbol{y} ) \\
&= \boldsymbol{X}^\mathrm{T}\boldsymbol{X} \boldsymbol{w} – \boldsymbol{X}^\mathrm{T}\boldsymbol{y}
\end{aligned}
$$

令 $\nabla_{\boldsymbol{w}} J = 0$,有

$$
\boldsymbol{X}^\mathrm{T}\boldsymbol{X} \boldsymbol{w} – \boldsymbol{X}^\mathrm{T}\boldsymbol{y} = 0
$$

$$
\boldsymbol{X}^\mathrm{T}\boldsymbol{X} \boldsymbol{w} = \boldsymbol{X}^\mathrm{T}\boldsymbol{y}
$$

当 $\boldsymbol{X}^\mathrm{T} \boldsymbol{X}$ 可逆,有

$$
\boldsymbol{w} = (\boldsymbol{X}^\mathrm{T}\boldsymbol{X})^{-1} \boldsymbol{X}^\mathrm{T}\boldsymbol{y} \tag{6}
$$