梯度下降

作为机器学习最常用的优化方法，梯度下降占有重要地位。以前对梯度下降算法的理解只是按照梯度方向可以最快找到最优解，很片面。

这里从头归纳总结下梯度下降的相关知识，其余的优化算法与梯度下降的比较有时间再总结，在本文中不涉及。

定义

假定现在有一简单需求：

给定学习时间与期末分数的关系的简单数据集，求出学习时间与分数的模型（这里的数据不严谨，只是为了说明这个问题）：

学习时间	期末分数
1	3
2	5
3	7
4	？
4.5	？

我们将模型假设为线性模型（ $\hat{y} = wx+b$ ），（因为线性模型已经可以拟合上述的简单数据）

这里我们使用平均平方误差（MSE）作为损失函数

$cost(w,b)=\frac{1}{N}\sum\limits_{n=1}^N(\hat{y_n}-y)^2$

求解w和b，求出损失最小的参数,即求出： $(w,b)^*=arg\ min(cost(w,b))$

最简单直观的方法可以在参数空间中随机w和b，找出最小。但这种方法在参数量大时显然不可用（如果一个维度的参数为100，2个维度就需要 $100^2$ ,10个需要 $100^{10}$ ）。于是引入优化算法，在参数空间中按照某种规律去寻找最优参数，这里引出梯度下降方法：

简单起见，我们使用单变量的函数进行举例，如上图所示：需要求出 $w* = arg\ min(cost(w))$ 。一般而言，可以使用“导数”来求解某个函数的极值

在单变量的实值函数中，梯度可简单理解为只是导数，或者说对于一个线性函数而言，梯度就是曲线在某点的斜率。

但对于多维变量的函数，梯度概念就不那么容易理解了，它就要涉及到标量场概念。

在向量微积分中，标量场的梯度，其实是一个向量场（vector field）。

假设一个标量函数 $f$ 的梯度记为： $\nabla f$ , 这里表示向量微分算子。那么，在一个三维直角坐标系，该函数的梯度就可以表示为

$\nabla f = (\frac{\partial f}{\partial x},\frac{\partial f}{\partial y},\frac{\partial f}{\partial z})$

为求得这个梯度值，难免要用到“偏导”的概念。说到“偏导”，这里顺便“轻拍”一下国内的翻译。“偏导”的英文本意是“partial derivatives（局部导数）”，书本上常将其翻译为“偏导”，可能会把读者的思路引导“偏”了。

那什么是“局部导数”呢？对于多维变量函数而言，当求某个变量的导数时，就是把其它变量视为常量，然后整个函数求其导数（相比于全部变量，这里只求一个变量，即为“局部”）。之后，这个过程对每个变量都“临幸”一遍，放在向量场中，就得到了这个函数的梯度了。举例来说，对于3变量函数，它的梯度可以这样求得：

于是，函数f的梯度可表示为：

针对某个特定点，如点A（1, 2, 3），带入对应的值即可得到该点的梯度：

对于函数的某个特定点，它的梯度就表示从该点出发，函数值增长最为迅猛的方向（direction of greatest increase of a function）。

对于图9-4所示的案例，梯度可理解为，站在向量点A（1, 2, 3），如果想让函数f的值增长得最快，那么它的下一个前进的方向，就是朝着向量点B（8,7,27）方向进发。

一方面，的显式解，并不容易求得，当输入变量很多时或者函数很复杂时，就更不容易求解微分方程。

另一方面，求解微分方程并不是计算机所长。计算机所擅长的是，凭借强大的计算能力，通过插值等方法（如牛顿下山法、弦截法等），海量尝试，一步一步的去把函数的极值点“试”出来。

用python来实现一下：

梯度下降Python实现

步骤：

定义模型
初始化模型的超参数
定义代价函数
定义梯度
进行梯度下降

#这里使用简单的线性模型进行举例（y=wx）
x_data = [1.0, 2.0, 3.0]
y_data = [2.0, 4.0, 6.0]
w = 1.0
def forward(x):
    return x * w

def cost(xs, ys):
    cost = 0
    for x, y in zip(xs, ys):
        y_pred = forward(x)
        cost += (y_pred - y) ** 2
    return cost / len(xs)

def gradient(xs, ys):
    grad = 0
    for x, y in zip(xs, ys):
        grad += 2 * x * (x * w - y)
    return grad / len(xs)
