得到损失函数后 如何优化模型

常用的优化方法有
对损失函数的优化：
当我们对分类的Loss进行改进的时候，我们要通过梯度下降，每次优化一个step大小的梯度，这个时候我们就要求Loss对每个权重矩阵的偏导，然后应用链式法则。
最小二乘法（主要是说线性回归中的优化算法）梯度下降法、牛顿法、拟牛顿法、共轭梯度法
详细说一下梯度下降法
在求解机器学习算法的模型参数，即无约束优化问题时，梯度下降（Gradient Descent）是最常采用的方法之一，梯度下降不一定能够找到全局的最优解，有可能是一个局部最优解。当然，如果损失函数是凸函数，梯度下降法得到的解就一定是全局最优解。
1）梯度
在微积分里面，对多元函数的参数求∂偏导数，把求得的各个参数的偏导数以向量的形式写出来，就是梯度。
那么这个梯度向量求出来有什么意义呢？他的意义从几何意义上讲，就是函数变化增加最快的地方。或者说，沿着梯度向量的方向，更加容易找到函数的最大值。反过来说，沿着梯度向量相反的方向，也就是 -(∂f/∂x0, ∂f/∂y0)T的方向，梯度减少最快，也就是更加容易找到函数的最小值。
2）梯度下降与梯度上升
在机器学习算法中，在最小化损失函数时，可以通过梯度下降法来一步步的迭代求解，通过启发式的方式一步步迭代求解函数的最小值,得到最小化的损失函数，和模型参数值。反过来，如果我们需要求解损失函数的最大值，这时就需要用梯度上升法来迭代了。
梯度下降法和梯度上升法是可以互相转化的。比如我们需要求解损失函数f(θ)的最小值，这时我们需要用梯度下降法来迭代求解。但是实际上，我们可以反过来求解损失函数 -f(θ)的最大值，这时梯度上升法就派上用场了。
3）梯度下降的算法调优
在使用梯度下降时，需要进行调优。
第一、算法的步长选择。在前面的算法描述中，我提到取步长为1，但是实际上取值取决于数据样本，可以多取一些值，从大到小，分别运行算法，看看迭代效果，如果损失函数的值在变小，说明取值有效，否则要增大步长。前面说了。步长太大，会导致迭代过快，甚至有可能错过最优解。步长太小，迭代速度太慢，很长时间算法都不能结束。所以算法的步长需要多次运行后才能得到一个较为优的值。
第二、算法参数的初始值选择。初始值不同，获得的最小值也有可能不同，因此梯度下降求得的只是局部最小值；当然如果损失函数是凸函数则一定是最优解。由于有局部最优解的风险，需要多次用不同初始值运行算法，观测损失函数的最小值，选择损失函数最小化的初值。
第三、归一化。由于样本不同特征的取值范围不一样，可能导致迭代很慢，为了减少特征取值的影响，可以对特征数据归一化，也就是对于每个特征x，求出它的期望x¯和标准差std(x)，然后转化为x−x¯¯¯std(x)x−x¯std(x)
这样特征的新期望为0，新方差为1，迭代次数可以大大加快。

梯度法是从初值开始按照负梯度方向一步一步走，确定方向、确定步长、再确定方向、再确定步长只顾眼前情况，大局观念差~
牛顿法是令目标函数梯度等于零，直接解方程，求方向，目的就是一步就跨到最优解，只不过由于求解是近似的，导致这一步走得不太准，还需要在迭代，但是已经能说明目标观念很强了~

梯度下降是非常常用的优化算法。作为机器学习的基础知识，这是一个必须要掌握的算法。借助本文，让我们来一起详细了解一下这个算法。

前言

本文的代码可以到我的Github上获取：

>

本文的算法示例通过Python语言实现，在实现中使用到了numpy和matplotlib。如果你不熟悉这两个工具，请自行在网上搜索教程。

关于优化

大多数学习算法都涉及某种形式的优化。优化指的是改变x以最小化或者最大化某个函数的任务。

我们通常以最小化指代大多数最优化问题。最大化可经由最小化来实现。

我们把要最小化或最大化的函数成为目标函数（objective function）或准则（criterion）。

我们通常使用一个上标表示最小化或最大化函数的x值，记做这样：

[x^ = arg; min; f(x)]

优化本身是一个非常大的话题。如果有兴趣，可以通过《数值优化》和《运筹学》的书籍进行学习。

模型与假设函数

所有的模型都是错误的，但其中有些是有用的。– George Edward Pelham Box

模型是我们对要分析的数据的一种假设，它是为解决某个具体问题从数据中学习到的，因此它是机器学习最核心的概念。

针对一个问题，通常有大量的模型可以选择。

本文不会深入讨论这方面的内容，关于各种模型请参阅机器学习的相关书籍。本文仅以最简单的线性模型为基础来讨论梯度下降算法。

这里我们先介绍一下在监督学习（supervised learning）中常见的三个符号：

m，描述训练样本的数量

x，描述输入变量或特征

y，描述输出变量或者叫目标值

请注意，一个样本可能有很多的特征，因此x和y通常是一个向量。不过在刚开始学习的时候，为了便于理解，你可以暂时理解为这就是一个具体的数值。

训练集会包含很多的样本，我们用 表示其中第i个样本。

x是数据样本的特征，y是其目标值。例如，在预测房价的模型中，x是房子的各种信息，例如：面积，楼层，位置等等，y是房子的价格。在图像识别的任务中，x是图形的所有像素点数据，y是图像中包含的目标对象。

我们是希望寻找一个函数，将x映射到y，这个函数要足够的好，以至于能够预测对应的y。由于历史原因，这个函数叫做假设函数（hypothesis function）。

学习的过程如下图所示。即：首先根据已有的数据（称之为训练集）训练我们的算法模型，然后根据模型的假设函数来进行新数据的预测。

线性模型（linear model）正如其名称那样：是希望通过一个直线的形式来描述模式。线性模型的假设函数如下所示：

[h_{\theta}(x) = \theta_{0} + \theta_{1} x]

这个公式对于大家来说应该都是非常简单的。如果把它绘制出来，其实就是一条直线。

下图是一个具体的例子，即： 的图形：

在实际的机器学习工程中，你会拥有大量的数据。这些数据会来自于某个数据源。它们存储在csv文件中，或者以其他的形式打包。

但是本文作为演示使用，我们通过一些简单的代码自动生成了需要的数据。为了便于计算，演示的数据量也很小。

import numpy as np

max_x = 10
data_size = 10
theta_0 = 5
theta_1 = 2

def get_data:
x = nplinspace(1, max_x, data_size)
noise = nprandomnormal(0, 02, len(x))
y = theta_0 + theta_1 x + noise
return x, y

这段代码很简单，我们生成了x范围是 [1, 10] 整数的10条数据。对应的y是以线性模型的形式计算得到，其函数是：。现实中的数据常常受到各种因素的干扰，所以对于y我们故意加上了一些高斯噪声。因此最终的y值为比原先会有轻微的偏离。

最后我们的数据如下所示：

x = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
y = [666, 911, 1108, 1267, 1512, 1676, 1875, 2135, 2277, 2456]

我们可以把这10条数据绘制出来这样就有一个直观的了解了，如下图所示：

虽然演示用的数据是我们通过公式计算得到的。但在实际的工程中，模型的参数是需要我们通过数据学习到的。所以下文我们假设我们不知道这里线性模式的两个参数是什么，而是通过算法的形式求得。

最后再跟已知的参数进行对比以验证我们的算法是否正确。

有了上面的数据，我们可以尝试画一条直线来描述我们的模型。

