深度学习中的梯度下降优化算法

梯度下降变型算法

批量梯度下降算法

本文翻译自http://sebastianruder.com/optimizing-gradient-descent/index.html#batchgradientdescent
普通的梯度下降算法，又称为批量梯度下降算法，会计算整个训练集的数据来得到目标函数的梯度：
$ \theta = \theta-\eta\cdot\bigtriangledown_{\theta}J(\theta)
$
因为我们需要计算整个训练集来进行一次参数更新，这种算法会非常缓慢，而且可能无法满足内存的需求，也不能允许我们进行在线学习。

伪代码可表示如下

for in range(nb_epochs):
trueparams_grad = evaluate_gradient(loss_function,data,params)
    params = params - learning_rate * params_grad

一些开源框架实现了自动求导功能，如果是手动计算梯度，最好进行梯度检查,例如here

随机梯度下降(SGD)

SGD 使用每个训练数据进行参数的更新。
$\theta = \theta-\eta\cdot\bigtriangledown_{\theta}J(\theta;x^{i};y^{i})$
这种方式每进行一次计算更新一次参数，可以加快更新速度和进行在线学习
但这种算法随机性太强容易导致代价函数震荡问题,但同时也有利于跳出具有最优值，找到全局最优。

小批量梯度下降综合两种方法，每次使用包含n个训练数据的数据包进行计算和梯度更新

$$\theta = \theta-\eta\cdot\bigtriangledown_{\theta}J(\theta;x^{i:i+n};y^{i:i+n})$$

伪代码如下

for i in range(nb_epochs):
truenp.random.shuffle(data)
    for batch in get_batches(data,batch_size = bs):
    	params_grad = evaluate_gradient(loss_function,batch,params)
        params = params -learning_rate*params_grad

但是这种方法也需要注意一下问题：

• 选择一个合适的学习率是比较困难的，过小的学习率会使得收敛过于缓慢，过大的学习率可能会导致震荡以致无法收敛
• 采用学习率预置表[11]希望可以通过一个预先设置的学习率的表来随着训练减小学习率，但是这样不能根据具体的数据库改变学习策略[10].
• 所有的参数同时使用相同的学习率进行迭代也是一个问题，如果我们的数据是稀疏的而且我们的特征拥有不同的频率，那么我们不希望同时更新他们，对于那些很少出现的特征，我们希望能够有比较大的更新。
• 另外就是求解复杂非凸目标函数可能陷于局部最优解的问题[19]探讨了优化过程中遇到鞍点的问题，而且鞍点周围经常是平原，梯度在各个方向上都是0.

梯度下降优化算法

下面我们将介绍一些常用的深度学习梯度下降优化算法，我们不会介绍那些对于高维数据训练不适用的算法，例如Newton’s method

Momentum

SGD算法在狭窄的山谷中的下降引导方向上不是很好，这些地方一个方向上的梯度远远大于另外一个方向[1],在这种情况下，SGD算法会表现出一种摇摆不定的优化路线，如下图所示：

Momentum[2]是一种在可以加速SGD，抑制方向摆动的算法，如下图所示，算法通过加入一个因子$\gamma$

$$v_t=\gamma v_{t-1}+\eta\bigtriangledown_{\theta}J(\theta)$$ $$\theta=\theta-v_t$$

在实际中，$\gamma$通常为0.9或者相近的数值

本质上来说，使用这种算法，就好像我们在山顶推下一个球，这个球在下降过程中不断加速，我们的参数更新和这种方式类似，动量因素随着指向相似方向的梯度的增加还增大，这样我们就可以更快的收敛。

Nesterov accelerated gradient

但是，一个球从山上滚下来，盲目的随着倾斜的方向是不满足要求的，我们希望拥有一个智能化的球，它知道目标在哪从而在到达底部之前进行减速。
NAG[7]便是给我们的动量法预见能力的算法，我们知道我们会使用动量(momentum)参数$\gamma v_{t-1}$ 去更新参数 $\theta$,计算$\theta-\gamma v_{t-1}$ 可以给我们下一个参数 $\theta$ 的大致位置，我们现在可以高效地通过计算下一刻的参数进行预测而不是根据目前的参数

$$v_t=\gamma v_{t-1}+\eta\bigtriangledown_{\theta}J(\theta-\gamma v_{t-1})$$ $$\theta=\theta-v_t$$

$\gamma$ 大致设置为0.9，当Momentum第一次计算出当前的梯度，下面短的蓝色的向量，然后向着更新的梯度方向迈一大步，图中长的蓝色的向量，NAG 首先向着变化方向迈出一大步，褐色的向量，测量梯度然后做出修正（绿色的向量），这种前向更新策略避免了前进过快掠过最优值，这种方式在RNNS的一些任务[8]中可能会因此偏差非常大。

