【优化算法】3. 学习率优化算法

文章目录

• 概论
• 基础
• • 牛顿法
  • 稀疏特征的学习率
• AdaGrad
• Adadelta
• RMSProp算法
• Adam
• Yogi

概论

学习率(learning rate)决定目标函数能否收敛到最小值，和何时收敛到最小值。如果直接设定一个学习率η，是一个很棘手的问题。学习率η设定太小，算法就会进展缓慢，设定太大，就会震荡或者发散。针对这样的问题，就产生了学习率自适应算法。

基础 牛顿法

函数 f : R d → R f: \mathbb{R}^d \rightarrow \mathbb{R} f:Rd→R的泰勒展开式，事实上我们可以把它写成

f ( x + ϵ ) = f ( x ) + ϵ ⊤ ∇ f ( x ) + 1 2 ϵ ⊤ ∇ 2 f ( x ) ϵ + O ( ∥ ϵ ∥ 3 ) . f(\mathbf{x} + \boldsymbol{\epsilon}) = f(\mathbf{x}) + \boldsymbol{\epsilon}^\top \nabla f(\mathbf{x}) + \frac{1}{2} \boldsymbol{\epsilon}^\top \nabla^2 f(\mathbf{x}) \boldsymbol{\epsilon} + \mathcal{O}(\|\boldsymbol{\epsilon}\|^3). f(x+ϵ)=f(x)+ϵ⊤∇f(x)+21​ϵ⊤∇2f(x)ϵ+O(∥ϵ∥3).

为了避免繁琐的符号，我们将 H = d e f ∇ 2 f ( x ) \mathbf{H} \stackrel{\mathrm{def}}{=} \nabla^2 f(\mathbf{x}) H=def∇2f(x)定义为 f f f的Hessian，是 d × d d \times d d×d矩阵。当 d d d的值很小且问题很简单时， H \mathbf{H} H很容易计算。但是对于深度神经网络而言，考虑到 H \mathbf{H} H可能非常大， O ( d 2 ) \mathcal{O}(d^2) O(d2)个条目的存储代价会很高，
此外通过反向传播进行计算可能雪上加霜。然而，我们姑且先忽略这些考量，看看会得到什么算法。

毕竟， f f f的最小值满足 ∇ f = 0 \nabla f = 0 ∇f=0。遵循的微积分规则，通过取 ϵ \boldsymbol{\epsilon} ϵ对 f f f的导数，再忽略不重要的高阶项，我们便得到

∇ f ( x ) + H ϵ = 0  and hence  ϵ = − H − 1 ∇ f ( x ) . \nabla f(\mathbf{x}) + \mathbf{H} \boldsymbol{\epsilon} = 0 \text{ and hence } \boldsymbol{\epsilon} = -\mathbf{H}^{-1} \nabla f(\mathbf{x}). ∇f(x)+Hϵ=0 and hence ϵ=−H−1∇f(x).

也就是说，作为优化问题的一部分，我们需要将Hessian矩阵 H \mathbf{H} H求逆。

举一个简单的例子，对于 f ( x ) = 1 2 x 2 f(x) = \frac{1}{2} x^2 f(x)=21​x2，我们有 ∇ f ( x ) = x \nabla f(x) = x ∇f(x)=x和 H = 1 \mathbf{H} = 1 H=1。因此，对于任何 x x x，我们可以获得 ϵ = − x \epsilon = -x ϵ=−x。换言之，单单一步就足以完美地收敛，而无须任何调整。我们在这里比较幸运：泰勒展开式是确切的，因为 f ( x + ϵ ) = 1 2 x 2 + ϵ x + 1 2 ϵ 2 f(x+\epsilon)= \frac{1}{2} x^2 + \epsilon x + \frac{1}{2} \epsilon^2 f(x+ϵ)=21​x2+ϵx+21​ϵ2。

稀疏特征的学习率

在深度学习训练中，为了获得良好的准确性，我们希望在训练过程中降低学习率，速度通常是为 O ( t − 1 2 ) \mathcal{O}(t^{-\frac{1}{2}}) O(t−21​)或更低。这种情况下，我们在训练过程中就会遇到以下情况：

• 常用特征的参数迅速收敛的最佳值，学习率相对来说降低太慢。
• 稀疏特征因为缺乏足够的观测数据收敛很慢，学习率对其来说降低太快。

