详解梯度下降法的三种形式BGD、SGD以及MBGD

哈尔滨工业大学计算机科学与技术博士在读

在应用机器学习算法时，我们通常采用梯度下降法来对采用的算法进行训练。其实，常用的梯度下降法还具体包含有三种不同的形式，它们也各自有着不同的优缺点。

下面我们以线性回归算法来对三种梯度下降法进行比较。

一般线性回归函数的假设函数为：

对应的损失函数为：

（ 这里的1/2是为了后面求导计算方便 ）
下图作为一个二维参数（ $\theta _{0}$ ， $\theta _{1}$ ） 组对应能量函数的可视化图 ：

下面我们来分别讲解三种梯度下降法

批量梯度下降法BGD

我们的目的是要 误差函数尽可能的小 ，即求解weights使误差函数尽可能小。首先，我们随机初始化weigths，然后 不断反复的更新weights使得误差函数减小， 直到满足要求时停止。这里更新算法我们选择梯度下降算法，利用初始化的weights并且反复更新weights：

这里 $\alpha$ 代表学习率，表示 每次向着J最陡峭的方向迈步的大小 。为了更新weights， 我们需要求出函数J的偏导数。首先当我们只有一个数据点（x,y）的时候，J的偏导数是：

则对 所有数据点， 上述损失函数的偏导（累和）为：

再最小化损失函数的过程中，需要 不断反复的更新weights使得误差函数减小 ，更新过程如下：

那么好了， 每次参数更新的伪代码 如下：

由上图更新公式我们就可以看到， 我们每一次的参数更新都用到了所有的训练数据 （比如有m个，就用到了m个），如果训练数据非常多的话， 是非常耗时的。

下面给出批梯度下降的收敛图：

从图中，我们可以得到BGD迭代的次数相对较少。

随机梯度下降法SGD

由于批梯度下降每跟新一个参数的时候，要用到所有的样本数，所以训练速度会随着样本数量的增加而变得非常缓慢。随机梯度下降正是为了解决这个办法而提出的。它是利用每个样本的损失函数对θ求偏导得到对应的梯度，来更新θ：

更新过程如下：

随机梯度下降是通过每个样本来迭代更新一次，对比上面的批量梯度下降，迭代一次需要用到所有训练样本（ 往往如今真实问题训练数据都是非常巨大 ），一次迭代不可能最优，如果迭代10次的话就需要遍历训练样本10次。 但是，SGD伴随的一个问题是噪音较BGD要多，使得SGD并不是每次迭代都向着整体最优化方向。

随机梯度下降收敛图如下：

我们可以从图中看出SGD迭代的次数较多，在解空间的搜索过程看起来很盲目。 但是大体上是往着最优值方向移动。

min-batch 小批量梯度下降法MBGD

我们从上面两种梯度下降法可以看出，其各自均有优缺点，那么能不能在两种方法的性能之间取得一个折衷呢？ 即，算法的训练过程比较快，而且也要保证最终参数训练的准确率， 而这正是小批量梯度下降法（Mini-batch Gradient Descent，简称MBGD）的初衷。

我们假设每次更新参数的时候用到的样本数为10个（ 不同的任务完全不同，这里举一个例子而已 ）

更新伪代码如下：

实例以及代码详解

这里参考他人博客，创建了一个数据，如下图所示：

待训练数据A、B为自变量，C为因变量。

我希望通过这些训练数据给我训练出一个线性模型，用于进行下面数据的预测，test集合如下：

比如我们给出(3.1,5.5)希望模型预测出来的值与我们给定的9.5的差别是多少？这不是重点，重点是我们训练模型过程中的参数更新方法（ 这是我们这篇文章的重点 ）批梯度下降以及随机梯度下降代码如何实现。下面分别来讲：

首先我们看批梯度下降法的代码如下：

这里有可能还是比如抽象，为了让大家更好的弄懂理解这俩个重要的方法， 我下面结合例子，一行一行代码解释：

我们看随机梯度下降法的代码如下：

与批梯度下降最大的区别就在于，我们这里更新参数的时候， 并没有将所有训练样本考虑进去， 然后求和除以总数，而是我自己编程实现 任取一个样本点 （ 代码中random函数就能清楚看到 ），然后利用这个样本点进行更新！这就是最大的区别！

那么到这个时候，我们也非常容易知道 小批量随机梯度下降法 的实现就是在这个的基础上， 随机取batch个样本， 而不是1个样本即可，掌握了本质就非常容易实现！

下面给出这个线性模型所有代码，训练，预测以及结果供参考：

#coding=utf-8
import numpy as np
import random
#下面实现的是批量梯度下降法
def batchGradientDescent(x, y, theta, alpha, m, maxIterations):
    xTrains = x.transpose()                             #得到它的转置
    for i in range(0, maxIterations):
        hypothesis = np.dot(x, theta)
        loss = hypothesis - y
        # print loss
        gradient = np.dot(xTrains, loss) / m             #对所有的样本进行求和，然后除以样本数
        theta = theta - alpha * gradient
    return theta
#下面实现的是随机梯度下降法
def StochasticGradientDescent(x, y, theta, alpha, m, maxIterations):
    data = []
    for i in range(10):
        data.append(i)
    xTrains = x.transpose()     #变成3*10，没一列代表一个训练样本
    # 这里随机挑选一个进行更新点进行即可（不用像上面一样全部考虑）
    for i in range(0,maxIterations):
        hypothesis = np.dot(x, theta)
        loss = hypothesis - y                   #注意这里有10个样本的，我下面随机抽取一个进行更新即可
        index = random.sample(data,1)           #任意选取一个样本点，得到它的下标,便于下面找到xTrains的对应列
        index1 = index[0]                       #因为回来的时候是list，我要取出变成int，更好解释
        gradient = loss[index1]*x[index1]       #只取这一个点进行更新计算
        theta = theta - alpha * gradient.T
    return theta
def predict(x, theta):
    m, n = np.shape(x)
    xTest = np.ones((m, n+1))                     #在这个例子中，是第三列放1
    xTest[:, :-1] = x                             #前俩列与x相同
    res = np.dot(xTest, theta)                    #预测这个结果
    return res
trainData = np.array([[1.1,1.5,1],[1.3,1.9,1],[1.5,2.3,1],[1.7,2.7,1],[1.9,3.1,1],[2.1,3.5,1],[2.3,3.9,1],[2.5,4.3,1],[2.7,4.7,1],[2.9,5.1,1]])
trainLabel = np.array([2.5,3.2,3.9,4.6,5.3,6,6.7,7.4,8.1,8.8])
m, n = np.shape(trainData)
theta = np.ones(n)
alpha = 0.1
maxIteration = 5000
#下面返回的theta就是学到的theta
theta = batchGradientDescent(trainData, trainLabel, theta, alpha, m, maxIteration)
print "theta = ",theta
x = np.array([[3.1, 5.5], [3.3, 5.9], [3.5, 6.3], [3.7, 6.7], [3.9, 7.1]])
print predict(x, theta)