精华内容
下载资源
问答
  • 使用神经网络进行样本训练,要实现随机梯度下降算法。这里我根据麦子学院彭亮老师的讲解,总结如下,(神经网络的结构在另一篇博客中已经定义): def SGD(self, training_data, epochs, mini_batch_size, eta, ...
  • Adam 设计用于处理随机梯度下降问题; 即当仅使用小批量数据来估计每次迭代的梯度时,或使用随机 dropout 正则化时 [2]。 有关示例,请参阅 GIT 存储库: https://github.com/DylanMuir/fmin_adam 用法: [x, fval...
  • backpropagation backpropagation解决的核心问题损失函数c与w,b求偏导,(c为cost(w,b)) 整体来说,分两步 1.z=w*a’+b 2.a=sigmoid(z) 其中,a’表示上一层的输出值,a表示当前该层的输出值 1,输入x,正向的更新一...
  • SGD 随机梯度下降 Keras 中包含了各式优化器供我们使用,但通常我会倾向于使用 SGD 验证模型能否快速收敛,然后调整不同的学习速率看看模型最后的性能,然后再尝试使用其他优化器。 Keras 中文文档中对 SGD 的描述...
  • m = 100000 x = np.random.normal(size = m) X = x.reshape(-1, 1) y = 4.0 * x + 3.0 + np.random.normal(0 ,3, size = m) 。。。
  • 本专栏是书《深度学习入门》的阅读笔记一共八章: 第一章深度学习中的Python基础。主要讲解了深度学习将要用到的python的基础知识以及简单介绍了numpy库和matpoltlib库,本书编写深度学习神经网络代码仅使用Python和...
  • 您需要使用课程中介绍的随机梯度下降法来实现一个版本的软边距支持向量机。您将在给定的数据集(从课程网站下载)上运行代码,然后对测试数据集进行预测。衡量你得分的标准是你在测试数据集上的准确性。(提示:由于...
  • 主要为大家详细介绍了基于随机梯度下降的矩阵分解推荐算法,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
  • 资源中包含随机梯度下降逻辑回归算法的Python代码和测试数据,python的版本为3.6,您运行代码前,将测试文件路径修改为您本地的存储路径,使用pycharm平台运行即可。
  • 随机梯度下降sgd

    2018-03-14 10:53:38
    logistic随机梯度下降问题.docx
  • 随机梯度下降算法SDG的MATLAB实现,数据集可到UCI数据库里下载
  • 大规模数据聚类的基于随机梯度下降的K-Means算法
  • 多元逻辑斯蒂回归,并实现随机梯度下降和L1/L2正则化项。 参照 在此基础上加入L1和L2 Regularization;关于逻辑斯蒂回归中的L1和L2正则化项详见以下两个链接: 并对输入格式进行泛化,例如可以对“Sun Weather=rainy:...
  • 机器学习 SGD BGD 批量梯度下降 随机梯度下降
  • 主要为大家详细介绍了python实现随机梯度下降法,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
  • 拜占庭共识中基于随机梯度下降的聚合规则
  • 基于随机梯度下降的基于应力的图形绘制 。 有关相应演讲的视频(在IEEE VIS 2019上提供)可以在上观看。 我们建议使用可用的python软件包,该软件包使用SWIG在C ++中实现以生成绑定。 可以使用conda通过conda安装 ...
  • 梯度下降与随机梯度下降概念及推导过程

    万次阅读 多人点赞 2018-11-03 14:43:52
    同这一章的梯度下降部分加起来,才是我们要讲的如何求解多元线性回归.如果写在一章中,内容过长,担心有的同学会看不完,所以拆分成两章.[坏笑] 上一章中有提到利用解析解求解多元线性回归,虽然看起来很方便,但是在...

    接前一章:常用算法一 多元线性回归详解2(求解过程)

            同这一章的梯度下降部分加起来,才是我们要讲的如何求解多元线性回归.如果写在一章中,内容过长,担心有的同学会看不完,所以拆分成两章.[坏笑]

            上一章中有提到利用解析解求解多元线性回归,虽然看起来很方便,但是在解析解求解的过程中会涉及到矩阵求逆的步骤.随着维度的增多,矩阵求逆的代价会越来越大(时间/空间),而且有些矩阵没有逆矩阵,这个时候就需要用近似矩阵,影响精度.所以本章我们一起来学习求解多元线性回归最常用的,也是后边可能会讲的深度学习最常用的求解办法:梯度下降与随机梯度下降.

            其实随机梯度下降才是咱们最常用的求解办法,但是不知道梯度下降,理解随机梯度下降就有些直接盖二楼的感觉了(我的意思是空中楼阁).那什么是梯度下降呢?

            从字面意思上,我们就可以get到他最重要的点--梯度.所以首先我们来看梯度的概念.(事先声明,好多概念纯粹为了方便理解)

     

    什么是梯度:

            1-先看官方解释:

                       梯度的本意是一个向量(矢量),表示某一函数在该点处的方向导数沿着该方向取得最大值,即函数在该点处沿着该方向(此梯度的方向)变化最快,变化率最大(为该梯度的模)。

            2-通俗理解:

                       我们对一个多元函数求偏导,会得到多个偏导函数.这些导函数组成的向量,就是梯度.

                       这里需要开拓一下你聪明的头脑.一元函数的梯度是什么?思考一下.它的梯度可以理解为就是它的导数.

                       我们求解一元函数的时候有一种办法是对函数求导得到导函数,令导函数为零得到这个函数的解析解.那我们可不可以理解为求解一元函数时利用让一元函数的梯度变为0的时候,梯度所在的位置就是函数的最优解呢?  (稍稍有点偷天换日,但是在一元函数中梯度和导数并无区别,这块一定要理解)

     

                       梯度中元素(导函数)的个数的个数同未知数的个数是对应,每一个未知数都可以像求解一元一次函数一样,通过它所对应的梯度求得最优解.其实求解多元函数和一元函数的道理是一样的,只不过函数是一元的时候,梯度中只有一个导函数,函数时多元的时候,梯度中有多个导函数.

                      当我们把梯度中的所有偏导函数都变为0的时候,就可以找到每个未知数的对应解?(事实证明是这样的)

              附上一张梯度的图

             

              假设这个曲面是一个多元函数,我们可以把这个曲面看成是由无数条曲线组成,每条曲线代表了多元函数的一个维度,当所有维度都下降到梯度为0的点,是不是这个点就是多元函数的解的那个点呢?

     

    什么是梯度下降:

            1-还是按照惯例,先看官方解释.

             梯度下降是迭代法的一种,可以用于求解最小二乘问题(线性和非线性都可以)。在求解机器学习算法的模型参数,即无约束优化问题时,梯度下降(Gradient Descent)是最常采用的方法之一,另一种常用的方法是解析解。

             上一段来源于网络,对于咱们要理解的内容来看,上边一段等于没说.

            2-通俗讲

             梯度下降就是让梯度中所有偏导函数都下降到最低点的过程.(划重点:下降)

             都下降到最低点了,那每个未知数(或者叫维度)的最优解就得到了,所以他是解决函数最优化问题的算法

             这里需要注意一点,梯度是对所有未知数求偏导,所得偏导函数组成的向量.在多元线性回归中,谁才是未知数呢?我们使用梯度下降法的目的是求解多元线性回归中的最小二乘函数的,在最小二乘函数中,已拥有的条件是一些样本点和样本点的结果,就是矩阵X和每一条X样本的lable值y.X是矩阵,y是向量.

             所以我们要知道,梯度下降中求偏导数的未知数不是x和y,而是x的参数W或者叫\Theta(就是个名字,只不过常用这两个字母表示).

             数据集中数据是固定的,结果是固定的,我们要找到的是数据中样本与结果的对应规律.所以求得\Theta才是我们的目的.我们梯度下降,下降的也是\Theta而不是X.

    怎样理解下降:

              梯度下降中的下降,意思是让函数的未知数随着梯度的方向运动.什么是梯度的方向呢?把这一点带入到梯度函数中,结果为正,那我们就把这一点的值变小一些,同时就是让梯度变小些;当这一点带入梯度函数中的结果为负的时候,就给这一点的值增大一些.

            (图一)

             如上图,点A的导函数(此时把导函数看作梯度)为负,就让点A沿着函数轨迹往右移动一点,点B的导数为正,就让点B往左移动一点,这个移动的过程中,点A和店B的高度都在慢慢下降,所以这个过程叫做梯度下降.

             在这个下降的过程中.因为我们并不知道哪一个点才是最低点,也没有办法来预测下降多少次才能到最低点.这里梯度下降给出的办法是:先随便蒙一个点出来,然后根据这个点每次下降以丢丢.什么时候下降得到的值(点带入偏导函数得到的)和上一次的值基本基本一样也就是相差特别特别小的时候,我们认为就到了最低点.

             当然这里有两个问题:

                     1-这个值并不是完全准确:

                                我们并不需要一个完完全全准确的值来当做函数的解,因为多元线性回归构的理念中就讲了,我们是用一条回归线来预测未来结果,本身我们预测出的这个结果就存在一个误差,所以梯度下降的结果是否完全准确并不特别重要.

                     2-如果函数图像是一个波浪形,我们只能找到其中一个浪谷的最低点,这个点可能不是所有浪谷最低点中的最小值.

                               我们初始点的位置是随机蒙出来的造成了这种情况,多次随机可以有效解决解决这个问题.

                               如果我们多次有规律的随机都没有采集到的最低点,可能是因为这个最低点造成的原因是出现了某个离群值.(这句话不用理解,你就记得其实是不是最小值也并不是特别重要就行了.)

     

            函数在点\Theta_{A}\Theta_{B}的移动过程如何用公式来表达呢?公式如下:

            \Theta_{k} = \Theta_{k-1} - \alpha \cdot g     (公式一)

            公式中,\Theta_{k}为当前时刻的\theta值,\Theta_{k+1}为下一时刻的\theta值.g为梯度.\alpha是一个正数,我们先不看他.

            此时我们随机一个点,将这个点叫做k+1点,如果它的梯度为正,那么按照公式一,我们会将这个给它的梯度减去一个正数,得到一个k+1点梯度更小的梯度的点k;如果k+1的梯度像图一的点B一样梯度为负数,此时我们减去一个负数,就等于给他加了一个正数,得到的k点的梯度要比原来k+1点的梯度大.

             所以,按照公式一,无论k+1点的梯度是正还是负,我们都可以让他沿着函数图像向比原来更低的方向运动.

     

    \alpha是什么:是学习率

             我们把公式一中的\alpha叫做学习率.

             让点沿着梯度方向下降慢慢求得最优解的过程我们叫做学习,学习率就是用来限制他每次学习别太过"用功"的,因为机器学习也存在书呆子[奸笑].请看下图:

             (图二)

           图二中,左图是我们所期望的,一个点按照梯度方向下降,慢慢逼近最低点,右图中展示的就是那个书呆子.模型每次下降都是减去梯度的值,当这个梯度值过大的时候,点下降的step就过大了,一次性迈过了最低点,导致函数无法找到最优解.

           \alpha就是来限制这种情况的.我们让梯度乘以一个很小的数,虽然增加了它到达最低点的step数,但是可以让图二这种情况发生概率降低.

     

            到现在,我们知道了梯度下降法到底是什么,也知道了每一步是如何下降的,按照这个方法一次一次迭代下降就可以得到函数的最优解.但是还有很重要的一点:如何求梯度.

            重复一下:梯度就是对一个多元函数的未知数求偏导,得到的偏导函数构成的向量就叫梯度.那我们要求解的多元函数是哪个?

            是最小二乘函数:

                            (公式二)

           求导过程如下:

                             (公式三)

            公式三种,h_{\Theta }(x)W^{T}X,y所有样本点的lable值向量y.得到的公式(h_{\theta}(x) -y)x_{i}中,x_{i}是一个维度的所有数据,(h_{\theta}(x) -y)x_{i}本身是对这个维度的所有数据求梯度的和.所以我们得到梯度下降中的梯度g:

             g=1/m x (h_{\theta}(x) -y)x_{i}.   m为样本点的个数.

     公式的另一种表达形式:

             

    到这里,梯度下降就讲解完毕了.梯度下降又叫做批量梯度下降,简称BGD.

    (休息两分钟)

     

     

    下面我们来看随机梯度下降(SGD):

            批量梯度下降是,求出一个维度中所有的数据,取个平均来当做每一次梯度下降的step.这样做虽然准确,但是每次要计算一个维度的所有数据的梯度,花费资源较大.所以才有了随机梯度下降的思想:每次只随机取一个维度中的一条数据求梯度,来当做这个维度梯度下降的step.公式如下:

              

            可以看出,随机梯度下降和梯度下降公式的区别就是,里边的x由矩阵x变成了x的分量x^{i}

           为了更好的让大家理解梯度下降和随机梯度下降的区别,看下图:

           (批量梯度下降)   (随机梯度下降)

            途中,蓝色点为两个\Theta的取值,圆形越靠近里边表示误差越小.

            BGD总是综合所有数据的梯度,取到的下降至一直很平滑,SGD随机抽取一条数据作为参数,步子很不稳定.但是最终都可以到达函数的最优解位置.虽然看起来SGD比BGD的误差要大一些,但是SGD随着迭代次数的增加,误差会越来越小.

         

    最后,SGD因为每次只随机抽取一条数据来做梯度下降,计算代价比SGD小的不是一点半点.所有后边无论机器学习还是深度学习,对SGD的应用是非常非常广泛的.

    在SGD和BGD中间,还有一个集合了两种下降法的有点的办法:mini-bach-GD,你猜一猜他是啥?对了,是随机抽取小批量数据来做下降,但是用的并不多.

     

    利用梯度下降法求解梯度的过程:

            一般情况下分为三步:

            1-随机一个初始值,在多元线性回归中,我们随机一组w,带入到损失函数中,得到一个初始点.

            2-让这个点按照负梯度的方向运动,就是我们前边讲的 \Theta_{k} = \Theta_{k-1} - \alpha \cdot g,梯度的计算如上文所述.

            3-迭代第二步,当迭代此处达到某一个数,或者上一步和这一步的结果误差小于某个数,就认为是最优解了,停止迭代.迭代次数和最小误差值都是可以设置的.

            通过第三步,我们就可以得到一个我们想要的最优解.

            最后补充一点,梯度下降的公式\Theta_{k} = \Theta_{k-1} - \alpha \cdot g     (公式一)看起来好像开玩笑一样就定下来了,没有任何依据,其实不是这样的,它背后的理论依据是泰勒展开式.这里不再过多赘述了.文章就到这里,请大家帮忙勘误.

    (写文章很耗神,如果对您有帮助,欢迎点赞和评论)

                       

    下一篇:零基础理解 逻辑回归(logistics regression)

    展开全文
  • 随机梯度下降算法

    2018-03-12 14:25:47
    自己编写的随机梯度下降算法,附上房价预测数据集,感兴趣的可以看看
  • 主要为大家详细介绍了Spark MLlib随机梯度下降法概述与实例,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
  • 主要介绍了Python语言描述随机梯度下降法,具有一定借鉴价值,需要的朋友可以参考下
  • 文章目录前言1....随后,我们将引出随机梯度下降(stochastic gradient descent)。 1. 一维梯度下降 我们先以简单的一维梯度下降为例,解释梯度下降算法可能降低目标函数值的原因。假设连续可导的函数f:R→R

    前言

    在本节中,我们将介绍梯度下降(gradient descent)的工作原理。虽然梯度下降在深度学习中很少被直接使用,但理解梯度的意义以及沿着梯度反方向更新自变量可能降低目标函数值的原因是学习后续优化算法的基础。随后,我们将引出随机梯度下降(stochastic gradient descent)。

    1. 一维梯度下降

    我们先以简单的一维梯度下降为例,解释梯度下降算法可能降低目标函数值的原因。假设连续可导的函数 f : R → R f: \mathbb{R} \rightarrow \mathbb{R} f:RR的输入和输出都是标量。给定绝对值足够小的数 ϵ \epsilon ϵ,根据泰勒展开公式,我们得到以下的近似:

    f ( x + ϵ ) ≈ f ( x ) + ϵ f ′ ( x ) . f(x + \epsilon) \approx f(x) + \epsilon f'(x) . f(x+ϵ)f(x)+ϵf(x).

    这里 f ′ ( x ) f'(x) f(x)是函数 f f f x x x处的梯度。一维函数的梯度是一个标量,也称导数。

    接下来,找到一个常数 η > 0 \eta > 0 η>0,使得 ∣ η f ′ ( x ) ∣ \left|\eta f'(x)\right| ηf(x)足够小,那么可以将 ϵ \epsilon ϵ替换为 − η f ′ ( x ) -\eta f'(x) ηf(x)并得到

    f ( x − η f ′ ( x ) ) ≈ f ( x ) − η f ′ ( x ) 2 . f(x - \eta f'(x)) \approx f(x) - \eta f'(x)^2. f(xηf(x))f(x)ηf(x)2.

    如果导数 f ′ ( x ) ≠ 0 f'(x) \neq 0 f(x)=0,那么 η f ′ ( x ) 2 > 0 \eta f'(x)^2>0 ηf(x)2>0,所以

    f ( x − η f ′ ( x ) ) ≲ f ( x ) . f(x - \eta f'(x)) \lesssim f(x). f(xηf(x))f(x).

    这意味着,如果通过

    x ← x − η f ′ ( x ) x \leftarrow x - \eta f'(x) xxηf(x)

    来迭代 x x x,函数 f ( x ) f(x) f(x)的值可能会降低。因此在梯度下降中,我们先选取一个初始值 x x x和常数 η > 0 \eta > 0 η>0,然后不断通过上式来迭代 x x x,直到达到停止条件,例如 f ′ ( x ) 2 f'(x)^2 f(x)2的值已足够小或迭代次数已达到某个值。

    下面我们以目标函数 f ( x ) = x 2 f(x)=x^2 f(x)=x2为例来看一看梯度下降是如何工作的。虽然我们知道最小化 f ( x ) f(x) f(x)的解为 x = 0 x=0 x=0,这里依然使用这个简单函数来观察 x x x是如何被迭代的。首先,导入本节实验所需的包或模块。

    %matplotlib inline
    import matplotlib.pyplot as plt
    import numpy as np
    import torch
    import math
    import sys
    sys.path.append("..") 
    

    接下来使用 x = 10 x=10 x=10作为初始值,并设 η = 0.2 \eta=0.2 η=0.2。使用梯度下降对 x x x迭代10次,可见最终 x x x的值较接近最优解。

    def gd(eta):
        x = 10
        results = [x]
        for i in range(10):
            x -= eta * 2 * x  # f(x) = x * x的导数为f'(x) = 2 * x
            results.append(x)
        print('epoch 10, x:', x)
        return results
    
    res = gd(0.2)
    

    输出:

    epoch 10, x: 0.06046617599999997
    

    下面将绘制出自变量 x x x的迭代轨迹。

    def show_trace(res):
        n = max(abs(min(res)), abs(max(res)), 10)
        f_line = np.arange(-n, n, 0.1)
    	plt.rcParams['figure.figsize'] = (4.5, 2.5)
        plt.plot(f_line, [x * x for x in f_line])
        plt.plot(res, [x * x for x in res], '-o')
        plt.xlabel('x')
        plt.ylabel('f(x)')
    
    show_trace(res)
    

    在这里插入图片描述

    2. 学习率

    上述梯度下降算法中的正数 η \eta η通常叫作学习率。这是一个超参数,需要人工设定。如果使用过小的学习率,会导致 x x x更新缓慢从而需要更多的迭代才能得到较好的解。

    下面展示使用学习率 η = 0.05 \eta=0.05 η=0.05时自变量 x x x的迭代轨迹。可见,同样迭代10次后,当学习率过小时,最终 x x x的值依然与最优解存在较大偏差。

    show_trace(gd(0.05))
    

    输出:

    epoch 10, x: 3.4867844009999995
    

    在这里插入图片描述

    如果使用过大的学习率, ∣ η f ′ ( x ) ∣ \left|\eta f'(x)\right| ηf(x)可能会过大从而使前面提到的一阶泰勒展开公式不再成立:这时我们无法保证迭代 x x x会降低 f ( x ) f(x) f(x)的值。

    举个例子,当设学习率 η = 1.1 \eta=1.1 η=1.1时,可以看到 x x x不断越过(overshoot)最优解 x = 0 x=0 x=0并逐渐发散。

    show_trace(gd(1.1))
    

    输出:

    epoch 10, x: 61.917364224000096
    

    在这里插入图片描述

    3. 多维梯度下降

    在了解了一维梯度下降之后,我们再考虑一种更广义的情况:目标函数的输入为向量,输出为标量。假设目标函数 f : R d → R f: \mathbb{R}^d \rightarrow \mathbb{R} f:RdR的输入是一个 d d d维向量 x = [ x 1 , x 2 , … , x d ] ⊤ \boldsymbol{x} = [x_1, x_2, \ldots, x_d]^\top x=[x1,x2,,xd]。目标函数 f ( x ) f(\boldsymbol{x}) f(x)有关 x \boldsymbol{x} x的梯度是一个由 d d d个偏导数组成的向量:

    ∇ x f ( x ) = [ ∂ f ( x ) ∂ x 1 , ∂ f ( x ) ∂ x 2 , … , ∂ f ( x ) ∂ x d ] ⊤ . \nabla_{\boldsymbol{x}} f(\boldsymbol{x}) = \bigg[\frac{\partial f(\boldsymbol{x})}{\partial x_1}, \frac{\partial f(\boldsymbol{x})}{\partial x_2}, \ldots, \frac{\partial f(\boldsymbol{x})}{\partial x_d}\bigg]^\top. xf(x)=[x1f(x),x2f(x),,xdf(x)].

    为表示简洁,我们用 ∇ f ( x ) \nabla f(\boldsymbol{x}) f(x)代替 ∇ x f ( x ) \nabla_{\boldsymbol{x}} f(\boldsymbol{x}) xf(x)。梯度中每个偏导数元素 ∂ f ( x ) / ∂ x i \partial f(\boldsymbol{x})/\partial x_i f(x)/xi代表着 f f f x \boldsymbol{x} x有关输入 x i x_i xi的变化率。为了测量 f f f沿着单位向量 u \boldsymbol{u} u(即 ∥ u ∥ = 1 \|\boldsymbol{u}\|=1 u=1)方向上的变化率,在多元微积分中,我们定义 f f f x \boldsymbol{x} x上沿着 u \boldsymbol{u} u方向的方向导数为

    D u f ( x ) = lim ⁡ h → 0 f ( x + h u ) − f ( x ) h . \text{D}_{\boldsymbol{u}} f(\boldsymbol{x}) = \lim_{h \rightarrow 0} \frac{f(\boldsymbol{x} + h \boldsymbol{u}) - f(\boldsymbol{x})}{h}. Duf(x)=h0limhf(x+hu)f(x).

    依据方向导数性质,以上方向导数可以改写为

    D u f ( x ) = ∇ f ( x ) ⋅ u . \text{D}_{\boldsymbol{u}} f(\boldsymbol{x}) = \nabla f(\boldsymbol{x}) \cdot \boldsymbol{u}. Duf(x)=f(x)u.

    方向导数 D u f ( x ) \text{D}_{\boldsymbol{u}} f(\boldsymbol{x}) Duf(x)给出了 f f f x \boldsymbol{x} x上沿着所有可能方向的变化率。为了最小化 f f f,我们希望找到 f f f能被降低最快的方向。因此,我们可以通过单位向量 u \boldsymbol{u} u来最小化方向导数 D u f ( x ) \text{D}_{\boldsymbol{u}} f(\boldsymbol{x}) Duf(x)

    由于 D u f ( x ) = ∥ ∇ f ( x ) ∥ ⋅ ∥ u ∥ ⋅ cos ( θ ) = ∥ ∇ f ( x ) ∥ ⋅ cos ( θ ) \text{D}_{\boldsymbol{u}} f(\boldsymbol{x}) = \|\nabla f(\boldsymbol{x})\| \cdot \|\boldsymbol{u}\| \cdot \text{cos} (\theta) = \|\nabla f(\boldsymbol{x})\| \cdot \text{cos} (\theta) Duf(x)=f(x)ucos(θ)=f(x)cos(θ)
    其中 θ \theta θ为梯度 ∇ f ( x ) \nabla f(\boldsymbol{x}) f(x)和单位向量 u \boldsymbol{u} u之间的夹角,当 θ = π \theta = \pi θ=π时, cos ( θ ) \text{cos}(\theta) cos(θ)取得最小值 − 1 -1 1。因此,当 u \boldsymbol{u} u在梯度方向 ∇ f ( x ) \nabla f(\boldsymbol{x}) f(x)的相反方向时,方向导数 D u f ( x ) \text{D}_{\boldsymbol{u}} f(\boldsymbol{x}) Duf(x)被最小化。因此,我们可能通过梯度下降算法来不断降低目标函数 f f f的值:

    x ← x − η ∇ f ( x ) . \boldsymbol{x} \leftarrow \boldsymbol{x} - \eta \nabla f(\boldsymbol{x}). xxηf(x).

    同样,其中 η \eta η(取正数)称作学习率。

    下面我们构造一个输入为二维向量 x = [ x 1 , x 2 ] ⊤ \boldsymbol{x} = [x_1, x_2]^\top x=[x1,x2]和输出为标量的目标函数 f ( x ) = x 1 2 + 2 x 2 2 f(\boldsymbol{x})=x_1^2+2x_2^2 f(x)=x12+2x22。那么,梯度 ∇ f ( x ) = [ 2 x 1 , 4 x 2 ] ⊤ \nabla f(\boldsymbol{x}) = [2x_1, 4x_2]^\top f(x)=[2x1,4x2]。我们将观察梯度下降从初始位置 [ − 5 , − 2 ] [-5,-2] [5,2]开始对自变量 x \boldsymbol{x} x的迭代轨迹。我们先定义两个辅助函数,第一个函数使用给定的自变量更新函数,从初始位置 [ − 5 , − 2 ] [-5,-2] [5,2]开始迭代自变量 x \boldsymbol{x} x共20次,第二个函数对自变量 x \boldsymbol{x} x的迭代轨迹进行可视化。

    def train_2d(trainer):  # 本函数将保存在d2lzh_pytorch包中方便以后使用
        x1, x2, s1, s2 = -5, -2, 0, 0  # s1和s2是自变量状态,本章后续几节会使用
        results = [(x1, x2)]
        for i in range(20):
            x1, x2, s1, s2 = trainer(x1, x2, s1, s2)
            results.append((x1, x2))
        print('epoch %d, x1 %f, x2 %f' % (i + 1, x1, x2))
        return results
    
    def show_trace_2d(f, results):  # 本函数将保存在d2lzh_pytorch包中方便以后使用
        plt.plot(*zip(*results), '-o', color='#ff7f0e')
        x1, x2 = np.meshgrid(np.arange(-5.5, 1.0, 0.1), np.arange(-3.0, 1.0, 0.1))
        plt.contour(x1, x2, f(x1, x2), colors='#1f77b4')
        plt.xlabel('x1')
        plt.ylabel('x2')
    
    

    然后,观察学习率为 0.1 0.1 0.1时自变量的迭代轨迹。使用梯度下降对自变量 x \boldsymbol{x} x迭代20次后,可见最终 x \boldsymbol{x} x的值较接近最优解 [ 0 , 0 ] [0,0] [0,0]

    eta = 0.1
    
    def f_2d(x1, x2):  # 目标函数
        return x1 ** 2 + 2 * x2 ** 2
    
    def gd_2d(x1, x2, s1, s2):
        return (x1 - eta * 2 * x1, x2 - eta * 4 * x2, 0, 0)
    
    show_trace_2d(f_2d, train_2d(gd_2d))
    
    

    输出:

    epoch 20, x1 -0.057646, x2 -0.000073
    

    在这里插入图片描述

    4. 随机梯度下降

    在深度学习里,目标函数通常是训练数据集中有关各个样本的损失函数的平均。设 f i ( x ) f_i(\boldsymbol{x}) fi(x)是有关索引为 i i i的训练数据样本的损失函数, n n n是训练数据样本数, x \boldsymbol{x} x是模型的参数向量,那么目标函数定义为

    f ( x ) = 1 n ∑ i = 1 n f i ( x ) . f(\boldsymbol{x}) = \frac{1}{n} \sum_{i = 1}^n f_i(\boldsymbol{x}). f(x)=n1i=1nfi(x).

    目标函数在 x \boldsymbol{x} x处的梯度计算为

    ∇ f ( x ) = 1 n ∑ i = 1 n ∇ f i ( x ) . \nabla f(\boldsymbol{x}) = \frac{1}{n} \sum_{i = 1}^n \nabla f_i(\boldsymbol{x}). f(x)=n1i=1nfi(x).

    如果使用梯度下降,每次自变量迭代的计算开销为 O ( n ) \mathcal{O}(n) O(n),它随着 n n n线性增长。因此,当训练数据样本数很大时,梯度下降每次迭代的计算开销很高。

    随机梯度下降(stochastic gradient descent,SGD)减少了每次迭代的计算开销。在随机梯度下降的每次迭代中,我们随机均匀采样的一个样本索引 i ∈ { 1 , … , n } i\in\{1,\ldots,n\} i{1,,n},并计算梯度 ∇ f i ( x ) \nabla f_i(\boldsymbol{x}) fi(x)来迭代 x \boldsymbol{x} x

    x ← x − η ∇ f i ( x ) . \boldsymbol{x} \leftarrow \boldsymbol{x} - \eta \nabla f_i(\boldsymbol{x}). xxηfi(x).

    这里 η \eta η同样是学习率。可以看到每次迭代的计算开销从梯度下降的 O ( n ) \mathcal{O}(n) O(n)降到了常数 O ( 1 ) \mathcal{O}(1) O(1)。值得强调的是,随机梯度 ∇ f i ( x ) \nabla f_i(\boldsymbol{x}) fi(x)是对梯度 ∇ f ( x ) \nabla f(\boldsymbol{x}) f(x)的无偏估计:

    E i ∇ f i ( x ) = 1 n ∑ i = 1 n ∇ f i ( x ) = ∇ f ( x ) . E_i \nabla f_i(\boldsymbol{x}) = \frac{1}{n} \sum_{i = 1}^n \nabla f_i(\boldsymbol{x}) = \nabla f(\boldsymbol{x}). Eifi(x)=n1i=1nfi(x)=f(x).

    这意味着,平均来说,随机梯度是对梯度的一个良好的估计。

    下面我们通过在梯度中添加均值为0的随机噪声来模拟随机梯度下降,以此来比较它与梯度下降的区别。

    def sgd_2d(x1, x2, s1, s2):
        return (x1 - eta * (2 * x1 + np.random.normal(0.1)),
                x2 - eta * (4 * x2 + np.random.normal(0.1)), 0, 0)
    
    show_trace_2d(f_2d, train_2d(sgd_2d))
    

    输出:

    epoch 20, x1 -0.047150, x2 -0.075628
    
    

    在这里插入图片描述

    可以看到,随机梯度下降中自变量的迭代轨迹相对于梯度下降中的来说更为曲折。这是由于实验所添加的噪声使模拟的随机梯度的准确度下降。在实际中,这些噪声通常指训练数据集中的无意义的干扰。

    小结

    • 使用适当的学习率,沿着梯度反方向更新自变量可能降低目标函数值。梯度下降重复这一更新过程直到得到满足要求的解。
    • 学习率过大或过小都有问题。一个合适的学习率通常是需要通过多次实验找到的。
    • 当训练数据集的样本较多时,梯度下降每次迭代的计算开销较大,因而随机梯度下降通常更受青睐。
    展开全文
  • 梯度下降、随机梯度下降、小批量梯度下降、动量梯度下降、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 ( θ ) J(\theta) J(θ) 是关于参数 θ \theta θ 的损失函数, η \eta η学习率(正标量),也称为梯度下降的步长。由上述公式可知,梯度下降的想法是使得参数 θ \theta θ 向着负梯度方向做更新迭代。

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

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

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

    ∂ J ( θ 0 , θ 1 ) ∂ θ 0 = 1 m ∑ i = 1 m ( θ 0 + θ 1 x i − y i ) \frac{\partial J(\theta_0,\theta_1)}{\partial \theta_0} = \frac{1}{m}\sum_{i = 1}^m(\theta_0+\theta_1x^i -y^i) θ0J(θ0,θ1)=m1i=1m(θ0+θ1xiyi) ∂ J ( θ 0 , θ 1 ) ∂ θ 1 = 1 m ∑ i = 1 m ( θ 0 + θ 1 x i − y i ) x i \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 θ1J(θ0,θ1)=m1i=1m(θ0+θ1xiyi)xi

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

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

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

    下面给出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 ( θ , x i , y i ) ∂ θ \theta := \theta - \eta\cdot\frac{\partial J(\theta,x^i,y^i)}{\partial \theta} θ:=θηθJ(θ,xi,yi)步骤如下:

    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个样本来训练参数:
    θ : = θ − η ⋅ 1 n ∑ i = 1 n ∂ J ( θ , x i , y i ) ∂ θ \theta := \theta - \eta\cdot\frac{1}{n}\sum_{i=1}^n\frac{\partial J(\theta,x^i,y^i)}{\partial \theta} θ:=θηn1i=1nθJ(θ,xi,yi)步骤如下:

    1. 随机打乱数据集。
    2. 将数据集分为 m n \frac{m}{n} nm个集合,如果有余,将剩余样本单独作为一个集合。
    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)策略,使用之前梯度信息修正当前梯度,来加速参数学习。这里我们令梯度项
    1 m ∑ i = 1 m ∂ J ( θ , x i , y i ) ∂ θ = ∇ θ J ( θ ) \frac{1}{m}\sum_{i=1}^m\frac{\partial J(\theta,x^i,y^i)}{\partial \theta} = \nabla_\theta J(\theta) m1i=1mθJ(θ,xi,yi)=θJ(θ)则梯度下降可以简化表示为
    θ : = θ − η ⋅ ∇ θ J ( θ ) \theta := \theta - \eta\cdot\nabla_\theta J(\theta) θ:=θηθJ(θ)
    对于动量梯度下降,初始化动量项 m = 0 m = 0 m=0,更新迭代公式如下
    m : = γ ⋅ m + η ⋅ ∇ θ J ( θ ) m := \gamma\cdot m + \eta\cdot\nabla_\theta J(\theta) m:=γm+ηθJ(θ) θ : = θ − m \theta :=\theta - m θ:=θm
    其中 m m m为动量梯度下降的动量项,且初始化为0; γ \gamma γ是关于动量项的超参数一般取小于等于0.9。我们可以发现,越是远离当前点的梯度信息,对于当前梯度的贡献越小。

    优点:通过过去梯度信息来优化下降速度,如果当前梯度与之前梯度方向一致时候,收敛速度得到加强,反之则减弱。换句话说,加快收敛同时减小震荡,分别对应图中 θ 0 \theta_0 θ0 θ 1 \theta_1 θ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) θJ(θηm)考虑进来。其更新公式如下:
    m : = γ ⋅ m + η ⋅ ∇ θ J ( θ − γ ⋅ m ) m :=\gamma\cdot m+\eta\cdot\nabla_\theta J(\theta-\gamma\cdot m) m:=γm+ηθJ(θγm) θ : = θ − m \theta := \theta - m θ:=θm
    对于公式理解如下图所示,

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

    在这里插入图片描述
    优点

    1. 相对于动量梯度下降法,因为NAG考虑到了未来预测梯度,收敛速度更快(如上图)。
    2. 当更新幅度很大时,NAG可以抑制震荡。例如起始点在最优点的左侧 γ m \gamma m γm对应的值在最优点的右侧,对于动量梯度而言,叠加 η ∇ 1 \eta\nabla_1 η1使得迭代后的点更加远离最优点→→。而NAG首先跳到 γ m \gamma m γm对应的值,计算梯度为正,再叠加反方向的 η ∇ 2 \eta\nabla_2 η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 θ1对应的学习率 η \eta η升高到0.005后,得到以下另一组数据方便对比。η=[0.1,0.005]

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

    后语

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

    展开全文
  • 损失使用平方函数,简单的线性模型 y = theta1 + theta2 * x
  • 批量梯度下降、随机梯度下降、小批量梯度下降的python实现 之前写线性回归那一块内容的时候,发过手写二元线性回归梯度下降的博,由于基于方程的写法过于复杂,于是有了这一篇基于矩阵的梯度下降实现~

    写在前面

    之前写线性回归那一块内容的时候,发过手写二元线性回归梯度下降的博,由于基于方程的写法过于复杂,于是有了这一篇基于矩阵的梯度下降实现~

    梯度下降回顾

    首先,我们一起回顾一下梯度下降的算法原理:
    梯度下降是一种最优化算法的常见求解方法,广泛应用于:线性回归、逻辑回归、神经网络、支持向量机等算法中。
    我们之前都有说过梯度下降的白话解说:详情戳☞机器学习入门——线性回归剖析☜
    梯度下降就是用以解决最小二乘算法解决不了的问题,当损失函数非凸时,常规的最小二乘无法求解(容易陷入局部最优)见下图:
    在这里插入图片描述
    上图即是损失函数非凸函数的情况,这时直接使用最小二乘求全局最优解是非常不切实际的。(全局最优解无法得到,往往陷入局部坑中)
    这个时候,灵活的梯度下降就出现了。
    梯度下降分为:批量梯度下降(Batch Gradient Descent)、随机梯度下降(Stochastic Gradient Descent)和小批量梯度下降(Mini Batch Gradient Descent)。
    我们常说的梯度下降就是批量梯度下降,用大白话来理解这三个算法就是:
    批量梯度下降BGD:使用全部样本构建了损失函数(在线性回归中为SSE),再根据损失函数梯度下降求得系数(权值);
    随机梯度下降SGD:每次只使用一个样本点得到损失函数的公式,根据梯度下降求解参数,再随机选择样本进行系数更新;
    小批量梯度下降MBGD:每次使用部分样本计算得到损失函数,根据梯度下降算法求解参数,再不断更新。
    根据理解,我们可以总结得出其三个算法的优缺点见下表:

    算法优点缺点
    BGD容易理解,得到稳定的参数值每次迭代需要计算所有的样本,计算复杂;容易收敛到局部最优
    SGD用随机性对抗数据集可能存在的不确定性,解决容易收敛到局部最优解的问题;大大加快了收敛速率每次计算得到的系数值都不同,对关注于参数的算法不适用
    MBGD结合上述两算法不同batch_size的选择可能带来一些问题

    算法过程

    设样本量为m,回归方程为:
    h θ ( x 1 , x 2 , . . . x n ) = θ 0 + θ 1 x 1 + . . . + θ n x n h θ ( x 1 , x 2 , . . . x n ) = θ 0 + θ 1 x 1 + . . . + θ n x n h_θ(x1,x2,...x_n)=θ_0+θ_1x_1+...+θ_nx_nh_θ(x_1,x_2,...x_n)=θ_0+θ_1x_1+...+θ_nx_n hθ(x1,x2,...xn)=θ0+θ1x1+...+θnxnhθ(x1,x2,...xn)=θ0+θ1x1+...+θnxn 损失函数为: J ( θ 0 , θ 1 . . . , θ n ) = 1 2 m ∑ j m ( h θ ( x j ) − y j ) 2 = 1 2 m ( X θ − Y ) T ( X θ − Y ) J(θ_0,θ_1...,θ_n)=\frac{1}{2m}∑_j^m(h_θ(x^j)−y^j)^2=\frac{1}{2m}(X\theta-Y)^T(X\theta-Y) J(θ0,θ1...,θn)=2m1jm(hθ(xj)yj)2=2m1(XθY)T(XθY) g r a d θ = ∇ J ( θ ) = ∂ J ( θ ) ∂ θ = 1 m X T ( X θ − Y ) grad_\theta = \nabla J(\theta)=\frac{\partial J(\theta)}{\partial \theta}=\frac{1}{m}X^T(X\theta-Y) gradθ=J(θ)=θJ(θ)=m1XT(XθY)PS.上述具体推导过程详见:☞之前博客-正规方程法☜
    系数更新: θ : = θ − α ∗ g r a d θ = θ − α ∗ 1 m X T ( X θ − Y ) \theta:=\theta-\alpha*grad_\theta=\theta-\alpha*\frac{1}{m}X^T(X\theta-Y) θ:=θαgradθ=θαm1XT(XθY)
    Note.在介绍下述算法实现之前,首先应该明了,使用梯度下降的算法应该对数据进行标准化以消除量纲对梯度下降的影响。(对特征进行缩放(归一化、标准化)可以更快进行收敛。)
    在这里插入图片描述
    我们以吴恩达老师所说的例子(仍然是房价),对于房屋数量和房屋面积,其量纲差别较大,此时不标准化,直接进行梯度下降的结果如上图左,收敛速度慢;而对数据进行标准化后再进行梯度下降,得到的结果如上右图更快的收敛到全局最小值。

    定义标准化函数:

    def regulization(X):
    	xmat = X.copy()
    	x_mean = np.mean(xmat,axis = 0)
    	x_std = np.std(xmat,axis = 0)
    	x_norm = (xmat-x_mean)/x_std
    	return x_norm
    

    批量梯度下降的python实现

    def bgd(data,alp=0.01,numit=5000):
    	# 将数据转化为矩阵形式(分特征矩阵和标签矩阵)
    	xMat = np.mat(data.iloc[:,:-1].values)
    	yMat = np.mat(data.iloc[:,-1].values).T
    	# 将数据标准化
    	xMat = regulization(xMat)
    	yMat = regulization(yMat)
    	m,n = xMat.shape
    	# 存储系数
    	w = np.zeros((n,1))
    	for k in range(numit):
    		grad = xMat.T*(xMat*w-yMat)/m
    		w -= alp*grad
    	return w
    

    随机梯度下降的python实现

    注意:此处更换数据集,尽量不要在线性回归中使用随机梯度下降(线性回归关注参数,随机梯度下降每次运行的参数都不同!)
    以逻辑回归为例(损失函数非凸)详情可见☞“机器学习入门——10分钟走进逻辑回归(Logistic Regression)”☜

    def sgd(data,alp=0.01,numit=5000):
    	# 设置“随机性”:数据打乱
    	data = data.sample(numit,replace=True)
    	data.index = range(data.shape[0])
    	xMat = np.mat(data.iloc[:,:-1].values)
    	yMat = np.mat(data.iloc[:,-1].values).T
    	xMat = regulization(xMat)
    	m,n = xMat.shape
    	w = np.zeros((n,1))
    	# 对打乱的数据依次求解梯度下降
    	for i in range(m):
    		grad = xMat[i].T*(xMat[i]*w-yMat[i])
    		w -= alp*grad
    	return w
    

    小批量梯度下降的python实现

    def sbgd(data,alp=0.01,numit=5000,batch_size=10):
        data = data.sample(numit,replace=True)
        data.index = range(data.shape[0])
        xMat = np.mat(data.iloc[:,:-1].values)
        yMat = np.mat(data.iloc[:,-1].values).T
        xMat = regulization(xMat)
        m,n = xMat.shape
        w = np.zeros((n,1))
        k = m/batch_size
        for i in range(batch_size):
            if i < (batch_size-1):
                grad = xMat[range(int(k)*i,(i+1)*int(k))].T*(xMat[range(int(k)*i,(i+1)*int(k))]*w-yMat[range(int(k)*i,(i+1)*int(k))])
            else:
                grad = xMat[range(int(k)*i,m)].T*(xMat[range(int(k)*i,m)]*w-yMat[range(int(k)*i,m)])
                w -= alp*grad
        return w
    sbgd(abalone,alp=0.01,numit=5000,batch_size=10)
    

    写在最后

    以上是本人对梯度下降三个方法的浅要理解,如果哪里有问题,欢迎大家批评指正~希望和大家共同进步!

    展开全文
  • 随机梯度下降法 数学原理Minimising cost function is the holy grail of machine learning. Gradient descent is our master key to all cost minimisation problems. But gradient descent is slow. It uses ...
  • 接触过神经网络的人都知道,网络的训练是其核心,本人在读书时接触的是BP神经网络,那时写的代码训练样本量不大,没有注意到题目所列出的这些训练方式,偶尔也曾看到了 “批量梯度下降”的名词,却并没有深入研究它...
  • 梯度下降法: ·不是一个机器学习方法 是一种基于搜素的最优化方法 作用:最小化一个损失函数(最终我们要求解的线性回归模型的本质就是最小化一个损失函数,直接计算出最小化函数的对应的参数的数学解,但是后面会...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 81,943
精华内容 32,777
关键字:

随机梯度下降