【深度学习】常见优化算法

转自：http://blog.csdn.net/shenxiaolu1984/article/details/52511202

本文介绍常见的一阶数值优化算法，这些方法在现代神经网络框架(tensorflow, caffe, torch)中已经是标准配置。

问题

设系统参数为 ω 。对于样本 i ，其代价函数为 Qi(ω) 。在n个样本组成的训练集上，其整体代价函数为： 

Q(ω)=∑i=1nQi(ω)

要求 ω 使得上式最小，由于没有闭式解，需要通过近似迭代逐步逼近。

基础一阶优化

GD

GD(Gradient Descent)以 η 为学习率，在每次迭代中用一阶泰勒展开近似： 

ωt+1=ωt−η∇Q(ω)

将求和与梯度互换。GD方法的增量来源于对所有样本同时求梯度之和： 

ωt+1=ωt−η∑i=1n∇Qi(ω)

设 ω 的维度为D，代价函数 Q 是个标量，减号后的梯度也是一个D维向量。

SGD

SGD(Stochastic Gradient Descent)在每次迭代中，顺次使用每个样本的梯度，更新参数：

for i=1 to n 

ωt+1=ωt−η∇Qi(ω)

一种折衷的方法是，把m个样本组成一个mini-batch，使用mini-batch的总梯度更新参数：

for i=1 to n/m 

ωt+1=ωt−η∑j=1m∇Qij(ω)

其中 Qij(ω) 为第i个minibatch中第j个样本的代价。

为书写简便，以下说明中不再出现样本序号i。 ∇Q(ω) 可以指一个样本、一个mini-batch或者全部样本的梯度只和。

更快的一阶优化

这些方法都以GD为基础，但收敛速度更快，换句话说 ϵt 更小。 
关于收敛速度的意义，请参看这篇博客。

ASGD

ASGD(Average Stochastic Gradient Descent)选择一个迭代的时间点(代数) t0 ，在这个时间点之前，和SGD一样： 

ω¯t=ωt

在这个时间点之后，使用 t0 到当前时刻 t 的平均值： 

ω¯t=1t−t0+1∑τ=t0tωτ

AdaGrad

AdaGrad1(Adaptive Gradient)方法对参数的每一维进行归一化，使用的分母是之前步骤中该维度的平方和： 

ωdt+1=ωdt−η1∑t−1τ=1[∇Q(ωt)d]2−−−−−−−−−−−−−−√∇Q(ωt)
相当于 为每一维参数设定了不同的学习率：压制常常变化的参数，突出稀缺的更新。能够更有效地利用少量有意义样本。

AdaDelta

AdaDelta2(Adaptive Delta)和AdaGrad一样为每一维参数设定不同学习率，但是不用再设定基础学习率 η 。

首先维护一个期望D，描述之前迭代中的参数变化情况，同样是个D维向量： 

Dt=γDt−1+(1−γ)Δω2t

另一个期望G，描述之前迭代中的梯度的平方： 

Gt=γGt−1+(1−γ)∇Q(ω)2t

使用D和G的比值作为权重，分别归一化每一维参数： 

ωdt+1=ωdt−DdtGdt+1∇Q(ω)

减号后的归一化参数决定了：单位梯度变化对应多少参数变化。

Adam

Adam3(Adaptive Moment Estimation)的思路和AdaGrad相似，都使用梯度平方根归一化学习率。

注意：为书写简便，后续的矩阵相乘相除都逐元素进行，更新也对参数每一维单独进行。

维护一个一阶momentum，等价于梯度： 

mt=α⋅mt−1+(1−α)⋅∇Q(ω)

另一个二阶momentum，等价于梯度平方： 

vt=β⋅vt−1+(1−β)⋅∇Q(ω)2

由于 m,v 都初始化为0，使用t次幂让其在头几次迭代中更大一些： 

m^t=mt1−αt,v^t=vt1−βt

使用梯度平方 v 归一化学习率，更新幅度为梯度 m : 

ωt+1=ωt−η1v^t−−√m^t

Rprop

RProp4(Resilient Propagation)比较本次梯度 ∇Q(ω)dt+1 和上次梯度 ∇Q(ω)dt 符号变化来为参数d的变化加权。

如果两次梯度符号相反，则抑制参数变化( η−<1 )： 

ωdt+1=ωdt−η−⋅∇Q(ω)

如果两次符号相同，则增强参数变化( η+>1 )： 

ωdt+1=ωdt−η+⋅∇Q(ω)

RMSprop

RMSprop5(Root Mean Square Propagation)类似于简化版的AdaDelta，但是是独立发展而来的。

维护期望G，描述之前迭代中的梯度的平方： 

Gt=γGt−1+(1−γ)∇Q(ω)2t

用G修正学习率： 

ωdt+1=ωdt−ηGdt+1∇Q(ω)

NAG

NAG6(Nesterov’s Accelerated Gradient)，发明者是毛国数学家Yurii Nesterov。

参数变化由 γ 控制： 

mt=γ⋅mt−1+η⋅∇Q(ω−γ⋅mt−1)

导数的计算点不再是当前参数 ω ，而是从当前参数根据前次变化前进一小步。

用 mt 更新参数： 

ωt+1=ωt−mt

总结

提速可以归纳为以下几个方面： 
- 使用momentum来保持前进方向(velocity)； 
- 为每一维参数设定不同的学习率：在梯度连续性强的方向上加速前进； 
- 用历史迭代的平均值归一化学习率：突出稀有的梯度；

辨：其他优化方法

共轭梯度法(Conjugate Gradient)也是一阶方法，针对特殊形式的代价函数： 

Q(ω)=12ωTAω−ωTb

常见的各种牛顿法, L-BFGS核心都是二阶优化方法，利用了代价函数的Hessian矩阵： 

xt+1=xt−η⋅H[Q(ω)]−1∇Q(ω)
换句话说，牛顿法用线性函数拟合代价函数的导数，而不是代价函数本身。

单纯形法，插值法等只计算代价函数值，不需要求导。

---

1. Duchi, J., Hazan, E., & Singer, Y. (2011). Adaptive Subgradient Methods for Online Learning and Stochastic Optimization. Journal of Machine Learning Research, 12, 2121–2159. ↩
2. Zeiler, M. D. (2012). ADADELTA: An Adaptive Learning Rate Method. Retrieved from http://arxiv.org/abs/1212.5701 ↩
3. Kingma, D. P., & Ba, J. L. (2015). Adam: a Method for Stochastic Optimization. International Conference on Learning Representations, 1–13. ↩
4. Martin Riedmiller und Heinrich Braun: Rprop - A Fast Adaptive Learning Algorithm. Proceedings of the International Symposium on Computer and Information Science VII, 1992 ↩
5. http://www.cs.toronto.edu/~tijmen/csc321/slides/lecture_slides_lec6.pdf ↩
6. https://blogs.princeton.edu/imabandit/2013/04/01/acceleratedgradientdescent/ ↩