优化算法梯度下降、牛顿法、SGD、AdaGrad、Adam是不是 ...
本篇近八千字真的有点长，把常见的优化算法都纳入进来，梳理了脉络，希望感兴趣的朋友关注、点赞加收藏，需要用到的时候来看看。本文中的示意图和动态图有相应代码，如果感兴趣可以关注同名公V，私戳我，有完整代码文档。
什么是优化算法？其实换一个词应该更清楚些，叫“求解算法”。在机器学习里常常会遇到用优化方法的地方，比如线性回归、逻辑回归、GBDT、XGBoost、神经网络等等。
它有什么作用呢？在我的上一篇讲线性回归原理的时候说到，机器学习其实就是从大量数据里提取一个抽象数学模型来帮助我们预测新的数据。这个数学模型具体形式就是一个函数，对于简单线性回归来说是下面这样的：
其他的模型又有其他的函数形式，那么无论长什么样，我们再进一步抽象成下面这种函数表示：
其中θ是函数参数，因为y和x就是数据点，是已知的，我们需要求出参数θ，这样我们就确定了函数的具体形式。其实我们要求的这个函数是以参数θ为变量的。那怎么求出参数θ呢？一种方式是假设已经知道了所有参数，得到了函数：
这里y'是预测值，θ‘是假设找到的θ预估值。我们让实际值y与预测值y'作差，不就是表示预测值偏离实际值的误差么？把每个实际值y与预测值y'之间的误差加起来，让总误差最小：
在求这个总误差最小的过程不就可以得到θ的理想参数θ’吗？所以现实问题就转化为数学问题，求解使得（y'-y)最小的参数θ‘。在上一篇讲到这个求解方法有两种，一种是矩阵直接求解，一种是迭代法，前一种因为需要矩阵可逆而且计算量大，所以普遍都采用后一种迭代法。
迭代法的典型方法是什么呢？就是梯度下降法。就是对参数θ，先随机猜一个值带入函数中计算所有数据点的总误差，看误差是否低于设定的能接受的误差阈值，如果高，那就再带入一个新的参数θ1计算，重复前面的步骤，直到误差符合预期。那怎么确定这个新的参数θ1呢？这就是问题的关键。怎么从前一个参数θ转到新的参数θ。
以下山来举例：
如果从p2点往下走可能走不到山底而是走到一个洼地，如果从p1点往下走可能就走到山底，一个聪明的方法不是盲目的往下走，而是每次都按照坡度下降最大的方向去走，这样走到山底的把握不就更大吗？（当然从这张图你也可以看出也不一定，跟初始值也就是开始走的地点在哪里有关，实际情况中人不可能一直反复的尝试哪里是最低，但是计算机的好处就是可以穷极遍历，所以我们模型求解就是利用计算机遍历的特性）。
那对一个函数或曲线来说坡度下降最大的方向是什么呢？就是函数值的导数，我们把它称为梯度。这样我们就找到了参数θ转到新的参数θ之间的关系可以通过梯度建立。接下来就是有关优化求解的方法了。
围绕着怎么一步一步从初始θ找到目标θ’，就产生了梯度下降（BGD)、随机梯度下降(SGD)、小批量梯度下降（MBGD)、牛顿法、拟牛顿法（lbfgs）、共轭梯度下降法、坐标轴下降法、动量梯度下降法、NAG、AdaGrad、AdaDelta、RMSProp、Adam、NAdam等等各种优化算法。目前用的最多的是SGD、lbfgs和Adam。
这些算法基础其实都是梯度下降，但是出于实际工程实践的考虑，数据量很大、迭代次数很多就会造成求解时间很长（一个模型就算求解的方法你都知道，但是你算一个星期也算不出来也等于没用），所以原始梯度下降算法（BGD)之后的算法都是以提高计算效率而出现。知道这个目的，就明白了为什么叫优化算法了，既要求解，又要能优化到最快时间、最小成本计算。
1.梯度下降法
简而言之，就是每一个新θ的值，都是在旧θ值的基础上再减去一个梯度得到（当然也有损失函数是求最大值的，这就是梯度上升法，跟下降法相反，那就加上一个梯度），对于线性回归，梯度下降迭代公式是下面这样的：
那对于更一般的损失函数迭代公式我们用下面的形式来表示：
这里θ就是我们要求解的参数θ，η就是学习率，θL(θ)是损失函数的导数，也就是梯度。接下来的优化算法迭代公式基本都是这个形式，不同的就是会在学习率η（步长）和迭代方向（梯度）做文章。找到了迭代公式，下面就是如何迭代，每种优化算法迭代的方式也都是一样的：
第一步：设置初始θ（随机设置），设置步长（也叫做学习率，通常在0~1之间）α，设置迭代终止的误差接受度（或者是精度e阈值）也就是误差最小到多少就可以停止计算了；
第二次迭代：将参数θ_new1带入到损失函数在θ_new1这一点的损失函数的导数值（即梯度），然后将参数θ_new1带入到上面的迭代公式求计算新的梯度和θ_new，同时计算损失函数（也是误差和）的大小，比较损失函数与精度e阈值的大小，如果大于阈值，进行第三次迭代，具体的计算步骤如下：
1.计算损失函数关于当前参数θ的梯度：
这里需要解释为什么带上角标t，它表示该值有时间序列的属性，这里先不解释为什么，后面会在对应优化方法在解释。
2.根据前面的梯度计算一阶导数和二阶导数：
这里的一阶导数和二阶导数是关于原始导数的函数，不同的方法这一步可能不同，有的没用到二阶导数。
3.计算当前时刻的下降梯度：
“|”表示或者的意思。
4.根据下降梯度进行更新θ：
第n次迭代：重复第二次的操作；
第三步：当损失函数（即误差和）的值小于设定的误差阈值，满足条件，退出循环，返回最新的参数θnew，此时的θnew就是我们要找的理想的模型参数。
这就是各种优化方法迭代的整个过程。请记住这整个步骤，下面的每种优化算法你都可以代进来迭代。
下面以y=0.1x1^2 +2x2^2二元二次方程为例怎么用梯度迭代找到最小值，并且可视化。代码：
def f_2d(x1, x2):#定义函数
'''original function to minimize'''
return 0.1 * x1 ** 2 + 2 * x2 ** 2
def f_grad(x1, x2):#计算梯度
'''the gradient dfdx1 and dfdx2'''
dfdx1 = 0.2 * x1
dfdx2 = 4 * x2
return dfdx1, dfdx2
def sgd(x1, x2, s1, s2, lr):#计算迭代公式，这里是原始梯度下降法迭代公式
dfdx1, dfdx2 = f_grad(x1, x2)
return (x1 - lr * dfdx1, x2 - lr * dfdx2, 0, 0, lr)2.随机梯度下降(SGD)
因为上面梯度下降法里的损失函数是在整个数据集上进行计算得到的均值，所以每更新一次模型参数，就要对整个数据集进行一个计算，这就是批量梯度下降法(BGD)，可想而知这样非常的慢，并且当数据集变得非常大的时候，如此多的数据没法都加载到内存中；而且也可能花了很长时间只找到到了局部最小值，所以就产生随机梯度下降法(SGD)：
采用每次更新都只用一对样本，即上面公式中的一对样本( xi , yi ) ，这样虽然不如直接做BGD在迭代路径上更稳定，但是会很快找到最优解，而且还有好处是可以从局部最小值中跳出来，只要新选取的一个样本可以提供一个向外的梯度。
但是随机梯度下降也有缺点，每次更新可能并不会按照正确的方向进行，参数更新具有高方差，从而导致损失函数剧烈波动。不过，如果目标函数有盆地区域，SGD会使优化的方向从当前的局部极小值点跳到另一个更好的局部极小值点，这样对于非凸函数，可能最终收敛于一个较好的局部极值点，甚至全局极值点。
上图是SGD迭代过程的可视化，跳跃性比较大。
上图就是随机梯度下降法更新过程中loss值的变化，可以发现loss值的变化非常大，整个模型比较不稳定。
3.小批量随机梯度下降（MBGD)
所以就出现了折中的小批量梯度下降算法（MBGD)，在SGD的基础上，我们还可以一次采样一个小批量的样本，然后利用该小批量来计算梯度。这样做比每次仅采样一个样本，能够使得计算的梯度值更加符合期望的梯度值，排除减少异常样本的干扰：
所有梯度下降法都面临两个挑战：
1. 很难选择一个合适学习率，需要我们大量的尝试。太小的学习率会导致模型收敛变得缓慢，导致训练时间变长；太大的学习率会阻碍模型的收敛，使损失函数在最优值附近来回波动甚至是发散。
2、对于所有的参数，均使用相同的学习率。如果有的参数的梯度很大，有的很小，使用相同的学习率显然就不是很合适。
3、在非凸函数的优化过程中，我们往往希望模型能够跳过那些局部极值点，去找一个更好的极值。在实际训练过程中，鞍点也是非常难以解决的问题。例如在某个点处，一个维度的梯度方向是往上的，一个维度的梯度是往下的，那梯度下降法在就很难跳出这个点，因为这个点所有维度的梯度是接近0的。
所以就衍生出了后面几种优化方法。
4.动量梯度下降（Momentum Gradient Descent）
虽然随机梯度下降(SGD)、小批量随机梯度下降（MBGD)好像解决了计算速度问题，但是还是不够快，而且迭代误差波动非常大，它们都只利用了每个数据点当前梯度信息，但是我们有一个常识，就是我们再下山往下走时，身体会有个惯性，你上一步走的速度会影响你下一步的速度，你走的快惯性就会带着你下一步会快一点。所以梯度下降有没有惯性呢？有，那就是历史梯度会影响当前梯度。那怎么理解呢？
既然意识到当前梯度会受历史梯度的影响，说明每个梯度之间存在时间序列的关系，所以令：
再令n= 1/(1-γ) 项的指数加权移动平均，时间越近的权重越高。同样，当γ=0.95时，我们可以认为这个加权平均使用的该时间序列最近20项的梯度、学习率的观测值。这样做的一个直观表现就是，如果目标函数最近n个时间步的梯度方向比较一致，那么t时刻的梯度加上t-1时刻的速度会t时刻的速度变量较大，则模型参数的改变量就大；若这几个时间步内梯度方向变化较大，会造成其加权平均值较小，则模型参数的改变量就相对小。上面这个式子换一种说法就是加权移动平均。
再来看这个式子跟泰勒展开公式是不是很像？我们把当前时间点的梯度只取前两项，用它自身和上一个时间点点的梯度表示，这样就就利用到历史信息，体现了惯性的作用，把这种历史梯度叫做动量：
这里当前m_t其实就是当前梯度g_t，一阶动量是各个时刻梯度方向的指加权移动平均值，约等于最近 1-(1-γ)个时刻的梯度向量和的平均值。也就是说，t时刻的下降方向，不仅由当前点的梯度方向决定，而且由此前累积的下降方向决定。一般来说γ 的经验值为0.9（就是当前梯度的权重小而上一梯度权重大），这就意味着下降方向主要是此前累积的下降方向，并略微偏向当前时刻的下降方向。想象高速公路上汽车转弯，在高速向前的同时略微偏向，急转弯可是要出事的。
有了新的梯度迭代的量，那我们新的迭代公式就是：
迭代公式代码（这里因为举例的目标函数有两个待优化参数x，都要求解）：
def inertia(x1, x2, v1, v2, lr):
dfdx1, dfdx2 = f_grad(x1, x2)
v1 = gamma * v1 + (1 - gamma) * dfdx1
v2 = gamma * v2 + (1 - gamma) * dfdx2
x1 = x1 - lr * v1
x2 = x2 - lr * v2
return (x1, x2, v1, v2, lr)
上面这张图就是动量梯度下降，你看它跟SGD走的方向和终点差不多，但是比SGD少饶了很多弯路，它也有避免陷入局部极小值的优点。
5.Nesterov加速梯度下降（Nestrov Accelerated Gradient（NAG））
上面的动量梯度下降考虑了历史梯度信息，顺着这个思路，我们也可以想想能不能考虑考虑未来的信息呢？这个怎么理解？也可以根据常识理解。还是假如你在下山，你踏出下一步（离目标移动最快的步子）的时候，考虑一下这一步和下下一步一起怎么移动最快，我们要知道下下一步的梯度会走到哪，那我们这一步就直接跨过去，NAG算法就是这样聪明的算法。
所以现在把上面动量梯度下降公式改进一下，把（1-γ）改成学习率η，然后在梯度g_t = θL(θ)这个公式里关于θ的函数加上γm_{t-1}，就是下面这个公式：
这个迭代公式实际怎么计算呢？关键就在学习率η这个后面的梯度g_t，它经过变形得到：
这个公式怎么证明大家可以看这篇文档：https://baijiahao.baidu.com/s?id=1613121229156499765&wfr=spider&for=pc
6.Adagrad梯度下降
动量梯度下降和Nesterov加速梯度下降都是对梯度的方向进行了改进，但是梯度的步长同样会影响到到达最小值的时间，所以我们也可以考虑这个因素，那就是学习率因素。前面讲了在梯度下降法中，因为对所有的参数均使用相同的学习率，而当有的参数的梯度很大，有的很小时，显然不合适。
另外，对于不同的样本，如果有的样本出现的较为频繁，导致其对应的一些参数更新较为频繁，而有的样本出现的频率很低，导致一些参数更新频率很低时，再采用相同的学习率有时候也不太合适。我们更加希望那些出现更新频率比较低的参数能够有更大的更新幅度。
Adagrad就是这样做的：它使学习率适应参数θ，对与频繁发生的特征相关的参数θ执行较小的更新（即低学习率），对与不频繁的特征相关的参数θ执行较大的更新（即高学习率）。也就是根据每个参数以前的梯度情况，对不同参数使用不同的学习率，同时动态调整参数学习率。因此，它非常适合处理稀疏数据。这也是为什么它叫自适应学习率优化算法。
那具体怎么实现计算的呢？这次它不是变动梯度，而是改变学习率的η的形式：
那这个式子中的v_t怎么来的呢？v_t就是我们一开始讲梯度下降法提到的迭代步骤里的二阶导数，它是关于梯度的函数，表示的是历史梯度平方值总和：
上面这两个公式怎么理解呢？其实就是把原来的学习率变成原（全局）学习率除以历史梯度平方和的平方根，使得每个参数的学习率不同。为了防止v_t可能等于0，所以在平方根下加了误差项来平滑一下，这就是Adagrad的迭代公式。
迭代公式代码：
def adagrad(x1, x2, s1, s2, lr):
g1, g2 = f_grad(x1, x2)
eps = 1e-6
s1 += g1 ** 2
s2 += g2 ** 2
x1 -= lr / math.sqrt(s1 + eps) * g1
x2 -= lr / math.sqrt(s2 + eps) * g2
可以看到自适应学习率梯度下降会随时调整下降步长，从而使得下降过程很顺畅而不会走很多弯路。
7.RMSProp(Root Mean Square Propagation)
但是Adagrad也有缺陷，因为迭代v_t公式是单调递增的，会使得学习率单调递减至0，可能会使得训练过程提前结束，后面的梯度可能就学不到了。而且因为它把历史所有梯度平方求和使得历史梯度地位相同，但实际上梯度影响作用是衰减的。所以另一种思路产生：不累积全部历史梯度，而只关注过去一段时间窗口的下降梯度。它跟前面的一阶动量法很像。
迭代公式代码：
def rmsprop(x1, x2, s1, s2, lr):
eps = 1e-6
g1, g2 = f_grad(x1, x2)
s1 = gamma * s1 + (1 - gamma) * g1 ** 2
s2 = gamma * s2 + (1 - gamma) * g2 ** 2
x1 -= lr / math.sqrt(s1 + eps) * g1
x2 -= lr / math.sqrt(s2 + eps) * g2
return x1, x2, s1, s2, lr8.Adam(Adaptive Moment Estimation)
有了上面思路的启发，聪明的大佬就想到为啥不把动量和自适应学习率一起结合使用呢？就产生了下面的这种方法：
在tensorflow中常见的两个超参数γ1，γ2 就都在这里了，前者控制一阶动量，后者控制二阶动量。在实际使用过程中，参数的经验值是γ1=0.9,γ2=0.999。这就是前面各种梯度下降法的集大成者，在近几年的深度游学习中的实践效果很好。
它的完整更新公式是：
迭代公式代码：
def Deltax(m, n, g, t):
eps = 1.0E-6
m = beta1 * m + (1 - beta1) * g
n = beta2 * n + (1 - beta2) * g*g
m_hat = m / (1 - beta1**t)
n_hat = n / (1 - beta2**t)
dx = lr * m_hat / (math.sqrt(n_hat) + eps)
return m, n, dx
def adam_2d(x1, x2, m1, n1, m2, n2, lr, t):
'''m1, m2: E(g1), E(g2)
n1, n2: E(g1^2), E(g2^2) where E() is expectation
lr: learning rate
t: time step'''
eps = 1e-6
g1, g2 = f_grad(x1, x2)
m1, n1, dx1 = Deltax(m1, n1, g1, t)
m2, n2, dx2 = Deltax(m2, n2, g2, t)
x1 -= dx1
x2 -= dx2
return x1, x2, m1, n1, m2, n2, lr
到这里基本上梯度下降优化算法的改进过程基本讲完了，下面看一下几种算法在找最小值的曲面上鞍点和等高线上的性能：
9.如何选择？
在深度学习力，如果数据是稀疏的，就用自适应方法，即 Adagrad, Adadelta,RMSprop, Adam。如果不知道哪种好，Adam是最好的选择。很多文里都会用 SGD，没有momentum动量等。SGD虽然能达到极小值，但是比其它算法用的时间长，而且可能会被困在鞍点。如果需要更快的收敛，或者是训练更深更复杂的神经网络，需要用一种自适应的算法。
在介绍完上面梯度迭代方法之后，下面再介绍另外三种不同的迭代方法，但是不再详细解释。因为本文篇幅已经太长了。后面有机会会对每个优化算法单独开篇一一进行解释。
10.牛顿法
上面用的都是迭代逼近参数θ的方法，我们也知道还有一种解法就是矩阵直接求导的方式，那么我们是不是也可以把这两中结合一下？我们目标是要求函数的最小值，假设我们现在已经在最小值附近，对其求导，令其等于0，就可以得到最小值点。那根据泰勒展开式我们还知道函数上某个点的值可以近似于它的本身与一阶导数和二阶导数之和，这样可以把复杂的函数简化为下面这个式子：将函数 f(x) 在x0 处展开成泰勒级数:
取其前两项一阶导数和二阶导数作为 f(x) 的近似：
我们要对f(x0)求导，即让f‘(x0)=0，则可用f’(x0)+ f'‘(x0)(x-x0) = 0 的解来近似f’(x0)=0的解，其解为
由于牛顿法是基于当前位置的切线来确定下一次的位置，所以牛顿法又被很形象地称为是"切线法"。牛顿法的搜索路径（二维情况）如下图所示：
牛顿法和梯度下降法的效率对比：
从本质上去看，牛顿法是二阶收敛，梯度下降是一阶收敛，所以牛顿法就更快。如果更通俗地说的话，比如你想找一条最短的路径走到一个盆地的最底部，梯度下降法每次只从你当前所处位置选一个坡度最大的方向走一步，牛顿法在选择方向时，不仅会考虑坡度是否够大，还会考虑你走了一步之后，坡度是否会变得更大。所以，可以说牛顿法比梯度下降法看得更远一点，能更快地走到最底部。（牛顿法目光更加长远，所以少走弯路；相对而言，梯度下降法只考虑了局部的最优，没有全局思想。）
根据wiki上的解释，从几何上说，牛顿法就是用一个二次曲面去拟合你当前所处位置的局部曲面，而梯度下降法是用一个平面去拟合当前的局部曲面，通常情况下，二次曲面的拟合会比平面更好，所以牛顿法选择的下降路径会更符合真实的最优下降路径。
上图中红色的牛顿法的迭代路径，绿色的是梯度下降法的迭代路径。
下面是牛顿法的迭代代码：
def Jacobian(x):
return array(, 0.4*x, 1.2*x])
def Hessian(x):
return array([,,])
def Newton(x0):
i = 0
iMax = 10
x = x0
Delta = 1
alpha = 1
while i10**(-5):
p = -dot(linalg.inv(Hessian(x)),Jacobian(x))
xOld = x
x = x + alpha*p
Delta = sum((x-xOld)**2)
i += 1
print x
x0 = array([-2,2,-2])
Newton(x0)牛顿法主要存在的问题是：
1.Hesse 矩阵不可逆时无法计算。
2.矩阵的逆计算复杂为 n 的立方，当问题规模比较大时，计算量很大，解决的办法是采用拟牛顿法如BFGS, L-BFGS, DFP, Broyden’s Algorithm 进行近似。在sklearn中经常会用到的L-BFGS就是改良的牛顿法算法。
3.如果初始值离局部极小值太远，Taylor 展开并不能对原函数进行良好的近似。
如果对比sklearn和tensorflow，你会发现后者没有采用牛顿法，就是因为在超大数据量下矩阵计算非常庞大，也没法并行化，但是对适用于中小规模数据的sklearn来说神经网络层数不多，可以比较快速的求解。
11.共轭梯度下降法
共轭梯度法是介于最速下降法与牛顿法之间的一个方法，它仅需利用一阶导数信息，但克服了最速下降法收敛慢的缺点，又避免了牛顿法需要存储和计算Hesse矩阵并求逆的缺点，共轭梯度法不仅是解决大型线性方程组最有用的方法之一，也是解大型非线性最优化最有效的算法之一。在各种优化算法中，共轭梯度法是非常重要的一种。其优点是所需存储量小，具有收敛性，稳定性高，而且不需要任何外来参数。
12.坐标轴下降法
坐标下降法（coordinate descent）是一种非梯度优化算法。算法在每次迭代中，固定其它维度的坐标方向，在当前点处沿一个坐标方向进行一维搜索以求得一个函数的局部极小值，一个周期的一维搜索迭代过程相当于一个梯度下降的迭代。在整个过程中循环使用不同的坐标方向。对于不可拆分的函数而言，算法可能无法在较小的迭代步数中求得最优解。坐标轴下降法主要用在线性回归中的lasso回归算法中，因为它采用的是L1正则。
好了，以上几乎就是在机器学习或者深度学习里最常遇到的优化求解方法了。本文没有详细解释每个方法的公式推导过程，一篇文章也解释不了，还有很多没有介绍的基本都是基于上面这些衍生出来的。本文可能有理解或者表述错误的地方，欢迎指正，本篇只是一个学习整理文档，只是想把机器学习常用的优化算法收纳进来，不具有严谨性，借用了下面参考文档的很多观点和原话，供大家参考。
最后欢迎大家关注我，我是拾陆，关注同名"二八Data"，更多干货持续为你奉献。
参考文档：
https://zhuanlan.zhihu.com/p/32230623
https://ruder.io/optimizing-gradient-descent/
https://baijiahao.baidu.com/s?id=1613121229156499765&wfr=spider&for=pc
https://zhuanlan.zhihu.com/p/147275344
https://blog.csdn.net/sunflower_sara/article/details/81321886
牛顿法：https://blog.csdn.net/weixin_39445556/article/details/84502260/
页:
[1]