正则化

| 研究学术  | 机器学习基础  正则化  Matlab 

正则化来源于处理函数逼近（function approximation）中的病态问题（ill-posed problem）。克服过拟合的一个方法是从简单模型开始尝试；正则化是相反的思路，从复杂模型的假设集开始，通过正则化约束求解得到未过拟合的简单模型（复杂项的系数很小或接近0）。

正则化等价于结构风险最小化（SRM，structural risk minimuzation）[1, P. 9]，它是结构风险最小化策略的实现，通过在经验风险上加一个正则化项或惩罚项实现[1, P. 13]。正则化符合奥卡姆剃刀（Occam’s rezor）原理：在所有可能选择的模型中，能够很好解释已知数据并且十分简单才是最好的模型。从贝叶斯估计的角度看，正则化项对应于模型的先验概率，可以假设复杂的模型有较大的先验概率，简单的模型有较小的先验概率[1, P. 14]。

本文的主要参考资料是机器学习基石[2]。

带约束回归

对于$x\in\mathbb R$的Q阶多项式变换$\Phi_Q(x)=\left(1,x,x^2,\ldots,x^Q\right)$，为了方便用$\mathbf w$代替回归系数$\tilde{\mathbf w}$。10次和2次空间中回归问题的假设集$\mathcal H_{10}$和$\mathcal H_2$分别表示为 \[ \begin{aligned} &w_0+w_1x+w_2x^2+w_3x^3+\ldots,w_{10}x^{10}\\ &w_0+w_1x+w_2x^2。 \end{aligned} \] 若$w_3=w_4=\ldots=w_{10}=0$，则$\mathcal H_2=\mathcal H_{10}$，也就是$\mathcal H_2$的回归问题可以用带约束的$\mathcal H_{10}$实现 \[ \min_{\mathbf w\in\mathbb R^{10+1}} E_{in}(\mathbf w)\quad\mbox{s.t. }w_3=w_4=\ldots=w_{10}=0。 \] 正则化可以看作带约束的优化$E_{in}$。

稍微放松约束条件，任意8个系数为0，得到用带约束的$\mathcal H_{10}$表示的$\mathcal H’_2$ \[ \min_{\mathbf w\in\mathbb R^{10+1}} E_{in}(\mathbf w)\quad\mbox{s.t. }\sum_{q=0}^{10}\left[\left[w_q\neq 0\right]\right]\leq 3。 \] $\mathcal H’_2$比$\mathcal H_2$宽松，但比$\mathcal H_{10}$过拟合风险低，$\mathcal H_2\subset\mathcal H’_2\subset\mathcal H_{10}$。求解稀疏形式（含8个0系数）$\mathcal H’_2$中的假设非常困难，NP-hard。

进一步放松约束条件，得到用带约束的$\mathcal H_{10}$表示的$\mathcal H(C)$ \[ \min_{\mathbf w\in\mathbb R^{10+1}} E_{in}(\mathbf w)\quad\mbox{s.t. }\sum_{q=0}^{10}w_q^2\leq C。 \] $\mathcal H(C)$和$\mathcal H’_2$有交集（overlap），对$C\geq 0$存在嵌套结构 \[ \mathcal H(0)\subset\mathcal H(1.126)\subset\ldots\subset\mathcal H(1126)\subset\ldots\subset\mathcal H(\infty)=\mathcal H(10)。 \] 从正则化假设集$\mathcal H(C)$的到的最优解就是正则化假设$\mathbf w_{REG}$。

拉格朗日乘子法

根据上述推导，正则化回归问题的向量表示形式 \begin{equation} \min_{\mathbf w\in\mathbb R^{Q+1}}E_{in}(\mathbf w)= {1\over N}\sum_{n=1}^N\left(\mathbf w^T\mathbf z_n-y_n\right)^2\qquad\mbox{s.t. }\sum_{q=0}^Qw_q^2\leq C， \end{equation} 进一步记为矩阵形式 \begin{equation} \min_{\mathbf w\in\mathbb R^{Q+1}}E_{in}(\mathbf w)= {1\over N}(\mathbf Z\mathbf w-\mathbf y)^T(\mathbf Z\mathbf w-\mathbf y)\qquad\mbox{s.t. }\mathbf w^T\mathbf w\leq C， \label{eq:constrained-Ein-matrix} \end{equation} 事实上$\mathbf w$位于半径为$\sqrt C$的球中。

