深度学习笔记之优化算法(三)动量法的简单认识

机器学习笔记之优化算法——动量法的简单认识 引言回顾：条件数与随机梯度下降的相应缺陷动量法简单认识动量法的算法过程描述附：动量法示例代码

引言

上一节介绍了随机梯度下降 ( Stochastic Gradient Descent,SGD ) (\text{Stochastic Gradient Descent,SGD}) (Stochastic Gradient Descent,SGD)，本节将介绍动量法。

回顾：条件数与随机梯度下降的相应缺陷

早在梯度下降法在强凸函数的收敛性分析中介绍了条件数 ( Condition Number ) (\text{Condition Number}) (Condition Number)的概念。如果目标函数 f ( ⋅ ) f(\cdot) f(⋅)在某点处的 Hessian Matrix ⇒ ∇ 2 f ( ⋅ ) \text{Hessian Matrix} \Rightarrow \nabla^2 f(\cdot) Hessian Matrix⇒∇2f(⋅)存在并且它具备： 这意味着 Hessian Matrix \text{Hessian Matrix} Hessian Matrix必然是正定矩阵。 ∇ 2 f ( ⋅ ) ≽ I \nabla^2 f(\cdot) \succcurlyeq \mathcal I ∇2f(⋅)≽I 那么它的条件数 C \mathcal C C可表示为： C = λ m a x λ m i n \mathcal C = \frac{\lambda_{max}}{\lambda_{min}} C=λmin​λmax​​ 其中 λ m a x \lambda_{max} λmax​与 λ m i n \lambda_{min} λmin​分别表示 ∇ 2 f ( ⋅ ) \nabla^2 f(\cdot) ∇2f(⋅)特征值的最大、最小值。如果 C \mathcal C C过大，会导致：使用梯度下降法处理 f ( ⋅ ) f(\cdot) f(⋅)的优化问题，当 C ⇒ ∞ \mathcal C \Rightarrow \infty C⇒∞时，那么算法的收敛速度由线性收敛退化至次线性收敛。这种现象也被称作 Hessain Matrix \text{Hessain Matrix} Hessain Matrix的病态条件。

上面仅仅是理论上的描述。在真实环境下，会出现什么样的效果 ? ? ?以标准二次型 f ( x ) = x T Q x f(x) = x^T \mathcal Q x f(x)=xTQx为例，其中 Q = ( 0.5 0 0 20 ) , x = ( x 1 , x 2 ) T \mathcal Q = \begin{pmatrix}0.5 \quad 0 \\ 0 \quad 20 \end{pmatrix},x=(x_1,x_2)^T Q=(0.50020​),x=(x1​,x2​)T。使用梯度下降法对该目标函数求解最小值的迭代过程见下图：

由于 Q \mathcal Q Q是对角阵，因而它的特征值分别是 0.5 , 20 0.5,20 0.5,20因而在 f ( x ) f(x) f(x)定义域内的点，其对应 Hessian Matrix \text{Hessian Matrix} Hessian Matrix的条件数也是不低的。如果从目标函数的角度观察，它会是一个中间狭窄，两端狭长的船形形状。关于该图代码见文章末尾,下同~

在该示例中，我们并不否认其最终收敛到最优解，但使用迭代步骤的数量是比较夸张的：

其中一个原因是梯度下降法不具备二次终止性——即便已经到达最优解附近，但依然不能基于有限迭代步骤内接近最优解；在整个迭代过程中，梯度下降法在 f ( ⋅ ) f(\cdot) f(⋅)的收敛路径过于冗余(线性收敛退化至次线性收敛的效果)——完全可以通过震荡更小的、路径更直接的方式实现收敛过程。 动量法简单认识

关于上述梯度下降法的迭代公式表示如下： θ ⇐ θ − η ⋅ ∇ θ J ( θ ) \theta \Leftarrow \theta - \eta \cdot \nabla_{\theta} \mathcal J(\theta) θ⇐θ−η⋅∇θ​J(θ) 其中 η \eta η表示学习率。它可以被理解为每一迭代步骤，负梯度方向上调整的步长大小。随着迭代步骤的推移，梯度结果逐渐减小，而学习率是固定值，从而导致收敛速度越来越慢：

如果目标函数 f ( ⋅ ) f(\cdot) f(⋅)至少是严格凸函数，那么 f ( ⋅ ) f(\cdot) f(⋅)存在全局解，这种情况充其量是不具备二次终止性——需要花费较长时间收敛到最优解附近；但如果目标函数非常复杂，收敛速度慢可能导致：数值解陷入局部最优或者鞍点。