print('Predict (before training)', 4, forward(4))
for epoch in range(10):
    cost_val = cost(x_data, y_data)
    grad_val = gradient(x_data, y_data)
    w -= 0.1 * grad_val
    print('Epoch:', epoch, 'w=', w, 'loss=', cost_val)
print('Predict (after training)', 4, forward(4))

Predict (before training) 4 4.0
Epoch: 0 w= 1.9333333333333336 loss= 4.666666666666667
Epoch: 1 w= 1.9955555555555555 loss= 0.020740740740740594
Epoch: 2 w= 1.9997037037037038 loss= 9.218106995885089e-05
Epoch: 3 w= 1.9999802469135801 loss= 4.096936442612555e-07
Epoch: 4 w= 1.999998683127572 loss= 1.820860641186282e-09
Epoch: 5 w= 1.9999999122085048 loss= 8.092713960827921e-12
Epoch: 6 w= 1.9999999941472337 loss= 3.5967617630537535e-14
Epoch: 7 w= 1.9999999996098157 loss= 1.598560741415451e-16
Epoch: 8 w= 1.9999999999739877 loss= 7.104714637326717e-19
Epoch: 9 w= 1.9999999999982658 loss= 3.1576645553726146e-21
Predict (after training) 4 7.999999999993063

# 这里使用简单的线性模型进行举例（y=wx+b）
x_data = [1,2,3]
y_data = [3,5,7]
w, b,learning_rate, num_iter = 1, 1, 0.1, 200     #模型的超参数
def forward(x): #定义模型
    return w*x + b

def cost(xs, ys): # 定义代价函数
    cost = 0
    for x, y in zip(xs,ys):
        y_pred = forward(x)
        cost += (y_pred-y)**2
    return cost / len(xs)

def gradient(xs, ys): # 定义梯度
    grad_w, grad_b = 0, 0
    for x, y in zip(xs, ys):
        grad_w += 2 * x * (x*w+b -y)
        grad_b += 2 * (w*x+b - y)
    return grad_w / len(xs), grad_b /len(xs)

for index, epoch in enumerate(range(num_iter)):
    cost_val = cost(x_data, y_data)
    grad_val_w, grad_val_b = gradient(x_data, y_data)
    w -= learning_rate * grad_val_w
    b -= learning_rate * grad_val_b
    if index %20 == 0:
        print('Epoch:', epoch, 'w=', w, 'b=', b, 'loss=', cost_val)
print('Predict (after training)', 4, forward(4) )

Epoch: 0 w= 1.9333333333333336 b= 1.4 loss= 4.666666666666667
Epoch: 20 w= 1.9027336160002466 b= 1.221109353263385 loss= 0.007363240551269273
Epoch: 40 w= 1.94021265778235 b= 1.1359106818560742 loss= 0.0027820308578501585
Epoch: 60 w= 1.9632501369696291 b= 1.0835410767113935 loss= 0.001051126286061144
Epoch: 80 w= 1.9774107297187675 b= 1.0513507209498785 loss= 0.00039714385846262995
Epoch: 100 w= 1.9861149106483238 b= 1.0315640717820993 loss= 0.0001500516602107077
Epoch: 120 w= 1.9914651644827936 b= 1.019401687240924 loss= 5.66935639371265e-05
Epoch: 140 w= 1.9947538387790809 b= 1.0119257575636396 loss= 2.1420357411437314e-05
Epoch: 160 w= 1.9967753089675375 b= 1.0073304806793664 loss= 8.093188710848365e-06
Epoch: 180 w= 1.998017858808193 b= 1.0045058728306204 loss= 3.0578249583479597e-06
Predict (after training) 4 8.997844331553102

从Loss的变化可以看出损失一直在降低，模型越来越接近真实值

1	## 随机梯度下降（Stochastic Gradient Descent）

# 这里使用简单的线性模型进行举例（y=wx+b）
x_data = [1,2,3]
y_data = [3,5,7]
w, b,learning_rate, num_iter = 1, 1, 0.1, 200     #模型的超参数
def forward(x): #定义模型
    return w*x + b

def loss(xs, ys): # 这里使用单个样本计算损失
    y_pred = forward(x)
    return (y_pred-y)**2

def gradient(xs, ys): # 定义梯度
    grad_w = 2 * x * (x*w+b -y)
    grad_b = 2 * (w*x+b - y)
    return grad_w, grad_b

