划重点！十分钟掌握牛顿法凸优化

AI有道

一个有情怀的公众号

之前，我发过一篇文章，通俗地解释了梯度下降算法的数学原理和推导过程，推荐一看。链接如下：

我们知道，梯度下降算法是利用梯度进行一阶优化，而今天我介绍的牛顿优化算法采用的是二阶优化。本文将重点讲解牛顿法的基本概念和推导过程，并将梯度下降与牛顿法做个比较。

1

牛顿法求解方程的根

有时候，在方程比较复杂的情况下，使用一般方法求解它的根并不容易。牛顿法通过迭代的方式和不断逼近的思想，可以近似求得方程较为准确的根。

牛顿法求根的核心思想是泰勒一阶展开。例如对于方程 f(x) = 0，我们在任意一点 x0 处，进行一阶泰勒展开：

令 f(x) = 0，带入上式，即可得到：

注意，这里使用了近似，得到的 x 并不是方程的根，只是近似解。但是，x 比 x0 更接近于方程的根。效果如下图所示：

然后，利用迭代方法求解，以 x 为 x0，求解下一个距离方程的根更近的位置。迭代公式可以写成：

经过一定次数的有效迭代后，一般都能保证在方程的根处收敛。下面给出整个迭代收敛过程的动态演示。

2

牛顿法凸优化

上一部分介绍牛顿法如何求解方程的根，这一特性可以应用在凸函数的优化问题上。

机器学习、深度学习中，损失函数的优化问题一般是基于一阶导数梯度下降的。现在，从另一个角度来看，想要让损失函数最小化，这其实是一个最值问题，对应函数的一阶导数 f'(x) = 0。也就是说，如果我们找到了能让 f'(x) = 0 的点 x，损失函数取得最小值，也就实现了模型优化目标。

现在的目标是计算 f'(x) = 0 对应的 x，即 f'(x) = 0 的根。转化为求根问题，就可以利用上一节的牛顿法了。

与上一节有所不同，首先，对 f(x) 在 x0 处进行二阶泰勒展开：

上式成立的条件是 f(x) 近似等于 f(x0)。令 f(x) = f(x0)，并对 (x - x0) 求导，可得：

同样，虽然 x 并不是最优解点，但是 x 比 x0 更接近 f'(x) = 0 的根。这样，就能得到最优化的迭代公式：

通过迭代公式，就能不断地找到 f'(x) = 0 的近似根，从而也就实现了损失函数最小化的优化目标。

3

梯度下降 VS 牛顿法

现在，分别写出梯度下降和牛顿法的更新公式：

梯度下降算法是将函数在 xn 位置进行一次函数近似，也就是一条直线。计算梯度，从而决定下一步优化的方向是梯度的反方向。而牛顿法是将函数在 xn 位置进行二阶函数近似，也就是二次曲线。计算梯度和二阶导数，从而决定下一步的优化方向。一阶优化和二阶优化的示意图如下所示：

梯度下降：一阶优化

牛顿法：二阶优化

以上所说的是梯度下降和牛顿法的优化方式差异。那么谁的优化效果更好呢？

首先，我们来看一下牛顿法的优点。第一，牛顿法的迭代更新公式中没有参数学习因子，也就不需要通过交叉验证选择合适的学习因子了。第二，牛顿法被认为可以利用到曲线本身的信息, 比梯度下降法更容易收敛（迭代更少次数）。如下图是一个最小化一个目标方程的例子, 红色曲线是利用牛顿法迭代求解, 绿色曲线是利用梯度下降法求解。显然，牛顿法最优化速度更快一些。

然后，我们再来看一下牛顿法的缺点。我们注意到牛顿法迭代公式中除了需要求解一阶导数之外，还要计算二阶导数。从矩阵的角度来说，一阶导数和二阶导数分别对应雅可比矩阵（Jacobian matrix）和海森矩阵（Hessian matrix）。

Jacobian 矩阵

Hessian 矩阵

牛顿法不仅需要计算 Hessian 矩阵，而且需要计算 Hessian 矩阵的逆。当数据量比较少的时候，运算速度不会受到大的影响。但是，当数据量很大，特别在深度神经网络中，计算 Hessian 矩阵和它的逆矩阵是非常耗时的。从整体效果来看，牛顿法优化速度没有梯度下降算法那么快。所以，目前神经网络损失函数的优化策略大多都是基于梯度下降。

值得一提的是，针对牛顿法的缺点，目前已经有一些改进算法。这类改进算法统称拟牛顿算法。比较有代表性的是 BFGS 和 L-BFGS。

BFGS 算法使用近似的方法来计算 Hessian 矩阵的逆，有效地提高了运算速度。但是仍然需要将整个 Hessian 近似逆矩阵存储起来，空间成本较大。

L-BFGS 算法是对BFGS 算法的改进，不需要存储 Hessian 近似逆矩阵， 而是直接通过迭代算法获取本轮的搜索方向，空间成本大大降低。

总的来说，基于梯度下降的优化算法，在实际应用中更加广泛一些，例如 RMSprop、Adam等。但是，牛顿法的改进算法，例如 BFGS、L-BFGS 也有其各自的特点，也有很强的实用性。

推荐阅读：