正则化约束的梯度下降法
图 1: 正则化约束的梯度下降法 [PNG]

上图展示了正则化约束的梯度下降法，蓝色的椭圆曲线表示梯度相同的等高线，红色的圆形表示约束条件。没有正则化约束时，$\mathbf w$沿着$-\nabla E_{in}(\mathbf w)$方向达到最优解$\mathbf w_{lin}$，梯度方向指出了到达最优解的方式。有正则化约束时，大部分情况，最优解都在球面$\mathbf w^T\mathbf w=C$上。$-\nabla E_{in}(\mathbf w)$可以分解为绿色和红色$\mathbf w$（球切面的法向量）两个方向，如果已经在球面上，仍然继续沿着$\mathbf w$下降，会破坏约束条件。正则化梯度下降法，可看作在绿色箭头方向作用下接近最优解。达到最优解的条件是满足约束且不能继续下降，也就是$-\nabla E_{in}(\mathbf w)$平行于$\mathbf w$，那么有$-\nabla E_{in}(\mathbf w_{REG})\propto\mathbf w_{REG}$，此时绿色方向的分量为0，不再下降，优化过程结束。

利用拉格朗日乘子$\lambda>0$，达到最优解的条件是 \begin{equation} \nabla E_{in}(\mathbf w_{REG})+{2\lambda\over N}\mathbf w_{REG}=0。 \label{eq:nabla-E-w-reg} \end{equation} 因为$\nabla E_{in}(\mathbf w_{REG})={2\over N}\left(\mathbf Z^T\mathbf Z\mathbf w_{REG}-\mathbf Z^T\mathbf y\right)$，所以可得最优解1 \begin{equation} \mathbf w_{REG}\leftarrow\left(\mathbf Z^T\mathbf Z+\lambda\mathbf I\right)^{-1}\mathbf Z^T\mathbf y。 \end{equation} $\mathbf Z^T\mathbf Z$是半正定的，当$\lambda>0$时，上述逆矩阵总存在。正则化的线性回归在统计学中称为脊回归（ridge regression）。

求解\eqref{eq:nabla-E-w-reg}等价于最小化增广误差（augmented error） \begin{equation} \mathbf w_{REG}\leftarrow \arg\min_{\mathbf w}E_{aug}(\mathbf w)\quad \lambda\geq 0， \label{eq:Eaug-minimization} \end{equation} 其中增广误差 \begin{equation} E_{aug}(\mathbf w)=E_{in}(\mathbf w)+{\lambda\over N}\mathbf w^T\mathbf w， \label{eq:E-aug} \end{equation} $\mathbf w^T\mathbf w$称为正则化项（regularizer）。带约束优化$E_{in}$，可通过无约束优化$E_{aug}(\mathbf w)$高效求解，每个$C$都有对应的$\lambda$，大的$\lambda$对应着小的$C$，也对应着短的$\mathbf w$。当$\lambda=1$或$C=\infty$或$C\geq\lVert\mathbf w_{LIN}\rVert^2$（相当于红色的圆已经把$\mathbf w_{LIN}$包含在内）时，相当于没有进行正则化。

不同系数下正则化的效果
图 2: 不同系数下正则化的效果 [PNG]

$\lambda$相当于对过拟合的惩罚因子，上图展示了不同$\lambda$惩罚下的效果。

${\lambda\over N}\mathbf w^T\mathbf w$称为权重衰减（weight-decay）正则化，可推广到“任意变换 ＋ 线性模型”。

勒让德多项式

当$x_n\in[-1,1]$和$Q$很大时，$x_n^q$会变得非常小，除精确度因素影响外，还需要很大的$w_q$才能体现$x_n^q$的影响，这就与正则化的目的有些“矛盾”，过度惩罚了高次项。对于$\mathcal Z$空间的特征 \[ \Phi(\mathbf x)=\left(1,x,x^2,\ldots,x^Q\right)， \] 特征之间彼此非正交，对低次项容忍度较大，对高次项惩罚力度更大。

勒让德多项式
图 3: 勒让德多项式 [PNG]

