精华内容
下载资源
问答
  • 最速下降法

    千次阅读 2016-05-15 21:47:43
    最速下降法有两种,一种是学习步长每次都是确定的(这里不讨论),一种是学习步长是按照沿直线最小化计算获得。 这里不进行公式的推导,只是用图例解释: 特点:1.在等值图中看到的寻优路线呈锯齿状(标准90度...

    最速下降法有两种,一种是学习步长每次都是确定的(这里不讨论),一种是学习步长是按照沿直线最小化计算获得。

    这里不进行公式的推导,只是用图例解释:


    特点:1.在等值图中看到的寻优路线呈锯齿状(标准90度)

                 2.沿直线的最小化总会在轮廓线上的一点停止,因为此处在此方向上的导数为零。

           

    展开全文
  • 我们这一讲将要介绍的最速下降法,是梯度法的一种改进实现。 1.SymPy库的介绍 在具体进行算法介绍之前,我们先花一点时间来专门谈谈pythonpythonpython的SymPySymPySymPy库,SymPySymPySymPy库是PythonPythonPython...

    我们这一讲将要介绍的最速下降法,是梯度法的一种改进实现。

    1.SymPy库的介绍

    在具体进行算法介绍之前,我们先花一点时间来专门谈谈pythonpythonSymPySymPy库,SymPySymPy库是PythonPython的数学符号计算库,用它可以进行数学表达式的符号推导和计算,可以很方便的进行公式推导、级数展开、积分、微分以及解方程等重要运算。

    可能大家对于符号计算这个名字感觉有些陌生和奇怪,我们下面结合例子来慢慢熟悉他:

    1.1.符号导入

    我们举一个最典型的例子:欧拉公式。

    eiπ+1=0e^{i\pi}+1=0,这里面有自然对数ee,虚数ii,圆周率π\pi等数学符号,如果我们想用pythonpython来描述这个等式,运用之前的知识也可以办到,只不过相对而言比较麻烦,这里如果使用SymPySymPy库就会非常简单,他可以一次性将这些符号都导入进来,并完成公式的计算:

    代码片段:

    from sympy import *
    
    print("E**(I*pi)+1={}".format(E**(I*pi)+1))
    

    运行结果:

    E**(I*pi)+1=0
    

    1.2.自定义符号

    上面的欧拉公式中,我们所用的符号eeiiπ\pi都是已有的常量,如果我们的目标是实现一个带有自变量xx的表达式,该如何处理?这里,我们需要自己定义新加入的变量xx,我们看一个例子:验证eixe^{ix}这个表达式展开为实部和虚部的形式:eix=isinx+cosxe^{ix}=isinx+cosx

    代码片段:

    from sympy import *
    
    x = Symbol('x', real=True)
    print(expand(E**(I*x), complex=True))
    

    运行结果:

    I*sin(x) + cos(x)
    

    在这个例子中,我们利用SymbolSymbol函数定义了一个实变量符号xx,并基于他定义了一个新的表达式eixe^{ix},然后我们使用expandexpand方法在复数的范围内将eixe^{ix}展开为了实部+虚部的形式:isin(x)+cos(x)isin(x) + cos(x)

    1.3.任意阶数的泰勒展开

    之前我们学习过函数的泰勒展开的有关知识,实际上利用SymPySymPy库对指定函数进行任意阶数的泰勒展开是非常容易的,我们下面分别对sin(x)sin(x)cos(x)cos(x)进行1010阶泰勒展开:

    代码片段:

    from sympy import *
    
    x = Symbol('x', real=True)
    sin_s = series(sin(x), x, 0, 10)
    cos_s = series(cos(x), x, 0, 10)
    print('sin(x)={}'.format(sin_s))
    print('cos(x)={}'.format(cos_s))
    

    运行结果:

    sin(x)=x - x**3/6 + x**5/120 - x**7/5040 + x**9/362880 + O(x**10)
    cos(x)=1 - x**2/2 + x**4/24 - x**6/720 + x**8/40320 + O(x**10)
    

    可以看出,得到的泰勒展开式的结果是非常准确的,还包含了无穷小量的表达。

    1.4.自定义符号替换

    在实际的程序当中,我们经常需要对表达式中的变量进行名称替换,最简单的,比如把变量名xx替换成变量名yy,至于说用处是什么,我们在后面的例子中会见到,我们先看看如何使用,试着把上面的cos(x)cos(x)的级数展开式中的变量xx替换成yy

    代码片段:

    from sympy import *
    
    x = Symbol('x', real=True)
    y = Symbol('y', real=True)
    cos_s = series(cos(x), x, 0, 10)
    print('cos(x)={}'.format(cos_s))
    cos_s = cos_s.subs(x, y)
    print('cos(y)={}'.format(cos_s))
    

    运行结果:

    cos(x)=1 - x**2/2 + x**4/24 - x**6/720 + x**8/40320 + O(x**10)
    cos(y)=1 - y**2/2 + y**4/24 - y**6/720 + y**8/40320 + O(y**10)
    

    这样就完成了变量名称的替换工作。

    1.5.求导与微分

    我们来看看如何利用SymPySymPy库里的diffdiff函数对函数进行求导运算。

    这里,我们分别举三个例子,看看导数ddxsin(2x)\frac{d}{dx}sin(2x)、二阶导d2dx2(x2+2x+1)\frac{d^2}{dx^2}(x^2+2x+1)、偏导数2xy(x2y2+2x3+y2)\frac{\partial^2}{\partial x \partial y}(x^2y^2+2x^3+y^2)的符号求解方法:

    代码片段:

    from sympy import *
    
    x = Symbol('x', real=True)
    y = Symbol('y', real=True)
    
    print(diff(sin(2*x),x))
    print(diff(x**2+2*x+1,x,2))
    print(diff(x**2*y**2+2*x**3+y**2,x,1,y,1))
    

    运行结果:

    2*cos(2*x)
    2
    4*x*y
    

    从结果中,我们很轻松的得到了三种导数结果的符号表达式:

    ddxsin(2x)=2cos(2x)\frac{d}{dx}sin(2x)=2cos(2x)

    d2dx2x2+2x+1=2\frac{d^2}{dx^2}x^2+2x+1=2

    2xyx2y2+2x3+y2=4xy\frac{\partial^2}{\partial x \partial y}x^2y^2+2x^3+y^2=4xy

    1.6.解方程

    SymPySymPy库当中的solvesolve方法可以用来解方程,这个就非常方便了,我们看两个简单的例子:

    一次方程:x+1=0x+1=0

    二次方程:x2+3x+2=0x^2+3x+2=0

    代码片段:

    from sympy import *
    
    x = Symbol('x', real=True)
    
    f1 = x + 1
    f2 = x**2+3*x+2
    
    print(solve(f1))
    print(solve(f2))
    

    运行结果:

    [-1]
    [-2, -1]
    

    得到的结果是一个列表,里面包含了方程所有的解。

    1.7.表达式求值

    这个用法其实非常关键,前面我们用各种方式生成了表达式,如何对我们自定义的符号变量赋值,并计算出表达式的值,看下面的具体实现:

    我们求当x=2x=2的时候,函数f(x)=x2+3x+2f(x)=x^2+3x+2的取值:

    很简单,表达式求值的本质也是符号变量的替换,就是把自定义的符号变量xx替换成目标取值22

    代码片段:

    from sympy import *
    x = Symbol('x', real=True)
    f = x**2+3*x+2
    
    print(f.subs(x,2))
    

    运行结果:

    12.0000000000000
    

    之所以花了这么多的篇幅来介绍一个新的pythonpython库用法,目的是在接下来的最速下降法的实现中使用他们,以简化我们的代码实现。

    2.最速下降法的核心思想

    最速下降法是梯度下降法的一种实现形式,每一步都是沿着负梯度的方向迭代前进,但是同上一讲里介绍的方法不同之处在于学习率的选择方式:

    在基础的梯度下降法当中,学习率λk\lambda_k是固定的,即pk+1=pkf(pk)λkp_{k+1}=p_k-\nabla f(p_k)\lambda_k

    但是最速下降法则不然,搜索方向仍然是当前点pkp_k的负梯度方向f(pk)-\nabla f(p_k),但是迭代的目标点是需要满足在这个搜索方向上使得函数ff取得该方向上的极小值,即:

    pk+1=pkαkf(pk)p_{k+1}=p_k-\alpha_k\nabla f(p_k),使得函数取值f(pk+1)f(p_{k+1})在搜索的一维方向上取得极小值。

    更进一步的,在pkp_k点进行迭代时,由于此时pkp_kf(pk)\nabla f(p_k)都是已知的,实际上的工作就是锁定αk\alpha_k的取值,使得函数f(pkαkf(pk))f(p_k-\alpha_k\nabla f(p_k))取得极小值。此时在寻找函数极小值的过程中,仅仅只有一个未知数,那就是αk\alpha_k,因此我们面对的问题实际上就是一个一元函数极值点的搜索问题,方法有很多,这在我们前面的内容中已经详细讲解过了,相信对大家没有难度。

    每次迭代的过程都是在当前迭代点的负梯度方向上寻找使得函数取得极小值点的αk\alpha_k值,然后依次迭代出下一个迭代点,最终直至满足预设阈值条件,迭代停止。

    3.算法步骤

    这里,我们来总结一下最速下降法的步骤:

    首先,我们从一个初始的迭代点p0p_0开始;

    每一轮迭代,对于当前点pkp_k,计算当前点的梯度f(pk)\nabla f(p_k),如果梯度的模长f(pk)|\nabla f(p_k)|小于预设的阈值ϵ\epsilon,则停止迭代,当前点pkp_k即为函数的极小值点;

    否则:寻找使得f(pkαkf(pk))f(p_k-\alpha_k\nabla f(p_k))取得极小值的αk\alpha_k,然后迭代出新的取值点:pk+1=pkαkf(pk)p_{k+1}=p_k-\alpha_k\nabla f(p_k)

    循环往复的进行上述迭代过程。

    4.代码演示

    我们举一个实际的例子f(x1,x2)=2x12+x22x1x22x2f(x_1,x_2)=2x_1^2+x_2^2-x_1x_2-2x_2,来演示最速下降法的代码实现。

    代码片段:

    from sympy import *
    from matplotlib import pyplot as plt
    import numpy as np
    from mpl_toolkits.mplot3d import Axes3D
    
    fig = plt.figure()
    ax = Axes3D(fig)
    
    def get_func_val(f, p):
        return f.subs(x1, p[0]).subs(x2, p[1])
    
    
    def grad_l2(grad_cur, p_cur):
        return sqrt(get_func_val(grad_cur[0], p_cur) ** 2 +
                    get_func_val(grad_cur[1], p_cur) ** 2)
    			
    			
    def get_alpha(f):
        alpha_list = np.array(solve(diff(f)))
        return min(alpha_list[alpha_list>0])
    
    
    def func(x1,x2):
        return 2*x1**2+x2**2-x1*x2-2*x2
    
    
    x1 = np.arange(-1.5, 1.5, 0.01)
    x2 = np.arange(-1.5, 1.5, 0.01)
    x1, x2 = np.meshgrid(x1, x2)
    ax.plot_surface(x1, x2, func(x1, x2), color='y', alpha=0.3)
    
    x1 = symbols("x1")
    x2 = symbols("x2")
    f = 2*x1**2+x2**2-x1*x2-2*x2
    
    p0 = np.array([0, 0])
    p_cur = p0
    grad_cur = np.array([diff(f, x1), diff(f, x2)])
    
    while(True):
        ax.scatter(float(p_cur[0]),float(p_cur[1]),func(float(p_cur[0]),float(p_cur[1])),color='r')
        if (grad_l2(grad_cur, p_cur) < 0.001):
            break
        grad_cur_val = np.array([get_func_val(grad_cur[0], p_cur),get_func_val(grad_cur[1], p_cur)])
        a = symbols('a')
        p_val = p_cur - a * grad_cur_val
        alpha = get_alpha(f.subs(x1, p_val[0]).subs(x2, p_val[1]))
        p_cur = p_cur - alpha * grad_cur_val
        
    plt.show()
    

    这段代码比较复杂,并且里面用到了大量SymPySymPy库中的方法,我们仔细分析一下:

    x1 = symbols("x1")
    x2 = symbols("x2")
    f = 2*x1**2+x2**2-x1*x2-2*x2
    

    这里面我们自定义了符号x1x_1x2x_2,并用上述符号变量定义了函数符号ff

    def get_func_val(f, p):
        return f.subs(x1, p[0]).subs(x2, p[1])
    

    上述函数的作用是将点坐标p=[x1,x2]p=[x_1,x_2]的值,实际带入到符号函数中,得到函数的最终取值。

    def grad_l2(grad_cur, p_cur):
        return sqrt(get_func_val(grad_cur[0], p_cur) ** 2 +
                    get_func_val(grad_cur[1], p_cur) ** 2)
    

    grad_curgrad\_cur是一个用符号表示的梯度表达式,函数的目标是计算出当前点处梯度的模长。

    def get_alpha(f):
        alpha_list = np.array(solve(diff(f)))
        return min(alpha_list[alpha_list>0])
    
    a = symbols('a')
    p_val = p_cur - a * grad_cur_val
    alpha = get_alpha(f.subs(x1, p_val[0]).subs(x2, p_val[1]))
    p_cur = p_cur - alpha * grad_cur_val
    

    这两部分代码连同起来看,就是找到使得f(pkαkf(pk))f(p_k-\alpha_k\nabla f(p_k))取得极小值的αk\alpha_k的过程,符号变量aa就是所有αk\alpha_k可能取到的变量集,此时我们发现p_varp\_var是当前点的坐标向量,他其中唯一的未知变量就是符号变量aa,而恰恰就是这个p_varp\_var需要使得函数ff取得极小值,因此,此时的函数ff就是一个关于aa的一元函数。

    这里有一个隐含的条件,由于我们是沿着负梯度的方向向前走,即pk+1=pkαkf(pk)p_{k+1}=p_k-\alpha_k\nabla f(p_k)。因此,aa必须满足大于00,同时,在刚刚开始走的一段时间里,负梯度方向决定了函数值是不断减小的,换句话说开始走的一段一定是下坡路,因此我们碰到的第一个极值点,一定是极小值点。

    那么,我们通过让一阶导函数f(a)=0f'(a)=0得到的一系列解当中,最小的正数解就是我们要找的步长αk\alpha_k,他让我们跨到第一个局部极小值点,而函数get_alpha(f)get\_alpha(f)干的就是这个事儿。

    当然我们使用前面介绍的牛顿法、割线法去迭代寻找αk\alpha_k也都是可以的,大家可以尝试进行替换。

    我们来看看最终迭代出来的取值点序列。

    运行结果:
    图1.最速下降法的结果

    5.迭代路径的特性分析

    实际上,在最速下降法的迭代过程中,迭代序列中的各点还满足一个规律。具体是什么?我们还是在xoyxoy投影平面上,将迭代点绘制在等位线图上进行观察:

    代码片段:

    from sympy import *
    from matplotlib import pyplot as plt
    import numpy as np
    
    
    def get_func_val(f, p):
        return f.subs(x1, p[0]).subs(x2, p[1])
    
    
    def grad_l2(grad_cur, p_cur):
        return sqrt(get_func_val(grad_cur[0], p_cur) ** 2 +
    		get_func_val(grad_cur[1], p_cur) ** 2)
    
    
    def get_alpha(f):
        alpha_list = np.array(solve(diff(f)))
        return min(alpha_list[alpha_list > 0])
    
    
    def func(x1, x2):
        return 2 * x1 ** 2 + x2 ** 2 - x1 * x2 - 2 * x2
    
    
    x1 = np.arange(-0.2, 1.2, 0.01)
    x2 = np.arange(-0.2, 1.2, 0.01)
    x1, x2 = np.meshgrid(x1, x2)
    
    C = plt.contour(x1, x2, func(x1, x2), 60)
    plt.clabel(C, inline=True, fontsize=12)
    
    x1 = symbols("x1")
    x2 = symbols("x2")
    f = 2 * x1 ** 2 + x2 ** 2 - x1 * x2 - 2 * x2
    
    p0 = np.array([0, 0])
    p_cur = p0
    grad_cur = np.array([diff(f, x1), diff(f, x2)])
    
    while (True):
        plt.plot(float(p_cur[0]), float(p_cur[1]),'ro', markersize=4)
        if (grad_l2(grad_cur, p_cur) < 0.001):
            break
        grad_cur_val = np.array([get_func_val(grad_cur[0], p_cur), get_func_val(grad_cur[1], p_cur)])
        a = symbols('a')
        p_val = p_cur - a * grad_cur_val
        alpha = get_alpha(f.subs(x1, p_val[0]).subs(x2, p_val[1]))
        p_cur = p_cur - alpha * grad_cur_val
    
    plt.show()
    

    运行结果:
    图2.迭代点的路径分析
    在图中,我们肉眼观察出迭代点pkpk+1p_kp_{k+1}的连线与pk+1pk+2p_{k+1}p_{k+2}的连线是垂直的,也就是说相邻两次的迭代搜索方向保持相互间的垂直关系。这是巧合还是必然?

    其实这是最速下降法中的必然结果,我们简单证明一下:

    首先有pk+1=pkαkf(pk)p_{k+1}=p_k-\alpha_k\nabla f(p_k)

    我们令ϕk=f(pkαf(pk))\phi_k=f(p_k-\alpha\nabla f(p_k)),由于αk\alpha_k的选取,使得ϕ(αk)=f(pkαkf(pk))\phi(\alpha_k)=f(p_k-\alpha_k\nabla f(p_k))取得最小值,因此我们让ϕk\phi_k对变量α\alpha进行求导,按照求导的链式法则:

    dϕkdα=df(pkαf(pk))d(pkαf(pk)d(pkαf(pk))dα\frac{d\phi_k}{d\alpha}=\frac{df(p_k-\alpha\nabla f(p_k))}{d(p_k-\alpha\nabla f(p_k)}\frac{d(p_k-\alpha\nabla f(p_k))}{d\alpha}

    且当α=αk\alpha=\alpha_k时,dϕkdα(αk)=0\frac{d\phi_k}{d\alpha}(\alpha_k)=0

    这个式子看上去有点麻烦,实际上抓住两个关键点就好了:

    第一:在这个求导的表达式中pkp_kf(pk)\nabla f(p_k)都是常数,变量只有一个,那就是α\alpha,因此后面一个表达式化简为:d(pkαf(pk))dα=f(pk)\frac{d(p_k-\alpha\nabla f(p_k))}{d\alpha}=-\nabla f(p_k)

    第二:当α=αk\alpha=\alpha_k时,我们可以将前面一部分中的pkαkf(pk)p_k-\alpha_k\nabla f(p_k)整体替换成pk+1p_{k+1},而此时df(pkαf(pk))d(pkαf(pk)=df(pk+1)d(pk+1)\frac{df(p_k-\alpha\nabla f(p_k))}{d(p_k-\alpha\nabla f(p_k)}=\frac{df(p_{k+1})}{d(p_{k+1})},这是什么?这不就是迭代点pk+1p_{k+1}处的梯度f(pk+1)\nabla f(p_{k+1})吗?

    这样一来,我们可以把dϕkdα(αk)\frac{d\phi_k}{d\alpha}(\alpha_k)进一步化简成为上述两个梯度向量点积的形式:

    dϕkdα(αk)=f(pk+1)(f(pk))=0\frac{d\phi_k}{d\alpha}(\alpha_k)=\nabla f(p_{k+1})\cdot (-\nabla f(p_k))=0

    最终结果出来了,我们得到了f(pk+1)f(pk)=0\nabla f(p_{k+1})\cdot \nabla f(p_k)=0的关系,由于我们每次搜索的方向都是当前位置的负梯度方向,因此就证明了相邻两次的搜索方向满足相互正交。

    展开全文
  • 在机器学习中,我们构建的模型,大部分...梯度下降法或最速下降法是求解无约束最优化问题的一种最常用的方法,有实现简单的优点。梯度下降法是迭代算法,每一步需要求解目标函数的梯度向量。 假设f(x)是Rn上具有一...

      在机器学习中,我们构建的模型,大部分都是通过求解代价函数的最优值进而得到模型参数的值。那么,对于构建好的目标函数和约束条件,我们应该如何对其进行求解呢!

           在机器学习中,最常用的优化方法是梯度下降法。梯度下降法或最速下降法是求解无约束最优化问题的一种最常用的方法,有实现简单的优点。梯度下降法是迭代算法,每一步需要求解目标函数的梯度向量。

           假设f(x)是Rn上具有一阶连续偏导数的函数。要求解的无约束最优化问题是:

    x*表示目标函数f(x)的极小值。

           梯度下降法是一种迭代算法。选取适当的初值x0,不断迭代,更新x的值,进行目标函数的极小化,直到收敛。由于负梯度方向是使函数值下降最快的反向,在迭代的每一步,以负梯度方向更新x的值,从而达到减小函数值的目的。

           由于f(x)是具有一阶连续偏导数,若第k次迭代值为X(k),则可将f(x)在X(k)附近进行一阶泰勒展开:

     

    这里,为f(x)在X(k)的梯度。

           求出第k+1次迭代值X(k+1):

     

    其中,P(k)是搜索方向,取负梯度方向是步长,由一维搜索确定,即使得:

     

            

     

          

     

     

     

     

     

     

     

     

     

     

     

      当目标函数是凸函数时,梯度下降的解是全局最优解,一般情况下,其解不保证是全局最优解。梯度下降法的收敛速度也未必是很快的。

           梯度下降算法根据更新梯度所使用的样本数,又可以分为:标准梯度下降,随机梯度下降,批量梯度下降。

           标准梯度下降:通过所有的训练样本来进行梯度下降,每一次得到的结果都能靠近极值点,但是对于所有的样本进行计算,每次更新需花费的时间较多。

           随机梯度下降:通过每次随机选取一个样本来对参数进行更新,由于是随机选取一个样本来进行更新,因而并不是每次迭代都能够靠近极值点,但是迭代的整体方向是朝着最优化方向的,并且迭代的速度较快。

           批量梯度下降:将上述两种方法进行折中,就得到了批量梯度下降,将训练数据分为若干个批次,每次选取其中的一个批次进行迭代,既能够加快训练速度,又能够使得模型稳定的收敛。

    简单代码演示:

     1 import numpy as np
     2 import matplotlib as mpl
     3 import matplotlib.pyplot as plt
     4 from mpl_toolkits.mplot3d import Axes3D
     5 
     6 def f(x, y):
     7     # z = 2*np.sin(1.5*x**2 - 0.25*y + 0.25*np.pi) + 3*np.cos(1.5*x*y - 0.5*np.pi)
     8     z = np.sin(x) + np.cos(y)
     9     return z
    10 
    11 if __name__ == '__main__':
    12     t = np.linspace(0, np.pi*2, 50)
    13     x1, y1 = np.meshgrid(t, t)
    14     z = np.stack([x1.flat, y1.flat], axis=1)
    15     # print(z.shape)
    16     x = z[:, 0]
    17     y = z[:, 1]
    18     # print(x)
    19     z = f(x, y)
    20     # print(z)
    21     z = z.reshape(x1.shape)
    22     # print(z.shape)
    23     fig = plt.figure()
    24     ax = Axes3D(fig)
    25     ax.plot_surface(x1, y1, z, rstride=1, cstride=1, cmap='rainbow')
    26     plt.xlabel("x")
    27     plt.ylabel("y")
    28     ax.set_zlabel("z")
    29 
    30     x0 = 2
    31     y0 = 0.5
    32     n = 0.5
    33     xy = []
    34     for i in range(100):
    35         xn = x0 - n*np.cos(x0)
    36         yn = y0 + n*np.sin(y0)
    37         x0 = xn
    38         y0 = yn
    39         xy.append([x0, y0])
    40     xy = np.array(xy)
    41     ax.plot(xy[:, 0], xy[:, 1], f(xy[:, 0], xy[:, 1]), 'k-' ,linewidth=5)
    42     ax.plot(xy[:, 0], xy[:, 1], f(xy[:, 0], xy[:, 1]), 'k*' ,linewidth=20)
    43     plt.show()

      

     

      

    转载于:https://www.cnblogs.com/baby-lily/p/10746385.html

    展开全文
  • 梯度下降法(gradient descent),又名最速下降法(steepest descent)是求解无约束最优化问题最常用的方法,它是一种迭代方法,每一步主要的操作是求解目标函数的梯度向量,将当前位置的负梯度方向作为搜索方向...

    Artificial Intelligence

    梯度下降法

    参考链接

    基本概念

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

    梯度下降,其实就是一个公式:在这里插入图片描述

    公式推导

    在这里插入图片描述

    基本梯度下降步骤

    步骤在这里插入图片描述

    η为学习率,ε为收敛条件。梯度下降法属于机器学习,本质为:不断迭代判断是否满足条件,会用到循环语句。

    Created with Raphaël 2.2.0首先设定一个较小的正数m,n;求当前位置处的各个偏导数;修改当前函数的参数值;参数变化量小于n求得极小值结束框回退迭代yesno

    在这里插入图片描述
    在这里插入图片描述

    批量梯度下降(BGD)

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

    bgd.png

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

    • 优点:

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

    • 缺点:

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

    代码实现

    #引库
    #引入matplotlib库,用于画图
    import matplotlib.pyplot as plt
    from math import pow
    #图片嵌入jupyter
    #matplotlib inline
    
    #为了便于取用数据,我们将数据分为x,y,在直角坐标系中(x,y)是点
    x = [1,2,3,4,5,6]
    y = [13,14,20,21,25,30]
    print("打印初始数据图...")
    plt.scatter(x,y)
    plt.xlabel("X")
    plt.ylabel("Y")
    plt.show()
    
    #超参数设定
    alpha = 0.01#学习率/步长
    theta0 = 0#θ0
    theta1 = 0#θ1
    epsilon = 0.001#误差
    m = len(x)
    
    count = 0
    loss = []
    
    for time in range(1000):
        count += 1
        #求偏导theta0和theta1的结果
        temp0 = 0#J(θ)对θ0求导的结果
        temp1 = 0#J(θ)对θ1求导的结果
        diss = 0
        for i in range(m):
            temp0 += (theta0+theta1*x[i]-y[i])/m
            temp1 += ((theta0+theta1*x[i]-y[i])/m)*x[i]
    
        #更新theta0和theta1
        for i in range(m):
            theta0 = theta0 - alpha*((theta0+theta1*x[i]-y[i])/m) 
            theta1 = theta1 - alpha*((theta0+theta1*x[i]-y[i])/m)*x[i]
    
        #求损失函数J(θ)
        for i in range(m):
            diss = diss + 0.5*(1/m)*pow((theta0+theta1*x[i]-y[i]),2)
        loss.append(diss)
    
        #看是否满足条件
        '''
        if diss<=epsilon:
            break
        else:
            continue
        '''
    print("最终的结果为:")
    print("此次迭代次数为:{}次,最终theta0的结果为:{},最终theta1的结果为:{}".format(count,theta0,theta1))
    print("预测的最终回归函数为:y={}+{}x\n".format(theta0,theta1))
    print("迭代图像绘制...")
    plt.scatter(range(count),loss)
    plt.show()
    

    运行结果
    在这里插入图片描述

    随机梯度下降(SGD)

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

    sgd.png

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

    • 优点:

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

    • 缺点:

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

    代码实现

    #引库
    #引入matplotlib库,用于画图
    import matplotlib.pyplot as plt
    from math import pow
    import numpy as np
    #图片嵌入jupyter
    #matplotlib inline
    
    #为了便于取用数据,我们将数据分为x,y,在直角坐标系中(x,y)是点
    x = [1,2,3,4,5,6]
    y = [13,14,20,21,25,30]
    print("打印初始数据图...")
    plt.scatter(x,y)
    plt.xlabel("X")
    plt.ylabel("Y")
    plt.show()
    
    #超参数设定
    alpha = 0.01#学习率/步长
    theta0 = 0#θ0
    theta1 = 0#θ1
    epsilon = 0.001#误差
    m = len(x)
    
    count = 0
    loss = []
    
    for time in range(1000):
        count += 1
        diss = 0
        #求偏导theta0和theta1的结果
        temp0 = 0#J(θ)对θ0求导的结果
        temp1 = 0#J(θ)对θ1求导的结果
        for i in range(m):
            temp0 += (theta0+theta1*x[i]-y[i])/m
            temp1 += ((theta0+theta1*x[i]-y[i])/m)*x[i]
    
        #更新theta0和theta1
        for i in range(m):
            theta0 = theta0 - alpha*((theta0+theta1*x[i]-y[i])/m) 
            theta1 = theta1 - alpha*((theta0+theta1*x[i]-y[i])/m)*x[i]
    
        #求损失函数J(θ)
        rand_i = np.random.randint(0,m)
        diss += 0.5*(1/m)*pow((theta0+theta1*x[rand_i]-y[rand_i]),2)
        loss.append(diss)
    
        #看是否满足条件
        '''
        if diss<=epsilon:
            break
        else:
            continue
        '''
    print("最终的结果为:")
    print("此次迭代次数为:{}次,最终theta0的结果为:{},最终theta1的结果为:{}".format(count,theta0,theta1))
    print("预测的最终回归函数为:y={}+{}x\n".format(theta0,theta1))
    print("迭代图像绘制...")
    plt.scatter(range(count),loss)
    plt.show()
    

    运行结果
    在这里插入图片描述

    小批量梯度下降(MBGD)

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

    mbgd.png

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

    • 优点:

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

    代码实现

    #引库
    #引入matplotlib库,用于画图
    import matplotlib.pyplot as plt
    from math import pow
    import numpy as np
    #图片嵌入jupyter
    #matplotlib inline
    
    #为了便于取用数据,我们将数据分为x,y,在直角坐标系中(x,y)是点
    x = [1,2,3,4,5,6]
    y = [13,14,20,21,25,30]
    print("打印初始数据图...")
    plt.scatter(x,y)
    plt.xlabel("X")
    plt.ylabel("Y")
    plt.show()
    
    #超参数设定
    alpha = 0.01#学习率/步长
    theta0 = 0#θ0
    theta1 = 0#θ1
    epsilon = 0.001#误差
    diss = 0#损失函数
    m = len(x)
    
    count = 0
    loss = []
    
    for time in range(1000):
        count += 1
        diss = 0
        #求偏导theta0和theta1的结果
        temp0 = 0#J(θ)对θ0求导的结果
        temp1 = 0#J(θ)对θ1求导的结果
        for i in range(m):
            temp0 += (theta0+theta1*x[i]-y[i])/m
            temp1 += ((theta0+theta1*x[i]-y[i])/m)*x[i]
    
        #更新theta0和theta1
        for i in range(m):
            theta0 = theta0 - alpha*((theta0+theta1*x[i]-y[i])/m) 
            theta1 = theta1 - alpha*((theta0+theta1*x[i]-y[i])/m)*x[i]
    
        #求损失函数J(θ)
        result = []
        for i in range(3):
            rand_i = np.random.randint(0,m)
            result.append(rand_i)
        for j in result:
            diss += 0.5*(1/m)*pow((theta0+theta1*x[j]-y[j]),2)
        loss.append(diss)
    
        #看是否满足条件
        '''
        if diss<=epsilon:
            break
        else:
            continue
        '''
    print("最终的结果为:")
    print("此次迭代次数为:{}次,最终theta0的结果为:{},最终theta1的结果为:{}".format(count,theta0,theta1))
    print("预测的最终回归函数为:y={}+{}x\n".format(theta0,theta1))
    print("迭代图像绘制...")
    plt.scatter(range(count),loss)
    plt.show()
    

    运行结果
    在这里插入图片描述

    线性回归

    参考链接1

    参考链接2

    一元线性回归概念

    一元线性回归其实就是从一堆训练集中去算出一条直线,使数据集到直线之间的距离差最小。

    最简单的模型如图所示:在这里插入图片描述

    下列2个模型都是线性回归模型,即便右图中的线看起来并不像直线。
    在这里插入图片描述

    原理引入

    唯一特征X,共有m = 500个数据数量,Y是实际结果,要从中找到一条直线,使数据集到直线之间的距离差最小,如下图所示:
    在这里插入图片描述
    在这里插入图片描述

    作业

    实例一:单变量线性回归问题

    房屋价格与面积(数据在下面表格中)

    序号 面积 价格
    1 150 6450
    2 200 7450
    3 250 8450
    4 300 9450
    5 350 11450
    6 400 15450
    7 600 18450

    使用梯度下降求解线性回归在这里插入图片描述
    在这里插入图片描述
    要求:

    (1)对关键代码进行注释;

    (2)把每次迭代计算出来的theta0 ,theta1 画出来;

    (3)分别用随机梯度和批量梯度实现,并在同一个图形中进行对比(颜色不同)。

    代码实现

    #引入matplotlib库,用于画图
    import matplotlib.pyplot as plt
    import random
    import matplotlib
    #建立直角坐标系(x,y)
    x = [150,200,250,300,350,400,600]
    y = [6450,7450,8450,9450,11450,15450,18450]
    #步长
    alpha = 0.00001
    #计算样本个数,即m=7
    m = len(x)
    #初始化参数的值,拟合函数为 y=theta0+theta1*x,p为批量,s为随机
    ptheta0 = 0
    ptheta1 = 0
    stheta1=0
    stheta0=0
    #误差
    error0=0
    error1=0
    #退出迭代的两次误差差值的阈值
    epsilon=0.000001
    #批量梯度下降BGD
    def p(x):
        return ptheta1*x+ptheta0
    #随机梯度下降SGD
    def s(x):
        return stheta1*x+stheta0
    #开始迭代批量梯度
    presult0 = []
    presult1 = []
    while True:
        diff = [0,0]
        # 梯度下降
        for i in range(m):
            diff[0] += p(x[i]) - y[i]  # 对theta0求导
            diff[1] += (p(x[i]) - y[i]) * x[i]  # 对theta1求导
        ptheta0 = ptheta0 - alpha / m * diff[0]
        ptheta1 = ptheta1 - alpha / m * diff[1]
        presult0.append(ptheta0)
        presult1.append(ptheta1)
        error1 = 0
        # 计算两次迭代的误差的差值,小于阈值则退出迭代,输出拟合结果
        for i in range(len(x)):
            error1 += (y[i] - (ptheta0 + ptheta1 * x[i])) ** 2 / 2
        if abs(error1 - error0) < epsilon:
            break
        else:
            error0 = error1
    
    #开始迭代随机梯度
    sresult0 = []
    sresult1 = []
    for j in range(5000):
        diff = [0, 0]
        # 梯度下降
        i = random.randint(0, m - 1)
        diff[0] += s(x[i]) - y[i]  # 对theta0求导
        diff[1] += (s(x[i]) - y[i]) * x[i]  # 对theta1求导
        stheta0 = stheta0 - alpha / m * diff[0]
        stheta1 = stheta1 - alpha / m * diff[1]
        sresult0.append(stheta0)
        sresult1.append(stheta1)
        error1 = 0
        # 计算两次迭代的误差的差值,小于阈值则退出迭代,输出拟合结果
        for k in range(len(x)):
            error1 += (y[i] - (stheta0 + stheta1 * x[i])) ** 2 / 2
        if abs(error1 - error0) < epsilon:
            break
        else:
            error0 = error1
    #结果
    print(ptheta1,ptheta0)
    print(stheta1,stheta0)
    #画图
    a=len(presult0)
    C=len(presult1)
    b=range(a)
    c=range(C)
    plt.plot(b,presult0)
    plt.xlabel("Runs")
    plt.ylabel("theta0")
    plt.show()
    plt.plot(c,presult1)
    plt.xlabel("Runs")
    plt.ylabel("theta1")
    plt.show()
    a1=len(sresult0)
    C1=len(sresult1)
    b1=range(a1)
    c1=range(C1)
    plt.plot(b1,sresult0)
    plt.xlabel("Runs")
    plt.ylabel("theta0")
    plt.show()
    plt.plot(c1,sresult1)
    plt.xlabel("运行次数")
    plt.ylabel("theta1")
    plt.show()
    matplotlib.rcParams['font.sans-serif'] = ['SimHei']
    plt.plot(x,[p(x) for x in x],label='批量梯度')
    plt.plot(x,[s(x) for x in x],label='随机梯度')
    plt.plot(x,y,'bo',label='数据')
    plt.legend()
    plt.show()
    

    运行结果

    (1)批量梯度:

    theta1=28.778604659732547
    theta0=1771.0428917695647
    在这里插入图片描述
    theta0随运行次数的变化见上图
    在这里插入图片描述
    theta1随运行次数的变化见上图

    (2)批量梯度:

    theta1=33.71739545116426
    theta0=2.0564426533254134
    在这里插入图片描述
    theta0随运行次数的变化见上图
    在这里插入图片描述
    theta1随运行次数的变化见上图
    在这里插入图片描述
    结果对比见上图

    总结

    ​ 我想,大部分人刚接触到这块知识,都是觉得好难,头秃@~~@。其实学后在回头想想,还行吧,这一章节主要是理解梯度下降的本质、公式的推导、批量梯度下降和随机梯度下降。(小批量梯度下降不太常用)

    ​ 代码的话(以房屋价格与面积的问题为例),其实就是两种梯度下降的合成,代码中除BGD和SGD的关键代码不同,其余的还是很相似的。还有一点就是,matplotlib库函数的一些操作,如果不会这个,那就没办法画图像了。

    展开全文
  • 梯度下降法(Gradient descent)是一个一阶最优化算法,通常也称为最速下降法。 要使用梯度下降法找到一个函数的局部极小值,必须向函数上当前点对应梯度(或者是近似梯度)的反方向的规定步长距离点进行迭代搜索。...
  • Dogleg(狗腿法)的推导与步骤

    千次阅读 2019-07-04 20:15:47
    首先L-M法是G-N法与最速下降法的混合形式,通过调整阻尼因子来在这两种方法之间切换,而狗腿法类似,只不过它是通过改变信赖域来实现的。这里可以分为两个问题: 如何判断是使用G-N法还是最速...
  • 为了提高系统的谐波抑制能力,以最近时域区间系统偏差的积分构造目标函数,通过梯度下降法分析了目标函数的最速下降方向,推导出锁相环系统的非线性状态方程,从而对输入信号属性进行估计。为了进行系统性能分析和参数...
  • 梯度下降、牛顿

    2020-07-12 16:05:07
    目录一、梯度下降(最速下降)二、牛顿 一、梯度下降(最速下降) 最优化:目标是寻找x值,使得函数f(x)逐步往f(x)最小值方向移动。 直观解释:从几何意义上来说,梯度向量就是函数f增加最快的地方,或者说,...
  • CNN神经网络算法是常用的模式识别算法,该算法通过卷积运算将图片特征存储到多个卷积核中,卷积核通过算法的反向传输一步步逼近于图片特征,最常用的反向传导方法是BP反向传导方法,采用最速下降法,将结果误差传递...
  • 原始GBDT推导

    千次阅读 2017-10-16 16:45:40
    GBDT采用的是数值优化的思维, 用的最速下降法去求解Loss Function的最优解, 其中用CART决策树去拟合负梯度, 用牛顿法求步长. XGboost用的解析的思维, 对Loss Function展开到二阶近似, 求得解析解, 用解析解作为Gain...
  • 梯度下降

    2020-09-27 21:03:12
    梯度下降法(gradient descent),又名最速下降法(steepest descent)是求解无约束最优化问题最常用的方法,它是一种迭代方法,每一步主要的操作是求解目标函数的梯度向量,将当前位置的负梯度方向作为搜索方向...
  • 梯度下降法是一个一阶最优化算法,通常也称为最速下降法。要使用梯度下降法找到一个函数的局部极小值,必须向函数上当前点对于梯度(或者是近似梯度)的反方向的规定步长距离点进行迭代搜索。所以梯度下降法可以帮助...
  • 一,什么是BP "BP(Back Propagation)网络是1986年由Rumelhart和McCelland为首的科学家小组提出,是一种按误差...它的学习规则是使用最速下降法,通过反向传播来不断调整网络的权值和阈值,使网络的误差平方和最小...
  • 此处有两个写的比较好的介绍最速下降,牛顿法,共轭梯度下降法的网页,mark一下。 http://www.codelast.com/?p=2573&cpage=1#comment-579 http://bbs.sciencenet.cn/blog-588243-573819.html 共轭...
  • Freidman提出了梯度提升算法,该方法是利用最速下降法的近似方法,其关键是利用损失函数的负梯度在当前模型的值 −[∂L(y,f(xi))∂f(xi)]f(x)=fm−1(x)-[{\partial L(y,f(x_i)) \over \partial f(x_i)}]_{f(x) = f_{...
  • BP神经网络算法的理论推导和源代码

    千次阅读 2015-01-28 23:35:28
    一、算法详解(来自互联网) "BP(Back Propagation)网络是1986年由Rumelhart和McCelland为首的科学家小组提出,是一种按误差逆...它的学习规则是使用最速下降法,通过反向传播来不断调整网络的权值和阈值,使
  • 为避免权值反复迭代修正的冗长BP训练过程,避免传统方法陷入局部极小点,根据多项式理论,构造了一种新型前向神经网络模型,推导了基于最速下降法的误差反传算法和基于伪逆的直接确定法.仿真结果显示,迭代方法和伪...
  • 优化方法小结

    2020-02-26 22:00:44
    文章目录一维搜索算法Fibonacci法与黄金分割法黄金分割法步骤进退法平分法不精确的一维搜索无约束最优化方法最速下降法Newton法共轭方向法和共轭梯度法拟Newton法约束最优化方法等式约束的最优性条件不等式约束的最...
  • 凸优化学习 学习笔记 一、牛顿法(Newton’s ...在最速下降法中,我们的方向: dk=arg⁡min⁡v{f(xk+v)∣∥v∥=1} d^k=\arg\min_v\lbrace f(x^k+v)\big|\|v\|=1\rbrace dk=argvmin​{f(xk+v)∣∣...
  • 在二维静电场有限元分析的基础上,推导了基于最速下降法的设计变量灵敏度公式和伴随变量公式。基于现有的Delaunay三角剖分技术,采用Swapping Algorithm更新有限元网格。最后将有限元方法、基于最速下降法的灵敏度...
  • 专题1 无约束优化.pdf

    2020-04-12 00:42:03
    本专题从最简单的一维线性搜索(黄金分割法、斐波那契数列法、牛顿法、割线法)开始,然后介绍多元函数的搜索方法,包括最速下降法和牛顿法,最后针对牛顿法需要计算Hessen矩阵的特点对牛顿法的改进提出了一些想法...
  • 机器学习面试集

    2018-05-14 21:42:43
    1.牛顿下降法和梯度下降法(最速下降法)的速度的比较公式推导牛顿法是二阶收敛,梯度下降是一阶收敛,所以牛顿法就更快。如果更通俗地说的话,比如你想找一条最短的路径走到一个盆地的最底部,梯度下降法每次只从你...
  • 逻辑回归算法-CSDN

    2016-01-27 22:10:44
    Logistic Regression算法分析及Java代码只是从以下几个方面学习,现在还只是学习阶段,转载分析...最速下降法原理 (原理分析及其他算法) 遍历一个矩阵:public static void matrixTraverse(Matrix matrix) { //遍历
  • 运用统一色噪声近似理论、最速下降法理论和随机共振的双态理论推导出在色散型光学双稳系统中由于注入相干光的强度和位相的波动所引起的乘性噪声并在外部周期性弱信号共同驱动下系统的平均首次通过时间和系统信噪比的...
  • 字节跳动三维视觉(一面) 1. 为什么使用分解后的最后一列是的解? 答:推导过程如下: 可以求取的最小二乘解,因此问题转换...最速下降法的本质: 非线性优化的本质是:如何寻找合适的步长和梯度下降方向。 下...
  • 采用状态方程有约束最速下降法(CSDSE)对控制系统控制参数进行优化,建立了直流电机位置控制系统性能优化的数学模型,结合具体的位置控制系统推导CSDSE优化方法,并给出优化程序的编制步骤。伪微分反馈直流电机位置...
  • 第三节主要讲解了VIO中基于优化的 IMU 与视觉信息融合,首先回顾了最小二乘问题,包括最速下降法,牛顿法,高斯牛顿,LM等;然后讲解了VIO残差函数的构建,以及预计分量的构建和模型;最后推导了残差Jacobian 1 ...
  • 二阶优化算法Natural Gradient Descent,是从分布空间推导最速梯度下降方向的方法,和牛顿方法有非常紧密的联系。Fisher Information Matrix往往可以用来代替牛顿的Hessian矩阵计算。下面详细道来。
  • 引入了二次形式的概念并用于推导最速下降、共轭方向和共轭梯度的方法。 特征向量被解释并用于检查雅可比方法、最速下降和共轭梯度的收敛性。 其他主题包括预处理和非线性共轭梯度方法。 我已竭尽全力使本文易于阅读...

空空如也

空空如也

1 2
收藏数 36
精华内容 14
关键字:

最速下降法推导