例如，像下面这样画一条水平的直线：

很显然，这条水平线离数据太远了，非常的不匹配。

那我们可以再画一条斜线。

我们初次画的斜线可能也不贴切，它可能像下面这样：

最后我们通过不断尝试，找到了最终最合适的那条，如下所示：

梯度下降算法的计算过程，就和这种本能式的试探是类似的，它就是不停的迭代，一步步的接近最终的结果。

代价函数

上面我们尝试了几次通过一条直线来拟合（fitting）已有的数据。

二维平面上的一条直线可以通过两个参数唯一的确定，两个参数的确定也即模型的确定。那如何描述模型与数据的拟合程度呢？答案就是代价函数。

代价函数（cost function）描述了学习到的模型与实际结果的偏差程度。以上面的三幅图为例，最后一幅图中的红线相比第一条水平的绿线，其偏离程度（代价）应该是更小的。

很显然，我们希望我们的假设函数与数据尽可能的贴近，也就是说：希望代价函数的结果尽可能的小。这就涉及到结果的优化，而梯度下降就是寻找最小值的方法之一。

代价函数也叫损失函数。

对于每一个样本，假设函数会依据计算出一个估算值，我们常常用来表示。即 。

很自然的，我们会想到，通过下面这个公式来描述我们的模型与实际值的偏差程度：

[(h_\theta(x^i) - y^i)^2 = (\widehat{y}^{i} - y^i)^2 = (\theta_{0} + \theta_{1} x^{i} - y^{i})^2]

请注意， 是实际数据的值， 是我们的模型的估算值。前者对应了上图中的离散点的y坐标，后者对应了离散点在直线上投影点的y坐标。

每一条数据都会存在一个偏差值，而代价函数就是对所有样本的偏差求平均值，其计算公式如下所示：

[L(\theta) = \frac {1}{m} \sum_{i=1}^{m}(h_\theta(x^i) - y^i)^2 = \frac {1}{m} \sum_{i=1}^{m}(\theta_{0} + \theta_{1} x^{i} - y^{i})^2]

当损失函数的结果越小，则意味着通过我们的假设函数估算出的结果与真实值越接近。这也就是为什么我们要最小化损失函数的原因。

不同的模型可能会用不同的损失函数。例如，logistic回归的假设函数是这样的：。其代价函数是这样的：

借助上面这个公式，我们可以写一个函数来实现代价函数：

def cost_function(x, y, t0, t1):
cost_sum = 0
for i in range(len(x)):
cost_item = nppower(t0 + t1 x[i] - y[i], 2)
cost_sum += cost_item
return cost_sum / len(x)

这个函数的代码应该不用多做解释，它就是根据上面的完成计算。

我们可以尝试选取不同的 和 组合来计算代价函数的值，然后将结果绘制出来：

import numpy as np
import matplotlibpyplot as plt

from matplotlib import cm
from mpl_toolkitsmplot3d import Axes3D

theta_0 = 5
theta_1 = 2

def draw_cost(x, y):
fig = pltfigure(figsize=(10, 8))
ax = figgca(projection='3d')
scatter_count = 100
radius = 1
t0_range = nplinspace(theta_0 - radius, theta_0 + radius, scatter_count)
t1_range = nplinspace(theta_1 - radius, theta_1 + radius, scatter_count)
cost = npzeros((len(t0_range), len(t1_range)))
for a in range(len(t0_range)):
for b in range(len(t1_range)):
cost[a][b] = cost_function(x, y, t0_range[a], t1_range[b])
t0, t1 = npmeshgrid(t0_range, t1_range)

axset_xlabel('theta_0')
axset_ylabel('theta_1')
axplot_surface(t0, t1, cost, cmap=cmhsv)

在这段代码中，我们对 和 各自指定了一个范围进行100次的采样，然后以不同的 组合对来计算代价函数的值。

如果我们将所有点的代价函数值绘制出来，其结果如下图所示：

从这个图形中我们可以看出，当 越接近 [5, 2]时其结果（偏差）越小。相反，离得越远，结果越大。

直观解释

从上面这幅图中我们可以看出，代价函数在不同的位置结果大小不同。

从三维的角度来看，这就和地面的高低起伏一样。最高的地方就好像是山顶。

而我们的目标就是：从任意一点作为起点，能够快速寻找到一条路径并以此到达图形最低点（代价值最小）的位置。

而梯度下降的算法过程就和我们从山顶想要快速下山的做法是一样的。

在生活中，我们很自然会想到沿着最陡峭的路往下行是下山速度最快的。如下面这幅图所示：

针对这幅图，细心的读者可能很快就会有很多的疑问，例如：

对于一个函数，怎么确定下行的方向？

每一步该往前走多远？

有没有可能停留在半山腰的平台上？

这些问题也就是本文接下来要讨论的内容。

算法描述

梯度下降算法最开始的一点就是需要确定下降的方向，即：梯度。

我们常常用 来表示梯度。

对于一个二维空间的曲线来说，梯度就是其切线的方向。如下图所示：

而对于更高维空间的函数来说，梯度由所有变量的偏导数决定。

其表达式如下所示：

[\nabla f({\theta}) = ( \frac{\partial f({\theta})}{\partial \theta_1} , \frac{\partial f({\theta})}{\partial \theta_2} , , \frac{\partial f({\theta})}{\partial \theta_n} )]

在机器学习中，我们主要是用梯度下降算法来最小化代价函数，记做：

[\theta ^ = arg min L(\theta)]

其中，L是代价函数，是参数。

梯度下降算法的主体逻辑很简单，就是沿着梯度的方向一直下降，直到参数收敛为止。

记做：

[\theta ^{k + 1}_i = \theta^{k}_i - \lambda \nabla f(\theta^{k})]

这里的下标i表示第i个参数。 上标k指的是第k步的计算结果，而非k次方。在能够理解的基础上，下文的公式中将省略上标k。

这里有几点需要说明：

收敛是指函数的变化率很小。具体选择多少合适需要根据具体的项目来确定。在演示项目中我们可以选择001或者0001这样的值。不同的值将影响算法的迭代次数，因为在梯度下降的最后，我们会越来越接近平坦的地方，这个时候函数的变化率也越来越小。如果选择一个很小的值，将可能导致算法迭代次数暴增。

公式中的 称作步长，也称作学习率（learning rate）。它决定了每一步往前走多远，关于这个值我们会在下文中详细讲解。你可以暂时人为它是一个类似001或0001的固定值。

在具体的项目，我们不会让算法无休止的运行下去，所以通常会设置一个迭代次数的最大上限。

线性回归的梯度下降

有了上面的知识，我们可以回到线性模型代价函数的梯度下降算法实现了。

首先，根据代价函数我们可以得到梯度向量如下：

[\nabla f({\theta}) = (\frac{\partial L(\theta)}{ \partial\theta_{0}}, \frac{ \partial L(\theta)}{ \partial\theta_{1}}) = (\frac {2}{m} \sum_{i=1}^{m}(\theta_{0} + \theta_{1} x^{i} - y^{i}) , \frac {2}{m} \sum_{i=1}^{m}(\theta_{0} + \theta_{1} x^{i} - y^{i}) x^{i})]

接着，将每个偏导数带入迭代的公式中，得到：

[\theta_{0} := \theta_{0} - \lambda \frac{\partial L(\theta_{0})}{ \partial\theta_{0}} = \theta_{0} - \frac {2 \lambda }{m} \sum_{i=1}^{m}(\theta_{0} + \theta_{1} x^{i} - y^{i}) \ \theta_{1} := \theta_{1} - \lambda \frac{\partial L(\theta_{1})}{ \partial\theta_{1}} = \theta_{1} - \frac {2 \lambda }{m} \sum_{i=1}^{m}(\theta_{0} + \theta_{1} x^{i} - y^{i}) x^{i}]

