L2正则项与早停止(Early Stop)之间的数学联系

最近在看Goodfellow和Bengio等人的大作《Deep Learning》(以下简称DL Book)。

这本书从数学本质分析了很多我们认为“理所应当”、甚至是认为“很工程”的算法。

这篇文章主要就是介绍Early Stop这个算法和\(L^2\)正则项之间的联系。早停止算法在DL Book的第七章第八节中介绍的。

仔细研读之后发现很有收获。收货有二:

  1. 了解到了哪怕像早停止这种看起来简单粗暴纯工程的方法,其背后都是有深厚的数学依托来证明其合理性的。
  2. 学习到了一种寻找事物内在联系的方法:近似。当我们怀疑二者之间有联系,而二者之间的解析形式明显不同的时候,我们可以用相同的近似理论来将这二者“统一”到一个相同的形式然后去寻找他们的联系。

下面我就按照原书中的脉络,从“定性”和“定量”的角度分析“早停止”这种方法为什么能起到类似“正则项”的效果,并且将会探索“早停止”与“\(L^2\)参数范数惩罚”之间的关系。

早停止实际上是一种学习时的策略。通常我们在训练一个模型的时候,如果模型过于强大,或者训练数据过少等原因,很容易会导致过拟合等问题的产生。不幸的是,这种情况几乎是必然发生的。因为随着训练的深入,你的模型会越来越倾向于学习到“训练数据”的规律,而不是“生成训练数据的模型”的规律。这个时候,就是我们常说到的“过拟合”了。

发生过拟合的一个现象,就是训练误差足够小,但是测试误差却比较大。例如下面这张图

先忽略掉bias和variance这两件事,我们只看坐标轴和这两条曲线。

这张图的纵轴是指误差,我们的目标就是让这个误差最小化。然而对于模型来说,有两个误差:一是训练过程中的训练误差(青线),二是显示模型真正能力的测试误差(红线)。

对于横轴,我们可以从两个角度来考虑。

第一个角度是模型的复杂性。也就是说,一般我们的模型越复杂,就越容易训练出来一个“过拟合”的模型。

第二个角度是训练的“深入程度”,也就是“训练周期”的数量。当模型训练周期增加,就很容易出现“训练误差越来越小,测试误差却越来越大”的情况。这时候,模型就是过拟合了。

借用原书中的一幅图更能表示这个现象:

这张图是一个比较经典的训练过程的描述,我们发现随着Time的增加,训练集的损失不断在减小,但测试集(此处是Validation集)的误差却是先减小,后缓慢增加。

这时候,早停止的策略呼之欲出:在测试误差开始上升之前,就将训练停下来。因为在这个“提前停下来”的位置,尽管训练误差并没有达到最小,但是如果继续训练,测试误差就会变得更大,得不偿失了。

然而这时候要考虑一个小问题,就是测试误差的曲线是震荡的,不能因为一次微小的上升就认为整个训练应该结束,因为继续训练有可能获得更好的结果。

考虑清楚了这个问题,这个早停止的算法也就简单粗暴地呈现出来了:

首先我们要保存好现在的模型(网络结构和权值)。训练n次,然后用validation集测试一次,如果发现测试误差与上一次做evaluation的误差相比有下降,就再将现在的模型保存下来。如果发现比上次evaluation的性能差,那也不立刻终止,而是往后再看几步。直到经过了p次evaluation,如果测试误差依旧没有下降,那就认为这个实验应该早在上一次达到最低测试误差的时候停下来。

这个想法非常直接,用算法表示出来也更容易理解,贴一张之前做的slide:

那么,为什么这个算法能起到“正则化”的效果?也就是为什么它能防止overfit?这就要从定性和定量两个角度来考虑了。

定性来说,我们可以从这张图中看出一些端倪:

图中的同心圆是等高线。右图表示了\(L^2\)正则项的损失函数。实心椭圆是“没有正则化项的目标函数”。这个函数在\(w^*\)处取得最小值。而在坐标轴原点扩散的虚线同心圆表示正则化项本身。而添加了正则化项的损失函数则应该是原始的损失函数与正则化项相加。显然在\(\tilde{w}\)处这个带有正则化的损失函数取得极小值。这就是\(L^2\)正则项“定性”来分析的原理。

再来看左边的图。虚线轨迹是模型的训练过程。因为没有添加正则项,则这个椭圆跟右边的椭圆一模一样,最小值也在\(w^*\)。训练从原点开始,向\(w^*\)进发。而早停止的作用就是,在还没有达到\(w^*\)的位置\(\tilde{w}\)处结束训练。可以发现,此时早停止起到了\(L^2\)正则化项的作用。

说完了定性,再说说定量。

我们为什么能认定早停止就是起到正则项的作用呢?我们需要建立一个模型来分析它。

对于早停止来说,我们可以假定一个参数\(\tau\)。这个参数表示“训练步”。\(\tau\)也是一个模型的超参数,训练过程相当于不但要训练模型,还要寻找到一个合适的“\(\tau\)”。

这时候,我们对损失函数在\(w^*\)处用二次逼近展开,即:

$$\hat{J}(\theta)=J(w^*)+\frac{1}{2}(w-w^*)^T\mathbf{H}(w-w^*)$$