为改善这一问题，可以考虑在多项式空间找到一组正交的基函数（orthonormal basis function），也称为勒让德多项式（legendre polynomials），构造如上图所示的新多项式变换 \[ \Phi(\mathbf x)=\left(1,L_1(x),L_2(x),\ldots,L_Q(x)\right)。 \]

VC维分析

带约束$E_{in}$优化\eqref{eq:constrained-Ein-matrix}的VC上界 \begin{equation} E_{out}(\mathbf w)\leq E_{in}(\mathbf w)+\Omega(\mathcal H(C))， \label{eq:vc-bound} \end{equation} 采用与$C$等价的$\lambda$时，可以用优化\eqref{eq:Eaug-minimization}实现，在没有限定$\mathcal H(C)$的情况下，通过优化$E_{aug}$间接获得了VC维的保证。对比\eqref{eq:E-aug}和\eqref{eq:vc-bound}，$\mathbf w^T\mathbf w=\Omega(\mathbf w)$衡量了单一假设的复杂度，$\Omega(\mathcal H(C))$衡量了整个假设集的复杂度。如果${\lambda\over N}\Omega(\mathbf w)$能很好的表示$\Omega(\mathcal H(C))$，衡量$E_{out}$时，$E_{aug}$是比$E_{in}$更好中介。

对$\mathcal Z$空间的非正则化方法，$d_{VC}(\mathcal H)=\tilde d+1$。事实上，采用正则化考虑的假设集$\mathcal H(C)$要小于$\mathcal H$。采用了正则化后，有效（effective）VC维$d_{EFF}(\mathcal H,\mathcal A)\leq d_{VC}(\mathcal H)$，其中$\mathcal A$为正则化算法。因此，正则化方法具有更好的泛化性能。增大$\lambda$使$C$变小，从而使$\mathcal H(C)$变小，使得$d_{EFF}(\mathcal H,\mathcal A)$减小。

正则化的推广

除权重衰减（weight-decay）正则化外，还有很多其它的正则化方法。正则化的约束条件应当向着目标函数方向，选择正则化方法的思路包括：

  • 目标相关（target-dependent）：利用目标的特性，比如已知目标函数的对称性，可采用对称正则化$\sum[[q\mbox{ is odd}]]w_q^2$；
  • 合理性（plausible）：使结果更加光滑和简单，比如要对随机或确定性噪声鲁棒，可采用稀疏的$L_1$正则化$\sum |w_q|$；
  • 友好（friendly）：易于优化，比如采用除权重衰减的$L_2$正则化$\sum w_q^2$。

如果正则化选择不合适，还有$\lambda=0$这道防线，可以避免危害。以上正则化选择思路和误差度量一致：用户相关（user-dependent）、合理性、友好。

［左］：L2正则化；［右］L1正则化
图 4: ［左］：L2正则化；［右］L1正则化 [PNG]

$L_1$正则化在需要稀疏解时很有用。上图右是$L_1$正则化示意图，$L_1$正则化 \begin{equation} \Omega(\mathbf w)=\sum_{q=0}^Q|w_q|=\lVert\mathbf w\rVert_1， \end{equation} 虽然不可微分，但它是凸的，解是稀疏的（$\mathbf w$有很多0元素）。$-\nabla E_{in}$可分解到垂直于边界面的方向（边界面的法向量方向，如上图右红色箭头所示）和沿边界面的方向。当到达边界面后，如果继续沿着法向量方向下降，会破坏约束条件，沿着面的方向如果还能下降，则继续沿着面的方向下降，直到停在菱形球的顶点，或者直到$-\nabla E_{in}(\mathbf w)$平行$\mathbf w$（沿边界面的方向分量为0）。边界面的法向量只和$\mathbf w$的符号有关，如果要$-\nabla E_{in}(\mathbf w)$平行$\mathbf w$比较困难，通常会停在菱形球的顶点，该点在坐标轴上，必有元素为0。

最优$\lambda$

噪声对性能的影响
图 5: 噪声对性能的影响 [PNG]

上图表明，噪声等级越高，正则化的惩罚力度$\lambda$越大。实际上，噪声的等级不可预知，只有通过实验的方法选择最佳$\lambda$，也就是通过验证（validation）选择最佳$\lambda$。

正则化实例

本节内容源于机器学习[3]网络课程，这里没有对增加的偏移项$x_0=1$的系数正则化，且$y\in\{0,1\}$。

正则化线性回归

一、代价函数

