1 理解正则化方法
- 1.1 基础概念
- 1.2 从训练模型的角度理解
- 1.3 从应用数学的角度理解
- 1.4 从 Bayes 的角度理解
2 常见的正则化项及其理解
- 2.1 L0 范数
- 2.2 L1 范数
- 2.3 L2 范数
  - 2.3.1 防止不适定
  - 2.3.2 防止过拟合
  - 2.3.3 加快迭代速度
- 2.4 核范数
3 引用和扩展阅读

目录展开

1 理解正则化方法

带正则化项的优化问题具的一般形式：

$$
\begin{aligned}
&\mathop{\arg\min_f} \epsilon(f) + \lambda \cdot \Omega(f)\\
=& \mathop{\arg\min_f} \sum_{i=1}^N l(y_i,f(x_i))+ \lambda \cdot \Omega(f)\\
\end{aligned}$$

其中，$\epsilon(f)$ 为损失函数，$\Omega(f)$ 为正则化项。

1.1 基础概念

范数[2]、不适定[1]

1.2 从训练模型的角度理解

引入正则化项的目的是在规则化参数的同时，最小化误差。

什么叫“规则化参数”呢？在机器学习的训练过程中，如果训练数据量比较少，而数据特征很多，那么将很容易出现过拟合。原来非常简单的问题（如分布在二次函数上的点），用非常复杂的方法解（如用 8 次方程拟合）就叫做过拟合。为了防止过拟合，我们要让没用的参数尽量小，这样就可以凸显关键特征的作用。正则化项“规则化参数”的第一层含义便是如此。

正则化项“规则化参数”还有第二层含义：正则化项的引入，可以约束模型的特征。比如，l0、l1 范数可让模型稀疏，其它范数可让模型平滑、低秩等等。其具体原因详见下文。

1.3 从应用数学的角度理解

我们知道，机器学习的问题大多是不适定的（详见[1]）。具体来讲，当输入的数据发生微小扰动，输出的结果可能有非常大的改变。比如在自然语言中，一句话里面改一个字，整句话的含义可能发生巨大的、甚至相反的变化；在求函数某点处导数时，邻域内的值改变很小，导数也可能有翻天覆地的变化。

我们用信号处理的方法描述这个问题：

$$y = w \cdot x + b$$

这个式子描述了信号 $x$ 通过一个系统，得到 $y$。其中 $w,b$ 是非线性算子。不适定问题即 $x$ 变化很小，而 $y$ 却变了很多。

怎么解决这个不适定的问题呢？最朴素的想法便是约束这个系统，让输入输出差不多 —— 这跟范数的定义差不多。矩阵的范数衡量了矩阵的大小，所以让范数更小，就是让优化问题更加适定。换句话说，范数的引入，使我们可以用一族与原不适定问题相“临近”的适定问题的解去逼近原问题的解。（更深一步的理解请见 2.3.1）

当然，这样做也会让最终的解有更大的误差，即由经验风险泛函拟合原不适定问题的误差。更深入的理解详见 [7]。

1.4 从 Bayes 的角度理解

正则化项规范了参数，从另外一个角度来讲，这是引入了参数的先验分布。如稀疏、平滑、低秩，都是我们对参数的先验知识。放到广义的线性模型中，就是对一些基函数做了取舍，选择关键的减小没用的，避免了过拟合。

[4] 中进行了如下推导，对于理解非常有帮助：

给定观察数据 $D$，用贝叶斯方法通过最大化后验概率估计参数 $w$。

$$
\begin{aligned}
w^* = & \mathop{\arg\max_w} P(w|D)\\
=& \mathop{\arg\max_w} \frac{P(D|w)P(w)}{P(D)}\\
=& \mathop{\arg\max_w} P(D|w)P(w)\\
\end{aligned}
$$