关于动量法的迭代公式表示如下： 一些文章中也描述为: { m ⇐ γ ⋅ m + η ⋅ ∇ θ J ( θ ) θ ⇐ θ − m \begin{cases} m \Leftarrow \gamma \cdot m + \eta \cdot \nabla_{\theta} \mathcal J(\theta) \\ \theta \Leftarrow \theta - m \end{cases} {m⇐γ⋅m+η⋅∇θ​J(θ)θ⇐θ−m​,两者之间等价,因为负梯度方向的描述就是 − ∇ θ J ( θ ) -\nabla_{\theta} \mathcal J(\theta) −∇θ​J(θ)该式首先仅将梯度数值部分进行累积，再执行更新。 { m ⇐ γ ⋅ m − η ⋅ ∇ θ J ( θ ) θ ⇐ θ + m \begin{cases} m \Leftarrow \gamma \cdot m - \eta \cdot \nabla_{\theta} \mathcal J(\theta) \\ \theta \Leftarrow \theta + m \end{cases} {m⇐γ⋅m−η⋅∇θ​J(θ)θ⇐θ+m​ 其中 m m m表示动量；并且该变量在每次迭代过程中均被更新——它在每一次迭代过程中都对梯度元素 η ⋅ ∇ θ J ( θ ) \eta \cdot \nabla_{\theta} \mathcal J(\theta) η⋅∇θ​J(θ)进行累积； γ ∈ [ 0 , 1 ) \gamma \in [0,1) γ∈[0,1)表示动量因子，它决定了之前迭代步骤累积得到的动量衰减的程度效果。

而动量法的核心思想是：利用过去累积的梯度元素与当前迭代步骤的梯度元素进行加权运算，使其朝着最优解更快收敛：

如果 γ = 0 \gamma = 0 γ=0意味着：在当前迭代步骤中，之前累积的梯度元素没有任何比重。也就是说，每次迭代过程仅与当前迭代步骤的梯度相关，此时的动量法也退化为梯度下降法。这里以 γ = 0.1 \gamma = 0.1 γ=0.1图像进行示例： 其中绿色图像表示梯度下降法的迭代路径;红色图像则表示 γ = 0.1 \gamma=0.1 γ=0.1时动量法的迭代路径。此时两者已经非常接近了，但动量法的迭代步骤明显小于梯度法。 如果 γ ⇒ 1 \gamma \Rightarrow 1 γ⇒1意味着：当前迭代步骤中的梯度信息几乎不起作用，而过去累积的梯度元素占主导部分。这里以 γ = 0.9 \gamma=0.9 γ=0.9为例，对应图像结果表示如下： 很明显，通过红色图像可知，当前迭代步骤的梯度元素也是有意义的，不能过于否定当前结果而过于依赖过去信息。 因而需要找到合适的 γ \gamma γ，使其能够稳定收敛的基础上，减少迭代路径的距离。例如 γ = 0.6 \gamma=0.6 γ=0.6时的图像结果： 可以明显看出:随着迭代步骤的更新，动量法迭代的幅度(跨越的距离长度)越来越大。即:过去梯度元素牵制着当前步骤的梯度方向。从而会有效减少更新步骤。并且，对于这类病态条件的二次目标函数有着不错的效果。

关于动量法的更新速度，见如下示例：

m t m_t mt​表示第 t t t次迭代步骤的动量；假设每次迭代的梯度结果均相同，为 G = ∇ θ J ( θ ) \mathcal G = \nabla_{\theta} \mathcal J(\theta) G=∇θ​J(θ)，从初始时刻 m 0 = 0 m_0=0 m0​=0开始，有如下迭代过程： 常用泰勒公式，需要满足 γ ∈ ( − 1 , 1 ) \gamma \in (-1,1) γ∈(−1,1) m 0 = 0 m 1 = γ ⋅ m 0 + η ⋅ G = η ⋅ G m 2 = γ ⋅ m 1 + η ⋅ G = ( 1 + γ ) η ⋅ G m 3 = γ ⋅ m 2 + η ⋅ G = ( 1 + γ + γ 2 ) η ⋅ G ⋮ m + ∞ = ( 1 + γ + γ 2 + γ 3 + ⋯   ) η ⋅ G = 1 1 − γ η ⋅ G m_0 = 0 \\ m_1 = \gamma \cdot m_0 + \eta \cdot \mathcal G = \eta \cdot \mathcal G \\ m_2 = \gamma \cdot m_1 + \eta \cdot \mathcal G = (1 + \gamma) \eta \cdot \mathcal G \\ m_3 = \gamma \cdot m_2 + \eta \cdot \mathcal G = (1 + \gamma + \gamma^2) \eta \cdot \mathcal G\\ \vdots \\ m_{+\infty} = (1 + \gamma + \gamma^2 + \gamma^3 + \cdots) \eta \cdot \mathcal G = \frac{1}{1 - \gamma} \eta \cdot \mathcal G m0​=0m1​=γ⋅m0​+η⋅G=η⋅Gm2​=γ⋅m1​+η⋅G=(1+γ)η⋅Gm3​=γ⋅m2​+η⋅G=(1+γ+γ2)η⋅G⋮m+∞​=(1+γ+γ2+γ3+⋯)η⋅G=1−γ1​η⋅G这意味着：动量在迭代过程中进行累积， γ \gamma γ越大，动量越大，它的迭代幅度越大，更新速度也更快(见上图 2 2 2)。反之，一直快下去也不是优质的选择，我们同样需要当前迭代步骤的 η ⋅ G \eta \cdot \mathcal G η⋅G对动量进行约束。 动量法的算法过程描述

基于动量法的随机梯度下降的算法步骤表示如下： 初始化操作：

学习率 η \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)})\}_{i=1}^{k} {(x(i),y(i))}i=1k​；计算当前迭代步骤的梯度估计： 其中 f ( x ( i ) ; θ ) f(x^{(i)};\theta) f(x(i);θ)表示模型预测结果; L ( ⋅ ) \mathcal L(\cdot) L(⋅)表示损失函数; G = 1 k ∑ i = 1 k ∇ θ L [ f ( x ( i ) ; θ ) , y ( i ) ] \mathcal G = \frac{1}{k} \sum_{i=1}^k \nabla_{\theta} \mathcal L[f(x^{(i)};\theta),y^{(i)}] G=k1​i=1∑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 附：动量法示例代码

