Question

1. 当训练一个容量较大的模型时会经常发现：训练误差逐渐降低，但是验证误差先下降后上升。

   当验证误差没有进一步改善时，算法就提前终止。这种策略被称作早停early stopping。

   

2. 早停是深度学习中最常用的正则化形式，因为它简单、有效。

3. 当训练终止时，返回的不是最新的模型参数，而是验证误差最小的模型参数，因此需要频繁存储模型参数。

5.1 早停算法

1. 早停算法：

   • 输入：

     • 当前验证集的误差非最小值的次数 $ MathJax-Element-300 $
     • 验证集验证的间隔 $ MathJax-Element-455 $
     • 初始参数 $ MathJax-Element-380 $

   • 输出：

     • 最佳参数 $ MathJax-Element-282 $
     • 获得最佳参数时迭代的步数 $ MathJax-Element-315 $

   • 算法步骤：

     • 初始化：

       • 参数变量 $ MathJax-Element-284 $
       • 迭代步数变量 $ MathJax-Element-285 $
       • 验证次数变量 $ MathJax-Element-286 $
       • 验证集的最小误差 $ MathJax-Element-287 $
       • 最佳参数 $ MathJax-Element-288 $
       • 最佳迭代步数 $ MathJax-Element-289 $

     • 循环，循环条件为： $ MathJax-Element-290 $ ：

       • 学习模型 $ MathJax-Element-455 $ 步（每隔 $ MathJax-Element-455 $ 步验证一次）

       • 更新 $ MathJax-Element-293 $

       • 记录最新的验证集误差 $ MathJax-Element-294 $

       • 如果 $ MathJax-Element-295 $ ，则： $ MathJax-Element-296 $ 。

         如果 $ MathJax-Element-297 $ ，则： $ MathJax-Element-298 $ 。

         若当前验证集误差是最小的，则 $ MathJax-Element-299 $ 清零。这意味着必须连续 $ MathJax-Element-300 $ 次 $ MathJax-Element-301 $ ，才说明算法到达终止条件。

2. 可以认为早停是一个非常高效的超参数选择算法：训练步数是一个超参数，该超参数在验证误差上具有 U形曲线。

   • 早停策略通过控制训练步数来控制模型的有效容量capacity 。
   • 早停策略只需要跑一轮训练就能够得到很多的超参数（即：训练步数）及其对应的验证误差。

3. 早停策略的代价有两个：

   • 需要在训练期间定期评估验证集。

     • 可以通过并行的执行训练和验证来加速这一过程。
     • 也可以选取一个较小的验证集、或者不那么频繁地评估验证集来减小评估代价。

   • 需要保持最佳的参数的副本。

     这种代价一般可以忽略不计。

4. 早停是正则化的一种非常不起眼的形式，其优点有：

   • 它几乎不需要干涉基本的训练过程，适合任何模型。
   • 可以单独使用，或者与其他的正则化策略相结合。
   • 早停不仅有正则化的好处，还有降低计算成本的好处。

5. 以泛化误差的偏差方差分解角度来看，早停试图同时解决偏差和方差，其结果很可能导致得到的模型并不是一个最优的模型。

   如下图中所示的验证误差曲线。因为提前停止了训练，所以使得代价函数的值可能不够小，即：偏差可能还可以继续降低。方差（即：验证误差与训练误差之间的gap ) 虽然处于上升趋势，但是它们叠加的结果可能导致验证误差呈现波动走势。

   

5.2 二次训练

1. 早停需要验证集，这意味着某些样本不能用于模型的训练过程，这会造成数据的浪费。

   为了更好地利用验证集的样本，可以在早停之后进行额外的训练。在第二轮额外的训练中，所有的训练数据都被包括在内（包括验证集）。

   有两个基本的策略可以用于第二轮训练过程 ：

   • 保留迭代步：再次初始化模型，然后使用所有数据再次训练。此时使用第一轮早停确定的最佳步数作为第二轮的迭代步数。

     该策略重新训练模型，成本较高，但是效果较好。

   • 保留参数：保持从第一轮训练中获得的参数，然后使用全部的数据继续训练。此时观察原始验证集的损失函数，直到它低于第一轮停止时的原始训练集的损失函数值。

     根据早停策略，第一轮结束时原始验证集的损失函数值是较大的

     该策略避免了重新训练模型的高成本，但是表现一般。

     这是因为一旦将 $ MathJax-Element-324 $ 合并到训练集，则对它们评估的结果就是训练误差（而不再是验证误差）。新的训练误差小于原来的验证误差，并不能说明模型的泛化能力得到了提升。