为了解决这个问题，我们可以通过记录特征次数来调整对应的学习率。我们使用 η i = η 0 s ( i , t ) + c \eta_i = \frac{\eta_0}{\sqrt{s(i, t) + c}} ηi​=s(i,t)+c ​η0​​的学习率，而不是 η = η 0 t + c \eta = \frac{\eta_0}{\sqrt{t + c}} η=t+c ​η0​​。 s ( i , t ) s(i, t) s(i,t)计下了我们截至 t t t时观察到功能 i i i的次数。

AdaGrad

AdaGrad算法使用先前所得梯度平方和 s ( i , t + 1 ) = s ( i , t ) + ( ∂ i f ( x ) ) 2 s(i, t+1) = s(i, t) + \left(\partial_i f(\mathbf{x})\right)^2 s(i,t+1)=s(i,t)+(∂i​f(x))2来替代 s ( i , t ) s(i, t) s(i,t)来调整学习率。算法有两个优点：

• 不需要决定梯度何时算足够大。
• 学习率会随着梯度大小自动变化。梯度较大时学习率会显著缩小，梯度较小时学习率会平滑处理。

我们使用 s t s_t st​来累加过去的梯度方差：
g t = ∂ w l ( y t , f ( x t , w ) ) s t = s t − 1 + g t 2 w t = w t − 1 − η s t + ϵ ⋅ g t \mathbf{g}_t=\partial_{\mathbf{w}} l(y_t, f(\mathbf{x}_t, \mathbf{w})) \ \mathbf{s}_t= \mathbf{s}_{t-1} + \mathbf{g}_t^2 \ \mathbf{w}_t = \mathbf{w}_{t-1} -\frac{\eta}{\sqrt{\mathbf{s}_t+\epsilon}}\cdot \mathbf{g}_t gt​=∂w​l(yt​,f(xt​,w))st​=st−1​+gt2​wt​=wt−1​−st​+ϵ ​η​⋅gt​
随着算法不断迭代， s \mathbf{s} s不断变大，学习率就越来越小。

Adadelta

Adadelta算法是AdaGrad算法的变体。主要的不同是Adadelta算法减少了学习率适应坐标的数量，简单说就是计算大小为w的时间区间内的梯度值的累积和，代替使用所有梯度值的平方和。而且，adadelta也被称为没有学习率，因为它使用变化量本身作为未来变化的校准。

Adadelta使用两个状态变量 s t \mathbf{s}_t st​和 Δ x t \Delta \mathbf{x}_t Δxt​，其中 s t \mathbf{s}_t st​存储梯度二阶导数的泄漏平均值， Δ x t \Delta \mathbf{x}_t Δxt​存储的是模型本身中参数变化二阶导数的泄漏平均值。

梯度泄漏更新： s t = ρ s t − 1 + ( 1 − ρ ) g t 2 . \mathbf{s}_t = \rho \mathbf{s}_{t-1} + (1 - \rho) \mathbf{g}_t^2. st​=ρst−1​+(1−ρ)gt2​.

使用重新缩放的梯度 g t ′ \mathbf{g}_t' gt′​执行更新： x t = x t − 1 − g t ′ \mathbf{x}_t=\mathbf{x}_{t-1}-\mathbf{g}_t' xt​=xt−1​−gt′​

其中： g t ′ = Δ x t − 1 + ϵ s t + ϵ ⊙ g t \mathbf{g}_t'=\frac{\sqrt{\Delta \mathbf{x}_{t-1} + \epsilon}}{\sqrt{s_t+\epsilon}} \odot \mathbf{g}_t gt′​=st​+ϵ ​Δxt−1​+ϵ ​​⊙gt​

Δ x t − 1 \Delta \mathbf{x}_{t-1} Δxt−1​是重新缩放梯度的平方 g t ′ \mathbf{g}_t' gt′​​的泄漏平均值。我们将 Δ x 0 \Delta \mathbf{x}_{0} Δx0​初始化为 0 0 0，然后在每个步骤中使用 g t ′ \mathbf{g}_t' gt′​更新它，即：