\begin{equation} J(\boldsymbol\theta) = \frac{1}{2m}\left( \sum_{i=1}^m\left( h_{\boldsymbol\theta}\left(\mathbf x^{(i)}\right) - y^{(i)} \right)^2 + \lambda\sum_{j=1}^n\theta_j^2 \right) \label{eq:cf-linear-regression-r} \end{equation}

二、梯度下降法估计参数

repeat until convergence { \begin{equation*} \begin{aligned} \theta_0 & := \theta_0 - \alpha\frac{1}{m}\sum_{i=1}^m\left( h_{\boldsymbol\theta}\left(\mathbf x^{(i)}\right) - y^{(i)} \right)x_0^{(i)} \\
\theta_j & := \theta_j - \alpha\frac{1}{m}\left(\sum_{i=1}^m\left( h_{\boldsymbol\theta}\left(\mathbf x^{(i)}\right) - y^{(i)} \right)x_j^{(i)} + \lambda\theta_j\right)~~(j = 1, 2, \ldots, n) \end{aligned} \end{equation*} }

迭代过程可以化为如下形式： \begin{equation*} \theta_j := \theta_j\left(1 - \alpha\frac{\lambda}{m} \right) - \alpha\frac{1}{m}\sum_{i=1}^m\left( h_{\boldsymbol\theta}\left(\mathbf x^{(i)}\right) - y^{(i)} \right)x_j^{(i)};~~(j = 1, 2, \ldots, n) \end{equation*}

通常$1 - \alpha\frac{\lambda}{m} < 1$，与非正则化的梯度下降法比较，$\theta_j$减小更快。

正则化Logistic回归

一、代价函数

\begin{equation} \begin{aligned} J(\boldsymbol\theta) = &-\frac{1}{m}\sum_{i=1}^{m}\left(y^{(i)}\log h_{\boldsymbol\theta}\left(\mathbf x^{(i)}\right)+\left(1-y^{(i)}\right)\log \left(1-h_{\boldsymbol\theta}\left(\mathbf x^{(i)}\right)\right)\right) \\ & + \frac{\lambda}{2m}\sum_{j=1}^n\theta_j^2 \end{aligned} \label{eq:cf-logistic-regression-r} \end{equation}

二、梯度下降法估计参数

repeat until convergence { \begin{equation*} \begin{aligned} \theta_0 & := \theta_0 - \alpha\frac{1}{m}\sum_{i=1}^m\left( h_{\boldsymbol\theta}\left(\mathbf x^{(i)}\right) - y^{(i)} \right)x_0^{(i)} \\
\theta_j & := \theta_j - \alpha\frac{1}{m}\left(\sum_{i=1}^m\left( h_{\boldsymbol\theta}\left(\mathbf x^{(i)}\right) - y^{(i)} \right)x_j^{(i)} + \lambda\theta_j\right)~~(j = 1, 2, \ldots, n) \end{aligned} \end{equation*} }

Matlab实现

第一步：实现Logistic函数

function g = sigmoid(z)
g = 1.0 ./ (1.0 + exp(-z));
end

第二步：实现代价函数（包含梯度计算）

function [J, grad] = costFunctionReg(theta, X, y, lambda)
m = length(y); % number of training examples

h = sigmoid(X * theta);
J = -mean(y .* log(h) + (1 - y) .* log(1 - h)) + ...
    lambda / (2 * m) * sum(theta(2:end) .^ 2);
grad = (X' * (h - y) + lambda * [0; theta(2:end)]) / m;

end

第三步：估计参数

initial_theta = zeros(size(X, 2), 1);
lambda = 1;
options = optimset('GradObj', 'on', 'MaxIter', 400);
[theta, J, exit_flag] = ...
	fminunc(@(t)(costFunctionReg(t, X, y, lambda)), initial_theta, options);

参考资料

  1. [1]李航, 统计学习方法. 北京: 清华大学出版社, 2012.
  2. [2]H.-T. Lin, “Lecture 14: Regularization.” Coursera, 2014. [Online]
  3. [3]A. Ng, “Regularization: The problem of overfitting.” Coursera, 2014. [Online]

脚注

  1. 为什么正则化包括$x_0=1$的偏移项系数，两者有何区别？ ↩

打赏作者

上一篇：过拟合的危害     下一篇：验证