for index, epoch in enumerate(range(num_iter)):
    for x,y in zip(x_data, y_data):
        grad_val_w, grad_val_b = gradient(x_data, y_data)
        w -= learning_rate * grad_val_w
        b -= learning_rate * grad_val_b
        l = loss(x,y)
    if index %20 == 0:
        print('Epoch:', epoch, 'w=', w, 'b=', b, 'loss=', l)
print('Predict (after training)', 4, forward(4) )

Epoch: 0 w= 1.9039999999999992 b= 1.5279999999999996
Epoch: 20 w= 1.9910765961470305 b= 1.0490787211913317
Epoch: 40 w= 1.9991705506633 b= 1.0045619713518497
Epoch: 60 w= 1.9999229009228443 b= 1.000424044924356
Epoch: 80 w= 1.9999928334770611 b= 1.0000394158761645
Epoch: 100 w= 1.9999993338564752 b= 1.000003663789388
Epoch: 120 w= 1.9999999380805447 b= 1.0000003405570042
Epoch: 140 w= 1.9999999942444546 b= 1.000000031655497
Epoch: 160 w= 1.9999999994650095 b= 1.0000000029424456
Epoch: 180 w= 1.9999999999502716 b= 1.0000000002735059
Predict (after training) 4 9.000000000007809

分析：从性能和时间复杂度两个方面进行分析

1	## 批量随机梯度下降

梯度下降法的神经网络容易收敛到局部最优，为什么还广泛使用？

这个问题没有一个统一的结论，这里将我认为合理的总结一下：

深度神经网络“容易收敛到局部最优”，很可能是一种想象，实际情况是，我们可能从来没有找到过“局部最优”，更别说全局最优了。

很多人都有一种看法，就是“局部最优是神经网络优化的主要难点”。这来源于一维优化问题的直观想象。在单变量的情形下，优化问题最直观的困难就是有很多局部极值，如

人们直观的想象，高维的时候这样的局部极值会更多，指数级的增加，于是优化到全局最优就更难了（我最疑惑的地方）。然而单变量到多变量一个重要差异是，单变量的时候，Hessian矩阵只有一个特征值，于是无论这个特征值的符号正负，一个临界点都是局部极值。但是在多变量的时候，Hessian有多个不同的特征值，这时候各个特征值就可能会有更复杂的分布，如有正有负的不定型和有多个退化特征值（零特征值）的半定型

在后两种情况下，是很难找到局部极值的，更别说全局最优了。

现在看来神经网络的训练的困难主要是鞍点的问题。在实际中，我们很可能也从来没有真的遇到过局部极值。

前面很多回答说了，现在看来神经网络的训练的困难主要是鞍点的问题。在实际中，我们很可能也从来没有真的遇到过局部极值。Bengio组这篇文章Eigenvalues of the Hessian in Deep Learning里面的实验研究给出以下的结论：

• Training stops at a point that has a small gradient. The norm of the gradient is not zero, therefore it does not, technically speaking, converge to a critical point.
• There are still negative eigenvalues even when they are small in magnitude.

另一方面，一个好消息是，即使有局部极值，具有较差的loss的局部极值的吸引域也是很小的Towards Understanding Generalization of Deep Learning: Perspective of Loss Landscapes。

For the landscape of loss function for deep networks, the volume of basin of attraction of good minima dominates over that of poor minima, which guarantees optimization methods with random initialization to converge to good minima.

补充说明，这些都是实验研究结果。理论方面，在各种假设下，深度神经网络的Landscape 的鞍点数目指数增加，而具有较差loss的局部极值非常少。

SGD收敛性的很多结论都是经验性的。在loss function landscape是退化的情况下loss 停滞在某个数值上训练不动的原因，很大程度上不是因为停在某个点不动了，是停在某个区域不动了。over-parameterized的神经网络有大片的平坦区域，这里一阶二阶乃至更高阶都是退化的，甚至有实验说这样的区域时dominant的（虽然我觉得那个结论有点大）。这时候可以说反复迭代也没啥改进，但是这反过来说算法无需太多迭代就能找到这样一个平坦区域，这里loss 和其中的local minima （可能也是退化的）相差不大，是不是真的找到local minima也没那么重要了。

所以，很可能我们实际上是在“什么也没找到”的情况下就停止了训练，然后拿到测试集上试试，“咦，效果还不错”。

