[ML Notes] 线性回归：正则化
Contents
1. L2 正则化，岭回归
对如前文所述的线性模型 $f(\boldsymbol{x})$ 和代价函数 $J(\boldsymbol{w})$
$$
f(\boldsymbol x) = w_0 + w_1 x_1 + w_2 x_2 + \cdots + w_n x_n = w_0 + \sum_{i=1}^n w_i x_i = \boldsymbol{w}^\mathrm{T} \boldsymbol{x} \tag{1}
$$
$$
J(\boldsymbol{w}) = \frac{1}{2} \sum_{i=1}^m \big( y^{(i)} – f(\boldsymbol{x}^{(i)}) \big)^2 \tag{2}
$$
岭回归（Ridge Regression）通过在代价函数上添加一个额外的项 $\frac{1}{2} \alpha \sum\limits_{i=1}^n w_i^2$，来缩小模型参数，此时代价函数变为
$$
J_{\mathrm{ridge}}(\boldsymbol{w}) = \frac{1}{2} \sum_{i=1}^m \big( y^{(i)} – f(\boldsymbol{x}^{(i)}) \big)^2 + \frac{1}{2} \alpha \sum\limits_{i=1}^n w_i^2 \tag{3}
$$
其中 $\alpha$ 为正则化系数，$\sum\limits_{i=1}^n w_i^2$ 为参数 $\boldsymbol{w}$ 的 L2 范数的平方，即 $||\boldsymbol{w}||_2^2 = \boldsymbol{w}^\mathrm{T} \boldsymbol{w}$。注意这里的 $i$ 从 $1$ 开始，不对偏置 $w_0$ 进行正则化。
使用前文的符号，式 $(1)$ 和式 $(3)$ 又可以写成
$$
\boldsymbol{f}(X) = X \boldsymbol{w} \tag{4}
$$
$$
\begin{aligned}
J_{\mathrm{ridge}}(\boldsymbol{w}) &= \frac{1}{2}||\boldsymbol{y} – X \boldsymbol{w}||_2^2 + \frac{1}{2} \alpha ||\boldsymbol{w}||_2^2 \\
&= \frac{1}{2} (\boldsymbol{y} – X \boldsymbol{w})^\mathrm{T} (\boldsymbol{y} – X \boldsymbol{w}) + \frac{1}{2} \alpha \boldsymbol{w}^\mathrm{T} \boldsymbol{w}
\end{aligned} \tag{5}
$$
类似地，计算梯度
$$
\begin{aligned}
\nabla_{\boldsymbol{w}} J_{\mathrm{ridge}}(\boldsymbol{w}) &= X^\mathrm{T}X \boldsymbol{w} – X^\mathrm{T}\boldsymbol{y} + \alpha \boldsymbol{w} \\
&= (X^\mathrm{T}X + \alpha \boldsymbol{I}) \boldsymbol{w} – X^\mathrm{T}\boldsymbol{y}
\end{aligned} \tag{6}
$$
令 $\nabla_{\boldsymbol{w}} J_{ridge}(\boldsymbol{w}) = 0$，有
$$
(X^\mathrm{T}X + \alpha \boldsymbol{I}) \boldsymbol{w} – X^\mathrm{T}\boldsymbol{y} = 0
$$
$$
(X^\mathrm{T}X + \alpha \boldsymbol{I}) \boldsymbol{w} = X^\mathrm{T}\boldsymbol{y}
$$
$$
\boldsymbol{w} = (X^\mathrm{T}X + \alpha \boldsymbol{I})^{-1} X^\mathrm{T}\boldsymbol{y} \tag{7}
$$
注意只对权重 $w_1, w_2, \cdots, w_n$ 进行正则化，而不对偏置 $w_0$ 作正则化，因此上式中的 $\boldsymbol{I}$ 是一个 $n \times n$ 的单位矩阵，但左上角的元素为 $0$。
2. L1 正则化，Lasso 回归
Lasso 回归使用权重 L1 范数作为正则化项，此时的代价函数为
$$
J_{\mathrm{lasso}}(\boldsymbol{w}) = \frac{1}{2} \sum_{i=1}^m \big( y^{(i)} – f(\boldsymbol{x}^{(i)}) \big)^2 + \alpha \sum_{i=1}^n |w_i| \tag{8}
$$
或者写为
$$
\begin{aligned}
J_{\mathrm{lasso}}(\boldsymbol{w}) &= \frac{1}{2}||\boldsymbol{y} – X \boldsymbol w ||_2^2 + \alpha ||\boldsymbol{w}||_1 \\
&= \frac{1}{2} (\boldsymbol{y} – X \boldsymbol{w})^\mathrm{T} (\boldsymbol{y} – X \boldsymbol{w}) + \alpha \sum_{i=1}^n |w_i|
\end{aligned} \tag{9}
$$
其梯度为
$$
\nabla J_{\mathrm{lasso}}(\boldsymbol{w}) = \nabla J(\boldsymbol{w}) + \alpha \sum_{i=1}^n \mathrm{sign}(w_i) \tag{10}
$$
其中
$$
\mathrm{sign}(w_i) = \begin{cases}
-1 & \mathrm{if} \; w_i < 0 \\
0 & \mathrm{if} \;w_i = 0 \\
1 & \mathrm{if} \; w_i > 0 \\
\end{cases}
$$