网站app建设方案,设计装修,重庆优化网站推广,wordpress phpwamp目录 1. 梯度下降算法2. BGD、SGD、MBGD3. momentum与dampening3.1 另一种形式的momentum3.1.1 学习率固定3.1.2 学习率不固定 4. nesterov4.1 PyTorch中的Nesterov4.2 Polyak与Nesterov的比较 Ref 1. 梯度下降算法
先考虑一元情形。假设待更新的参数为 θ \theta θ#xf… 目录 1. 梯度下降算法2. BGD、SGD、MBGD3. momentum与dampening3.1 另一种形式的momentum3.1.1 学习率固定3.1.2 学习率不固定 4. nesterov4.1 PyTorch中的Nesterov4.2 Polyak与Nesterov的比较 Ref 1. 梯度下降算法
先考虑一元情形。假设待更新的参数为 θ \theta θ学习率为 η \eta η目标函数为 f ( θ ) f(\theta) f(θ)则更新策略表示为 θ ← θ − η ⋅ g \theta\leftarrow \theta - \eta\cdot g θ←θ−η⋅g
其中 g f ′ ( θ ) gf(\theta) gf′(θ) 是梯度我们需要沿着梯度的反方向进行更新。
学习率 η \eta η 是我们通常所说的步长。步长过小会导致更新缓慢步长过大会导致振荡。以 f ( θ ) θ 2 f(\theta)\theta^2 f(θ)θ2 为例 θ 0 \theta0 θ0 是它的极值点。我们从 θ − 5 \theta-5 θ−5 开始进行梯度下降并设置不同的学习率来观察更新的效果。
import numpy as np
import matplotlib.pyplot as pltdef f(x):return x**2def grad_f(x):return 2*xdef gradient_descent(start_x, learning_rate, steps):x_vals [start_x]for _ in range(steps):grad grad_f(x_vals[-1])new_x x_vals[-1] - learning_rate * gradx_vals.append(new_x)return np.array(x_vals)start_x -5
steps 10
learning_rates [0.01, 0.05, 0.2, 0.7, 0.9, 1.01]
x_range np.linspace(-5.5, 5.5, 400)fig, axes plt.subplots(2, 3, figsize(10, 6.6))for idx, eta in enumerate(learning_rates):ax axes[idx // 3, idx % 3]x_vals gradient_descent(start_x, eta, steps)ax.plot(x_range, f(x_range), colorblue)ax.plot(x_vals, f(x_vals), o-, colororange)ax.set_title(fLearning Rate: {eta})ax.set_xlabel(x)ax.set_ylabel(f(x))ax.legend()plt.tight_layout()
plt.show()从图中可以观察到当学习率较小时参数更新的速度会明显减缓当学习率 0.5 0.5 0.5 时参数更新开始出现振荡现象而当学习率 1 1 1 时更新过程甚至会导致参数发散。
现考虑多元情形以二元为例。设 θ ( θ 1 , θ 2 ) \theta(\theta_1,\theta_2) θ(θ1,θ2) f ( θ ) f ( θ 1 , θ 2 ) f(\theta)f(\theta_1,\theta_2) f(θ)f(θ1,θ2)则更新策略为 θ ← θ − η ⋅ ∇ f ( θ ) ⇔ ( θ 1 , θ 2 ) ← ( θ 1 , θ 2 ) − η ⋅ ( ∂ f ∂ θ 1 , ∂ f ∂ θ 2 ) ⇔ θ i ← θ i − η ⋅ ∂ f ∂ θ i , i 1 , 2 \begin{aligned} \theta\leftarrow \theta -\eta\cdot \nabla f(\theta) \\ \Leftrightarrow\quad (\theta_1,\theta_2)\leftarrow(\theta_1,\theta_2)-\eta\cdot\left(\frac{\partial f}{\partial \theta_1},\frac{\partial f}{\partial \theta_2}\right) \\ \Leftrightarrow\quad \theta_i\leftarrow\theta_i-\eta\cdot \frac{\partial f}{\partial \theta_i},\quad i 1,2 \end{aligned} ⇔⇔θ←θ−η⋅∇f(θ)(θ1,θ2)←(θ1,θ2)−η⋅(∂θ1∂f,∂θ2∂f)θi←θi−η⋅∂θi∂f,i1,2
即每个参数分别更新。以 f ( θ 1 , θ 2 ) θ 1 2 6 θ 2 2 f(\theta_1,\theta_2)\theta_1^26\theta_2^2 f(θ1,θ2)θ126θ22 为例显然 ( 0 , 0 ) (0,0) (0,0) 是它的极值点且 ∇ f ( θ ) ( 2 θ 1 , 12 θ 2 ) \nabla f(\theta)(2\theta_1,12\theta_2) ∇f(θ)(2θ1,12θ2)。我们从 ( − 10 , 3 ) (-10,3) (−10,3) 开始进行梯度下降并设置不同的学习率来观察更新的效果。
import numpy as np
import matplotlib.pyplot as pltdef f(x1, x2):return x1**2 6*x2**2def grad_f(x1, x2):return np.array([2*x1, 12*x2])def gradient_descent(start_x, learning_rate, steps):x_vals [start_x]for _ in range(steps):grad grad_f(*x_vals[-1])new_x x_vals[-1] - learning_rate * gradx_vals.append(new_x)return np.array(x_vals)start_x np.array([-10, 3])
steps 20
learning_rates [0.01, 0.05, 0.1, 0.15, 0.2, 0.5]
x1_range np.linspace(-12, 2, 200)
x2_range np.linspace(-6, 6, 200)
x1_grid, x2_grid np.meshgrid(x1_range, x2_range)
f_vals f(x1_grid, x2_grid)fig, axes plt.subplots(2, 3, figsize(10, 6.6))for idx, eta in enumerate(learning_rates):ax axes[idx // 3, idx % 3]x_vals gradient_descent(start_x, eta, steps)ax.contour(x1_grid, x2_grid, f_vals, levels15, cmapBlues)ax.plot(x_vals[:, 0], x_vals[:, 1], o-, colororange)ax.set_title(fLearning Rate: {eta})ax.set_xlabel(r$x_1$)ax.set_ylabel(r$x_2$)ax.legend()ax.set_xlim([-12, 2])ax.set_ylim([-6, 6])plt.tight_layout()
plt.show()从图中可以看出多元情形依然有着相同的规律。学习率较小时参数更新十分缓慢当学习率增大到一定值时开始出现振荡现象继续增大学习率则会直接导致发散。
据此可以总结出梯度下降法的优缺点。
优点
计算简单易于实现。在凸优化问题中梯度下降法有严格的收敛性保证。
缺点
梯度下降法无法保证找到全局最优解特别是对于非凸函数时可能会陷入局部极小值或鞍点而难以跳出。对学习率敏感。过小的学习率会导致收敛速度过慢过大的学习率则会使得参数更新出现振荡甚至导致发散。对初始点的选择敏感若初始点距离最优点较远可能需要更多的迭代次数才能收敛甚至可能收敛到较差的局部极小值。
2. BGD、SGD、MBGD
在深度学习场景中 θ \theta θ 通常指代模型的参数而 f ( θ ) f(\theta) f(θ) 则指代模型在训练集上的平均损失即 f ( θ ) 1 n ∑ i 1 n f i ( θ ) f(\theta)\frac1n\sum_{i1}^nf_i(\theta) f(θ)n1i1∑nfi(θ)
其中 n n n 是训练集的大小 f i ( θ ) f_i(\theta) fi(θ) 是模型在第 i i i 个样本上的损失。于是 ∇ f ( θ ) 1 n ∑ i 1 n ∇ f i ( θ ) \nabla f(\theta)\frac1n\sum_{i1}^n\nabla f_i(\theta) ∇f(θ)n1i1∑n∇fi(θ)
如果采用梯度下降法那么计算 ∇ f ( θ ) \nabla f(\theta) ∇f(θ) 的时间复杂度将是 O ( n ) O(n) O(n) 的。特别是当训练集特别大时这种方法往往是不可行的。
以上方法又叫Batch Gradient DescentBGD批量梯度下降即每次采用所有样本进行更新。那我们能不能不用那么多样本呢能不能每次随机挑一个样本呢
随机挑选时每个样本被选中的概率为 1 n \frac1n n1因此 E i [ ∇ f i ( θ ) ] ∑ i 1 n 1 n ⋅ ∇ f i ( θ ) ∇ f ( θ ) \mathbb{E}_i[\nabla f_i(\theta)]\sum_{i1}^n\frac1n\cdot \nabla f_i(\theta)\nabla f(\theta) Ei[∇fi(θ)]i1∑nn1⋅∇fi(θ)∇f(θ)
这说明 ∇ f i ( θ ) \nabla f_i(\theta) ∇fi(θ) 是 ∇ f ( θ ) \nabla f(\theta) ∇f(θ) 的无偏估计因此我们可以用 ∇ f i ( θ ) \nabla f_i(\theta) ∇fi(θ) 代替 ∇ f ( θ ) \nabla f(\theta) ∇f(θ) 进行梯度下降这样一来计算 ∇ f ( θ ) \nabla f(\theta) ∇f(θ) 的时间复杂度就降低至 O ( 1 ) O(1) O(1) 了。这种方法又叫Stochastic Gradient DescentSGD随机梯度下降即每次随机挑选一个样本进行更新。
只挑选一个样本或挑选所有样本未免有些太过极端了有没有一种折中的办法呢比如每次挑选 b ( 1 ≤ b ≤ n ) b\,(1\leq b\leq n) b(1≤b≤n) 个样本来进行个更新即用下式去代替 ∇ f ( θ ) \nabla f(\theta) ∇f(θ) 1 b ∑ i ∈ B ∇ f i ( θ ) , B ⊂ { 1 , 2 , ⋯ , n } , ∣ B ∣ b \frac1b \sum_{i\in \mathcal{B}} \nabla f_i(\theta),\quad \mathcal{B}\subset \{1,2,\cdots,n\},\quad|\mathcal{B}|b b1i∈B∑∇fi(θ),B⊂{1,2,⋯,n},∣B∣b
该式依然是 ∇ f ( θ ) \nabla f(\theta) ∇f(θ) 的无偏估计且由于 ∇ f i ( θ ) \nabla f_i(\theta) ∇fi(θ) 是独立同分布的具有相同的期望和方差因此 Var i [ 1 b ∑ i ∈ B ∇ f i ( θ ) ] 1 b 2 ∑ i ∈ B Var i [ ∇ f i ( θ ) ] 1 b Var t [ ∇ f t ( θ ) ] \text{Var}_i\left[\frac1b \sum_{i\in \mathcal{B}} \nabla f_i(\theta)\right]\frac{1}{b^2}\sum_{i\in \mathcal{B}}\text{Var}_i\left[ \nabla f_i(\theta)\right]\frac1b\text{Var}_t\left[ \nabla f_t(\theta)\right] Vari[b1i∈B∑∇fi(θ)]b21i∈B∑Vari[∇fi(θ)]b1Vart[∇ft(θ)] 诸 ∇ f i ( θ ) \nabla f_i(\theta) ∇fi(θ) 的方差均为 1 n ∑ i 1 n ∥ ∇ f i ( θ ) ∥ 2 − ∥ ∇ f ( θ ) ∥ 2 \frac1n \sum_{i1}^n \Vert \nabla f_i(\theta) \Vert^2-\Vert \nabla f(\theta)\Vert^2 n1∑i1n∥∇fi(θ)∥2−∥∇f(θ)∥2证明如下 Var i [ ∇ f i ( θ ) ] E i [ ∥ ∇ f i ( θ ) − ∇ f ( θ ) ∥ 2 ] E i [ ( ∇ f i ( θ ) − ∇ f ( θ ) ) T ( ∇ f i ( θ ) − ∇ f ( θ ) ) ] E i [ ∥ ∇ f i ( θ ) ∥ 2 − 2 ∇ f i ( θ ) T ∇ f ( θ ) ∥ ∇ f ( θ ) ∥ 2 ] 1 n ∑ i 1 n ∥ ∇ f i ( θ ) ∥ 2 − ∥ ∇ f ( θ ) ∥ 2 \begin{aligned} \text{Var}_i[\nabla f_i(\theta)]\mathbb{E}_i[\Vert \nabla f_i(\theta)-\nabla f(\theta)\Vert^2]\mathbb{E}_i[(\nabla f_i(\theta)-\nabla f(\theta))^{\text{T}}(\nabla f_i(\theta)-\nabla f(\theta))] \\ \mathbb{E}_i[\Vert \nabla f_i(\theta) \Vert^2-2\nabla f_i(\theta)^{\text T}\nabla f(\theta)\Vert \nabla f(\theta)\Vert^2] \\ \frac1n \sum_{i1}^n \Vert \nabla f_i(\theta) \Vert^2-\Vert \nabla f(\theta)\Vert^2 \end{aligned} Vari[∇fi(θ)]Ei[∥∇fi(θ)−∇f(θ)∥2]Ei[(∇fi(θ)−∇f(θ))T(∇fi(θ)−∇f(θ))]Ei[∥∇fi(θ)∥2−2∇fi(θ)T∇f(θ)∥∇f(θ)∥2]n1i1∑n∥∇fi(θ)∥2−∥∇f(θ)∥2 这说明选取的 b b b 越大相应的方差就越小我们对 ∇ f ( θ ) \nabla f(\theta) ∇f(θ) 的估计就更稳定。
每次选取 b b b 个样本来进行更新的方法又叫Mini-Batch Gradient DescentMBGD小批量梯度下降。 b b b 通常被称为batch size。
据此可以对三种方法进行总结
BGD批量梯度下降每次采用所有样本来更新参数。SGD随机梯度下降每次随机选择一个样本来更新参数。MBGD小批量梯度下降每次随机选择 b b b 个样本来更新参数。
BGD、SGD可以看做是MBGD的特殊情形一个是 b b b 取 n n n一个是 b b b 取 1 1 1。 接下来对比BGD、SGD和MBGD的效果。由于BGD、SGD是MBGD的特殊情形我们只需要实现MBGD即可。
假设训练集有 100 100 100 个样本MBGD中的batch size设为 10 10 10采用MSE作为损失函数训练 5 5 5 个epoch。三种方法的更新步数如下
SGD 500 / 1 500 500/1500 500/1500 步。BGD 500 / 100 5 500/1005 500/1005 步。MBGD 500 / 10 50 500/1050 500/1050 步。 在深度学习中完整遍历一次训练集称为一个 epoch而处理一个 batch 数据称为一个 step。设训练集包含 n n n 个样本训练的 epoch 数为 e e ebatch size 为 b b b则训练过程中总的参数更新步数为 n e b \frac{ne}{b} bne。 import numpy as np
import matplotlib.pyplot as pltnp.random.seed(42)n_samples 100 # 样本数量
n_features 1 # 特征数量# 真实参数
w_true np.array([2])
b_true 5# 生成特征和标签添加一些噪声
X np.random.randn(n_samples, n_features)
noise 0.5 * np.random.randn(n_samples, 1)
y X w_true.reshape(-1, 1) b_true noisedef compute_loss(X, y, w, b):n X.shape[0]y_pred X w bloss (1 / (2 * n)) * np.sum((y_pred - y) ** 2)return lossdef compute_gradient(X, y, w, b):n X.shape[0]y_pred X w berror y_pred - ydw (1 / n) * X.T errordb (1 / n) * np.sum(error)return dw, dbdef mini_batch_gradient_descent(X, y, w_init, b_init, lr, epochs, batch_size):w w_init.copy()b b_initn X.shape[0]w_history [w.copy()]b_history [b]for _ in range(epochs):indices np.arange(n)np.random.shuffle(indices)X_shuffled X[indices]y_shuffled y[indices]for i in range(0, n, batch_size):Xi X_shuffled[i:ibatch_size]yi y_shuffled[i:ibatch_size]dw, db compute_gradient(Xi, yi, w, b)w - lr * dwb - lr * dbw_history.append(w.copy())b_history.append(b)return w, b, w_history, b_historyw_init np.array([[0.0]])
b_init 0.0
lr 0.1
epochs 5batch_sizes [1, 10, n_samples]
labels [SGD (b1), MBGD (b10), BGD (bn)]
colors [r, g, b]# 创建等高线图的数据
w_range np.linspace(-1, 5, 50)
b_range np.linspace(0, 10, 50)
W, B np.meshgrid(w_range, b_range)
Loss np.zeros_like(W)# 计算每个网格点的损失值
for i in range(W.shape[0]):for j in range(W.shape[1]):w_ij np.array([[W[i, j]]])b_ij B[i, j]Loss[i, j] compute_loss(X, y, w_ij, b_ij)plt.figure(figsize(8, 6))
CS plt.contour(W, B, Loss, levels30, cmapviridis)
plt.clabel(CS, inline1, fontsize8)
plt.xlabel(w)
plt.ylabel(b)
plt.title(Parameter Descent Paths on Loss Contour)for batch_size, label, color in zip(batch_sizes, labels, colors):w_final, b_final, w_history, b_history mini_batch_gradient_descent(X, y, w_init, b_init, lr, epochs, batch_size)w_vals np.array(w_history).flatten()b_vals np.array(b_history)plt.plot(w_vals, b_vals, markero, colorcolor, labellabel, markersize3, linewidth1)plt.legend()
plt.show()可以看出
SGD方法下降的最快但是下降的过程中波动较大且无法及时收敛到最优解。BGD方法下降的最慢5个epoch后离最优解依然还有很远的一段距离但是它的每一步都很稳定。MBGD方法的速度介于SGD和BGD之间且及时收敛到了最优解并且更新过程也比较稳定。
3. momentum与dampening
在第一节的讨论中我们提到了梯度下降容易陷入局部最优或鞍点。一个典型的例子是 y x 3 yx^3 yx3显然 x 0 x0 x0 是它的鞍点。从 x 3 x3 x3 处出发使用 0.05 0.05 0.05 的学习率进行梯度下降
import numpy as np
import matplotlib.pyplot as pltdef f(x):return x**3def grad_f(x):return 3*x**2def gradient_descent(start_x, learning_rate, steps):x_vals [start_x]for _ in range(steps):grad grad_f(x_vals[-1])new_x x_vals[-1] - learning_rate * gradx_vals.append(new_x)return np.array(x_vals)start_x 3
learning_rate 0.05
steps 20
x_vals gradient_descent(start_x, learning_rate, steps)x_range np.linspace(-5, 5, 400)
y_range f(x_range)plt.figure(figsize(8, 6))
plt.plot(x_range, y_range, colorblue)
plt.plot(x_vals, f(x_vals), o-, colororange, labellr0.05)
plt.title(Gradient Descent on $f(x) x^3$)
plt.xlabel(x)
plt.ylabel(f(x))
plt.legend()
plt.grid(True)
plt.show()在高维空间中鞍点的存在往往更加普遍。 除非调大学习率否则最后总会收敛到 x 0 x0 x0 处。这一结果显然不是我们想要的。如果把梯度下降比作小球在曲线上的滚动我们更希望小球能够越过 x 0 x0 x0 这一点继续向下滚动这也更加符合真实的物理场景。
我们已经知道梯度下降的公式为 θ ← θ − η g \theta\leftarrow\theta-\eta g θ←θ−ηg由于 η \eta η 通常是固定的因此可以将其视为一小段时间 Δ t \Delta t Δt这样一来 θ \theta θ 便可以视作位置 g g g 便可以视作速度此时公式变为 x ← x − v Δ t x\leftarrow x-v\Delta t x←x−vΔt。在梯度下降的场景中 v v v 取决于 x x x即 v v ( x ) 3 x 2 vv(x)3x^2 vv(x)3x2当 x x x 减小时 v v v 也随之减小说明小球在下落的过程中速度会越来越慢这显然是不符合事实的。一个直观的想法是我们可以累积小球的历史速度然后使用这个累积速度作为当前的速度进行下落 m t v 1 v 2 ⋯ v t x t x t − 1 − m t Δ t m_tv_1v_2\cdotsv_t \\ x_{t}x_{t-1}-m_t\Delta t mtv1v2⋯vtxtxt−1−mtΔt
其中 m t m_t mt 就是 t t t 时刻的累积速度。
直接累加会有一个很明显的缺点那就是 m t m_t mt 可以记住很久以前的速度。换句话说历史任一时刻的速度对当前累积速度的贡献都是相同的而我们更希望累积速度 m t m_t mt 具有遗忘性即距离当前时刻越远的速度相应的贡献就应当越少。
利用指数函数的衰减性我们可以重新计算累积速度 m t β 0 v t β 1 v t − 1 β 2 v t − 2 ⋯ β t − 1 v 1 , β 1 v t β ( v t − 1 β v t − 2 ⋯ β t − 2 v 1 ) β m t − 1 v t \begin{aligned} m_t\beta^0v_t\beta^1v_{t-1}\beta^2v_{t-2}\cdots\beta^{t-1}v_1,\quad\beta1 \\ v_t\beta(v_{t-1}\beta v_{t-2}\cdots\beta^{t-2}v_1) \\ \beta m_{t-1}v_t \end{aligned} mtβ0vtβ1vt−1β2vt−2⋯βt−1v1,β1vtβ(vt−1βvt−2⋯βt−2v1)βmt−1vt
于是我们得到了带动量的梯度下降公式 m t β m t − 1 g t θ t θ t − 1 − η ⋅ m t m_t\beta m_{t-1}g_t \\ \theta_t\theta_{t-1}-\eta\cdot m_t mtβmt−1gtθtθt−1−η⋅mt
其中 m t m_t mt 是动量 β \beta β 是动量系数。
设置 β 0.9 \beta0.9 β0.9更新步数为 5 5 5我们来观察小球的运动轨迹
def gradient_descent(start_x, learning_rate, steps):x_vals [start_x]m 0beta 0.9for _ in range(steps):grad grad_f(x_vals[-1])m beta * m gradnew_x x_vals[-1] - learning_rate * mx_vals.append(new_x)return np.array(x_vals)可以发现此时小球成功越过了鞍点。
接下来以 y x 2 yx^2 yx2 为例比较带动量和不带动量的梯度下降法的效果
import numpy as np
import matplotlib.pyplot as plt
from matplotlib.animation import FuncAnimation, PillowWriterdef f(x):return x**2def grad_f(x):return 2*x# 带动量的梯度下降算法
def gradient_descent_with_momentum(start_x, learning_rate, steps):x_vals [start_x]m 0beta 0.9for _ in range(steps):grad grad_f(x_vals[-1])m beta * m gradnew_x x_vals[-1] - learning_rate * mx_vals.append(new_x)return np.array(x_vals)# 不带动量的梯度下降算法
def gradient_descent_without_momentum(start_x, learning_rate, steps):x_vals [start_x]for _ in range(steps):grad grad_f(x_vals[-1])new_x x_vals[-1] - learning_rate * gradx_vals.append(new_x)return np.array(x_vals)start_x 3
learning_rate 0.05
steps 50x_vals_with_momentum gradient_descent_with_momentum(start_x, learning_rate, steps)
x_vals_without_momentum gradient_descent_without_momentum(start_x, learning_rate, steps)x_range np.linspace(-5, 5, 400)
y_range f(x_range)fig, (ax1, ax2) plt.subplots(1, 2, figsize(16, 6))ax1.plot(x_range, y_range, colorblue)
point1, ax1.plot([], [], o, colororange, markersize10, labelWith Momentum)
ax1.set_title(Gradient Descent with Momentum on $f(x) x^2$, fontsize16)
ax1.set_xlabel(x, fontsize14)
ax1.set_ylabel(f(x), fontsize14)
ax1.legend(fontsize12)
ax1.grid(True)ax2.plot(x_range, y_range, colorblue)
point2, ax2.plot([], [], o, colorgreen, markersize10, labelWithout Momentum)
ax2.set_title(Gradient Descent without Momentum on $f(x) x^2$, fontsize16)
ax2.set_xlabel(x, fontsize14)
ax2.set_ylabel(f(x), fontsize14)
ax2.legend(fontsize12)
ax2.grid(True)def init():point1.set_data([], [])point2.set_data([], [])return point1, point2def update(frame):point1.set_data(x_vals_with_momentum[frame], f(x_vals_with_momentum[frame]))point2.set_data(x_vals_without_momentum[frame], f(x_vals_without_momentum[frame]))return point1, point2ani FuncAnimation(fig, update, frameslen(x_vals_with_momentum), init_funcinit, blitTrue, interval100)
ani.save(gradient_descent_comparison.gif, writerPillowWriter(fps10))plt.show()显然左图更贴近现实世界的情况但其收敛速度不如右图快。原因是动量法会累积历史梯度从而导致过冲和振荡。既然我们可以控制历史累积梯度的贡献程度即 β \beta β我们同样希望能控制当前梯度的贡献程度由此可以引入阻尼系数 τ \tau τ它相当于摩擦力从而动量的更新公式变为 m t β m t − 1 ( 1 − τ ) g t m_t\beta m_{t-1}(1-\tau)g_t mtβmt−1(1−τ)gt
有些教程会将 τ \tau τ 固定为 β \beta β使得 g t g_t gt 的贡献程度恒为 1 − β 1 - \beta 1−β这在一定程度上限制了灵活性。
为了充分验证动量系数和阻尼系数对优化过程的影响我们选取函数 f ( x ) ( x 2 ) 2 ( x − 1 ) 2 1.5 x 2 f(x) (x2)^2(x-1)^2 1.5x^2 f(x)(x2)2(x−1)21.5x2 进行实验。该函数具有两个极小值点其中一个为局部极小值另一个为全局极小值。实验从初始点 x − 2.5 x -2.5 x−2.5 开始学习率设定为 0.01 0.01 0.01并通过以下六组设置进行比较
不使用动量和阻尼。动量系数设置为 0.9 0.9 0.9阻尼系数为 0 0 0。动量系数设置为 0.9 0.9 0.9阻尼系数为 0.5 0.5 0.5。动量系数设置为 0.9 0.9 0.9阻尼系数为 0.9 0.9 0.9。动量系数设置为 0.99 0.99 0.99阻尼系数为 0 0 0。动量系数设置为 0.999 0.999 0.999阻尼系数为 0 0 0。
import numpy as np
import matplotlib.pyplot as plt
from matplotlib.animation import FuncAnimation, PillowWriterdef f(x):return (x 2)**2 * (x - 1)**2 1.5 * x**2def grad_f(x):return 2 * (x 2) * (x - 1)**2 2 * (x - 1) * (x 2)**2 3 * xdef gradient_descent_with_momentum(start_x, learning_rate, steps, beta0.9, tau0.0):x_vals [start_x]m 0for _ in range(steps):grad grad_f(x_vals[-1])m beta * m (1 - tau) * gradnew_x x_vals[-1] - learning_rate * mx_vals.append(new_x)return np.array(x_vals)start_x -2.5
learning_rate 0.01
steps 100x_vals_no_momentum gradient_descent_with_momentum(start_x, learning_rate, steps, beta0.0, tau0.0)
x_vals_momentum_no_damping gradient_descent_with_momentum(start_x, learning_rate, steps, beta0.9, tau0.0)
x_vals_momentum_medium_damping gradient_descent_with_momentum(start_x, learning_rate, steps, beta0.9, tau0.5)
x_vals_momentum_high_damping gradient_descent_with_momentum(start_x, learning_rate, steps, beta0.9, tau0.9)
x_vals_momentum_0_99 gradient_descent_with_momentum(start_x, learning_rate, steps, beta0.99, tau0.0)
x_vals_momentum_0_999 gradient_descent_with_momentum(start_x, learning_rate, steps, beta0.999, tau0.0)x_range np.linspace(-3, 2, 400)
y_range f(x_range)fig, axes plt.subplots(2, 3, figsize(10, 6))titles [No Momentum, No Damping, Momentum0.9, No Damping,Momentum0.9, Damping0.5,Momentum0.9, Damping0.9,Momentum0.99, No Damping,Momentum0.999, No Damping
]
colors [orange, green, blue, red, purple, brown]
x_vals_list [x_vals_no_momentum,x_vals_momentum_no_damping,x_vals_momentum_medium_damping,x_vals_momentum_high_damping,x_vals_momentum_0_99,x_vals_momentum_0_999
]plots []
for i, ax in enumerate(axes.flat):ax.plot(x_range, y_range, colorblue)point, ax.plot([], [], o, colorcolors[i], markersize8)ax.set_title(titles[i])ax.set_xlim([-3, 2])ax.set_ylim([0, 30])ax.set_xlabel(x)ax.set_ylabel(f(x))ax.grid(True)plots.append(point)def init():for plot in plots:plot.set_data([], [])return plotsdef update(frame):for i in range(6):plots[i].set_data(x_vals_list[i][frame], f(x_vals_list[i][frame]))return plotsani FuncAnimation(fig, update, frameslen(x_vals_no_momentum), init_funcinit, blitTrue, interval100)
ani.save(momentum_damping_experiments.gif, writerPillowWriter(fps10))plt.show()从图中可以得出以下结论
在未使用动量法即无动量和阻尼的情况下或当阻尼系数较大时优化过程更容易陷入局部极小值。动量系数过大时对历史梯度的记忆会更加明显可能导致优化过程中的振荡现象。
一般而言建议设置 β 0.9 , τ 0 \beta0.9,\tau0 β0.9,τ0但更多时候还是要视具体情况而定。 ⚠️ 学术界关于阻尼系数的研究目前还不是很充分大多数情况下建议直接设置为 0 0 0即不考虑阻尼。 回顾第一节中的二元梯度下降当学习率设置为 0.15 0.15 0.15 时优化过程呈振荡式下降。设置合适的动量系数可以有效缓解振荡并加速下降。
import numpy as np
import matplotlib.pyplot as pltdef f(x1, x2):return x1**2 6*x2**2def grad_f(x1, x2):return np.array([2*x1, 12*x2])def gradient_descent_with_momentum(start_x, learning_rate, steps, beta0):x_vals [start_x]m 0for _ in range(steps):grad grad_f(*x_vals[-1])m beta * m gradnew_x x_vals[-1] - m * learning_ratex_vals.append(new_x)return np.array(x_vals)start_x np.array([-10, 3])
steps 100
learning_rate 0.15
beta_momentum 0.3
x1_range np.linspace(-12, 2, 200)
x2_range np.linspace(-6, 6, 200)
x1_grid, x2_grid np.meshgrid(x1_range, x2_range)
f_vals f(x1_grid, x2_grid)fig, axes plt.subplots(1, 2, figsize(12, 4))x_vals gradient_descent_with_momentum(start_x, learning_rate, steps, beta0)
ax axes[0]
ax.contour(x1_grid, x2_grid, f_vals, levels15, cmapBlues)
ax.plot(x_vals[:, 0], x_vals[:, 1], o-, colororange)
ax.set_title(fGradient Descent (LR: {learning_rate}))
ax.set_xlabel(r$x_1$)
ax.set_ylabel(r$x_2$)
ax.set_xlim([-12, 2])
ax.set_ylim([-6, 6])x_vals_momentum gradient_descent_with_momentum(start_x, learning_rate, steps, betabeta_momentum)
ax axes[1]
ax.contour(x1_grid, x2_grid, f_vals, levels15, cmapBlues)
ax.plot(x_vals_momentum[:, 0], x_vals_momentum[:, 1], o-, colororange)
ax.set_title(fMomentum (LR: {learning_rate}, Beta: {beta_momentum}))
ax.set_xlabel(r$x_1$)
ax.set_ylabel(r$x_2$)
ax.set_xlim([-12, 2])
ax.set_ylim([-6, 6])plt.tight_layout()
plt.show()在不使用动量的情况下每次参数更新的梯度可以分解为沿 x 1 x_1 x1 和 x 2 x_2 x2 方向的分量。其中沿 x 1 x_1 x1 方向的梯度始终为正因此参数在该方向上会持续减小而沿 x 2 x_2 x2 方向的梯度则时而为正、时而为负导致参数在该方向上的更新呈现出上下振荡的趋势。
动量法通过累积梯度有效缓解了这种振荡现象。由于沿 x 2 x_2 x2 方向的梯度正负交替变化动量累积过程中这些相反的梯度部分抵消从而减小了沿 x 2 x_2 x2 方向的振荡幅度。与此同时沿 x 1 x_1 x1 方向的梯度始终为正因此动量会不断累积导致参数沿 x 1 x_1 x1 方向下降得越来越快。
当然在此场景中若设置 β 0.9 \beta0.9 β0.9参数更新就会出现过冲现象。
3.1 另一种形式的momentum
3.1.1 学习率固定
我们之前提到的带动量的更新公式为 m t β m t − 1 g t θ t θ t − 1 − η ⋅ m t m_t\beta m_{t-1}g_t \\ \theta_t\theta_{t-1}-\eta\cdot m_t mtβmt−1gtθtθt−1−η⋅mt
在不少教程中还存在另外一种形式 m t β m t − 1 − η ⋅ g t θ t θ t − 1 m t m_t\beta m_{t-1}-\eta \cdot g_t \\ \theta_t\theta_{t-1}m_t mtβmt−1−η⋅gtθtθt−1mt
先来推导第一个形式。不难得出 m t ∑ i 1 t β t − i g i , θ t θ 0 − η ∑ i 1 t m i m_t\sum_{i1}^t \beta^{t-i} g_i,\quad \theta_t\theta_0-\eta\sum_{i1}^t m_i mti1∑tβt−igi,θtθ0−ηi1∑tmi
合并两式即可得到 θ t θ 0 − η ∑ i 1 t ∑ j 1 i β i − j g j \theta_t\theta_0-\eta\sum_{i1}^t\sum_{j1}^i\beta^{i-j}g_j θtθ0−ηi1∑tj1∑iβi−jgj
再来推导第二个形式。不难得出 m t − η ∑ i 1 t β t − i g i , θ t θ 0 ∑ i 1 t m i m_t-\eta\sum_{i1}^t \beta^{t-i} g_i,\quad \theta_t\theta_0\sum_{i1}^t m_i mt−ηi1∑tβt−igi,θtθ0i1∑tmi
合并两式即可得到 θ t θ 0 − η ∑ i 1 t ∑ j 1 i β i − j g j \theta_t\theta_0-\eta\sum_{i1}^t\sum_{j1}^i\beta^{i-j}g_j θtθ0−ηi1∑tj1∑iβi−jgj
由此可知学习率固定的情况下这两种形式是完全等价的。
3.1.2 学习率不固定
此时每一步的学习率都不一样第一种形式的更新公式为 m t β m t − 1 g t θ t θ t − 1 − η t ⋅ m t m_t\beta m_{t-1}g_t \\ \theta_t\theta_{t-1}-\eta_t\cdot m_t mtβmt−1gtθtθt−1−ηt⋅mt
不难得出 m t ∑ i 1 t β t − i g i , θ t θ 0 − ∑ i 1 t η i m i m_t\sum_{i1}^t \beta^{t-i} g_i,\quad \theta_t\theta_0-\sum_{i1}^t \eta_im_i mti1∑tβt−igi,θtθ0−i1∑tηimi
合并两式即可得到 θ t θ 0 − ∑ i 1 t η i ∑ j 1 i β i − j g j \theta_t\theta_0-\sum_{i1}^t\eta_i\sum_{j1}^i\beta^{i-j}g_j θtθ0−i1∑tηij1∑iβi−jgj
第二种形式的更新公式为 m t β m t − 1 − η t ⋅ g t θ t θ t − 1 m t m_t\beta m_{t-1}-\eta_t \cdot g_t \\ \theta_t\theta_{t-1}m_t mtβmt−1−ηt⋅gtθtθt−1mt
不难得出 m t − ∑ i 1 t β t − i η i g i , θ t θ 0 ∑ i 1 t m i m_t-\sum_{i1}^t \beta^{t-i} \eta_ig_i,\quad \theta_t\theta_0\sum_{i1}^t m_i mt−i1∑tβt−iηigi,θtθ0i1∑tmi
合并两式即可得到 θ t θ 0 − ∑ i 1 t ∑ j 1 i β i − j η j g j \theta_t\theta_0-\sum_{i1}^t\sum_{j1}^i\beta^{i-j}\eta_jg_j θtθ0−i1∑tj1∑iβi−jηjgj
可以看出学习率不固定的情况下两者并不等价。
4. nesterov
Nesterov Accelerated Gradient (NAG) 是一种加速梯度下降的优化算法最早由苏联数学家 Yurii Nesterov 提出。它是对标准的带动量梯度下降方法的改进能够在收敛性和效率上表现得更好。与标准动量方法不同NAG 在计算梯度时并不是根据当前的参数位置而是根据向前预测的参数位置。这个改进让NAG可以在每一步中更具前瞻性避免在接近局部最优点或鞍点时的惯性过冲现象。
NAG的主要思想是利用当前的动量预测出未来参数的位置然后在该预测位置计算梯度再利用这个梯度来调整动量和更新参数。
这样解释或许有些抽象为方便接下来的讲解我们假定 β η 1 \beta\eta1 βη1从而更新公式变为 m t m t − 1 g t θ t θ t − 1 − m t m_tm_{t-1}g_t\\ \theta_t\theta_{t-1}-m_t mtmt−1gtθtθt−1−mt
在高维空间中上述公式其实就是向量的加减法。下图展示了从 θ t − 1 \theta_{t-1} θt−1 到 θ t \theta_t θt 的更新过程 ⚠️ 图中和 g , m g,m g,m 相关的均在前面加上了负号这是因为它们原本表示的是上升的方向加上负号才能变成下降的方向。 模型初始参数为 θ 0 \theta_0 θ0动量初始为 m 0 0 m_00 m00因为还没开始累积。
在第 1 1 1 时刻我们会在 θ 0 \theta_0 θ0 处计算梯度得到 g 1 ∇ f ( θ 0 ) g_1\nabla f(\theta_0) g1∇f(θ0)然后我们会用当前时刻的梯度 g 1 g_1 g1 和上一时刻的动量 m 0 m_0 m0历史累积梯度合成当前时刻的动量 m 1 m 0 g 1 m_1m_0g_1 m1m0g1。当前时刻的动量代表了 θ \theta θ 将要更新的方向。
以此类推在第 t t t 时刻我们会在 θ t − 1 \theta_{t-1} θt−1 处计算梯度得到 g t ∇ f ( θ t − 1 ) g_t\nabla f(\theta_{t-1}) gt∇f(θt−1)。然后用当前时刻的梯度 g t g_t gt 和上一时刻的动量 m t − 1 m_{t-1} mt−1历史累积梯度合成当前时刻的动量 m t m_t mt。
仔细观察 m t m_t mt 决定了第 t t t 时刻的更新方向即当前时刻的动量决定了当前时刻的参数更新并且参数更新均是使用动量来完成的。既然 m t m_t mt 的计算依赖于 m t − 1 m_{t-1} mt−1 和 g t g_t gt那在计算之前我们能不能用上一时刻的动量来提前预判当前时刻的参数更新呢即用 m t − 1 m_{t-1} mt−1 去预判 θ t \theta_t θt 的位置。
我们在第 t t t 时刻不去计算 m t m_t mt而是先用 m t − 1 m_{t-1} mt−1 去预判 θ t \theta_t θt 的位置假设预判的结果为 θ ~ t \tilde{\theta}_t θ~t那么有 θ ~ t θ t − 1 − m t − 1 \tilde{\theta}_t\theta_{t-1}-m_{t-1} θ~tθt−1−mt−1然后我们在预判的位置上重新计算梯度 g ~ t ∇ f ( θ ~ t ) \tilde{g}_t\nabla f(\tilde{\theta}_t) g~t∇f(θ~t)于是可以得到第 t t t 时刻的更新结果 θ t θ ~ t − g ~ t θ t − 1 − m t − 1 − ∇ f ( θ t − 1 − m t − 1 ) θ t − 1 − ( m t − 1 ∇ f ( θ t − 1 − m t − 1 ) ) \theta_t\tilde{\theta}_t-\tilde{g}_t\theta_{t-1}-m_{t-1}-\nabla f(\theta_{t-1}-m_{t-1})\theta_{t-1}-(m_{t-1}\nabla f(\theta_{t-1}-m_{t-1})) θtθ~t−g~tθt−1−mt−1−∇f(θt−1−mt−1)θt−1−(mt−1∇f(θt−1−mt−1))
完整的更新公式如下 m t m t − 1 ∇ f ( θ t − 1 − m t − 1 ) θ t θ t − 1 − m t m_tm_{t-1}\nabla f(\theta_{t-1}-m_{t-1}) \\ \theta_t\theta_{t-1}-m_t mtmt−1∇f(θt−1−mt−1)θtθt−1−mt Nesterov相比原始的动量法无非是计算梯度的位置发生了变化原先是在 θ t − 1 \theta_{t-1} θt−1 处计算梯度而现在是在 θ ~ t θ t − 1 − m t − 1 \tilde{\theta}_t\theta_{t-1}-m_{t-1} θ~tθt−1−mt−1 处计算梯度更具有前瞻性。
Nesterov原论文中的更新公式如下 m t β m t − 1 − η ∇ f ( θ t − 1 β m t − 1 ) θ t θ t − 1 m t m_{t}\beta m_{t-1}-\eta \nabla f(\theta_{t-1}\beta m_{t-1}) \\ \theta_t\theta_{t-1}m_t mtβmt−1−η∇f(θt−1βmt−1)θtθt−1mt
这对应了我们之前所说的第二种形式的momentum。那第一种形式对应的Nesterov公式又是什么样的呢首先可以知道 θ t θ t − 1 − η m t θ t − 1 − η ( β m t − 1 g t ) ( θ t − 1 − η β m t − 1 ) − η g t − 1 \begin{aligned} \theta_t\theta_{t-1}-\eta m_t \\ \theta_{t-1}-\eta(\beta m_{t-1}g_t) \\ (\theta_{t-1}-\eta \beta m_{t-1})-\eta g_{t-1} \end{aligned} θtθt−1−ηmtθt−1−η(βmt−1gt)(θt−1−ηβmt−1)−ηgt−1
于是可以推测 g t − 1 ∇ f ( θ t − 1 − η β m t − 1 ) g_{t-1}\nabla f(\theta_{t-1}-\eta \beta m_{t-1}) gt−1∇f(θt−1−ηβmt−1)从而该形式下的Nesterov公式为 m t β m t − 1 ∇ f ( θ t − 1 − η β m t − 1 ) θ t θ t − 1 − η m t ( ∗ ) m_{t}\beta m_{t-1}\nabla f(\theta_{t-1}-\eta \beta m_{t-1}) \\ \theta_t \theta_{t-1}-\eta m_t \tag{$*$} mtβmt−1∇f(θt−1−ηβmt−1)θtθt−1−ηmt(∗)
4.1 PyTorch中的Nesterov
PyTorch中的Nesterov公式为 m t β m t − 1 ∇ f ( θ t − 1 ) θ t θ t − 1 − η ( β m t ∇ f ( θ t − 1 ) ) m_t\beta m_{t-1} \nabla f(\theta_{t-1}) \\ \theta_{t}\theta_{t-1}-\eta(\beta m_t\nabla f(\theta_{t-1})) mtβmt−1∇f(θt−1)θtθt−1−η(βmt∇f(θt−1))
可以发现它并没有使用偏移后的参数进行梯度计算这是为什么呢
在 ( ∗ ) (*) (∗) 式中令 θ ~ t − 1 θ t − 1 − η β m t − 1 \tilde{\theta}_{t-1}\theta_{t-1}-\eta \beta m_{t-1} θ~t−1θt−1−ηβmt−1然后利用 ( ∗ ) (*) (∗) 式中的结果去推导 θ ~ t \tilde{\theta}_{t} θ~t θ ~ t θ t − η β m t θ t − 1 − η m t − η β m t θ t − 1 − η ( β m t − 1 ∇ f ( θ ~ t − 1 ) ) − η β m t ( θ t − 1 − η β m t − 1 ) − η ∇ f ( θ ~ t − 1 ) − η β m t θ ~ t − 1 − η ( β m t ∇ f ( θ ~ t − 1 ) ) \begin{aligned} \tilde{\theta}_{t}\theta_{t}-\eta\beta m_{t} \\ \theta_{t-1}-\eta m_t-\eta \beta m_t \\ \theta_{t-1}-\eta(\beta m_{t-1}\nabla f(\tilde{\theta}_{t-1}))-\eta\beta m_t \\ (\theta_{t-1}-\eta\beta m_{t-1})-\eta \nabla f(\tilde{\theta}_{t-1})-\eta\beta m_t \\ \tilde{\theta}_{t-1}-\eta(\beta m_t\nabla f(\tilde{\theta}_{t-1})) \end{aligned} θ~tθt−ηβmtθt−1−ηmt−ηβmtθt−1−η(βmt−1∇f(θ~t−1))−ηβmt(θt−1−ηβmt−1)−η∇f(θ~t−1)−ηβmtθ~t−1−η(βmt∇f(θ~t−1))
由此可以得知PyTorch在实际进行计算的时候是把参数 θ t \theta_t θt 当作是已经偏移过后的参数 θ ~ t \tilde{\theta}_t θ~t所以其实一直更新的是 θ ~ t \tilde{\theta}_t θ~t。按理来说在更新结束后我们应当修正回原来的参数 θ t θ ~ t η β m t \theta_t\tilde{\theta}_t\eta\beta m_t θtθ~tηβmt
但PyTorch的源码中并未做这一修正所以PyTorch关于Nesterov的实现实际上是一种近似。
4.2 Polyak与Nesterov的比较 Polyak动量法就是传统的动量法也叫Classical MomentumCM。 我们使用PyTorch中的更新方法初始时先进行偏移即 θ ~ 0 θ 0 − η β m 0 θ 0 \tilde{\theta}_0\theta_0-\eta\beta m_0\theta_0 θ~0θ0−ηβm0θ0之后的每次更新按照如下流程计算 m t β m t − 1 ∇ f ( θ ~ t − 1 ) ∇ f ( θ ~ t − 1 ) ∇ f ( θ ~ t − 1 ) β m t θ t θ t − 1 − η ∇ f ( θ ~ t − 1 ) m_t\beta m_{t-1} \nabla f(\tilde{\theta}_{t-1}) \\ \nabla f(\tilde{\theta}_{t-1}) \nabla f(\tilde{\theta}_{t-1}) \beta m_t\\ \theta_{t}\theta_{t-1}-\eta \nabla f(\tilde{\theta}_{t-1}) mtβmt−1∇f(θ~t−1)∇f(θ~t−1)∇f(θ~t−1)βmtθtθt−1−η∇f(θ~t−1)
计算完成后修正参数即可。
import numpy as np
import matplotlib.pyplot as plt
from matplotlib.animation import FuncAnimation, PillowWriterdef f(x):return (x 2)**2 * (x - 1)**2 1.5 * x**2def grad_f(x):return 2 * (x 2) * (x - 1)**2 2 * (x - 1) * (x 2)**2 3 * xdef gradient_descent_with_momentum(start_x, learning_rate, steps, beta0.9, nesterovFalse):x_vals [start_x]m 0for _ in range(steps):grad grad_f(x_vals[-1])m beta * m gradif nesterov:grad beta * melse:grad mnew_x x_vals[-1] - learning_rate * gradx_vals.append(new_x)if nesterov:x_vals[-1] beta * learning_rate * mreturn np.array(x_vals)start_x -3
learning_rate 0.01
steps 100x_vals_momentum gradient_descent_with_momentum(start_x, learning_rate, steps, beta0.9, nesterovFalse)
x_vals_nesterov gradient_descent_with_momentum(start_x, learning_rate, steps, beta0.9, nesterovTrue)x_range np.linspace(-3.5, 2, 400)
y_range f(x_range)fig, axes plt.subplots(1, 2, figsize(12, 6))titles [Momentum0.9, No Nesterov, Momentum0.9, Nesterov]
x_vals_list [x_vals_momentum, x_vals_nesterov]
colors [green, red]plots []
for i, ax in enumerate(axes):ax.plot(x_range, y_range, colorblue)point, ax.plot([], [], o, colorcolors[i], markersize8)ax.set_title(titles[i])ax.set_xlim([-3, 2])ax.set_ylim([0, 30])ax.set_xlabel(x)ax.set_ylabel(f(x))ax.grid(True)plots.append(point)def init():for plot in plots:plot.set_data([], [])return plotsdef update(frame):for i in range(2):plots[i].set_data(x_vals_list[i][frame], f(x_vals_list[i][frame]))return plotsani FuncAnimation(fig, update, frameslen(x_vals_momentum), init_funcinit, blitTrue, interval100)
ani.save(momentum_vs_nesterov.gif, writerPillowWriter(fps10))plt.show()可以看到Nesterov明显收敛的更快。 Ref
[1] https://pytorch.org/docs/stable/generated/torch.optim.SGD.html [2] https://d2l.ai/chapter_optimization/momentum.html [3] https://www.bilibili.com/video/BV1jh4y1q7ua [4] https://www.bilibili.com/video/BV1YF411n7Dr [5] https://optimi.benjaminwarner.dev/optimizers/sgd/ [6] https://towardsdatascience.com/is-pytorchs-nesterov-momentum-implementation-wrong-5dc5f5032008 [7] https://www.bilibili.com/video/BV1kL411E7P5