其中，$P(D|w)$ 为似然函数，满足 $P(D|w) = \prod_{i=1}^nP(D_i|w)$；$P(w)$ 为参数的先验概率，满足高斯分布 $N(\mu,\sigma^2)$

$$
\begin{aligned}
w^* = & \mathop{\arg\max_w} \prod_{i=1}^nP(D_i|w) \cdot P(w)\\
=& \mathop{\arg\max_w} \sum_{i=1}^n \log{P(D_i|w)} + \log{P(w)}\\
=& \mathop{\arg\min_w} – \sum_{i=1}^n \log{P(D_i|w)} – \sum_{i=1}^n \log{P(w_i)}\\
=& \mathop{\arg\min_w} – \sum_{i=1}^n \log{P(D_i|w)} – \sum_{i=1}^n \log{\lbrace\frac{1}{\sqrt{2\pi\sigma^2}}exp[\frac{(w_i-\mu)^2}{-2\sigma^2}]\rbrace}\\
=& \mathop{\arg\min_w} – \sum_{i=1}^n \log{P(D_i|w)} + \lambda \sum_{i=1}^n \frac{1}{\sigma^2}(w_i – \mu)^2\\
\end{aligned}
$$

当 $P(w)$ 满足标准正态分布时，有

$$
\begin{aligned}
w^* =& \mathop{\arg\min_w} – \sum_{i=1}^n \log{P(D_i|w)} + \lambda \sum_{i=1}^n (w_i)^2\\
\end{aligned}
$$

猛然发现，后一项正是 l2 正则。因此 l2 正则可以规范参数，使其接近正态分布。

同理，如果 $P(w)$ 满足拉普拉斯分布，即

$$P(w_i) = \frac{1}{2b} exp[-\frac{|w_i – \mu|}{b}]$$

这时便可以推出 l1 正则。

观察拉普拉斯分布和高斯分布的图像，我们可以发现：拉普拉斯在 0 附近非常突出，因此 l1 范数使参数更多接近零，即使参数稀疏；高斯分布在 0 附近平缓，周围稀疏，因此 l2 范数惩罚权值大的参数。（诶呀把下面要说的给提前说了 XD）

2 常见的正则化项及其理解

2.1 L0 范数

l0 范数即为矩阵中非零元素的个数。这是一个“数数”的过程，因此是 NP 难的，没法用。在机器学习里面，常将其松弛成 l1 范数。

2.2 L1 范数

l1 范数即为矩阵中各元素绝对值之和。也是为了稀疏，是 l0 范数最优凸近似。对应 lasso 回归[8]

2.3 L2 范数

l2 范数即为矩阵的 f 范数，即各元素平方之和。可防止不适定，防止过拟合，加快迭代速度。

2.3.1 防止不适定

这里我们更理性地讨论一下正则化对于不适定问题的帮助。

矩阵 $A$ 的 condition number $\mathcal{K}(A) = |A|_k\cdot|A^{-1}|_k$。如果 A 是奇异的（不可逆），那么 $\mathcal{K}(A)$ 无穷大。$k$ 的取值由具体的范数决定。

$\mathcal{K}(A)$ 是矩阵（或者它所描述的线性系统）的稳定性或者敏感度的度量，如果一个矩阵的 $\mathcal{K}(A)$ 在 1 附近，那么它就是 well-conditioned 的，如果远大于 1，那么它就是 ill-conditioned 的。如果一个系统是 ill-conditioned 的，中文叫“病态的”，因此也是不适定的。（关于病态与不适定，详见[9]）

举例来说，对于线性回归问题，我们的损失函数为：

$$E(w) = |x^Tw-y|_2^2$$

令 $\dfrac{\partial E(w)}{\partial w} = 2xx^Tw – 2xy = 0$

则我们可以得到闭式解：

$$\hat{w} = (xx^T)^{-1} \cdot xy$$