2. 保留迭代步二次训练算法：

   • 输入：

     • 训练集 $ MathJax-Element-318 $ ， $ MathJax-Element-319 $
       

   • 步骤：

     • 将 $ MathJax-Element-318 $ 和 $ MathJax-Element-319 $ 分割为 $ MathJax-Element-323 $ 和 $ MathJax-Element-324 $
     • 随机选择参数的初始化值 $ MathJax-Element-380 $ ，将 $ MathJax-Element-323 $ 作为训练集， 将 $ MathJax-Element-324 $ 作为验证集，运行早停算法，返回最佳训练步数 $ MathJax-Element-315 $
     • 再次选择参数的另一个初始化值 $ MathJax-Element-313 $ ，在 $ MathJax-Element-314 $ 上再次训练 $ MathJax-Element-315 $ 步

3. 保留参数二次训练算法：

   • 输入：

     • 训练集 $ MathJax-Element-318 $ ， $ MathJax-Element-319 $
       

   • 步骤：

     • 将 $ MathJax-Element-318 $ 和 $ MathJax-Element-319 $ 分割为 $ MathJax-Element-323 $ 和 $ MathJax-Element-324 $

     • 随机选择参数的初始化值 $ MathJax-Element-380 $ ，将 $ MathJax-Element-323 $ 作为训练集， 将 $ MathJax-Element-324 $ 作为验证集，运行早停算法，返回算法停止时的目标函数的值 $ MathJax-Element-325 $

     • 迭代： $ MathJax-Element-326 $

       • 在 $ MathJax-Element-327 $ 上训练 $ MathJax-Element-455 $ 步 (每隔 $ MathJax-Element-455 $ 步检查一次，为了降低评估代价)

5.3 早停与 L2 正则化

1. 早停将优化过程的参数空间限制在初始参数值 $ MathJax-Element-380 $ 的一个小的邻域内。

2. 假设参数 $ MathJax-Element-331 $ 。令 $ MathJax-Element-332 $ ，它就是无正则化项时使得目标函数最小的权重向量。

   和 $ MathJax-Element-460 $ 正则化中的推导相同，有： $ MathJax-Element-334 $ 。

   $ MathJax-Element-363 $ 为 $ MathJax-Element-413 $ 在 $ MathJax-Element-361 $ 处的海森矩阵， 其中 $ MathJax-Element-526 $ 在 $ MathJax-Element-361 $ 的一个邻域内。

   • 根据梯度下降法，参数的迭代过程为：

     $ \mathbf{\vec w}^{(\tau)}=\mathbf{\vec w}^{(\tau-1)}-\epsilon \nabla_{\mathbf{\vec w}}\hat J(\mathbf{\vec w}^{(\tau-1)})=\mathbf{\vec w}^{(\tau-1)}-\epsilon\mathbf H(\mathbf{\vec w}^{(\tau-1)}-\mathbf{\vec w}^{*})\\ \rightarrow \mathbf{\vec w}^{(\tau)}-\mathbf{\vec w}^{*}=(\mathbf I-\epsilon\mathbf H)(\mathbf{\vec w}^{(\tau-1)}-\mathbf{\vec w}^{*}) $

     注意：这里并没有加入任何正则化项，而是使用 $ MathJax-Element-413 $

   • 将 $ MathJax-Element-363 $ 进行特征分解： $ MathJax-Element-342 $ ，其中 $ MathJax-Element-343 $ 为对角矩阵， $ MathJax-Element-344 $ 为特征向量的一组标准正交基。则有：

     $ \mathbf{\vec w}^{(\tau)}-\mathbf{\vec w}^{*}=\mathbf Q(\mathbf I-\epsilon\Lambda)\mathbf Q^{T}(\mathbf{\vec w}^{(\tau-1)}-\mathbf{\vec w}^{*}) \\ \rightarrow \mathbf Q^{T}(\mathbf{\vec w}^{(\tau)}-\mathbf{\vec w}^{*})=(\mathbf I-\epsilon\Lambda)\mathbf Q^{T}(\mathbf{\vec w}^{(\tau-1)}-\mathbf{\vec w}^{*}) $

   • 令参数向量的初始值为原点： $ MathJax-Element-345 $ ，并且选择 $ MathJax-Element-492 $ 使得 $ MathJax-Element-347 $ （ $ MathJax-Element-348 $ 为 $ MathJax-Element-363 $ 的特征值）。则经过 $ MathJax-Element-377 $ 次参数更新之后： $ MathJax-Element-351 $ 。