那么问题来了，既然局部最优点很难踩到，鞍点也很容易逃离出去，那么

为什么我们的模型看起来是收敛了呢？

初学者可能会说 “诶诶，会不会是学习率太大了，导致在“鞍点”附近震荡？” 首先，鞍点不像最优点那样容易震荡，而且哪怕你不断的减小学习率继续让模型收敛，大部分时候你这时计算output层或者后几层的梯度向量的长度时往往会发现它依然离0很遥远！（这句话是有实验支撑的，不过那篇论文我暂时没记起来，找到时贴出来）说明大部分时候收敛到的并不是鞍点。

那会不会踩到的鞍点太多，虽然前面的鞍点都轻松逃逸了，但是最后恰好收敛到一个跳不下去的鞍点身上了？

这倒是有可能，不排除有一些“马鞍面”特别平坦的鞍点区域，当模型陷入这种鞍点上时，由于计算出的梯度非常小，导致要连续迭代非常多次才可能慢慢移开这个鞍点，事实上大部分工程情况下，没等它移开的时候我们就已经默认为模型收敛、训练结束了，实际上人家模型还在努力逃离鞍点中呢。

不过话说回来，虽然高维空间中的鞍点数量远远大于最优点，而且鞍点数量随着特征空间维度增高而指数级增长，但是鞍点的数量在整个空间中又是微不足道的：按前面的假设，假设在某个维度上随机一跳有10%的概率踩到导数为0的点，那么我们在101维的空间中的一步恰好踩到这个点上的概率为10^{-100，也就是说在101维空间里随机乱跳的时候，有10}-100的可能性踩到鞍点身上。因此，即使有难以逃离的鞍点，即使我们的优化算法在努力向附近的鞍点靠拢，那么被我们正好踩到那些难以逃离的特殊鞍点的概率也是非常小的。

所以更令人信服的是，在高维空间里（深度学习问题上）真正可怕的不是局部最优也不是鞍点问题，而是一些特殊地形。比如大面积的平坦区域：

（图片来自《deep learning》）

在平坦区域，虽然导数不为0但是却不大。虽然是在不断下降但是路程却非常长。对于优化算法来说，它需要走很多很多步才有可能走过这一片平坦区域。甚至在这段地形的二阶导数过于特殊的情况下，一阶优化算法走无穷多步也走不出去（设想一下，如果终点在一米外，但是你第一次走0.5米，后续每一步都是前一步的一半长度，那么你永远也走不到面前的一米终点处）。

所以相比于栽到最优点和鞍点上，优化算法更有可能载到这种类似平坦区的地形中（如果这个平坦区又是“高原地带”，即loss值很高的地带，那么恭喜你悲剧了）。更糟糕的是，由于高维地形难以可视化，还有很多更复杂的未知地形会导致假收敛，一旦陷入到这些危险地形中，几乎是无解的。

所以说，在深度学习中，与其担忧陷入局部最优点怎么跳出来，更不如去考虑数据集要怎么做才能让网络更好学习，以及网络该怎么设计才能更好的捕获pattern，网络该怎么训练才能学到我们想让它学习的知识。

我很奇怪这两个东西有什么逻辑关系吗？人干活很多时候连局部最优都做不到，难道就不用干了吗？比如你每天上班的路线，我估计也不是一个局部最优解，更不用说全局最优，难道就不用上班了？你等下想要吃的晚餐，也不一定就是最有营养的，难道就不吃了？

我们从来就没有多少次要求自己得到最优解的行为，何苦强求模型最优解？反过来讲，既然我们的“远远不足最优解”还能让我们好好活着，那就说明模型也未必需要最优解。

假设在一个20,000维的参数空间中，如果某个点梯度值为0，那么在每个方向上既可以是凸（convex）函数也可以是凹（concave）函数（如下图所示）。但要想该点成为local minima的话，所有的20,000个方向都必须是凸的，在神经网络构成的巨大的参数空间中，这个概率是十分小的。
随机梯度下降和梯度下降的效率对比：

对于计算机的并行而言，随机梯度下降不能并行计算慢但性能高，而梯度下降可以并行计算快但性能低。

mini-batch的梯度下降（默认的SGD）

应该是标准梯度下降容易陷入局部最优，随机梯度下降因为每次计算的是一个样本所以很容易跳出局部最优从而实现全局最优，但是这样频繁的更新参数会使得损失函数具有不同强度的波动，于是引入了mini batch gradient descent。

