梯度下降，随机梯度下降，

本文链接：https://blog.csdn.net/kwame211/article/details/80364079
假设我们提供了这样的数据样本（样本值取自于y=3*x1+4*x2）：
x1 x2 y
1 4 19
2 5 26
5 1 19
4 2 29
x1和x2是样本值，y是预测目标，我们需要以一条直线来拟合上面的数据，待拟合的函数如下：

我们的目的就是要求出θ1和θ2的值，让h(θ)尽量逼近目标值y。

这是一个线性回归问题，若对线性回归有所了解的同学就知道：利用最小二乘法则和梯度下降法可以求出两个参数，而深度学习也同样可以利用这两种方法求得所有的网络参数，因此，在这里用这个数学模型来解释BGD、SGD、MSGD这几个概念。

梯度下降法原理

我们首先确定损失函数：

其中，J(θ)是损失函数，m代表每次取多少样本进行训练，如果采用SGD进行训练，那每次随机取一组样本，m=1；如果是批处理，则m等于每次抽取作为训练样本的数量。θ是参数，对应（1式）的θ1和θ2。求出了θ1和θ2，h(x)的表达式就出来了：

我们的目标是让损失函数J(θ)的值最小，根据梯度下降法，首先要用J(θ)对θ求偏导：

由于是要最小化损失函数，所以参数θ按其负梯度方向来更新：

示例：

BGD(Batch gradient descent)批量梯度下降法：每次迭代使用所有的样本

每次迭代都需要把所有样本都送入，这样的好处是每次迭代都顾及了全部的样本，做的是全局最优化。
[python] view plain copy
#-*- coding: utf-8 -*-
import random
#用y = Θ1*x1 + Θ2*x2来拟合下面的输入和输出
#input1  1   2   5   4
#input2  4   5   1   2
#output  19  26  19  20
input_x = [[1,4], [2,5], [5,1], [4,2]]  #输入
y = [19,26,19,20]   #输出
theta = [1,1]       #θ参数初始化
loss = 10           #loss先定义一个数，为了进入循环迭代
step_size = 0.01    #步长
eps =0.0001         #精度要求
max_iters = 10000   #最大迭代次数
error =0            #损失值
iter_count = 0      #当前迭代次数

err1=[0,0,0,0]      #求Θ1梯度的中间变量1
err2=[0,0,0,0]      #求Θ2梯度的中间变量2

while( loss > eps and iter_count < max_iters):   #迭代条件
    loss = 0
    err1sum = 0
    err2sum = 0
    for i in range (4):     #每次迭代所有的样本都进行训练
        pred_y = theta[0]*input_x[i][0]+theta[1]*input_x[i][1]  #预测值
        err1[i]=(pred_y-y[i])*input_x[i][0]
        err1sum=err1sum+err1[i]
        err2[i]=(pred_y-y[i])*input_x[i][1]
        err2sum=err2sum+err2[i]
    theta[0] = theta[0] - step_size * err1sum/4  #对应5式
    theta[1] = theta[1] - step_size * err2sum/4  #对应5式
    for i in range (4):
        pred_y = theta[0]*input_x[i][0]+theta[1]*input_x[i][1]   #预测值
        error = (1/(2*4))*(pred_y - y[i])**2  #损失值
        loss = loss + error  #总损失值
    iter_count += 1
    print ("iters_count", iter_count)
print ('theta: ',theta )
print ('final loss: ', loss)
print ('iters: ', iter_count)

结果：
theta: [3.0044552563214433, 3.9955447274498894]
final loss: 9.428456066652548e-05
iters: 97

SGD（Stochastic gradientdescent）随机梯度下降法：每次迭代使用一组样本

针对BGD算法训练速度过慢的缺点，提出了SGD算法，普通的BGD算法是每次迭代把所有样本都过一遍，每训练一组样本就把梯度更新一次。而SGD算法是从样本中随机抽出一组，训练后按梯度更新一次，然后再抽取一组，再更新一次，在样本量及其大的情况下，可能不用训练完所有的样本就可以获得一个损失值在可接受范围之内的模型了。

