【代码】优化算法BGD、SGD、Momentum、Adam算法python实现

目前优化算法主要用的就是梯度下降算法，在原始梯度下降的基础上变化出很多更加优秀的算法。发展历史为：BGD $\Rightarrow$ SGD $\Rightarrow$ SGDM $\Rightarrow$ NAG $\Rightarrow$ AdaGrad $\Rightarrow$ AdaDelta $\Rightarrow$ Adam $\Rightarrow$ Nadam
本博客用python实现了部分主要算法
话不多说，且看下文：

文章目录

概述

一般用一个通用框架来表述优化算法

有如下定义：
1）待优化的参数 $\theta$
2）目标函数 $J(\theta)$
3）学习率 $\alpha$

有如下过程（每次迭代）：
1）计算目标关于此时参数的梯度 $\nabla_\theta(J (\theta) )$
2）计算历史梯度的一阶动量和二阶动量
3）计算下降梯度 $g$
4）根据梯度进行迭代 $\theta=\theta-g$

优化算法目前有 $\underline{固定学习率}$ 和 $\underline{适应学习率}$ 两种，差别也就体现在过程的第1和第2步
固定学习率优化算法有：BGD、SGD、SGDM、NAG
自适应学习率优化算法有：AdaGrad、AdaDelta、Adam、Nadam

经验总结

现在用的最多的算法是SGD和Adam，两者各有好坏。SGD能够到达全局最优解，而且训练的最佳精度也要高于其他优化算法，但它对学习率的调节要求非常严格，而且容易停在鞍点；Adam很容易的跳过鞍点，而且不需要人为的干预学习率的调节，但是它很容易在局部最小值处震荡，存在在特殊的数据集下出现学习率突然上升，造成不收敛的情况。

算法	优点	缺点	适用情况
BGD	目标函数为凸函数时，可以找到全局最优值	收敛速度慢，需要用到全部数据，内存消耗大	不适用于大数据集，不能在线更新模型
SGD	避免冗余数据的干扰，收敛速度加快，能够在线学习	更新值的方差较大，收敛过程会产生波动，可能落入极小值（卡在鞍点），选择合适的学习率比较困难（需要不断减小学习率）	适用于需要在线更新的模型，适用于大规模训练样本情况
Momentum	能够在相关方向加速SGD，抑制振荡，从而加快收敛	需要人工设定学习率	适用于有可靠的初始化参数
Adagrad	实现学习率的自动更改	仍依赖于人工设置一个全局学习率，学习率设置过大，对梯度的调节太大。中后期，梯度接近于0，使得训练提前结束	需要快速收敛，训练复杂网络时；适合处理稀疏梯度¹
Adadelta	不需要预设一个默认学习率，训练初中期，加速效果不错，很快，可以避免参数更新时两边单位不统一的问题	在局部最小值附近震荡，可能不收敛	需要快速收敛，训练复杂网络时
Adam	速度快，对内存需求较小，为不同的参数计算不同的自适应学习率	在局部最小值附近震荡，可能不收敛	需要快速收敛，训练复杂网络时；善于处理稀疏梯度和处理非平稳目标的优点，也适用于大多非凸优化 - 适用于大数据集和高维空间

对于稀疏数据，尽量使用学习率可自适应的优化方法，不用手动调节，而且最好采用默认值
SGD通常训练时间更长，但是在好的初始化和学习率调度方案的情况下，结果更可靠
如果在意更快的收敛，并且需要训练较深较复杂的网络时，推荐使用学习率自适应的优化方法。
Adadelta，RMSprop，Adam是比较相近的算法，在相似的情况下表现差不多。
在想使用带动量的RMSprop，或者Adam的地方，大多可以使用Nadam取得更好的效果

批量梯度下降BGD

每一次迭代都用到训练集的所有数据，用所有数据来计算梯度。
优劣点：迭代速度慢，全局最优解

迭代公式： $\theta_j = \theta_j-\frac {\alpha} {m} \sum_{i=0}^m (h_\theta(x^i)-y^i)x_j^i$

以y=x1+2*x2为例，得出的代码结果为：Github代码
在这里插入图片描述

# 批量梯度下降BGD
# 拟合函数为：y = theta * x
# 代价函数为：J = 1 / (2 * m) * ((theta * x) - y) * ((theta * x) - y).T;
# 梯度迭代为: theta = theta - alpha / m * (x * (theta * x - y).T);
import numpy as np