3. 根据 $ MathJax-Element-460 $ 正则化项中的推导结果，有：

   $ \tilde{\mathbf{\vec w}}^{*}=\mathbf Q(\mathbf \Lambda+ \alpha\mathbf I)^{-1}\mathbf \Lambda\mathbf Q^{T} \mathbf{\vec w}^{*} \\ \rightarrow \mathbf Q^{T}\tilde{\mathbf{\vec w}}^{*}=(\mathbf \Lambda+ \alpha\mathbf I)^{-1}\mathbf \Lambda\mathbf Q^{T} \mathbf{\vec w}^{*} = [\mathbf I-(\Lambda+\alpha\mathbf I)^{-1}\alpha]\mathbf Q^{T} \mathbf{\vec w}^{*} $

   通过直接写出逆矩阵的形式可以证明等式

   如果超参数 $ MathJax-Element-353 $ 满足： $ MathJax-Element-354 $ ，则 $ MathJax-Element-460 $ 正则化等价于早停。

4. 为了求得三个超参数满足的条件，求解：

   $ \begin{bmatrix} (1-\epsilon\lambda_1)^{\tau}&0&\cdots&0\\ 0&(1-\epsilon\lambda_2)^{\tau}&\cdots&0\\ \vdots&\vdots&\ddots&\vdots\\ 0&0&\cdots&(1-\epsilon\lambda_n)^{\tau}\\ \end{bmatrix}=\begin{bmatrix} \frac{\alpha}{\lambda_1+\alpha}&0&\cdots&0\\ 0&\frac{\alpha}{\lambda_2+\alpha}&\cdots&0\\ \vdots&\vdots&\ddots&\vdots\\ 0&0&\cdots&\frac{\alpha}{\lambda_n+\alpha}\\ \end{bmatrix} $

   则有： $ MathJax-Element-356 $ 。

   两边取对数，然后使用 $ MathJax-Element-357 $ 的级数展开有（假设 $ MathJax-Element-358 $ ，且 $ MathJax-Element-359 $ ）： $ MathJax-Element-360 $ 。

   由于 $ MathJax-Element-361 $ 是 $ MathJax-Element-362 $ 的最小点，因此海森矩阵 $ MathJax-Element-363 $ 是半正定的，因此其特征值 $ MathJax-Element-364 $

   则有： $ MathJax-Element-365 $ 。即： $ MathJax-Element-366 $ 的倒数与 $ MathJax-Element-460 $ 正则化系数的作用类似。

   在给定 $ MathJax-Element-492 $ 的条件下：

   • $ MathJax-Element-377 $ 越小，则正则化系数越大。这与以下事实吻合： $ MathJax-Element-526 $ 从原点出发开始迭代，如果 $ MathJax-Element-377 $ 越小，则 $ MathJax-Element-526 $ 越靠近原点。
   • $ MathJax-Element-377 $ 越大，则正则化系数越小。这与以下事实吻合：此时 $ MathJax-Element-526 $ 迭代足够多步之后会逐渐远离原点。

5. 假设用学习率 $ MathJax-Element-492 $ 进行了 $ MathJax-Element-377 $ 个优化步骤（对应于 $ MathJax-Element-377 $ 个训练迭代）， $ MathJax-Element-381 $ 可以视作模型的有效容量 effective capacity 的度量。

   假设梯度有界，则限制迭代的次数和学习率，会限制 $ MathJax-Element-467 $ 从 $ MathJax-Element-380 $ 能够到达的范围。 $ MathJax-Element-381 $ 的行为就像是 $ MathJax-Element-460 $ 正则化项的系数的倒数。

6. 早停比 $ MathJax-Element-460 $ 正则化更有优势：

   • 早停能够监控验证误差，从而自动在某个较好的参数解的位置终止。

     训练一次就相当于得到了多个超参数 $ MathJax-Element-386 $ 的结果。

   • 采用 $ MathJax-Element-460 $ 正则化需要多次训练，从而选择合适的超参数 $ MathJax-Element-386 $ 的值。

     这种方式的计算成本太高。