精华内容
下载资源
问答
  • 梯度下降法迭代结束的条件

    万次阅读 2015-01-09 17:01:30
    如果是求极小值,沿着梯度相反的方向迭代即可,即梯度下降法梯度下降法(梯度上升法应该也适用)迭代结束的条件,常用的有两种: 一、定义一个合理的阈值,当两次迭代之间的差值小于该阈值时,迭代结束。 二、...

    梯度的方向总是函数值越来越大的方向,如果是求极大值,沿着梯度的方向迭代接口;如果是求极小值,沿着梯度相反的方向迭代即可,即梯度下降法。

    梯度下降法(梯度上升法应该也适用)迭代结束的条件,常用的有两种:

    一、定义一个合理的阈值,当两次迭代之间的差值小于该阈值时,迭代结束。

    二、设置一个大概的迭代步数,比如1000或500,梯度下降法最终的迭代肯定会收敛,只要达到相应迭代次数,多了也没关系。因为迭代次数多了后,在

    到达极值点时,函数对变量的导数已近乎为0,即使过了极值点,导数就变为正数了,之前的导数为负数。这个时候,变量x的值减去步长与导数的乘

    积反倒变小了。所以即使步数多了,结果也基本上就在极值点处左右徘徊,几乎等于极值点,因此没有问题。

    展开全文
  • 梯度下降法、牛顿迭代法和坐标下降法  最优化方法是一种数学方法,它是研究在给定约束之下如何寻求某些因素(的量),以使某一(或某些)指标达到最优的一些学科的总称。大部分的机器学习算法的本质都是建立优化模型,...

    梯度下降法、牛顿迭代法和坐标下降法

           最优化方法是一种数学方法,它是研究在给定约束之下如何寻求某些因素(的量),以使某一(或某些)指标达到最优的一些学科的总称。大部分的机器学习算法的本质都是建立优化模型,通过最优化方法对目标函数(或损失函数)进行优化,从而训练出最好的模型。常见的最优化方法有梯度下降法、牛顿法和拟牛顿法、坐标下降法等等。

    梯度下降法

    梯度下降法是迭代法的一种,可以用于求解最小二乘问题(线性和非线性都可以)。在求解机器学习算法的模型参数,即无约束优化问题时,梯度下降(Gradient Descent)是最常采用的方法之一,另一种常用的方法是最小二乘法。在求解损失函数的最小值时,可以通过梯度下降法来一步步的迭代求解,得到最小化的损失函数和模型参数值。反过来,如果我们需要求解损失函数的最大值,这时就需要用梯度上升法来迭代了。在机器学习中,基于基本的梯度下降法发展了两种梯度下降方法,分别为随机梯度下降法和批量梯度下降法。

    示例:

    只含有一个特征的线性回归,此时线性回归的假设函数是:

    其中 i=1,2,...,m表示样本数。

       

    对应的目标函数(代价函数)即为:

    下图为 J(θ0+θ1) 与参数θ0θ1的关系的图:

    1、批量梯度下降(Batch Gradient Descent,BGD)

       批量梯度下降法是最原始的形式,它是指在每一次迭代时使用所有样本来进行梯度的更新。从数学上理解如下:

    1. 对目标函数求偏导:

     

    其中 i=1,2,...,m表示样本数, j=0,表示特征数,这里我们使用了偏置项x0(i)=1

     

    1. 每次迭代对参数进行更新:

     

    注意这里更新时存在一个求和函数,即为对所有样本进行计算处理,可与下文SGD法进行比较。
    伪代码形式为:  

    其中α表示学习率,一般根据经验进行设置。

    优点:
    (1)一次迭代是对所有样本进行计算,此时利用矩阵进行操作,实现了并行。  
    (2)由全数据集确定的方向能够更好地代表样本总体,从而更准确地朝向极值所在的方向。当目标函数为凸函数时,BGD一定能够得到全局最优。  
    缺点:
    (1)当样本数目m很大时,每迭代一步都需要对所有样本计算,训练过程会很慢。
    从迭代的次数上来看,BGD迭代的次数相对较少。其迭代的收敛曲线示意图可以表示如下:  

     

    2、随机梯度下降(Stochastic Gradient Descent,SGD)

     梯度下降法不同于批量梯度下降,随机梯度下降是每次迭代使用一个样本来对参数进行更新。使得训练速度加快。
        样本的目标函数为:

    1. 对目标函数求偏导:

     

    1. 参数更新:

    注意,这里不再有求和符号

    伪代码形式为:

     

    优点:
    (1)由于不是在全部训练数据上的损失函数,而是在每轮迭代中,随机优化某一条训练数据上的损失函数,这样每一轮参数的更新速度大大加快。  
      缺点:
    (1)准确度下降。由于即使在目标函数为强凸函数的情况下,SGD仍旧无法做到线性收敛。  
    (2)可能会收敛到局部最优,由于单个样本并不能代表全体样本的趋势。  
    (3)不易于并行实现。 

    3、小批量梯度下降(Mini-Batch Gradient Descent, MBGD

    小批量梯度下降是对批量梯度下降以及随机梯度下降的一个折中办法。其思想是:每次迭代 使用 ** batch_size** 个样本来对参数进行更新。
    这里我们假设batchsize=10 ,样本数 m=1000 
    伪代码形式为:  

     

    优点:
    (1)通过矩阵运算,每次在一个batch上优化神经网络参数并不会比单个数据慢太多。  
    (2)每次使用一个batch可以大大减小收敛所需要的迭代次数,同时可以使收敛到的结果更加接近梯度下降的效果。(比如上例中的30W,设置batch_size=100时,需要迭代3000次,远小于SGD的30W次)  
    (3)可实现并行化。  
      缺点:
    (1)batch_size的不当选择可能会带来一些问题。  

     

    batcha_size的选择带来的影响:
    (1)在合理地范围内,增大batch_size的好处:  
    a. 内存利用率提高了,大矩阵乘法的并行化效率提高。    
    b. 跑完一次 epoch(全数据集)所需的迭代次数减少,对于相同数据量的处理速度进一步加快。    
    c. 在一定范围内,一般来说 Batch_Size 越大,其确定的下降方向越准,引起训练震荡越小。  

      
    (2)盲目增大batch_size的坏处:  
    a. 内存利用率提高,但是内存容量可能不足。    
    b. 跑完一次 epoch(全数据集)所需的迭代次数减少,要想达到相同的精度,其所花费的时间大大增加了,从而对参数的修正也就显得更加缓慢。    
    c. Batch_Size 增大到一定程度,其确定的下降方向已经基本不再变化。    

     

     

     

     

     

    牛顿迭代法

    牛顿法的基本思想是利用迭代点http://latex.codecogs.com/gif.latex?x_k处的一阶导数(梯度)和二阶导数(Hessen矩阵)对目标函数进行二次函数近似,然后把二次模型的极小点作为新的迭代点,并不断重复这一过程,直至求得满足精度的近似极小值。牛顿法的速度相当快,而且能高度逼近最优值。牛顿法分为基本的牛顿法和全局牛顿法。

     

    • 牛顿法计算函数零点

    首先,选择一个接近函数f(x)零点的x0,计算相应的f(x0) 和切线斜率 f'(x0)(这里 f'表示函数f的导数)。然后我们计算穿过点 (x0,f(x0))并且斜率为f'(x0) 的直线和x轴的交点的x坐标,也就是求如下方程的解:

     

    我们将新求得的点的x坐标命名为x_1,通常 x_1会比x_{0}更接近方程 f(x)=0的解。因此我们现在可以利用x_1开始下一轮迭代。迭代公式可化简为如下所示:

    已有证明牛顿迭代法的二次收敛必须满足以下条件:

    1. f'(x)≠ 0};
    2. 对于所有x ∈I,其中 I为区间[α − r, α + r],且x0在区间I内,即 r>=|a-x0|

    3、对于所有x ∈I,f''(x)是连续的;

    4、x0足够接近根 α。

     

    • 牛顿法求解最优化问题
    1. 考虑一维的简单情形

         简单情形N=1(此时目标函数f(X)  变为f(x) .牛顿法的基本思想是:在现有极小点估计值的附近对f(x)做二阶泰勒展开,进而找到极小点的下一个估计值。

      f(x) 为当前的极小点估计值,则:

    表示f(x) xk 附近的二阶泰勒展开式(其中略去了关于x-xk  的高阶无穷小项)。

    由于求的是最值,由极值必要条件可知, φ(x)应满足:

    即:

    解得:

    于是,若给定初始值x0,则可以构造如下的迭代格式:

    产生序列{xk}来逼近f(x)的极小点。在一定条件下,{xk}可以收敛到f(x)的极小点。

    1. 对于N>1的情形,二阶泰勒展开式可以做推广,此时:

     

    注意:

    1∇f和∇2f中的元素均为关于x的函数,以下分别将其简记为g和H。

    2、f(xk)和∇2f(xk)表示将x取为xk后得到的实值向量和矩阵,以下分别将其简记为gkHk

     

    同样地,由于是求极小点,极值必要条件要求它为φ(x)的驻点,即:∇φx=0

     

     

    对泰勒展开使用梯度算子得:

    进一步,若矩阵HK非奇异,则可解得:

    于是,若给定初始值x0,则同样可以构造出迭代格式:

    这就是原始的牛顿迭代法,其迭代格式中的搜索方向dk=-Hk-1gk称为牛顿方向.

    牛顿法的优点:

      当目标函数是二次函数时,由于二次泰勒展开函数与原目标函数不是近似而是完全相同的二次式,海森矩阵退化成一个常数矩阵,从任一初始点出发,利用xk+1的迭代式,只需一步迭代即可达到x的极小点x*,因此牛顿法是一种具有二次收敛性的算法。对于非二次函数,若函数的二次性态较强,或迭代点已进入极小点的领域,则其收敛速度也是很快的,这是牛顿法的主要优点.

     

    牛顿法的缺点:

      但原始牛顿法由于迭代公式中没有步长因子,而是定步长迭代,对于非二次目标函数来说,有时会使函数值上升,即出现f(xk+1)>f(xk)的情况,这表明原始牛顿法不能保证函数值稳定地下降.在严重的情况下甚至可能造成迭代点列{xk}的发散而导致计算失败.

     

    坐标下降法

    坐标下降优化方法是一种非梯度优化算法。为了找到一个函数的局部极小值,在每次迭代中可以在当前点处沿一个坐标方向进行一维搜索。在整个过程中循环使用不同的坐标方向。一个周期的一维搜索迭代过程相当于一个梯度迭代。

    坐标下降优化方法为了找到一个函数的局部极小值,在每次迭代中可以在当前点处沿一个坐标方向进行一维搜索。在整个过程中循环使用不同的坐标方向。一个周期的一维搜索迭代过程相当于一个梯度迭代。 其实,gradient descent 方法是利用目标函数的导数(梯度)来确定搜索方向的,而该梯度方向可能不与任何坐标轴平行。而coordinate descent方法是利用当前坐标系统进行搜索,不需要求目标函数的导数,只按照某一坐标方向进行搜索最小值。坐标下降法在稀疏矩阵上的计算速度非常快,同时也是Lasso回归最快的解法。

     

    算法描述:

    坐标下降法基于的思想是多变量函数可以通过每次沿一个方向优化来获取最小值。与通过梯度获取最速下降的方向不同,在坐标下降法中,优化方向从算法一开始就予以固定。例如,可以选择线性空间的一组基作为搜索方向。 在算法中,循环最小化各个坐标方向上的目标函数值。亦即,如果已给定,那么,的第个维度为

    因而,从一个初始的猜测值以求得函数的局部最优值,可以迭代获得的序列。

    通过在每一次迭代中采用一维搜索,可以很自然地获得不等式

    可以知道,这一序列与最速下降具有类似的收敛性质。如果在某次迭代中,函数得不到优化,说明一个驻点已经达到。

    这一过程可以用下图表示。

    梯度下降法、牛顿法、和坐标下降法优缺点对比

    1、梯度下降法

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

    梯度下降法的优化思想:用当前位置负梯度方向作为搜索方向,因为该方向为当前位置的最快下降方向,所以也被称为是“最速下降法”。最速下降法越接近目标值,步长越小,前进越慢。

    缺点:

    靠近极小值时收敛速度减慢,求解需要很多次的迭代;

    直线搜索时可能会产生一些问题;

    可能会“之字形”地下降。

     

    2、牛顿法

    牛顿法最大的特点就在于它的收敛速度很快。

    优点:二阶收敛,收敛速度快;

    缺点:

    牛顿法是一种迭代算法,每一步都需要求解目标函数的Hessian矩阵的逆矩阵,计算比较复杂。

    牛顿法收敛速度为二阶,对于正定二次函数一步迭代即达最优解。

    牛顿法是局部收敛的,当初始点选择不当时,往往导致不收敛;

    二阶海塞矩阵必须可逆,否则算法进行困难。

    关于牛顿法和梯度下降法的效率对比:

    从本质上去看,牛顿法是二阶收敛,梯度下降是一阶收敛,所以牛顿法就更快。如果更通俗地说的话,比如你想找一条最短的路径走到一个盆地的最底部,梯度下降法每次只从你当前所处位置选一个坡度最大的方向走一步,牛顿法在选择方向时,不仅会考虑坡度是否够大,还会考虑你走了一步之后,坡度是否会变得更大。所以,可以说牛顿法比梯度下降法看得更远一点,能更快地走到最底部。(牛顿法目光更加长远,所以少走弯路;相对而言,梯度下降法只考虑了局部的最优,没有全局思想。)

     

    3、坐标下降法求最值问题和梯度下降法对比

    1. 坐标下降法在每次迭代中在当前点处沿一个坐标方向进行一维搜索 ,固定其他的坐标方向,找到一个函数的局部极小值。而梯度下降总是沿着梯度的负方向求函数的局部最小值。
    2. 坐标下降优化方法是一种非梯度优化算法。在整个过程中依次循环使用不同的坐标方向进行迭代,一个周期的一维搜索迭代过程相当于一个梯度下降的迭代。
    3. 梯度下降是利用目标函数的导数来确定搜索方向的,该梯度方向可能不与任何坐标轴平行。而坐标下降法法是利用当前坐标方向进行搜索,不需要求目标函数的导数,只按照某一坐标方向进行搜索最小值。
    4. 两者都是迭代方法,且每一轮迭代,都需要O(mn)的计算量(m为样本数,n为系数向量的维度)

     

    实验效果对比

    1、线性问题拟合y = 3*x1 + 4*x2

    数据集:代码生成的1000个样本点 X

    对比算法:

        1、随机梯度下降

    2、批量梯度下降

    3、小批量梯度下降

    对别内容:

        1、生成参数

        2、算法迭代次数

    3、算法运行时间

    实验结果:

     

    1、非线性问题拟合最优化

    已知函数f(x1,x2)=(1 - x1)2 + 100 * (x2 - x12)2

    是光滑的凸函数,且只有一个最小值点f(1,1)=0

    对比算法:

        1、随机梯度下降

    2、牛顿法

    对别内容:

        1、精度损失

        2、最优点坐标

    3、算法运行时间

    实验结果:

     

    代码实现:

    from mpl_toolkits.mplot3d import axes3d
    import matplotlib.pyplot as plt
    from matplotlib import cm
    import numpy as np
    import random
    import time
    def print_Chart():
        # fig = plt.figure()
        fig = plt.figure()
        ax = fig.add_subplot(111, projection='3d')
        ax.set_xlabel('X')
        ax.set_ylabel('Y')
        ax.set_zlabel('Z')
        # Make data
        X = np.linspace(-2, 2, 100)
        Y = np.linspace(-2,2, 100)
        X, Y = np.meshgrid(X, Y)
        Z =(1-X)**2+(X-Y**2)**2*100
        # Plot the surface
        ax.plot_surface(X, Y, Z, color='g')
        plt.show()
    
    def cal_rosenbrock(x1, x2):
        """
        计算rosenbrock函数的值
        :param x1:
        :param x2:
        :return:
        """
        return (1 - x1) ** 2 + 100 * (x2 - x1 ** 2) ** 2
    
    def cal_rosenbrock_prax(x1, x2):
        """
        对x1求偏导
        """
        return -2 + 2 * x1 - 400 * (x2 - x1 ** 2) * x1
    
    def cal_rosenbrock_pray(x1, x2):
        """
        对x2求偏导
        """
        return 200 * (x2 - x1 ** 2)
    
    def gradient_descent(max_iter_count=100000, step_size=0.001,x1=0.0,x2=0.0):
        '''
        梯度下降
        最小值为0
        默认初试点(0,0)
        :param max_iter_count:
        :param step_size:
        :param x1:
        :param x2:
        :return:
        '''
        pre_x = np.array([x1,x2])
        loss = 10
        iter_count = 0
        while loss > 0.001 and iter_count < max_iter_count:
            error = np.zeros((2,), dtype=np.float32)
            error[0] = cal_rosenbrock_prax(pre_x[0], pre_x[1])
            error[1] = cal_rosenbrock_pray(pre_x[0], pre_x[1])
    
            for j in range(2):
                pre_x[j] -= step_size * error[j]
    
            loss = cal_rosenbrock(pre_x[0], pre_x[1])  # 目标值为0
    
            print("iter_count: ", iter_count, "the loss:", loss)
            iter_count += 1
        return loss,pre_x
    
    def h(x1=0.0,x2=0.0,r=2,c=2):
        _h=np.zeros((r,c),dtype=np.float32)
        _h[0][0]=2+1200*x1**2-400*x2
        _h[0][1]=-400*x1
        _h[1][0]=_h[0][1]
        _h[1][1]=200
        return _h
    
    def g(x1=0.0,x2=0.0):
        return np.array([cal_rosenbrock_prax(x1,x2),cal_rosenbrock_pray(x1,x2)])
    
    
    def newton(max_iter_count=100000,x1=0.0,x2=0.0):
        pre_x = np.array([x1,x2])
        loss = 10
        iter_count = 0
        while loss > 0.001 and iter_count < max_iter_count:
            h_inv=np.linalg.inv(h(x1=pre_x[0],x2=pre_x[1]))
            _g=np.matrix(g(pre_x[0],pre_x[1]).reshape([2,1]))
            t=h_inv*_g
            for i in range(t.size):
                pre_x[i]-=t[i]
            loss = cal_rosenbrock(pre_x[0], pre_x[1])  # 目标值为0
            print("iter_count: ", iter_count, "the loss:", loss)
            iter_count += 1
        return loss,pre_x
    
    
    
    '''
    BGD(批量梯度下降法)
    '''
    def gen_line_data(sample_num=1000):
        """
        y = 3*x1 + 4*x2
        :return:
        """
        x1 = np.linspace(0, 9, sample_num)
        x2 = np.linspace(4, 13, sample_num)
        x = np.concatenate(([x1], [x2]), axis=0).T
        y = np.dot(x, np.array([3, 4]).T)  # y 列向量
        return x, y
    
    def bgd(samples, y, step_size=0.01, max_iter_count=10000):
        '''
        批量梯度下降
        :param samples:
        :param y:
        :param step_size:
        :param max_iter_count:
        :return:
        '''
        sample_num, dim = samples.shape
        y = y.flatten()
        w = np.ones((dim,), dtype=np.float32)
        loss = 10
        iter_count = 0
        while loss > 0.001 and iter_count < max_iter_count:
            loss = 0 #每次迭代从新计算受损失值
            error = np.zeros((dim,), dtype=np.float32)
            '''
            遍历所有样本后更新一次参数
            '''
            for i in range(sample_num):
                predict_y = np.dot(w.T, samples[i])
                for j in range(dim):
                    error[j] += (y[i] - predict_y) * samples[i][j]
    
            for j in range(dim):
                w[j] += step_size * error[j] / sample_num
    
            for i in range(sample_num):
                predict_y = np.dot(w.T, samples[i])
                error = (1 / (sample_num * dim)) * np.power((predict_y - y[i]), 2)
                loss += error
    
            print("iter_count: ", iter_count, "the loss:", loss)
            iter_count += 1
        return w,iter_count
    
    def mbgd(samples, y, step_size=0.01, max_iter_count=10000, batch_size=0.2):
        """
        MBGD(Mini-batch gradient descent)小批量梯度下降:每次迭代使用b组样本
        :param samples:
        :param y:
        :param step_size:
        :param max_iter_count:
        :param batch_size:
        :return:
        """
        sample_num, dim = samples.shape
        y = y.flatten()
        w = np.ones((dim,), dtype=np.float32)
        # batch_size = np.ceil(sample_num * batch_size)
        loss = 10
        iter_count = 0
        while loss > 0.001 and iter_count < max_iter_count:
            loss = 0
            error = np.zeros((dim,), dtype=np.float32)
    
            # batch_samples, batch_y = select_random_samples(samples, y,
            # batch_size)
    
            index = random.sample(range(sample_num),
                                  int(np.ceil(sample_num * batch_size)))
            batch_samples = samples[index]
            batch_y = y[index]
    
            for i in range(len(batch_samples)):
                predict_y = np.dot(w.T, batch_samples[i])
                for j in range(dim):
                    error[j] += (batch_y[i] - predict_y) * batch_samples[i][j]
    
            for j in range(dim):
                w[j] += step_size * error[j] / sample_num
    
            for i in range(sample_num):
                predict_y = np.dot(w.T, samples[i])
                error = (1 / (sample_num * dim)) * np.power((predict_y - y[i]), 2)
                loss += error
    
            print("iter_count: ", iter_count, "the loss:", loss)
            iter_count += 1
        return w,iter_count
    
    def sgd(samples, y, step_size=0.01, max_iter_count=10000):
        """
        随机梯度下降法,每读取一次样本后都对参数进行更新
        :param samples: 样本
        :param y: 结果value
        :param step_size: 每一接迭代的步长
        :param max_iter_count: 最大的迭代次数
        :param batch_size: 随机选取的相对于总样本的大小
        :return:
        """
        sample_num, dim = samples.shape
        y = y.flatten()
        w = np.ones((dim,), dtype=np.float32)
        loss = 10
        iter_count = 0
        while loss > 0.001 and iter_count < max_iter_count:
            loss = 0
            error = np.zeros((dim,), dtype=np.float32)
            for i in range(sample_num):
                predict_y = np.dot(w.T, samples[i])
                for j in range(dim):
                    '''
                    每次读取一个样本后对参数进行更新,
                    下一个样本使用更新后的参数进行估计
                    '''
                    error[j] += (y[i] - predict_y) * samples[i][j]
                    w[j] += step_size * error[j] / sample_num
    
            for i in range(sample_num):
                predict_y = np.dot(w.T, samples[i])
                error = (1 / (sample_num * dim)) * np.power((predict_y - y[i]), 2)
                loss += error
    
            print("iter_count: ", iter_count, "the loss:", loss)
            iter_count += 1
        return w,iter_count
    
    '''
    在使用坐标下降算法
    对x1求偏导为0时,无法显示的用x2来表示x1
    因此该方程不适用于坐标下降算法
    
    '''
    # def coordinate_descent(max_iter_count=100000,x1=0.0,x2=0.0):
    #
    #     def cordinate_x1(x1=0.0,x2=0.0):
    #
    #     def cordinate_x1(x1=0.0,x2=0.0):
    #
    #     pre_x = np.array([x1,x2])
    #     loss = 10
    #     iter_count = 0
    #     while loss > 0.001 and iter_count < max_iter_count:
    #         h_inv=np.linalg.inv(h(x1=pre_x[0],x2=pre_x[1]))
    #         _g=np.matrix(g(pre_x[0],pre_x[1]).reshape([2,1]))
    #         t=h_inv*_g
    #         for i in range(t.size):
    #             pre_x[i]-=t[i]
    #         loss = cal_rosenbrock(pre_x[0], pre_x[1])  # 目标值为0
    #         print("iter_count: ", iter_count, "the loss:", loss)
    #         iter_count += 1
    #     return loss,pre_x
    
    
    
    if __name__ == '__main__':
        # print_Chart()
    
        # 批量梯度下降,线性问题
        samples, y = gen_line_data()
        time1=time.time()
        w1,iter_count1 = bgd(samples, y)
        cost_time1=time.time()-time1
        print('批量梯度下降结果:','  参数:',w1,'  迭代次数:',iter_count1,'  使用时间:',cost_time1,'sec')
    
        time2=time.time()
        w2,iter_count2=mbgd(samples,y)
        cost_time2=time.time()-time2
        print('小批量梯度下降结果:','  参数:',w2,'  迭代次数:',iter_count2,'  使用时间:',cost_time2,'sec')
    
        time3=time.time()
        w3,iter_count3=sgd(samples,y)
        cost_time3=time.time()-time3
    
        print('=====================运行结果对比===========================')
        print('批量梯度下降结果:','  参数:',w1,'  迭代次数:',iter_count1,'  使用时间:',cost_time1,'sec')
        print('小批量梯度下降结果:','  参数:',w2,'  迭代次数:',iter_count2,'  使用时间:',cost_time2,'sec')
        print('随机梯度下降结果:','  参数:',w3,'  迭代次数:',iter_count3,'  使用时间:',cost_time3,'sec')
    
        '''
        非线性问题
        '''
        # 梯度下降 非线性问题
        time4=time.time()
        loss,coordinate=gradient_descent(x1=1.5,x2=1.5)
        cost_time4=time.time()-time4
        print('随机梯度下降非线性问题运行结束:\n','精度损失:',loss,'\n最优点坐标:',coordinate, '\n使用时间:',cost_time4,'sec')
    
    
        # 牛顿法 非线性问题
        time5=time.time()
        loss,pre_x=newton()
        cost_time5=time.time()-time4
        print('牛顿法非线性问题运行结束:\n','精度损失:',loss,'\n最优点坐标:',pre_x, '\n使用时间:',cost_time5,'sec')
    展开全文
  • 前文介绍了梯度下降法,其每次迭代均需使用全部的样本,因此计算量巨大。就此,提出了基于单个样本的随机梯度下降法(Stochastic gradient descent,SGD)和基于部分样本的小批量梯度下降法(Mini-Batch gradient ...

    前文介绍了梯度下降法,其每次迭代均需使用全部的样本,因此计算量巨大。就此,提出了基于单个样本的随机梯度下降法(Stochastic gradient descent,SGD)和基于部分样本的小批量梯度下降法(Mini-Batch gradient descent,Mini-batch gradient descent)。

    一、随机梯度下降法

    随机梯度下降法,即在每次梯度更新过程中仅使用某个随机样本点:θ:=θα(θTxiyi)xi\boldsymbol \theta:=\boldsymbol \theta-\alpha (\boldsymbol \theta^T\boldsymbol x_i-y_i)\boldsymbol x_i

    随机梯度下降法虽然很好的解决了每次都要使用全量样本的问题,但由于其在样本选择时的随机性,会导致每一步并不是沿着全局梯度下降的方向推进,因此尽管最终结果会逐渐走向局部最小值,但过程较为波折,且最终结果会在最小值附近徘徊。

    二、小批量梯度下降法

    小批量梯度下降法是随机梯度下降法和随机梯度下降法的折中,即每次选取部分数据样本进行梯度的迭代。其迭代流程为:

    for i in N epoches:     # 每个epoch使用全部的数据样本
    	for j in m batches:     # 每个batch间的数据都是不同,每个batch内的数据都不重复
    		t:=t-a*sum(t*x-y)*x
    

    三、三种形式梯度下降法的对比

    综上所述,梯度下降法包括三种形式:批量梯度下降法、随机梯度下降法和小批量梯度下降法。其迭代过程见下方示意图:
    在这里插入图片描述

    三种形式梯度下降的主要优缺点在于:

    1)梯度下降法
    优点:全局最优解,能保证每一次更新权值,都能降低损失函数;在计算各样本的损失时易于并行实现。

    缺点:需要用到全量样本,对内存的要求高,同时计算缓慢。

    2)随机梯度下降法
    优点:每次迭代训练速度快

    缺点:搜索方向随机性强,迭代步数多,每一步并不一定指向最优化方向。最终结果并非全局最优,准确性略弱。

    3)小批量梯度下降法
    克服上面两种方法的缺点,又同时兼顾两种方法的优点。

    因此在实际使用中:

    1)一般情况下,优先采用小批量梯度下降法,在很多情况下SGD默认指代小批量梯度下降法;

    2)若数据量小,可直接采用批量梯度下降法;

    3)若数据量非常大,或者需要在线学习,可考虑使用随机梯度下降法。

    展开全文
  • SGD(Stochastic Gradient Descent,随机梯度下降法)和New-ton Method(牛顿迭代法) 梯度下降法,牛顿法,高斯-牛顿迭代法,附代码实现:https://blog.csdn.net/piaoxuezhong/article/details/60135153 梯度下...

    我一直以为两者是相同的。。。原来SGD是一阶梯度,而牛顿迭代法是二阶梯度。

    SGD(Stochastic Gradient Descent,随机梯度下降法)和New-ton Method(牛顿迭代法) 

    梯度下降法,牛顿法,高斯-牛顿迭代法,附代码实现:https://blog.csdn.net/piaoxuezhong/article/details/60135153

    梯度下降法与牛顿法的解释与对比:https://www.cnblogs.com/happylion/p/4172632.html

    梯度下降法、牛顿迭代法、共轭梯度法:https://wenku.baidu.com/view/81ba70fc915f804d2a16c149.html

    梯度下降和牛顿迭代:https://blog.csdn.net/qjzcy/article/details/51946304

    SGD(Stochastic Gradient Descent,随机梯度下降法)中随机一词是指的样本随机选取,没有特别含义。

    Stochastic gradient descent (often shortened to SGD), also known as incremental gradient descent, is a stochastic approximation of the gradient descent optimization and iterative method for minimizing an objective function that is written as a sum of differentiable functions. In other words, SGD tries to find minima or maxima by iteration.

    SGD,又称为增量梯度递减,是一种随机梯度下降优化逼近以及使目标函数最小的迭代方法,目标函数可写为差分函数之和。换句话说,SGD努力通过迭代寻找最小或最大。

    Both statistical estimation and machine learning consider the problem of minimizing an objective function that has the form of a sum:

    统计估计和机器学习都考虑最小化目标函数的问题:

    where the parameter w which minimizes Q(w) is to be estimated. Each summand function Qi is typically associated with the  i-th observation in the data set (used for training).

    其中使Q(w)最小的参数w是需要估计的。每一个相加的sum函数Qi一般与数据集中的第i个观测(用于训练的数据)相关。

    In classical statistics, sum-minimization problems arise in least squares and in maximum-likelihood estimation (for independent observations). The general class of estimators that arise as minimizers of sums are called M-estimators. However, in statistics, it has been long recognized that requiring even local minimization is too restrictive for some problems of maximum-likelihood estimation.[1] Therefore, contemporary statistical theorists often consider stationary points of the likelihood function (or zeros of its derivative, the score function, and other estimating equations).

    在典型的统计学中,总和最小问题出现在最小二乘和最大似然估计(独立观测)中。通常的一类作为总和最小的估计者叫M-估计者。然而,在统计学中,一直以来认识到哪怕是要求局部最小对于最大似然估计也太严格了。因此,当代统计理论者通常考虑似然函数的平稳点(或导数为零的点,得分函数,和其他的估计等式)。

    The sum-minimization problem also arises for empirical risk minimization. In this case,  Qi(w) is the value of the loss function at i-th example, and Q(w) is the empirical risk.

    这类总和最小问题也出现在最小风险估计中。在这种例子中,Qi(w)是损失函数在第i个例子的值,而Q(w)是最小风险。

    When used to minimize the above function, a standard (or "batch") gradient descent method would perform the following iterations :

    当用于最小化上式时,一个标准的(或“包”)梯度下降方法将如下面的迭代进行:

    (推导方法参加机器学习课程)

    where η is a step size (sometimes called the learning rate in machine learning).

    其中η是步长(有时在机器学习中称为学习率)。

    In many cases, the summand functions have a simple form that enables inexpensive evaluations of the sum-function and the sum gradient. For example, in statistics, one-parameter exponential families allow economical function-evaluations and gradient-evaluations.

    在很多情况下,被加函数有简单的形式,使不费时。

    However, in other cases, evaluating the sum-gradient may require expensive evaluations of the gradients from all summand functions. When the training set is enormous and no simple formulas exist, evaluating the sums of gradients becomes very expensive, because evaluating the gradient requires evaluating all the summand functions' gradients. To economize on the computational cost at every iteration, stochastic gradient descent samples a subset of summand functions at every step. This is very effective in the case of large-scale machine learning problems.

    Newton's method(牛顿迭代法)

    牛顿迭代法(Newton's method)又称为牛顿-拉夫逊(拉弗森)方法(Newton-Raphson method),它是牛顿在17世纪提出的一种在实数域和复数域上近似求解方程的方法。多数方程不存在求根公式,因此求精确根非常困难,甚至不可能,从而寻找方程的近似根就显得特别重要。方法使用函数f(x)的泰勒级数的前面几项来寻找方程f(x) = 0的根。牛顿迭代法是求方程根的重要方法之一,其最大优点是在方程f(x) = 0的单根附近具有平方收敛,而且该法还可以用来求方程的重根、复根,此时线性收敛,但是可通过一些方法变成超线性收敛。另外该方法广泛用于计算机编程中。

    设r是  的根,选取  作为r的初始近似值,过点  做曲线  的切线L,L的方程为  ,求出L与x轴交点的横坐标  ,称x1为r的一次近似值。过点 做曲线  的切线,并求该切线与x轴交点的横坐标  ,称  为r的二次近似值。重复以上过程,得r的近似值序列,其中,  称为r的  次近似值,上式称为牛顿迭代公式。

    用牛顿迭代法解非线性方程,是把非线性方程  线性化的一种近似方法。把  在点  的某邻域内展开成泰勒级数  ,取其线性部分(即泰勒展开的前两项),并令其等于0,即  ,以此作为非线性方程  的近似方程,若  ,则其解为  , 这样,得到牛顿迭代法的一个迭代关系式:  。
    已经证明,如果是连续的,并且待求的零点是孤立的,那么在零点周围存在一个区域,只要初始值位于这个邻近区域内,那么牛顿法必定收敛。 并且,如果不为0, 那么牛顿法将具有平方收敛的性能. 粗略的说,这意味着每迭代一次,牛顿法结果的有效数字将增加一倍。
    以上是关于求方程的根,那么求方程的参数呢?
    设方程为Q(w)
    那么怎么根据样本求w?Q(w,x)=y
    迭代法求方程参数就两步:(1)找到搜索方向;(2)迭代的步长。应该先采集样本并标上标签y吧。
    对泰勒公式上的导数再用一次泰勒公式则可以得到

    为什么非得用二次泰勒公式而不用第一次的泰勒公式近似法呢(牛顿迭代用于求近似和求最优以及与泰勒公式的关系)?(函数为Loss函数,求Loss最小)Loss=y-Estimate(w,x)

    方向一定要是使Loss最小的方向。也就是梯度方向,那么大小呢?步长。(梯度与导数的关系)

    那么梯度下降法跟牛顿迭代法有什么不同呢?

    梯度下降是迭代法的一种,可以用于求解最小二乘问题(线性和非线性都可以)。在求解机器学习算法的模型参数,即无约束优化问题时,梯度下降(Gradient Descent)是最常采用的方法之一,另一种常用的方法是最小二乘法。在求解损失函数的最小值时,可以通过梯度下降法来一步步的迭代求解,得到最小化的损失函数和模型参数值。反过来,如果我们需要求解损失函数的最大值,这时就需要用梯度上升法来迭代了。在机器学习中,基于基本的梯度下降法发展了两种梯度下降方法,分别为随机梯度下降法和批量梯度下降法。

    梯度:对于可微的数量场  ,以  为分量的向量场称为f的梯度或斜量。梯度下降法(gradient descent)是一个最优化算法,常用于机器学习和人工智能当中用来递归性地逼近最小偏差模型。
    顾名思义,梯度下降法的计算过程就是沿梯度下降的方向求解极小值(也可以沿梯度上升方向求解极大值)。
    其迭代公式为  ,其中  代表梯度负方向,  表示梯度方向上的搜索步长。梯度方向我们可以通过对函数求导得到,步长的确定比较麻烦,太大了的话可能会发散,太小收敛速度又太慢。一般确定步长的方法是由线性搜索算法来确定,即把下一个点的坐标看做是ak+1的函数,然后求满足f(ak+1)的最小值的 即可。
    因为一般情况下,梯度向量为0的话说明是到了一个极值点,此时梯度的幅值也为0.而采用梯度下降算法进行最优化求解时,算法迭代的终止条件是梯度向量的幅值接近0即可,可以设置个非常小的常数阈值。
    举一个非常简单的例子,如求函数  的最小值。
    利用梯度下降的方法解题步骤如下:
    1、求梯度, 
    2、向梯度相反的方向移动  ,如下
     ,其中,  为步长。如果步长足够小,则可以保证每一次迭代都在减小,但可能导致收敛太慢,如果步长太大,则不能保证每一次迭代都减少,也不能保证收敛。
    3、循环迭代步骤2,直到  的值变化到使得  在两次迭代之间的差值足够小,比如0.00000001,也就是说,直到两次迭代计算出来的  基本没有变化,则说明此时  已经达到局部最小值了。
    4、此时,输出  ,这个  就是使得函数  最小时的  的取值 。
    Matlab代码:
    %% 最速下降法图示
    % 设置步长为0.1,f_change为改变前后的y值变化,仅设置了一个退出条件。
    syms x;f=x^2;
    step=0.1;x=2;k=0;         %设置步长,初始值,迭代记录数
    f_change=x^2;             %初始化差值
    f_current=x^2;            %计算当前函数值
    ezplot(@(x,f)f-x.^2)       %画出函数图像
    axis([-2,2,-0.2,3])       %固定坐标轴
    hold on
    while f_change>0.000000001                %设置条件,两次计算的值之差小于某个数,跳出循环
        x=x-step*2*x;                         %-2*x为梯度反方向,step为步长,!最速下降法!
        f_change = f_current - x^2;           %计算两次函数值之差
        f_current = x^2 ;                     %重新计算当前的函数值
        plot(x,f_current,'ro','markersize',7) %标记当前的位置
        drawnow;pause(0.2);
        k=k+1;
    end
    hold off
    fprintf('在迭代%d次后找到函数最小值为%e,对应的x值为%e\n',k,x^2,x)
    

      综上所述,梯度下降法与牛顿迭代法都属于迭代法,但是梯度下降法是一阶偏导,而牛顿迭代法是二阶微分而且有Hessian矩阵。两者各有优缺点。

    转载于:https://www.cnblogs.com/2008nmj/p/8857873.html

    展开全文
  • 梯度下降法,共轭梯度下降法,随机梯度下降法 Posted on2015-11-18 | Inmath | 在机器学习领域,优化方法一直是一个很重要的领域,最常见的就是利用目标函数的导数通过多次迭代来求解无约束最优化问题,那么什么...
  • 1 梯度下降法 2 坐标下降法 1.首先给定一个初始点,如 X_0=(x1,x2,…,xn);  2.for x_i=1:n  固定除x_i以外的其他维度  以x_i为自变量,求取使得f取得最小值的x_i;  end  3. 循环执行步骤...
  • 一个多元函数的梯度方向是该函数值增大最陡的方向。对于一元函数而言,梯度方向是沿着曲线切线的,然后取切线向上增长的方向为梯度方向。对于二元或多元函数而言,梯度向量为函数F对每个变量的导数,该向量的方向...
  • 梯度下降法 其有着三种不同的形式: 批量梯度下降(Batch Gradient Descent)、 随机梯度下降(Stochastic Gradient Descent) 以及小批量梯度下降...批量梯度下降法是最原始的形式,它是指在每一次迭代时使...
  • 梯度下降法

    2018-06-30 19:35:43
    采用梯度下降法求解方程最小值的实验,代码中包括梯度下降法迭代方式
  • 最小二乘法 基本公式: 考虑超定方程组(超定指方程个数大于未知量个数): 其中m代表有m个等式,n代表有 n 个未知数 ,m>...顾名思义,梯度下降法的计算过程就是沿梯度下降的方向求解极小值(也可以沿
  • 批量梯度下降法就是在计算代价函数的时候会用到所有的样本数目,比如当权值都为1的时候会得到一个假设函数好h(x),然后运用所有的样本数目计算出此时的误差。此时每进行一次迭代都会运用全部的样本数量。计算量大 ...
  • 梯度下降法迭代算法,每一步需要求解目标函数的梯度向量。 二.应用场景 1.给定许多组数据(xi, yi),xi (向量)为输入,yi为输出。设计一个线性函数y=h(x)去拟合这些数据。 2.感知机:感知机(perceptron...
  • 随机梯度下降法和批量梯度下降法

    千次阅读 2017-09-27 13:45:36
     在机器学习中,基于基本的梯度下降法发展了两种梯度下降方法,分别为随机梯度下降法和批量梯度下降法。  比如对一个线性回归(Linear Logistics)模型,假设下面的h(x)是要拟合的函数,J(theta)为损失函数,...
  • 梯度下降法 所以logistic回归算法实现为logistic回归是分类问题。前面我们讲的分类问题的输出都是 “yes”或者“no”。但是在现实生活中,我们并不是总是希望结果那么肯定,而是概率(发生的可能性)。比如,我们...
  • 这里写自定义目录标题梯度下降法算法详解新的改变功能快捷键合理的创建标题,有助于目录的生成如何改变文本的样式插入链接与图片如何插入一段漂亮的代码片生成一个适合你的列表创建一个表格设定内容居中、居左、居右...
  • 这几天在看《统计学习方法》这本书,发现 梯度下降法 在 感知机 等机器学习算法中有很重要的应用,所以就特别查...梯度下降法迭代算法,每一步需要求解目标函数的梯度向量。    二.应用场景  1.给定许多
  • 文章目录记录TensorFlow听课笔记一,梯度下降法:求解函数极值问题二,梯度下降法的优化 多层神经网络——非线性分类问题 损失函数不是凸函数,很难计算解析解 通常采用梯度下降法,得到数值解 一,梯度下降法:...
  •   梯度下降法(Gradient Descent,GD)是机器学习中常见的一种迭代优化算法,它根据目标函数fff在某点xix_ixi​的偏导数∂f∂xi\frac{\partial f}{\partial x_i}∂xi​∂f​的正负决定“爬坡”或“下山”,最终...
  • 梯度下降法的基本思想是函数沿着其梯度方向增加最快,反之,沿着其梯度反方向减小最快。在前面的线性回归和逻辑回归中,都采用了梯度下降法来求解。梯度下降的迭代公式为: θj=θj−α∂J(θ)∂θj  在回归算法...
  • 1 梯度下降法 ...梯度下降法是利用待优化变量,沿着负梯度方向不断迭代寻找最优值。 直观理解: 梯度下降法算法流程: (PPT画个图可真难) 梯度下降法证明:通过泰勒展开表达式证明沿...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,723
精华内容 689
关键字:

梯度下降法迭代