梯度下降(GD)

1,443 阅读8分钟

一、梯度下降算法概述

1、介绍

梯度下降法(gradient descent),又名最速下降法(steepest descent)是求解无约束最优化问题最常用的方法,它是一种迭代方法,每一步主要的操作是求解目标函数的梯度向量,将当前位置的负梯度方向作为搜索方向(因为在该方向上目标函数下降最快,这也是最速下降法名称的由来)。

梯度下降法特点:越接近目标值,步长越小,下降速度越慢。

gd1.png

这里每一个圈代表一个函数梯度,最中心表示函数极值点,每次迭代根据当前位置求得的梯度(用于确定搜索方向以及与步长共同决定前进速度)和步长找到一个新的位置,这样不断迭代最终到达目标函数局部最优点(如果目标函数是凸函数,则到达全局最优点)。

我们更加直观清晰的说明梯度下降,其实就是一个公式:

gd2.png

上面的公式这个位置更新公式,说白了,就是你每走一步,就记录下你现在的位置,也就是等号左边的θi,那么走一步走多远呐?答案应该是α,那你要朝哪个方向走呢?答案是J(θ)关于θi的偏导数。

说明:

在这里我们区分下经常用的函数:

  1. 损失函数(Loss Function )是定义在单个样本上的,算的是一个样本的误差。

  2. 代价函数(Cost Function )是定义在整个训练集上的,是所有样本误差的平均,也就是损失函数的平均。

  3. 目标函数(Object Function)定义为:最终需要优化的函数。等于经验风险+结构风险(也就是Cost Function + 正则化项)。

而在梯度下降中用到的J(θ)就是这里面的损失函数。

2、推导

说明:

  1. 在这里我们用含两个简单参数θ0和θ1的线性回归函数为例进行推导。

  2. 推导用到的知识:偏导数

gd.png

3、梯度下降算法变种

梯度下降算法主要有三种变种,主要区别在于使用多少数据来计算目标函数的梯度。 不同方法主要在准确性和优化速度间做权衡。

1.Batch gradient descent (BGD)

批量梯度下降算法(BGD),其需要计算整个训练集的梯度,即:

bgd.png

其中η为学习率,用来控制更新的“力度”/"步长"。

  • 优点:

对于凸目标函数,可以保证全局最优; 对于非凸目标函数,可以保证一个局部最优。

  • 缺点:

速度慢; 数据量大时不可行; 无法在线优化(即无法处理动态产生的新样本)。

2.Stochastic gradient descent (SGD)

随机梯度下降算法(SGD),仅计算某个样本的梯度,即针对某一个训练样本 xi及其label yi更新参数:

sgd.png

逐步减小学习率,SGD表现得同BGD很相似,最后都可以有不错的收敛。

  • 优点:

更新频次快,优化速度更快; 可以在线优化(可以无法处理动态产生的新样本);一定的随机性导致有几率跳出局部最优(随机性来自于用一个样本的梯度去代替整体样本的梯度)。

  • 缺点:

随机性可能导致收敛复杂化,即使到达最优点仍然会进行过度优化,因此SGD得优化过程相比BGD充满动荡。

3.Mini-batch gradient descent (MBGD)

小批量梯度下降算法(MBGD),计算包含n个样本的mini-batch的梯度

mbgd.png

MBGD是训练神经网络最常用的优化方法。

  • 优点:

参数更新时的动荡变小,收敛过程更稳定,降低收敛难度;可以利用现有的线性代数库高效的计算多个样本的梯度。

4、挑战

由梯度下降算法变种来看, Mini-batch gradient descent (MBGD) 是一种相对较好的策略,但同样不能保证一个最优解。此外,这里还存在很多问题需要处理:

1) 如何选择合适的学习率?

学习率过小导致收敛太慢,过大又导致收敛动荡甚至偏离最优点。

2) 如何确定学习率的调整策略?

目前调整学习率基本都按照一种 “退火”的思想,要么按照预定模式调整,要么根据目标函数值的变化是否满足阈值动态改变学习率。 但是,“模式”和“阈值”都需要事先指定,无法自适应不同数据集。

3) 对所有参数的更新采用相同的学习率是否恰当?

如果数据是稀疏的且特征分布不均,似乎我们更应该给予较少出现的特征一个大的更新。

4) 如何跳出局部最优?

理论上只有严格的凸函数才可以通过梯度下降获得全局最优解。 但是,神经网络所面临的基本上都是严重非凸的目标函数,这也意味着优化容易陷入局部最优。 事实上,我们的困难往往来自 “鞍点” 而非局部极小点。 鞍点周围通常拥有相同的损失函数值,这导致SGD很难发挥作用,因为每个方向的梯度都接近于0.

5、梯度下降优化算法

下面说一些在深度学习中常用的用以解决上述问题的梯度下降优化方法。 一些对高维数据不可行的方法不再讨论,如二阶方法中的牛顿法。

  1. Momentum

  2. Nesterov accelerated gradient

  3. Adagrad

  4. Adadelta

  5. RMSprop

  6. Adam

  7. AdaMax

所有以上优化算法,由于博主研究不深入,感兴趣的可以去梯度下降优化算法总结进行详细的学习。

二、代码练习

1、批量梯度下降(BGD)

#引库
#引入matplotlib库,用于画图
import matplotlib.pyplot as plt
from math import pow
#图片嵌入jupyter
%matplotlib inline

#为了便于取用数据,我们将数据分为x,y,在直角坐标系中(x,y)是点
x = [1,2,3,4,5,6]
y = [13,14,20,21,25,30]
print("打印初始数据图...")
plt.scatter(x,y)
plt.xlabel("X")
plt.ylabel("Y")
plt.show()

