人工智能中文网
  • 主页
  • 线代考研视频
  • 线性代数
  • Python机器学习与算法
  • 大数据与机器学习
  • Python基础入门教程
  • 人工智能中文网
    教程目录
    阅读:

    梯度下降法的原理和步骤(Python实现)

    < 上一篇:逻辑回归算法 下一篇:逻辑回归算法实践 >
    在机器学习算法中,对于很多监督学习模型,需要对原始的模型构建损失函数 l,接下来便是通过优化算法对损失函数 l 进行优化,以便寻找到最优的参数 W。在求解机器学习参数 W 的优化算法时,使用较多的是基于梯度下降的优化算法(Gradient Descent,GD)

    梯度下降法有很多优点,其中,在梯度下降法的求解过程中,只需求解损失函数的一阶导数,计算的成本比较小,这使得梯度下降法能在很多大规模数据集上得到应用。梯度下降法的含义是通过当前点的梯度方向寻找到新的迭代点,并从当前点移动到新的迭代点继续寻找新的迭代点,直到找到最优解。

    梯度下降法的流程

    梯度下降法是一种迭代型的优化算法,根据初始点在每一次迭代的过程中选择下降法方向,进而改变需要修改的参数,对于优化问题 min f(w),梯度下降法的详细过程如下所示。

    1) 随机选择一个初始点 w0

    2) 重复以下过程:
    • 决定梯度下降的方向:

    • 选择步长 α;
    • 更新:wi+1=wi+α·di
    • 直到满足终止条件;

    具体过程如图 1 所示。


    图 1 梯度下降的过程

    在初始时,在点 w0 处,选择下降的方向 d0 ,选择步长 α,更新 w 的值,此时到达 w1 处,判断是否满足终止的条件,发现并未到达最优解 w,重复上述的过程,直至到达 w

    凸优化与非凸优化

    简单来讲,凸优化问题是指只存在一个最优解的优化问题,即任何一个局部最优解即全局最优解,如图 2 所示。


    图 2 凸函数

    非凸优化是指在解空间中存在多个局部最优解,而全局最优解是其中的某一个局部最优解,如图 3 所示。


    图 3 非凸函数

    最小二乘(Least Squares)、岭回归(Ridge Regression)和 Logistic回归(Logistic Regression)的损失函数都是凸优化问题。

    利用梯度下降法训练Logistic Regression模型

    对于上述的 Logistic Regression 算法的损失函数可以通过梯度下降法对其进行求解,其梯度为:


    其中,x(i)j表示的是样本 x(i) 的第 j 个分量。取 w0 = b,且将偏置项的变量 x0 设置为 1,则可以将上述的梯度合并为:


     
    根据梯度下降法,得到如下的更新公式:


    利用上述的 Logistic Regression 中权重的更新公式,我们可以实现 Logistic Regression 模型的训练,利用梯度下降法训练模型的具体过程,具体实现代码如下所示。
    def lr_train_bgd(feature, label, maxCycle, alpha):
        '''利用梯度下降法训练LR模型
        input:
            feature (mat)特征
            label (mat)标签
            maxCycle (int)最大迭代次数
            alpha (float)学习率
        output:
            w (mat):权重
        '''
        n = np.shape(feature)[1] # 特征个数
        w = np.mat(np.ones((n,1))) #初始化权重
        i = 0
        while i <= maxCycle : #在最大迭代次数的范围内
            i += 1 #当前的迭代次数
            h = sig(feature * w) # 计算 Sigmoid 值
            err = label — h
            if i % 100 == 0:
                print "	---------iter=” + str(i) + 
                ",train error rate= " + str(error_rate(h, label))
        w = w + alpha * feature.T*err #权重修正
    retuen w

    程序中,函数 lr_train_bgd 使用了梯度下降法对 Logistic Regression 算法中的损失函数进行优化,其中,lr_train_bgd 函数的输入为训练样本的特征、训练样本的标签、最大的迭代次数和学习率,在每一次迭代的过程中,需要计算当前的模型的误差,误差函数为 error_rate。

    error_rate 函数的具体实现形式如下所示。在迭代的过程中,不断通过梯度下降的方法对 Logistic Regression 算法中的权重进行更新。
    def error_rate(h, label):
        '''计算当前的损失函数值
        input:
            h (mat):预测值
            label (mat):实际值
        output:
            err/m (float):错误率
        '''
        m = np.shape(h)[0]
        sum_err =0.0
        for i in xrange(m):
            if h[i,0] > 0 and (1 -h[i,0]) > 0 :
                sum_err -= (label[i,0] *np.log(h[i,0])+
                (1-label[i,0])*np.log(l-h[i,0]))
            else:
                sum_err -= 0
        return sum_err / m
    该程序中,error_rate 函数的输入为假设函数对训练样本的预测值 h 和训练样本的标签 label,输出值为损失函数的值。

    梯度下降法的若干问题

    选择下降的方向

    为了求解优化问题 f(w) 的最小值,我们希望每次迭代的结果能够接近最优值 w,对于一维的情况,如图 4 所示。


    图 4 下降的方向

    若当前点的梯度为负,则最小值在当前点的右侧,若当前点的梯度为正,则最小值在当前点的左侧,负的梯度即为下降的方向。对于上述的一维的情况,有下述的更新规则:


     
    其中,αi为步长。对于二维的情况,此时更新的规则如下:

    步长的选择

    对于步长 α 的选择,若选择太小,会导致收敛的速度比较慢;若选择太大,则会出现震荡的现象,即跳过最优解,在最优解附近徘徊,上述两种情况如图 5 所示。


    图 5 步长太大或者太小

    因此,选择合适的步长对于梯度下降法的收敛效果显得尤为重要,如图 6 所示。



    图 6 合适的步长
    < 上一篇:逻辑回归算法 下一篇:逻辑回归算法实践 >