梯度下降 订阅
梯度下降是迭代法的一种,可以用于求解最小二乘问题(线性和非线性都可以)。在求解机器学习算法的模型参数,即无约束优化问题时,梯度下降(Gradient Descent)是最常采用的方法之一,另一种常用的方法是最小二乘法。在求解损失函数的最小值时,可以通过梯度下降法来一步步的迭代求解,得到最小化的损失函数和模型参数值。反过来,如果我们需要求解损失函数的最大值,这时就需要用梯度上升法来迭代了。在机器学习中,基于基本的梯度下降法发展了两种梯度下降方法,分别为随机梯度下降法和批量梯度下降法。 展开全文
梯度下降是迭代法的一种,可以用于求解最小二乘问题(线性和非线性都可以)。在求解机器学习算法的模型参数,即无约束优化问题时,梯度下降(Gradient Descent)是最常采用的方法之一,另一种常用的方法是最小二乘法。在求解损失函数的最小值时,可以通过梯度下降法来一步步的迭代求解,得到最小化的损失函数和模型参数值。反过来,如果我们需要求解损失函数的最大值,这时就需要用梯度上升法来迭代了。在机器学习中,基于基本的梯度下降法发展了两种梯度下降方法,分别为随机梯度下降法和批量梯度下降法。
信息
用    于
求解非线性方程组
类    型
最优化算法
中文名
梯度下降
外文名
steepest descent (gradient descent)
梯度下降简介
梯度:对于可微的数量场 ,以 为分量的向量场称为f的梯度或斜量。 [1]  梯度下降法(gradient descent)是一个最优化算法,常用于机器学习和人工智能当中用来递归性地逼近最小偏差模型。
收起全文
精华内容
下载资源
问答
  • 梯度下降算法原理讲解——机器学习

    万次阅读 多人点赞 2019-01-21 20:27:48
    详细来讲讲梯度下降算法的原理,感受数学和程序的魅力吧!!

    1. 概述

    梯度下降(gradient descent)在机器学习中应用十分的广泛,不论是在线性回归还是Logistic回归中,它的主要目的是通过迭代找到目标函数的最小值,或者收敛到最小值。
    本文将从一个下山的场景开始,先提出梯度下降算法的基本思想,进而从数学上解释梯度下降算法的原理,解释为什么要用梯度,最后实现一个简单的梯度下降算法的实例!

    2. 梯度下降算法

    2.1 场景假设

    梯度下降法的基本思想可以类比为一个下山的过程。
    假设这样一个场景:一个人被困在山上,需要从山上下来(找到山的最低点,也就是山谷)。但此时山上的浓雾很大,导致可视度很低;因此,下山的路径就无法确定,必须利用自己周围的信息一步一步地找到下山的路。这个时候,便可利用梯度下降算法来帮助自己下山。怎么做呢,首先以他当前的所处的位置为基准,寻找这个位置最陡峭的地方,然后朝着下降方向走一步,然后又继续以当前位置为基准,再找最陡峭的地方,再走直到最后到达最低处;同理上山也是如此,只是这时候就变成梯度上升算法了
    在这里插入图片描述

    2.2 梯度下降

    梯度下降的基本过程就和下山的场景很类似。

    首先,我们有一个可微分的函数。这个函数就代表着一座山。我们的目标就是找到这个函数的最小值,也就是山底。根据之前的场景假设,最快的下山的方式就是找到当前位置最陡峭的方向,然后沿着此方向向下走,对应到函数中,就是找到给定点的梯度 ,然后朝着梯度相反的方向,就能让函数值下降的最快!因为梯度的方向就是函数之变化最快的方向(在后面会详细解释)
    所以,我们重复利用这个方法,反复求取梯度,最后就能到达局部的最小值,这就类似于我们下山的过程。而求取梯度就确定了最陡峭的方向,也就是场景中测量方向的手段。那么为什么梯度的方向就是最陡峭的方向呢?接下来,我们从微分开始讲起:

    2.2.1 微分

    看待微分的意义,可以有不同的角度,最常用的两种是:

    • 函数图像中,某点的切线的斜率
    • 函数的变化率
      几个微分的例子:

    1.单变量的微分,函数只有一个变量时

    d(x2)dx=2x\frac{d(x^2)}{dx}=2x

    d(2y5)dy=10y4\frac{d(-2y^5)}{dy}=-10y^4

    d(5θ)2dθ=2(5θ)\frac{d(5-\theta )^2}{d\theta}=-2(5-\theta)

    2.多变量的微分,当函数有多个变量的时候,即分别对每个变量进行求微分

    x(x2y2)=2xy2\frac{\partial}{\partial x}(x^2y^2) = 2xy^2

    y(2y5+z2)=10y4\frac{\partial}{\partial y}(-2y^5+z^2) = -10y^4

    θ2(5θ1+2θ212θ3)=2\frac{\partial}{\partial \theta_{2}}(5\theta_{1} + 2\theta_{2} - 12\theta_{3}) = 2

    θ2(0.55(5θ1+2θ212θ3))=2\frac{\partial}{\partial \theta_{2}}(0.55 - (5\theta_{1} + 2\theta_{2} - 12\theta_{3})) = -2

    2.2.2 梯度

    梯度实际上就是多变量微分的一般化。
    下面这个例子:

    J(Θ)=0.55(5θ1+2θ212θ3)J(\Theta ) = 0.55 - (5\theta_{1} + 2\theta_{2} - 12\theta_{3})

    J(Θ)=<Jθ1,Jθ2,Jθ3>=(5,2,12)\triangledown J(\Theta ) = \left < \frac{\partial J}{\partial \theta_{1}}, \frac{\partial J}{\partial \theta_{2}},\frac{\partial J}{\partial \theta_{3}} \right > =(-5,-2,12)

    我们可以看到,梯度就是分别对每个变量进行微分,然后用逗号分割开,梯度是用<>包括起来,说明梯度其实一个向量。

    梯度是微积分中一个很重要的概念,之前提到过梯度的意义

    • 在单变量的函数中,梯度其实就是函数的微分,代表着函数在某个给定点的切线的斜率
    • 在多变量函数中,梯度是一个向量,向量有方向,梯度的方向就指出了函数在给定点的上升最快的方向

    这也就说明了为什么我们需要千方百计的求取梯度!我们需要到达山底,就需要在每一步观测到此时最陡峭的地方,梯度就恰巧告诉了我们这个方向。梯度的方向是函数在给定点上升最快的方向,那么梯度的反方向就是函数在给定点下降最快的方向,这正是我们所需要的。所以我们只要沿着梯度的方向一直走,就能走到局部的最低点!

    2.3 数学解释

    首先给出数学公式:

    Θ1=Θ0+αJ(Θ)evaluatedatΘ0{\color{Red} \Theta^1} = {\color{Blue} \Theta^0} + {\color{Green} \alpha} {\color{Purple} \triangledown J(\Theta)}\rightarrow evaluated at \Theta^0

    此公式的意义是:J是关于Θ的一个函数,我们当前所处的位置为Θ0点,要从这个点走到J的最小值点,也就是山底。首先我们先确定前进的方向,也就是梯度的反向,然后走一段距离的步长,也就是α,走完这个段步长,就到达了Θ1这个点!
    在这里插入图片描述

    2.3.1 α

    α在梯度下降算法中被称作为学习率或者步长,意味着我们可以通过α来控制每一步走的距离,以保证不要步子跨的太大扯着蛋,哈哈,其实就是不要走太快,错过了最低点。同时也要保证不要走的太慢,导致太阳下山了,还没有走到山下。所以α的选择在梯度下降法中往往是很重要的!α不能太大也不能太小,太小的话,可能导致迟迟走不到最低点,太大的话,会导致错过最低点!

    2.3.2 梯度要乘以一个负号

    梯度前加一个负号,就意味着朝着梯度相反的方向前进!我们在前文提到,梯度的方向实际就是函数在此点上升最快的方向!而我们需要朝着下降最快的方向走,自然就是负的梯度的方向,所以此处需要加上负号;那么如果时上坡,也就是梯度上升算法,当然就不需要添加负号了。

    3. 实例

    我们已经基本了解了梯度下降算法的计算过程,那么我们就来看几个梯度下降算法的小实例,首先从单变量的函数开始,然后介绍多变量的函数。

    3.1 单变量函数的梯度下降

    我们假设有一个单变量的函数

    J(θ)=θ2J(\theta) = \theta^2

    函数的微分,直接求导就可以得到

    J(θ)=2θJ'(\theta) = 2\theta

    初始化,也就是起点,起点可以随意的设置,这里设置为1

    θ0=1\theta^0 = 1

    学习率也可以随意的设置,这里设置为0.4

    α=0.4\alpha = 0.4

    根据梯度下降的计算公式

    Θ1=Θ0+αJ(Θ)evaluatedatΘ0{\color{Red} \Theta^1} = {\color{Blue} \Theta^0} + {\color{Green} \alpha} {\color{Purple} \triangledown J(\Theta)}\rightarrow evaluated at \Theta^0

    我们开始进行梯度下降的迭代计算过程:

    θ0=1\theta^0 = 1

    θ1=θ0αJ(θ0)=10.42=0.2\theta^1 = \theta^0 - \alpha*J'(\theta^0)=1 - 0.4*2 = 0.2

    θ2=θ1αJ(θ1)=0.20.40.4=0.04\theta^2 = \theta^1 - \alpha*J'(\theta^1)= 0.2 - 0.4*0.4=0.04

    θ3=0.008\theta^3 = 0.008

    θ4=0.0016\theta^4 = 0.0016

    如图,经过四次的运算,也就是走了四步,基本就抵达了函数的最低点,也就是山底
    在这里插入图片描述

    3.2 多变量函数的梯度下降

    我们假设有一个目标函数

    J(Θ)=θ12+θ22J(\Theta) = \theta_{1}^2 + \theta_{2}^2

    现在要通过梯度下降法计算这个函数的最小值。我们通过观察就能发现最小值其实就是 (0,0)点。但是接下来,我们会从梯度下降算法开始一步步计算到这个最小值!
    我们假设初始的起点为:

    Θ0=(1,3)\Theta^0 = (1, 3)

    初始的学习率为:

    α=0.1\alpha = 0.1

    函数的梯度为:

    J(Θ)=<2θ1,2θ2>\triangledown J(\Theta ) = \left < 2\theta_{1},2\theta_{2} \right >

    进行多次迭代:

    Θ0=(1,3)\Theta^0 = (1, 3)

    Θ1=Θ0αJ(Θ)=(1,3)0.1(2,6)=(0.8,2.4)\Theta^1 = \Theta^0 - \alpha\triangledown J(\Theta ) = (1,3) - 0.1*(2, 6)=(0.8, 2.4)

    Θ2=(0.8,2.4)0.1(1.6,4.8)=(0.64,1.92)\Theta^2 = (0.8, 2.4) - 0.1*(1.6, 4.8)=(0.64, 1.92)

    Θ3=(0.5124,1.536)\Theta^3 =(0.5124, 1.536)

    Θ4=(0.4096,1.228800000000001)\Theta^4 =(0.4096, 1.228800000000001)
    \vdots
    Θ10=(0.1073741824000003,0.32212254720000005)\Theta^{10} =(0.1073741824000003, 0.32212254720000005)
    \vdots
    Θ50=(1.141798154164342e05,3.42539442494306e05)\Theta^{50} =(1.141798154164342e^{-05}, 3.42539442494306e^{-05})
    \vdots
    Θ100=(1.6296287810675902e10,4.8888886343202771e10)\Theta^{100} =(1.6296287810675902e^{-10}, 4.8888886343202771e^{-10})

    我们发现,已经基本靠近函数的最小值点
    在这里插入图片描述

    4. 代码实现

    4. 1 场景分析

    下面我们将用python实现一个简单的梯度下降算法。场景是一个简单的线性回归的例子:假设现在我们有一系列的点,如下图所示:
    在这里插入图片描述
    我们将用梯度下降法来拟合出这条直线!

    首先,我们需要定义一个代价函数,在此我们选用均方误差代价函数(也称平方误差代价函数)

    J(Θ)=12mi=1m(hθ(x(i))y(i))2J(\Theta) = \frac{1}{2m}\sum_{i=1}^{m}(h_{\theta}(x^{(i)})-y^{(i)})^2

    此公式中

    • m是数据集中数据点的个数,也就是样本数
    • ½是一个常量,这样是为了在求梯度的时候,二次方乘下来的2就和这里的½抵消了,自然就没有多余的常数系数,方便后续的计算,同时对结果不会有影响
    • y 是数据集中每个点的真实y坐标的值,也就是类标签
    • h 是我们的预测函数(假设函数),根据每一个输入x,根据Θ 计算得到预测的y值,即

    hΘ(x(i))=Θ0+Θ1x1(i)h_{\Theta}(x^{(i)}) = \Theta_{0} + \Theta_{1}x_{1}^{(i)}

    我们可以根据代价函数看到,代价函数中的变量有两个,所以是一个多变量的梯度下降问题,求解出代价函数的梯度,也就是分别对两个变量进行微分

    J(Θ)=<δJδΘ0,δJδΘ1>\triangledown J(\Theta ) = \left < \frac{\delta J}{\delta \Theta_{0}}, \frac{\delta J}{\delta \Theta_{1}} \right >

    δJδΘ0=1mi=1m(hΘ(x(i))y(i))\frac{\delta J}{\delta \Theta_{0}} = \frac{1}{m}\sum_{i=1}^{m}(h_{\Theta}(x^{(i)})-y^{(i)})

    δJδΘ1=1mi=1m(hΘ(x(i))y(i))x1(i)\frac{\delta J}{\delta \Theta_{1}} = \frac{1}{m}\sum_{i=1}^{m}(h_{\Theta}(x^{(i)})-y^{(i)})x_{1}^{(i)}

    明确了代价函数和梯度,以及预测的函数形式。我们就可以开始编写代码了。但在这之前,需要说明一点,就是为了方便代码的编写,我们会将所有的公式都转换为矩阵的形式,python中计算矩阵是非常方便的,同时代码也会变得非常的简洁。
    为了转换为矩阵的计算,我们观察到预测函数的形式

    hΘ(x(i))=Θ0+Θ1x(i)h_{\Theta}(x^{(i)}) = \Theta_{0} + \Theta_{1}x^{(i)}

    我们有两个变量,为了对这个公式进行矩阵化,我们可以给每一个点x增加一维,这一维的值固定为1,这一维将会乘到Θ0上。这样就方便我们统一矩阵化的计算

    (x1(i),y(i))(x0(i),x1(i),y(i))withx0(i)=1i(x_{1}^{(i)},y^{(i)})\rightarrow (x_{0}^{(i)},x_{1}^{(i)},y^{(i)}) with x_{0}^{(i)} = 1 \forall _{i}

    然后我们将代价函数和梯度转化为矩阵向量相乘的形式

    J(Θ)=12m(XΘy)T(XΘy)J(\Theta) = \frac{1}{2m}(X\Theta - \vec{y})^{T}(X\Theta - \vec{y})

    J(Θ)=1mXT(XΘy))\triangledown J(\Theta) = \frac{1}{m}X^{T}(X\Theta - \vec{y}))

    4. 2 代码

    首先,我们需要定义数据集和学习率

    #!/usr/bin/env python3
    # -*- coding: utf-8 -*-
    # @Time    : 2019/1/21 21:06
    # @Author  : Arrow and Bullet
    # @FileName: gradient_descent.py
    # @Software: PyCharm
    # @Blog    :https://blog.csdn.net/qq_41800366
    
    from numpy import *
    
    # 数据集大小 即20个数据点
    m = 20
    # x的坐标以及对应的矩阵
    X0 = ones((m, 1))  # 生成一个m行1列的向量,也就是x0,全是1
    X1 = arange(1, m+1).reshape(m, 1)  # 生成一个m行1列的向量,也就是x1,从1到m
    X = hstack((X0, X1))  # 按照列堆叠形成数组,其实就是样本数据
    # 对应的y坐标
    y = np.array([
        3, 4, 5, 5, 2, 4, 7, 8, 11, 8, 12,
        11, 13, 13, 16, 17, 18, 17, 19, 21
    ]).reshape(m, 1)
    # 学习率
    alpha = 0.01
    

    接下来我们以矩阵向量的形式定义代价函数和代价函数的梯度

    # 定义代价函数
    def cost_function(theta, X, Y):
        diff = dot(X, theta) - Y  # dot() 数组需要像矩阵那样相乘,就需要用到dot()
        return (1/(2*m)) * dot(diff.transpose(), diff)
    
    
    # 定义代价函数对应的梯度函数
    def gradient_function(theta, X, Y):
        diff = dot(X, theta) - Y
        return (1/m) * dot(X.transpose(), diff)
    

    最后就是算法的核心部分,梯度下降迭代计算

    # 梯度下降迭代
    def gradient_descent(X, Y, alpha):
        theta = array([1, 1]).reshape(2, 1)
        gradient = gradient_function(theta, X, Y)
        while not all(abs(gradient) <= 1e-5):
            theta = theta - alpha * gradient
            gradient = gradient_function(theta, X, Y)
        return theta
    
    
    optimal = gradient_descent(X, Y, alpha)
    print('optimal:', optimal)
    print('cost function:', cost_function(optimal, X, Y)[0][0])
    

    当梯度小于1e-5时,说明已经进入了比较平滑的状态,类似于山谷的状态,这时候再继续迭代效果也不大了,所以这个时候可以退出循环!
    运行代码,计算得到的结果如下:

    print('optimal:', optimal)  # 结果 [[0.51583286][0.96992163]]
    print('cost function:', cost_function(optimal, X, Y)[0][0])  # 1.014962406233101
    

    通过matplotlib画出图像,

    # 根据数据画出对应的图像
    def plot(X, Y, theta):
        import matplotlib.pyplot as plt
        ax = plt.subplot(111)  # 这是我改的
        ax.scatter(X, Y, s=30, c="red", marker="s")
        plt.xlabel("X")
        plt.ylabel("Y")
        x = arange(0, 21, 0.2)  # x的范围
        y = theta[0] + theta[1]*x
        ax.plot(x, y)
        plt.show()
    
    
    plot(X1, Y, optimal)
    

    所拟合出的直线如下
    在这里插入图片描述
    全部代码如下,大家有兴趣的可以复制下来跑一下看一下结果:

    #!/usr/bin/env python3
    # -*- coding: utf-8 -*-
    # @Time    : 2019/1/21 21:06
    # @Author  : Arrow and Bullet
    # @FileName: gradient_descent.py
    # @Software: PyCharm
    # @Blog    :https://blog.csdn.net/qq_41800366
    
    from numpy import *
    
    # 数据集大小 即20个数据点
    m = 20
    # x的坐标以及对应的矩阵
    X0 = ones((m, 1))  # 生成一个m行1列的向量,也就是x0,全是1
    X1 = arange(1, m+1).reshape(m, 1)  # 生成一个m行1列的向量,也就是x1,从1到m
    X = hstack((X0, X1))  # 按照列堆叠形成数组,其实就是样本数据
    # 对应的y坐标
    Y = array([
        3, 4, 5, 5, 2, 4, 7, 8, 11, 8, 12,
        11, 13, 13, 16, 17, 18, 17, 19, 21
    ]).reshape(m, 1)
    # 学习率
    alpha = 0.01
    
    
    # 定义代价函数
    def cost_function(theta, X, Y):
        diff = dot(X, theta) - Y  # dot() 数组需要像矩阵那样相乘,就需要用到dot()
        return (1/(2*m)) * dot(diff.transpose(), diff)
    
    
    # 定义代价函数对应的梯度函数
    def gradient_function(theta, X, Y):
        diff = dot(X, theta) - Y
        return (1/m) * dot(X.transpose(), diff)
    
    
    # 梯度下降迭代
    def gradient_descent(X, Y, alpha):
        theta = array([1, 1]).reshape(2, 1)
        gradient = gradient_function(theta, X, Y)
        while not all(abs(gradient) <= 1e-5):
            theta = theta - alpha * gradient
            gradient = gradient_function(theta, X, Y)
        return theta
    
    
    optimal = gradient_descent(X, Y, alpha)
    print('optimal:', optimal)
    print('cost function:', cost_function(optimal, X, Y)[0][0])
    
    
    # 根据数据画出对应的图像
    def plot(X, Y, theta):
        import matplotlib.pyplot as plt
        ax = plt.subplot(111)  # 这是我改的
        ax.scatter(X, Y, s=30, c="red", marker="s")
        plt.xlabel("X")
        plt.ylabel("Y")
        x = arange(0, 21, 0.2)  # x的范围
        y = theta[0] + theta[1]*x
        ax.plot(x, y)
        plt.show()
    
    
    plot(X1, Y, optimal)
    

    5. 小结

    至此,就基本介绍完了梯度下降法的基本思想和算法流程,并且用python实现了一个简单的梯度下降算法拟合直线的案例!
    最后,我们回到文章开头所提出的场景假设:
    这个下山的人实际上就代表了反向传播算法,下山的路径其实就代表着算法中一直在寻找的参数Θ,山上当前点的最陡峭的方向实际上就是代价函数在这一点的梯度方向,场景中观测最陡峭方向所用的工具就是微分 。在下一次观测之前的时间就是有我们算法中的学习率α所定义的。
    可以看到场景假设和梯度下降算法很好的完成了对应!

    本文部分内容来自一位前辈,非常感谢分享!谢谢!

    展开全文
  • 一文看懂常用的梯度下降算法

    万次阅读 多人点赞 2017-11-29 00:00:00
    梯度下降算法(Gradient Descent Optimization)是神经网络模型训练最常用的优化算法。对于深度学习模型,基本都是采用梯度下降算法来进行优化训练的。梯度下降算法背后的原理:目标函数关于参数的梯度将是目标函数...


    作者:叶    虎

    编辑:祝鑫泉


    640?wx_fmt=png&wxfrom=5&wx_lazy=1

    概述

    梯度下降算法(Gradient Descent Optimization)是神经网络模型训练最常用的优化算法。对于深度学习模型,基本都是采用梯度下降算法来进行优化训练的。梯度下降算法背后的原理:目标函数640?wx_fmt=png&wxfrom=5&wx_lazy=1关于参数640?wx_fmt=png&wxfrom=5&wx_lazy=1的梯度将是目标函数上升最快的方向。对于最小化优化问题,只需要将参数沿着梯度相反的方向前进一个步长,就可以实现目标函数的下降。这个步长又称为学习速率640?wx_fmt=png&wxfrom=5&wx_lazy=1。参数更新公式如下:

    640?wx_fmt=png&wxfrom=5&wx_lazy=1

    其中640?wx_fmt=png&wxfrom=5&wx_lazy=1是参数的梯度,根据计算目标函数640?wx_fmt=png&wxfrom=5&wx_lazy=1采用数据量的不同,梯度下降算法又可以分为批量梯度下降算法(Batch Gradient Descent),随机梯度下降算法(Stochastic GradientDescent)和小批量梯度下降算法(Mini-batch Gradient Descent)。对于批量梯度下降算法,640?wx_fmt=png&wxfrom=5&wx_lazy=1是在整个训练集上计算的,如果数据集比较大,可能会面临内存不足问题,而且其收敛速度一般比较慢。随机梯度下降算法是另外一个极端,640?wx_fmt=png&wxfrom=5&wx_lazy=1是针对训练集中的一个训练样本计算的,又称为在线学习,即得到了一个样本,就可以执行一次参数更新。所以其收敛速度会快一些,但是有可能出现目标函数值震荡现象,因为高频率的参数更新导致了高方差。小批量梯度下降算法是折中方案,选取训练集中一个小批量样本计算640?wx_fmt=png&wxfrom=5&wx_lazy=1这样可以保证训练过程更稳定,而且采用批量训练方法也可以利用矩阵计算的优势。这是目前最常用的梯度下降算法。

    对于神经网络模型,借助于BP算法可以高效地计算梯度,从而实施梯度下降算法。但梯度下降算法一个老大难的问题是:不能保证全局收敛。如果这个问题解决了,深度学习的世界会和谐很多。梯度下降算法针对凸优化问题原则上是可以收敛到全局最优的,因为此时只有唯一的局部最优点。而实际上深度学习模型是一个复杂的非线性结构,一般属于非凸问题,这意味着存在很多局部最优点(鞍点),采用梯度下降算法可能会陷入局部最优,这应该是最头疼的问题。这点和进化算法如遗传算法很类似,都无法保证收敛到全局最优。因此,我们注定在这个问题上成为高级调参师。可以看到,梯度下降算法中一个重要的参数是学习速率,适当的学习速率很重要:学习速率过小时收敛速度慢,而过大时导致训练震荡,而且可能会发散。理想的梯度下降算法要满足两点:收敛速度要快;能全局收敛。为了这个理想,出现了很多经典梯度下降算法的变种,下面将分别介绍它们。


    01

    Momentum optimization

    冲量梯度下降算法是BorisPolyak1964年提出的,其基于这样一个物理事实:将一个小球从山顶滚下,其初始速率很慢,但在加速度作用下速率很快增加,并最终由于阻力的存在达到一个稳定速率。对于冲量梯度下降算法,其更新方程如下:

    0?wx_fmt=png

    可以看到,参数更新时不仅考虑当前梯度值,而且加上了一个积累项(冲量),但多了一个超参0?wx_fmt=png,一般取接近1的值如0.9。相比原始梯度下降算法,冲量梯度下降算法有助于加速收敛。当梯度与冲量方向一致时,冲量项会增加,而相反时,冲量项减少,因此冲量梯度下降算法可以减少训练的震荡过程。TensorFlow中提供了这一优化器:tf.train.MomentumOptimizer(learning_rate=learning_rate,momentum=0.9)。


    02 

    NAG

    NAG算法全称Nesterov Accelerated Gradient,是YuriiNesterov1983年提出的对冲量梯度下降算法的改进版本,其速度更快。其变化之处在于计算超前梯度更新冲量项,具体公式如下:

    0?wx_fmt=png

    既然参数要沿着0?wx_fmt=png更新,不妨计算未来位置0?wx_fmt=png的梯度,然后合并两项作为最终的更新项,其具体效果如图1所示,可以看到一定的加速效果。在TensorFlow中,NAG优化器为:tf.train.MomentumOptimizer(learning_rate=learning_rate,momentum=0.9, use_nesterov=True)


    0?wx_fmt=png

    1 NAG效果图


    03

    AdaGrad

    AdaGradDuchi2011年提出的一种学习速率自适应的梯度下降算法。在训练迭代过程,其学习速率是逐渐衰减的,经常更新的参数其学习速率衰减更快,这是一种自适应算法。其更新过程如下:

    0?wx_fmt=png

    其中是梯度平方的积累量,在进行参数更新时,学习速率要除以这个积累量的平方根,其中加上一个很小值是为了防止除0的出现。由于是该项逐渐增加的,那么学习速率是衰减的。考虑如图2所示的情况,目标函数在两个方向的坡度不一样,如果是原始的梯度下降算法,在接近坡底时收敛速度比较慢。而当采用AdaGrad,这种情况可以被改观。由于比较陡的方向梯度比较大,其学习速率将衰减得更快,这有利于参数沿着更接近坡底的方向移动,从而加速收敛。


    0?wx_fmt=png

    2 AdaGrad效果图


    前面说到AdaGrad其学习速率实际上是不断衰减的,这会导致一个很大的问题,就是训练后期学习速率很小,导致训练过早停止,因此在实际中AdaGrad一般不会被采用,下面的算法将改进这一致命缺陷。不过TensorFlow也提供了这一优化器:tf.train.AdagradOptimizer



    04

    RMSprop

    RMSpropHinton在他的课程上讲到的,其算是对Adagrad算法的改进,主要是解决学习速率过快衰减的问题。其实思路很简单,类似Momentum思想,引入一个超参数,在积累梯度平方项进行衰减:

    0?wx_fmt=png

    可以认为仅仅对距离时间较近的梯度进行积累,其中一般取值0.9,其实这样就是一个指数衰减的均值项,减少了出现的爆炸情况,因此有助于避免学习速率很快下降的问题。同时Hinton也建议学习速率设置为0.001RMSprop是属于一种比较好的优化算法了,在TensorFlow中当然有其身影:tf.train.RMSPropOptimizer(learning_rate=learning_rate,momentum=0.9, decay=0.9, epsilon=1e-10)

    不得不说点题外话,同时期还有一个Adadelta算法,其也是Adagrad算法的改进,而且改进思路和RMSprop很像,但是其背后是基于一次梯度近似代替二次梯度的思想,感兴趣的可以看看相应的论文,这里不再赘述。


    05

    Adam

    Adam全称Adaptive moment estimation,Kingma等在2015年提出的一种新的优化算法,其结合了MomentumRMSprop算法的思想。相比Momentum算法,其学习速率是自适应的,而相比RMSprop,其增加了冲量项。所以,Adam是两者的结合体:

    0?wx_fmt=png

    可以看到前两项和MomentumRMSprop是非常一致的,由于的初始值一般设置为0,在训练初期其可能较小,第三和第四项主要是为了放大它们。最后一项是参数更新。其中超参数的建议值是0?wx_fmt=pngAdm是性能非常好的算法,在TensorFlow其实现如下: tf.train.AdamOptimizer(learning_rate=0.001,beta1=0.9, beta2=0.999, epsilon=1e-08)





    学习速率

    前面也说过学习速率的问题,对于梯度下降算法,这应该是一个最重要的超参数。如果学习速率设置得非常大,那么训练可能不会收敛,就直接发散了;如果设置的比较小,虽然可以收敛,但是训练时间可能无法接受;如果设置的稍微高一些,训练速度会很快,但是当接近最优点会发生震荡,甚至无法稳定。不同学习速率的选择影响可能非常大,如图3所示。

    0?wx_fmt=png

    3 不同学习速率的训练效果




    理想的学习速率是:刚开始设置较大,有很快的收敛速度,然后慢慢衰减,保证稳定到达最优点。所以,前面的很多算法都是学习速率自适应的。除此之外,还可以手动实现这样一个自适应过程,如实现学习速率指数式衰减:

    0?wx_fmt=png

    TensorFlow中,你可以这样实现:

    initial_learning_rate = 0.1
    decay_steps = 10000
    decay_rate = 1/10
    global_step = tf.Variable(0, trainable=False)
    learning_rate = tf.train.exponential_decay(initial_learning_rate,                          
                               global_step, decay_steps, decay_rate)
    # decayed_learning_rate = learning_rate *
    #                decay_rate ^ (global_step / decay_steps)
    optimizer = tf.train.MomentumOptimizer(learning_rate, momentum=0.9)
    training_op = optimizer.minimize(loss, global_step=global_step)







    总结

    本文简单介绍了梯度下降算法的分类以及常用的改进算法,总结来看,优先选择学习速率自适应的算法如RMSpropAdam算法,大部分情况下其效果是较好的。还有一定要特别注意学习速率的问题。其实还有很多方面会影响梯度下降算法,如梯度的消失与爆炸,这也是要额外注意的。最后不得不说,梯度下降算法目前无法保证全局收敛还将是一个持续性的数学难题。







    参考文献

    1. Anoverview of gradient descent optimization algorithms: http://sebastianruder.com/optimizing-gradient-descent/.

    2. Hands-OnMachine Learning with Scikit-Learn and TensorFlow, Aurélien Géron, 2017.

    3. NAG:http://proceedings.mlr.press/v28/sutskever13.pdf.

    4. Adagrad:http://www.jmlr.org/papers/volume12/duchi11a/duchi11a.pdf.

    5. RMSprop:http://www.cs.toronto.edu/~tijmen/csc321/slides/lecture_slides_lec6.pdf.

    6. Adadelta:https://arxiv.org/pdf/1212.5701v1.pdf.

    7. Adam:https://arxiv.org/pdf/1412.6980.pdf.

    8. 不同的算法的效果可视化:https://imgur.com/a/Hqolp.






    欢迎大家加群在群中探讨

    欢迎留言或赞赏。









    阅 

    1. 客官,来嘛,谷歌小菜请你尝尝!

    2. 趣谈深度学习核心----激活函数

    3. 朴素贝叶斯实战篇之新浪新闻分类

    4. Object Detection R-CNN

    5. 史上最详细的XGBoost实战(上)




    扫描个人微信号,

    拉你进机器学习大牛群。

    福利满满,名额已不多…

    640.jpeg?



    80%的AI从业者已关注我们微信公众号

    0?wx_fmt=gif 0?wx_fmt=gif 0?wx_fmt=gif 0?wx_fmt=gif 0?wx_fmt=gif 0?wx_fmt=gif 0?wx_fmt=gif 0?wx_fmt=gif

    0?wx_fmt=gif 0?wx_fmt=gif 0?wx_fmt=gif 0?wx_fmt=gif 0?wx_fmt=gif 0?wx_fmt=gif 0?wx_fmt=gif 0?wx_fmt=gif




    展开全文
  • 梯度下降

    2019-08-04 19:31:51
    梯度下降1 、基本概念2、批量梯度下降(BGD)3、随机梯度下降(SGD)4、小批量梯度下降(MBGD) 1 、基本概念 谈到梯度,童鞋们在学高数时见过,就表示某一函数在该点处的方向导数沿着该方向取得最大值,即函数在该...

    1 、基本概念

    谈到梯度,童鞋们在学高数时见过,就表示某一函数在该点处的方向导数沿着该方向取得最大值,即函数在该点处沿着该方向(此梯度的方向)变化最快,变化率最大(为该梯度的模)。当然这是定义了。我们现在谈的梯度是酱紫的。
    见图1
    在这里插入图片描述
    现在想求theta让他尽快到达底端,也就是函数导数为0的位置。
    如何去做呢,现在我用三种梯度下降方法去做这件事。

    2、批量梯度下降(BGD)

    没有代码说jb啊,贴出代码。

    import numpy as np
    import matplotlib.pyplot as plt
    from sklearn.metrics import r2_score
    import pandas as pd
    import time
    
    
    pdData = pd.read_csv('random_data.txt', header=None, names=['X', 'y'])
    orig_data = pdData.values  # 将取到的数据转化为数组的形式
    cols = orig_data.shape[1]  # 得到列数的数值
    X = orig_data[:, 0:cols - 1]  # 取每一行的第一列到倒数第二列的数据
    y = orig_data[:, cols - 1:cols]  # 取每一行的最后一列的数据
    x_b = np.c_[np.ones((100, 1)), X]
    
    learning_rate = 0.1
    n_iterations = 10000
    m = len(X)
    
    theta = np.random.randn(2, 1)
    count = 0
    
    init_time = time.time()  # 初始化时间
    for iteration in range(n_iterations):
        count += 1
        # 2,接着求梯度gradient
        gradients = 1/m * x_b.T.dot(x_b.dot(theta)-y)
        # 3,应用公式调整theta值,theta_t + 1 = theta_t - grad * learning_rate
        theta = theta - learning_rate * gradients
    
    print("迭代的时间:", time.time() - init_time)  # 迭代的时间
    
    y_pred = x_b.dot(theta)
    # 解释方差得分 1 是完美预测
    print('Variance score: %.2f' % r2_score(y, y_pred))
    
    plt.scatter(X, y,  color='black')
    plt.plot(X, y_pred, color='blue', linewidth=3)
    plt.xlabel('x_test')
    plt.ylabel('y_pred')
    
    print("迭代的次数:", count)
    print("得到的权重参数:", theta)
    
    plt.show()
    

    编译结果:
    迭代的时间: 0.07683420181274414
    Variance score: 0.44
    迭代的次数: 10000
    得到的权重参数: [[3.92391528]
    [3.20786631]]
    在这里插入图片描述
    这里的迭代时间是用来对比三种梯度下降方法所需的时间,按道理说批量梯度下降的所需时间最长,但我在这次实验中竟然最短,尼玛,希望大神指点。

    3、随机梯度下降(SGD)

    import numpy as np
    import matplotlib.pyplot as plt
    from sklearn.metrics import r2_score
    import pandas as pd
    import time
    
    pdData = pd.read_csv('random_data.txt', header=None, names=['X', 'y'])
    orig_data = pdData.values  # 将取到的数据转化为数组的形式
    cols = orig_data.shape[1]  # 得到列数的数值
    X = orig_data[:, 0:cols - 1]  # 取每一行的第一列到倒数第二列的数据
    y = orig_data[:, cols - 1:cols]  # 取每一行的最后一列的数据
    x_b = np.c_[np.ones((100, 1)), X]
    
    learning_rate = 0.1
    n_iterations = 10000
    
    theta = np.random.randn(2, 1)
    count = 0
    
    init_time = time.time()
    for i in range(n_iterations):
        count += 1
        loss = x_b.dot(theta)-y
        m = np.random.randint(1, 100, 1)
        gradients = loss[m] * x_b[m]
        theta = theta - learning_rate * gradients.T
    
    print("迭代的时间:", time.time() - init_time)  # 迭代的时间
    y_pred = x_b.dot(theta)
    # 解释方差得分 1 是完美预测
    print('Variance score: %.2f' % r2_score(y, y_pred))
    
    plt.scatter(X, y,  color='black')
    plt.plot(X, y_pred, color='blue', linewidth=3)
    plt.xlabel('x_test')
    plt.ylabel('y_pred')
    
    print("迭代的次数:", count)
    print("得到的权重参数:", theta)
    
    plt.show()
    

    编译结果:
    迭代的时间: 0.1137397289276123
    Variance score: 0.33
    迭代的次数: 10000
    得到的权重参数: [[3.42439112]
    [3.3517127 ]]
    在这里插入图片描述

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

    import numpy as np
    import matplotlib.pyplot as plt
    from sklearn.metrics import r2_score
    import pandas as pd
    import random
    import time
    
    pdData = pd.read_csv('random_data.txt', header=None, names=['X', 'y'])
    orig_data = pdData.values  # 将取到的数据转化为数组的形式
    cols = orig_data.shape[1]  # 得到列数的数值
    X = orig_data[:, 0:cols - 1]  # 取每一行的第一列到倒数第二列的数据
    y = orig_data[:, cols - 1:cols]  # 取每一行的最后一列的数据
    x_b = np.c_[np.ones((100, 1)), X]
    
    learning_rate = 0.1
    n_iterations = 10000
    
    theta = np.random.randn(2, 1)
    count = 0
    
    init_time = time.time()  # 初始化时间
    for i in range(n_iterations):
        count += 1
        loss = x_b.dot(theta)-y
        m = random.randrange(1, 90)
        loss_l = list(loss)
        loss_l = loss_l[m:(m+10)]
        loss_s = np.array(loss_l)
        x_b_l = list(x_b)[m:(m+10)]
        x_b_s = np.array(x_b_l)
        gradients = 1/10*x_b_s.T.dot(loss_s)
        theta = theta - learning_rate * gradients
    
    print("迭代的时间:", time.time() - init_time)  # 迭代的时间
    
    y_pred = x_b.dot(theta)
    # 解释方差得分 1 是完美预测
    print('Variance score: %.2f' % r2_score(y, y_pred))
    
    plt.scatter(X, y,  color='black')
    plt.plot(X, y_pred, color='blue', linewidth=3)
    plt.xlabel('x_test')
    plt.ylabel('y_pred')
    
    print("迭代的次数:", count)
    print("得到的权重参数:", theta)
    
    plt.show()
    

    编译结果:
    迭代的时间: 0.4085395336151123
    Variance score: 0.43
    迭代的次数: 10000
    得到的权重参数: [[3.82729008]
    [3.22677617]]
    在这里插入图片描述
    当然只有好人才会在给出代码和附上数据集
    https://pan.baidu.com/s/1K1-vq7dJE2KFfxARMj7NnA

    展开全文
  • 梯度下降、随机梯度下降、小批量梯度下降、动量梯度下降、Nesterov加速梯度下降法前言梯度下降法(Gradient Descent / GD)单变量线性回归模型(Univariate Linear Regression)批梯度下降法(Batch Gradient ...

    前言

    本文通过使用单变量线性回归模型讲解一些常见的梯度下降算法。为了更好的作对比,我们对参数设置了不同的学习率

    梯度下降法(GD / Gradient Descent)

    梯度下降法(Gradient Descent)是一种常见的、用于寻找函数极小值的一阶迭代优化算法,又称为最速下降(Steepest Descent),它是求解无约束最优化问题的一种常用方法。以下是梯度下降的基本公式:

    θ:=θJ(θ)θ \theta := \theta - \frac{\partial J(\theta)}{\partial \theta}
    其中 J(θ)J(\theta) 是关于参数 θ\theta 的损失函数,η\eta学习率(正标量),也称为梯度下降的步长。由上述公式可知,梯度下降的想法是使得参数 θ\theta 向着负梯度方向做更新迭代。

    下面通过一个简单的例子来直观了解梯度下降的过程。假设 J(θ)J(\theta) 为关于 θ\theta 的一元二次函数,即 J(θ)=θ2J(\theta) = \theta^2。假设初始值为 (θ,J(θ))=(9,81)(\theta, J(\theta)) = (9,81)η=0.2\eta = 0.2。对于第一次迭代,求取梯度为:J(θ)θ=2θ=18\frac{\partial J(\theta)}{\partial \theta} = 2\theta = 18,更新θ:=θJ(θ)θ=90.218=5.4\theta := \theta - \frac{\partial J(\theta)}{\partial \theta} = 9 - 0.2*18 = 5.4。继续重复迭代步骤,最后函数将会趋于极值点x=0x = 0

    如下图所示,我们可以发现,随着梯度的不断减小,函数收敛越来越慢:

    在这里插入图片描述

    下面是该程序的matlab代码:

    % writen by: Weichen Gu,   date: 4/18th/2020 
    clc; clf; clear;
    xdata = linspace(-10,10,1000);                   % x range
    f = @(xdata)(xdata.^2);                         % Quadratic function - loss function
    
    ydata = f(xdata);
    plot(xdata,ydata,'c','linewidth',2);
    title('y = x^2 (learning rate = 0.2)');
    hold on;
    
    x = [9 f(9)];            % Initial point
    slope = inf;               % Slope
    LRate = 0.2;               % Learning rate
    slopeThresh = 0.0001;      % Slope threshold for iteration
    
    plot(x(1),x(2),'r*');
    
    while abs(slope) > slopeThresh
        [tmp,slope] = gradientDescent(x(1),f,LRate);
        x1 = [tmp f(tmp)];
        line([x(1),x1(1)],[x(2),x1(2)],'color','k','linestyle','--','linewidth',1);
        plot(x1(1),x1(2),'r*');
        legend('y = x^2');
        drawnow;
        x = x1;
    end
    hold off
    
    function [xOut,slope] = gradientDescent(xIn,f, eta)
        syms x;
        slope = double(subs(diff(f(x)),xIn));
        xOut = xIn- eta*(slope);
    end

    学习率决定了梯度下降的收敛速度,合适的学习率会使收敛速度得到一定的提高。我们应该避免过小或者过大的学习率:

    • 学习率过小会导致函数收敛速度非常慢,所需迭代次数多,难以收敛。
    • 学习率过大会导致梯度下降过程中出现震荡、不收敛甚至发散的情况。

    如下图所示:

    在这里插入图片描述
    对于学习率,一开始可以设置较大的步长,然后再慢慢减小步长来调整收敛速度,但是实际过程中,设置最优的学习率一般来说是比较困难的。

    同时我们应该知道,梯度下降是一种寻找函数极小值的方法,如下图,不同的初始点可能会获得不同的极小值:

    在这里插入图片描述

    单变量线性回归模型(Univariate Linear Regression)

    下面我们通过使用吴恩达老师课程中的单变量线性回归(Univariate Linear Regression)模型来讲解几种梯度下降策略。如下公式:
    hθ(x)=θ0x+θ1 h_{\theta}(x) = \theta_0 x+\theta_1

    它是一种简单的线性拟合模型,并且目标函数为凸函数(根据一阶导二阶导性质),所以对于梯度下降求得的极小值就是损失函数的最优解。下列公式为单变量线性回归模型的损失函数/目标函数
    J(θ0,θ1)=12mi=1m(hθ(xi)yi)2 J(\theta_0,\theta_1) = \frac{1}{2m}\sum_{i = 1}^m(h_{\theta}(x^i)-y^i)^2
    其中hθ(x(i))h_\theta(x^{(i)})是通过回归模型预测的输出。mm为样本个数。
    我们的目标是求出使得目标函数最小的参数值
    (θ^0,θ^1)=arg minθ0,θ1J(θ0,θ1) (\hat\theta_0,\hat\theta_1) = \argmin_{\theta_0,\theta_1}J(\theta_0,\theta_1)

    对损失函数进行梯度求解,可得到:

    J(θ0,θ1)θ0=1mi=1m(θ0+θ1xiyi) \frac{\partial J(\theta_0,\theta_1)}{\partial \theta_0} = \frac{1}{m}\sum_{i = 1}^m(\theta_0+\theta_1x^i -y^i) J(θ0,θ1)θ1=1mi=1m(θ0+θ1xiyi)xi \frac{\partial J(\theta_0,\theta_1)}{\partial \theta_1} = \frac{1}{m}\sum_{i = 1}^m(\theta_0+\theta_1x^i -y^i)x^i

    批梯度下降法(Batch GD / Batch Gradient Descent)

    批梯度下降法根据整个数据集求取损失函数的梯度,来更新参数θ\theta的值。公式如下:
    θ:=θη1mi=1mJ(θ,xi,yi)θ \theta := \theta - \eta\cdot\frac{1}{m}\sum_{i=1}^m\frac{\partial J(\theta,x^i,y^i)}{\partial \theta}
    优点:考虑到了全局数据,更新稳定,震荡小,每次更新都会朝着正确的方向。
    缺点:如果数据集比较大,会造成大量时间和空间开销

    下图显示了通过批梯度下降进行拟合的结果。根据图像可看到,我们的线性回归模型逐渐拟合到了一个不错的结果。
    在这里插入图片描述

    下面给出matlab的代码:

    % Writen by weichen GU, data 4/19th/2020
    clear, clf, clc; 
    
    data = linspace(-20,20,100);                    % x range
    col = length(data);                             % Obtain the number of x
    data = [data;0.5*data + wgn(1,100,1).*2+10];    % Generate dataset - y = 0.5 * x + wgn^2 + 10;
    X = [ones(1, col); data(1,:)]';                 % X ->[1;X];
    
    plot(data(1,:),data(2,:),'r.','MarkerSize',10); % Plot data
    title('Data fiting using Univariate Linear Regression');
    axis([-30,30,-10,30])
    hold on;
    
    theta =[0;0];           % Initialize parameters
    LRate = [0.1; 0.002]; % Learning rate
    thresh = 0.5;           % Threshold of loss for jumping iteration
    iteration = 40;        % The number of teration
    
    lineX = linspace(-30,30,100);
    [row, col] = size(data)                     % Obtain the size of dataset
    lineMy = [lineX;theta(1)*lineX+theta(2)];   % Fitting line
    hLine = plot(lineMy(1,:),lineMy(2,:),'c','linewidth',2);  % draw fitting line
    
    for iter = 1 : iteration
        delete(hLine)       % set(hLine,'visible','off')
        
        [thetaOut] = GD(X,data(2,:)',theta,LRate); % Gradient Descent algorithm
        theta = thetaOut;   % Update parameters(theta)
        
        loss = getLoss(X,data(2,:)',col,theta); % Obtain the loss 
        lineMy(2,:) = theta(2)*lineX+theta(1); % Fitting line
        hLine = plot(lineMy(1,:),lineMy(2,:),'c','linewidth',2); % draw fitting line
        
        drawnow()
        
        if(loss < thresh)
            break;
        end
    end
    
    hold off
    
    
    function [thetaOut] = GD(X,Y,theta,LRate)
        dataSize = length(X);               % Obtain the number of data 
        dx = 1/dataSize*(X'*(X*theta-Y));   % Obtain the gradient
        thetaOut = theta -LRate.*dx;         % gradient descent method
    end
    
    
    function [Z] = getLoss(X,Y, num,theta)
        Z= 1/(2*num)*sum((X*theta-Y).^2);
    end
    

    我们希望可以直观的看到批梯度下降的过程,以便和后续的一些梯度下降算法作比较,于是我们将其三维可视化出来,画出其拟合图(1)、三维损失图(2)、等高线图(3)以及迭代损失图(4)

    在这里插入图片描述

    根据上图可以看到,批梯度下降收敛稳定,震荡小。

    这里给出具体matlab实现代码:

    % Writen by weichen GU, data 4/19th/2020
    clear, clf, clc;
    data = linspace(-20,20,100);                    % x range
    col = length(data);                             % Obtain the number of x
    data = [data;0.5*data + wgn(1,100,1)+10];       % Generate dataset - y = 0.5 * x + wgn^2 + 10;
    X = [ones(1, col); data(1,:)]';                 % X ->[1;X];
    
    t1=-40:0.1:50;
    t2=-4:0.1:4;
    [meshX,meshY]=meshgrid(t1,t2);
    meshZ = getTotalCost(X, data(2,:)', col, meshX,meshY);
    
    theta =[-30;-4];        % Initialize parameters
    LRate = [0.1; 0.002];   % Learning rate
    thresh = 0.5;           % Threshold of loss for jumping iteration
    iteration = 50;         % The number of teration
    
    lineX = linspace(-30,30,100);
    [row, col] = size(data)                                     % Obtain the size of dataset
    lineMy = [lineX;theta(1)*lineX+theta(2)];                   % Fitting line
    hLine = plot(lineMy(1,:),lineMy(2,:),'c','linewidth',2);    % draw fitting line
    
    loss = getLoss(X,data(2,:)',col,theta);                     % Obtain current loss value
    
    subplot(2,2,1);
    plot(data(1,:),data(2,:),'r.','MarkerSize',10);
    title('Data fiting using Univariate LR');
    axis([-30,30,-10,30])
    xlabel('x');
    ylabel('y');
    hold on;
    
    % Draw 3d loss surfaces
    subplot(2,2,2)
    mesh(meshX,meshY,meshZ)
    xlabel('θ_0');
    ylabel('θ_1');
    title('3D surfaces for loss')
    hold on;
    scatter3(theta(1),theta(2),loss,'r*');
    
    % Draw loss contour figure
    subplot(2,2,3)
    contour(meshX,meshY,meshZ)
    xlabel('θ_0');
    ylabel('θ_1');
    title('Contour figure for loss')
    hold on;
    plot(theta(1),theta(2),'r*')
    
    % Draw loss with iteration
    subplot(2,2,4)
    hold on;
    title('Loss when using Batch GD');
    xlabel('iter');
    ylabel('loss');
    plot(0,loss,'b*');
    
    set(gca,'XLim',[0 iteration]);
    %set(gca,'YLim',[0 4000]);
    hold on;
    
    for iter = 1 : iteration
        delete(hLine) % set(hLine,'visible','off')
        
        [thetaOut] = GD(X,data(2,:)',theta,LRate); % Gradient Descent algorithm
        subplot(2,2,3);
        line([theta(1),thetaOut(1)],[theta(2),thetaOut(2)],'color','k')
    
        theta = thetaOut;
        loss = getLoss(X,data(2,:)',col,theta); % Obtain losw
        
        
        lineMy(2,:) = theta(2)*lineX+theta(1); % Fitting line
        subplot(2,2,1);
        hLine = plot(lineMy(1,:),lineMy(2,:),'c','linewidth',2); % draw fitting line
        %legend('training data','linear regression');
        
        subplot(2,2,2);
        scatter3(theta(1),theta(2),loss,'r*');
        
        subplot(2,2,3);
        plot(theta(1),theta(2),'r*')
        
        subplot(2,2,4)
        plot(iter,loss,'b*');
        
        drawnow();
        
        if(loss < thresh)
            break;
        end
    end
    
    hold off
    
    
    function [Z] = getTotalCost(X,Y, num,meshX,meshY);
        [row,col] = size(meshX);
        Z = zeros(row, col);
        for i = 1 : row
            theta = [meshX(i,:); meshY(i,:)];
            Z(i,:) =  1/(2*num)*sum((X*theta-repmat(Y,1,col)).^2);   
        end
    
    end
    
    function [Z] = getLoss(X,Y, num,theta)
        Z= 1/(2*num)*sum((X*theta-Y).^2);
    end
    
    function [thetaOut] = GD(X,Y,theta,eta)
        dataSize = length(X);                       % Obtain the number of data
        dx = 1/dataSize.*(X'*(X*theta-Y));          % Obtain the gradient of Loss function
        thetaOut = theta -eta.*dx;                  % Update parameters(theta)
    end
    

    随机梯度下降法(SGD / Stochastic Gradient Descent)

    因为批梯度下降所需要的时间空间成本大,我们考虑随机抽取一个样本来获取梯度,更新参数 θ\theta。其公式如下:
    θ:=θηJ(θ,xi,yi)θ \theta := \theta - \eta\cdot\frac{\partial J(\theta,x^i,y^i)}{\partial \theta} 步骤如下:

    1. 随机打乱数据集。
    2. 对于每个样本点,依次迭代更新参数θ\theta
    3. 重复以上步骤直至损失足够小或到达迭代阈值

    优点:训练速度快,每次迭代只需要一个样本,相对于批梯度下降,总时间、空间开销小。
    缺点:噪声大导致高方差。导致每次迭代并不一定朝着最优解收敛,震荡大。

    下图直观显示了随机梯度下降的迭代过程:
    在这里插入图片描述

    下面给出随机梯度下降的matlab代码,因为它是小批量梯度下降的特殊情况(batchSize = 1),所以我将小批量梯度下降的代码放在本章节,并设置batchSize = 1。

    % Writen by weichen GU, data 4/19th/2020
    clear, clf, clc;
    data = linspace(-20,20,100);                    % x range
    col = length(data);                             % Obtain the number of x
    data = [data;0.5*data + wgn(1,100,1)+10];       % Generate dataset - y = 0.5 * x + wgn^2 + 10;
    X = [ones(1, col); data(1,:)]';                 % X ->[1;X];
    
    t1=-40:0.1:50;
    t2=-4:0.1:4;
    [meshX,meshY]=meshgrid(t1,t2);
    meshZ = getTotalCost(X, data(2,:)', col, meshX,meshY);
    
    theta =[-30;-4];        % Initialize parameters
    LRate = [0.1; 0.002]  % Learning rate
    thresh = 0.5;           % Threshold of loss for jumping iteration
    iteration = 100;        % The number of teration
    
    lineX = linspace(-30,30,100);
    [row, col] = size(data)                                     % Obtain the size of dataset
    lineMy = [lineX;theta(1)*lineX+theta(2)];                   % Fitting line
    hLine = plot(lineMy(1,:),lineMy(2,:),'c','linewidth',2);    % draw fitting line
    
    loss = getLoss(X,data(2,:)',col,theta);                     % Obtain current loss value
    
    subplot(2,2,1);
    plot(data(1,:),data(2,:),'r.','MarkerSize',10);
    title('Data fiting using Univariate LR');
    axis([-30,30,-10,30])
    xlabel('x');
    ylabel('y');
    hold on;
    
    % Draw 3d loss surfaces
    subplot(2,2,2)
    mesh(meshX,meshY,meshZ)
    xlabel('θ_0');
    ylabel('θ_1');
    title('3D surfaces for loss')
    hold on;
    scatter3(theta(1),theta(2),loss,'r*');
    
    % Draw loss contour figure
    subplot(2,2,3)
    contour(meshX,meshY,meshZ)
    xlabel('θ_0');
    ylabel('θ_1');
    title('Contour figure for loss')
    hold on;
    plot(theta(1),theta(2),'r*')
    
    % Draw loss with iteration
    subplot(2,2,4)
    hold on;
    title('Loss when using SGD');
    xlabel('iter');
    ylabel('loss');
    plot(0,loss,'b*');
    
    set(gca,'XLim',[0 iteration]);
    hold on;
    
    batchSize = 1;
    for iter = 1 : iteration
        delete(hLine) % set(hLine,'visible','off')
    
        
        %[thetaOut] = GD(X,data(2,:)',theta,LRate); % Gradient Descent algorithm
        [thetaOut] = MBGD(X,data(2,:)',theta,LRate,batchSize);
        subplot(2,2,3);
        line([theta(1),thetaOut(1)],[theta(2),thetaOut(2)],'color','k')
    
        theta = thetaOut;
        loss = getLoss(X,data(2,:)',col,theta); % Obtain losw
        
        
        lineMy(2,:) = theta(2)*lineX+theta(1); % Fitting line
        subplot(2,2,1);
        hLine = plot(lineMy(1,:),lineMy(2,:),'c','linewidth',2); % draw fitting line
        %legend('training data','linear regression');
        
        subplot(2,2,2);
        scatter3(theta(1),theta(2),loss,'r*');
        
        subplot(2,2,3);
        plot(theta(1),theta(2),'r*')
        
        
        subplot(2,2,4)
        plot(iter,loss,'b*');
        
        drawnow();
        
        if(loss < thresh)
            break;
        end
    end
    
    hold off
    
    
    function [Z] = getTotalCost(X,Y, num,meshX,meshY);
        [row,col] = size(meshX);
        Z = zeros(row, col);
        for i = 1 : row
            theta = [meshX(i,:); meshY(i,:)];
            Z(i,:) =  1/(2*num)*sum((X*theta-repmat(Y,1,col)).^2);   
        end
    
    end
    
    
    function [Z] = getLoss(X,Y, num,theta)
        Z= 1/(2*num)*sum((X*theta-Y).^2);
    end
    
    function [thetaOut] = GD(X,Y,theta,eta)
        dataSize = length(X);                       % Obtain the number of data
        dx = 1/dataSize.*(X'*(X*theta-Y));          % Obtain the gradient of Loss function
        thetaOut = theta -eta.*dx;                  % Update parameters(theta)
    end
    
    % @ Depscription: 
    %       Mini-batch Gradient Descent (MBGD)
    %       Stochastic Gradient Descent(batchSize = 1) (SGD)
    % @ param:
    %       X - [1 X_] X_ is actual X; Y - actual Y
    %       theta - theta for univariate linear regression y_pred = theta_0 + theta1*x
    %       eta - learning rate;
    %
    function [thetaOut] = MBGD(X,Y,theta, eta,batchSize) 
        dataSize = length(X);           % obtain the number of data 
        k = fix(dataSize/batchSize);    % obtain the number of batch which has absolutely same size: k = batchNum-1;    
        batchIdx = randperm(dataSize);  % randomly sort for every epoch for achiving sample diversity
        
        batchIdx1 = reshape(batchIdx(1:k*batchSize),k,batchSize);   % batches which has absolutely same size
        batchIdx2 = batchIdx(k*batchSize+1:end);                    % ramained batch
        
        for i = 1 : k
            thetaOut = GD(X(batchIdx1(i,:),:),Y(batchIdx1(i,:)),theta,eta);
        end
        if(~isempty(batchIdx2))
            thetaOut = GD(X(batchIdx2,:),Y(batchIdx2),thetaOut,eta);
        end
    end
    

    小批量梯度下降(Mini Batch GD / Mini-batch Gradient Descent)

    随机梯度下降收敛速度快,但是波动较大,在最优解处出现波动很难判断其是否收敛到一个合理的值。而批梯度下降稳定但是时空开销很大,针对于这种情况,我们引入小批量梯度下降对二者进行折衷,在每轮迭代过程中使用n个样本来训练参数:
    θ:=θη1ni=1nJ(θ,xi,yi)θ \theta := \theta - \eta\cdot\frac{1}{n}\sum_{i=1}^n\frac{\partial J(\theta,x^i,y^i)}{\partial \theta} 步骤如下:

    1. 随机打乱数据集。
    2. 将数据集分为mn\frac{m}{n}个集合,如果有余,将剩余样本单独作为一个集合。
    3. 依次对于这些集合做批梯度下降,更新参数θ\theta
    4. 重复上述步骤,直至损失足够小或达到迭代阈值

    下图显示了小批量梯度下降的迭代过程,其中batchSize = 32。我们可以看到,小批量折衷了批梯度下降和随机梯度下降的特点,做到了相对来说收敛快、较稳定的结果。

    在这里插入图片描述

    这里附上小批量梯度下降的相关代码:

    % Writen by weichen GU, data 4/19th/2020
    clear, clf, clc;
    data = linspace(-20,20,100);                    % x range
    col = length(data);                             % Obtain the number of x
    data = [data;0.5*data + wgn(1,100,1)+10];       % Generate dataset - y = 0.5 * x + wgn^2 + 10;
    X = [ones(1, col); data(1,:)]';                 % X ->[1;X];
    
    t1=-40:0.1:50;
    t2=-4:0.1:4;
    [meshX,meshY]=meshgrid(t1,t2);
    meshZ = getTotalCost(X, data(2,:)', col, meshX,meshY);
    
    theta =[-30;-4];        % Initialize parameters
    LRate = [0.1; 0.002]  % Learning rate
    thresh = 0.5;           % Threshold of loss for jumping iteration
    iteration = 50;        % The number of teration
    
    lineX = linspace(-30,30,100);
    [row, col] = size(data)                                     % Obtain the size of dataset
    lineMy = [lineX;theta(1)*lineX+theta(2)];                   % Fitting line
    hLine = plot(lineMy(1,:),lineMy(2,:),'c','linewidth',2);    % draw fitting line
    
    loss = getLoss(X,data(2,:)',col,theta);                     % Obtain current loss value
    
    subplot(2,2,1);
    plot(data(1,:),data(2,:),'r.','MarkerSize',10);
    title('Data fiting using Univariate LR');
    axis([-30,30,-10,30])
    xlabel('x');
    ylabel('y');
    hold on;
    
    % Draw 3d loss surfaces
    subplot(2,2,2)
    mesh(meshX,meshY,meshZ)
    xlabel('θ_0');
    ylabel('θ_1');
    title('3D surfaces for loss')
    hold on;
    scatter3(theta(1),theta(2),loss,'r*');
    
    % Draw loss contour figure
    subplot(2,2,3)
    contour(meshX,meshY,meshZ)
    xlabel('θ_0');
    ylabel('θ_1');
    title('Contour figure for loss')
    hold on;
    plot(theta(1),theta(2),'r*')
    
    % Draw loss with iteration
    subplot(2,2,4)
    hold on;
    title('Loss when using Mini-Batch GD');
    xlabel('iter');
    ylabel('loss');
    plot(0,loss,'b*');
    
    set(gca,'XLim',[0 iteration]);
    %set(gca,'YLim',[0 4000]);
    hold on;
    
    batchSize = 32;
    for iter = 1 : iteration
        delete(hLine) % set(hLine,'visible','off')
    
        
        %[thetaOut] = GD(X,data(2,:)',theta,LRate); % Gradient Descent algorithm
        [thetaOut] = MBGD(X,data(2,:)',theta,LRate,batchSize);
        subplot(2,2,3);
        line([theta(1),thetaOut(1)],[theta(2),thetaOut(2)],'color','k')
    
        theta = thetaOut;
        loss = getLoss(X,data(2,:)',col,theta); % Obtain losw
        
        
        lineMy(2,:) = theta(2)*lineX+theta(1); % Fitting line
        subplot(2,2,1);
        hLine = plot(lineMy(1,:),lineMy(2,:),'c','linewidth',2); % draw fitting line
        %legend('training data','linear regression');
        
        subplot(2,2,2);
        scatter3(theta(1),theta(2),loss,'r*');
        
        subplot(2,2,3);
        plot(theta(1),theta(2),'r*')
        
        
        subplot(2,2,4)
        plot(iter,loss,'b*');
        
        drawnow();
        
        if(loss < thresh)
            break;
        end
    end
    
    hold off
    
    
    function [Z] = getTotalCost(X,Y, num,meshX,meshY);
        [row,col] = size(meshX);
        Z = zeros(row, col);
        for i = 1 : row
            theta = [meshX(i,:); meshY(i,:)];
            Z(i,:) =  1/(2*num)*sum((X*theta-repmat(Y,1,col)).^2);   
        end
    
    end
    
    
    function [Z] = getLoss(X,Y, num,theta)
        Z= 1/(2*num)*sum((X*theta-Y).^2);
    end
    
    function [thetaOut] = GD(X,Y,theta,eta)
        dataSize = length(X);                       % Obtain the number of data
        dx = 1/dataSize.*(X'*(X*theta-Y));          % Obtain the gradient of Loss function
        thetaOut = theta -eta.*dx;                  % Update parameters(theta)
    end
    
    % @ Depscription: 
    %       Mini-batch Gradient Descent (MBGD)
    %       Stochastic Gradient Descent(batchSize = 1) (SGD)
    % @ param:
    %       X - [1 X_] X_ is actual X; Y - actual Y
    %       theta - theta for univariate linear regression y_pred = theta_0 + theta1*x
    %       eta - learning rate;
    %
    function [thetaOut] = MBGD(X,Y,theta, eta,batchSize) 
        dataSize = length(X);           % obtain the number of data 
        k = fix(dataSize/batchSize);    % obtain the number of batch which has absolutely same size: k = batchNum-1;    
        batchIdx = randperm(dataSize);  % randomly sort for every epoch for achiving sample diversity
        
        batchIdx1 = reshape(batchIdx(1:k*batchSize),k,batchSize);   % batches which has absolutely same size
        batchIdx2 = batchIdx(k*batchSize+1:end);                    % ramained batch
        
        for i = 1 : k
            thetaOut = GD(X(batchIdx1(i,:),:),Y(batchIdx1(i,:)),theta,eta);
        end
        if(~isempty(batchIdx2))
            thetaOut = GD(X(batchIdx2,:),Y(batchIdx2),thetaOut,eta);
        end
    end
    

    动量梯度下降(Momentum / Gradient Descent with Momentum)

    动量梯度下降通过指数加权平均(Exponentially weighted moving averages)策略,使用之前梯度信息修正当前梯度,来加速参数学习。这里我们令梯度项
    1mi=1mJ(θ,xi,yi)θ=θJ(θ) \frac{1}{m}\sum_{i=1}^m\frac{\partial J(\theta,x^i,y^i)}{\partial \theta} = \nabla_\theta J(\theta) 则梯度下降可以简化表示为
    θ:=θηθJ(θ) \theta := \theta - \eta\cdot\nabla_\theta J(\theta)
    对于动量梯度下降,初始化动量项m=0m = 0,更新迭代公式如下
    m:=γm+ηθJ(θ) m := \gamma\cdot m + \eta\cdot\nabla_\theta J(\theta) θ:=θm \theta :=\theta - m
    其中mm为动量梯度下降的动量项,且初始化为0;γ\gamma是关于动量项的超参数一般取小于等于0.9。我们可以发现,越是远离当前点的梯度信息,对于当前梯度的贡献越小。

    优点:通过过去梯度信息来优化下降速度,如果当前梯度与之前梯度方向一致时候,收敛速度得到加强,反之则减弱。换句话说,加快收敛同时减小震荡,分别对应图中 θ0\theta_0θ1\theta_1 方向。
    缺点:可能在下坡过程中累计动量太大,冲过极小值点。

    下图直观显示动量梯度下降迭代过程。
    在这里插入图片描述

    这里附上动量梯度下降的相关代码:

    % Writen by weichen GU, data 4/19th/2020
    clear, clf, clc;
    data = linspace(-20,20,100);                    % x range
    col = length(data);                             % Obtain the number of x
    data = [data;0.5*data + wgn(1,100,1)+10];       % Generate dataset - y = 0.5 * x + wgn^2 + 10;
    X = [ones(1, col); data(1,:)]';                 % X ->[1;X];
    
    t1=-40:0.1:50;
    t2=-4:0.1:4;
    [meshX,meshY]=meshgrid(t1,t2);
    meshZ = getTotalCost(X, data(2,:)', col, meshX,meshY);
    
    theta =[-30;-4];        % Initialize parameters
    LRate = [0.1; 0.002]  % Learning rate
    thresh = 0.5;           % Threshold of loss for jumping iteration
    iteration = 50;        % The number of teration
    
    lineX = linspace(-30,30,100);
    [row, col] = size(data)                                     % Obtain the size of dataset
    lineMy = [lineX;theta(1)*lineX+theta(2)];                   % Fitting line
    hLine = plot(lineMy(1,:),lineMy(2,:),'c','linewidth',2);    % draw fitting line
    
    loss = getLoss(X,data(2,:)',col,theta);                     % Obtain current loss value
    
    subplot(2,2,1);
    plot(data(1,:),data(2,:),'r.','MarkerSize',10);
    title('Data fiting using Univariate LR');
    axis([-30,30,-10,30])
    xlabel('x');
    ylabel('y');
    hold on;
    
    % Draw 3d loss surfaces
    subplot(2,2,2)
    mesh(meshX,meshY,meshZ)
    xlabel('θ_0');
    ylabel('θ_1');
    title('3D surfaces for loss')
    hold on;
    scatter3(theta(1),theta(2),loss,'r*');
    
    % Draw loss contour figure
    subplot(2,2,3)
    contour(meshX,meshY,meshZ)
    xlabel('θ_0');
    ylabel('θ_1');
    title('Contour figure for loss')
    hold on;
    plot(theta(1),theta(2),'r*')
    
    % Draw loss with iteration
    subplot(2,2,4)
    hold on;
    title('Loss when using Momentum GD');
    xlabel('iter');
    ylabel('loss');
    plot(0,loss,'b*');
    
    set(gca,'XLim',[0 iteration]);
    
    hold on;
    
    batchSize = 32;
    grad = 0; gamma = 0.5;
    
    for iter = 1 : iteration
        delete(hLine) % set(hLine,'visible','off')
    
        
        %[thetaOut] = GD(X,data(2,:)',theta,LRate); % Gradient Descent algorithm
        %[thetaOut] = MBGD(X,data(2,:)',theta,LRate,20);
        [thetaOut,grad] = MBGDM(X,data(2,:)',theta,LRate,batchSize,grad,gamma);
        subplot(2,2,3);
        line([theta(1),thetaOut(1)],[theta(2),thetaOut(2)],'color','k')
    
        theta = thetaOut;
        loss = getLoss(X,data(2,:)',col,theta); % Obtain losw
        
        
        lineMy(2,:) = theta(2)*lineX+theta(1); % Fitting line
        subplot(2,2,1);
        hLine = plot(lineMy(1,:),lineMy(2,:),'c','linewidth',2); % draw fitting line
        %legend('training data','linear regression');
        
        subplot(2,2,2);
        scatter3(theta(1),theta(2),loss,'r*');
        
        subplot(2,2,3);
        plot(theta(1),theta(2),'r*')
        
        
        subplot(2,2,4)
        plot(iter,loss,'b*');
    
        drawnow();
        
        if(loss < thresh)
            break;
        end
    end
    
    hold off
    
    
    function [Z] = getTotalCost(X,Y, num,meshX,meshY);
        [row,col] = size(meshX);
        Z = zeros(row, col);
        for i = 1 : row
            theta = [meshX(i,:); meshY(i,:)];
            Z(i,:) =  1/(2*num)*sum((X*theta-repmat(Y,1,col)).^2);   
        end
    
    end
    
    
    function [Z] = getLoss(X,Y, num,theta)
        Z= 1/(2*num)*sum((X*theta-Y).^2);
    end
    
    function [thetaOut] = GD(X,Y,theta,eta)
        dataSize = length(X);                       % Obtain the number of data
        dx = 1/dataSize.*(X'*(X*theta-Y));          % Obtain the gradient of Loss function
        thetaOut = theta -eta.*dx;                  % Update parameters(theta)
    end
    % Gradient Descent with Momentum
    function [thetaOut, momentum] = GDM(X,Y,theta,eta,momentum,gamma)
        dataSize = length(X);                       % Obtain the number of data
        dx = 1/dataSize.*(X'*(X*theta-Y));          % Obtain the gradient of Loss function
        momentum = gamma*momentum +eta.*dx;         % Obtain the momentum of gradient
        thetaOut = theta - momentum;                % Update parameters(theta)
    end
    
    % @ Depscription: 
    %       Mini-batch Gradient Descent (MBGD)
    %       Stochastic Gradient Descent(batchSize = 1) (SGD)
    % @ param:
    %       X - [1 X_] X_ is actual X; Y - actual Y
    %       theta - theta for univariate linear regression y_pred = theta_0 + theta1*x
    %       eta - learning rate;
    %
    function [thetaOut] = MBGD(X,Y,theta, eta,batchSize) 
        dataSize = length(X);           % obtain the number of data 
        k = fix(dataSize/batchSize);    % obtain the number of batch which has absolutely same size: k = batchNum-1;    
        batchIdx = randperm(dataSize);  % randomly sort for every epoch for achiving sample diversity
        
        batchIdx1 = reshape(batchIdx(1:k*batchSize),k,batchSize);   % batches which has absolutely same size
        batchIdx2 = batchIdx(k*batchSize+1:end);                    % ramained batch
        
        for i = 1 : k
            thetaOut = GD(X(batchIdx1(i,:),:),Y(batchIdx1(i,:)),theta,eta);
        end
        if(~isempty(batchIdx2))
            thetaOut = GD(X(batchIdx2,:),Y(batchIdx2),thetaOut,eta);
        end
    end
    
    function [thetaOut,grad] = MBGDM(X,Y,theta, eta,batchSize,grad,gamma) 
        dataSize = length(X);           % obtain the number of data 
        k = fix(dataSize/batchSize);    % obtain the number of batch which has absolutely same size: k = batchNum-1;    
        batchIdx = randperm(dataSize);  % randomly sort for every epoch for achiving sample diversity
        
        batchIdx1 = reshape(batchIdx(1:k*batchSize),k,batchSize);   % batches which has absolutely same size
        batchIdx2 = batchIdx(k*batchSize+1:end);                    % ramained batch
        
        for i = 1 : k
            [thetaOut,grad] = GDM(X(batchIdx1(i,:),:),Y(batchIdx1(i,:)),theta,eta,grad,gamma);
            
        end
        if(~isempty(batchIdx2))
            [thetaOut,grad] = GDM(X(batchIdx2,:),Y(batchIdx2),thetaOut,eta,grad,gamma);
        end
    end
    
    

    Nesterov加速梯度下降法(NAG / Nesterov Accelerated Gradient)

    Nesterov加速梯度下降相比于动量梯度下降的区别是,通过使用未来梯度来更新动量。即将下一次的预测梯度θJ(θηm)\nabla_\theta J(\theta-\eta\cdot m)考虑进来。其更新公式如下:
    m:=γm+ηθJ(θγm) m :=\gamma\cdot m+\eta\cdot\nabla_\theta J(\theta-\gamma\cdot m) θ:=θm \theta := \theta - m
    对于公式理解如下图所示,

    1. 对于起始点应用动量梯度下降,首先求得在该点处的带权梯度η1\eta\cdot\nabla_1,通过与之前动量γm\gamma\cdot m矢量加权,求得下一次的θ\theta位置。
    2. 对于起始点应用Nesterov加速梯度下降,首先通过先前动量求得θ\theta的预测位置,再加上预测位置的带权梯度γm\gamma\cdot m

    在这里插入图片描述
    优点

    1. 相对于动量梯度下降法,因为NAG考虑到了未来预测梯度,收敛速度更快(如上图)。
    2. 当更新幅度很大时,NAG可以抑制震荡。例如起始点在最优点的左侧γm\gamma m对应的值在最优点的右侧,对于动量梯度而言,叠加η1\eta\nabla_1使得迭代后的点更加远离最优点→→。而NAG首先跳到γm\gamma m对应的值,计算梯度为正,再叠加反方向的η2\eta\nabla_2,从而达到抑制震荡的目的。

    下图直观显示了Nesterov加速梯度下降的迭代过程:

    在这里插入图片描述

    下面是Nesterov加速梯度下降的相关代码:

    
    % Writen by weichen GU, data 4/19th/2020
    clear, clf, clc;
    data = linspace(-20,20,100);                    % x range
    col = length(data);                             % Obtain the number of x
    data = [data;0.5*data + wgn(1,100,1)+10];       % Generate dataset - y = 0.5 * x + wgn^2 + 10;
    X = [ones(1, col); data(1,:)]';                 % X ->[1;X];
    
    t1=-40:0.1:50;
    t2=-4:0.1:4;
    [meshX,meshY]=meshgrid(t1,t2);
    meshZ = getTotalCost(X, data(2,:)', col, meshX,meshY);
    
    theta =[-30;-4];        % Initialize parameters
    LRate = [0.1; 0.002]  % Learning rate
    thresh = 0.5;           % Threshold of loss for jumping iteration
    iteration = 50;        % The number of teration
    
    lineX = linspace(-30,30,100);
    [row, col] = size(data)                                     % Obtain the size of dataset
    lineMy = [lineX;theta(1)*lineX+theta(2)];                   % Fitting line
    hLine = plot(lineMy(1,:),lineMy(2,:),'c','linewidth',2);    % draw fitting line
    
    loss = getLoss(X,data(2,:)',col,theta);                     % Obtain current loss value
    
    subplot(2,2,1);
    plot(data(1,:),data(2,:),'r.','MarkerSize',10);
    title('Data fiting using Univariate LR');
    axis([-30,30,-10,30])
    xlabel('x');
    ylabel('y');
    hold on;
    
    % Draw 3d loss surfaces
    subplot(2,2,2)
    mesh(meshX,meshY,meshZ)
    xlabel('θ_0');
    ylabel('θ_1');
    title('3D surfaces for loss')
    hold on;
    scatter3(theta(1),theta(2),loss,'r*');
    
    % Draw loss contour figure
    subplot(2,2,3)
    contour(meshX,meshY,meshZ)
    xlabel('θ_0');
    ylabel('θ_1');
    title('Contour figure for loss')
    hold on;
    plot(theta(1),theta(2),'r*')
    
    % Draw loss with iteration
    subplot(2,2,4)
    hold on;
    title('Loss when using NAG');
    xlabel('iter');
    ylabel('loss');
    plot(0,loss,'b*');
    
    set(gca,'XLim',[0 iteration]);
    
    hold on;
    
    batchSize = 32;
    grad = 0; gamma = 0.5;
    
    for iter = 1 : iteration
        delete(hLine) % set(hLine,'visible','off')
    
        
        %[thetaOut] = GD(X,data(2,:)',theta,LRate); % Gradient Descent algorithm
        %[thetaOut] = MBGD(X,data(2,:)',theta,LRate,20);
        [thetaOut,grad] = MBGDM(X,data(2,:)',theta,LRate,batchSize,grad,gamma);
        subplot(2,2,3);
        line([theta(1),thetaOut(1)],[theta(2),thetaOut(2)],'color','k')
    
        theta = thetaOut;
        loss = getLoss(X,data(2,:)',col,theta); % Obtain losw
        
        
        lineMy(2,:) = theta(2)*lineX+theta(1); % Fitting line
        subplot(2,2,1);
        hLine = plot(lineMy(1,:),lineMy(2,:),'c','linewidth',2); % draw fitting line
        %legend('training data','linear regression');
        
        subplot(2,2,2);
        scatter3(theta(1),theta(2),loss,'r*');
        
        subplot(2,2,3);
        plot(theta(1),theta(2),'r*')
        
        
        subplot(2,2,4)
        plot(iter,loss,'b*');
    
        drawnow();
        
        if(loss < thresh)
            break;
        end
    end
    
    hold off
    
    
    function [Z] = getTotalCost(X,Y, num,meshX,meshY);
        [row,col] = size(meshX);
        Z = zeros(row, col);
        for i = 1 : row
            theta = [meshX(i,:); meshY(i,:)];
            Z(i,:) =  1/(2*num)*sum((X*theta-repmat(Y,1,col)).^2);   
        end
    
    end
    
    
    function [Z] = getLoss(X,Y, num,theta)
        Z= 1/(2*num)*sum((X*theta-Y).^2);
    end
    
    function [thetaOut] = GD(X,Y,theta,eta)
        dataSize = length(X);                       % Obtain the number of data
        dx = 1/dataSize.*(X'*(X*theta-Y));          % Obtain the gradient of Loss function
        thetaOut = theta -eta.*dx;                  % Update parameters(theta)
    end
    % Gradient Descent with Momentum
    function [thetaOut, momentum] = GDM(X,Y,theta,eta,momentum,gamma)
        dataSize = length(X);                       % Obtain the number of data
        dx = 1/dataSize.*(X'*(X*theta-Y));          % Obtain the gradient of Loss function
        momentum = gamma*momentum +eta.*dx;         % Obtain the momentum of gradient
        thetaOut = theta - momentum;                % Update parameters(theta)
    end
    
    % @ Depscription: 
    %       Mini-batch Gradient Descent (MBGD)
    %       Stochastic Gradient Descent(batchSize = 1) (SGD)
    % @ param:
    %       X - [1 X_] X_ is actual X; Y - actual Y
    %       theta - theta for univariate linear regression y_pred = theta_0 + theta1*x
    %       eta - learning rate;
    %
    function [thetaOut] = MBGD(X,Y,theta, eta,batchSize) 
        dataSize = length(X);           % obtain the number of data 
        k = fix(dataSize/batchSize);    % obtain the number of batch which has absolutely same size: k = batchNum-1;    
        batchIdx = randperm(dataSize);  % randomly sort for every epoch for achiving sample diversity
        
        batchIdx1 = reshape(batchIdx(1:k*batchSize),k,batchSize);   % batches which has absolutely same size
        batchIdx2 = batchIdx(k*batchSize+1:end);                    % ramained batch
        
        for i = 1 : k
            thetaOut = GD(X(batchIdx1(i,:),:),Y(batchIdx1(i,:)),theta,eta);
        end
        if(~isempty(batchIdx2))
            thetaOut = GD(X(batchIdx2,:),Y(batchIdx2),thetaOut,eta);
        end
    end
    
    % Nesterov Accelerated Gradient (NAG)
    function [thetaOut, momentum] = NAG(X,Y,theta,eta,momentum,gamma)
        dataSize = length(X);                                   % Obtain the number of data
        dx = 1/dataSize.*(X'*(X*(theta- gamma*momentum)-Y));    % Obtain the gradient of Loss function
        momentum = gamma*momentum +eta.*dx;                     % Obtain the momentum of gradient
        thetaOut = theta - momentum;                            % Update parameters(theta)
    end
    
    function [thetaOut,grad] = MBGDM(X,Y,theta, eta,batchSize,grad,gamma)
        dataSize = length(X);           % obtain the number of data 
        k = fix(dataSize/batchSize);    % obtain the number of batch which has absolutely same size: k = batchNum-1;    
        batchIdx = randperm(dataSize);  % randomly sort for every epoch for achiving sample diversity
        
        batchIdx1 = reshape(batchIdx(1:k*batchSize),k,batchSize);   % batches which has absolutely same size
        batchIdx2 = batchIdx(k*batchSize+1:end);                    % ramained batch
        
        for i = 1 : k
            %[thetaOut,grad] = GDM(X(batchIdx1(i,:),:),Y(batchIdx1(i,:)),theta,eta,grad,gamma);
            [thetaOut,grad] = NAG(X(batchIdx1(i,:),:),Y(batchIdx1(i,:)),theta,eta,grad,gamma);
        end
        if(~isempty(batchIdx2))
            %[thetaOut,grad] = GDM(X(batchIdx2,:),Y(batchIdx2),thetaOut,eta,grad,gamma);
            [thetaOut,grad] = NAG(X(batchIdx2,:),Y(batchIdx2),thetaOut,eta,grad,gamma);
        end
        
    end
    

    我们将θ1\theta_1对应的学习率η\eta升高到0.005后,得到以下另一组数据方便对比。η=[0.1,0.005]

    批梯度下降随机梯度下降的迭代过程:
    在这里插入图片描述 在这里插入图片描述
    小批量梯度下降动量梯度下降的迭代过程:
    在这里插入图片描述 在这里插入图片描述
    Nesterov加速梯度下降的迭代过程:
    在这里插入图片描述

    后语

    下一篇我们将介绍几种常见的学习率自适应梯度下降算法:AdaGrad、RMSProp、AdaDelta、Adam和Nadam。

    展开全文
  • 要使用梯度下降法找到一个函数的局部极小值,必须向函数上当前点对应梯度(或者是近似梯度)的反方向的规定步长距离点进行迭代搜索。如果相反地向梯度正方向迭代进行搜索,则会接近函数的局部极大值点;
  • 在机器学习领域中,梯度下降的方式有三种,分别是:批量梯度下降法BGD、随机梯度下降法SGD、小批量梯度下降法MBGD,并且都有不同的优缺点。 下面我们以线性回归算法为例子来对三种梯度下降法进行比较。 1. 线性...
  • 梯度下降公式 损失函数公式 梯度下降(Gradient Descent),一次更新θ,使用训练样本中所有样本 随机梯度下降(Stochastic Gradient Descent),一次更新θ,使用训练样本中一个数据 批量梯度下降(Batch ...
  • 梯度下降与随机梯度下降概念及推导过程

    万次阅读 多人点赞 2018-11-03 14:43:52
    同这一章的梯度下降部分加起来,才是我们要讲的如何求解多元线性回归.如果写在一章中,内容过长,担心有的同学会看不完,所以拆分成两章.[坏笑] 上一章中有提到利用解析解求解多元线性回归,虽然看起来很方便,但是在...
  • 梯度下降 Gradient Descent 简介 ( 梯度下降过程 | 梯度下降方向 ) II . 梯度下降 示例说明 ( 单个参数 ) III . 梯度下降 示例说明 ( 多个参数 ) IV . 梯度下降 总结 ( 定义损失函数 | 损失函数求导 ) V . 梯度下降...
  • 批量梯度下降、随机梯度下降、小批量梯度下降的python实现 之前写线性回归那一块内容的时候,发过手写二元线性回归梯度下降的博,由于基于方程的写法过于复杂,于是有了这一篇基于矩阵的梯度下降实现~
  • 在机器学习领域,体梯度下降算法分为三种 - 批量梯度下降算法(BGD,Batch gradient descent algorithm) - 随机梯度下降算法(SGD,Stochastic gradient descent algorithm) - 小批量梯度下降算法(MBGD,Mini-...
  • 一、批量梯度下降法(Batch Gradient Descent,BGD) 有N个样本,求梯度的时候就用了N个样本的梯度数据 优点:准确 缺点:速度慢 二、随机梯度下降法(Stochastic Gradient Descent,SGD) 和批量梯度下降法原理类似...
  • 梯度下降法的三种形式BGD、SGD以及MBGD   梯度下降法的三种形式BGD、SGD以及MBGD 阅读目录 1. 批量梯度下降法BGD 2. 随机梯度下降法SGD 3. 小批量梯度下降法MBGD 4. 总结 在应用机器学习...
  • 批量梯度下降, 随机梯度下降,小批量梯度下降 批量梯度下降 计算梯度时,使用全部的样本,换句话说就是,每一次参数更新,使用所有的样本 缺点:当样本很多时,训练过程非常慢 随机梯度下降 计算梯度的时,仅仅...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 28,414
精华内容 11,365
关键字:

梯度下降