深度学习笔记(三)

牛顿法与BFGS

Posted by Pelhans on April 11, 2019

概览

与一阶的相比,二阶梯度方法使用二阶导数改进了优化。最广泛使用的二阶方法是牛顿法。

牛顿法

牛顿法是给予二阶泰勒级数展开在某点 $\theta_{0}$附近来近似 $J(\theta)$的方法,它忽略了高于二阶的导数:

对上式两侧同时求梯度,得到函数的导数为:

令梯度等于0:

可得:

将 $\nabla^{2}f(x_{0}) $ 记为 H, $\nabla f(x_{0})$ 记为 g,则得到更新公式:

其中 $-H^{-1}g $ 称为牛顿方向。迭代的终止条件是梯度的模接近于0或者函数值下降小于指定阈值。

对于局部的二次函数(具有正定的H),牛顿法会直接调到极小值。对于非二次的表面,只要 Hessian 矩阵保持正定,牛顿法能够迭代地应用。

ps: Hessian 矩阵正定的话, 函数的二阶偏导数大于0, 函数的一阶导数始终处于递增状态, 函数为凸函数。因此,在诸如牛顿法等梯度方法中,使用 Hessian 矩阵的正定性可以非常便捷的判断函数是否有凸性,也就是是否可收敛到局部/全局的最优解

但在深度学习中,目标函数的表面通常是非凸的,因此使用牛顿法是有问题的。如在靠近鞍点处牛顿法会朝着错误的方向移动,这种情况可以通过正则化 Hessian 来避免。另一个缺点是,牛顿法需要计算 Hessian 矩阵的逆,这将带来非常大的计算量,若 Hessian 不可逆,则牛顿法将失效。

拟牛顿法

对于上面提到的牛顿法的缺点,提出了一些改进方法,典型的代表是拟牛顿算法(Quasi-Newton)。拟牛顿算法的思想是不计算目标函数的 Hessian 矩阵然后求逆,而是通过其他手段得到 Hessian 矩阵或者 H的逆矩阵的近似矩阵。具体做法是构造一个近似 Hessian矩阵或逆矩阵的正定对称矩阵,用它来进行牛顿法的迭代。

这个近似矩阵不是随意构造的,需要满足拟牛顿条件:

该条件的来源就是对泰勒展开式的两侧同时求导,而后移项即可。

首先做泰勒展开

然后两边同时求梯度

,

令 $x = x_{k}$, 带入有

最终有

牛顿条件是迭代过程中对 Hessian 矩阵的约束,拟牛顿法选取的近似矩阵也需要满足该条件。

BFGS

BFGS 是 Broyden-Fletcher-Goldfarb-Shanno 的缩写。算法的核心思想是构造 Hessian 矩阵的近似矩阵 B,而后用 B 来代替 H进行更新:

等价于:

算法更新流程是,一开始 B是单位矩阵 I,k=0,而后以此计算个变量得到$\Delta B$,更新它,然后重复迭代。

若记 , ,应用 Sherman-Morrison 公式可以将上述公式改写为

有了 Hessian 矩阵的逆,我们就可以根据求得的一阶梯度来更新求得最优参数。

BFGS 算法必须存储 H 矩阵 的逆矩阵,比较耗费内存。为此提出改进方案 L-BFGS,其思想是不存储完成的逆矩阵,而是只存储向量 S 和 Y(对于 G 来说就是存 $\delta_{k}, y_{k}$)。

深度学习中为什么不用牛顿法去优化?

  • 神经网络通常是非凸的,这种情况下,牛顿法的收敛性难以保证
  • 即使是凸优化,只有在迭代点离全局最优很近时,牛顿法才会体现出收敛快的优势
  • 可能被鞍点吸引

参考

深度学习 理解牛顿法