DL——各种梯度下降相关的优化算法

Posted on

本文从梯度下降(Gradient Descent, GD)开始,讲述深度学习中的各种优化算法

参考文章:【干货】深度学习必备：随机梯度下降（SGD）优化算法及可视化

三种梯度下降框架

随机梯度下降

核心思想
  • 每次从随机从训练集中选择一个训练样本来计算误差,进而更新模型参数
  • 单次迭代时参数移动方向可能不太精确甚至相反,但是最终会收敛
  • 单次迭代的波动也带来了一个好处,可以到达一个更好的局部最优点,甚至到达全局最优点
参数更新公式

Stochastic Gradient Descent, SGD

  • 公式: \(\theta=\theta-\lambda\frac{\partial L(\theta;x_{i};y_{i})}{\partial \theta}\)
  • 其中:\(L(\theta;x_{i};y_{i})=L(f(\theta;x_{i}),y_{i})\)

批量梯度下降

Batch Gradient Descent, BGD

核心思想
  • 每次使用全量的训练集样本(假设共m个)来计算误差,进而更新模型参数
  • 每次参数能够朝着正确的方向移动
  • 每次遍历所有数据,耗费时间较长
参数更新公式
  • 公式: \(\theta=\theta-\lambda\frac{\partial L(\theta;x_{1:m};y_{1:m})}{\partial \theta}\)
  • 一般来说: \(L(\theta;x_{1:m};y_{1:m}) = \frac{1}{m}\sum_{i=1}^{m} L(\theta;x_{i};y_{i})\)

小批量梯度下降

核心思想
  • 每次从随机从训练集中选择k(k < m)个训练样本来计算误差,进而更新模型参数
  • 介于SGD和BGD之间
    • 波动小
    • 内存占用也相对较小
参数更新公式

Mini-Batch Gradient Descent, MBGD

  • 公式: \(\theta=\theta-\lambda\frac{\partial L(\theta;x_{i:i+k};y_{i:i+k})}{\partial \theta}\)
  • 一般来说: \(L(\theta;x_{1:k};y_{1:k}) = \frac{1}{k}\sum_{i=1}^{k} L(\theta;x_{i};y_{i})\)

总结

优点
  • 梯度下降算法应用广泛,算法效果很好
缺点
学习速率
  • 大小很难确定,太大容易震荡,太小则收敛太慢
  • 学习速率一般为定值,有时候会实现为逐步衰减
  • 但是无论如何,都需要事前固定一个值,因此无法自适应不同的数据集特点
局部最优
  • 对于非凸的目标函数,容易陷入局部极值点中
  • 比局部极值点更严重的问题:有时候会嵌入鞍点?

SD算法的优化

Momentum法(动量法)

核心思想
  • 考虑一种情况,在峡谷地区(某些方向比另一些方向陡峭很多)
    • SGD(或者MBGD,实际上,SGD是特殊的MBGD,平时可以认为这两者是相同的东西)会在这些放附近振荡,从而导致收敛速度变慢
    • 这里最好的例子是鞍点,鞍点出的形状像一个马鞍,一个方向两头上翘,一个方向两头下垂,当上翘的方向比下垂的方向陡峭很多时,SDG和MDG等方法容易在上翘方向上震荡
  • 此时动量可以使得
    • 当前梯度方向与上一次梯度方向相同的地方进行加强,从而加快收敛速度
    • 当前梯度方向与上一次梯度方向不同的地方进行削减,从而减少振荡
  • 动量可以理解为一个从山顶滚下的小球,遇到新的力(当前梯度)时,会结合之前的梯度方向决定接下来的运动方向
参数更新公式
  • 公式: \(\theta=\theta-m_{t}\)
    • \(m_{t}\)表示当前下降方向, \(m_{t-1}\)表示上一次的下降方向
    • \(m_{t}=\gamma m_{t-1}+\lambda\frac{\partial L(\theta;x_{i};y_{i})}{\partial \theta}\)
    • \(\gamma<1\),值一般取0.9
    • \(\gamma m_{t-1}\)是动量项
    • \(\gamma\)是衰减量
    • \(\lambda\)是学习率