但是，若样本数 < 样本维度，那么 $x^T \cdot x$ 将是低秩的。我们知道，只有满秩的矩阵才可逆。因此在这时，没法直接计算闭式解，所以用梯度下降等数值方法求解，所以才使用神经网络等复杂结构。

不过，若加上 l2 正则，便有：

$$\hat{w} = (xx^T + \alpha I)^{-1} \cdot x y$$

式中 $xx^T + \alpha I$ 这个矩阵更接近满秩，因此 condition number 比原来小得多。

2.3.2 防止过拟合

l2 正则的作用并非让所有的参数都接近零，而是有选择地让某些无关紧要的参数接近零。

还是以线性回归为例说明：当样本特征很多时，大部分的特征都是无关紧要的。对应地，大部分参数也是无关紧要的。因此在 l2 正则的约束之下，这些无关紧要的参数将变得很小，接近于零。而对于关键的特征，他们对应的参数对于模型曲线的走势变化有着重要的影响，因此他们的微小变化会使得损失函数急剧增大。而若正则项想要约束这些关键的参数，损失函数的扩大将远大于正则项的减小，因此这些关键参数几乎不受正则项的干涉。

上面是感性的思考，接下来理性地推导[6]：

我们设有正则的解为 $w$，无正则的解为 $w’$，则有

$$
\begin{aligned}
\begin{cases}
w’ &= (xx^T)^{-1}xy\\
w &= (xx^T + \alpha I)^{-1}xy
\end{cases}\\
\therefore w = (xx^T + \alpha I)^{-1}(xx^T)w’
\end{aligned}
$$

$xx^T$ 是实对称矩阵，必存在相似对角矩阵，使得 $xx^T = Q^T\Lambda Q$，则有

$$
\begin{aligned}
w =& (Q^T\Lambda Q + \alpha Q^TI Q)^{-1}Q^T\Lambda Qw’\\
=& Q^T(\Lambda + \alpha I)^{-1}\Lambda Q w’
\end{aligned}
$$

如果 $\lambda_i$ 是 $xx^T$ 的特征值，则 $\dfrac{\lambda_i}{\lambda_i+\alpha}$ 是 $Q^T(\Lambda + \alpha I)^{-1}\Lambda Q$ 的特征值，所以有：

$$\begin{aligned}
&w = Q^T
\left(
\begin{array}{cccc}
\dfrac{\lambda_1}{\lambda_1+\alpha}&0&\cdots&0\\
0& \dfrac{\lambda_2}{\lambda_2+\alpha}&\cdots&0\\
\vdots&\vdots&\ddots&\vdots\\
0&0&\cdots& \dfrac{\lambda_k}{\lambda_k+\alpha}\\
\end{array}
\right)
Qw’\\
\Rightarrow \quad &
Qw =
\left(
\begin{array}{cccc}
\dfrac{\lambda_1}{\lambda_1+\alpha}&0&\cdots&0\\
0& \dfrac{\lambda_2}{\lambda_2+\alpha}&\cdots&0\\
\vdots&\vdots&\ddots&\vdots\\
0&0&\cdots& \dfrac{\lambda_n}{\lambda_n+\alpha}\\
\end{array}
\right)
(Qw’)\\
\end{aligned}$$

这个式子表明，$w$ 和 $w’$ 是在以 $Q$ 为基下的坐标满足上面对角阵变换，对于每个基，有

$$(Qw)_i = \dfrac{\lambda_i}{\lambda_i+\alpha}(Qw’)_i$$

$w’$ 在 $Q$ 下的所有分量都被缩小了，且对应特征值越小的分量，缩小越明显。[6] 中推出，特征值 $\lambda_i$ 代表损失函数 $E(w)$ 在基 $Q$ 的第 $i$ 个方向上的凸性强弱。引入 l2 正则之后，在这个方向上凸性越强，则越陡峭，$w’$ 在这个方向上的变化对 $E(w’)$ 的影响越大，则正则项在这个方向上对 $w’$ 削减的最小。QED