自学内容网 自学内容网

优化理论及应用精解【23】

优化

Nesterov加速梯度

是一种优化算法,由Yurii Nesterov于1983年提出,是梯度下降算法的一种改进,也是目前最常用的优化算法之一。以下是对Nesterov加速梯度的详细解析:

一、定义

Nesterov加速梯度法(Nesterov Accelerated Gradient,简称NAG)是一种用于优化问题的迭代算法,旨在通过预测参数的未来位置来更新,从而加速梯度下降的收敛速度。其核心思想是在计算当前梯度之前,先根据动量项对参数进行一步预测更新。

二、公式

Nesterov加速梯度法的迭代公式如下:

  • 基本公式 x k + 1 = y k − α k ∇ f ( y k ) x_{k+1}=y_k−α_k∇f(y_k) xk+1=ykαkf(yk)

    • 其中, x k x_k xk表示第k次迭代的参数值, y k y_k yk表示估计的下一步的参数值, α k α_k αk表示学习率, ∇ f ( y k ) ∇f(y_k) f(yk)表示在y_k处的梯度。
  • 简化公式 x k + 1 = x k − α k ∇ f ( y k ) x_{k+1}=x_k−α_k∇f(y_k) xk+1=xkαkf(yk)

    • 其中, y k y_k yk可以看作是 x k x_k xk沿着动量方向更新后的预测值。

三、数学原理与推导

Nesterov加速梯度法的数学原理比较复杂,但简单来说,它是通过引入动量项来累积前几次的更新方向,并在计算当前梯度之前先应用动量更新来预测下一步的参数值。这种“前瞻”的方式使得算法能够更智能地选择更新方向,特别是在遇到“陡峭”的梯度变化时,能够提前调整步伐,避免过度冲动。

四、性质

  • 加速收敛:通过预测参数的未来位置来更新,Nesterov加速梯度法能够显著加速梯度下降的收敛速度。
  • 减少震荡:由于引入了动量项,算法在更新参数时能够平滑地穿越平坦区域,减少震荡。
  • 全局最优解:在训练深度神经网络时,Nesterov加速梯度法能够更快地找到全局最优解。

五、例子

