常用优化算法介绍

作者：Walker

在机器学习的世界中，通常我们会发现有很多问题并没有最优的解，或是要计算出最优的解要花费很大的计算量，面对这类问题一般的做法是利用迭代的思想尽可能的逼近问题的最优解。我们把解决此类优化问题的方法叫做优化算法，优化算法本质上是一种数学方法，常见的优化算法包括梯度下降法、牛顿法、Momentum、Nesterov Momentum、Adagrad、Adam等。其实大部分机器学习算法的本质都是建立优化模型，通过优化算法对损失函数（优化的目标函数）进行优化，从而训练出最好的模型。

(1)梯度下降法：
梯度下降法是最常用的一种优化算法。其核心思想是：在当前位置寻找梯度下降最快的方向，来逐渐逼近优化的目标函数。且离目标函数越近，逼近的“步伐”也就越小。梯度下降法本质是一种迭代方法，常用于机器学习算法的模型参数求解。其示意图如下图1所示：

图1梯度下降法

梯度下降法的更新公式为：

其中α为梯度上每次逼近的步长，前边的“-”表示搜索方向为负梯度的方向，L我损失函数。算法更新终止的条件是梯度向量接近于0即可。此外需要特别注意的是，梯度下降法不一定能够找到全局的最优解，很有可能找到的是一个局部最优解。

（2）梯度下降法的变式

通常基于梯度的下降方法又有很多变式，我们主要为大家介绍：随机梯度下降法（SDG）、Momentum、Nesterov Momentum、Adagrad、Adam。

随机梯度下降法是每次使用一批数据进行梯度的计算，而非计算全部数据的梯度，因为如果每次计算全部数据的梯度，会导致运算量加大，运算时间变长，容易陷入局部最优解，而随机梯度下降可能每次不是朝着真正最小的方向，这样反而可以跳出局部的最优解。

Momentum是在随机梯度下降法的基础上，增加了动量（Momentum）的技术。其核心是通过优化相关方向的训练和弱化无关方向的振荡，来加速SGD训练。Momentum的方法能够在一定程度上缓解随机梯度下降法收敛不稳定的问题，并且有一定的摆脱陷入局部最优解的能力。

Nesterov Momentum是基于Momentum的加速算法，相比于传统的动量算法，最大的优化是计算经过动量更新之后的位置梯度。

Adagrad即adaptive gradient，是一种自适应学习率的梯度法。它通过记录并调整每次迭代过程中的前进方向和距离，使得针对不同问题都有一套自适应学习率的方法。Adagrad最大的优势是不需要手动来调整学习率，但与此同时会降低学习率。

Adam即Adaptive Moment Estimation，是能够自适应时刻的估计方法，能够针对每个参数，计算自适应学习率。这是一种综合性的优化方法，在机器学习实际训练中，往往能够取得不错的效果。

（3）牛顿法和拟牛顿法

与上述梯度类型的优化算法最大的不同是，牛顿法是一种二阶收敛算法，所以它的收敛速度相较于一阶算法会更快。牛顿法二阶的意义在于它不仅会沿着梯度最大的方向下降，还会考虑走的下一步坡度是不是也很大，它能够以较远的目光全局的逼近目标函数。其算法的具体步骤为：

1.首先选择接近于函数f(x)的零点x₀，并计算f(x₀)处的斜率f’(x₀)。然后我们求解以下方程，得到比刚刚的x₀更加准确的解x1。

2.接下来我们利用x1进行下一轮的迭代，迭代公式如下所示。这样经过反复的迭代过程，我们便能取得函数f(x)的最优解。

牛顿法的迭代示意图如下所示：

图2 牛顿法

虽然牛顿法相较于梯度下降法等优化算法收敛速度更快，但每一步都需要求解复杂的Hessian矩阵，计算非常不易。所以后来美国Argonne国家实验室的物理学家W.C.Davidon又针对牛顿法计算复杂的缺陷提出了拟牛顿法。它的核心思想是使用正定矩阵来近似Hessian矩阵的逆，从而简化了运算的复杂。另外，因为拟牛顿法不需要二阶导数的信息，所以现在拟牛顿法在机器学习实际问题中应用更加的广泛。

【总结】：除了以上几类较为常见的优化算法以外，还有共轭梯度法、启发式优化算法等。在实际的机器学习问题中，往往需要具体问题具体分析，根据每类优化问题的特征，选择合适的优化算法。