开篇废话

优化算法几乎是绝大部分机器学习模型训练的必要算法，最近参加一些大厂的笔试，发现优化算法是基础考点，本文着重介绍几种常用的优化算法，同时整理一些面试、笔试题以供大家参考，以后相关的博客都会以基础概念和面试试题两部分呈现。当然这些博客（包括已发表的）也会持续更新

正式内容

优化算法基本可以分为两类算法：一阶算法和二阶算法，一阶算法主要以计算梯度为主，比如我们熟知的梯度下降，也叫最速下降法；二阶算法主要以计算海塞矩阵为主。

1、梯度下降

梯度下降法是最早最简单，也是最为常用的最优化方法。梯度下降法实现简单，当目标函数是凸函数时，梯度下降法的解是全局解。一般情况下，其解不保证是全局最优解，梯度下降法的速度也未必是最快的。梯度下降法的优化思想是用当前位置负梯度方向作为搜索方向，因为该方向为当前位置的最快下降方向，所以也被称为是”最速下降法“。最速下降法越接近目标值，步长越小，前进越慢。梯度下降法的搜索迭代示意图如下图所示：

梯度下降法的缺点：

（1）靠近极小值时收敛速度减慢，如下图所示；

（2）直线搜索时可能会产生一些问题；

（3）可能会“之字形”地下降。

从上图可以看出，梯度下降法在接近最优解的区域收敛速度明显变慢，利用梯度下降法求解需要很多次的迭代。

在机器学习中，基于基本的梯度下降法发展了两种梯度下降方法，分别为随机梯度下降法和批量梯度下降法。

比如对一个线性回归（Linear Logistics）模型，假设下面的h(x)是要拟合的函数，J(theta)为损失函数，theta是参数，要迭代求解的值，theta求解出来了那最终要拟合的函数h(theta)就出来了。其中m是训练集的样本个数，n是特征的个数。
比如对一个线性回归（Linear Logistics）模型，假设下面的h(x)是要拟合的函数，J(theta)为损失函数，theta是参数，要迭代求解的值，theta求解出来了那最终要拟合的函数h(theta)就出来了。其中m是训练集的样本个数，n是特征的个数。

1）批量梯度下降法（Batch Gradient Descent，BGD）

（1）将J(theta)对theta求偏导，得到每个theta对应的的梯度：

（2）由于是要最小化风险函数，所以按每个参数theta的梯度负方向，来更新每个theta：

对于批量梯度下降法，样本个数m，x为n维向量，一次迭代需要把m个样本全部带入计算，迭代一次计算量为m*n^2。

2）随机梯度下降（Stochastic Gradient Descent，SGD）

（1）上面的风险函数可以写成如下这种形式，损失函数对应的是训练集中每个样本的粒度，而上面批量梯度下降对应的是所有的训练样本：

（2）每个样本的损失函数，对theta求偏导得到对应梯度，来更新theta：

（3）随机梯度下降是通过每个样本来迭代更新一次，如果样本量很大的情况（例如几十万），那么可能只用其中几万条或者几千条的样本，就已经将theta迭代到最优解了，对比上面的批量梯度下降，迭代一次需要用到十几万训练样本，一次迭代不可能最优，如果迭代10次的话就需要遍历训练样本10次。但是，SGD伴随的一个问题是噪音较BGD要多，使得SGD并不是每次迭代都向着整体最优化方向。

随机梯度下降每次迭代只使用一个样本，迭代一次计算量为n^2，当样本个数m很大的时候，随机梯度下降迭代一次的速度要远高于批量梯度下降方法。两者的关系可以这样理解：随机梯度下降方法以损失很小的一部分精确度和增加一定数量的迭代次数为代价，换取了总体的优化效率的提升。增加的迭代次数远远小于样本的数量。

对批量梯度下降法和随机梯度下降法的总结：
批量梯度下降---最小化所有训练样本的损失函数，使得最终求解的是全局的最优解，即求解的参数是使得风险函数最小，但是对于大规模样本问题效率低下。
随机梯度下降---最小化每条样本的损失函数，虽然不是每次迭代得到的损失函数都向着全局最优方向， 但是大的整体的方向是向全局最优解的，最终的结果往往是在全局最优解附近，适用于大规模训练样本情况。

PS: 讲完了梯度下降，下面让我们聊一聊深度学习中的一些优化算法，它们很大程度都在改进梯度下降的算法

SGD缺点：（正因为有这些缺点才让这么多大神发展出了后续的各种算法）

此处的SGD指mini-batch gradient descent（小批量梯度下降），可以解决高方差的参数更新和不稳定收敛的问题。单个样本的SGD会造成参数比较剧烈的波动，关于batch gradient descent, stochastic gradient descent, 以及 mini-batch gradient descent的具体区别就不细说了。现在的SGD一般都指mini-batch gradient descent。

SGD就是每一次迭代计算mini-batch的梯度，然后对参数进行更新，是最常见的优化方法了。

这里的图片中的符号作为参考，方法众多，容易产生公式的混淆，f=损失函数

SGD完全依赖于当前batch的梯度，所以η可理解为允许当前batch的梯度多大程度影响参数更新

缺点

选择合适的learning rate比较困难
对所有的参数更新使用同样的learning rate。对于稀疏数据或者特征，有时我们可能想更新快一些对于不经常出现的特征，对于常出现的特征更新慢一些，这时候SGD就不太能满足要求了
SGD容易收敛到局部最优，在某些情况下可能被困在鞍点【但是在合适的初始化和学习率设置下，鞍点的影响其实没这么大】

2、学习率改进的一些优化算法

1）Adagrad

Adagrad其实是对学习率进行了一个约束。

也有人使用之前的梯度平方和做约束，思想是大同小异

特点：
前期G（G是由g累加起来的，这里是指第一种定义）
较小的时候， regularizer较大，能够放大梯度
后期G
较大的时候，regularizer较小，能够约束梯度适合处理稀疏梯度

缺点：
由公式可以看出，仍依赖于人工设置一个全局学习率η，设置过大的话，会使regularizer过于敏感，对梯度的调节太大中后期，分母上梯度平方的累加将会越来越大，使gradient→0，使得训练提前结束

3）RMSprop

3、关于梯度本身的一些改进

1）Momentum

SGD方法的一个缺点是其更新方向完全依赖于当前batch计算出的梯度，因而十分不稳定。Momentum算法借用了物理中的动量概念，它模拟的是物体运动时的惯性，即更新的时候在一定程度上保留之前更新的方向，同时利用当前batch的梯度微调最终的更新方向。这样一来，可以在一定程度上增加稳定性，从而学习地更快，并且还有一定摆脱局部最优的能力：

Momentum算法会观察历史梯度v_(t-1)，若当前梯度的方向与历史梯度一致（表明当前样本不太可能为异常点），则会增强这个方向的梯度，若当前梯度与历史梯方向不一致，则梯度会衰减。一种形象的解释是：我们把一个球推下山，球在下坡时积聚动量，在途中变得越来越快，γ可视为空气阻力，若球的方向发生变化，则动量会衰减。Momentum可以使网络能更优和更稳定的收敛；减少振荡过程。

给大家一个直观的感受，前面梯度会影响后面梯度的方向和大小，这边的图就是提了前面一个梯度的影响，其实影响这一时刻的梯度是前面所有梯度的指数平均梯度。

红色代表是我们的momentum，黑色代表的是我们的sgd；

（未完待续……）

20170806000414235.gif

20170806001149509.gif