由此就可以通过代码实现我们的梯度下降算法了，算法逻辑并不复杂：

learning_rate = 001

def gradient_descent(x, y):
t0 = 10
t1 = 10
delta = 0001
for times in range(1000):
sum1 = 0
sum2 = 0
for i in range(len(x)):
sum1 += (t0 + t1 x[i] - y[i])
sum2 += (t0 + t1 x[i] - y[i]) x[i]
t0_ = t0 - 2 learning_rate sum1 / len(x)
t1_ = t1 - 2 learning_rate sum2 / len(x)
print('Times: {}, gradient: [{}, {}]'format(times, t0_, t1_))
if (abs(t0 - t0_) < delta and abs(t1 - t1_) < delta):
print('Gradient descent finish')
return t0_, t1_
t0 = t0_
t1 = t1_
print('Gradient descent too many times')
return t0, t1

这段代码说明如下：

我们随机选择了 都为10作为起点

设置最多迭代1000次

收敛的范围设为0001

学习步长设为001

如果我们将算法迭代过程中求得的线性模式绘制出来，可以得到下面这幅动态图：

最后算法得到的结果如下：

Times: 657, gradient: [5196562662718697, 1952931052920264]
Times: 658, gradient: [5195558390180733, 19530753071808193]
Times: 659, gradient: [5194558335124868, 19532189556399233]
Times: 660, gradient: [5193562479839619, 19533620008416623]
Gradient descent finish

从输出中可以看出，算法迭代了660次就收敛了。这时的结果[5193562479839619, 19533620008416623]，这已经比较接近目标值 [5, 2]了。如果需要更高的精度，可以将delta的值调的更小，当然，此时会需要更多的迭代次数。

高维扩展

虽然我们举的例子是二维的，但是对于更高维的情况也是类似的。同样是根据迭代的公式进行运算即可：

[\theta_{i} = \theta_{i} - \lambda \frac {\partial L(\theta)}{\partial \theta_i} = \theta_{i} - \frac{2\lambda}{m} \sum_{i=1}^{m}(h_\theta(x^{k})-y^k)x_i^k]

这里的下标i表示第i个参数，上标k表示第k个数据。

梯度下降家族BGD

在上面的内容中我们看到，算法的每一次迭代都需要把所有样本进行遍历处理。这种做法称为之Batch Gradient Descent，简称BGD。作为演示示例只有10条数据，这是没有问题的。

但在实际的项目中，数据集的数量可能是几百万几千万条，这时候每一步迭代的计算量就会非常的大了。

于是就有了下面两个变种。

SGD

Stochastic Gradient Descent，简称SGD，这种算法是每次从样本集中仅仅选择一个样本来进行计算。很显然，这样做算法在每一步的计算量一下就少了很多。

其算法公式如下：

[\theta_{i} = \theta_{i} - \lambda \frac {\partial L(\theta)}{\partial \theta_i} = \theta_{i} - \lambda(h_\theta(x^k)-y^k)x_i^k]

当然，减少算法计算量也是有代价的，那就是：算法结果会强依赖于随机取到的数据情况，这可能会导致算法的最终结果不太令人满意。

MBGD

以上两种做法其实是两个极端，一个是每次用到了所有数据，另一个是每次只用一个数据。

我们自然就会想到两者取其中的方法：每次选择一小部分数据进行迭代。这样既避免了数据集过大导致每次迭代计算量过大的问题，也避免了单个数据对算法的影响。

这种算法称之为Mini-batch Gradient Descent，简称MBGD。

其算法公式如下：

[\theta_{i} = \theta_{i} - \lambda \frac {\partial L(\theta)}{\partial \theta_i} = \theta_{i} - \frac{2\lambda}{m} \sum_{i=a}^{a + b}(h_\theta(x^k)-y^k)x_i^k]

当然，我们可以认为SGD是Mini-batch为1的特例。

针对上面提到的算法变种，该如何选择呢？

下面是Andrew Ng给出的建议：

如果样本数量较小（例如小于等于2000），选择BGD即可。

如果样本数量很大，选择 来进行MBGD，例如：64，128，256，512。

下表是 Optimization for Deep Learning 中对三种算法的对比

方法准确性更新速度内存占用在线学习BGD好慢高否SGD好（with annealing）快低是MBGD好中等中等是
算法优化

式7是算法的基本形式，在这个基础上有很多人进行了更多的研究。接下来我们介绍几种梯度下降算法的优化方法。

Momentum

Momentum是动量的意思。这个算法的思想就是借助了动力学的模型：每次算法的迭代会使用到上一次的速度作为依据。

算法的公式如下：

[v^t = \gamma v^{t - 1} + \lambda \nabla f(\theta) \ \theta = \theta - v_t]

对比式7可以看出，这个算法的主要区别就是引入了，并且，每个时刻的受前一个时刻的影响。

从形式上看，动量算法引入了变量 v 充当速度角色——它代表参数在参数空间移动的方向和速率。速度被设为负梯度的指数衰减平均。名称动量来自物理类比，根据牛顿运动定律，负梯度是移动参数空间中粒子的力。动量在物理学上定义为质量乘以速度。在动量学习算法中，我们假设是单位质量，因此速度向量 v 也可以看作是粒子的动量。

对于可以取值0，而是一个常量，设为09是一个比较好的选择。

下图是momentum算法的效果对比：

对原来的算法稍加修改就可以增加动量效果：

def gradient_descent_with_momentum(x, y):
t0 = 10
t1 = 10
delta = 0001
v0 = 0
v1 = 0
gamma = 09
for times in range(1000):
sum1 = 0
sum2 = 0
for i in range(len(x)):
sum1 += (t0 + t1 x[i] - y[i])
sum2 += (t0 + t1 x[i] - y[i]) x[i]
v0 = gamma v0 + 2 learning_rate sum1 / len(x)
v1 = gamma v1 + 2 learning_rate sum2 / len(x)
t0_ = t0 - v0
t1_ = t1 - v1
print('Times: {}, gradient: [{}, {}]'format(times, t0_, t1_))
if (abs(t0 - t0_) < delta and abs(t1 - t1_) < delta):
print('Gradient descent finish')
return t0_, t1_
t0 = t0_
t1 = t1_
print('Gradient descent too many times')
return t0, t1

以下是该算法的输出：

Times: 125, gradient: [4955453758569991, 2000005017897775]
Times: 126, gradient: [4955309381126545, 19956928964532015]
Times: 127, gradient: [49542964317327005, 19855674828684156]
Times: 128, gradient: [49536358220657, 19781180992510465]
Times: 129, gradient: [495412496254411, 19788858350530971]
Gradient descent finish

从结果可以看出，改进的算法只用了129次迭代就收敛了。速度比原来660次快了很多。

同样的，我们可以把算法计算的过程做成动态图：

对比原始的算法过程可以看出，改进算法最大的区别是：在寻找目标值时会在最终结果上下跳动，但是越往后跳动的幅度越小，这也就是动量所产生的效果。

Learning Rate 优化

至此，你可能还是好奇该如何设定学习率的值。

事实上，这个值的选取需要一定的经验或者反复尝试才能确定。

《深度学习》一书中是这样描述的：“与其说是科学，这更像是一门艺术，我们应该谨慎地参考关于这个问题的大部分指导。”。

关键在于，这个值的选取不能过大也不能过小。