注：代码中没有使用确定的学习率作为步长，是对最速下降法代码的一个修改，使用查找的方式找到一个优质步长实现迭代过程。

import numpy as np import math import matplotlib.pyplot as plt def f(x, y): return 0.5 * (x ** 2) + 20 * (y ** 2) def ConTourFunction(x, Contour): return math.sqrt(0.05 * (Contour - (0.5 * (x ** 2)))) def Derfx(x): return x def Derfy(y): return 40 * y def DrawBackGround(): ContourList = [0.2, 1.0, 4.0, 8.0, 16.0, 32.0] LimitParameter = 0.0001 plt.figure(figsize=(10, 5)) for Contour in ContourList: # 设置范围时，需要满足x的定义域描述。 x = np.linspace(-1 * math.sqrt(2 * Contour) + LimitParameter, math.sqrt(2 * Contour) - LimitParameter, 200) y1 = [ConTourFunction(i, Contour) for i in x] y2 = [-1 * j for j in y1] plt.plot(x, y1, '--', c="tab:blue") plt.plot(x, y2, '--', c="tab:blue") def GradientDescent(stepTime=80,epsilon=5.0,mode="momentum"): assert mode in ["SGD","momentum"] Start = (8.0, 0.5) StartV = (0.0, 0.0) alpha = 0.6 LocList = list() LocList.append(Start) for _ in range(stepTime): DerStart = (Derfx(Start[0]), Derfy(Start[1])) for _,step in enumerate(list(np.linspace(0.0, 1.0, 1000))): if mode == "momentum": NextV = (alpha * StartV[0] - step * DerStart[0], alpha * StartV[1] - step * DerStart[1]) Next = (Start[0] + NextV[0],Start[1] + NextV[1]) DerfNext = Derfx(Next[0]) * (-1 * DerStart[0]) + Derfy(Next[1]) * (-1 * DerStart[1]) if abs(DerfNext) <= epsilon: LocList.append(Next) StartV = NextV Start = Next epsilon /= 1.1 break else: Next = (Start[0] - (DerStart[0] * step), Start[1] - (DerStart[1] * step)) DerfNext = Derfx(Next[0]) * (-1 * DerStart[0]) + Derfy(Next[1]) * (-1 * DerStart[1]) if abs(DerfNext) <= epsilon: LocList.append(Next) Start = Next epsilon /= 1.1 break plotList = list() if mode == "momentum": c = "tab:red" else: c = "tab:green" for (x, y) in LocList: plotList.append((x, y)) plt.scatter(x, y, s=30, facecolor="none", edgecolors=c, marker='o') if len(plotList) < 2: continue else: plt.plot([plotList[0][0], plotList[1][0]], [plotList[0][1], plotList[1][1]], c=c) plotList.pop(0) if __name__ == '__main__': DrawBackGround() GradientDescent(mode="SGD") GradientDescent(mode="momentum") plt.show()

Reference \text{Reference} Reference： 谈谈优化算法之一（动量法、Nesterov法、自然梯度法） 深度学习（一）优化算法之动量法详解