图示
小结
  • 学习过程
    • 从训练集中的随机抽取一批容量为m的样本\({x_{1},…,x_{m}}\),以及相关的输出\({y_{1},…,y_{m}}\)
    • 计算梯度和误差,更新v和参数\(\theta\)

NAG,涅斯捷罗夫梯度加速法

Nesterov Accelerated Gradient,NAG

核心思想
  • 继续考虑普通的SDG算法,添加了Momentum,此时从山顶滚下的球会盲目的选择斜坡
  • 更好的方式是在遇到向上的斜坡时减慢速度
  • NAG在计算梯度时首先获取(近似获得)未来的参数而不是当前参数,然后计算未来参数对应的损失函数的梯度
  • NAG在预测了未来的梯度后,根据未来(\(\theta - \gamma m_{t-1}\))梯度方向和之前梯度的方向决定当前的方向, 这样可以保证在遇到下一点为上升斜坡时适当减慢当前点的速度(否则可能由于惯性走上斜坡, 提前知道\(\theta - \gamma m_{t-1}\)处的梯度, 从而保证不要走上去), 从而找到了比Momentum超前的更新方向
  • 对比: Momentum是根据当前梯度方向和之前梯度方向决定当前的方向
参数更新公式
  • 公式: \(\theta=\theta-m_{t}\)
    • \(m_{t}=\gamma m_{t-1}+\lambda\frac{\partial L(\theta - \gamma v_{t-1};x_{i};y_{i})}{\partial \theta}\)
    • NAG使用的是未来的梯度方向(Momentum使用的是当前梯度方向)和之前的梯度方向
图示
  • Momentum(动量)法首先计算当前的梯度值(小蓝色向量)，然后在更新的积累向量（大蓝色向量）方向前进一大步
  • NAG 法则首先(试探性地)在之前积累的梯度方向(棕色向量)前进一大步，再根据当前地情况修正，以得到最终的前进方向(绿色向量)
  • 这种基于预测的更新方法，使我们避免过快地前进，并提高了算法地响应能力(responsiveness)，大大改进了 RNN 在一些任务上的表现
    • 公式中\(-\gamma m_{t-1}\)对应BC向量
    • \(\theta-\gamma m_{t-1}\)就对应C点(参数)
小结
  • Momentum和NAG法可以使得参数更新过程中根据随时函数的斜率自适应的学习,从而加速SGD的收敛
  • 实际应用中,NAG将比Momentum收敛快很多
  • 学习过程
    • 从训练集中的随机抽取一批容量为m的样本\({x_{1},…,x_{m}}\),以及相关的输出\({y_{1},…,y_{m}}\)
    • 计算梯度和误差,更新v和参数\(\theta\)

Adagrad

核心思想
  • 对于较少出现的特征,使用较大的学习率更新,即对低频的参数给予更大的更新
  • 对于较多出现的特征,使用较小的学习率更新,即对高频的参数给予更小的更新
  • 很适合处理稀疏数据