如果这个值过小，会导致每一次迭代的步长很小，其结果就是算法需要迭代非常多的次数。

那么，如果这个值过大会怎么样呢？其结果就是：算法可能在结果的周围来回震荡，却落不到目标的点上。下面这幅图描述了这个现象：

事实上，学习率的取值未必一定要是一个常数，关于这个值的设定有很多的研究。

下面是比较常见的一些改进算法。

AdaGrad

AdaGrad是Adaptive Gradient的简写，该算法会为每个参数设定不同的学习率。它使用历史梯度的平方和作为基础来进行计算。

其算法公式如下：

[\theta_i = \theta_i - \frac{\lambda}{\sqrt{G_t + \epsilon}} \nabla f(\theta)]

对比式7，这里的改动就在于分号下面的根号。

根号中有两个符号，第二个符号比较好理解，它就是为了避免除0而人为引入的一个很小的常数，例如可以设为：0001。

第一个符号的表达式展开如下：

[G_t = \sum_{i = 1}^{t} \nabla f(\theta){i}\nabla f(\theta){i}^{T}]

这个值其实是历史中每次梯度的平方的累加和。

AdaGrad算法能够在训练中自动的对learning rate进行调整，对于出现频率较低参数采用较大的学习率；相反，对于出现频率较高的参数采用较小的学习率。因此，Adagrad非常适合处理稀疏数据。

但该算法的缺点是它可能导致学习率非常小以至于算法收敛非常的慢。

关于这个算法的直观解释可以看李宏毅教授的视频课程：ML Lecture 3-1: Gradient Descent。

RMSProp

RMS是Root Mean Square的简写。RMSProp是AI教父Geoff Hinton提出的一种自适应学习率方法。AdaGrad会累加之前所有的梯度平方，而RMSProp仅仅是计算对应的平均值，因此可缓解Adagrad算法学习率下降较快的问题。

该算法的公式如下：

[E[\nabla f(\theta_{i})^2]^{t} = \gamma E[\nabla f(\theta_{i})^2]^{t - 1} + (1-\gamma)(\nabla f(\theta_{i})^{t})^{2} \ \theta_i = \theta_i - \frac{\lambda}{\sqrt{E[g^2]^{t+1} + \epsilon}} \nabla f(\theta_{i})]

类似的，是为了避免除0而引入。 是衰退参数，通常设为09。

这里的 是t时刻梯度平方的平均值。

Adam

Adam是Adaptive Moment Estimation的简写。它利用梯度的一阶矩估计和二阶矩估计动态调整每个参数的学习率。

Adam的优点主要在于经过偏置校正后，每一次迭代学习率都有个确定范围，使得参数比较平稳。

该算法公式如下：

[m^{t} = \beta_{1} m^{t-1} + (1-\beta_{1}) \nabla f(\theta) \ v^{t} = \beta_{2} v^{t-1} + (1-\beta_{2}) \nabla f(\theta)^2 \ \widehat{m}^{t} = \frac{m^{t}}{1 - \beta^{t}_1} \ \widehat{v}^{t} = \frac{v^{t}}{1 - \beta^{t}_2} \ \theta = \theta - \frac{\lambda}{\sqrt{\widehat{v}^{t}} + \epsilon}\widehat{m}^{t}]

，分别是对梯度的一阶矩估计和二阶矩估计。， 是对，的校正，这样可以近似为对期望的无偏估计。

Adam算法的提出者建议 默认值为09，默认值为0999，默认值为 。

在实际应用中 ，Adam较为常用，它可以比较快地得到一个预估结果。

优化小结

这里我们列举了几种优化算法。它们很难说哪种最好，不同的算法适合于不同的场景。在实际的工程中，可能需要逐个尝试一下才能确定选择哪一个，这个过程也是目前现阶段AI项目要经历的工序之一。

实际上，该方面的研究远不止于此，如果有兴趣，可以继续阅读 《Sebastian Ruder: An overview of gradient descent optimization algorithms》 这篇论文或者 Optimization for Deep Learning 这个Slides进行更多的研究。

由于篇幅所限，这里不再继续展开了。

算法限制

梯度下降算法存在一定的限制。首先，它要求函数必须是可微分的，对于不可微的函数，无法使用这种方法。

除此之外，在某些情况下，使用梯度下降算法在接近极值点的时候可能收敛速度很慢，或者产生Z字形的震荡。这一点需要通过调整学习率来回避。

另外，梯度下降还会遇到下面两类问题。

局部最小值

局部最小值（Local Minima）指的是，我们找到的最小值仅仅是一个区域内的最小值，而并非全局的。由于算法的起点是随意取的，以下面这个图形为例，我们很容易落到局部最小值的点里面。

这就是好像你从上顶往下走，你第一次走到的平台未必是山脚，它有可能只是半山腰的一个平台的而已。

算法的起点决定了算法收敛的速度以及是否会落到局部最小值上。

坏消息是，目前似乎没有特别好的方法来确定选取那个点作为起点是比较好的，这就有一点看运气的成分了。多次尝试不同的随机点或许是一个比较好的方法，这也就是为什么做算法的优化这项工作是特别消耗时间的了。

但好消息是：

对于凸函数或者凹函数来说，不存在局部极值的问题。其局部极值一定是全局极值。

最近的一些研究表明，某些局部极值并没有想象中的那么糟糕，它们已经非常的接近全局极值所带来的结果了。

鞍点

除了Local Minima，在梯度下降的过程中，还有可能遇到另外一种情况，即：鞍点（Saddle Point）。鞍点指的是我们找到点某个点确实是梯度为0，但它却不是函数的极值，它的周围既有比它小的值，也有比它大的值。这就好像马鞍一样。

如下图所示：

多类随机函数表现出以下性质：在低维空间中，局部极值很普遍。但在高维空间中，局部极值比较少见，而鞍点则很常见。

不过对于鞍点，可以通过数学方法Hessian矩阵来确定。关于这点，这里就不再展开了，有兴趣的读者可以以这里提供的几个链接继续探索。

参考资料与推荐读物

Wikipeida: Gradient descent

Sebastian Ruder: An overview of gradient descent optimization algorithms

吴恩达：机器学习

吴恩达：深度学习

Peter Flach：机器学习

李宏毅 - ML Lecture 3-1: Gradient Descent

PDF: 李宏毅 - Gradient Descent

Intro to optimization in deep learning: Gradient Descent

Intro to optimization in deep learning: Momentum, RMSProp and Adam

Stochastic Gradient Descent – Mini-batch and more

刘建平Pinard - 梯度下降（Gradient Descent）小结

多元函数的偏导数、方向导数、梯度以及微分之间的关系思考

[Machine Learning] 梯度下降法的三种形式BGD、SGD以及MBGD

作者：阿Paul >这里主要讨论梯度下降法和牛顿法的原理

形式： ，其中 为损失函数， 为模型参数
下面将推导这一形式的由来

首先，需要用到多元函数的一级泰勒展开式：

如果忽略高阶无穷小，即 是 的 领域，那么等号就会变为近似相等，即：

要使得损失函数 下降更快，只需要等式右边得到最小值。

由 可知，当 与 的夹角余弦 时等式右边可取得最小值。

由于 对应的方向单位向量可表示为：

当 与 的方向相反(夹角余弦 )时有： ，其中 为正数。由于分母为标量，因此可以合并到 中，化简为：
需要注意的是， 和 要离的充分近，也就是在它的 邻域里面，才能忽略掉泰勒展开里面的一次以上的项，否则就不能忽略它了，它就不是高阶无穷小了，约等于的条件就不成立了，所以 步长不能够太大，由此我们就得到了梯度下降法的公式。
     形式：  ， 其中为Hessian矩阵

