深入浅出--梯度下降法及其实现

作者: 六尺帐篷 | 来源:发表于2018-01-17 21:06 被阅读1830次
    • 梯度下降的场景假设
    • 梯度
    • 梯度下降算法的数学解释
    • 梯度下降算法的实例
    • 梯度下降算法的实现
    • Further reading

    本文将从一个下山的场景开始,先提出梯度下降算法的基本思想,进而从数学上解释梯度下降算法的原理,最后实现一个简单的梯度下降算法的实例!

    梯度下降的场景假设

    梯度下降法的基本思想可以类比为一个下山的过程。假设这样一个场景:一个人被困在山上,需要从山上下来(i.e. 找到山的最低点,也就是山谷)。但此时山上的浓雾很大,导致可视度很低。因此,下山的路径就无法确定,他必须利用自己周围的信息去找到下山的路径。这个时候,他就可以利用梯度下降算法来帮助自己下山。具体来说就是,以他当前的所处的位置为基准,寻找这个位置最陡峭的地方,然后朝着山的高度下降的地方走,同理,如果我们的目标是上山,也就是爬到山顶,那么此时应该是朝着最陡峭的方向往上走。然后每走一段距离,都反复采用同一个方法,最后就能成功的抵达山谷。


    image.png

    我们同时可以假设这座山最陡峭的地方是无法通过肉眼立马观察出来的,而是需要一个复杂的工具来测量,同时,这个人此时正好拥有测量出最陡峭方向的能力。所以,此人每走一段距离,都需要一段时间来测量所在位置最陡峭的方向,这是比较耗时的。那么为了在太阳下山之前到达山底,就要尽可能的减少测量方向的次数。这是一个两难的选择,如果测量的频繁,可以保证下山的方向是绝对正确的,但又非常耗时,如果测量的过少,又有偏离轨道的风险。所以需要找到一个合适的测量方向的频率,来确保下山的方向不错误,同时又不至于耗时太多!

    梯度下降

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


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

    微分

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

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


      image.png

    上面的例子都是单变量的微分,当一个函数有多个变量的时候,就有了多变量的微分,即分别对每个变量进行求微分


    image.png

    梯度

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


    image.png

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

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

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

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


    image.png

    梯度下降算法的数学解释

    上面我们花了大量的篇幅介绍梯度下降算法的基本思想和场景假设,以及梯度的概念和思想。下面我们就开始从数学上解释梯度下降算法的计算过程和思想!


    image.png

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


    image.png

    下面就这个公式的几个常见的疑问:

    • α是什么含义?
      α在梯度下降算法中被称作为学习率或者步长,意味着我们可以通过α来控制每一步走的距离,以保证不要步子跨的太大扯着蛋,哈哈,其实就是不要走太快,错过了最低点。同时也要保证不要走的太慢,导致太阳下山了,还没有走到山下。所以α的选择在梯度下降法中往往是很重要的!α不能太大也不能太小,太小的话,可能导致迟迟走不到最低点,太大的话,会导致错过最低点!
    image.png
    • 为什么要梯度要乘以一个负号?
      梯度前加一个负号,就意味着朝着梯度相反的方向前进!我们在前文提到,梯度的方向实际就是函数在此点上升最快的方向!而我们需要朝着下降最快的方向走,自然就是负的梯度的方向,所以此处需要加上负号

    梯度下降算法的实例

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

    单变量函数的梯度下降

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


    image.png

    函数的微分


    image.png
    初始化,起点为
    image.png

    学习率为


    image.png
    根据梯度下降的计算公式
    image.png
    我们开始进行梯度下降的迭代计算过程:
    image.png
    如图,经过四次的运算,也就是走了四步,基本就抵达了函数的最低点,也就是山底
    image.png

    多变量函数的梯度下降

    我们假设有一个目标函数


    image.png

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


    image.png
    初始的学习率为:
    image.png

    函数的梯度为:


    image.png
    进行多次迭代:
    image.png
    我们发现,已经基本靠近函数的最小值点
    image.png

    梯度下降算法的实现

    下面我们将用python实现一个简单的梯度下降算法。场景是一个简单的线性回归的例子:假设现在我们有一系列的点,如下图所示

    image.png

    我们将用梯度下降法来拟合出这条直线!

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

    image.png

    此公示中

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


      image.png

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


    image.png

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

    为了转换为矩阵的计算,我们观察到预测函数的形式


    image.png

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


    image.png

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


    image.png

    coding time

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

    import numpy as np
    
    # Size of the points dataset.
    m = 20
    
    # Points x-coordinate and dummy value (x0, x1).
    X0 = np.ones((m, 1))
    X1 = np.arange(1, m+1).reshape(m, 1)
    X = np.hstack((X0, X1))
    
    # Points y-coordinate
    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)
    
    # The Learning Rate alpha.
    alpha = 0.01
    

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

    def error_function(theta, X, y):
        '''Error function J definition.'''
        diff = np.dot(X, theta) - y
        return (1./2*m) * np.dot(np.transpose(diff), diff)
    
    def gradient_function(theta, X, y):
        '''Gradient of the function J definition.'''
        diff = np.dot(X, theta) - y
        return (1./m) * np.dot(np.transpose(X), diff)
    

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

    def gradient_descent(X, y, alpha):
        '''Perform gradient descent.'''
        theta = np.array([1, 1]).reshape(2, 1)
        gradient = gradient_function(theta, X, y)
        while not np.all(np.absolute(gradient) <= 1e-5):
            theta = theta - alpha * gradient
            gradient = gradient_function(theta, X, y)
        return theta
    

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

    完整的代码如下

    import numpy as np
    
    # Size of the points dataset.
    m = 20
    
    # Points x-coordinate and dummy value (x0, x1).
    X0 = np.ones((m, 1))
    X1 = np.arange(1, m+1).reshape(m, 1)
    X = np.hstack((X0, X1))
    
    # Points y-coordinate
    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)
    
    # The Learning Rate alpha.
    alpha = 0.01
    
    def error_function(theta, X, y):
        '''Error function J definition.'''
        diff = np.dot(X, theta) - y
        return (1./2*m) * np.dot(np.transpose(diff), diff)
    
    def gradient_function(theta, X, y):
        '''Gradient of the function J definition.'''
        diff = np.dot(X, theta) - y
        return (1./m) * np.dot(np.transpose(X), diff)
    
    def gradient_descent(X, y, alpha):
        '''Perform gradient descent.'''
        theta = np.array([1, 1]).reshape(2, 1)
        gradient = gradient_function(theta, X, y)
        while not np.all(np.absolute(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('error function:', error_function(optimal, X, y)[0,0])
    

    运行代码,计算得到的结果如下


    image.png

    所拟合出的直线如下


    image.png

    小结

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

    Further reading

    相关文章

      网友评论

      • 李燕_0417:写的真好,通俗易懂,感谢!
      • INKWWW:谢谢 又复习了一遍加深理解
      • Jedore:在 梯度下降算法的实现里,对theta1微分的公式 最后 x 不应该有下表1吧,困惑了我好大一会呢
      • 微漾_7724:写的很好,通俗易懂,如果把theta的[1,1]改成任意随机[a,b]更能让人感到神奇
      • kathrynlala:专门注册个号 关注你了
      • 8af26d39f4a9:写的很好,谢谢!
      • 六常O:写的很好,看了很多文章都没看懂,这篇文章让我看懂了,感谢。
      • 7864f6f6faf1:讲的很好理解
      • zzzzzzz_4b33:太棒了!!感谢!!!
      • EtsuNegi:我专门注册了个号,就是为了上来感谢你。写的太好了,只有真正把原理弄明白的人,才能把一个复杂的原理讲得这么简单。那些把这个原理讲的更加复杂的人,要么就是自己都没弄明白,要不就是故弄玄虚。
        宣雄民:表示严重同意,我搜索了好多资源都没搞明白,直到看到篇文章
      • haojie:好文,有个问题下面问了类似的,不过不太一样,我来问问,最后得出θ=(0.515,0.969),那么可以认为θ0=0.515,θ1=0.969吗?如果不是,预测函数hθ(x)=θ0+θ1*x,它的表达式是是什么呢?
      • 郑斌_e582:老师,这个误差函数J(θ)应该是寻求最小值,目的是寻找误差函数最小时候的θ值,为什么要用θ-J(θ) 呢?而且最后为什么求出来θ的最小值?
        8af26d39f4a9:权且一看,初始为θ,然后每次向最低值进行逼近,第二次的一定比第一次的小,所以多次逼近后就接近最小值了
      • 044a00d99c3c:非常好的介绍。
      • 30fbdecfc3ba:给你赞赏一下
      • 30fbdecfc3ba:CSDN上面那么多博客我都没有看懂,博主的博客,让我一下子就看懂了。
      • 30fbdecfc3ba:写得真好,简书中的大神太多了。
      • lucky_ceb9:文章写得很清晰,很感谢。就是有一点不是很懂,按照迭代θ最小值作为依据,这个原理不是很懂,虽然梯度下降是减少的。但感觉应该按照代价函数的最小值来作为迭代终止条件,而θ作为变量参与计算。麻烦解答一下,谢谢!
        8af26d39f4a9:最小值有可能永远达不到,下山的步子太大,假如步子为从北京到上海,那么按照这个步子找杭州,很明显最终不会找到杭州,因为步子太大迈过了,要是步子太小,那么每次迈的小,但是耗时长,有可能直接求解到太阳下山,所以是综合了性能上的考量,没有设定最小值为迭代终止条件,而且最小值本身貌似就是一个伪概念,他如何定义呢?只有穷举了所有值,那么才有最小值,我们要的其实只是更好的那个值就可以了,以上都是自己的理解,若有错误,还请其他大神纠正
      • 四大爷:写得蛮好的,看了这篇文档,才算理解梯度下降算法
      • Hczt:最后loss函数代码应该是1/2/m,你写成乘以m了
      • 太阳晒得我丶好干瘪:我们有两个变量,为了对这个公式进行矩阵化,我们可以给每一个点x增加一维,这一维的值固定为1,这一维将会乘到Θ0上。这样就方便我们统一矩阵化的计算,这里没有看懂,可以解释下吗
        haojie:@Hczt 那么作者最后求出的θ和θ0、θ1的关系是怎么对应的呢?
        Hczt:矩阵操作需要X的列数等于Θ的行数。假设Θ为(2,1)T,那么y=2x+1,矩阵操作为(x,1) * (2,1)T ,即看成y=2*x+1*1。多个输入的情况下,X矩阵第一列为x的值,第二列全为1,即1乘到Θ0上
      • 凝枫:正好最近在看吴恩达的视频,其中描述了这个算法的思路推演过程,这篇文章更好的补充了这一点,而且最后的python代码很实用,谢谢!
        ArvinLiu_8422:真的写的很好,看的时候都在感叹理解得多么深刻,才能把问题写的如此清晰明了,学到了,我有一点点疑问,就是,梯度矩阵化那里能拆开讲一下嘛。
        六尺帐篷:@凝枫 谢谢鼓励,一起学习

      本文标题:深入浅出--梯度下降法及其实现

      本文链接:https://www.haomeiwen.com/subject/knuuoxtx.html