参数更新公式
  • 计算梯度
    • 分量形式: \(g_{t,k} = \frac{\partial L(\theta;x_{i};y_{i})}{\theta}|_{\theta = \theta_{t-1,k}}\)
      • \(g_{t,k}\)是指第t次迭代时第k个参数\(\theta_{t-1, k}\)的梯度
      • 有些地方会这样表达: \(g_{t,k} = \frac{\partial L(\theta_{t-1,k};x_{i};y_{i})}{\theta_{t-1,k}}\)
        • 式子中使用\(\theta_{t-1, k}\)在梯度中,事实上不够严谨, 容易让人误解分子分母都不是函数,而是一个确定的值, 事实上我们是先求了导数然后再带入 \(\theta = \theta_{t-1}\) 的
    • 向量形式: \(g_{t} = \frac{\partial L(\theta;x_{i};y_{i})}{\partial \theta}|_{\theta=\theta_{t-1}}\)
  • 此时普通的SGD如下更新参数
    • 分量形式:\(\theta_{t,k} = \theta_{t-1,k} - \lambda g_{t,k}\)
    • 向量形式:\(\theta_{t} = \theta_{t-1} - \lambda g_{t}\)
  • 而Adagrad对学习率\(\lambda\)根据不同参数进行了修正
    • 分量形式:\(\theta_{t,k} = \theta_{t-1,k} - \frac{\lambda}{\sqrt{G_{t,kk}+\epsilon}} g_{t,k}\)
      • \(G_{t,kk}=\sum_{r=1}^{t}(g_{r,k})^{2}\)
    • 向量形式:\(\theta_{t} = \theta_{t-1} - \frac{\lambda}{\sqrt{G_{t}+\epsilon}}\bigodot g_{t}\)
      • \(G_{t}=\sum_{r=1}^{t}g_{r}\bigodot g_{r}\)
      • \(\bigodot\)表示按照对角线上的值与对应梯度相乘
      • 进一步可以简化写为: \(G_t = G_{t-1} + g_t^2\)
        • 注意: 这里\(g_t^2\)是指向量按照维度分别相乘, 计算后还是原始向量维度
    • G是一个对角矩阵,对角线上的元素(\(G_{k,k}\))是从一开始到k次迭代目标函数对于参数(\(\theta_{k}\))的梯度的平方和
      • G的累计效果保证了出现次数多的参数(\(\theta_{k}\))对应的对角线上的元素(\(G_{k,k}\))大,从而得到更小的更新
    • \(\epsilon\)是一个平滑项,用于防止分母为0
  • 总结参数更新公式:
    • \(\theta_{t} = \theta_{t-1} - \frac{\lambda}{\sqrt{G_{t}+\epsilon}} g_{t}\)
    • \(g_{t} = \frac{\partial L(\theta;x_{i};y_{i})}{\partial \theta }|_{\theta = \theta_{t-1}}\)
    • \(G_t = G_{t-1} + g_t^2\)
小结
  • 在分母上累计了平方梯度和,造成训练过程中G的对角线元素越来越大,最终导致学习率非常小,甚至是无限小的值,从而学不到东西
  • 学习过程
    • 从训练集中的随机抽取一批容量为m的样本\({x_{1},…,x_{m}}\),以及相关的输出\({y_{1},…,y_{m}}\)
    • 计算梯度和误差,更新G的每个元素,再根据G以及梯度计算参数更新量

Adadelta

核心思想
  • 是Adagrad的一个扩展,目标是解决Adagrad学习率单调下降的问题
  • 解决方案:只累计一段时间内的平方梯度值?
  • 实际上实现是累加时给前面的平方梯度和一个衰减值
  • 方法名delta的来源是选取部分
参数更新公式
  • 将矩阵G的每一项变成当前梯度平方加上过去梯度平方的衰减值(指数衰减)即可
    • 指数衰减:前n-1项的系数是衰减率的n-1次方
    • 实现指数衰减
    • 在Adagrad的基础上修改为: \(G_t = \gamma G_{t-1} + (1-\gamma)g_t^2\)
      • 注意: 这里\(g_t^2\)是指向量按照维度分别相乘, 计算后还是原始向量维度
    • 我们通常也把 \(G_t\) 表达为 \(E[g^2]_t\)
      • 因为修改后的 \(G_t\)可以视为于对 \(g_t^2\) 求期望(不同的\(t\)概率权重不一样的分布的期望)
      • 进一步表达为: \(E[g^2]_t = \gamma E[g^2]_{t-1} + (1-\gamma)g_t^2\)
小结
  • 经过衰减后,G的每一项(忽略掉平滑项\(\epsilon\))相当于有权重的梯度均方差(Root Mean Square, RMS),后面RMSprop算法就用了这个RMS来命名
    • 均方根的定义是:对所有数求平方和,取平均值(每一项的权重根据概率分布可以不同),再开方
  • 学习过程
    • 从训练集中的随机抽取一批容量为m的样本\({x_{1},…,x_{m}}\),以及相关的输出\({y_{1},…,y_{m}}\)
    • 计算梯度和误差,更新G的每个元素,再根据G以及梯度计算参数更新量

RMSprop

Root Mean Square prop

核心思想
  • 一种适应性学习率方法,至今未公开发表
  • 是Adagrad的一个扩展,目标也是解决Adagrad学习率单调下降的问题
  • RMS的来源是由于分母相当于(忽略掉平滑项\(\epsilon\))是梯度的均方根(Root Mean Squared, RMS)