# 1、单元数据程序
# 以 y=x为例，所以正确的结果应该趋近于theta = 1
def bgd_single():
    # 训练集, 单样本
    x = np.array([1, 2, 3, 4, 5, 6, 7, 8, 9, 10])

    y = np.array([1, 2, 3, 4, 5, 6, 7, 8, 9, 10])

    # 初始化
    m = len(y)
    theta = 0  # 参数
    alpha = 0.01  # 学习率
    threshold = 0.0001  # 停止迭代的错误阈值
    iterations = 1500  # 迭代次数
    error = 0  # 初始错误为0

    # 迭代开始
    for i in range(iterations):
        error = 1 / (2 * m) * np.dot(((theta * x) - y).T, ((theta * x) - y))
        # 迭代停止
        if abs(error) <= threshold:
            break

        theta -= alpha / m * (np.dot(x.T, (theta * x - y)))

    print('单变量：', '迭代次数： %d' % (i + 1), 'theta： %f' % theta,
          'error1： %f' % error)


# 2、多元数据程序
# 以 y=x1+2*x2为例，所以正确的结果应该趋近于theta = [1，2]


def bgd_multi():
    # 训练集，每个样本有2个分量
    x = np.array([(1, 1), (1, 2), (2, 2), (3, 1), (1, 3), (2, 4), (2, 3), (3,
                                                                           3)])
    y = np.array([3, 5, 6, 5, 7, 10, 8, 9])

    # 初始化
    m, dim = x.shape
    theta = np.zeros(dim)  # 参数
    alpha = 0.01  # 学习率
    threshold = 0.0001  # 停止迭代的错误阈值
    iterations = 1500  # 迭代次数
    error = 0  # 初始错误为0

    # 迭代开始
    for i in range(iterations):
        error = 1 / (2 * m) * np.dot((np.dot(x, theta) - y).T,
                                     (np.dot(x, theta) - y))
        # 迭代停止
        if abs(error) <= threshold:
            break

        theta -= alpha / m * (np.dot(x.T, (np.dot(x, theta) - y)))

    print('多元变量：', '迭代次数：%d' % (i + 1), 'theta：', theta, 'error：%f' % error)


if __name__ == '__main__':
    bgd_single()
    bgd_multi()

随机梯度下降SGD

因为BGD的迭代速度在大数据量的情况下会变得非常慢，所以提出了随机梯度下降算法，即每一次迭代只使用一个样本，根据这一个样本来计算梯度。
优劣点：迭代速度快，不是全局最优解

迭代公式： $\theta_j = \theta_j-\alpha (h_\theta(x^i)-y^i)x^i$

以y=x1+2*x2为例，得出的代码结果为：Github代码
在这里插入图片描述

# 随机梯度下降SGD
# 以 y=x1+2*x2为例

import numpy as np


# 多元数据
def sgd():
    # 训练集，每个样本有三个分量
    x = np.array([(1, 1), (1, 2), (2, 2), (3, 1), (1, 3), (2, 4), (2, 3), (3,
                                                                           3)])
    y = np.array([3, 5, 6, 5, 7, 10, 8, 9])

    # 初始化
    m, dim = x.shape
    theta = np.zeros(dim)  # 参数
    alpha = 0.01  # 学习率
    threshold = 0.0001  # 停止迭代的错误阈值
    iterations = 1500  # 迭代次数
    error = 0  # 初始错误为0

    # 迭代开始
    for i in range(iterations):
        j = i % m
        error = 1 / (2 * m) * np.dot((np.dot(x, theta) - y).T,
                                     (np.dot(x, theta) - y))
        # 迭代停止
        if abs(error) <= threshold:
            break

        theta -= alpha * (x[j] * (np.dot(x[j], theta) - y[j]))

    print('迭代次数：%d' % (i + 1), 'theta：', theta, 'error：%f' % error)


if __name__ == '__main__':
    sgd()

带动量的随机梯度下降Momentum-SGD

因为SGD只依赖于当前迭代的梯度，十分不稳定，加一个“动量”的话，相当于有了一个惯性在里面，梯度方向不仅与这次的迭代有关，还与之前一次的迭代结果有关。“当前一次效果好的话，就加快步伐；当前一次效果不好的话，就减慢步伐”；而且在局部最优值处，没有梯度但因为还存在一个动量，可以跳出局部最优值。

迭代公式是：
$g = momentum*g + \alpha (h_\theta(x^i)-y^i)x^i$
$\theta_j = theta_j - g$

以y=x1+2*x2为例，得出的代码结果为：Github代码
在这里插入图片描述

# 带冲量的随机梯度下降SGD
# 以 y=x1+2*x2为例

import numpy as np


# 多元数据
def sgd():
    # 训练集，每个样本有三个分量
    x = np.array([(1, 1), (1, 2), (2, 2), (3, 1), (1, 3), (2, 4), (2, 3), (3,
                                                                           3)])
    y = np.array([3, 5, 6, 5, 7, 10, 8, 9])

    # 初始化
    m, dim = x.shape
    theta = np.zeros(dim)  # 参数
    alpha = 0.01  # 学习率
    momentum = 0.1  # 冲量
    threshold = 0.0001  # 停止迭代的错误阈值
    iterations = 1500  # 迭代次数
    error = 0  # 初始错误为0
    gradient = 0  # 初始梯度为0

    # 迭代开始
    for i in range(iterations):
        j = i % m
        error = 1 / (2 * m) * np.dot((np.dot(x, theta) - y).T,
                                     (np.dot(x, theta) - y))
        # 迭代停止
        if abs(error) <= threshold:
            break

        gradient = momentum * gradient + alpha * (x[j] *
                                                  (np.dot(x[j], theta) - y[j]))
        theta -= gradient

    print('迭代次数：%d' % (i + 1), 'theta：', theta, 'error：%f' % error)