下面将推导这一形式的由来。

首先，需要用到多元函数的二级泰勒展开式：

如果忽略高阶无穷小，即 是 的 邻域，那么等号就会变为近似相等，即：

如果是二次函数的话，我们找它梯度等于0的点是非常好找的，基于约等于的式子，两边同时求导。

因为

且H是对称矩阵，所以：

下面可以求解一次方程， 如果 hessian 矩阵可逆 ，就可以两边乘上 H 的逆矩阵，令 ，则

两边同时乘H 的逆矩阵，有

注意一下H和 都是 点处取得的，稍作调整为：

有同学肯定会说，那我们去求解方程组，那不是一次就可以求得梯度等于 0 的点 了嘛， 但是因为我们忽略了后面的高阶无穷小，所以我们只是近似的找到了梯度等于 0 的点，但 是它并没有真正找到，所以我们下次要继续去用这个公式去迭代。

迭代优化时会加上步长：

如果我们的 是二次函数的话，牛顿法一步就可以收敛，前提是步长不做设置，等于 1 的 时候就可以了，这是因为如果原函数 是二次函数的话，泰勒展开里面就不是约等于，而是直接等于。
梯度下降法和牛顿法的关系
梯度下降法只用到了一阶导数的信息，牛顿法既用到了一阶导数的信息，也用到了二阶导数的信息。

梯度下降法是用线性函数来代替目标函数，牛顿法是用二次函数来代替目标函数， 所以说牛顿法的收敛速度是更快的。

但是牛顿法也有它的局限，hessian 矩阵不一定可逆，第二个即使存在，我们来解一个线性 方程组，当 hessian 矩阵规模很大，解线性方程组是非常耗时的，因此出现了一种改进的算 法叫拟牛顿法

设有一元函数
 

则函数在点 处的导数为
 

求出来的值是 在 处沿 方向的变化率即
 
也是 在 处的切线的斜率

如果函数有极小值，那么使 不断沿着切线方向减少，可以得到使 最小的
即通过下面的迭代，算出来的 可以使 最小
 
其中 是步长，即沿切线方向变化的大小，必须取一个很小的值
设有多元函数
 
 
则函数在点 处沿 方向的偏导数为
 
 
 
求出来的值是 在 处沿 方向的变化率即
 
 
 
也是 在 处沿 方向的切线的斜率（函数在 处有不同方向的多条切线）
计算过程是只把一个坐标轴当成变量，其他轴当成常量，这样变成对一元函数求导
其实偏导就是对多元函数的某个二维切面求导
 
举个简单的例子
 
 
该函数是一个以坐标原点为顶点的旋转抛物面
求在 方向的偏导，就是把 当常数然后求导，结果为
 
 
实际上固定 得到的是一个二维切面，这个切面实际上是一条抛物线
该抛物线形状不受 取值的影响， 的变化影响的是抛物线的位置
就像 在 处的导数即切线斜率不受 值的影响
 
可以看到导数和偏导数本质上是一样的，都是求函数值沿某个坐标轴方向的变化率
只不过导数针对一元函数，偏导数针对多元函数
偏导数只能求函数值在某个坐标轴方向的变化率，方向导数则是求函数值在任意方向的变化率
 
设有多元函数
 
 
则函数在点 处沿任意方向 的导数为
 
 
 
其中
 
 
  的方向由 各个值的比例关系决定
 
可以看到偏导数是方向导数的一个特例，即 只在一个方向上有值的话就是偏导数
 
将 转换为余弦向量，可以通过偏导数求出方向导数
比如
 
要求导的点为
 
要求导的方向为
 
的长度为
 
转为余弦向量
 
则有
 
   
   
   
方向导数是为了求函数值在某个点沿某个方向的变化率
梯度则是为了求函数值在某个点处变化率最大的方向，梯度由各个轴的偏导函数组成

设有多元函数
 

其在 处的梯度为
 
 

可以看到梯度是一个向量，代表函数值变化率最大的方向

并且该梯度向量在每个轴的分量是函数在该轴的偏导数
如果函数有极小值，那么使 不断沿着梯度方向减小，可以得到使 最小的
即通过下面的迭代，算出来的 可以使 最小
  
其中 是步长，即沿梯度方向变化的大小，必须取一个很小的值

梯度下降是非常常用的优化算法。作为机器学习的基础知识，这是一个必须要掌握的算法。借助本文，让我们来一起详细了解一下这个算法。

前言

本文的代码可以到我的Github上获取：

>

本文的算法示例通过Python语言实现，在实现中使用到了numpy和matplotlib。如果你不熟悉这两个工具，请自行在网上搜索教程。

关于优化

大多数学习算法都涉及某种形式的优化。优化指的是改变x以最小化或者最大化某个函数的任务。

我们通常以最小化指代大多数最优化问题。最大化可经由最小化来实现。

我们把要最小化或最大化的函数成为目标函数（objective function）或准则（criterion）。

我们通常使用一个上标表示最小化或最大化函数的x值，记做这样：

[x^ = arg; min; f(x)]

优化本身是一个非常大的话题。如果有兴趣，可以通过《数值优化》和《运筹学》的书籍进行学习。

模型与假设函数

所有的模型都是错误的，但其中有些是有用的。– George Edward Pelham Box

模型是我们对要分析的数据的一种假设，它是为解决某个具体问题从数据中学习到的，因此它是机器学习最核心的概念。

针对一个问题，通常有大量的模型可以选择。

本文不会深入讨论这方面的内容，关于各种模型请参阅机器学习的相关书籍。本文仅以最简单的线性模型为基础来讨论梯度下降算法。

这里我们先介绍一下在监督学习（supervised learning）中常见的三个符号：

m，描述训练样本的数量

x，描述输入变量或特征

y，描述输出变量或者叫目标值

请注意，一个样本可能有很多的特征，因此x和y通常是一个向量。不过在刚开始学习的时候，为了便于理解，你可以暂时理解为这就是一个具体的数值。

训练集会包含很多的样本，我们用 表示其中第i个样本。

x是数据样本的特征，y是其目标值。例如，在预测房价的模型中，x是房子的各种信息，例如：面积，楼层，位置等等，y是房子的价格。在图像识别的任务中，x是图形的所有像素点数据，y是图像中包含的目标对象。

我们是希望寻找一个函数，将x映射到y，这个函数要足够的好，以至于能够预测对应的y。由于历史原因，这个函数叫做假设函数（hypothesis function）。

学习的过程如下图所示。即：首先根据已有的数据（称之为训练集）训练我们的算法模型，然后根据模型的假设函数来进行新数据的预测。

线性模型（linear model）正如其名称那样：是希望通过一个直线的形式来描述模式。线性模型的假设函数如下所示：

[h_{\theta}(x) = \theta_{0} + \theta_{1} x]

这个公式对于大家来说应该都是非常简单的。如果把它绘制出来，其实就是一条直线。

下图是一个具体的例子，即： 的图形：

在实际的机器学习工程中，你会拥有大量的数据。这些数据会来自于某个数据源。它们存储在csv文件中，或者以其他的形式打包。

但是本文作为演示使用，我们通过一些简单的代码自动生成了需要的数据。为了便于计算，演示的数据量也很小。

import numpy as np

max_x = 10
data_size = 10
theta_0 = 5
theta_1 = 2

def get_data:
x = nplinspace(1, max_x, data_size)
noise = nprandomnormal(0, 02, len(x))
y = theta_0 + theta_1 x + noise
return x, y

