優化算法optimization：SGD動量法momentum

動量法

提出動機

在SGD的每次疊代中，梯度下降根據自變量目前位置，沿着目前位置的梯度更新自變量。然而，如果自變量的疊代方向僅僅取決于自變量目前位置可能會帶來一些問題。

我們考慮一個二維輸入向量 x = [ x 1 , x 2 ] T x = [x_1,x_2]^T x=[x1​,x2​]T和目标函數 f ( x ) = 0.1 x 1 2 + 2 x 2 2 f(x) =0.1x_1^2+2x_2^2 f(x)=0.1x12​+2x22​。

import numpy as np
import matplotlib.pyplot as plt

# 目标函數
def f_2d(x1, x2):
    return 0.1 * x1 ** 2 + 2 * x2 ** 2

# 目标函數的梯度
def gd_2d(x1, x2, s1, s2, eta=0.4):
    return (x1 - eta * 0.2 * x1, x2 - eta * 4 * x2, 0, 0)

# x參數為起始位置，s是自變量狀态
def train_2d(trainer, iters=20, x1=-5, x2=-2, s1=0, s2=0): 
    results = [(x1, x2)]
    for i in range(iters):
        x1, x2, s1, s2 = trainer(x1, x2, s1, s2)
        results.append((x1, x2))
    print('epoch {}, x1 {}, x2 {}'.format(i+1, x1, x2))
    return results

# 梯度下降過程
def show_trace_2d(f, results, xrange=np.arange(-5.5, 1.0, 0.1), yrange=np.arange(-3.0, 2.0, 0.1)):  
    plt.plot(*zip(*results), '-o', color='#ff7f0e')
    x1, x2 = np.meshgrid(xrange, yrange)
    plt.contour(x1, x2, f(x1, x2), colors='#1f77b4')
    plt.xlabel('x1')
    plt.ylabel('x2')
           

利用如下代碼畫出運作軌迹。

我們發現，最開始的幾次疊代在梯度陡峭的方向進行較大的更新，但是這種震蕩恰恰是我們不太需要的。我們更希望向梯度較為平緩的方向進行更新。如果調大學習率，在梯度較為平緩的方向進行的更新确實會增大，但是也可能導緻參數最後沒有收斂到最優解。

動量法

我們定義動量超參數 γ \gamma γ，範圍是 [ 0 , 1 ) [0,1) [0,1)。取零時，等同于小批量随機梯度下降。在時間步 t t t的小批量随機梯度為 g t g_t gt​，學習率是 η t \eta_t ηt​。對每次疊代做如下改動

v t = γ v t − 1 + η t g t x t = x t − 1 − v t v_t = \gamma v_{t-1} + \eta_tg_t \\\\ x_t = x_{t-1} - v_t vt​=γvt−1​+ηt​gt​xt​=xt−1​−vt​

利用代碼畫出更新過程。

def momentum_2d(x1, x2, v1, v2, eta=0.4, gamma=0.5):
    v1 = gamma * v1 + eta * 0.2 * x1 ## 此處導數是寫死
    v2 = gamma * v2 + eta * 4 * x2 ## 此處導數是寫死
    return x1 - v1, x2 - v2, v1, v2

show_trace_2d(f_2d, train_2d(momentum_2d))
           

我們發現軌迹在上下方向的振幅減小了，而且更快收斂到了最優解。

指數權重移動平均

學過時間序列的同學可能對權重移動平均非常熟悉。目前時間步 t t t的變量 y t y_t yt​是上一時間步改變量的值和目前時間步另一變量 x t x_t xt​的線性組合。

y t = γ y t − 1 + ( 1 − γ ) x t y_t = \gamma y_{t-1} + (1-\gamma) x_t yt​=γyt−1​+(1−γ)xt​

如果我們将這個通項公式進行展開，

y t = ( 1 − γ ) x t + γ y t − 1 = ( 1 − γ ) x t + ( 1 − γ ) γ x t − 1 + γ 2 y t − 2 = ( 1 − γ ) x t + ( 1 − γ ) γ x t − 1 + ( 1 − γ ) γ 2 x t − 2 + γ 3 y t − 3 . . . . y_t = (1-\gamma) x_t + \gamma y_{t-1}\\\\ = (1-\gamma) x_t + (1-\gamma) \gamma x_{t-1} + \gamma^2 y_{t-2}\\\\ = (1-\gamma) x_t + (1-\gamma) \gamma x_{t-1} + (1-\gamma) \gamma^2 x_{t-2} + \gamma^3 y_{t-3}\\\\ .... yt​=(1−γ)xt​+γyt−1​=(1−γ)xt​+(1−γ)γxt−1​+γ2yt−2​=(1−γ)xt​+(1−γ)γxt−1​+(1−γ)γ2xt−2​+γ3yt−3​....

令 n = 1 / ( 1 − γ ) n=1/(1-\gamma) n=1/(1−γ)，可以得到

( 1 − 1 n ) n = γ 1 1 − γ (1- \frac 1 n)^n = \gamma^{\frac 1 {1-\gamma}} (1−n1​)n=γ1−γ1​

我們知道

l i m n → ∞ ( 1 − 1 n ) n = e x p ( − 1 ) ≈ 0.3679 lim_{n \rightarrow \infty} (1 - \frac 1 n)^n = exp(-1) \approx 0.3679 limn→∞​(1−n1​)n=exp(−1)≈0.3679

是以，當 γ → 1 \gamma \rightarrow 1 γ→1時， γ 1 1 − γ = e x p ( − 1 ) \gamma^{\frac 1 {1-\gamma}} = exp(-1) γ1−γ1​=exp(−1)。我們可以将 e x p ( − 1 ) exp(-1) exp(−1)當成一個很小的數，進而在通項公式展開中忽略帶有這一項（或者更高階）的系數的項。是以，在實際中，我們常常将 y t y_t yt​看成是對最近 1 1 − γ \frac 1 {1-\gamma} 1−γ1​個時間步的 x t x_t xt​值的權重平均。距離目前時間步 t t t越近的 x t x_t xt​值獲得的權重越大（越接近1）。

我們可以對動量法的速度變量做變形。

v t = γ v t − 1 + ( 1 − γ ) ( η t 1 − γ g t ) v_t = \gamma v_{t-1} + (1-\gamma) (\frac {\eta_t} {1-\gamma} g_t) vt​=γvt−1​+(1−γ)(1−γηt​​gt​)

由指數權重移動平均的形式可得，速度變量 v t v_t vt​實際上對序列 η t 1 − γ g t \frac{\eta_t} {1-\gamma} g_t 1−γηt​​gt​做了指數權重移動平均。動量法在每個時間步的自變量更新量近似于将前者對應的最近 1 / ( 1 − γ ) 1/(1−\gamma) 1/(1−γ)個時間步的更新量做了指數權重移動平均後再除以 1 − γ 1−\gamma 1−γ。是以，在動量法中，自變量在各個方向上的移動幅度不僅取決于目前梯度，還取決于過去的各個梯度在各個方向上是否一緻。如果一緻，則會加速，使自變量向最優解更快移動。

代碼實作

def init_momentum_states(dim=2):
    v_w = np.zeros((dim, 1))
    v_b = np.zeros(1)
    return (v_w, v_b)

def sgd_momentum(params, states, hyperparams):
    for p, v in zip(params, states):
        v[:] = hyperparams['momentum'] * v + hyperparams['lr'] * p.grad
        p[:] -= v
           

Reference

• Dive Into Deep Learning，第7章