- 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
2.3.3 加快迭代速度
由于 l2 范数是强凸的,所以加上 l2 范数,目标函数也更强凸,即从右到左:
这样梯度下降将更快收敛。
2.4 核范数
核范数 $|w|_* = \sum \lambda_i$,即为矩阵的迹。他是对矩阵低秩的最优凸近似。我们知道,低秩约束就是数非零特征值的个数,和 l0 范数相似,还是“数数”,NP 难,所以松弛成核范数。
何为低秩?如果数据矩阵表达的是结构性信息,即矩阵的行列数据之间存在一定的相关性,那么这个矩阵是含有冗余信息的,可以用一个低秩矩阵近似表示。
3 引用和扩展阅读
[2] 几种范数的简单介绍
[3] 机器学习中的正则化和范数规则化
[4] 从贝叶斯角度深入理解正则化
[5] 机器学习中的范数规则化之(一)L0、L1与L2范数 深度好文!评论区也要看!
[6] 一文搞懂深度学习正则化的L2范数
[8] 从Lasso开始说起
[9] 病态问题与不适定问题是否等价? – 吱昂的回答 – 知乎
[mathjax]