[python] view plain copy
#-*- coding: utf-8 -*-
import random
#用y = Θ1*x1 + Θ2*x2来拟合下面的输入和输出
#input1  1   2   5   4
#input2  4   5   1   2
#output  19  26  19  20
input_x = [[1,4], [2,5], [5,1], [4,2]]  #输入
y = [19,26,19,20]   #输出
theta = [1,1]       #θ参数初始化
loss = 10           #loss先定义一个数，为了进入循环迭代
step_size = 0.01    #步长
eps =0.0001         #精度要求
max_iters = 10000   #最大迭代次数
error =0            #损失值
iter_count = 0      #当前迭代次数

while( loss > eps and iter_count < max_iters):    #迭代条件
    loss = 0
    i = random.randint(0,3)  #每次迭代在input_x中随机选取一组样本进行权重的更新
    pred_y = theta[0]*input_x[i][0]+theta[1]*input_x[i][1] #预测值
    theta[0] = theta[0] - step_size * (pred_y - y[i]) * input_x[i][0]
    theta[1] = theta[1] - step_size * (pred_y - y[i]) * input_x[i][1]
    for i in range (3):
        pred_y = theta[0]*input_x[i][0]+theta[1]*input_x[i][1] #预测值
        error = 0.5*(pred_y - y[i])**2
        loss = loss + error
    iter_count += 1
    print ('iters_count', iter_count)
print ('theta: ',theta )
print ('final loss: ', loss)
print ('iters: ', iter_count)

结果：
theta: [3.0044552563214433, 3.9955447274498894]
final loss: 9.428456066652548e-05
iters: 97
MBGD（Mini-batch gradient descent）小批量梯度下降：每次迭代使用b组样本

SGD相对来说要快很多，但是也有存在问题，由于单个样本的训练可能会带来很多噪声，使得SGD并不是每次迭代都向着整体最优化方向，因此在刚开始训练时可能收敛得很快，但是训练一段时间后就会变得很慢。在此基础上又提出了小批量梯度下降法，它是每次从样本中随机抽取一小批进行训练，而不是一组。

[python] view plain copy
#-*- coding: utf-8 -*-
import random
#用y = Θ1*x1 + Θ2*x2来拟合下面的输入和输出
#input1  1   2   5   4
#input2  4   5   1   2
#output  19  26  19  20
input_x = [[1,4], [2,5], [5,1], [4,2]]  #输入
y = [19,26,19,20]       #输出
theta = [1,1]           #θ参数初始化
loss = 10               #loss先定义一个数，为了进入循环迭代
step_size = 0.01        #步长
eps =0.0001             #精度要求
max_iters = 10000       #最大迭代次数
error =0                #损失值
iter_count = 0          #当前迭代次数


while( loss > eps and iter_count < max_iters):  #迭代条件
    loss = 0
    #这里每次批量选取的是2组样本进行更新，另一个点是随机点+1的相邻点
    i = random.randint(0,3)     #随机抽取一组样本
    j = (i+1)%4                 #抽取另一组样本，j=i+1
    pred_y0 = theta[0]*input_x[i][0]+theta[1]*input_x[i][1]  #预测值1
    pred_y1 = theta[0]*input_x[j][0]+theta[1]*input_x[j][1]  #预测值2
    theta[0] = theta[0] - step_size * (1/2) * ((pred_y0 - y[i]) * input_x[i][0]+(pred_y1 - y[j]) * input_x[j][0])  #对应5式
    theta[1] = theta[1] - step_size * (1/2) * ((pred_y0 - y[i]) * input_x[i][1]+(pred_y1 - y[j]) * input_x[j][1])  #对应5式
    for i in range (3):
        pred_y = theta[0]*input_x[i][0]+theta[1]*input_x[i][1]     #总预测值
        error = (1/(2*2))*(pred_y - y[i])**2                    #损失值
        loss = loss + error       #总损失值
    iter_count += 1
    print ('iters_count', iter_count)