Adagrad

Adagrad[3]的原理是，根据参数调整学习率，对不经常更新的参数进行大的更新，对经常更新的参数进行小的更新，由于这个原因，这种方式对于稀疏数据十分合适。Dean等人[4]发现Adagrad算法很好地提高了SGD的鲁棒性，而且使用这种方法在谷歌进行大数据训练，另外，Pennington等人[5]使用Adagrad去训练GloVe word embeddings，因为不常用的词需要更大的更新步伐。
之前我们因为所有的参数$\theta$均使用一个学习率$\eta$，所以会同时对所有参数$\theta_i$在时间点$t$进行更新，因为Adagrad对每个参数分别设置学习率，我们首先
讲解Adagrad每个参数的更新，然后我们会向量化计算。简单的说，我们设置$g_{t,i}$表示参数$\theta_i$在步骤的梯度

$$g_{t,i} = \bigtriangledown_\theta J(\theta_i)$$ $$\theta_{t+1,i} = \theta_{t,i}-\eta \cdot g_{t,i}$$

在更新规则上，Adagrad修改了学习率$\eta$,每个参数，每次更新

$$\theta_{t+1,i} = \theta_{t,i}- \frac{\eta}{\sqrt{G_{t,ii}+\epsilon}}\cdot g_{t,i}$$ $$G_t\in \mathbb{R^{dxd}}$$

是一个对角矩阵，矩阵中对角线元素$i,i$是梯度$\theta_i$在t阶段的平方和，$\epsilon$是一个平滑项参数防止除数为0的情况，有趣的是，如果没有这个平方和开根号，这个算法就表现得差多了。
因为$G_t$包含的对角元素包含所有参数的平方和，我们可以使用元素级别的矩阵乘法来进行向量化计算

$$\theta_{t+1} = \theta_{t}- \frac{\eta}{\sqrt{G_{t}+\epsilon}}\odot g_{t}$$

Adagrad算法的一个好处就是可以消除人工及逆行学习率调节的需要，大多数实现采用默认为0.01然后就不管了。
Adagrad算法的缺点主要是累计的梯度的平方是分母，因为每次加入的梯度都是正数，所以一直在累加，在训练过程中，这会造成学习率越来越小直至消失，这样就无法通过训练继续学习了，下面的算法就是用来解决这个问题的。

Adadelta

Adadelta[6]是Adagrad算法的一个扩展，这个算法没有计算过去的所有的梯度，而是使用一个大小为$w$的窗口来进行约束。

$$E[g^2]_t = \gamma E[g^2]_{t-1}+(1-\gamma)g_t^2$$

是移动平均值
我们将$\gamma$设置为和momentum参数相类似的数，大概为0.9，为了清楚表达，我们现在重写SGD更新

$$\bigtriangleup\theta_t=-\eta\cdot g_{t,i}$$ $$\theta_{t+1} = \bigtriangleup \theta_t$$ $$\bigtriangleup \theta_t = -\frac{\eta}{\sqrt{E[g^2]_t+\epsilon}}g_t$$

作者指出这样梯度就和参数的单位不一样了，梯度应该有和参数有相同的理论单位。为了实现这个目标，他们首先定义了另外一个只是衰减平均数，这次不是梯度的平方，而是参数的平方更新。

$$E[\bigtriangleup \theta^2]_t=\gamma E[\bigtriangleup \theta^2]_{t-1}+(1-\gamma)\bigtriangleup \theta_t^2$$ $$RMS[\bigtriangleup \theta]_t=\sqrt{E[g^2]_t+\epsilon}$$

因为$RMS[\bigtriangleup \theta]_t$是未知的，我们通过之前的参数更行平方根来进行预测，用$RMS[\bigtriangleup \theta]_{t—1}$来代替$\eta$最终的更新公式为

$$\bigtriangleup \theta_t=\frac{RMS[\bigtriangleup \theta]_{t-1}}{RMS[g]_t}$$ $$\theta_{t+1}=\theta_t+\bigtriangleup \theta_t$$

Adam

Adaptive Moment Estimation(Adam)[15] 对每个参数动态计算学习率的另外一种算法。除了像Adam那样存储指数削减的过去梯度平方的平均值$v_t$Adam 也保存了指数衰减的类似于momentum的参数$m_t$

$$m_t=\beta_1m_{t-1}+(1-\beta_1)g_t$$ $$v_t=\beta_2v_{t-1}+(1-\beta_2)g_t^2$$

$m_t$和$v_t$分别对应梯度的一阶中心距和二阶中心距的估计，因为他们都用0进行初始化，Adam的作者发现他们偏向0发展，特别是是在初始化的几步，特别是在衰减系数很小的时候($\beta_1 \beta_2$)
他们通过计算一阶和二阶偏差矫正来抵消这种效果。