这段代码很简单，我们生成了x范围是 [1, 10] 整数的10条数据。对应的y是以线性模型的形式计算得到，其函数是：。现实中的数据常常受到各种因素的干扰，所以对于y我们故意加上了一些高斯噪声。因此最终的y值为比原先会有轻微的偏离。

最后我们的数据如下所示：

x = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
y = [666, 911, 1108, 1267, 1512, 1676, 1875, 2135, 2277, 2456]

我们可以把这10条数据绘制出来这样就有一个直观的了解了，如下图所示：

虽然演示用的数据是我们通过公式计算得到的。但在实际的工程中，模型的参数是需要我们通过数据学习到的。所以下文我们假设我们不知道这里线性模式的两个参数是什么，而是通过算法的形式求得。

最后再跟已知的参数进行对比以验证我们的算法是否正确。

有了上面的数据，我们可以尝试画一条直线来描述我们的模型。

例如，像下面这样画一条水平的直线：

很显然，这条水平线离数据太远了，非常的不匹配。

那我们可以再画一条斜线。

我们初次画的斜线可能也不贴切，它可能像下面这样：

最后我们通过不断尝试，找到了最终最合适的那条，如下所示：

梯度下降算法的计算过程，就和这种本能式的试探是类似的，它就是不停的迭代，一步步的接近最终的结果。

代价函数

上面我们尝试了几次通过一条直线来拟合（fitting）已有的数据。

二维平面上的一条直线可以通过两个参数唯一的确定，两个参数的确定也即模型的确定。那如何描述模型与数据的拟合程度呢？答案就是代价函数。

代价函数（cost function）描述了学习到的模型与实际结果的偏差程度。以上面的三幅图为例，最后一幅图中的红线相比第一条水平的绿线，其偏离程度（代价）应该是更小的。

很显然，我们希望我们的假设函数与数据尽可能的贴近，也就是说：希望代价函数的结果尽可能的小。这就涉及到结果的优化，而梯度下降就是寻找最小值的方法之一。

代价函数也叫损失函数。

对于每一个样本，假设函数会依据计算出一个估算值，我们常常用来表示。即 。

很自然的，我们会想到，通过下面这个公式来描述我们的模型与实际值的偏差程度：

[(h_\theta(x^i) - y^i)^2 = (\widehat{y}^{i} - y^i)^2 = (\theta_{0} + \theta_{1} x^{i} - y^{i})^2]

请注意， 是实际数据的值， 是我们的模型的估算值。前者对应了上图中的离散点的y坐标，后者对应了离散点在直线上投影点的y坐标。

每一条数据都会存在一个偏差值，而代价函数就是对所有样本的偏差求平均值，其计算公式如下所示：

[L(\theta) = \frac {1}{m} \sum_{i=1}^{m}(h_\theta(x^i) - y^i)^2 = \frac {1}{m} \sum_{i=1}^{m}(\theta_{0} + \theta_{1} x^{i} - y^{i})^2]

当损失函数的结果越小，则意味着通过我们的假设函数估算出的结果与真实值越接近。这也就是为什么我们要最小化损失函数的原因。

不同的模型可能会用不同的损失函数。例如，logistic回归的假设函数是这样的：。其代价函数是这样的：

借助上面这个公式，我们可以写一个函数来实现代价函数：

def cost_function(x, y, t0, t1):
cost_sum = 0
for i in range(len(x)):
cost_item = nppower(t0 + t1 x[i] - y[i], 2)
cost_sum += cost_item
return cost_sum / len(x)

这个函数的代码应该不用多做解释，它就是根据上面的完成计算。

我们可以尝试选取不同的 和 组合来计算代价函数的值，然后将结果绘制出来：

import numpy as np
import matplotlibpyplot as plt

from matplotlib import cm
from mpl_toolkitsmplot3d import Axes3D

theta_0 = 5
theta_1 = 2

def draw_cost(x, y):
fig = pltfigure(figsize=(10, 8))
ax = figgca(projection='3d')
scatter_count = 100
radius = 1
t0_range = nplinspace(theta_0 - radius, theta_0 + radius, scatter_count)
t1_range = nplinspace(theta_1 - radius, theta_1 + radius, scatter_count)
cost = npzeros((len(t0_range), len(t1_range)))
for a in range(len(t0_range)):
for b in range(len(t1_range)):
cost[a][b] = cost_function(x, y, t0_range[a], t1_range[b])
t0, t1 = npmeshgrid(t0_range, t1_range)

axset_xlabel('theta_0')
axset_ylabel('theta_1')
axplot_surface(t0, t1, cost, cmap=cmhsv)

在这段代码中，我们对 和 各自指定了一个范围进行100次的采样，然后以不同的 组合对来计算代价函数的值。

如果我们将所有点的代价函数值绘制出来，其结果如下图所示：

从这个图形中我们可以看出，当 越接近 [5, 2]时其结果（偏差）越小。相反，离得越远，结果越大。

直观解释

从上面这幅图中我们可以看出，代价函数在不同的位置结果大小不同。

从三维的角度来看，这就和地面的高低起伏一样。最高的地方就好像是山顶。

而我们的目标就是：从任意一点作为起点，能够快速寻找到一条路径并以此到达图形最低点（代价值最小）的位置。

而梯度下降的算法过程就和我们从山顶想要快速下山的做法是一样的。

在生活中，我们很自然会想到沿着最陡峭的路往下行是下山速度最快的。如下面这幅图所示：

针对这幅图，细心的读者可能很快就会有很多的疑问，例如：

对于一个函数，怎么确定下行的方向？

每一步该往前走多远？

有没有可能停留在半山腰的平台上？

这些问题也就是本文接下来要讨论的内容。

算法描述

梯度下降算法最开始的一点就是需要确定下降的方向，即：梯度。

我们常常用 来表示梯度。

对于一个二维空间的曲线来说，梯度就是其切线的方向。如下图所示：

而对于更高维空间的函数来说，梯度由所有变量的偏导数决定。

其表达式如下所示：

[\nabla f({\theta}) = ( \frac{\partial f({\theta})}{\partial \theta_1} , \frac{\partial f({\theta})}{\partial \theta_2} , , \frac{\partial f({\theta})}{\partial \theta_n} )]

在机器学习中，我们主要是用梯度下降算法来最小化代价函数，记做：

[\theta ^ = arg min L(\theta)]

其中，L是代价函数，是参数。

梯度下降算法的主体逻辑很简单，就是沿着梯度的方向一直下降，直到参数收敛为止。

记做：

[\theta ^{k + 1}_i = \theta^{k}_i - \lambda \nabla f(\theta^{k})]

这里的下标i表示第i个参数。 上标k指的是第k步的计算结果，而非k次方。在能够理解的基础上，下文的公式中将省略上标k。

这里有几点需要说明：

收敛是指函数的变化率很小。具体选择多少合适需要根据具体的项目来确定。在演示项目中我们可以选择001或者0001这样的值。不同的值将影响算法的迭代次数，因为在梯度下降的最后，我们会越来越接近平坦的地方，这个时候函数的变化率也越来越小。如果选择一个很小的值，将可能导致算法迭代次数暴增。

公式中的 称作步长，也称作学习率（learning rate）。它决定了每一步往前走多远，关于这个值我们会在下文中详细讲解。你可以暂时人为它是一个类似001或0001的固定值。

在具体的项目，我们不会让算法无休止的运行下去，所以通常会设置一个迭代次数的最大上限。

线性回归的梯度下降

有了上面的知识，我们可以回到线性模型代价函数的梯度下降算法实现了。

首先，根据代价函数我们可以得到梯度向量如下：

