精华内容
下载资源
问答
  • 梯度下降算法中的Adagrad和Adadelta

    千次阅读 2017-08-15 23:52:43
    与梯度下降不同的是,更新规则中,对于学习率不在设置固定的值,每次迭代过程中,每个参数优化时使用不同的学习率。  假设 某次迭代时刻t,gt,i=∇θJ(θi)是目标函数对参数的梯度,普通的随机梯度下降算法,对于...

    Adagrad

    与梯度下降不同的是,更新规则中,对于学习率不在设置固定的值,每次迭代过程中,每个参数优化时使用不同的学习率。 
    假设 某次迭代时刻t, gt,i=θJ(θi) 是目标函数对参数的梯度,普通的随机梯度下降算法,对于所有的 θi 都使用相同的学习率,因此迭代到第t次时,某一个参数向量 θi 的变化过程如下: 

    θt+1,i=θt,iηgt,i

    而在Adagrad的更新规则中,学习率  η  会随着每次迭代而根据历史梯度的变化而变化。 
    θt+1,i=θt,iηGt+ϵgt,i

    GtRd×d 是一个对角矩阵,每个对角线位置 i,i 的值累加到t次迭代的对应参数  θi  梯度平方和。 ϵ 是平滑项,防止除零操作,一般取值 1e8 。为什么分母要进行平方根的原因是去掉平方根操作算法的表现会大打折扣。

    Adadelta

    为了避免前文提到的问题,削弱单调猛烈下降的减少学习率,Adadelta产生了1。Adadelta限制把历史梯度累积窗口限制到固定的尺寸 w ,而不是累加所有的梯度平方和。 
    Adagrad的一大优势时可以避免手动调节学习率,比如设置初始的缺省学习率为0.01,然后就不管它,另其在学习的过程中自己变化。当然它也有缺点,就是它计算时要在分母上计算梯度平方的和,由于所有的参数平法必为正数,这样就造成在训练的过程中,分母累积的和会越来越大。这样学习到后来的阶段,网络的更新能力会越来越弱,能学到的更多知识的能力也越来越弱,因为学习率会变得极其小,为了解决这样的问题又提出了Adadelta算法。 
    梯度和是递归的定义成历史梯度平方的衰减平均值。动态平均值 E[g2]t 仅仅取决于当前的梯度值与上一时刻的平均值:

    E[g2]t=γE[g2]t1+(1γ)g2t

    γ 类似于冲量项,大约在0.9附近。需要说明的是,现在将SGD更新的参数变化向量 θt : 
    θt=ηgt,i

    θt+1=θt+θt

    在Adagrad中, θt 是由
    θt=ηGt+ϵgt,i
    表示的,现在用 E[g2]t 简单代替原来的对角矩阵 Gt
    θt=ηE[g2]t+ϵgt,i

    将分母简记为RMS,表示梯度的均方根误差的意思。 
    θt=ηRMS[g]tgt

    [6]作者说,更新中,定义指数衰减均值,代替梯度平方,二用参数平方来更新: 
    E[θ2t]t=γE[θ2t]t1+(1γ)θ2t
    RMS[θ]t1 代替学习率 η ,则得到Adadelta更新规则: 
    θt=RMS[θ]t1RMS[g]tgt

    θt+1=θt+θt

    由此看出,甚至不需要设定缺省学习率,因为更新规则已经不受它影响了
    展开全文
  • 二、Adagrad 注意是逐个元素应用,所以可以使每个参数的学习率不同 从上图可以看出,随着迭代的增加,我们的学习率是在逐渐变小的,这在“直观上”是正确的: 当我们越接近最优解时,函数的“坡度”会越平缓

    一、 Momentum

    如下图图 a 所示,当一个维度比另一个维度下降地明显更加急促时(经常是局部最优点),朴素 SGD 容易存在收敛极慢的问题。
    在这里插入图片描述

    momentum(动量)的引入可以直观地较好处理这个问题,其在计算当前时刻的更新向量vt 时,引入了上一次更新向量 vt-1,具体如下:
    在这里插入图片描述
    γ一般为0.9
    在这里插入图片描述

    二、Adagrad

    注意是逐个元素应用,所以可以使每个参数的学习率不同
    在这里插入图片描述
    从上图可以看出,随着迭代的增加,我们的学习率是在逐渐变小的,这在“直观上”是正确的:
    当我们越接近最优解时,函数的“坡度”会越平缓,我们也必须走的更慢来保证不会穿过最优解。

    AdaGrad的效果是:
    在参数空间中更为平缓的倾斜方向会取得更大的进步(因为平缓,所以历史梯度平方和较小,对应学习下降的幅度较小)。

    优点:

    Adagrad的最大优势是初始学习率(一般为0.01)设定后不用管,其可以为不同参数自适应地调整学习率。

    缺点:Adagrad的学习率消失问题

    但同时,随着训练进行 分母的平方项 是一个不断增长的过程,注定了其学习率是一个不断减小直至小到网络无法学习到新信息的过程。(2)需要手动设置全局学习率

    三、RMSProp

    Adagrad的学习率消失问题
    在这里插入图片描述
    在这里插入图片描述

    四、adam

    Adam相当于RMSProp+Momentum将两者方法的优势结合起来,集大成者。
    Momentum使用一阶梯度,RMSProp使用了二阶梯度,Adam二者均使用。

    一阶梯度:
    在这里插入图片描述
    二阶梯度:
    在这里插入图片描述
    偏差修正:
    在训练前期,梯度权值之和比较小,需要将权值之和修正为1。
    mt,vt对应梯度gt的一阶、二阶矩估计,是有偏估计,校正为无偏估计:
    在这里插入图片描述
    在这里插入图片描述
    Adam更新规则:
    在这里插入图片描述
    Adam对学习率没有那么敏感,建议默认为0.001,实践中,也可以设置为5*10^-4。Adam通常被认为对超参数的选择相当鲁棒,同时相比于Adagrad,不用存储全局所有的梯度,适合处理大规模数据。

    展开全文
  • momentum、AdaGrad、RMSProp、Adam 方法是对定步长SGD的改进。本文做了介绍和总结,并给出了代码模拟。


    深度模型中的优化——momentum|AdaGrad|RMSProp|Adam

    在随机梯度下降中,沿着最速下降方向可以得到最快的下降速度: x t + 1 = x t − λ ▽ f ( x t ) x_{t+1}=x_t-\lambda \triangledown f(x_t) xt+1=xtλf(xt)。其中, λ \lambda λ是下降步长,也被称为学习率

    在常见的SGD算法中,批量梯度下降(BSGD)的算法如下:(引用《深度学习》(花书)P180)

    算法:随机梯度下降(SGD)在第 k k k个训练迭代的更新


    Require: 学习率 ϵ k \epsilon_k ϵk

    Require: 初始参数 θ \theta θ

    while 停止准则未满足 do

    ​ 从训练集中采样 m m m个样本 x ( 1 ) , … , x ( m ) {x^{(1)},\dots,x^{(m)}} x(1),,x(m),其中 x ( i ) x^{(i)} x(i)对应的目标为 y ( i ) y^{(i)} y(i)

    ​ 计算梯度估计: g ^ ← + 1 m ▽ θ ∑ i L ( f ( x ( i ) ; θ ) , y ( i ) ) \hat g \leftarrow +\frac{1}{m}\triangledown_\theta\sum_i{L(f(x^{(i)};\theta), y^{(i)})} g^+m1θiL(f(x(i);θ),y(i))

    ​ 应用更新: θ ← θ − ϵ g ^ \theta \leftarrow \theta - \epsilon \hat g θθϵg^

    end while


    PS:花书中把学习率记为 ϵ \epsilon ϵ,把收敛条件记为 λ \lambda λ.

    下降步长对梯度下降的影响

    一个简单的例子:给定目标函数 f ( x ) = x 2 f(x)=x^2 f(x)=x2,初始点 x 0 = 1 x_0=1 x0=1,其梯度(导数)为 2 x 2x 2x,给定步长 λ = 1 \lambda=1 λ=1,根据上文的更新公式计算 x 1 = x 0 − λ × 2 x_1=x_0-\lambda \times 2 x1=x0λ×2,发现 f ( x 1 ) = f ( x 0 ) f(x_1)=f(x_0) f(x1)=f(x0);继续进行下降更新,发现 x 2 = 1 = x 0 … x_2=1=x_0\dots x2=1=x0;如此反复,搜寻结果会反复在[-1, 1]之间横跳,且目标函数的值并不下降。

    显然,随着训练的推进,我们应当逐渐减小下降步长。保证SGD收敛的一个充分条件是:
    ∑ k = 1 ∞ ϵ k = ∞ ,   A N D   ∑ k = 1 ∞ ϵ k 2 < ∞ \sum_{k=1}^\infin \epsilon_k=\infin, \ AND \ \sum_{k=1}^\infin \epsilon^2_k<\infin k=1ϵk=, AND k=1ϵk2<
    对于学习率/下降步长的选择设置,主要有以下两种情况:

    • 设置过大,会出现剧烈的震荡,甚至完全不收敛;
    • 设置过小,学习过程非常缓慢,且容易卡在一个局部最优值。

    对于BSGD,一个比较有意思的现象是当训练的批次样本较多时,他更容易收敛。在本文中我们只在一维上进行搜索,因此很容易出现不收敛的现象。

    学习率优化算法的衡量标准

    引入额外误差(excess error) J ( θ ) − m i n θ J ( θ ) J(\theta)-min_\theta J(\theta) J(θ)minθJ(θ),即当前代价函数超出全局最小值的量。在凸问题中,SGD在 k k k步迭代之后的额外误差量级为 O ( 1 k ) O(\frac{1}{\sqrt{k}}) O(k 1),强凸情况下是 1 k \frac{1}{k} k1

    SGD学习率的提升方案

    我们以 f ( x ) = sin ⁡ ( x ) + x 2 f(x)=\sin(x)+x^2 f(x)=sin(x)+x2为例子,先看看它的图像和梯度:(约定本文中所有的图横轴为迭代次数、纵轴为代价)

    import numpy as np
    import matplotlib.pyplot as plt
    
    
    def func(x):
        return np.sin(x) + np.power(x, 2)
    
    
    def grad(x):
        return np.cos(x) + 2 * x
    
    
    xes = np.arange(-5, 5, 0.1)
    plt.plot(xes, func(xes), label="f(x)=sin(x)+x^2")
    plt.plot(xes, [0 for i in xes], '--')
    plt.plot(xes, grad(xes), label="f'(x)=cos(x)+2*x")
    plt.legend()
    plt.show()
    

    origin.png

    线性衰减学习率

    根据SGD的收敛充分条件,我们不难给定一个线性衰减的学习率 α = k τ \alpha=\frac{k}{\tau} α=τk,设定经过 τ \tau τ次迭代之后,令 ϵ \epsilon ϵ保持常数。既有:
    ϵ k = ( 1 − α ) ϵ 0 + α ϵ τ \epsilon_k=(1-\alpha)\epsilon_0+\alpha\epsilon_\tau ϵk=(1α)ϵ0+αϵτ
    通常,设定 ϵ τ \epsilon_\tau ϵτ ϵ 0 \epsilon_0 ϵ0 1 % 1\% 1%左右(令 τ = 100 \tau=100 τ=100),即: ϵ k = ( 1 − 0.99 α 0 → 1 ) ϵ 0 \epsilon_k=(1-0.99\mathop{\alpha}\limits_{0\to1})\epsilon_0 ϵk=(10.9901α)ϵ0;但 ϵ 0 \epsilon_0 ϵ0的设定依旧容易带来函数收敛过程剧烈震荡或收敛过慢的问题,因此有更多优秀的自自适学习率算法被提出,在深度学习框架中有时把这些算法称为优化器

    利用 x t + 1 = x t − λ ▽ f ( x t ) x_{t+1}=x_t-\lambda \triangledown f(x_t) xt+1=xtλf(xt)进行定步长SDG和衰减学习率的下降:

    epsilon = 1e-1  # 停止准则
    lambda0 = 0.1  # 学习率(定长模式下如果给定较大的学习率可能不收敛)
    x0, x1 = -150, 100
    costs = []
    while abs(x1 - x0) >= epsilon:
        costs.append(func(x0))
        
        temp = x1
        x1 = x0 - lambda0 * grad(x0)
        x0 = temp
    print("x* = ", x0)
    plt.plot(range(min(len(costs), 30)), costs[0:30], label="sgd")
    
    
    epsilon = 1e-1  # 停止准则
    tau, k = 100, 1
    lambda0 = 1  # 学习率(可以直接给定一个较大的学习率也能保证收敛)
    lambda_tau = lambda0 / tau
    x0, x1 = -150, 100
    costs, l0 = [], lambda0
    while abs(x1 - x0) >= epsilon:
        costs.append(func(x0))
    
        temp = x1
        x1 = x0 - l0 * grad(x0)
        x0 = temp
    
        alpha = min(k/tau, 1)
        l0 = (1-alpha)*lambda0 + alpha*lambda_tau # 进行衰减
        k += 1
    print("x* = ", x0)
    plt.plot(range(min(len(costs), 30)), costs[0:30], label="sgd-decay")
    
    plt.legend()
    plt.show()
    

    其函数图像如下(可以明显看到衰减学习率方案收敛得更快,但由于给定了大学习率,因此震荡更剧烈):

    sgd.png

    动量下降(momentum)

    动量下降中引入了物理中惯性的概念,就像一个小球从山坡上滚下时,由于惯性的原因会直接冲过一些小坑,然后滚到山脚。在动量下降方案中,各超参数的更新规则如下:

    算法:使用了动量下降方案的SGD


    Require: 学习率 ϵ \epsilon ϵ、动量参数 α \alpha α

    Require: 初始参数 θ \theta θ、初始速度 v v v

    while 没有达到停止准则 do

    ​ 从训练集中采样 m m m个样本 x ( 1 ) , … , x ( m ) {x^{(1)},\dots,x^{(m)}} x(1),,x(m),其中 x ( i ) x^{(i)} x(i)对应的目标为 y ( i ) y^{(i)} y(i)

    ​ 计算梯度估计: g ← + 1 m ▽ θ ∑ i L ( f ( x ( i ) ; θ ) , y ( i ) ) g \leftarrow +\frac{1}{m}\triangledown_\theta\sum_i{L(f(x^{(i)};\theta), y^{(i)})} g+m1θiL(f(x(i);θ),y(i))

    ​ 计算速度更新: v ← α v − ϵ g v \leftarrow \alpha v - \epsilon g vαvϵg

    ​ 应用更新: θ ← θ + v \theta \leftarrow \theta + v θθ+v

    end while


    直观上理解,如果梯度的方向始终一致,那么SGD就会在这个方向上不停加速,将原步长每次放大为上一轮的 1 − α 1-\alpha 1α倍。否则,会产生一个相反的惩罚:

    momentum_fig.jpg

    这样的好处就在于我们能够在一定情况下冲破局部最优点的陷阱,同时,面对较高的壁垒时比定步长SGD有更好的收敛性质。

    在实践中, α \alpha α的取值一般为 0.5 , 0.9 , 0.99 0.5,0.9,0.99 0.5,0.9,0.99。利用python实现:

    epsilon = 1e-1  # 停止准则
    lambda0 = 0.5  # 给定与sgd相同的学习率
    alpha = 0.5
    v = 1 / (1-alpha)
    x0, x1 = -150, 100
    costs = []
    while abs(x1 - x0) >= epsilon:
        costs.append(func(x0))
        
        temp = x1
        v = alpha * v - lambda0 * grad(x0)
        x1 = x0 + v
        x0 = temp
    print("x* = ", x0)
    plt.plot(range(min(len(costs), 50)), costs[0:50], label="momentum")
    
    plt.legend()
    plt.show()
    

    对比图像其实很难看到momentum在收敛性上相比于定步长SGD并没有什么太大的优点,甚至给定较大步长时也容易不收敛:

    sgd_vs_momentum.png

    但是,如果我们稍微换一个损失函数/目标函数 f ( x ) = x sin ⁡ ( x 3 ) 10 + x 2 100 f(x)=\frac{x\sin(\frac{x}{3})}{10}+\frac{x^2}{100} f(x)=10xsin(3x)+100x2,效果就会非常明显:(接下来的实验都将继续采用这个函数)

    def func(x):
        return 0.1 * x * np.sin(0.3 * x) + 0.01 * x ** 2
    def grad(x):
        return 0.01 * np.cos(0.3 * x) * x + 0.2 * np.sin(0.3 * x) + 0.02 * x
    

    该新目标函数的图像如下,可以看到其有多个局部最优点:

    new_loss.png

    在区间 [ − 50 , 50 ] [-50,50] [50,50]中测量定步长SGD和momentum方案的性能,给定 α = 0.9   , v = 0.1 \alpha=0.9\ ,v=0.1 α=0.9 ,v=0.1、二者一致的学习率 ϵ = 0.1 \epsilon=0.1 ϵ=0.1

    sgd_vs_momentum2.png

    可以看到——在未经过细致调参的情况下,momentum方案冲破了第一个局部最优值 − 55.36 -55.36 55.36继续下降;但是相对的,定步长SGD就没那么好运了(同样的,学习率线性衰减的SGD也会困于局部最优解)。所以,当我们提到SGD方案时,实际上往往用的是momentum及其改进方案,例如Keras框架就是这么做的。

    Nesterov动量下降

    为了改进momentum方案的额外误差收敛率,一个比较著名的变种是Nesterov动量下降:

    算法:使用了Nesterov动量下降方案的SGD(花书P184)


    Require: 学习率 ϵ \epsilon ϵ、动量参数 α \alpha α

    Require: 初始参数 θ \theta θ、初始速度 v v v

    while 没有达到停止准则 do

    ​ 从训练集中采样 m m m个样本 x ( 1 ) , … , x ( m ) {x^{(1)},\dots,x^{(m)}} x(1),,x(m),其中 x ( i ) x^{(i)} x(i)对应的目标为 y ( i ) y^{(i)} y(i)

    ​ 应用临时更新: θ ^ ← θ + α v \hat\theta \leftarrow\theta + \alpha v θ^θ+αv

    ​ 计算梯度估计: g ← + 1 m ▽ θ ^ ∑ i L ( f ( x ( i ) ; θ ^ ) , y ( i ) ) g \leftarrow +\frac{1}{m}\triangledown_{\hat\theta}\sum_i{L(f(x^{(i)};\hat\theta), y^{(i)})} g+m1θ^iL(f(x(i);θ^),y(i))

    ​ 计算速度更新: v ← α v − ϵ g v \leftarrow \alpha v - \epsilon g vαvϵg

    ​ 应用更新: θ ← θ + v \theta \leftarrow \theta + v θθ+v

    end while


    它将额外误差收敛率从 O ( 1 k ) O(\frac{1}{k}) O(k1)改进到了 O ( 1 k 2 ) O(\frac{1}{k^2}) O(k21);但是在SGD的情况下,它并没有改进收敛率。

    直观上理解,Nesterov方案比momentum方案多跨了一步,即 θ ^ ← θ + α v \hat\theta \leftarrow\theta + \alpha v θ^θ+αv,考虑得更多的是物理上的微分概念;在SGD的应用上,个人感觉并没有太大的性能改进表现,只在全批量下降时有着比较优秀的收敛性能。

    AdaGrad

    我们注意到,动量下降虽然在一定程度上优化了线性衰减的学习率和定步长SGD方案的弱点,但同时又引入了另一个超参数 α \alpha α;而在实践中,超参数是一个非常难以确定的值。

    所以我们希望学习率能在训练过程中进行自适应,即自我进行调整,以提升收敛率和降低收敛额外误差同时又不至于引入更多的超参数,减小调参的工作量。之前曾提过“成功失败法”,即Delta-bar-delta算法的变种,但缺点在于这类算法只有面对全批量下降时才比较有效。

    而此处要介绍的AdaGrad算法,能够独立地适应所有模型参数的学习率,缩放每个参数反比于其所有梯度历史平方值总和的平方根。这么说可能过于拗口,我们直接看算法:

    算法:AdaGrad算法(花书P188)


    Require: 全局学习率 ϵ \epsilon ϵ

    Require: 初始参数 θ \theta θ

    Require: 小常数 δ = 1 0 − 6 \delta=10^{-6} δ=106(防止进行除法时的值溢出)

    初始化累积变量 r = 0 r=0 r=0

    while 没有达到停止准则 do

    ​ 从训练集中采样 m m m个样本 x ( 1 ) , … , x ( m ) {x^{(1)},\dots,x^{(m)}} x(1),,x(m),其中 x ( i ) x^{(i)} x(i)对应的目标为 y ( i ) y^{(i)} y(i)

    ​ 计算梯度估计: g ← 1 m ▽ θ ∑ i L ( f ( x ( i ) ; θ ) , y ( i ) ) g \leftarrow \frac{1}{m}\triangledown_{\theta}\sum_i{L(f(x^{(i)};\theta), y^{(i)})} gm1θiL(f(x(i);θ),y(i))

    ​ 累积平方梯度: r ← r + g ⨀ g r \leftarrow r + g \bigodot g rr+gg

    ​ 计算参数更新: △ θ = − ϵ δ + r ⨀ g \triangle\theta = - \frac{\epsilon}{\sqrt{\delta+r}}\bigodot g θ=δ+r ϵg

    ​ 应用更新: θ ← θ + △ θ \theta \leftarrow \theta + \triangle\theta θθ+θ

    end while


    花书中对AdaGrad的分析较少,但作为自适应学习率算法的入门算法,我觉得有必要进行一些分析:

    • 和常见的优化算法相比,AdaGrad的策略也是采取先快后慢的策略:随着算法不断迭代, r r r会越来越大,整体的学习率越来越小。
    • 在凸优化问题中,由于函数总能收敛到一个最小值且AdaGrad对梯度悬崖有着很强的抑制能力,因此表现得相当不错,较少出现不收敛的情况。
    • 较为直观地说,AdaGrad应用于凸优化问题时,能够给定一个巨大的学习率参数的同时保证收敛,利于加快解决优化问题时的搜寻速度。但其面对梯度壁垒时应对能力较弱,有可能被困于某个具备最优解。
    epsilon = 1e-1  # 停止准则
    lambda0 = 100  # 学习率,AdaGrad往往需要一个极大的初始学习率
    r = 0
    x0, x1 = -50, -40
    costs = []
    while abs(x1 - x0) >= epsilon:
        costs.append(func(x0))
        g = grad(x0)
    
        temp = x1
        r =  r + g ** 2
        x1 = x0 - lambda0 / np.sqrt(1e-6 + r) * g
        x0 = temp
    print("x* = ", x0)
    plt.plot(range(min(len(costs), 50)), costs[0:50] label="adagrad")
    

    得益于AdaGrad对梯度爆炸有着很好的抑制作用,所以实际上你可以给定一个很大的初始学习率,它在自我迭代的过程中也总能保证收敛。

    adagrad.png

    值得一说的是,AdaGrad在深度学习模型上表现得不错,比如采用64x64x1的全连接神经网络在波士顿房价回归问题上的表现如下:

    sgd_adagrad_boston.png

    RMSProp

    在上面的图像中,AdaGrad在非凸情况下表现得并不好,收敛时震荡还是比较剧烈的。同时,如果你把上文中AdaGrad的初始学习率调小,你会发现AdaGrad会跟SGD一样困于某个局部最优值。造成AdaGrad面对梯度壁垒无能为力的可能性有很多,但最大的可能是搜索在到达一个局部洼地时学习率就收缩得太小了,因此导致搜寻的脚步深陷泥沼。

    因此RMSProp改变梯度累积值 r r r为指数加权的移动平均值——抛弃过于遥远的历史,使其能够保证一定的跃出洼地泥沼的能力;但相对的,也会削弱其收敛率,在样本量较小时甚至完全不收敛。简单来说,就是把 r ← r + g ⨀ g r \leftarrow r + g \bigodot g rr+gg 改为 r ← ρ r + ( 1 − ρ ) g ⨀ g r \leftarrow \rho r + (1-\rho)g \bigodot g rρr+(1ρ)gg,其中 ρ \rho ρ为衰减速率。

    直观上理解,RSMProp的设计思路是这样的:梯度波动比较大的函数,它们的方差一定是非常大的,因此直接用梯度除以其二阶矩的开方,从而抑制了搜索时的摆动幅度。

    算法:RMSProp算法(花书P188)


    Require: 全局学习率 ϵ \epsilon ϵ、衰减速率 ρ \rho ρ

    Require: 初始参数 θ \theta θ

    Require: 小常数 δ = 1 0 − 6 \delta=10^{-6} δ=106(防止进行除法时的值溢出)

    初始化累积变量 r = 0 r=0 r=0

    while 没有达到停止准则 do

    ​ 从训练集中采样 m m m个样本 x ( 1 ) , … , x ( m ) {x^{(1)},\dots,x^{(m)}} x(1),,x(m),其中 x ( i ) x^{(i)} x(i)对应的目标为 y ( i ) y^{(i)} y(i)

    ​ 计算梯度估计: g ← 1 m ▽ θ ∑ i L ( f ( x ( i ) ; θ ) , y ( i ) ) g \leftarrow \frac{1}{m}\triangledown_{\theta}\sum_i{L(f(x^{(i)};\theta), y^{(i)})} gm1θiL(f(x(i);θ),y(i))

    ​ 累积平方梯度: r ← ρ r + ( 1 − ρ ) g ⨀ g r \leftarrow \rho r + (1-\rho)g \bigodot g rρr+(1ρ)gg

    ​ 计算参数更新: △ θ = − ϵ δ + r ⨀ g \triangle\theta = - \frac{\epsilon}{\sqrt{\delta+r}}\bigodot g θ=δ+r ϵg

    ​ 应用更新: θ ← θ + △ θ \theta \leftarrow \theta + \triangle\theta θθ+θ

    end while


    epsilon = 1e-1  # 停止准则
    lambda0 = 10  # 学习率,给定一个相比于AdaGrad的学习率,其也能快速收敛和突破梯度壁垒
    r, rho = 0, 0.5
    x0, x1 = -50, -40
    
    costs = []
    while len(costs) < 1000 and abs(x1 - x0) >= epsilon:
        costs.append(func(x0))
        g = grad(x0)
    
        temp = x1
        r = rho * r + (1-rho)*g ** 2
        x1 = x0 - lambda0 / np.sqrt(1e-6 + r) * g
        x0 = temp
    
    print("x* = ", x0)
    
    plt.plot(range(min(len(costs), 100)), costs[0:100], label="RMSProp")
    
    plt.legend()
    plt.show()
    

    运行结果如下:

    rmsprop.png

    有时候,还会为其加上Nesterov动量,使得其在某些问题上具有更好的性质:

    算法:使用Nesterov动量的RMSProp算法(花书P189)


    Require: 全局学习率 ϵ \epsilon ϵ、衰减速率 ρ \rho ρ、动量系数 α \alpha α

    Require: 初始参数 θ \theta θ、初始速度 v v v

    Require: 小常数 δ = 1 0 − 6 \delta=10^{-6} δ=106(防止进行除法时的值溢出)

    初始化累积变量 r = 0 r=0 r=0

    while 没有达到停止准则 do

    ​ 从训练集中采样 m m m个样本 x ( 1 ) , … , x ( m ) {x^{(1)},\dots,x^{(m)}} x(1),,x(m),其中 x ( i ) x^{(i)} x(i)对应的目标为 y ( i ) y^{(i)} y(i)

    ​ 计算临时更新: θ ^ ← θ + α v \hat \theta \leftarrow \theta + \alpha v θ^θ+αv

    ​ 计算梯度估计: g ← 1 m ▽ θ ^ ∑ i L ( f ( x ( i ) ; θ ^ ) , y ( i ) ) g \leftarrow \frac{1}{m}\triangledown_{\hat\theta}\sum_i{L(f(x^{(i)};\hat \theta), y^{(i)})} gm1θ^iL(f(x(i);θ^),y(i))

    ​ 累积平方梯度: r ← ρ r + ( 1 − ρ ) g ⨀ g r \leftarrow \rho r + (1-\rho)g \bigodot g rρr+(1ρ)gg

    ​ 计算参数更新: v = α v − ϵ δ + r ⨀ g v = \alpha v- \frac{\epsilon}{\sqrt{\delta+r}}\bigodot g v=αvδ+r ϵg

    ​ 应用更新: θ ← θ + v \theta \leftarrow \theta + v θθ+v

    end while


    我平常在应用时,并没有觉得二者有什么特别大的差别,因此老老实实用RMSProp就行了,还能少计算一些参数和引入超参数。可能对于一些较为疯狂的调参侠而言加了Nesterov,给了他们更多的微调空间。

    Adam

    Adam的词源来自adaptive moments,显然这又是一种动量方案和RMSProp的变种算法。从个人经验上来看,Adam往往更加地Robust,算是我用得比较多的一种优化方案。

    算法:Adam算法(花书P189)


    Require: 全局学习率 ϵ = 0.001 \epsilon=0.001 ϵ=0.001

    Require: 矩估计的指数衰减速率 ρ 1 , ρ 2 ∈ [ 0 , 1 ) ] \rho_1,\rho_2\in[0,1)] ρ1,ρ2[0,1)](建议默认0.9和0.9999)

    Require: 初始参数 θ \theta θ

    Require: 小常数 δ = 1 0 − 8 \delta=10^{-8} δ=108(防止进行除法时的值溢出)

    初始化时间序列 t = 0 t=0 t=0、一阶和二阶矩变量 s = 0 , r = 0 s=0,r=0 s=0,r=0

    while 没有达到停止准则 do

    t ← t + 1 t \leftarrow t +1 tt+1

    ​ 从训练集中采样 m m m个样本 x ( 1 ) , … , x ( m ) {x^{(1)},\dots,x^{(m)}} x(1),,x(m),其中 x ( i ) x^{(i)} x(i)对应的目标为 y ( i ) y^{(i)} y(i)

    ​ 计算梯度估计: g ← 1 m ▽ θ ∑ i L ( f ( x ( i ) ; θ ) , y ( i ) ) g \leftarrow \frac{1}{m}\triangledown_{\theta}\sum_i{L(f(x^{(i)};\theta), y^{(i)})} gm1θiL(f(x(i);θ),y(i))

    ​ 更新一阶矩估计: s ← ρ 1 s + ( 1 − ρ 1 ) g s \leftarrow \rho_1s+(1-\rho_1)g sρ1s+(1ρ1)g

    ​ 更新二阶矩估计: r ← ρ 2 r + ( 1 − ρ 2 ) g ⨀ g r \leftarrow \rho_2r + (1-\rho_2)g \bigodot g rρ2r+(1ρ2)gg

    ​ 修正一阶矩偏差: s ^ ← s 1 − ρ 1 t \hat s \leftarrow \frac{s}{1-\rho^t_1} s^1ρ1ts

    ​ 修正二阶矩偏差: r ^ ← r 1 − ρ 2 t \hat r \leftarrow \frac{r}{1-\rho^t_2} r^1ρ2tr

    ​ 计算参数更新: △ θ = − ϵ s ^ r ^ + δ \triangle\theta = -\epsilon \frac{\hat s}{\sqrt{\hat r}+\delta} θ=ϵr^ +δs^

    ​ 应用更新: θ ← θ + △ θ \theta \leftarrow \theta + \triangle\theta θθ+θ

    end while


    观察这个算法,一阶矩和二阶矩可以简单理解成均值和方差,由于二者初始值都是 0 0 0,因此需要在刚开始时进行放大修正防止其向 0 0 0偏置。最后计算参数更新时,实际上用了一阶矩和二阶矩进行了估算。

    矩估计可以看我的另外一篇文章:数理知识:参数估计——点估计、区间估计及置信区间

    在吴恩达的公开课中,他给出他对Adam的理解,他认为Adam是momentum和RMSProp的一种结合:若把一个优化问题看成超空间上的谷地,搜索过程会在某个方向上来回摇摆,我们把这个方向记为纵轴;相反的,直达谷底的方向即为横轴。我们要做的就是抑制纵轴上的移动距离、加大在横轴上的移动距离。Adam和momentum对梯度的均值进行估计,使得纵轴上的摆动幅度减小;而对二阶矩即方差的抑制,可以进一步减小摇摆,相对的就是加大了横向搜索距离。

    常用方案的对比总结

    这里再快速回顾一下以上各种算法的特点。

    算法名引入新的超参数容易困于洼地初始学习率/收敛率Cheat Sheet
    线性衰减学习率 α , τ \alpha,\tau α,τ可以较大 ϵ k = ( 1 − α ) ϵ 0 + α ϵ τ \epsilon_k=(1-\alpha)\epsilon_0+\alpha\epsilon_{\tau} ϵk=(1α)ϵ0+αϵτ
    momentum α , v \alpha,v α,v较小 v ← α v − ϵ g θ ← θ + v v \leftarrow \alpha v - \epsilon g \\ \theta \leftarrow \theta + v vαvϵgθθ+v
    Nesterov α , v \alpha,v α,v较小 g ^ ← g r a d ( θ + α v ) \hat g \leftarrow grad(\theta + \alpha v) g^grad(θ+αv)
    AdaGrad/ r ← r + g ⨀ g θ ← θ − ϵ δ + r ⨀ g r \leftarrow r + g \bigodot g \\ \theta \leftarrow \theta - \frac{\epsilon}{\delta + \sqrt{r}} \bigodot g rr+ggθθδ+r ϵg
    RMSProp ρ \rho ρ较大 r ← ρ r + ( 1 − ρ ) g ⨀ g r \leftarrow \rho r + (1-\rho) g \bigodot g rρr+(1ρ)gg
    Adam ρ 1 , ρ 2 \rho_1,\rho_2 ρ1,ρ2 s ← ρ 1 s + ( 1 − ρ 1 ) g r ← ρ 1 r + ( 1 − ρ 1 ) g ⨀ g x ^ ← x 1 − ρ x t θ ← θ − ϵ s ^ δ + r ^ s \leftarrow \rho_1 s + (1-\rho_1)g \\ r \leftarrow \rho_1 r + (1-\rho_1)g\bigodot g \\ \hat x \leftarrow \frac{x}{1-\rho^t_x} \\ \theta \leftarrow \theta - \epsilon \frac{\hat s}{\delta + \sqrt{\hat r}} sρ1s+(1ρ1)grρ1r+(1ρ1)ggx^1ρxtxθθϵδ+r^ s^
    展开全文
  • 文章目录各种优化器SGD,AdaGrad,Adam,LBFGS都做了什么?1. SGD:2. SGD+Momentum:3. NAG(Nesterov Accelerated Gradient ):4. AdaGrad(Adaptive Gradient Algorithm):5. AdaDelta:6. RMSProp:7. Adam:8...

    各种优化器SGD,AdaGrad,Adam,LBFGS都做了什么?

    优化的目标是希望找到一组模型参数,使模型在所有训练数据上的平均损失最小。

    1. SGD:

    用单个训练样本的损失来近似平均损失,即每次随机采样一个样本来估计当前梯度,对模型参数进行一次更新。
    θ t + 1 = θ t − η ∇ L ( θ t ; x i , y i ) = g t θ t + 1 = θ t − η g t \theta_{t+1}=\theta_t-\eta\nabla L(\theta_t;x_i,y_i)\\ \overset{\underset{g_t}{}}{=}\\ \theta_{t+1}=\theta_t-\eta g_t θt+1=θtηL(θt;xi,yi)=gtθt+1=θtηgt
    优点:训练速度快,内存开销小。

    缺点:SGD每步接受的信息有限,对梯度的估计准确性低,造成目标函数的收敛不稳定伴有震荡甚至出现不收敛。随机性大,并不保证全局最优化。

    2. SGD+Momentum:

    动量方法考虑了带衰减系数的前一步伐,可以加速SGD,抑制震荡。
    m t = β 1 m t − 1 + η ∇ L ( θ t ) θ t + 1 = θ t − m t m_{t}=\beta_1 m_{t-1}+\eta\nabla L(\theta_t)\\ \theta_{t+1}=\theta_t-m_t mt=β1mt1+ηL(θt)θt+1=θtmt
    优点:比SGD收敛更快,目标函数的收敛更稳定,减少在鞍点等的震荡。

    缺点:保持惯性,缺乏适应性。梯度方向不变的维度上速度变快,梯度方向有所改变的维度上的更新速度变慢 。

    3. NAG(Nesterov Accelerated Gradient ):

    在SGD+Momentum上增加“提前量”设计,在计算梯度时做了调整,用 θ t − β 1 m t − 1 \theta_t-\beta_1 m_{t-1} θtβ1mt1来近似当作参数下一步会变成的值,计算未来可能位置处的梯度而非当前位置的梯度。
    m t = β 1 m t − 1 + η ∇ L ( θ t − β 1 m t − 1 ) θ t + 1 = θ t − m t m_{t}=\beta_1 m_{t-1}+\eta\nabla L(\theta_t-\beta_1 m_{t-1})\\ \theta_{t+1}=\theta_t-m_t mt=β1mt1+ηL(θtβ1mt1)θt+1=θtmt
    优点:改进Momentum方法,防止按照惯性走的太快,会衡量一下梯度做出修正。

    4. AdaGrad(Adaptive Gradient Algorithm):

    自适应地确定参数的学习速度,对更新频率低的参数做较大的更新,对更新频率高的参数做较小的更新。采用“历史梯度平方和”来衡量不同参数的梯度的稀疏性,取值越小表明越稀疏。
    θ t + 1 , i = θ t , i − η ∑ k = 0 t g k , i 2 + ϵ g t , i \theta_{t+1,i}=\theta_{t,i}-\frac{\eta}{\sqrt{\sum_{k=0}^{t}g_{k,i}^2}+\epsilon}g_{t,i} θt+1,i=θt,ik=0tgk,i2 +ϵηgt,i
    优点:减少学习率的手动调整,更适用于稀疏数据,提高SGD的鲁棒性。

    缺点:分母会不断累积,学习率衰减越来越快。

    5. AdaDelta:

    针对AdaGrad改进:因为AdaGrad采用所有历史梯度平方和的平方根做分母,分母随时间单调递增,产生的自适应学习速率随时间衰减的速度过于激进 。AdaDelta 采用指数衰减平均的计算方法,用过去梯度平方的衰减平均值代替他们的求和。 这个分母相当于梯度的均方根 root mean squared (RMS),在数据统计分析中,将所有值平方求和,求其均值,再开平方,就得到均方根值。
    θ t + 1 = θ t − R M S [ Δ θ ] t − 1 R M S [ g ] t g t E [ g 2 ] t = γ E [ g 2 ] t − 1 + ( 1 − γ ) g t 2 E [ Δ θ 2 ] t = γ E [ Δ θ 2 ] t − 1 + ( 1 − γ ) Δ θ t 2 \theta_{t+1}=\theta_t-\frac{RMS[\Delta\theta]_{t-1}}{RMS[g]_t}g_t\quad \\ E[g^2]_t=\gamma E[g^2]_{t-1}+(1-\gamma)g_t^2\\ E[\Delta \theta^2]_t=\gamma E[\Delta \theta^2]_{t-1}+(1-\gamma)\Delta \theta_t^2 θt+1=θtRMS[g]tRMS[Δθ]t1gtE[g2]t=γE[g2]t1+(1γ)gt2E[Δθ2]t=γE[Δθ2]t1+(1γ)Δθt2
    优点:不需要提取设定学习速率,使用指数衰减平均计算,防止学习速率衰减过快。

    6. RMSProp:

    是 Geoff Hinton 提出的一种自适应学习率方法。结合了Momentum的惯性原则,加上AdaGrad对错误方向的阻力。但是缺少了Momentum的一部分,因此后面Adam补上这个想法。

    RMSprop 和 AdaDelta 都是为了解决 AdaGrad 学习率急剧下降问题的。
    v t = β 1 v t − 1 + ( 1 − β 1 ) g t 2 θ t + 1 = θ t − η v t + ϵ g t v_t = \beta_1 v_{t-1}+(1-\beta_1)g_t^2\\ \theta_{t+1}=\theta_t-\frac{\eta}{\sqrt{v_t+\epsilon}}g_t\\ vt=β1vt1+(1β1)gt2θt+1=θtvt+ϵ ηgt
    优点:解决 AdaGrad 学习率急剧下降。

    7. Adam:

    结合Momentum和AdaGrad的优点,即考虑过去梯度的平方的指数衰减平均值,也保持过去梯度的指数衰减平均值。还包含了偏置修正,修正从0初始化的一阶矩和二阶矩的估计。
    m t = β 1 m t − 1 + ( 1 − β 1 ) g t v t = β 2 v t − 1 + ( 1 − β 2 ) g t 2 m t ^ = m t 1 − β 1 t v t ^ = v t 1 − β 2 t θ t + 1 = θ t − η v t ^ + ϵ m t ^ m_t=\beta_1m_{t-1}+(1-\beta_1)g_t\\ v_t=\beta_2v_{t-1}+(1-\beta_2)g_t^2\\ \hat{m_t}=\frac{m_t}{1-\beta_1^t}\quad \hat{v_t}=\frac{v_t}{1-\beta_2^t}\\ \theta_{t+1}=\theta_t-\frac{\eta}{\sqrt{\hat{v_t}+\epsilon}}\hat{m_t} mt=β1mt1+(1β1)gtvt=β2vt1+(1β2)gt2mt^=1β1tmtvt^=1β2tvtθt+1=θtvt^+ϵ ηmt^
    优点:为不同参数产生自适应的学习速率。

    8. AdaMax

    Adamax优化器来自于Adam的论文的Section7,该方法是基于无穷范数的Adam方法的变体,对梯度平方的处理由指数衰减平均改为指数衰减求最大值。在Adam中,单个权重的更新规则是将其梯度与当前和过去梯度的 L 2 L^2 L2范数(标量)成反比例缩放。作者又将基于 L 2 L^2 L2范数的更新规则泛化到基于 L p L^p Lp范数的更新规则中。
    v t = β 2 p v t − 1 + ( 1 − β 2 p ) ∣ g t ∣ p = ( 1 − β 2 p ) ∑ i t β 2 p ( t − i ) ⋅ ∣ g i ∣ p \begin{aligned} v_t&=\beta_2^p v_{t-1}+(1-\beta_2^p)|g_t|^p\\ &=(1-\beta_2^p)\sum_{i}^{t} \beta_2^{p(t-i)}\cdot|g_i|^p \end{aligned} vt=β2pvt1+(1β2p)gtp=(1β2p)itβ2p(ti)gip
    虽然这样的变体会因为 p p p的值较大而在数值上变得不稳定,但是在特例中,令 p → ∞ p\rightarrow\infty p会得出一个极其稳定和简单的算法。
    u t = lim ⁡ p → ∞ ( v t ) 1 / p = max ⁡ ( β 2 ⋅ u t − 1 , ∣ g t ∣ ) \begin{aligned} u_t&=\lim_{p\rightarrow\infty}(v_t)^{1/p}\\ &=\max(\beta_2\cdot u_{t-1},|g_t|) \end{aligned} ut=plim(vt)1/p=max(β2ut1,gt)
    由于 u t u_t ut依赖于max操作,所以AdaMax不像在Adam中 m t m_t mt v t v_t vt的偏差趋向于0,所以不需要计算 u t u_t ut的偏差校正( u 0 = 0 u_0=0 u0=0)。
    m t = β 1 m t − 1 + ( 1 − β 1 ) g t u t = max ⁡ ( β 2 u t − 1 , ∣ g t ∣ ) θ t + 1 = θ t − η u t m t m_t=\beta_1m_{t-1}+(1-\beta_1)g_t\\ u_t=\max(\beta_2u_{t-1},|g_t|)\\ \theta_{t+1}=\theta_t-\frac{\eta }{u_t}m_t mt=β1mt1+(1β1)gtut=max(β2ut1,gt)θt+1=θtutηmt

    在这里插入图片描述

    9. AdamW:

    在Ilya Loshchilov & Frank Hutter 的论文Decoupled weight decay regularization中,把Adam中的权重衰减基于损失的梯度更新解耦(AdamW)。发现在Adam这种自适应学习率算法中L2正则化不像在SGD中有效:

    1. L2正则化和Weight Decay并不等价,只有在标准的SGD下可以把两者等价。特别当与自适应梯度相结合时,L2正则化导致具有较大历史参数或梯度幅度的权重比使用权重衰减时更小。
    2. 使用Adam优化带L2正则的损失并不有效。如果引入L2正则化项,在计算梯度的时候会加上正则项求梯度的结果。正常的权重衰减是对所有的权重都采用相同的系数进行更新,本身比较大的一些权重对应的梯度也会比较大,惩罚也越大。但由于Adam计算步骤中减去项会有除以梯度平方的累积,使得梯度大的减去项偏小,从而具有大梯度的权重不会像解耦权重衰减那样得到正则化。 这导致自适应梯度算法的L2和解耦权重衰减正则化的不等价。

    而在常见的深度学习库中只提供了L2正则,并没有提供权重衰减的实现。这可能就是导致Adam跑出来的很多效果相对SGD with Momentum有偏差的一个原因。大部分的模型都会有L2 regularization约束项,因此很有可能出现Adam的最终效果没有SGD的好。目前bert训练采用的优化方法就是AdamW,对除了layernorm,bias项之外的模型参数做weight decay。

    在这里插入图片描述

    Adam的weight decay发生在紫字部分,所以由于 g 2 g^2 g2作分母,会使得大的梯度得不到足够力度的正则化;而AdamW把weight decay放在了绿字部分,所以能有效的正则化。

    10. SGDW:

    和AdamW类似,是SGD+momentum使用解耦的weight decay(SGDW)。原始的SGD+momentum权重衰减发生在梯度的L2正则化,而SGDW是在更新参数 θ t \theta_t θt时使用解耦权重衰减。

    在这里插入图片描述

    11. AMSGrad

    偏置修正只是对训练的开始有用,先不考虑偏置修正。Adam中 η v t + ϵ \frac{\eta}{\sqrt{{v_t}+\epsilon}} vt+ϵ η朝着平均梯度方向前进的步幅,随着训练会逐渐减少。由于学习率是恒定或递减的,作者提出的解决方法是通过添加另一个变量来跟踪梯度平方的指数衰减平均 v t v_t vt的最大值,从而迫使 v t v_t vt增加。
    m t = β 1 m t − 1 + ( 1 − β 1 ) g t v t = β 2 v t − 1 + ( 1 − β 2 ) g t 2 v t ^ = max ⁡ ( v t , v ^ t − 1 ) θ t + 1 = θ t − η v t ^ + ϵ m t m_t=\beta_1m_{t-1}+(1-\beta_1)g_t\\ v_t=\beta_2v_{t-1}+(1-\beta_2)g_t^2\\ \hat{v_t}=\max (v_t,\hat{v}_{t-1})\\ \theta_{t+1}=\theta_t-\frac{\eta}{\sqrt{\hat{v_t}+\epsilon}}m_t mt=β1mt1+(1β1)gtvt=β2vt1+(1β2)gt2vt^=max(vt,v^t1)θt+1=θtvt^+ϵ ηmt

    12. LBFGS:

    经典的优化问题中迭代法的一阶法(梯度下降法),前面SGD、Adam等都是在一阶法的基础上进行改进,加快收敛速率。二阶法(牛顿法)的收敛速度是远快于一阶法的,但是Hessian矩阵求逆的计算复杂度很大,对于目标函数非凸时,二阶法有可能会收敛到鞍点。针对二阶法的这个问题,提出了BFGS算法,再是低存储的L-BFGS算法。简答说L-BFGS和梯度下降、SGD干的同样的事情。

    牛顿法求根 f ( x ) = 0 f(x)=0 f(x)=0的思路:

    1. 已知 f ( x ) f(x) f(x)下,随机产生点 x 0 x_0 x0.
    2. 由已知的 x 0 x_0 x0按照 x k = x k − 1 − f ( x k − 1 ) f ′ ( x k − 1 ) x_k=x_{k-1}-\frac{f(x_{k-1})}{f'(x_{k-1})} xk=xk1f(xk1)f(xk1)进行 k k k次迭代。
    3. 如果 x k x_k xk与上一次的迭代结果 x k − 1 x_{k-1} xk1相同或相差小于阈值,那么 x k x_k xk就是函数 f ( x ) f(x) f(x)的根。

    对于机器学习中的最优化问题,大部分要优化的是目标函数的导函数,即求导函数为0的点(驻点)。用牛顿法求导函数为0,转换迭代公式为: x k = x k − 1 − f ‘ ( x k − 1 ) f ′ ’ ( x k − 1 ) x_k=x_{k-1}-\frac{f‘(x_{k-1})}{f'’(x_{k-1})} xk=xk1f(xk1)f(xk1)。牛顿法求驻点本质是目标函数 f ( x ) f(x) f(x)的二阶泰勒展开: f ( x ) ≈ f ( x k ) + f ′ ( x k ) ( x − x k ) + 1 2 f ′ ′ ( x k ) ( x − x k ) 2 f(x)\approx f(x_k)+f'(x_k)(x-x_k)+\frac{1}{2}f''(x_k)(x-x_k)^2 f(x)f(xk)+f(xk)(xxk)+21f(xk)(xxk)2。对目标函数求导即对近似式求导即 f ′ ( x k ) + f ′ ′ ( x k ) ( x − x k ) = 0 f'(x_k)+f''(x_k)(x-x_k)=0 f(xk)+f(xk)(xxk)=0,变换后就是上面的迭代公式。

    机器学习中优化的目标函数是多元的, x , f ′ ( x ) x,f'(x) xf(x)都是向量, f ′ ′ ( x ) f''(x) f(x)是Hessian矩阵,迭代公式变为下式, g k g_k gk就是 f ′ ( x k ) f'(x_k) f(xk) H k − 1 H^{-1}_k Hk1是二阶导数的倒数:
    x k + 1 = x k − H k − 1 ⋅ g k ,    k = 0 , 1 , … x_{k+1}=x_k-H^{-1}_k\cdot g_k, \; k=0,1,\dots xk+1=xkHk1gk,k=0,1,
    直接求 H k − 1 H^{-1}_k Hk1很困难,因此提出BFGS算法:通过迭代法来逼近 H k − 1 H^{-1}_k Hk1的算法。
    D k + 1 = ( I − s k y k T y k T s k ) D k ( I − y k s k T y k T s k ) + s k s k T y k T s k D_{k+1}=(I-\frac{s_k y_k^T}{y_k^T s_k})D_k(I-\frac{y_k s_k^T}{y_k^T s_k})+\frac{s_k s_k^T}{y_k^T s_k} Dk+1=(IykTskskykT)Dk(IykTskykskT)+ykTskskskT
    其中 D k = H k − 1 , s k = x k + 1 − x k , y k = g k + 1 − g k D_k=H_k^{-1},s_k=x_{k+1}-x_k,y_k=g_{k+1}-g_k Dk=Hk1,sk=xk+1xk,yk=gk+1gk

    D k D_k Dk的迭代公式也很复杂,利用单位矩阵( D 0 = I D_0=I D0=I)逐步逼近 H H H矩阵,每次计算要存储 D D D矩阵。如果数据集维度很大,迭代所需要的存储巨大。

    因为无法保存巨大的 D D D矩阵,提出了L-BFGS算法

    时间换空间的方法:每次计算 D D D矩阵要迭代计算 s k s_k sk y k y_k yk,那存储所有的 s k s_k sk y k y_k yk就可以。如果要得到 D 10 D_{10} D10,用单位矩阵与存储的 s 1 , … , s 10 , y 1 , … , y 10 s_1,\dots,s_{10},y_1,\dots,y_{10} s1,,s10,y1,,y10计算即可。如果数据集是10000维,存储大小为 10000 × 10000 10000\times 10000 10000×10000 D k D_k Dk,变成存储10个大小为 1 × 10000 1\times 10000 1×10000的向量 s k s_k sk y k y_k yk,有效节省了内容空间。

    如果迭代次数很大,内存同样会不足。设定最大的存储向量数 N N N,如果 s k s_k sk y k y_k yk迭代超过 N N N,就丢弃第一组 s 1 , y 1 s_1,y_1 s1,y1,存储 s 2 , … , s N + 1 , y 2 , … , y N + 1 s_2,\dots, s_{N+1}, y_2,\dots, y_{N+1} s2,sN+1,y2,,yN+1,每次丢弃最前边的 s k s_k sk y k y_k yk。虽然损失了精度,但可以保证使用有限的内存将函数的解通过BFGS算法求得到。

    L-BFGS算法,可以看做是对BFGS算法的又一次近似。

    优点:收敛速度快、内存开销少。

    Reference

    当前训练神经网络最快的方式:AdamW优化算法+超级收敛

    Adamax优化器

    adam和adamW

    一文读懂L-BFGS算法

    深入机器学习系列17-BFGS & L-BFGS

    展开全文
  • SGD(随机梯度下降) 随机梯度下降的优化算法在科研和工业届是很常用的。 很多理论和工程问题都能转化成对目标函数进行最小化的数学问题。...学习率调整策略受限于预先指定的调整规则。 相同的学习率被应用于各个参
  • 想象一下纸团在山谷和鞍点处的运动轨迹,在山谷中纸团受重力作用沿山道滚下,两边是不规则的山壁,纸团不可避免地撞在山壁,由于质量小受山壁弹力的干扰大,从一侧山壁反弹回来撞向另一侧山壁 ,结果来回震荡地滚下 ...
  • 在每个步骤中,除了规则的渐变以外,它还增加了上一步的运动。在数学上,它通常表示为: 如果我稍微改动一下这个等式,并记录“梯度的(衰减的)累积和”,会更直观。当我们稍后介绍Adam算法时,这也会使事情变得更...
  • CADA大师 AISTATS2021论文的Python代码:陈天一,郭子业,孙跃娇,尹沃涛,“ CADA:通信自适应分布式亚当”。 [在线] 参考: 如果我们的代码可以帮助您进行研究,请引用我们的论文。 @misc{chen2020cada, ...
  • 前言 这里讨论的优化问题指的是,给定...梯度更新规则: BGD 采用整个训练集的数据来计算 cost function 对参数的梯度: 缺点: 由于这种方法是在一次更新中,就对整个数据集计算梯度,所以计算起来非常慢,遇到很大...
  • 图解深度学习-梯度下降法可视化(SGD, Momentum, Adagrad and RMSProp)前言定义了4个基本函数机器学习原理原始的梯度下降算法带动量的梯度下降算法带惯性的梯度下降算法Adagrad 自适应调整的梯度下降RMSPropAdam ...
  • 在网上看到有关各种分类器的讲解:优化器算法Optimizer详解(BGD、SGD、MBGD、Momentum、NAG、Adagrad、Adadelta、RMSprop、Adam) 英文原文传送门 中文翻译版传送门 机器学习算法的目标 机器学习和深度学习的目标...
  • 参考的两篇博文 (1) 优化算法总结-深度学习... (2)深度学习——优化器算法Optimizer详解(BGD、SGD、MBGD、Momentum、NAG、Adagrad、Adadelta、RMSprop、Adam)https://www.cnblogs....
  • 在机器学习、深度学习中使用的优化算法除了常见的梯度下降,还有 Adadelta,Adagrad,RMSProp 等几种优化器,都是什么呢,又该怎么选择呢? 在 Sebastian Ruder 的这篇论文中给出了常用优化器的比较,今天来学习...
  • 首先回顾随机梯度下降方法,并指出它具有学习率固定,只能利用一阶导数信息的缺点,针对学习率固定的缺点,首先采用Adagrad首先学习率的自我调节,但是这种方法后期学习速度过慢,进而进入RMSProp和Adadelta两种方法...
  • 在机器学习、深度学习中使用的优化算法除了常见的梯度下降,还有 Adadelta,Adagrad,RMSProp 等几种优化器,都是什么呢,又该怎么选择呢? 在 Sebastian Ruder 的这篇论文中给出了常用优化器的比较,今天来学习...
  • 为简便起见,我们将g_(t,i)设为目标函数在时间步长t参数θ_i的梯度: SGD更新每一个参数θ_i在每个时间步t就变成了: 在它的更新规则,Adagrad修改一般学习率η在每个时间步t为每个参数θ_i基于过去为θ_i的梯度计算...
  •  Momentum参照小球在碗中滚动的物理规则进行移动,AdaGrad为参数的每个元素适当的调整更新步伐。Adam就是将这两个方法融合在一起。这只是一个直观的说明,并不完全正确,详细内容可以参考作者的论文。Diederik ...
  • 在机器学习、深度学习中使用的优化算法除了常见的梯度下降,还有 Adadelta,Adagrad,RMSProp 等几种优化器,都是什么呢,又该怎么选择呢? 在 Sebastian Ruder 的这篇论文中给出了常用优化器的比较,今天来学习一下...
  • 在机器学习、深度学习中使用的优化算法除了常见的梯度下降,还有 Adadelta,Adagrad,RMSProp 等几种优化器,都是什么呢,又该怎么选择呢? 在 Sebastian Ruder 的这篇论文中给出了常用优化器的比较,今天来学习一下...
  • 在机器学习、深度学习中使用的优化算法除了常见的梯度下降,还有 Adadelta,Adagrad,RMSProp 等几种优化器,都是什么呢,又该怎么选择呢? 在 Sebastian Ruder 的这篇论文中给出了常用优化器的比较,今天来学习...
  • 学习率调整策略受限于预先指定的调整规则。 3. 相同的学习率被应用于各个参数。 4. 高度非凸的误差函数的优化过程,如何避免陷入大量的局部次优解或鞍点。 SGDM 也就是SGD+ Momentum。这里引入了一阶动量。 从直观...
  • 每个算法的梯度更新规则和缺点 为了应对这个不足而提出的下一个算法 超参数的一般设定值 几种算法的效果比较 选择哪种算法 0.梯度下降法深入理解 以下为个人总结,如有错误之处,各位前辈请指出。 对于优化...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,928
精华内容 771
关键字:

adagrad规则