$$\widehat{m}=\frac{m_t}{1-\beta_1^t}$$ $$\widehat{v}=\frac{v_t}{1-\beta_2^t}$$

最终

$$\theta_{t+1}=\theta_t - \frac{\eta}{\sqrt{\widehat{v_t}+\epsilon}}\widehat{m}_t$$

作者对$\beta_1 \beta_2 \epsilon$的默认值分别为0.9 0.999和10e-8

算法可视化

我们可以看到使用自适应参数的算法的性能比较好

如何选择合适的算法

所以我们改使用哪种算法呢，如果你的输入数据是系数的，那么选择一种自适应参数的算法可能回去的最好的效果，而且使用默认的参数也会得到很好的效果
总而言之，RMSprop,Adaelta和Adam是非常类似的算法，在类似的任务上结果也都不错，Kingma[15]等人表明Adam可能是最好的整体选择。

有趣的是，最近很多文章使用的简单的SGD和学习率变化表。正如之前所说的，SGD经常能够找到一个最小值，但是花费的时间可能会比其他算法长，而且可能会无法很好地收敛，所以，如果你希望快速训练深层次网络，你可以选择自动学习率的算法。

参考文献

1.Sutton, R. S. (1986). Two problems with backpropagation and other steepest-descent learning procedures for networks. Proc. 8th Annual Conf. Cognitive Science Society.
2.Qian, N. (1999). On the momentum term in gradient descent learning algorithms. Neural Networks : The Official Journal of the International Neural Network Society, 12(1), 145–151.00116-6)
3.Duchi, J., Hazan, E., & Singer, Y. (2011). Adaptive Subgradient Methods for Online Learning and Stochastic Optimization. Journal of Machine Learning Research, 12, 2121–2159
4.Dean, J., Corrado, G. S., Monga, R., Chen, K., Devin, M., Le, Q. V, … Ng, A. Y. (2012). Large Scale Distributed Deep Networks. NIPS 2012: Neural Information Processing Systems, 1–11.
5.Pennington, J., Socher, R., & Manning, C. D. (2014). Glove: Global Vectors for Word Representation. Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing, 1532–1543
6.Zeiler, M. D. (2012). ADADELTA: An Adaptive Learning Rate Method
7.Nesterov, Y. (1983). A method for unconstrained convex minimization problem with the rate of convergence o(1/k2). Doklady ANSSSR (translated as Soviet.Math.Docl.), vol. 269, pp. 543– 547.
8.Bengio, Y., Boulanger-Lewandowski, N., & Pascanu, R. (2012). Advances in Optimizing Recurrent Networks.
9.Training Recurrent neural Networks. PhD Thesis
10.Darken, C., Chang, J., & Moody, J. (1992). Learning rate schedules for faster stochastic gradient search. Neural Networks for Signal Processing II Proceedings of the 1992 IEEE Workshop, (September), 1–11. http://doi.org/10.1109/NNSP.1992.253713
11.H. Robinds and S. Monro, “A stochastic approximation method,” Annals of Mathematical Statistics, vol. 22, pp. 400–407, 1951
12.Mcmahan, H. B., & Streeter, M. (2014). Delay-Tolerant Algorithms for Asynchronous Distributed Online Learning. Advances in Neural Information Processing Systems (Proceedings of NIPS), 1–9.
13.Abadi, M., Agarwal, A., Barham, P., Brevdo, E., Chen, Z., Citro, C., … Zheng, X. (2015). TensorFlow : Large-Scale Machine Learning on Heterogeneous Distributed Systems
14.Zhang, S., Choromanska, A., & LeCun, Y. (2015). Deep learning with Elastic Averaging SGD. Neural Information Processing Systems Conference (NIPS 2015), 1–24.
15.Kingma, D. P., & Ba, J. L. (2015). Adam: a Method for Stochastic Optimization. International Conference on Learning Representations, 1–13
16.Bengio, Y., Louradour, J., Collobert, R., & Weston, J. (2009). Curriculum learning. Proceedings of the 26th Annual International Conference on Machine Learning, 41–48
17.Zaremba, W., & Sutskever, I. (2014). Learning to Execute, 1–25
18.Ioffe, S., & Szegedy, C. (2015). Batch Normalization : Accelerating Deep Network Training by Reducing Internal Covariate Shift. arXiv Preprint
19.Dauphin, Y., Pascanu, R., Gulcehre, C., Cho, K., Ganguli, S., & Bengio, Y. (2014). Identifying and attacking the saddle point problem in high-dimensional non-convex optimization. arXiv, 1–14. Retrieved from http://arxiv.org/abs/1406.2572