机器学习 - 正则化

概述

info

在 数学与计算机科学 中，尤其是在机器学习和逆问题领域中，正则化（regularization）是指为解决 适定性问题 或 过拟合 而加入额外信息的过程。¹

先来从损失函数的角度引入，机器学习训练的过程，就是要找到一个足够好的函数 $F^*$ 用以在新的数据上进行推理。而为了定义这个好，我们引入了损失函数的概念。一般的，对于样本 $(\vec{x}, y)$ 和模型 $F$，有预测值 $\hat{y}=F(\vec{x})$。而损失函数是定义在 $\mathbb{R}\times \mathbb{R}\to \mathbb{R}$ 上的二元函数 $\ell(y, \hat{y})$，用来描述 $\mathrm{Ground \ Truth}$ 和预测值之间的差距。一般来说，损失函数是一个有下确界的函数；当预测值和 $\mathrm{Ground \ Truth}$ 足够接近，损失函数的值也会接经该下确界。

tip

当然，这里的损失函数是一种一般的描述，根据任务的不同，其函数也不同。

因此，机器学习训练的过程可以转化为训练集 $\mathcal{D}$ 上的最小化问题。我们的目标是在参数空间 (泛函空间) 内，找到使得全局损失 $\displaystyle L(F)=\sum_{i \in \mathcal{D}} \ell\left(y_{i}, \hat{y}_{i}\right)$ 最小的模型 $F^*$。

$$F^{*}:=\underset{F}{\arg \min } L(F) .$$

但是损失函数只考虑在训练集上的经验风险²，这种做法可能会导致过拟合 (overfitting)。为了对抗过拟合，我们需要向损失函数中加入描述模型复杂度的正则项 $\Omega(F)$，将经验风险最小化转化为结构风险最小化。

$$F^{*}:=\underset{F}{\arg \min } \operatorname{Obj}(F)=\underset{F}{\arg \min }(L(F)+\gamma \Omega(F)), \quad \gamma>0 .$$

其中，$\operatorname{Obj}(F)$ 称为目标函数，它描述模型的结构风险；$L(F)$ 是训练集上的损失函数；$\Omega(F)$ 是正则项，它描述模型的复杂程度；$\gamma$ 是用于控制正则项重要程度的参数。正则项通常包括对光滑度及向量空间内范数上界的限制。

经验风险

在另一章 极大似然估计 中提到过似然函数，其实就是一种经验风险。我们无法确切知道算法在实际中的运行情况（真正的 “ 风险 “），因为我们不知道算法将在何种分布上的数据运行，但借助经验风险最小化，我们可以在一组已知的训练数据（” 经验 “ 风险）上衡量其性能。

结构风险以及描述模型复杂度

且看后文 $\mathrm{Lp}$ 正则项

Lp 正则项

范数

所谓范数便是长度的抽象的说法，通常满足三种性质：非负性，齐次性，三角不等式。 从函数的观点来说，函数是定义在 $\mathbb{R}^n\to \mathbb{R}$ 的函数；它和损失函数类似，也有明确的下确界。

一个 $\mathrm{Lp}$ 范式可以被定义为：

$$\|x\|_{p}=\sqrt[p]{\Sigma_{i}\left|x_{i}\right|^{p}}$$

L0 和 L1 正则项

机器学习模型中的参数，可以形式化的表示为参数向量，记为 $\vec{w}$。不失一般性，以线性模型为例：

$$F(\vec{x} ; \vec{\omega}):=\vec{\omega}^{\top} \cdot \vec{x}=\sum_{i=1}^{n} \omega_{i} \cdot x_{i}$$

Where is bias?

在一般的线性模型中有偏置项 (Bias)，其实可以使用下面方法，将 Bias 视为某种 $\vec{w}$

$$\begin{array}{c} \vec{w}^\top \vec{x} + b \\ \Updownarrow \\ \begin{bmatrix} \vec{w} \\ b \end{bmatrix}^\top\cdot \begin{bmatrix} \vec{x} \\ 1 \end{bmatrix} \Leftrightarrow \vec{w}^\top\vec{x} \end{array}$$

另外，实际上正则不会影响偏置项