print ('theta: ',theta )
print ('final loss: ', loss)
print ('iters: ', iter_count)

结果：
theta: [3.2044552563214433, 3.9955447274498894]
final loss: 9.728456066652548e-05
iters: 97

————————————————
版权声明：本文为CSDN博主「DemonHunter211」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/kwame211/article/details/80364079

在求解机器学习算法的模型参数，即无约束优化问题时，梯度下降（Gradient Descent）是最常采用的方法之一，另一种常用的方法是最小二乘法。这里就对梯度下降法做一个完整的总结。

1. 梯度

　　　　在微积分里面，对多元函数的参数求∂偏导数，把求得的各个参数的偏导数以向量的形式写出来，就是梯度。比如函数f(x,y), 分别对x,y求偏导数，求得的梯度向量就是(∂f/∂x, ∂f/∂y)^T,简称grad f(x,y)或者▽f(x,y)。对于在点(x₀,y₀)的具体梯度向量就是(∂f/∂x₀, ∂f/∂y₀)^T.或者▽f(x₀,y₀)，如果是3个参数的向量梯度，就是(∂f/∂x, ∂f/∂y，∂f/∂z)^T,以此类推。

　　　　那么这个梯度向量求出来有什么意义呢？他的意义从几何意义上讲，就是函数变化增加最快的地方。具体来说，对于函数f(x,y),在点(x₀,y₀)，沿着梯度向量的方向就是(∂f/∂x₀, ∂f/∂y₀)^T的方向是f(x,y)增加最快的地方。或者说，沿着梯度向量的方向，更加容易找到函数的最大值。反过来说，沿着梯度向量相反的方向，也就是 -(∂f/∂x₀, ∂f/∂y₀)^T的方向，梯度减少最快，也就是更加容易找到函数的最小值。

2. 梯度下降与梯度上升

　　　　在机器学习算法中，在最小化损失函数时，可以通过梯度下降法来一步步的迭代求解，得到最小化的损失函数，和模型参数值。反过来，如果我们需要求解损失函数的最大值，这时就需要用梯度上升法来迭代了。

　　　　梯度下降法和梯度上升法是可以互相转化的。比如我们需要求解损失函数f(θ)的最小值，这时我们需要用梯度下降法来迭代求解。但是实际上，我们可以反过来求解损失函数 -f(θ)的最大值，这时梯度上升法就派上用场了。

　　　　下面来详细总结下梯度下降法。

3. 梯度下降法算法详解

3.1 梯度下降的直观解释

　　　　首先来看看梯度下降的一个直观的解释。比如我们在一座大山上的某处位置，由于我们不知道怎么下山，于是决定走一步算一步，也就是在每走到一个位置的时候，求解当前位置的梯度，沿着梯度的负方向，也就是当前最陡峭的位置向下走一步，然后继续求解当前位置梯度，向这一步所在位置沿着最陡峭最易下山的位置走一步。这样一步步的走下去，一直走到觉得我们已经到了山脚。当然这样走下去，有可能我们不能走到山脚，而是到了某一个局部的山峰低处。

　　　　从上面的解释可以看出，梯度下降不一定能够找到全局的最优解，有可能是一个局部最优解。当然，如果损失函数是凸函数，梯度下降法得到的解就一定是全局最优解。

3.2 梯度下降的相关概念

　　　　在详细了解梯度下降的算法之前，我们先看看相关的一些概念。

　　　　1. 步长（Learning rate）：步长决定了在梯度下降迭代的过程中，每一步沿梯度负方向前进的长度。用上面下山的例子，步长就是在当前这一步所在位置沿着最陡峭最易下山的位置走的那一步的长度。

