梯度下降及其改进算法的比较

布满荆棘的人生 2022-09-29 12:56 226阅读 0赞

# 梯度下降及其改进算法的比较 #

*  **梯度下降**
 *  **随机梯度下降**
 *  **改进的随机梯度下降**
 *  **Mini-batch梯度下降**

## 1、梯度下降 ##

> 在机器学习中，一种非常常用的最优化方法——梯度下降算法。该方法的基本思想是：要找到某个函数的的最小值，最好的方法是沿着该函数的梯度方向探寻。

![这里写图片描述][SouthEast]

如上图所示，梯度下降算法，到达每个点后都会重新估计移动的方向。从P0开始，计算完该点的梯度，函数就会根据梯度移动到下一个点P1。在P1点，梯度再次被重新计算，并沿着新的梯度方向移动到P2。如此循环迭代，直到满足停止条件。在迭代过程中，梯度算子总是保证我们能选取最佳的移动方向。

梯度下降算法用来求函数的最小值，函数系数的更新公式如下：

> w:=w−α∇wf(w)

该公式将一直被执行下去，直至达到某个停止条件，比如迭代次数达到某个指定的值或者算法达到某个可以允许的误差范围。

实现梯度下降的伪代码如下：

每次回归系数初始化为1
    重复R次：
        计算整个数据集的梯度
        使用alpha*gradient更新函数的系数向量
        返回函数的系数

Python代码实现：

def gradDecent(dataMatIn, classLabels):
        dataMatrix = mat(dataMatIn)             #convert to NumPy matrix
        labelMat = mat(classLabels).transpose() #convert to NumPy matrix
        m,n = shape(dataMatrix)
        alpha = 0.001
        maxCycles = 500
        weights = ones((n,1))
        for k in range(maxCycles):              #heavy on matrix operations
            h = sigmoid(dataMatrix*weights)     #matrix mult
            error = (labelMat - h) 
            aa=dataMatrix.transpose()             #vector subtraction
            weights = weights - alpha * dataMatrix.transpose()* error #matrix mult
        return weights

> 注意：可以看出上面程序的迭代次数为500，每一次迭代都是用了全部的样本。可以想象当样本数量非常大时，该方法的计算量是巨大的。

## 2、随机梯度下降 ##

> 该方法的每次迭代只使用一个样本来更新回归系数，由于该方法可以在新样本到来时对分类器进行增量式的更新，所以该方法是一个在线学习算法。

实现随机梯度下降的伪代码如下：

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

Python代码实现：

def stocGradAscent0(dataMatrix, classLabels):
        m,n = shape(dataMatrix)
        alpha = 0.01
        weights = ones(n)   #initialize to all ones
        for i in range(m):
            h = sigmoid(sum(dataMatrix[i]*weights))
            error = classLabels[i] - h
            weights = weights - alpha * error * dataMatrix[i]
    return weights

> 注意：可以看出随机梯度下降和梯度下降算法代码很相似，但是也是有区别的。第一：后者的的变量h和误差error都是向量，而前者则全是数值；第二：前者没有矩阵的转换过程。

虽然随机梯度下降算法比梯度下降算法会快很多就达到了收敛，但是收敛后会存在一些小周期的波动。产生这种现象的原因是存在一些不能正确分类的样本点（数据集并不是线性可分的），在每次迭代时会引发系数的剧烈改变。

## 3、改进的随机梯度下降 ##

> 真正意义上的随机梯度下降，通过随机选取样本来更新回归系数，这种方法将减少周期性的波动（每次随机从列表中选出一个值，然后从列表中删除掉该值，再进行下一次迭代）。

Python代码实现：

def stocGradAscent1(dataMatrix, classLabels, numIter=150):
        m,n = shape(dataMatrix)
        weights = ones(n)   #initialize to all ones
        for j in range(numIter):
            dataIndex = range(m)
            for i in range(m):
                alpha = 4/(1.0+j+i)+0.0001    #apha decreases with iteration, does not 
                randIndex = int(random.uniform(0,len(dataIndex)))#go to 0 because of the constant
                h = sigmoid(sum(dataMatrix[randIndex]*weights))
                error = classLabels[randIndex] - h
                weights = weights + alpha * error * dataMatrix[randIndex]
                del(dataIndex[randIndex])
    return weights

从上面的代码可以看出，alpha的值在每次的迭代中会发生变化，随着迭代的次数不断的减小，有利于缓解数据的波动。

## 4、Mini-batch梯度下降 ##

> 这是介于BSD和SGD之间的一种优化算法。每次选取一定量的训练样本进行迭代。它的速度比BSD快，比SGD慢；精度比BSD低，比SGD高。

实现随机梯度下降的实现步骤：

1、选择n个训练样本（n<m，m为总训练集样本数）
    
    2、在这n个样本中进行n次迭代，每次使用1个样本
    
    3、对n次迭代得出的n个gradient进行加权平均再并求和，作为这一次mini-batch下降梯度
    
    4、不断在训练集中重复以上步骤，直到收敛。

[SouthEast]: /images/20220708/aac4645076114e0f8b6ad3bf50d98962.png