由于训练集 $\mathcal{D}$ 中统计噪声的存在，冗余的特征可能成为过拟合的一种来源。这是因为，对于统计噪声，模型无法从有效特征当中提取信息进行拟合，故而会转向冗余特征。为了对抗此类过拟合现象，人们希望让尽可能多的 $w_{i}$ 为零。为此，最直观的，引入 $L_{0}$- 正则项。

$$\Omega(F(\vec{x} ; \vec{\omega})):=\gamma_{0} \frac{\|\vec{\omega}\|_{0}}{n}, \gamma_{0}>0$$

warning

严格来说 $L_{0}$ 并不是一个范数。前面我们提到范数是需要满足 齐次性 的，但是我们有 ³：

$$\|\lambda x\|_{0}=\|x\|_{0}, \lambda\ne 0.$$

另外根据 $\mathrm{Lp}$ 范数的定义，需要对 $0$ 开根号，这是有问题的。所以可以称为 Pseudo-norm⁴

所以一般我们使用的是

$$\|x\|_{0}=\sharp\left(i \mid x_{i} \neq 0\right)$$

即，非零元素的个数

机制分析

通过引入 $L_{0}$- 正则项，人们实际上是向优化过程引入了一种 惩罚机制：当优化算法希望增加模型复杂度（此处特指将原来为零的参数 $w_{i}$ 更新为非零的情形）以降低模型的经验风险（即降低全局损失）时，在结构风险上进行大小为 $\displaystyle\frac{\gamma_{0}}{n}$ 的惩罚。于是，当增加模型复杂度在经验风险上的收益不足 $\displaystyle\frac{\gamma_{0}}{n}$ 时，整个结构风险实际上会增大而非减小。因此优化算法会拒绝此类更新。

note

引入 $L_{0}$- 正则项可以使模型参数稀疏化，以及使得模型易于解释。但是 $L_{0}$ 非连续、非凸、不可微。

因此，我们转而考虑 $L_{0}$- 范数的最紧凸放松——$L_{1}$- 范数，令

$$\Omega(F(\vec{x} ; \vec{\omega})):=\gamma_{1} \frac{\|\vec{\omega}\|_{1}}{n}, \gamma_{1}> 0$$

$L_{1}$ 正则是在结构风险上进行大小为 $\displaystyle\frac{\gamma_{1}\left|\omega_{i}\right|}{n}$ 的惩罚，以达到稀疏化的目的。

L2 正则项

我们将 $L_{2}$- 范数，作为 $L_{2}$- 正则项。令

$$\Omega(F(\vec{x} ; \vec{w})):=\gamma_{2} \frac{\|\vec{\omega}\|_{2}^{2}}{2 n}, \gamma_{2}>0$$

warning

这里是 $\|\vec{\omega}\|_{2}^{2}$，而并非 $\|\vec{\omega}\|_{2}$

我们有目标函数

$$\operatorname{Obj}(F)=L(F)+\gamma_{2} \frac{\|\vec{\omega}\|_{2}^{2}}{2 n}$$

于是对于参数 $w_{i}$ 求偏微分

$$\frac{\partial \mathrm{Obj}}{\partial \omega_{i}}=\frac{\partial L}{\partial \omega_{i}}+\frac{\gamma_{2}}{n} \omega_{i}$$

因此，在梯度下降时，参数 $w_{i}$ 的更新

$$\omega_{i}^{\prime} \leftarrow \omega_{i}-\eta \frac{\partial L}{\partial \omega_{i}}-\eta \frac{\gamma_{2}}{n} \omega_{i}=\left(1-\eta \frac{\gamma_{2}}{n}\right) \omega_{i}-\eta \frac{\partial L}{\partial \omega_{i}}$$

注意到 $\displaystyle\eta \frac{\gamma_{2}}{n}$ 通常是介于 $(0,1)$ 之间的数，$L_{2}$- 正则项会使参数接近零，从而对抗过拟合。

Footnotes

1. 正则化 (数学) - 维基百科，自由的百科全书) ↩

2. 经验风险最小化 - 维基百科，自由的百科全书 ↩

3. Norm (mathematics) - Wikipedia) ↩

4. inequality - Zero "norm" properties - Mathematics Stack Exchange ↩