其中,\(\mathbf{H}\)是海森矩阵。

为了应用梯度下降算法,我们对这个损失函数求导:

$$\nabla_w\hat{J}(w)=\mathbf{H}(w-w^*)$$

然后应用梯度下降,此时由于参数\(\tau\)的参与,梯度下降算法表示为:

$$ \begin{eqnarray} w^{(\tau)}&=&w^{(\tau-1)}-\epsilon\nabla_wJ(w^{(\tau-1)}) \\
&=&w^{(\tau-1)}-\epsilon\mathbf{H}(w^{(\tau-1)}-w^*) \\ w^{(\tau)}-w^*&=&(\mathbf{I}-\epsilon\mathbf{H})(w^{(\tau-1)}-w^*)
\end{eqnarray} $$

此时,我们利用\(\mathbf{H}\)的特征分解:\(\mathbf{H}=Q\Lambda Q^T\)。其中\(\Lambda\)是对角阵,\(Q\)是特征向量的一组标准正交基。此时:

$$ \begin{eqnarray} w^{(\tau)}-w^*&=&(\mathbf{I}-\epsilon Q\Lambda Q^T)(w^{(\tau-1)}=w^*)\\
Q^T(w^{(\tau)}-w^*)&=&(\mathbf{I}-\epsilon\Lambda)Q^T(w^{(\tau-1)}-w^*)
\end{eqnarray} $$

原书中忽略了几项推导,下面我给补上:

$$ \begin{eqnarray} Q^T(w^{(\tau)}-w^*)&=&(\mathbf{I}-\epsilon\Lambda)Q^T(w^{(\tau-1)}-w^*)\\
&=&(\mathbf{I}-\epsilon\Lambda)(\mathbf{I}-\epsilon\Lambda)Q^T(w^{(\tau-1)}-w^*)\\ &\dots& \\ &=&(\mathbf{I}-\epsilon\Lambda)^{\tau}Q^T(w^{(0)}-w^*) \end{eqnarray} $$

所以

$$ \begin{eqnarray} Q^Tw^{(\tau)}-Q^Tw^*&=&(\mathbf{I}-\epsilon\Lambda)^{\tau}Q^Tw^{(0)}-(\mathbf{I}-\epsilon\Lambda)^{\tau}Q^Tw^* \\
Q^Tw^{(\tau)}&=&(\mathbf{I}-\epsilon\Lambda)^{\tau}Q^Tw^{(0)}+Q^Tw^*-(\mathbf{I}-\epsilon\Lambda)^{\tau}Q^Tw^* \\
&=&(\mathbf{I}-\epsilon\Lambda)^{\tau}Q^Tw^{(0)}+\left[\mathbf{I}-(\mathbf{I}-\epsilon\Lambda)^{\tau}\right]Q^Tw^* \\ \end{eqnarray} $$

由于\(w^{(0)}=0\)(先暂时忽略权值随机初始化),所以

$$ Q^Tw^{(\tau)}=\left[\mathbf{I}-(\mathbf{I}-\epsilon\Lambda)^{\tau}\right]Q^Tw^*
$$

这个时候,让我们回顾一下在定量分析\(L^2\)正则项时,通过类似的二次近似得到的表达式(此时\(\tilde{w}\)表示添加了\(L^2\)正则化项之后的损失函数的最佳参数):

$$ Q^T\tilde{w}=(\Lambda-\alpha\mathbf{I})^{-1}\Lambda Q^Tw^*
$$

我们队它做个小小的变动: $$ Q^T\tilde{w}=\left[\mathbf{I}-(\Lambda-\alpha\mathbf{I})^{-1}\alpha\right]Q^Tw^*
$$

将这个式子与上面的早停止的式子放在一起对比一下:

$$ \begin{eqnarray} Q^Tw^{(\tau)}&=&\left[\mathbf{I}-(\mathbf{I}-\epsilon\Lambda)^{\tau}\right]Q^Tw^* \\
Q^T\tilde{w}&=&\left[\mathbf{I}-(\Lambda-\alpha\mathbf{I})^{-1}\alpha\right]Q^Tw^*
\end{eqnarray} $$

显然,用待定系数法我们可以得到这样一个等式:

$$(\mathbf{I}-\epsilon\Lambda)^{\tau}=(\Lambda-\alpha\mathbf{I})^{-1}\alpha$$

那么\(L^2\)正则化和早停止至少在对目标函数二次近似的意义上是等价的。

更进一步,通过取对数,然后使用\(\log(1+x)\)的级数展开之后我们会有这样的结论:如果所有的\(\lambda_i\)都比较小(也就是\(\epsilon\lambda_i<<1\)并且\(\lambda_i/\alpha<<1\))则 $$ \begin{eqnarray} \tau&\approx&\frac{1}{\epsilon\alpha} \\ \alpha&\approx&\frac{1}{\tau\epsilon} \end{eqnarray} $$

也就是说,在这些假设下,训练迭代次数\(\tau\)实际上与\(L^2\)正则项参数成反比。\(\tau\epsilon\)的倒数与权值衰减系数有相同的作用。

Friskit

继续阅读此作者的更多文章