机器学习与运筹优化（四）优化算法的动量加速技巧

pc8888888

摘要：本文介绍随机梯度下降法及几种常见的加速技巧，包括动量加速梯度下降法，Nesterov加速梯度下降法，Adam法等
在之前的几篇文章里，我们介绍了收敛速率和计算复杂度的关系。在大数据时代，机器学习问题的规模越来越大，深度神经网络的层数越来越多，人们更加倾向于简单而复杂度低的算法，于是人们的目光从二阶算法又回到了一阶算法，例如梯度下降法（gradient descent）：



梯度下降法只需要计算函数的梯度，复杂度为O（n）。如果使用最速下降法的精确步长，那么复杂度就是O（n^2），所以在机器学习中，一般使用非精确步长（如固定步长，或是有规律地减小的步长），总的复杂度只有O（n）。
即使如此，有时候n的规模在亿万级别，每一次迭代耗费的计算代价还是比较大，于是人们想到，可以考虑随机抽取梯度的部分信息，每次只更新一部分变量，如果每次采样的数字是m，那么复杂度就是O（m），大大减小了计算量，这就是随机梯度下降法（stochastic gradient descent）：



除了减小计算量，人们还考虑如何加速算法的收敛，比如一般的梯度下降法，在函数变动剧烈时，容易出现Zigzag现象：



前文介绍过BB法利用了上一步精确步长，从而加速收敛，但是BB法要求使用精确步长，跟最速下降法一样，精确步长的计算复杂度是O（n^2）。于是人们想到，在使用非精确步长的情况下，是否也可以利用上一步的信息加速收敛呢？这就是动量加速梯度下降法（momentum accelerated gradient）：



动量加速方法可以当做一种“自适应”方法，如果当前梯度和之前梯度的方向一致，说明我们在走正确的道路，就会朝这个方向加速，就像球从高处滚下来时，累积的动量越大，速度越快。而如果当前梯度和历史梯度的方向不一致，说明当前函数变动剧烈，就会减速调整方向。



但是熟悉BB法的朋友可能会发现，这种算法和最速下降法有着相同的缺点：梯度变化滞后于函数变化。于是改进的思路也是类似的：预测下一个时刻的函数变化，以修正这一步的动量，这就是Nesterov加速梯度下降法（Nesterov accelerated gradient）：



可以证明，Nesterov方法是二阶收敛的，而且是这一类一阶优化方法框架中最好的方法。
之后大家提出了多种加速方法，包括Adagrad方法，通过累加历史参数的平方和，调整不同频率的参数的更新步长（学习率）；Adadelta方法和RMSprop方法则把平方和改为期望以调整学习率，避免Adagrad方法后期梯度消失的问题，等等。
Adam(Adaptive Moment Estimation)方法可以看做是动量加速和学习率调整的结合：



其中mt跟之前的动量加速方法类似，是利用动量累积的思路，而mt’是mt的无偏估计，对更新进行调整，同时还计算了累积的梯度平方信息vt，vt’是vt的无偏估计，对步长进行了动态约束。
Adam方法可以看作是动量加速方法的集大成者，一方面通过动量累积调整前进方法，另一方面用累积的二阶信息调整步长，对于很多机器学习问题都有良好的效果，而且因为简单和计算量小，Adam方法被认为是机器学习与深度学习初学者必备技能，当你对这个问题的结构不了解时，不妨试试Adam算法。
Adam方法也有很多变体，包括把L2模改为最大模的AdaMax方法，把动量加速换为Nesterov加速的NAdam方法，等等。
本文介绍的动量加速技巧，不只适用于梯度下降法，对于其他的优化算法，包括无约束优化的一阶与二阶算法，约束优化的对偶算法等等，一般来说都可能有效。在优化界，这些技巧一般不作为单独的算法，而是作为构造新算法的技巧，以及做数值实验时加速收敛的方法。
BB法、拟牛顿法与动量加速算法，都有利用二阶信息的思想，但是BB法改进的是精确步长，拟牛顿法改进的是搜索方向，动量加速算法改进的是动态步长的更新策略。理论上说，方向、步长、策略等改进方法可以混用，在实际应用中都值得考虑，可以根据问题的结构进行选择。
一般来说直接应用Adam算法得到的结果通常都不会太差，但是做机器学习研究时，还是要注意问题的结构，例如空间维度有多大，函数和约束条件是否非凸，数据是否稀疏，内存条件适用于什么样的计算复杂度，等等。

参考文献
[1] Liu, Dong C., and Jorge Nocedal. "On the limited memory BFGS method for large scale optimization."Mathematical programming 45, no. 1-3 (1989): 503-528.
[2]袁亚湘, 孙文瑜. "最优化理论与方法." 科学出版社, 1997 年 1 月 (1997)

作者：火龙果一号
编辑：蜜汁酱