　　　　2.特征（feature）：指的是样本中输入部分，比如2个单特征的样本 $（ x^{(0)}, y^{(0)} ）, （ x^{(1)}, y^{(1)} ）$

　　　　3. 假设函数（hypothesis function）：在监督学习中，为了拟合输入样本，而使用的假设函数，记为 $h_{θ} (x)$

　　　　4. 损失函数（loss function）：为了评估模型拟合的好坏，通常用损失函数来度量拟合的程度。损失函数极小化，意味着拟合程度最好，对应的模型参数即为最优参数。在线性回归中，损失函数通常为样本输出和假设函数的差取平方。比如对于m个样本 $（ x_{i}, y_{i} ） (i = 1, 2, . . . m)$

$J (θ_{0}, θ_{1}) = \sum_{i = 1}^{m} (h_{θ} (x_{i}) - y_{i})^{2}$

　　　　其中 $x_{i}$

3.3 梯度下降的详细算法

　　　　梯度下降法的算法可以有代数法和矩阵法（也称向量法）两种表示，如果对矩阵分析不熟悉，则代数法更加容易理解。不过矩阵法更加的简洁，且由于使用了矩阵，实现逻辑更加的一目了然。这里先介绍代数法，后介绍矩阵法。

3.3.1 梯度下降法的代数方式描述

　　　　1. 先决条件：确认优化模型的假设函数和损失函数。

　　　　比如对于线性回归，假设函数表示为 $h_{θ} (x_{1}, x_{2}, . . . x_{n}) = θ_{0} + θ_{1} x_{1} + . . . + θ_{n} x_{n}$

　　　　同样是线性回归，对应于上面的假设函数，损失函数为：

$J (θ_{0}, θ_{1} . . ., θ_{n}) = \frac{1}{2 m} \sum_{j = 0}^{m} (h_{θ} (x_{0}^{(j)}, x_{1}^{(j)}, . . . x_{n}^{(j)}) - y_{j})^{2}$

　　　　2. 算法相关参数初始化：主要是初始化 $θ_{0}, θ_{1} . . ., θ_{n}$

　　　　3. 算法过程：

　　　　　　1）确定当前位置的损失函数的梯度，对于 $θ_{i}$

　　　　　　　　 $\frac{\partial}{\partial θ_{i}} J (θ_{0}, θ_{1} . . ., θ_{n})$

　　　　　　2）用步长乘以损失函数的梯度，得到当前位置下降的距离，即 $α \frac{\partial}{\partial θ_{i}} J (θ_{0}, θ_{1} . . ., θ_{n})$

　　　　　　3）确定是否所有的 $θ_{i}$

　　　　　　4）更新所有的 $θ$

　　　　　　　　 $θ_{i} = θ_{i} - α \frac{\partial}{\partial θ_{i}} J (θ_{0}, θ_{1} . . ., θ_{n})$

　　　　下面用线性回归的例子来具体描述梯度下降。假设我们的样本是 $(x_{1}^{(0)}, x_{2}^{(0)}, . . . x_{n}^{(0)}, y_{0}), (x_{1}^{(1)}, x_{2}^{(1)}, . . . x_{n}^{(1)}, y_{1}), . . . (x_{1}^{(m)}, x_{2}^{(m)}, . . . x_{n}^{(m)}, y_{n})$

　　　　 $J (θ_{0}, θ_{1} . . ., θ_{n}) = \frac{1}{2 m} \sum_{j = 0}^{m} (h_{θ} (x_{0}^{(j)}, x_{1}^{(j)}, . . . x_{n}^{(j)}) - y_{j})^{2}$

　　　　则在算法过程步骤1中对于 $θ_{i}$

　　　　 $\frac{\partial}{\partial θ_{i}} J (θ_{0}, θ_{1} . . ., θ_{n}) = \frac{1}{m} \sum_{j = 0}^{m} (h_{θ} (x_{0}^{(j)}, x_{1}^{(j)}, . . . x_{n}^{(j)}) - y_{j}) x_{i}^{(j)}$