if __name__ == '__main__':
    sgd()

Adagrad

$~~$ 对学习率加了一个约束，但依赖于一个全局学习率。
$~~$ 根据迭代公式，学习率 $\alpha$ 乘上了一个系数，这个系数与梯度有关，且当梯度大的时候，这个系数小；当梯度小的时候，这个系数大。这样的实际表现就是在面对频繁出现的特征时，使用小学习率；在面对不频繁出现的特征时，使用大学习率。这就使得这一算法非常适合处理稀疏数据。比如在训练单词嵌入时，常用单词和不常用单词分别用小学习率和大学习率能达到更好的效果。
$~~$ 问题在于公式中的 $v_t$ 会在后期变得非常大，使得矫正后的学习率趋近0，过早得结束迭代。

迭代公式
$v_t = v_{t-1} + {g_t}^2$
$\theta = \theta - \alpha*\frac {g_t} {\sqrt{v_t+\epsilon}}$

Adadelta

Adagrad会累加之前所有的梯度平方，而Adadelta只累加固定大小的项，并且也不直接存储这些项，仅仅是近似计算对应的平均值。不依赖全局学习率。

$v_t = \beta v_{t-1} + (1-\beta)*{g_t}^2$
$\theta = \theta - \alpha*\frac {g_t} {\sqrt{v_t+\epsilon}}$

Adam

$~~$ Adam是一种自适应学习率的方法，在Momentum一阶矩估计的基础上加入了二阶矩估计，也是在Adadelta的基础上加了一阶矩。它利用梯度的一阶矩估计和二阶矩估计动态调整每个参数的学习率。为了解决Adagrad算法出现学习率趋向0的问题，还加入了偏置校正，这样每一次迭代学习率都有个确定范围，使得参数比较平稳。
$~~$ 优劣点：迭代速度快，效果也好，但可能不收敛。

迭代公式是：
$g = h_\theta(x^i)-y^i)x^i$
$m_t = \beta_1 m_{t-1} + (1-\beta_1)*g$
$v_t = \beta_2 v_{t-1} + (1-\beta_2)*g^2$
$\hat{m_t} = \frac {m_t} {1- \beta_1^t}$
$\hat{v_t} = \frac {v_t} {1- \beta_2^t}$
$\theta_j = \theta_j - \hat{m_t}*\frac {\alpha} {\sqrt{\hat{v_t}}+\epsilon}$
以y=x1+2*x2为例，得出的代码结果为：Github代码
在这里插入图片描述

# ADAM
# 以 y=x1+2*x2为例
import math
import numpy as np


def adam():
    # 训练集，每个样本有三个分量
    x = np.array([(1, 1), (1, 2), (2, 2), (3, 1), (1, 3), (2, 4), (2, 3), (3,
                                                                           3)])
    y = np.array([3, 5, 6, 5, 7, 10, 8, 9])

    # 初始化
    m, dim = x.shape
    theta = np.zeros(dim)  # 参数
    alpha = 0.01  # 学习率
    momentum = 0.1  # 冲量
    threshold = 0.0001  # 停止迭代的错误阈值
    iterations = 3000  # 迭代次数
    error = 0  # 初始错误为0

    b1 = 0.9  # 算法作者建议的默认值
    b2 = 0.999  # 算法作者建议的默认值
    e = 0.00000001  #算法作者建议的默认值
    mt = np.zeros(dim)
    vt = np.zeros(dim)

    for i in range(iterations):
        j = i % m
        error = 1 / (2 * m) * np.dot((np.dot(x, theta) - y).T,
                                     (np.dot(x, theta) - y))
        if abs(error) <= threshold:
            break

        gradient = x[j] * (np.dot(x[j], theta) - y[j])
        mt = b1 * mt + (1 - b1) * gradient
        vt = b2 * vt + (1 - b2) * (gradient**2)
        mtt = mt / (1 - (b1**(i + 1)))
        vtt = vt / (1 - (b2**(i + 1)))
        vtt_sqrt = np.array([math.sqrt(vtt[0]),
                             math.sqrt(vtt[1])])  # 因为只能对标量进行开方
        theta = theta - alpha * mtt / (vtt_sqrt + e)

    print('迭代次数：%d' % (i + 1), 'theta：', theta, 'error：%f' % error)


if __name__ == '__main__':
    adam()

参考

An overview of gradient descent optimization algorithms-Sebastian Ruder

精心敲击公式也不容易，点个赞以表感谢吧