Δ x t = ρ Δ x t − 1 + ( 1 − ρ ） g t ′ 2 \Delta \mathbf{x}_t = \rho \Delta\mathbf{x}_{t-1} + (1 - \rho）{\mathbf{g}_t'}^2 Δxt​=ρΔxt−1​+(1−ρ）gt′​2 。

RMSProp算法

Root mean Square Prop算法，算法将速率调度与坐标自适应学习率分离进行简单修复。AdaGrad算法将梯度 g t \mathbf{g}_t gt​的平方累加成状态矢量 s t = s t − 1 + g t 2 \mathbf{s}_t = \mathbf{s}_{t-1} + \mathbf{g}_t^2 st​=st−1​+gt2​，因此学习率是不断缩减的。

要解决这个问题可以用以下两种方法

• 使用 s t / t \mathbf{s}_t / t st​/t。对于 g t \mathbf{g}_t gt​的合理分布来说，它将收敛。遗憾的是，限制行为生效可能需要很长时间，因为该流程记住了值的完整轨迹。
• 另一种方法是按动量法中的方式使用泄漏平均值，即 s t ← γ s t − 1 + ( 1 − γ ) g t 2 \mathbf{s}_t \leftarrow \gamma \mathbf{s}_{t-1} + (1-\gamma) \mathbf{g}_t^2 st​←γst−1​+(1−γ)gt2​，其中参数 γ > 0 \gamma > 0 γ>0。
  保持所有其它部分不变就产生了RMSProp算法。

算法详情：

s t ← γ s t − 1 + ( 1 − γ ) g t 2 , x t ← x t − 1 − η s t + ϵ ⊙ g t . \begin{aligned} \mathbf{s}_t & \leftarrow \gamma \mathbf{s}_{t-1} + (1 - \gamma) \mathbf{g}_t^2, \ \mathbf{x}_t & \leftarrow \mathbf{x}_{t-1} - \frac{\eta}{\sqrt{\mathbf{s}_t + \epsilon}} \odot \mathbf{g}_t. \end{aligned} st​xt​​←γst−1​+(1−γ)gt2​,←xt−1​−st​+ϵ ​η​⊙gt​.​

常数 ϵ > 0 \epsilon > 0 ϵ>0通常设置为 1 0 − 6 10^{-6} 10−6，以确保我们不会因除以零或步长过大而受到影响。鉴于这种扩展，我们现在可以自由控制学习率 η \eta η，而不考虑基于每个坐标应用的缩放。就泄漏平均值而言，我们可以采用与之前在动量法中适用的相同推理。扩展 s t \mathbf{s}_t st​定义可获得
s t = ( 1 − γ ) g t 2 + γ s t − 1 = ( 1 − γ ) ( g t 2 + γ g t − 1 2 + γ 2 g t − 2 + … , ) . \begin{aligned} \mathbf{s}_t & = (1 - \gamma) \mathbf{g}_t^2 + \gamma \mathbf{s}_{t-1} \ & = (1 - \gamma) \left(\mathbf{g}_t^2 + \gamma \mathbf{g}_{t-1}^2 + \gamma^2 \mathbf{g}_{t-2} + \ldots, \right). \end{aligned} st​​=(1−γ)gt2​+γst−1​=(1−γ)(gt2​+γgt−12​+γ2gt−2​+…,).​

我们使用 1 + γ + γ 2 + … , = 1 1 − γ 1 + \gamma + \gamma^2 + \ldots, = \frac{1}{1-\gamma} 1+γ+γ2+…,=1−γ1​。因此，权重总和标准化为 1 1 1且观测值的半衰期为 γ − 1 \gamma^{-1} γ−1。

Adam

Adam算法的关键组成部分之一是：它使用指数加权移动平均值来估算梯度的动量和二次矩，即它使用状态变量

v t ← β 1 v t − 1 + ( 1 − β 1 ) g t , s t ← β 2 s t − 1 + ( 1 − β 2 ) g t 2 . \begin{aligned} \mathbf{v}_t & \leftarrow \beta_1 \mathbf{v}_{t-1} + (1 - \beta_1) \mathbf{g}_t, \ \mathbf{s}_t & \leftarrow \beta_2 \mathbf{s}_{t-1} + (1 - \beta_2) \mathbf{g}_t^2. \end{aligned} vt​st​​←β1​vt−1​+(1−β1​)gt​,←β2​st−1​+(1−β2​)gt2​.​

这里 β 1 \beta_1 β1​和 β 2 \beta_2 β2​是非负加权参数。常将它们设置为 β 1 = 0.9 \beta_1 = 0.9 β1​=0.9和 β 2 = 0.999 \beta_2 = 0.999 β2​=0.999​。也就是说，方差估计的移动远远慢于动量估计的移动。注意，如果我们初始化 v 0 = s 0 = 0 \mathbf{v}_0 = \mathbf{s}_0 = 0 v0​=s0​=0，就会获得一个相当大的初始偏差。我们可以通过使用 ∑ i = 0 t β i = 1 − β t 1 − β \sum_{i=0}^t \beta^i = \frac{1 - \beta^t}{1 - \beta} ∑i=0t​βi=1−β1−βt​来解决这个问题。相应地，标准化状态变量由下式获得

v ^ t = v t 1 − β 1 t  and  s ^ t = s t 1 − β 2 t . \hat{\mathbf{v}}_t = \frac{\mathbf{v}_t}{1 - \beta_1^t} \text{ and } \hat{\mathbf{s}}_t = \frac{\mathbf{s}_t}{1 - \beta_2^t}. v^t​=1−β1t​vt​​ and s^t​=1−β2t​st​​.

有了正确的估计，我们现在可以写出更新方程。首先，我们以非常类似于RMSProp算法的方式重新缩放梯度以获得

g t ′ = η v ^ t s ^ t + ϵ . \mathbf{g}_t' = \frac{\eta \hat{\mathbf{v}}_t}{\sqrt{\hat{\mathbf{s}}_t} + \epsilon}. gt′​=s^t​ ​+ϵηv^t​​.

与RMSProp不同，我们的更新使用动量 v ^ t \hat{\mathbf{v}}_t v^t​而不是梯度本身。此外，由于使用 1 s ^ t + ϵ \frac{1}{\sqrt{\hat{\mathbf{s}}_t} + \epsilon} s^t​ ​+ϵ1​而不是 1 s ^ t + ϵ \frac{1}{\sqrt{\hat{\mathbf{s}}_t + \epsilon}} s^t​+ϵ ​1​进行缩放，两者会略有差异。前者在实践中效果略好一些，因此与RMSProp算法有所区分。通常，我们选择 ϵ = 1 0 − 6 \epsilon = 10^{-6} ϵ=10−6，这是为了在数值稳定性和逼真度之间取得良好的平衡。最后，我们简单更新：

x t ← x t − 1 − g t ′ . \mathbf{x}_t \leftarrow \mathbf{x}_{t-1} - \mathbf{g}_t'. xt​←xt−1​−gt′​.

回顾Adam算法，它的设计灵感很清楚：首先，动量和规模在状态变量中清晰可见，它们相当独特的定义使我们移除偏项（这可以通过稍微不同的初始化和更新条件来修正）。其次，RMSProp算法中两项的组合都非常简单。最后，明确的学习率 η \eta η使我们能够控制步长来解决收敛问题。

Yogi

Adam算法也存在一些问题：即使在凸环境下，当 s t \mathbf{s}_t st​的二次矩估计值爆炸时，它可能无法收敛。针对 s t \mathbf{s}_t st​提出了的改进更新和参数初始化。重写Adam算法更新如下：

s t ← s t − 1 + ( 1 − β 2 ) ( g t 2 − s t − 1 ) . \mathbf{s}_t \leftarrow \mathbf{s}_{t-1} + (1 - \beta_2) \left(\mathbf{g}_t^2 - \mathbf{s}_{t-1}\right). st​←st−1​+(1−β2​)(gt2​−st−1​).

每当 g t 2 \mathbf{g}_t^2 gt2​具有值很大的变量或更新很稀疏时， s t \mathbf{s}_t st​可能会太快地“忘记”过去的值。一个有效的解决方法是将 g t 2 − s t − 1 \mathbf{g}_t^2 - \mathbf{s}_{t-1} gt2​−st−1​替换为 g t 2 ⊙ s g n ( g t 2 − s t − 1 ) \mathbf{g}_t^2 \odot \mathop{\mathrm{sgn}}(\mathbf{g}_t^2 - \mathbf{s}_{t-1}) gt2​⊙sgn(gt2​−st−1​)。这就是Yogi更新，现在更新的规模不再取决于偏差的量。

s t ← s t − 1 + ( 1 − β 2 ) g t 2 ⊙ s g n ( g t 2 − s t − 1 ) . \mathbf{s}_t \leftarrow \mathbf{s}_{t-1} + (1 - \beta_2) \mathbf{g}_t^2 \odot \mathop{\mathrm{sgn}}(\mathbf{g}_t^2 - \mathbf{s}_{t-1}). st​←st−1​+(1−β2​)gt2​⊙sgn(gt2​−st−1​).