　　　　由于样本中没有 $x_{0}$

　　　　步骤4中 $θ_{i}$

$θ_{i} = θ_{i} - α \frac{1}{m} \sum_{j = 0}^{m} (h_{θ} (x_{0}^{(j)}, x_{1}^{(j)}, . . . x_{n}^{j}) - y_{j}) x_{i}^{(j)}$

　　　　从这个例子可以看出当前点的梯度方向是由所有的样本决定的，加 $\frac{1}{m}$

　　　　在下面第4节会详细讲到的梯度下降法的变种，他们主要的区别就是对样本的采用方法不同。这里我们采用的是用所有样本。

3.3.2 梯度下降法的矩阵方式描述

　　　　这一部分主要讲解梯度下降法的矩阵方式表述，相对于3.3.1的代数法，要求有一定的矩阵分析的基础知识，尤其是矩阵求导的知识。

　　　　1. 先决条件：和3.3.1类似，需要确认优化模型的假设函数和损失函数。对于线性回归，假设函数 $h_{θ} (x_{1}, x_{2}, . . . x_{n}) = θ_{0} + θ_{1} x_{1} + . . . + θ_{n} x_{n}$

　　　　　 $h_{θ} (x) = X θ$

损失函数的表达式为： $J (θ) = \frac{1}{2} (X θ - Y)^{T} (X θ - Y)$

　　　　2. 算法相关参数初始化: $θ$

　　　　3. 算法过程：

　　　　　　1）确定当前位置的损失函数的梯度，对于 $θ$

　　　　　　　　 $\frac{\partial}{\partial θ} J (θ)$

　　　　　　2）用步长乘以损失函数的梯度，得到当前位置下降的距离，即 $α \frac{\partial}{\partial θ} J (θ)$

　　　　　　3）确定 $θ$

　　　　　　4）更新 $θ$

　　　　　　　　 $θ = θ - α \frac{\partial}{\partial θ} J (θ)$

　　　　还是用线性回归的例子来描述具体的算法过程。

　　　　损失函数对于 $θ$

　　　　　　 $\frac{\partial}{\partial θ} J (θ) = X^{T} (X θ - Y)$

　　　　步骤4中 $θ$

　　　　对于3.3.1的代数法，可以看到矩阵法要简洁很多。这里面用到了矩阵求导链式法则，和两个矩阵求导的公式。

　　　　　　公式1： $\frac{\partial}{\partial X} (X X^{T}) = 2 X$

　　　　　　公式2： $\frac{\partial}{\partial θ} (X θ) = X^{T}$

　　　　如果需要熟悉矩阵求导建议参考张贤达的《矩阵分析与应用》一书。

3.4 梯度下降的算法调优

　　　　在使用梯度下降时，需要进行调优。哪些地方需要调优呢？

　　　　1. 算法的步长选择。在前面的算法描述中，我提到取步长为1，但是实际上取值取决于数据样本，可以多取一些值，从大到小，分别运行算法，看看迭代效果，如果损失函数在变小，说明取值有效，否则要增大步长。前面说了。步长太大，会导致迭代过快，甚至有可能错过最优解。步长太小，迭代速度太慢，很长时间算法都不能结束。所以算法的步长需要多次运行后才能得到一个较为优的值。

　　　　2. 算法参数的初始值选择。初始值不同，获得的最小值也有可能不同，因此梯度下降求得的只是局部最小值；当然如果损失函数是凸函数则一定是最优解。由于有局部最优解的风险，需要多次用不同初始值运行算法，关键损失函数的最小值，选择损失函数最小化的初值。

　　　　3.归一化。由于样本不同特征的取值范围不一样，可能导致迭代很慢，为了减少特征取值的影响，可以对特征数据归一化，也就是对于每个特征x，求出它的期望 $\bar{x}$