#超参数设定
alpha = 0.01#学习率/步长
theta0 = 0#θ0
theta1 = 0#θ1
epsilon = 0.001#误差
m = len(x)

count = 0
loss = []

for time in range(1000):
    count += 1
    #求偏导theta0和theta1的结果
    temp0 = 0#J(θ)对θ0求导的结果
    temp1 = 0#J(θ)对θ1求导的结果
    diss = 0
    for i in range(m):
        temp0 += (theta0+theta1*x[i]-y[i])/m
        temp1 += ((theta0+theta1*x[i]-y[i])/m)*x[i]

    #更新theta0和theta1
    for i in range(m):
        theta0 = theta0 - alpha*((theta0+theta1*x[i]-y[i])/m) 
        theta1 = theta1 - alpha*((theta0+theta1*x[i]-y[i])/m)*x[i]

    #求损失函数J(θ)
    for i in range(m):
        diss = diss + 0.5*(1/m)*pow((theta0+theta1*x[i]-y[i]),2)
    loss.append(diss)

    #看是否满足条件
    '''
    if diss<=epsilon:
        break
    else:
        continue
    '''
print("最终的结果为:")
print("此次迭代次数为:{}次,最终theta0的结果为:{},最终theta1的结果为:{}".format(count,theta0,theta1))
print("预测的最终回归函数为:y={}+{}x\n".format(theta0,theta1))
print("迭代图像绘制...")
plt.scatter(range(count),loss)
plt.show()

yx1.png

2、随机梯度下降(SGD)

#引库
#引入matplotlib库,用于画图
import matplotlib.pyplot as plt
from math import pow
import numpy as np
#图片嵌入jupyter
%matplotlib inline

#为了便于取用数据,我们将数据分为x,y,在直角坐标系中(x,y)是点
x = [1,2,3,4,5,6]
y = [13,14,20,21,25,30]
print("打印初始数据图...")
plt.scatter(x,y)
plt.xlabel("X")
plt.ylabel("Y")
plt.show()

#超参数设定
alpha = 0.01#学习率/步长
theta0 = 0#θ0
theta1 = 0#θ1
epsilon = 0.001#误差
m = len(x)

count = 0
loss = []

for time in range(1000):
    count += 1
    diss = 0
    #求偏导theta0和theta1的结果
    temp0 = 0#J(θ)对θ0求导的结果
    temp1 = 0#J(θ)对θ1求导的结果
    for i in range(m):
        temp0 += (theta0+theta1*x[i]-y[i])/m
        temp1 += ((theta0+theta1*x[i]-y[i])/m)*x[i]

    #更新theta0和theta1
    for i in range(m):
        theta0 = theta0 - alpha*((theta0+theta1*x[i]-y[i])/m) 
        theta1 = theta1 - alpha*((theta0+theta1*x[i]-y[i])/m)*x[i]

    #求损失函数J(θ)
    rand_i = np.random.randint(0,m)
    diss += 0.5*(1/m)*pow((theta0+theta1*x[rand_i]-y[rand_i]),2)
    loss.append(diss)

    #看是否满足条件
    '''
    if diss<=epsilon:
        break
    else:
        continue
    '''
print("最终的结果为:")
print("此次迭代次数为:{}次,最终theta0的结果为:{},最终theta1的结果为:{}".format(count,theta0,theta1))
print("预测的最终回归函数为:y={}+{}x\n".format(theta0,theta1))
print("迭代图像绘制...")
plt.scatter(range(count),loss)
plt.show()

yx2.png

3、小批量梯度下降(MBGD)

#引库
#引入matplotlib库,用于画图
import matplotlib.pyplot as plt
from math import pow
import numpy as np
#图片嵌入jupyter
%matplotlib inline

#为了便于取用数据,我们将数据分为x,y,在直角坐标系中(x,y)是点
x = [1,2,3,4,5,6]
y = [13,14,20,21,25,30]
print("打印初始数据图...")
plt.scatter(x,y)
plt.xlabel("X")
plt.ylabel("Y")
plt.show()

#超参数设定
alpha = 0.01#学习率/步长
theta0 = 0#θ0
theta1 = 0#θ1
epsilon = 0.001#误差
diss = 0#损失函数
m = len(x)

count = 0
loss = []

for time in range(1000):
    count += 1
    diss = 0
    #求偏导theta0和theta1的结果
    temp0 = 0#J(θ)对θ0求导的结果
    temp1 = 0#J(θ)对θ1求导的结果
    for i in range(m):
        temp0 += (theta0+theta1*x[i]-y[i])/m
        temp1 += ((theta0+theta1*x[i]-y[i])/m)*x[i]

    #更新theta0和theta1
    for i in range(m):
        theta0 = theta0 - alpha*((theta0+theta1*x[i]-y[i])/m) 
        theta1 = theta1 - alpha*((theta0+theta1*x[i]-y[i])/m)*x[i]

    #求损失函数J(θ)
    result = []
    for i in range(3):
        rand_i = np.random.randint(0,m)
        result.append(rand_i)
    for j in result:
        diss += 0.5*(1/m)*pow((theta0+theta1*x[j]-y[j]),2)
    loss.append(diss)

    #看是否满足条件
    '''
    if diss<=epsilon:
        break
    else:
        continue
    '''
print("最终的结果为:")
print("此次迭代次数为:{}次,最终theta0的结果为:{},最终theta1的结果为:{}".format(count,theta0,theta1))
print("预测的最终回归函数为:y={}+{}x\n".format(theta0,theta1))
print("迭代图像绘制...")
plt.scatter(range(count),loss)
plt.show()

yx3.png