机器学习笔记(八)——随机梯度上升(下降)算法调优

前言概述

上一篇文章对逻辑回归的原理和基本思想做了一些简要介绍，并通过引入Sigmoid函数和梯度公式成功推导出了梯度上升和梯度下降公式，上文分类实例是依据全批量提升上升法，而本文会介绍全批量梯度上升的一种优化算法——随机梯度上升，如果还未懂得逻辑回归思想和推理公式的原理，还请观看上一篇文章：机器学习笔记(七)——初识逻辑回归、不同方法推导梯度公式。

随机梯度上升

区别对比

在讲解全批量梯度上升和随机梯度上升的区别之前，先看一下二者的公式之间的对比，有助于之后的理解。
全批量梯度上升法：

随机梯度上升法：

全批量梯度上升公式我们已经很熟悉，在上一篇文章有介绍；其实随机梯度上升与全批量的公式十分相似，原理也是大致相同的，不同点体现在何处呢？全批量在每次更新回归系数时都需要遍历整个数据集，这种方法在处理小数据集时尚可，但如果有数十亿样本和成千上万的特征，那么该方法的计算复杂度太高。而随机梯度上升是一次仅用一个样本点来更新回归系数，这样做大大减小了计算复杂度，并且提高了函数的收敛速度。

更改算法

随机梯度上升算法伪代码如下

所有回归系数初始化为1
对数据集中每个样本
      计算该样本的梯度
      使用alpha*gradient更新回归系数值
返回回归系数值
1
2
3
4
5

因为两个公式大体上一致，所以随机梯度上升法的代码只会稍微有些出入。

def stocGradAscent1(dataMatrix, classLabels):
    #将列表转化为array格式
    dataMatrix = np.array(dataMatrix)
    # 获取dataMatrix的行、列数
    m,n = np.shape(dataMatrix)
    # 初始化回归系数和步长
    weights = np.ones(n)
    alpha = 0.01
    for i in range(m):
        # 遍历样本，每次选出一个，计算h
        h = sigmoid(sum(dataMatrix[i]*weights))
        # 计算误差
        error = classLabels[i] - h
        # 更新回归系数
        weights = weights + alpha * error * dataMatrix[i]
    return weights
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

可以看到两种算法有些区别：第一，随机梯度上升的变量h和误差error都是数值，而全批量中二者都是向量格式；第二，随机梯度没有矩阵运算，所有变量的数据类型都为Numpy数组。

执行上述代码可以得到一条新的最佳拟合直线图，如下：

可以看到，这条新的最佳拟合直线只分对了二分之一的样本。明明是对算法进行调优，可是准确率怎么越调越低呢？

原因是全批量梯度上升法是在整个数据集上迭代了500次才得到的，迭代次数要远大于随机梯度方法，而判断一个算法优劣的可靠方法是看它是否收敛，也就是参数是否达到了稳定值，是否还会不断变化。

下图为两种方法迭代次数与回归系数之间的关系：

可以看到全批量梯度三个回归图像与随机梯度相比波动幅度都比较大，用最明显的回归系数X2作比较，前者在下标为300时收敛完成，而后者在下标14000时曲线才近乎平稳；但这里需要注意的是，全批量梯度每次迭代都是利用整个数据集，所以该方法收敛完成时的准确迭代次数应该是30000次，比随机梯度的迭代次数要多的多。

随机梯度方法在大的波动之后，还有很多小的周期波动，产生这种现象的原因是存在一些不能正确分类的样本点，在每次迭代时会引发系数的剧烈改变。我们希望算法可以避免波动问题，从而收敛到某个值，并且加快收敛速度。

算法调优

所以对随机梯度上升算法做以下改进：

def stocGradAscent2(dataMatrix, classLabels, numIter=150):
    #将列表转化为array格式
    dataMatrix = np.array(dataMatrix)
    # 获取dataMatrix的行、列数
    m,n = np.shape(dataMatrix)
    # 初始化回归系数和步长
    weights = np.ones(n)
    for j in range(numIter):
        dataIndex = list(range(m))
        for i in range(m):
            # 逐渐减小alpha，每次减小量为1.0/(j+i)
            1、alpha = 4/(1.0+j+i)+0.01
            # 随机选取样本
            2、randIndex = int(random.uniform(0,len(dataIndex)))
            # 随机选取的一个样本，计算h
            h = sigmoid(sum(dataMatrix[randIndex]*weights))
            # 计算误差
            error = classLabels[randIndex] - h
            # 更新回归系数
            weights = weights + alpha * error * dataMatrix[randIndex]
            # 删除已经使用过的样本
            del(dataIndex[randIndex])
    return weights
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

第一处改进目的在于每一次迭代都会调整步长alpha的值，alpha每次迭代都会减小1/(j+i),其中j是迭代次数，i是样本点的下标。虽然alpha会随着迭代次数不断减小，但永远不会减小到0，其中还存在一个常数项，这是因为在多次迭代之后alpha的值近乎为0，这样新数据对于回归系数的更新几乎没有作用。

这里再利用图片再讲解一下为什么要这样优化alpha。

上图是一个二次函数的图像，在最开始时梯度较大，步长alpha可以比较大，但梯度是呈现逐渐减小趋势的，这时离最优值也越来越近，步长alpha也要随之减小。如果下降速率很大，在接近最优点时，梯度乘以了一个数值比较大的alpha，就会出现下图这类情况。

例如从点1直接跳到了点2，开始震荡，上述迭代次数与回归系数关系图中的较大震荡产生的原因，而上述对步长alpha的优化即可避免这类情况，虽然举例用的是梯度下降，但梯度上升和梯度下降的原理是一致的。

第二处改进的目的是减少随机梯度关系图中周期性的波动，这里通过随机选取抽样样本更新回归系数，每次随机从列表中选取一个值，然后从列表中删掉该值，再进行下一次迭代，与决策树选取信息增益的方式类似。

下图给出了改进后的随机梯度上升法迭代次数与回归系数的关系图。

可以看出这种方法三个回归系数图像比固定步长alpha的方法收敛速度都要快，并且没有了周期性的波动，为了更直观地看到改进算法的效果，下图给出了利用改进后的算法绘制出的最佳拟合直线图。

最终随机梯度的分类效果与全批量梯度几乎一样，但是迭代次数却要少很多很多，所以前者很大程度上降低了算法的计算复杂度，减小了程序使用的内存。

总结

文末总结一下全批量梯度下降法、随机梯度下降法、小批量梯度下降法的优缺点即适应场合。

全批量梯度下降法(BGD)：每次更新回归系数所有样本都参与。

• 优点：分类准确，获取全局最优解
• 缺点：当样本比较多时，训练速度特别慢
• 适用场合：样本较少的数据集

随机梯度下降法(SGD)：每次更新回归系数只有一个样本参与。

• 优点：训练速度很快
• 缺点：准确率会降低，并不是朝着整体最优方向进行，容易获取到局部最优解
• 适用场合：样本非常多的数据集

小批量梯度下降法(MBGD)：每次更新回归系数有一部分样本参与。这种方法兼顾了上述两种方法的优点，同时也减弱了两者的缺点，算是两种前两种算法的一种平衡。如果数据集的样本数不是很极端，最好采用小批量梯度下降法。

关注公众号【喵说Python】后台回复“随机梯度”可获取源码供参考，感谢阅读。