【Adam】优化算法浅析

Doris232

论文"ADAM: A METHOD FOR STOCHASTIC OPTIMIZATION"提出了Adam 优化算法（adaptive moment estimation)，用于解决机器学习中的大数据量，高特征纬度的优化问题。他集合了两个流行算法“Adagrad”（用于处理稀疏的梯度）和“RMSPro”（处理非稳态数据）。并且Adam算法仅需要少量的内存。本文将从以下三方面来分析Adam算法，首先介绍论文中相关的基础知识；接着介绍作者如何得出adam算法的，第三部分对adam算法的实验结论进行优缺点分析以及我的一些理解, 第四部分将基于paper中的伪代码实现一个简单的adam optimizer。
一，基础知识

• non-stationary objectives
  

数据的均值，方差，协方差等等指标会随着时间一直变化，参考上图。通常这种数据类型无法直接通过建模来进行预测。简而言之就是数据的分布具有太高的波动性。
2. 随机梯度下降(Stochastic Gradient Descent)
在优化领域最常用的梯度下降法，需要计算当前参数取值  下，目标函数 对参数  的梯度，当样本数据量很大的时候，这个梯度需要对所有样本都进行一次梯度计算并累加起来，这是一个非常高的计算开销。又是有人提出了随机梯度下降，就是每次仅抽样“部分”样本来计算梯度值（极端情况下仅抽取一个样本），当迭代次数足够多以后，模型最终也是可以“收敛”的。这个在样本特别大的神经网络参数的拟合优化问题中特别有效。
3. moment（矩）
矩在数学中的定义，一阶矩(first moment)就是样本的均值(mean), 二阶矩就是方差（variance）。
4. momentum(动量）
在梯度下降的时候由于数据不同维度分布的方差不一致，而每次计算的梯度的方向是垂直于当前计算点的等高线的方向，可能会产生这种波动而导致收敛缓慢。如果设置过小的学习率能减少这种波动但这会导致模型收敛效率太慢。


momentum概念的提出类似物理学上的（动量）的概念，也就是物体运动会趋向于保持于原来的运动状态。
5. SGD-Momentum
带动量的随机梯度下降算法如下：


它的思路就是计算上一次梯度的该变量，每次迭代会考虑上一次的计算结果。这样如果在某个维度上波动厉害的特征，会由于“momentum”的影响，而抵消波动的方向（因为波动剧烈的维度每次更新的方向是相反的，momentum能抵消这种波动）。使得梯度下降更加的平滑，得到更快的收敛效率。而后续提出的Adagrad，RMSProp以及结合两者优点的Adam算法都考虑了这种“momentum”的思想。
6. AdaGrad算法：



Image from the Textbook, Yoshua Bengio, Deep Learning, MIT Press 2016

7. RMSProp算法：



Image from the Textbook, Yoshua Bengio, Deep Learning, MIT Press 2016

RMSProp和Adagrad算法的最大区别就是在于更新累积梯度值 的时候RMSProp考虑加入了一个权重系数 。
8. SGD-Nesterov



Image from the Textbook, Yoshua Bengio, Deep Learning, MIT Press 2016

它的主要思路是先根据当前的速率  先用来更新一次  ，并根据  更新以后的值来计算当前的梯度。接着根据梯度来重新更新速率  ，最后用当前的速率更新最终的  .
9. 滑动平均(exponential moving average)
滑动平均(exponential moving average)，或者叫做指数加权平均(exponentially weighted moving average)，可以用来估计变量的局部均值，使得变量的更新与一段时间内的历史取值有关。
　　变量  在  时刻记为  ， 为变量   在  时刻的取值，即在不使用滑动平均模型时 ，在使用滑动平均模型后，  的更新公式如下：


上式中， ， 相当于没有使用滑动平均。
这也是RMSProp和Adam等算法里使用的最重要的思想。通过滑动平均来降低梯度的波动值。
二，这篇文章讲了什么？

优化领域的问题通常是对一个目标函数求不同的参数组合，使得目标函数取最大值或者最小值。如果该目标函数对于其参数是可求导的，那么就可以使用梯度下降的方法来迭代求出最优的参数组合。但是由于梯度下降中需要计算样本中所有数据的梯度求和，这对于样本量大的时候计算量的开销非常巨大。于是就有人提出了随机梯度下降（Stochastic Gradient Descent）的概念，在每次更新地图的时候只取一个小的样本来计算梯度用于更新全局的参数。而本论文的的重点则集中在高维参数空间中的随机梯度优化问题的讨论。
adam算法的实现伪代码如下：


adam算法比起adagrad和RMSProp，不仅加入了一阶和二阶moment的计算。而且加入了bias-correction term。以下将展开分析：

• adam的更新率（stepsize）
  

adam算法中最重要的就是每次迭代的迭代率（step size），他决定了adam算法的效率。根据上文的算法，step size等于：
1）当 的时候，它的上界满足不等式：
2）否则  
1）通常发生在数据很稀疏的时候。当数据密集的时候，stepsize会更小。
3） 当 的时候，因为 所以，也满足条件2的  。
总结以上3个条件，可以近似得出stepsize 满足
这里的 通常也成为信噪比（Signal-to-noise ratio SNR），并且满足SND越小，stepsize也越小。
2. 初始化偏差较正项( bias-correction term)
原算法中的这两行


称为偏差校正项(bias-correction term),他使用了滑动平均值(EMA: exponential moving average)的思想，例如计算二次moment的 可以写成如下的形式：


我们的目的是求得 （EMA）和二阶moment 之间的关系，推导如下：


最后得出

通常可以忽略常数 。得出


3. 收敛分析(Convergence Analysis)
这里采用由学者Zinkevich提出来的online learning 框架，思路如下：
给定一个凸函数序列 ，假设某时刻t的最优解是 ，我们要计算整个序列的regret：


其中
经过证明（这里省略了推导过程）adam算法的regret具有 的时间复杂度。


所以， 。
当T趋近无穷大的时候，我们有： 。
因此可以看出Adam算法是收敛的。
4. 性能测试实验：
对比算法RMSProp和Adagrad。
1）逻辑回归的测试：
逻辑回归的目标函数是标准凸函数，他能保证找到全局最优解，适合用来对比不同优化器的性能。对比了稀疏特征的场合。


基于逻辑回归的优化测试，数据集是MNIST图像和，IMDB视频评论文本基于BOW编码的特征向量
可以看出Adam不仅能够够快速收敛的（左图），并且可以处理稀疏特征（右图的测试数据BOW编码具有稀疏性）。
2）多层神经网络测试：
虽然神经网络本身是一个非凸优化问题，但是也能够用来测试一下Adam的性能。
测试模型采用了1000个隐含单元（hidden units），采用ReLU作为激活函数。miniBatch Size设置为128，损失函数采用交叉熵（cross-entropy）并采用L2正则项来防止过拟合。


在MNIST数据集合上测试神经网络的优化问题，A）神经网络使用Dropout正则的随机梯度下降，B）使用确定的损失函数（deterministic cost function）
左图可以看出adam还是具有最快的收敛，其次是SGDNesterov。
3）卷积神经网络（CNN）优化测试：



adam和adam带dropout的分数贵高，其次是SGDNesterov。在训练非凸目标函数上adam仍然获得了最好的测试成绩。
4）测试训练VAE（Variational AutoEncoder）时，bias-correction 项和 非 bias-correction项的影响：


红线为带bias-correction项，绿为非bias-correction项，y轴是损失函数。
移出了Bias correction 项就变成了带Momentum的RMSProp算法，当 接近1的时候，会导致非bias-correction项的训练变得不稳定。尤其是在前几次的训练。最佳的成绩是当bias-correction和 的值足够小的时候。可以看出无论是使用什么超参数组合，Adam算法的基本等于或优于RMSProp算法。

5. Adamax算法
基于adam算法中更新  的公式，将其替换为infinity norm（无穷大范数）可以得到如下的更新公式：


最后得出Adamax算法：



6. 尝试均值优化
因为当迭代趋近最优解的时候，最后的几次计算可能会因为噪声而带来波动，作者提出了一种基于EMA（Exponential Moving average）的思想，将每次迭代更新的 时候计算当前t的一个EMA均值化后的


三，文章的结论和自己的认知

adam算法是一种基于“momentum”思想的随机梯度下降优化方法，通过迭代更新之前每次计算梯度的一阶moment和二阶moment，并计算滑动平均值，后用来更新当前的参数。这种思想结合了Adagrad算法的处理稀疏型数据，又结合了RMSProp算法的可以处理非稳态的数据。最后在传统的凸优化问题和最近火热的深度学习优化问题中，取得了非常好的测试性能。达到了当时的state-of-the-art的评价。

• 对于Adam算法的认知
  

adam算法的核心是计算moment所采用了滑动评平均（EMA）的思想，这种滑动评价值的思想是否可以用来在数据预处理比如降噪上呢？
2. Adam算法的应用
如今深度学习的应用愈加广泛，各种大型的计算模型比如BERT，XLNET等参数数量级百万甚至上亿的模型，对于复杂模型的优化的收敛效率的研究成为了方向。ADAM算法的代码本身并不复杂，缺解决了由于数据分布复杂性带来的一些优化收敛慢的问题。
根据参考文献[3]，如果目标函数是一个线性函数 ，可以从数据的分布计算出一个收敛率， ， 是数据线性转换矩阵 的最大和最小的特征值之间的比值,可以等价成计算这个变换： ，其中 也成为Preconditioner. 后来也有学者提出了非线性的Preconditioner变换，他是基于一种数据“预处理”的思想。先将数据处理以后，保证能够效率的收敛，也许对于现在的某些复杂问题，可以基于“预处理”+adam的高效收敛的特性结合，达到一些优化性能的提升？

四、Adam算法简单实现：

这里使用了adam算法来优化逻辑回归：并对比基于mini-batch SGD的收敛性代码实现如下：
adam SGD
# stochastic gradient descent via Adam for logistic regression
def logistic_regression_adam(X, y, num_steps, learning_rate=0.001, batchsize = 128, beta1=0.9, beta2=0.999, epsilon=10e-8):
    """
    base on the gradient descent of Adam Algorithm
    X: training data, N * D
    y: training label,  N * 1
    num_steps: iteration times
    learning_rate: size of the step
    """
    N, D = X.shape
    w, b = np.zeros(X.shape[1]), 0
    beta1_exp = beta1
    beta2_exp = beta2
    # init the w, b.
    m_w = np.zeros(w.shape)
    m_b = 0
    v_w = np.zeros(w.shape)
    v_b = 0
    for step in range(num_steps):
        # get a random index for minibatch with batch size 100
        index = np.random.choice(range(0, N), batchsize, replace=False)

        # calculate the error between the predict and the actual
        error = sigmoid(X[index] @ w + b) - y[index]

        # calculate the gradient for w, b
        grad_w = np.matmul(X[index].T, error)
        grad_b = np.sum(error)

        # calculate first moment
        m_w = beta1 * m_w + (1 - beta1) * grad_w
        m_b = beta1 * m_b + (1 - beta1) * grad_b

        # calculate the second moment
        v_w = beta2 * v_w + (1 - beta2) * grad_w ** 2
        v_b = beta2 * v_b + (1 - beta2) * grad_b ** 2

        # calculate the bias-corrected first and second moment estimate
        beta1_exp *= beta1
        beta2_exp *= beta2

        bar_m_w = m_w / (1 - beta1_exp)
        bar_m_b = m_b / (1 - beta1_exp)

        bar_v_w = v_w / (1 - beta2_exp)
        bar_v_b = v_b / (1 - beta2_exp)

        # update w, b
        rate = learning_rate * np.sqrt(1 - beta2_exp) / (1 - beta1_exp)
        w = w - rate * bar_m_w / (np.sqrt(bar_v_w) + epsilon)
        b = b - rate * bar_m_b / (np.sqrt(bar_v_b) + epsilon)

        # calculate the likelihood
        if step % 1000 == 0:
            print('epoch\t%d\t------\tlost: '%step, log_likelihood(X, y, w, b))

    return w, b
minibatch-SGD
# mini-batch gradient descent for logistic regression
def logistic_regression_minibatch(X, y, num_steps, learning_rate, batchsize = 128):
    """
    base on the gradient descent
    X: training data, N * D
    y: training label,  N * 1
    num_steps: iteration times
    learning_rate: size of the step
    """
    N, D = X.shape
    w, b = np.zeros(X.shape[1]), 0
    for step in range(num_steps):
        # get a random index for minibatch with batch size 100
        index = np.random.choice(range(0, N), batchsize, replace=False)

        # calculate the error between the predict and the actual
        error = sigmoid(X[index] @ w + b) - y[index]

        # calculate the gradient for w, b
        grad_w = np.matmul(X[index].T, error)
        grad_b = np.sum(error)

        # update w, b
        w = w - learning_rate * grad_w
        b = b - learning_rate * grad_b

        # calculate the likelihood
        if step % 1000 == 0:
            print('epoch\t%d\t------\tlost: '%step, log_likelihood(X, y, w, b))

    return w, b完整代码实现如下：
Reference
[1] Diederik P.Kingma, Jimmy Lei Ba, Adam: A method for Stochastic Optimizaiton, ICLR 2015
[2] Martin Zinkevich, Online Convex Programming and Generalized Infinitesimal Gradient Ascent, CMU, 2003
[3] Marc Peter Deisenroth, A. Aldo Faisal, Cheng Soon Ong, Gradient Descent With Momentum, Mathematic for Machine Learning, Cambridge University Press, 2019
[4] Ian Goodfellow, Yoshua Bengio, Aaron Courville, Optimization for training deep model, Deep Learning, MIT Press 2016
[5] http://www.quora.com
[6] www.wikipedia.org, Meoment(mathematics),