　　　　　　 $\frac{x - \bar{x}}{s t d (x)}$

　　　　这样特征的新期望为0，新方差为1，迭代次数可以大大加快。

4. 梯度下降法大家族（BGD，SGD，MBGD）

4.1 批量梯度下降法（Batch Gradient Descent）

　　　　批量梯度下降法，是梯度下降法最常用的形式，具体做法也就是在更新参数时使用所有的样本来进行更新，这个方法对应于前面3.3.1的线性回归的梯度下降算法，也就是说3.3.1的梯度下降算法就是批量梯度下降法。　　

　　　　 $θ_{i} = θ_{i} - α \sum_{j = 0}^{m} (h_{θ} (x_{0}^{(j)}, x_{1}^{(j)}, . . . x_{n}^{(j)}) - y_{j}) x_{i}^{(j)}$

　　　　由于我们有m个样本，这里求梯度的时候就用了所有m个样本的梯度数据。

4.2 随机梯度下降法（Stochastic Gradient Descent）

　　　　随机梯度下降法，其实和批量梯度下降法原理类似，区别在与求梯度时没有用所有的m个样本的数据，而是仅仅选取一个样本j来求梯度。对应的更新公式是：

　　　　 $θ_{i} = θ_{i} - α (h_{θ} (x_{0}^{(j)}, x_{1}^{(j)}, . . . x_{n}^{(j)}) - y_{j}) x_{i}^{(j)}$

　　　　随机梯度下降法，和4.1的批量梯度下降法是两个极端，一个采用所有数据来梯度下降，一个用一个样本来梯度下降。自然各自的优缺点都非常突出。对于训练速度来说，随机梯度下降法由于每次仅仅采用一个样本来迭代，训练速度很快，而批量梯度下降法在样本量很大的时候，训练速度不能让人满意。对于准确度来说，随机梯度下降法用于仅仅用一个样本决定梯度方向，导致解很有可能不是最优。对于收敛速度来说，由于随机梯度下降法一次迭代一个样本，导致迭代方向变化很大，不能很快的收敛到局部最优解。

　　　　那么，有没有一个中庸的办法能够结合两种方法的优点呢？有！这就是4.3的小批量梯度下降法。

4.3 小批量梯度下降法（Mini-batch Gradient Descent）

　　小批量梯度下降法是批量梯度下降法和随机梯度下降法的折衷，也就是对于m个样本，我们采用x个样子来迭代，1<x<m。一般可以取x=10，当然根据样本的数据，可以调整这个x的值。对应的更新公式是：

　　　　 $θ_{i} = θ_{i} - α \sum_{j = t}^{t + x - 1} (h_{θ} (x_{0}^{(j)}, x_{1}^{(j)}, . . . x_{n}^{(j)}) - y_{j}) x_{i}^{(j)}$

5. 梯度下降法和其他无约束优化算法的比较

　　　　在机器学习中的无约束优化算法，除了梯度下降以外，还有前面提到的最小二乘法，此外还有牛顿法和拟牛顿法。

　　　　梯度下降法和最小二乘法相比，梯度下降法需要选择步长，而最小二乘法不需要。梯度下降法是迭代求解，最小二乘法是计算解析解。如果样本量不算很大，且存在解析解，最小二乘法比起梯度下降法要有优势，计算速度很快。但是如果样本量很大，用最小二乘法由于需要求一个超级大的逆矩阵，这时就很难或者很慢才能求解解析解了，使用迭代的梯度下降法比较有优势。

　　　　梯度下降法和牛顿法/拟牛顿法相比，两者都是迭代求解，不过梯度下降法是梯度求解，而牛顿法/拟牛顿法是用二阶的海森矩阵的逆矩阵或伪逆矩阵求解。相对而言，使用牛顿法/拟牛顿法收敛更快。但是每次迭代的时间比梯度下降法长。