[ML Notes] 线性回归：Normal Equation
Contents
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$ 个样例的特征和标签。
记
$$
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}
$$