Question

在本节中，我们会讨论训练深度神经网络的二阶方法。参考LeCun et al.（1998a）了解该问题的早期处理方法。为表述简单起见，我们只考察目标函数为经验风险：

然而，我们在这里讨论的方法很容易扩展到更一般的目标函数，例如，第7章讨论的包括参数正则项的函数。

8.6.1　牛顿法

在第4.3节，我们介绍了二阶梯度方法。与一阶方法相比，二阶方法使用二阶导数改进了优化。最广泛使用的二阶方法是牛顿法。我们现在更详细地描述牛顿法，重点在其应用于神经网络的训练。

牛顿法是基于二阶泰勒级数展开在某点θ₀附近来近似J(θ)的优化方法，其忽略了高阶导数：

其中H是J相对于θ的Hessian矩阵在θ₀处的估计。如果我们再求解这个函数的临界点，将得到牛顿参数更新规则：

因此，对于局部的二次函数（具有正定的H），用H _-1重新调整梯度，牛顿法会直接跳到极小值。如果目标函数是凸的但非二次的（有高阶项），该更新将是迭代的，得到和牛顿法相关的算法，如算法8.8所示。

对于非二次的表面，只要Hessian矩阵保持正定，牛顿法能够迭代地应用。这意味着一个两步迭代过程。首先，更新或计算Hessian逆（通过更新二阶近似）。其次，根据式（8.27）更新参数。

算法8.8　目标为的牛顿法。

Require：初始参数θ₀

Require：包含m个样本的训练集

while没有达到停止准则do

计算梯度：

计算Hessian矩阵：

计算Hessian逆：

计算更新：

应用更新：

end while

在第8.2.3节，我们讨论了牛顿法只适用于Hessian矩阵是正定的情况。在深度学习中，目标函数的表面通常非凸（有很多特征），如鞍点。因此使用牛顿法是有问题的。如果Hessian矩阵的特征值并不都是正的，例如，靠近鞍点处，牛顿法实际上会导致更新朝错误的方向移动。这种情况可以通过正则化Hessian矩阵来避免。常用的正则化策略包括在Hessian矩阵对角线上增加常数α。正则化更新变为

这个正则化策略用于牛顿法的近似，例如Levenberg-Marquardt算法（Levenberg，1944；Marquardt，1963），只要Hessian矩阵的负特征值仍然相对接近零，效果就会很好。在曲率方向更极端的情况下，α的值必须足够大，以抵消负特征值。然而，如果α持续增加，Hessian矩阵会变得由对角矩阵αI主导，通过牛顿法所选择的方向会收敛到普通梯度除以α。当很强的负曲率存在时，α可能需要特别大，以至于牛顿法比选择合适学习率的梯度下降的步长更小。

除了目标函数的某些特征带来的挑战，如鞍点，牛顿法用于训练大型神经网络还受限于其显著的计算负担。Hessian矩阵中元素数目是参数数量的平方，因此，如果参数数目为k（甚至是在非常小的神经网络中k也可能是百万级别），牛顿法需要计算k×k矩阵的逆，计算复杂度为O(k³)。另外，由于参数将每次更新都会改变，每次训练迭代都需要计算Hessian矩阵的逆。其结果是，只有参数很少的网络才能在实际中用牛顿法训练。在本节的剩余部分，我们将讨论一些试图保持牛顿法优点，同时避免计算障碍的替代算法。

8.6.2　共轭梯度

共轭梯度是一种通过迭代下降的共轭方向（conjugate directions）以有效避免Hessian矩阵求逆计算的方法。这种方法的灵感来自对最速下降方法弱点的仔细研究（详细信息请查看第4.3节），其中线搜索迭代地用于与梯度相关的方向上。图8.6说明了该方法在二次碗型目标中如何表现的，是一个相当低效的来回往复，锯齿形模式。这是因为每一个由梯度给定的线搜索方向，都保证正交于上一个线搜索方向。

图8.6　将最速下降法应用于二次代价表面。在每个步骤中，最速下降法沿着由初始点处的梯度定义的线跳到最低代价的点。这解决了图4.6中使用固定学习率所遇到的一些问题，但即使使用最佳步长，算法仍然朝最优方向曲折前进。根据定义，在沿着给定方向的目标最小值处，最终点处的梯度与该方向正交

假设上一个搜索方向是。在极小值处，线搜索终止，方向处的方向导数为零：。因为该点的梯度定义了当前的搜索方向，将不会贡献于方向。因此方向正交于。最速下降多次迭代中，方向和之间的关系如图8.6所示。如图展示的那样，下降正交方向的选择不会保持前一搜索方向上的最小值。这产生了锯齿形的过程。在当前梯度方向下降到极小值，我们必须重新最小化之前梯度方向上的目标。因此，通过遵循每次线搜索结束时的梯度，我们在某种程度上撤销了在之前线搜索的方向上取得的进展。共轭梯度试图解决这个问题。