[\nabla f({\theta}) = (\frac{\partial L(\theta)}{ \partial\theta_{0}}, \frac{ \partial L(\theta)}{ \partial\theta_{1}}) = (\frac {2}{m} \sum_{i=1}^{m}(\theta_{0} + \theta_{1} x^{i} - y^{i}) , \frac {2}{m} \sum_{i=1}^{m}(\theta_{0} + \theta_{1} x^{i} - y^{i}) x^{i})]

接着，将每个偏导数带入迭代的公式中，得到：

[\theta_{0} := \theta_{0} - \lambda \frac{\partial L(\theta_{0})}{ \partial\theta_{0}} = \theta_{0} - \frac {2 \lambda }{m} \sum_{i=1}^{m}(\theta_{0} + \theta_{1} x^{i} - y^{i}) \ \theta_{1} := \theta_{1} - \lambda \frac{\partial L(\theta_{1})}{ \partial\theta_{1}} = \theta_{1} - \frac {2 \lambda }{m} \sum_{i=1}^{m}(\theta_{0} + \theta_{1} x^{i} - y^{i}) x^{i}]

由此就可以通过代码实现我们的梯度下降算法了，算法逻辑并不复杂：

learning_rate = 001

def gradient_descent(x, y):
t0 = 10
t1 = 10
delta = 0001
for times in range(1000):
sum1 = 0
sum2 = 0
for i in range(len(x)):
sum1 += (t0 + t1 x[i] - y[i])
sum2 += (t0 + t1 x[i] - y[i]) x[i]
t0_ = t0 - 2 learning_rate sum1 / len(x)
t1_ = t1 - 2 learning_rate sum2 / len(x)
print('Times: {}, gradient: [{}, {}]'format(times, t0_, t1_))
if (abs(t0 - t0_) < delta and abs(t1 - t1_) < delta):
print('Gradient descent finish')
return t0_, t1_
t0 = t0_
t1 = t1_
print('Gradient descent too many times')
return t0, t1

这段代码说明如下：

我们随机选择了 都为10作为起点

设置最多迭代1000次

收敛的范围设为0001

学习步长设为001

如果我们将算法迭代过程中求得的线性模式绘制出来，可以得到下面这幅动态图：

最后算法得到的结果如下：

Times: 657, gradient: [5196562662718697, 1952931052920264]
Times: 658, gradient: [5195558390180733, 19530753071808193]
Times: 659, gradient: [5194558335124868, 19532189556399233]
Times: 660, gradient: [5193562479839619, 19533620008416623]
Gradient descent finish

从输出中可以看出，算法迭代了660次就收敛了。这时的结果[5193562479839619, 19533620008416623]，这已经比较接近目标值 [5, 2]了。如果需要更高的精度，可以将delta的值调的更小，当然，此时会需要更多的迭代次数。

高维扩展

虽然我们举的例子是二维的，但是对于更高维的情况也是类似的。同样是根据迭代的公式进行运算即可：

[\theta_{i} = \theta_{i} - \lambda \frac {\partial L(\theta)}{\partial \theta_i} = \theta_{i} - \frac{2\lambda}{m} \sum_{i=1}^{m}(h_\theta(x^{k})-y^k)x_i^k]

这里的下标i表示第i个参数，上标k表示第k个数据。

梯度下降家族BGD

在上面的内容中我们看到，算法的每一次迭代都需要把所有样本进行遍历处理。这种做法称为之Batch Gradient Descent，简称BGD。作为演示示例只有10条数据，这是没有问题的。

但在实际的项目中，数据集的数量可能是几百万几千万条，这时候每一步迭代的计算量就会非常的大了。

于是就有了下面两个变种。

SGD

Stochastic Gradient Descent，简称SGD，这种算法是每次从样本集中仅仅选择一个样本来进行计算。很显然，这样做算法在每一步的计算量一下就少了很多。

其算法公式如下：

[\theta_{i} = \theta_{i} - \lambda \frac {\partial L(\theta)}{\partial \theta_i} = \theta_{i} - \lambda(h_\theta(x^k)-y^k)x_i^k]

当然，减少算法计算量也是有代价的，那就是：算法结果会强依赖于随机取到的数据情况，这可能会导致算法的最终结果不太令人满意。

MBGD

以上两种做法其实是两个极端，一个是每次用到了所有数据，另一个是每次只用一个数据。

我们自然就会想到两者取其中的方法：每次选择一小部分数据进行迭代。这样既避免了数据集过大导致每次迭代计算量过大的问题，也避免了单个数据对算法的影响。

这种算法称之为Mini-batch Gradient Descent，简称MBGD。

其算法公式如下：

[\theta_{i} = \theta_{i} - \lambda \frac {\partial L(\theta)}{\partial \theta_i} = \theta_{i} - \frac{2\lambda}{m} \sum_{i=a}^{a + b}(h_\theta(x^k)-y^k)x_i^k]

当然，我们可以认为SGD是Mini-batch为1的特例。

针对上面提到的算法变种，该如何选择呢？

下面是Andrew Ng给出的建议：

如果样本数量较小（例如小于等于2000），选择BGD即可。

如果样本数量很大，选择 来进行MBGD，例如：64，128，256，512。

下表是 Optimization for Deep Learning 中对三种算法的对比

方法准确性更新速度内存占用在线学习BGD好慢高否SGD好（with annealing）快低是MBGD好中等中等是
算法优化

式7是算法的基本形式，在这个基础上有很多人进行了更多的研究。接下来我们介绍几种梯度下降算法的优化方法。

Momentum

Momentum是动量的意思。这个算法的思想就是借助了动力学的模型：每次算法的迭代会使用到上一次的速度作为依据。

算法的公式如下：

[v^t = \gamma v^{t - 1} + \lambda \nabla f(\theta) \ \theta = \theta - v_t]

对比式7可以看出，这个算法的主要区别就是引入了，并且，每个时刻的受前一个时刻的影响。

从形式上看，动量算法引入了变量 v 充当速度角色——它代表参数在参数空间移动的方向和速率。速度被设为负梯度的指数衰减平均。名称动量来自物理类比，根据牛顿运动定律，负梯度是移动参数空间中粒子的力。动量在物理学上定义为质量乘以速度。在动量学习算法中，我们假设是单位质量，因此速度向量 v 也可以看作是粒子的动量。

对于可以取值0，而是一个常量，设为09是一个比较好的选择。

下图是momentum算法的效果对比：

对原来的算法稍加修改就可以增加动量效果：

def gradient_descent_with_momentum(x, y):
t0 = 10
t1 = 10
delta = 0001
v0 = 0
v1 = 0
gamma = 09
for times in range(1000):
sum1 = 0
sum2 = 0
for i in range(len(x)):
sum1 += (t0 + t1 x[i] - y[i])
sum2 += (t0 + t1 x[i] - y[i]) x[i]
v0 = gamma v0 + 2 learning_rate sum1 / len(x)
v1 = gamma v1 + 2 learning_rate sum2 / len(x)
t0_ = t0 - v0
t1_ = t1 - v1
print('Times: {}, gradient: [{}, {}]'format(times, t0_, t1_))
if (abs(t0 - t0_) < delta and abs(t1 - t1_) < delta):
print('Gradient descent finish')
return t0_, t1_
t0 = t0_
t1 = t1_
print('Gradient descent too many times')
return t0, t1

以下是该算法的输出：

Times: 125, gradient: [4955453758569991, 2000005017897775]
Times: 126, gradient: [4955309381126545, 19956928964532015]
Times: 127, gradient: [49542964317327005, 19855674828684156]
Times: 128, gradient: [49536358220657, 19781180992510465]
Times: 129, gradient: [495412496254411, 19788858350530971]
Gradient descent finish