梯度下降法是万能的模型训练算法吗？

是不是对于所有的预测模型，比如神经网络、逻辑回归、SVM或者其他自定义的模型，只要能求出定义的损失函数对参数的导数，就可以用梯度下降法训练模型参数，如果具体的模型结构合理、学习率设置合理，便可以得到不错的效果

我们在担心神经网络进入局部最优值之前，更需要注意鞍点问题。

鞍点长这样：

鞍点(红色点)示意图，来源维基

那么如何来区分鞍点和局部最优点呢？这时候就需要用到神经网络的loss surface的Hessian矩阵，通过计算Hessian矩阵的特征值，我们就可以确定神经网络的解属于那种类型：

当Hessian矩阵的特征值有正有负的时候，神经网络的一阶导数为零的点为鞍点
当Hessian矩阵的特征值全部为非负的时候，神经网络的一阶导数为零的点为局部极小值点。

根据这篇文章：Geometry of Neural Network Loss Surfaces via Random Matrix Theory

我们可以知道近似情况下，神经网络的特征值分布图：

其中是参数数目和数据量之比，越大代表相对数据越少；是loss的大小；就是特征值。从这张图可以看出来：

当Loss很大的时候，特征值分布有正有负，表明鞍点是困扰优化的主要原因
当Loss很小的时候，逐渐鞍点消失，系统中主要是局部最小值点

所以，我们在优化神经网络的过程中，主要克服的是鞍点问题。

一阶导为零的点称为稳定点，可以分为以下三类：局部最小，局部最大，鞍点。

这些点根据二阶信息去区分。

当Hessian矩阵特征值全部大于零，这时称之为局部最小（也包含了全局最小）。
当Hessian矩阵特征值全部大于等于零，并且存在0特征值，这时可能为局部最小，也可能是鞍点。
当Hessian矩阵最小特征值小于零，则为严格鞍点（包含了局部最大）。

目前我们能逃离的鞍点只有严格鞍点。逃离鞍点的方法目前我知道的有两类：

利用严格鞍点它负特征值对应的方向，采用矩阵向量乘积的形式找到下降方向。
利用扰动梯度方法逃离鞍点，在梯度的模小于某个数的时候，在梯度上加个扰动量。

那么问题来了，不是严格鞍点怎么办？于是他们证明了很多问题只有严格鞍点。

那么问题又来了，即使我们逃离了鞍点，那也只是局部最小啊？

研究者又证明了事实上很多问题没有spurious local minima . 也就是说所有的局部最小都是全局最小。比如下面这些问题。

局部最小值可怕吗？

假设，我们经过了鞍点的考验，把loss降低到系统中只有局部最小值的地方，我们还需要惧怕这些局部最小值点吗？

答案是我们不太需要当心。

第一个，很直观的解释来自于上面特征值的分布信息：当loss很小的时候，我们才会遇到局部最小值问题，也就是说这时候的loss已经足够小，我们对这时候的loss已经足够满意了，不太需要花更大力气去找全局最优值。

第二个，在一定假设条件下，很多研究表明深度学习中局部最小值很接近于全局最小值。

· 由于优化器深受局部极小值驱使，即便它极力摆脱后者，也要用很长时间。因收敛速度慢，梯度下降法通常十分冗长，即使是适应像批量梯度下降这样的大数据集之后也是如此。

· 学习率决定优化器的可靠程度和风险度。学习率设置过高可能会导致优化器忽略全局最小值，而过低则会导致运行时崩溃。解决此问题需要设置随着衰减而变化的学习率，但是在决定学习率的许多其他变量中选择衰减率很困难。

· 梯度下降对优化器的初始化尤为敏感。例如，优化器在第二个局部最小值而非第一个局部最小值附近进行初始化，则优化器的性能可能会更优，但这都是随机决定的。

· 梯度下降需要梯度，这意味着除了无法处理不可微函数之外，还容易出现诸如梯度消失或梯度爆炸等梯度问题。

当然，梯度下降已受到广泛研究，且有许多解决方案——其中一些是梯度下降变体，另一些基于网络架构——在某些情况下起作用。不能仅因为梯度下降被高估就意味着它不是现阶段可用的最佳解决方案。不过，使用批归一化来消除误差空间或选择复杂的优化器（如Adam或Adagrad）等并不是本文的重点，即使它们通常表现更好。