梯度下降法和牛顿法

前言

最近做项目需要深度学习的内容,于是阅读了《deep learning》这部经典书籍。参考其中有关机器学习的内容,在此整理优化算法中广泛应用的梯度下降法和牛顿法。

一、梯度下降法

优化指的是改变$ x $以最小化或最大化某个函数$f(x)$的任务。我们通常以最小化$f(x)$指代大多数最优化问题。

针对具有多维输入的函数,梯度是相对一个向量求得的导数,记为:$\nabla_xf(x)$。在$\mu$(单位向量)方向的方向导数是函数在$\mu$方向的斜率。为了最小化$f$,我们希望找到使$f$下降得最快的方向。计算方向导数:

这在$\mu$与梯度方向相反时取得最小。换句话说,梯度向量指向上坡,负梯度向量指向下坡。我们在负梯度方向上移动可以减小$f$.因此最速下降建议新的点为:

其中$\epsilon$为学习率,是一个确定步长大小的正标量。其选择的方式有几种:

  1. 选择一个小的常数,缺点是收敛速度太慢。
  2. 线搜索,其优点在于能以较快的速度收敛于临界点。可以进一步分为:
    • 精确线搜索:包括黄金分割法、抛物线法等等。
    • 非精确线搜索:Wolfe准则、Armijo准则等。
  3. 利用Hessian矩阵计算使泰勒级数下降最多的最优步长:其中$g$是梯度,$H$是$x_0$点的Hessian矩阵。其本质是根据$f(x)$在$x_0$的近似二阶泰勒展开级数:于是有:当$g^THg$为正时,可以通过二次方程求解出最优$\epsilon$。最坏的情况下,$g$与$H$最大特征值$\lambda$对应的特征向量对齐,则最优步长是$\frac{1}{\lambda_{max}}$ 。

二、牛顿法

梯度下降法没有利用到二阶导数的信息,不知道导数的变化,所以也不知道应该优先探索导数长期为负的方向。如下图的例子,在此情况下最陡峭的方向实际上不是最有前途的搜索方向。
梯度
我们可以使用Hessian矩阵的信息来指导搜索,以解决这个问题。其中最简单的方法是牛顿法。其基于二阶泰勒展开:

据此可以得到函数驻点为:

牛顿法则需要多次迭代。迭代地更新近似函数和跳到近似函数的最小点可以比梯度下降更快地到达临界点。当附近的临界点是最小点(Hessian 的所有特征值都是正的)时牛顿法才适用,而梯度下降不会被吸引到鞍点(除非梯度指向鞍点)。

总结

仅使用梯度信息的优化算法被称为 一阶优化算法,如梯度下降。使用Hessian矩阵的优化算法被称为 二阶最优化算法,如牛顿法。

您的支持是我创造源源不断地动力