六、二阶近似方法

1. 为了简化问题，这里考察目标函数为经验风险函数（即：不考虑正则化项）：

   

   .

6.1 牛顿法

6.1.1 牛顿法算法

1. 牛顿法在某点 附近，利用二阶泰勒展开来近似 ：

   

   其中 为 对于 的海森矩阵在 处的值。

   如果求解这个函数的临界点，根据 ，则得到牛顿法的更新规则：

   

   • 如果 为 的二次函数，则牛顿法会直接跳到极值或者鞍点。

     • 如果 是正定的，则跳到的点是极小值点。
     • 如果 是负定的，则跳到的点是极大值点。
     • 如果 是非正定、非负定的，则跳到的点是鞍点。因此，牛顿法会主动跳到鞍点。
   • 如果 为 的高阶的，则需要迭代。

2. 牛顿法：

   • 输入：

     • 初始参数
     • 包含 个样本的训练集

   • 算法步骤：

     迭代，直到到达停止条件。迭代步骤为：

     • 计算梯度：
     • 计算海森矩阵：
     • 计算海森矩阵的逆矩阵：
     • 计算更新：
     • 应用更新：

6.1.2 牛顿法性质

1. 只要海森矩阵保持正定，牛顿法就能够迭代的使用。

2. 在深度学习中目标函数具有很多鞍点，海森矩阵的特征值并不全为正的，因此使用牛顿法有问题：在靠近鞍点附近，牛顿法会导致参数更新主动朝着鞍点的方向移动，这是错误的移动方向。

   解决的办法是：使用正则化的海森矩阵。

3. 常用的正则化策略是：在海森矩阵的对角线上增加常数 。

   于是更新过程为： 。

   • 这个正则化策略是牛顿法的近似。

   • 只要海森矩阵的负特征值都在零点附近，则可以起到效果。

   • 当有很强的负曲率存在时（即存在绝对值很大的负的特征值）， 可能需要特别大。

     但是如果 增大到一定程度，则海森矩阵就变得由对角矩阵 主导。此时，牛顿法选择的方向就是 的方向。

4. 海森矩阵的元素的数量是参数数量的平方。如果参数数量为 ，则牛顿法需要计算一个 矩阵的逆，计算一次参数更新的复杂度为 。

   由于每次参数更新时都将改变参数，因此每轮迭代训练都需要计算海森矩阵的逆矩阵，计算代价非常昂贵。因此只有参数很少的网络才能够在实际中应用牛顿法训练，绝大多数神经网络不能采用牛顿法训练。

5. 综上所述，牛顿法有两个主要缺点：

   • 主动跳向鞍点。
   • 逆矩阵的计算复杂度太大，难以计算。

6.2 BFGS

1. BFGS算法具有牛顿法的一些优点，但是没有牛顿法的计算负担。

   大多数拟牛顿法（包括 BFGS）采用矩阵 来近似海森矩阵的逆矩阵，当 更新时，下降方向为 。

   在该方向上的线性搜索到的最佳学习率为 ，则参数更新为： 。

2. BFGS算法迭代了一系列线性搜索，其方向蕴含了二阶信息。

   与共轭梯度不同，BFGS的成功并不需要线性搜索真正找到该方向上接近极小值的一点（而是探索一部分点）。因此BFGS在每个线性搜索上花费更少的时间。

3. BFGS算法必须存储海森矩阵逆矩阵的近似矩阵 ，需要 的存储空间。因此BFGS不适用于大多数具有百万级参数的现代深度学习模型。

   L-BFGS通过避免存储完整的海森矩阵的逆的近似矩阵 来降低存储代价，它假设起始的 为单位矩阵，每步存储一些用于更新 的向量，并且每一步的存储代价是 。