各种优化算法的比较

机器学习和深度学习中使用到的优化算法的演化历程如下：

SGD –> Momentum –> Nesterov –> Adagrad –> Adadelta –> Adam –> Nadam

演化过程	原因
SGD –> Momentum	由于SGD在优化过程中容易产生震荡，为减小震荡，Momentum在梯度下降过程中引入了动量，使之具有惯性
Momentum –> Nesterov	对梯度项进行矫正，使梯度下降方向由积累的动量和假设走到下一步的梯度两部分决定的
Nesterov –> Adagrad	Adagrad中引入二阶动量，使之能够自适应调节学习率
Adagrad –> Adadelta	由于Adagrad 使用了之前所有梯度的平方，会导致训练到后面梯度为0，因此，在Adadelta中只用前面一段时间的下降梯度的配方
Adadelta –> Adam	在梯度更新中，使用了动量，并且能够自适应调节学习率
Adam –> Nadam	引入了Nesterov 动量项

各优化算法的公式和特点

一、BGD批梯度下降

公式：

优点:

1、cost fuction若为凸函数，能够保证收敛到全局最优值；若为非凸函数，能够收敛到局部最优值

缺点:

1、由于每轮迭代都需要在整个数据集上计算一次，所以批量梯度下降可能非常慢

2、训练数较多时，需要较大内存

二、SGD随机梯度下降

公式：

优点:

1、算法收敛速度快(在Batch Gradient Descent算法中, 每轮会计算很多相似样本的梯度, 这部分是冗余的)

2、有几率跳出一个比较差的局部最优而收敛到一个更好的局部最优甚至是全局最优

缺点:

1、容易收敛到局部最优，并且容易被困在鞍点

2、对于非凸问题，只能收敛到局部最优，并且没有任何摆脱局部最优的能力（一旦梯度为0就不会再有任何变化）。

三、Mini-batch Gradient Descent：

公式：

优点：

1、在每轮迭代中仅仅计算一个mini-batch的梯度，不仅计算效率高，而且收敛较为稳定。通常一小批数据含有的样本数量在 50 至 256 之间，但对于不同的用途也会有所变化。该方法是目前深度学训练中的主流方法

以上三种方法留下的挑战：
1、选择适当的学习率是一个难题。太小的学习率会导致较慢的收敛速度，而太大的学习率则会阻碍收敛，并会引起罚函数在最小值处震荡，甚至有可能导致结果发散；

2、我们可以设置一个关于学习率地列表，通过如退火的方法，在学习过程中调整学习率——按照一个预先定义的列表、或是当每次迭代中目标函数的变化小于一定阈值时来降低学习率。但这些列表或阈值，需要根据数据集地特性，被提前定义。

3、此外，我们对所有的参数都采用了相同的学习率。但如果我们的数据比较稀疏，同时特征有着不同的出现频率，那么我们不希望以相同的学习率来更新这些变量，我们希望对较少出现的特征有更大的学习率。

4、深层神经网络之所以比较难训练，并不是因为容易进入local minimum。相反，由于网络结构非常复杂，在绝大多数情况下即使是 local minimum 也可以得到非常好的结果。而之所以难训练是因为学习过程容易陷入到马鞍面中，即在坡面上，一部分点是上升的，一部分点是下降的。而这种情况比较容易出现在平坦区域，在这种区域中，所有方向的梯度值都几乎是 0。

四、Momentum

原理：

模拟运动惯性，即更新的时候在一定程度上保留之前更新的方向，同时利用当前batch的梯度微调最终的更新方向。动量项在梯度指向方向相同的方向逐渐增大，对梯度指向改变的方向逐渐减小。动量项 γ 往往被设置为 0.9

公式：

di和di-1是下次和本次的更新方向，相同就加强，可以看作是动量方向

优点：

帮助 SGD 在相关方向加速前进，并减少它的震荡。

五、NAG

原理：

但当一个小球从山谷上滚下的时候，盲目的沿着斜率方向前行，其效果并不令人满意。我们需要有一个更「聪明」的小球，它能够知道它再往哪里前行，并在知道斜率再度上升的时候减速。

Nesterov 加速梯度法（NAG）是一种能给予梯度项上述「预测」功能的方法。我们知道，我们使用动量项γvt-1 来「移动」参数项θ。通过计算θ-γvt-1，我们能够得到一个下次参数位置的近似值——也就是能告诉我们参数大致会变为多少。那么，通过基于未来参数的近似值而非当前的参数值计算相得应罚函数 J(θ-γvt-1) 并求偏导数，我们能让优化器高效地「前进」并收敛：

公式：

公式变换：

后面的加上去的项就是近似函数的二阶导信息，二阶导就是斜率的变化的快慢，怪不得可以加速收敛了。本次的梯度相对上次的梯度加大了，那么我有理由相信下次梯度也会变大。

公式推导过程：http://www.360doc.com/content/16/1010/08/36492363_597225745.shtml

实际代码效果证明：https://github.com/WarBean/zhihuzhuanlan/blob/master/Momentum_Nesterov.ipynb

六、Adagrad

公式：

具体写法：

特点：

适合用于稀疏梯度
前期梯度下降较快，后期梯度下降较慢
具有自适应学习率
训练后期，由于梯度累计较大，会使训练提前结束

七、Adadelta

公式：

另种写法：

特点：

在adagrad基础上，减少提前结束训练的风险

后期容易在小范围内产生震荡

七、RMSprop（adadelta的特例）

公式：

特点：

Adagrad会累加之前所有的梯度平方，而RMSprop仅仅是计算对应的平均值，因此可缓解Adagrad算法学习率下降较快的问题。

八、Adam

公式：

原理：

它利用误差函数的一阶矩估计和二阶矩估计来约束全局学习率。

特点：

Adam梯度经过偏置校正后，每一次迭代学习率都有一个固定范围，使得参数比较平稳
结合了Adagrad善于处理稀疏梯度和RMSprop善于处理非平稳目标的优点
为不同的参数计算不同的自适应学习率
也适用于大多非凸优化问题——适用于大数据集和高维空间

分类

梯度修正	优化算法
没进入动量，且不具有自适应学习率	BGD、SGD
引入动量	Momentum、Nesterov
自适应学习率	Adagrad、Adadelta、RMSprop
引入动量且自适应学习率	Adam、Adamx、Nadam