从结果可以看出，改进的算法只用了129次迭代就收敛了。速度比原来660次快了很多。

同样的，我们可以把算法计算的过程做成动态图：

对比原始的算法过程可以看出，改进算法最大的区别是：在寻找目标值时会在最终结果上下跳动，但是越往后跳动的幅度越小，这也就是动量所产生的效果。

Learning Rate 优化

至此，你可能还是好奇该如何设定学习率的值。

事实上，这个值的选取需要一定的经验或者反复尝试才能确定。

《深度学习》一书中是这样描述的：“与其说是科学，这更像是一门艺术，我们应该谨慎地参考关于这个问题的大部分指导。”。

关键在于，这个值的选取不能过大也不能过小。

如果这个值过小，会导致每一次迭代的步长很小，其结果就是算法需要迭代非常多的次数。

那么，如果这个值过大会怎么样呢？其结果就是：算法可能在结果的周围来回震荡，却落不到目标的点上。下面这幅图描述了这个现象：

事实上，学习率的取值未必一定要是一个常数，关于这个值的设定有很多的研究。

下面是比较常见的一些改进算法。

AdaGrad

AdaGrad是Adaptive Gradient的简写，该算法会为每个参数设定不同的学习率。它使用历史梯度的平方和作为基础来进行计算。

其算法公式如下：

[\theta_i = \theta_i - \frac{\lambda}{\sqrt{G_t + \epsilon}} \nabla f(\theta)]

对比式7，这里的改动就在于分号下面的根号。

根号中有两个符号，第二个符号比较好理解，它就是为了避免除0而人为引入的一个很小的常数，例如可以设为：0001。

第一个符号的表达式展开如下：

[G_t = \sum_{i = 1}^{t} \nabla f(\theta){i}\nabla f(\theta){i}^{T}]

这个值其实是历史中每次梯度的平方的累加和。

AdaGrad算法能够在训练中自动的对learning rate进行调整，对于出现频率较低参数采用较大的学习率；相反，对于出现频率较高的参数采用较小的学习率。因此，Adagrad非常适合处理稀疏数据。

但该算法的缺点是它可能导致学习率非常小以至于算法收敛非常的慢。

关于这个算法的直观解释可以看李宏毅教授的视频课程：ML Lecture 3-1: Gradient Descent。

RMSProp

RMS是Root Mean Square的简写。RMSProp是AI教父Geoff Hinton提出的一种自适应学习率方法。AdaGrad会累加之前所有的梯度平方，而RMSProp仅仅是计算对应的平均值，因此可缓解Adagrad算法学习率下降较快的问题。

该算法的公式如下：

[E[\nabla f(\theta_{i})^2]^{t} = \gamma E[\nabla f(\theta_{i})^2]^{t - 1} + (1-\gamma)(\nabla f(\theta_{i})^{t})^{2} \ \theta_i = \theta_i - \frac{\lambda}{\sqrt{E[g^2]^{t+1} + \epsilon}} \nabla f(\theta_{i})]

类似的，是为了避免除0而引入。 是衰退参数，通常设为09。

这里的 是t时刻梯度平方的平均值。

Adam

Adam是Adaptive Moment Estimation的简写。它利用梯度的一阶矩估计和二阶矩估计动态调整每个参数的学习率。

Adam的优点主要在于经过偏置校正后，每一次迭代学习率都有个确定范围，使得参数比较平稳。

该算法公式如下：

[m^{t} = \beta_{1} m^{t-1} + (1-\beta_{1}) \nabla f(\theta) \ v^{t} = \beta_{2} v^{t-1} + (1-\beta_{2}) \nabla f(\theta)^2 \ \widehat{m}^{t} = \frac{m^{t}}{1 - \beta^{t}_1} \ \widehat{v}^{t} = \frac{v^{t}}{1 - \beta^{t}_2} \ \theta = \theta - \frac{\lambda}{\sqrt{\widehat{v}^{t}} + \epsilon}\widehat{m}^{t}]

，分别是对梯度的一阶矩估计和二阶矩估计。， 是对，的校正，这样可以近似为对期望的无偏估计。

Adam算法的提出者建议 默认值为09，默认值为0999，默认值为 。

在实际应用中 ，Adam较为常用，它可以比较快地得到一个预估结果。

优化小结

这里我们列举了几种优化算法。它们很难说哪种最好，不同的算法适合于不同的场景。在实际的工程中，可能需要逐个尝试一下才能确定选择哪一个，这个过程也是目前现阶段AI项目要经历的工序之一。

实际上，该方面的研究远不止于此，如果有兴趣，可以继续阅读 《Sebastian Ruder: An overview of gradient descent optimization algorithms》 这篇论文或者 Optimization for Deep Learning 这个Slides进行更多的研究。

由于篇幅所限，这里不再继续展开了。

算法限制

梯度下降算法存在一定的限制。首先，它要求函数必须是可微分的，对于不可微的函数，无法使用这种方法。

除此之外，在某些情况下，使用梯度下降算法在接近极值点的时候可能收敛速度很慢，或者产生Z字形的震荡。这一点需要通过调整学习率来回避。

另外，梯度下降还会遇到下面两类问题。

局部最小值

局部最小值（Local Minima）指的是，我们找到的最小值仅仅是一个区域内的最小值，而并非全局的。由于算法的起点是随意取的，以下面这个图形为例，我们很容易落到局部最小值的点里面。

这就是好像你从上顶往下走，你第一次走到的平台未必是山脚，它有可能只是半山腰的一个平台的而已。

算法的起点决定了算法收敛的速度以及是否会落到局部最小值上。

坏消息是，目前似乎没有特别好的方法来确定选取那个点作为起点是比较好的，这就有一点看运气的成分了。多次尝试不同的随机点或许是一个比较好的方法，这也就是为什么做算法的优化这项工作是特别消耗时间的了。

但好消息是：

对于凸函数或者凹函数来说，不存在局部极值的问题。其局部极值一定是全局极值。

最近的一些研究表明，某些局部极值并没有想象中的那么糟糕，它们已经非常的接近全局极值所带来的结果了。

鞍点

除了Local Minima，在梯度下降的过程中，还有可能遇到另外一种情况，即：鞍点（Saddle Point）。鞍点指的是我们找到点某个点确实是梯度为0，但它却不是函数的极值，它的周围既有比它小的值，也有比它大的值。这就好像马鞍一样。

如下图所示：

多类随机函数表现出以下性质：在低维空间中，局部极值很普遍。但在高维空间中，局部极值比较少见，而鞍点则很常见。

不过对于鞍点，可以通过数学方法Hessian矩阵来确定。关于这点，这里就不再展开了，有兴趣的读者可以以这里提供的几个链接继续探索。

参考资料与推荐读物

Wikipeida: Gradient descent

Sebastian Ruder: An overview of gradient descent optimization algorithms

吴恩达：机器学习

吴恩达：深度学习

Peter Flach：机器学习

李宏毅 - ML Lecture 3-1: Gradient Descent

PDF: 李宏毅 - Gradient Descent

Intro to optimization in deep learning: Gradient Descent

Intro to optimization in deep learning: Momentum, RMSProp and Adam

Stochastic Gradient Descent – Mini-batch and more

刘建平Pinard - 梯度下降（Gradient Descent）小结

多元函数的偏导数、方向导数、梯度以及微分之间的关系思考

[Machine Learning] 梯度下降法的三种形式BGD、SGD以及MBGD

作者：阿Paul >