参数更新公式
  • 参见Adadelta
  • RMSprop的本质是对Adadelta简单的取之前值和当前值的权重为0.9和0.1实现指数加权平均, 即 \(\gamma = 0.9\)
  • 有些地方也说RMSprop权重取的是0.5和0.5实现指数加权平均即 \(\gamma = 0.5\)
  • 学习率\(\lambda\)一般取值为0.001
小结
  • RMSprop是Adadelta的一种特殊形式
  • Adagrad的分母不能算是均方差(即使忽略平滑项\(\epsilon\)),因为这里没有取平均值的操作
  • 学习过程
    • 从训练集中的随机抽取一批容量为m的样本\({x_{1},…,x_{m}}\),以及相关的输出\({y_{1},…,y_{m}}\)
    • 计算梯度和误差,更新G的每个元素,再根据G以及梯度计算参数更新量

Adam

Adaptive Moment Estimation

核心思想
  • 一种适应性学习率方法,相当于 RMSprop + Momentum + Bias Correction
  • 像Adadelta和RMSprop一样存储了梯度的平方的指数衰减平均值
  • 像Momentum一样保持了过去梯度的指数衰减平均值
  • Bias Correction是为了得到期望的无偏估计
参数更新公式
  • \(\theta_{t} = \theta_{t-1} - \frac{\lambda}{\sqrt{\tilde{v}_t+\epsilon}} \tilde{m}_t\)
  • \(\tilde{v}_t=\frac{v_{t}}{1-\beta_{1}^{t}}\)
  • \(\tilde{m}_t=\frac{m_{t}}{1-\beta_{2}^{t}}\)
  • 梯度平方的指数衰减:\(v_{t} = \beta_{1}v_{t-1}+(1-\beta_{1})g_{t}^{2}\)
  • 梯度向量的指数衰减:\(m_{t} = \beta_{2}m_{t-1}+(1-\beta_{2})g_{t}\)
    • \(m_t\) 和 \(v_t\) 是对梯度一阶矩估计和二阶矩估计
    • \(m_t\) 和 \(v_t\) 可以看做是对期望 \(E[g]_t\) 和 \(E[g^2]_t\) 的估计
    • \(\tilde{m}_t\) 和 \(\tilde{v}_t\) 是对 \(m_t\) 和 \(v_t\) 的 Bias Correction, 这样可以近似为对对期望 \(E[g]_t\) 和 \(E[g^2]_t\) 的无偏估计
小结
  • 超参数设定推荐
    • 梯度平方衰减率:\(\beta_{1}=0.999\)
    • 梯度动量衰减率:\(\beta_{2}=0.9\)
    • 平滑项:\(\epsilon=10e^-8=1*10^{-8}\)
    • 一阶动量v,初始化为0
    • 二街动量m,初始化为0
  • 学习过程
    • 从训练集中的随机抽取一批容量为m的样本\({x_{1},…,x_{m}}\),以及相关的输出\({y_{1},…,y_{m}}\)
    • 计算梯度和误差,更新v和m,再根据v和m以及梯度计算参数更新量

各种优化方法的比较

鞍点

  • SGD optimization on saddle point

等高线表面

  • SGD optimization on loss surface contours

  • 上面两种情况都可以看出，Adagrad, Adadelta, RMSprop 几乎很快就找到了正确的方向并前进，收敛速度也相当快，而其它方法要么很慢，要么走了很多弯路才找到

  • 由图可知自适应学习率方法即 Adagrad, Adadelta, RMSprop, Adam 在这种情景下会更合适而且收敛性更好

如何选择

  • 如果数据是稀疏的，就用自适用方法，即 Adagrad, Adadelta, RMSprop, Adam
    • 因为他们能够为出现更新次数少(确切的说是梯度累计结果小)的特征分配更高的权重
  • RMSprop, Adadelta, Adam 在很多情况下的效果是相似的
  • Adam 可解释为 RMSprop + Momentum + Bias Correction
  • 随着梯度变的稀疏，Adam 比 RMSprop 效果会好
  • 整体来讲，Adam 是最好的选择
  • 很多论文里都会用 SGD，没有 momentum 等, SGD 虽然能达到极小值，但是比其它算法用的时间长，而且可能会被困在鞍点, 在不正确的方向上来回震荡
  • 如果需要更快的收敛，或者是训练更深更复杂的神经网络，需要用一种自适应的算法