哪些平台制作网站,怎样凡科建设网站,it运维,电子商务网站建设可用性机器学习笔记之优化算法——Nesterov动量方法的简单认识 引言回顾#xff1a;梯度下降法与动量法Nesterov动量法Nesterov动量法的算法过程描述总结 引言
上一节对动量法进行了简单认识#xff0c;本节将介绍 Nesterov \text{Nesterov} Nesterov动量方法。
回顾#xff1a;… 机器学习笔记之优化算法——Nesterov动量方法的简单认识 引言回顾梯度下降法与动量法Nesterov动量法Nesterov动量法的算法过程描述总结 引言
上一节对动量法进行了简单认识本节将介绍 Nesterov \text{Nesterov} Nesterov动量方法。
回顾梯度下降法与动量法
关于梯度下降法的迭代步骤描述如下 θ ⇐ θ − η ⋅ ∇ θ J ( θ ) \theta \Leftarrow \theta - \eta \cdot \nabla_{\theta} \mathcal J(\theta) θ⇐θ−η⋅∇θJ(θ) 以标准二次型 f ( x ) x T Q x , Q ( 0.5 0 0 20 ) , x ( x 1 , x 2 ) T f(x) x^T \mathcal Qx,\mathcal Q \begin{pmatrix} 0.5 \quad 0 \\ 0 \quad 20 \end{pmatrix},x (x_1,x_2)^T f(x)xTQx,Q(0.50020),x(x1,x2)T为目标函数使用梯度下降法求解目标函数 f ( x ) f(x) f(x)最小值的迭代过程如下 很明显由于 Q \mathcal Q Q的原因导致在算法迭代过程中迭代更新点对应的 Hessian Matrix ⇒ ∇ 2 f ( ⋅ ) \text{Hessian Matrix} \Rightarrow \nabla^2 f(\cdot) Hessian Matrix⇒∇2f(⋅)中的条件数都较大从而使梯度下降法在该凸二次函数中的收敛速度沿着次线性收敛的方向退化这也是图像中迭代路径震荡、折叠严重的主要原因。
这里仅观察少量几次迭代步骤见下面局部图
其中红色线表示梯度下降法在迭代过程中的更新方向以第一次迭代的更新方向为例将该方向进行分解可以得到上述两个方向分量。 由于目标函数 f ( x ) f(x) f(x)中 x x x是一个二维向量因而在上图中的蓝色箭头分别描述了该方向在 x 1 , x 2 x_1,x_2 x1,x2正交基上的分量。
从上述两个分量可以看出
关于横轴分量它一直指向前方也就是最优解的方向而造成迭代过程震荡、折叠的是纵轴分量。
综上从观察的角度描述迭代路径震荡折叠现象严重的原因在于横轴上的分量向前跨越的步幅很小相比之下纵轴上的分量上下的波动很大。针对该现象可以得到相应的优化思路 具体效果见下图绿色实心箭头,其中第一步红色与绿色实线箭头重合,因为在初始化过程中通常将动量向量初始化为零向量导致,这里以第二次迭代为例进行描述。图中的红色虚线表示梯度下降法当前迭代步骤在横轴、纵轴上的分量;绿色虚线则表示优化思路在当前步骤在横轴、纵轴上的分量。
压缩纵轴分量上的波动幅度拉伸/延长横轴分量上的步幅从而使其更快地达到极值点 如何从数学角度达到这样的效果利用过去迭代步骤中的梯度数据对当前迭代步骤的梯度信息进行修正。继续观察第二次迭代步骤 在第一次迭代步骤结束后我们得到了一个历史梯度的分量信息即图中的蓝色虚线在执行第二次迭代步骤时我们需要将该步骤的梯度分量与相应的历史梯度分量执行加权运算
观察纵轴分量由于历史纵轴分量与当前纵轴分量方向相反(红色、蓝色虚线垂直箭头)这势必会缩减当前迭代步骤的纵轴分量相反观察横轴分量历史横轴分量与当前横轴分量方向相同(红色、蓝色虚线横向箭头)这必然会扩张当前迭代步骤的横轴分量
如何对历史梯度信息进行描述我们需要引入一个新的变量 m m m用于累积历史梯度信息 { m t m t − 1 ∇ θ ; t − 1 J ( θ t − 1 ) θ t θ t − 1 − η ⋅ m t \begin{cases} m_{t} m_{t-1} \nabla_{\theta;t-1} \mathcal J(\theta_{t-1}) \\ \theta_t \theta_{t-1} - \eta \cdot m_t \end{cases} {mtmt−1∇θ;t−1J(θt−1)θtθt−1−η⋅mt
上式的 m t m_t mt确实达到了历史迭代步骤梯度累积的作用但同样衍生出了新的问题上面步骤仅是将历史梯度信息完整地存储进来如果迭代步骤较多的情况下由于历史信息在累积过程中没有任何的丢失最终可能导致迭代步骤较深时初始迭代步骤的历史梯度信息对当前时刻梯度的更新没有参考价值。相反有可能会给当前迭代步骤引向错误的方向。因而关于 m t m_t mt的调整方式表示如下 { m t β ⋅ m t − 1 ( 1 − β ) ⋅ ∇ θ ; t − 1 J ( θ t − 1 ) θ t θ t − 1 − η ⋅ m t \begin{cases} m_t \beta \cdot m_{t-1} (1 - \beta) \cdot \nabla_{\theta;t-1} \mathcal J(\theta_{t-1}) \\ \theta_t \theta_{t-1} - \eta \cdot m_t \end{cases} {mtβ⋅mt−1(1−β)⋅∇θ;t−1J(θt−1)θtθt−1−η⋅mt 关于上式的迭代加权运算被称作指数加权移动平均法。假设 β 0.9 \beta 0.9 β0.9关于 m t m_t mt的表示如下 m t 0.9 × m t − 1 0.1 × ∇ θ ; t − 1 J ( θ t − 1 ) 0.9 × [ 0.9 × m t − 2 0.1 × ∇ θ ; t − 2 J ( θ t − 2 ) ] 0.1 × ∇ θ ; t − 1 J ( θ t − 1 ) ⋯ 0.1 × 0. 9 0 × ∇ θ ; t − 1 J ( θ t − 1 ) 0.1 × 0. 9 1 × ∇ θ ; t − 2 J ( θ t − 2 ) 0.1 × 0. 9 2 × ∇ θ ; t − 3 J ( θ t − 3 ) ⋯ 0.1 × 0. 9 t − 1 × ∇ θ ; 1 J ( θ 1 ) \begin{aligned} m_t 0.9 \times m_{t-1} 0.1 \times \nabla_{\theta;t-1} \mathcal J(\theta_{t-1}) \\ 0.9 \times \left[0.9 \times m_{t-2} 0.1 \times \nabla_{\theta;t-2} \mathcal J(\theta_{t-2}) \right] 0.1 \times \nabla_{\theta;t-1} \mathcal J(\theta_{t-1}) \\ \cdots \\ 0.1 \times 0.9^0 \times \nabla_{\theta;t-1} \mathcal J(\theta_{t-1}) 0.1 \times 0.9^1 \times \nabla_{\theta;t-2} \mathcal J(\theta_{t-2}) 0.1 \times 0.9^2 \times \nabla_{\theta;t-3} \mathcal J(\theta_{t-3}) \cdots 0.1 \times 0.9^{t-1} \times \nabla_{\theta;1} \mathcal J(\theta_1) \end{aligned} mt0.9×mt−10.1×∇θ;t−1J(θt−1)0.9×[0.9×mt−20.1×∇θ;t−2J(θt−2)]0.1×∇θ;t−1J(θt−1)⋯0.1×0.90×∇θ;t−1J(θt−1)0.1×0.91×∇θ;t−2J(θt−2)0.1×0.92×∇θ;t−3J(θt−3)⋯0.1×0.9t−1×∇θ;1J(θ1) 很明显距离当前迭代步骤越近的梯度其保留权重越大反之随着迭代步骤的推移越靠近初始迭代步骤的梯度权重越小。 这让我想起了 GRU \text{GRU} GRU神经网络~
这种方法就是动量法也被称作冲量法。
Nesterov动量法
关于梯度下降法的优化不仅可以像动量法一样考虑历史迭代步骤的梯度信息实际上我们同样可以超前参考未来的梯度信息。
关于动量法在某迭代步骤中的更新过程示例如下
其中黄色结点表示动量法在迭代过程中的更新位置淡蓝色曲线表示理想状态下的下降路径其中红色实线表示梯度下降法的更新方向蓝色实线表示历史梯度构成的冲量信息 很明显当前迭代步骤的梯度方向与更新点处更高线的切线相垂直~
假设 β 0.5 \beta 0.5 β0.5图中的橘黄色虚线表示加权后真正的更新方向。我们不否认此时动量法相比纯粹的梯度下降法其下降路径更接近理想状态路径。两者比对效果如下 很明显梯度下降法不仅多使用一次迭代步骤并且最后结果依然不及两步的动量法。 但即便动量法有更优的下降路径但依然距离理想状态下的下降路径存在差距。
假设在动量法执行完第一次迭代步骤前就已经预估到了未来步骤的位置信息那么通过未来步骤加权的第一次迭代的位置信息会进一步得到修正。从数学角度观察 Nesterov \text{Nesterov} Nesterov动量法是如何实现超前参考的。回顾动量法公式 { m t β ⋅ m t − 1 ( 1 − β ) ⋅ ∇ θ ; t − 1 J ( θ t − 1 ) θ t θ t − 1 − η ⋅ m t \begin{cases} m_t \beta \cdot m_{t-1} (1 - \beta) \cdot \nabla_{\theta;t-1} \mathcal J(\theta_{t-1}) \\ \theta_t \theta_{t-1} - \eta \cdot m_t \end{cases} {mtβ⋅mt−1(1−β)⋅∇θ;t−1J(θt−1)θtθt−1−η⋅mt 其中 ∇ θ ; t − 1 J ( θ t − 1 ) \nabla_{\theta;t-1} \mathcal J(\theta_{t-1}) ∇θ;t−1J(θt−1)表示当前迭代步骤 t t t的梯度信息而 Nesterov \text{Nesterov} Nesterov动量法是将上一迭代步骤的 θ t − 1 ⇐ θ t − 1 γ ⋅ m t − 1 \theta_{t-1} \Leftarrow \theta_{t- 1} \gamma \cdot m_{t-1} θt−1⇐θt−1γ⋅mt−1从而得到一个新时刻的未知的权重信息并使用该信息替换 θ t − 1 \theta_{t-1} θt−1参与运算 之所以是新时刻或者说是未来时刻是因为当前迭代步骤的 θ t \theta_t θt还没有被解出来而 θ t − 1 γ ⋅ m t − 1 \theta_{t-1} \gamma \cdot m_{t-1} θt−1γ⋅mt−1又确实是超越了 t − 1 t-1 t−1迭代步骤的新信息。 { m t β ⋅ m t − 1 ( 1 − β ) ⋅ ∇ θ ; t − 1 J ( θ t − 1 γ ⋅ m t − 1 ) θ t θ t − 1 − η ⋅ m t \begin{cases} m_t \beta \cdot m_{t-1} (1 - \beta) \cdot \nabla_{\theta;t-1} \mathcal J(\theta_{t-1} \gamma \cdot m_{t-1}) \\ \theta_t \theta_{t-1} - \eta \cdot m_t \end{cases} {mtβ⋅mt−1(1−β)⋅∇θ;t−1J(θt−1γ⋅mt−1)θtθt−1−η⋅mt
继续观察上式关于超前信息 θ t − 1 γ ⋅ m t − 1 \theta_{t-1} \gamma \cdot m_{t-1} θt−1γ⋅mt−1它的格式与 θ t θ t − 1 − η ⋅ m t \theta_t \theta_{t-1} - \eta \cdot m_{t} θtθt−1−η⋅mt非常相似相当于该超前信息是 θ t − 1 \theta_{t-1} θt−1与 m t − 1 m_{t-1} mt−1之间的加权方向。 为简化起见这里仅描述一步: t − 1 ⇒ t t-1 \Rightarrow t t−1⇒t
初始状态下下图描述的是动量法的一次迭代步骤红色实线表示 ∇ θ ; t − 1 ∇ J ( θ t − 1 ) \nabla_{\theta;t-1} \nabla \mathcal J(\theta_{t-1}) ∇θ;t−1∇J(θt−1)蓝色实线表示 m t − 1 m_{t-1} mt−1中间的橙黄色虚线表示两者的加权结果 m t β ⋅ m t − 1 ( 1 − β ) ⋅ ∇ θ ; t − 1 J ( θ t − 1 ) m_t \beta \cdot m_{t-1} (1 - \beta) \cdot \nabla_{\theta;t-1} \mathcal J(\theta_{t-1}) mtβ⋅mt−1(1−β)⋅∇θ;t−1J(θt−1) 那么超前信息 θ t − 1 γ ⋅ m t − 1 \theta_{t-1} \gamma \cdot m_{t-1} θt−1γ⋅mt−1如何表示 ? ? ?假设图中 θ t − 1 \theta_{t-1} θt−1到红色点的长度为 γ ⋅ m t − 1 \gamma \cdot m_{t-1} γ⋅mt−1那么红色点的位置就是超前信息的位置 至此可以描述 ∇ θ ; t − 1 J ( θ t − 1 γ ⋅ m t − 1 ) \nabla_{\theta;t-1} \mathcal J(\theta_{t-1} \gamma \cdot m_{t-1}) ∇θ;t−1J(θt−1γ⋅mt−1)的方向过红色点与目标函数等高线相垂直的方向。 图中的红色虚线表示 ∇ θ ; t − 1 J ( θ t − 1 γ ⋅ m t − 1 ) \nabla_{\theta;t-1} \mathcal J(\theta_{t-1} \gamma \cdot m_{t-1}) ∇θ;t−1J(θt−1γ⋅mt−1)的方向仔细观察可以发现它与 ∇ θ ; t − 1 J ( θ t − 1 ) \nabla_{\theta;t-1} \mathcal J(\theta_{t-1}) ∇θ;t−1J(θt−1)描述的红色实线之间存在一丢丢的偏移不是平行的~ 接下来将红色虚线替代红色实线并得到 Nesterov \text{Nesterov} Nesterov动量法中的 m t β ⋅ m t − 1 ( 1 − β ) ⋅ ∇ θ ; t − 1 J ( θ t − 1 γ ⋅ m t − 1 ) m_{t} \beta \cdot m_{t-1} (1 - \beta) \cdot \nabla_{\theta;t-1} \mathcal J(\theta_{t-1} \gamma \cdot m_{t-1}) mtβ⋅mt−1(1−β)⋅∇θ;t−1J(θt−1γ⋅mt−1) 橙黄色虚线指向的红色点表示 Nesterov \text{Nesterov} Nesterov动量法中的经过 η \eta η修饰的 m t m_t mt结果(这里暂定 η \eta η不变的情况下)我们仍可以看出相比于动量法 Nesterov \text{Nesterov} Nesterov动量法在迭代过程中能够更偏向理想状态下降路径。
Nesterov动量法的算法过程描述
基于 Nesterov \text{Nesterov} Nesterov动量法的随机梯度下降的算法步骤表示如下 初始化操作
学习率 η \eta η动量因子 γ \gamma γ初始化参数 θ \theta θ初始动量 m m m
算法过程 While \text{While} While没有达到停止准则 do \text{do} do从训练集 D \mathcal D D中采集出包含 k k k个样本的小批量 { ( x ( i ) , y ( i ) ) } i 1 k \{(x^{(i)},y^{(i)})\}_{i1}^k {(x(i),y(i))}i1k应用临时的超前参数 θ ^ \hat \theta θ^ θ ^ ⇐ θ γ ⋅ m \hat \theta \Leftarrow \theta \gamma \cdot m θ^⇐θγ⋅m使用超前参数 θ ^ \hat \theta θ^计算该位置的梯度信息 G ⇐ 1 k ∑ i 1 k ∇ θ L [ f ( x ( i ) ; θ ^ ) , y ( i ) ] \mathcal G \Leftarrow \frac{1}{k} \sum_{i1}^k \nabla_{\theta} \mathcal L[f(x^{(i)};\hat \theta),y^{(i)}] G⇐k1i1∑k∇θL[f(x(i);θ^),y(i)]计算动量更新 m ⇐ γ ⋅ m − η ⋅ G m \Leftarrow \gamma \cdot m - \eta \cdot \mathcal G m⇐γ⋅m−η⋅G计算参数 θ \theta θ更新 θ ⇐ θ m \theta \Leftarrow \theta m θ⇐θm End While \text{End While} End While
总结
观察上述算法过程可以发现虽然我们更新的是 θ \theta θ但整个算法至始至终都没有求解 θ \theta θ的梯度 ∇ θ J ( θ ) \nabla_{\theta} \mathcal J(\theta) ∇θJ(θ)也就是说 m m m中的历史信息也均是超前梯度 ∇ θ J ( θ γ ⋅ m ) \nabla_{\theta} \mathcal J(\theta \gamma \cdot m) ∇θJ(θγ⋅m)构成的历史信息。 Reference \text{Reference} Reference “随机梯度下降、牛顿法、动量法、Nesterov、AdaGrad、RMSprop、Adam”打包理解对梯度下降的优化 深度学习(花书) P182 8.3.2 \text{P182 8.3.2} P182 8.3.2动量 8.3.3 nesterov \text{8.3.3 nesterov} 8.3.3 nesterov动量