假设我们要求解的优化问题是最小化函数f(x),其中x是参数向量。我们可以按照以下步骤使用Nesterov加速梯度法进行优化:

  1. 初始化参数 x 0 x_0 x0和动量 v 0 4 (与 v_04(与 v04(与x_0$同维度的向量)。

  2. 设置学习率η和动量因子γ(通常设置为0.9)。

  3. 对于每次迭代t,执行以下步骤:

    • 预测更新:计算预测的参数位置KaTeX parse error: Expected group after '_' at position 15: x_pred=x_t−γ∗v_̲t。
    • 梯度计算:在预测位置x_pred处计算梯度 g t = ∇ f ( x p r e d ) g_t=∇f(x_pred) gt=f(xpred)
    • 动量更新:更新动量项 v t + 1 = γ ∗ v t − η ∗ g t v_{t+1}=γ∗v_t−η∗g_t vt+1=γvtηgt
    • 参数更新:使用更新后的动量项更新参数 x t + 1 = x t + v t + 1 x_{t+1}=x_t+v_{t+1} xt+1=xt+vt+1

六、例题

例题:使用Nesterov加速梯度法优化二次函数f(x)=(x-3)^2。

解答

  1. 初始化:假设初始参数x_0=0,动量v_0=0,学习率η=0.1,动量因子γ=0.9。

  2. 迭代过程

    • 第一次迭代:
      • 预测更新: x p r e d = x 0 − γ ∗ v 0 = 0 x_pred=x_0−γ∗v_0=0 xpred=x0γv0=0
      • 梯度计算: g 0 = ∇ f ( x p r e d ) = 2 ∗ ( 0 − 3 ) = − 6 g_0=∇f(x_pred)=2∗(0-3)=-6 g0=f(xpred)=2(03)=6
      • 动量更新: v 1 = γ ∗ v 0 − η ∗ g 0 = 0 − 0.1 ∗ ( − 6 ) = 0.6 v_1=γ∗v_0−η∗g_0=0−0.1∗(−6)=0.6 v1=γv0ηg0=00.1(6)=0.6
      • 参数更新: x 1 = x 0 + v 1 = 0 + 0.6 = 0.6 x_1=x_0+v_1=0+0.6=0.6 x1=x0+v1=0+0.6=0.6
    • 第二次迭代:
      • 预测更新: x p r e d = x 1 − γ ∗ v 1 = 0.6 − 0.9 ∗ 0.6 = 0.06 x_pred=x_1−γ∗v_1=0.6−0.9∗0.6=0.06 xpred=x1γv1=0.60.90.6=0.06
      • 梯度计算: g 1 = ∇ f ( x p r e d ) = 2 ∗ ( 0.06 − 3 ) = − 5.88 g_1=∇f(x_pred)=2∗(0.06-3)=-5.88 g1=f(xpred)=2(0.063)=5.88
      • 动量更新: v 2 = γ ∗ v 1 − η ∗ g 1 = 0.9 ∗ 0.6 − 0.1 ∗ ( − 5.88 ) = 1.068 v_2=γ∗v_1−η∗g_1=0.9∗0.6−0.1∗(−5.88)=1.068 v2=γv1ηg1=0.90.60.1(5.88)=1.068
      • 参数更新: x 2 = x 1 + v 2 = 0.6 + 1.068 = 1.668 x_2=x_1+v_2=0.6+1.068=1.668 x2=x1+v2=0.6+1.068=1.668
    • 以此类推,直到收敛到最优解x=3。

通过以上步骤,我们可以看到Nesterov加速梯度法如何逐步优化参数,使其接近目标函数的最小值。

AdaGrad(Adaptive Gradient Algorithm)

是一种自适应学习率的梯度下降算法,由Duchi等人于2011年提出。以下是对AdaGrad的详细解析:

一、定义

AdaGrad是一种优化算法,旨在解决传统梯度下降算法中学习率一成不变的问题。它通过计算参数梯度的历史累积平方和,为每个参数自适应地调整学习率,从而在训练过程中动态调整每个参数的学习率,以适应不同的参数更新场景。

二、公式

AdaGrad的公式如下:

  • 学习率更新公式

η t = η 01 + ∑ t i = 1 ( ∇ w J ( w i ) ) 2 ηt=η01+∑ti=1(∇wJ(wi))2 ηt=η01+ti=1(wJ(wi))2

η t = η 0 √ ∑ t i = 1 ( ∇ w J ( w i ) ) 2 + ϵ ηt=η0√∑ti=1(∇wJ(wi))2+ϵ ηt=η0√ti=1(wJ(wi))2+ϵ

  • 参数更新公式

w t + 1 = w t − η t ∇ w J ( w t ) wt+1=wt−ηt∇wJ(wt) wt+1=wtηtwJ(wt)

其中,η0是初始学习率, ∇ w J ( w i ) ∇wJ(wi) wJ(wi)是第i次迭代时参数w的梯度, ϵ ϵ ϵ是一个很小的常数,用于防止分母为零。

三、数学原理与推导

AdaGrad的数学原理基于梯度下降算法,但引入了自适应学习率的概念。在标准的梯度下降算法中,所有参数都使用相同的学习率进行更新,这可能导致学习率过大时在最小值附近震荡,或学习率过小时收敛速度过慢。AdaGrad通过计算每个参数梯度的历史累积平方和,为每个参数自适应地调整学习率。具体推导过程如下:

  1. 初始化参数w和学习率η。
  2. 在每次迭代中,计算当前参数w的梯度 ∇ w J ( w ) ∇wJ(w) wJ(w)
  3. 累积梯度平方和,即更新∑ti=1(∇wJ(wi))2。
  4. 根据累积的梯度平方和计算当前的学习率ηt。
  5. 使用当前学习率ηt更新参数w。

四、性质

  • 自适应学习率:AdaGrad根据每个参数的历史梯度平方和自适应地调整学习率,减少了手动调节学习率的需要。
  • 适合稀疏数据:对于稀疏特征,AdaGrad能够自动提高其学习率,使得模型更快地学习到这些特征的重要性。
  • 学习率持续衰减:由于累积的平方梯度持续增加,学习率会持续衰减,最终导致学习率过小,从而使得训练后期模型难以收敛。
  • 内存开销:需要为每个参数存储一个累积的梯度平方和,这在参数很多时会增加额外的内存开销。

五、例子

假设我们有一个简单的二次损失函数J(w)=(w−3)2,我们使用AdaGrad算法来优化参数w。

  1. 初始化参数w0=0,学习率η0=0.1,累积梯度平方和G=0。
  2. 在第一次迭代中,计算梯度 ∇ w J ( w 0 ) = 2 ( 0 − 3 ) = − 6 ∇wJ(w0)=2(0−3)=−6 wJ(w0)=2(03)=6
  3. 更新累积梯度平方和 G = G + ( − 6 ) 2 = 36 G=G+(−6)2=36 G=G+(6)2=36
  4. 计算当前学习率 η 1 = η 0 √ 36 + ϵ = 0.1 √ 36 + 1 e − 8 ≈ 0.0167 η1=η0√36+ϵ=0.1√36+1e−8≈0.0167 η1=η0√36+ϵ=0.1√36+1e80.0167
  5. 更新参数 w 1 = w 0 − η 1 ∇ w J ( w 0 ) = 0 − 0.0167 × ( − 6 ) = 0.1 w1=w0−η1∇wJ(w0)=0−0.0167×(−6)=0.1 w1=w0η1∇wJ(w0)=00.0167×(6)=0.1

六、例题

例题:使用AdaGrad算法优化损失函数 J ( w ) = ( w − 5 ) 2 J(w)=(w−5)2 J(w)=(w5)2,并给出前两次迭代的参数更新过程。

解答

  1. 初始化参数w0=0,学习率η0=0.1,累积梯度平方和G=0。

  2. 在第一次迭代中:

    • 计算梯度 ∇ w J ( w 0 ) = 2 ( 0 − 5 ) = − 10 ∇wJ(w0)=2(0−5)=−10 wJ(w0)=2(05)=10
    • 更新累积梯度平方和 G = G + ( − 10 ) 2 = 100 G=G+(−10)2=100 G=G+(10)2=100
    • 计算当前学习率 η 1 = η 0 √ 100 + ϵ = 0.1 √ 100 + 1 e − 8 ≈ 0.01 η1=η0√100+ϵ=0.1√100+1e−8≈0.01 η1=η0√100+ϵ=0.1√100+1e80.01
    • 更新参数 w 1 = w 0 − η 1 ∇ w J ( w 0 ) = 0 − 0.01 × ( − 10 ) = 0.1 w1=w0−η1∇wJ(w0)=0−0.01×(−10)=0.1 w1=w0η1∇wJ(w0)=00.01×(10)=0.1
  3. 在第二次迭代中:

    • 计算梯度 ∇ w J ( w 1 ) = 2 ( 0.1 − 5 ) = − 9.8 ∇wJ(w1)=2(0.1−5)=−9.8 wJ(w1)=2(0.15)=9.8
    • 更新累积梯度平方和 G = G + ( − 9.8 ) 2 ≈ 196.04 G=G+(−9.8)2≈196.04 G=G+(9.8)2196.04
    • 计算当前学习率 η 2 = η 0 √ 196.04 + ϵ = 0.1 √ 196.04 + 1 e − 8 ≈ 0.0071 η2=η0√196.04+ϵ=0.1√196.04+1e−8≈0.0071 η2=η0√196.04+ϵ=0.1√196.04+1e80.0071
    • 更新参数 w 2 = w 1 − η 2 ∇ w J ( w 1 ) = 0.1 − 0.0071 × ( − 9.8 ) ≈ 0.1696 w2=w1−η2∇wJ(w1)=0.1−0.0071×(−9.8)≈0.1696 w2=w1η2∇wJ(w1)=0.10.0071×(9.8)0.1696

通过以上步骤,我们可以看到AdaGrad算法如何根据每个参数的历史梯度平方和自适应地调整学习率,并逐步优化参数w。

参考文献

  1. 文心一言

原文地址:https://blog.csdn.net/sakura_sea/article/details/142726064

免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!