在共轭梯度法中，我们寻求一个和先前线搜索方向共轭（conjugate）的搜索方向，即它不会撤销该方向上的进展。在训练迭代t时，下一步的搜索方向d_t的形式如下：

其中，系数β_t的大小控制我们应沿方向d_t−1加回多少到当前搜索方向上。

如果，其中H是Hessian矩阵，则两个方向d_t和d_t−1被称为共轭的。

适应共轭的直接方法会涉及H特征向量的计算以选择β_t。这将无法满足我们的开发目标：寻找在大问题比牛顿法计算更加可行的方法。我们能否不进行这些计算而得到共轭方向？幸运的是，这个问题的答案是肯定的。

两种用于计算β_t的流行方法是

（1）Fletcher-Reeves：

（2）Polak-Ribi`ere：

对于二次曲面而言，共轭方向确保梯度沿着前一方向大小不变。因此，我们在前一方向上仍然是极小值。其结果是，在k-维参数空间中，共轭梯度只需要至多k次线搜索就能达到极小值。共轭梯度算法如算法8.9所示。

算法8.9　共轭梯度方法。

Require：初始参数θ₀

Require：包含m个样本的训练集

初始化ρ₀＝0

初始化g₀＝0

初始化t＝1

while没有达到停止准则do

初始化梯度g _t＝0

计算梯度：

计算

（非线性共轭梯度：视情况可重置β_t为零，例如t是常数k的倍数时，如k＝5）

计算搜索方向：

执行线搜索寻找：

（对于真正二次的代价函数，存在的解析解，而无须显式地搜索）

应用更新：

t←t＋1

end while

非线性共轭梯度：目前，我们已经讨论了用于二次目标函数的共轭梯度法。当然，本章我们主要关注于探索训练神经网络和其他相关深度学习模型的优化方法，其对应的目标函数比二次函数复杂得多。或许令人惊讶，共轭梯度法在这种情况下仍然是适用的，尽管需要做一些修改。没有目标是二次的保证，共轭方向也不再保证在以前方向上的目标仍是极小值。其结果是，非线性共轭梯度算法会包括一些偶尔的重设，共轭梯度法沿未修改的梯度重启线搜索。

实践者报告，在实践中使用非线性共轭梯度算法训练神经网络是合理的，尽管在开始非线性共轭梯度前使用随机梯度下降迭代若干步来初始化效果更好。另外，尽管（非线性）共轭梯度算法传统上作为批方法，小批量版本已经成功用于训练神经网络（Le et al.，2011）。针对神经网路的共轭梯度应用早已被提出，例如缩放的共轭梯度算法（Moller，1993）。

8.6.3　BFGS

Broyden-Fletcher-Goldfarb-Shanno（BFGS）算法具有牛顿法的一些优点，但没有牛顿法的计算负担。在这方面，BFGS和CG很像。然而，BFGS使用了一个更直接的方法近似牛顿更新。回顾牛顿更新，由下式给出

其中，H是J相对于θ的Hessian矩阵在θ₀处的估计。运用牛顿法的主要计算难点在于计算Hessian逆H _-1。拟牛顿法所采用的方法（BFGS是其中最突出的）是使用矩阵M_t近似逆，迭代地低秩更新精度以更好地近似H _-1。

BFGS近似的说明和推导出现在很多关于优化的教科书中，包括Luenberger（1984）。

当Hessian逆近似M_t更新时，下降方向ρ_t为ρ_t=M_tg_t 。该方向上的线搜索用于决定该方向上的步长。参数的最后更新为

和共轭梯度法相似，BFGS算法迭代一系列线搜索，其方向含二阶信息。然而和共轭梯度不同的是，该方法的成功并不严重依赖于线搜索寻找该方向上和真正极小值很近的一点。因此，相比于共轭梯度，BFGS的优点是其花费较少的时间改进每个线搜索。另一方面，BFGS算法必须存储Hessian逆矩阵M，需要O(n²)的存储空间，使BFGS不适用于大多数具有百万级参数的现代深度学习模型。

存储受限的BFGS（或L-BFGS）　通过避免存储完整的Hessian逆近似M，BFGS算法的存储代价可以显著降低。L-BFGS算法使用和BFGS算法相同的方法计算M的近似，但起始假设是M^(t−1)是单位矩阵，而不是一步一步都要存储近似。如果使用精确的线搜索，L-BFGS定义的方向会是相互共轭的。然而，不同于共轭梯度法，即使只是近似线搜索的极小值，该过程的效果仍然不错。这里描述的无存储的L-BFGS方法可以拓展为包含Hessian矩阵更多的信息，每步存储一些用于更新M的向量，且每步的存储代价是O(n)。