参考 动手学深度学习-11.优化算法

AI辅助创作，部分内容因个人时间精力进行了取舍

梯度下降

利用泰勒展开，\(f(x+\epsilon) = f(x) + \epsilon f'(x)+O(\epsilon ^ 2)\)，由于我们的目的是求得另一个\(x_1\)，使得\(f(x_1) \lt f(x)\)，其中\(x_1=x+\epsilon\)

换言之就是让$\epsilon f'(x)<0$

固定步长为\(\eta>0\),取\(\epsilon=-\eta f'(x)\),代入可得\(\epsilon f'(x) = -\eta f'(x)^2 <0\)

1
2
3
4

%matplotlib inline
import numpy as np
import torch
from d2l import torch as d2l

定义目标函数为\(f(x)=x^2\),目标函数导数为\(2x\)

1
2
3
4

def f(x):
    return x ** 2
def f_grad(x):
    return 2 * x

使用\(x=10\)作为初始值，设\(\eta=0.2\)，使用梯度下降法迭代\(10\)次

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

import matplotlib.pyplot as plt

def gd(eta,f_grad):
    x = 10
    results = [x]
    for i in range(10):
        x -= eta * f_grad(x)
        results.append(float(x))
    print(f'epoch 10,x:{x:f}')
    return results

_trace_history = []

def show_trace(results, f, title=None, max_cols=3, reset=False, show=True):
    global _trace_history
    if reset:
        _trace_history = []

    _trace_history.append((results, f, title))

    if not show:
        return

    n = len(_trace_history)
    cols = min(max_cols, n)
    traces = _trace_history[-cols:]

    fig, axes = plt.subplots(1, cols, figsize=(4.8 * cols, 3.6))
    if cols == 1:
        axes = [axes]

    for i, (ax, (res, func, t)) in enumerate(zip(axes, traces), start=n - cols + 1):
        bound = max(abs(min(res)), abs(max(res)))
        f_line = torch.arange(-bound, bound, 0.01)
        x_line = f_line.numpy()
        y_line = [float(func(x)) for x in f_line]
        x_res = [float(x) for x in res]
        y_res = [float(func(x)) for x in res]

        ax.plot(x_line, y_line, '-')
        ax.plot(x_res, y_res, '-o')
        ax.set_xlabel('x')
        ax.set_ylabel('f(x)')
        ax.set_title(t if t is not None else f'第{i}次轨迹')
        ax.grid(alpha=0.3)

    plt.tight_layout()
    plt.show()

results = gd(0.2,f_grad)
show_trace(results, f, title='eta=0.2', reset=True)

epoch 10,x:7.295479

学习率决定目标函数能否收敛到最小值，以及决定收敛速度，学习率过低可能收敛过慢

1

show_trace(gd(0.05,f_grad), f, title='eta=0.05')

epoch 10,x:3.486784

学习率过高可能导致高阶项无法忽视导致发散

1

show_trace(gd(1.2,f_grad), f, title='eta=1.2')

epoch 10,x:289.254655

在非凸函数中，梯度下降并不保证找到全局最小值，它通常会收敛到“离初始点最近”的那个局部最小值或者鞍点

1
2
3
4
5
6
7
8
9

c = torch.tensor(0.15 * np.pi)
def f(x):
    return x * torch.cos(c * x)

def f_grad(x):
    return torch.cos(c * x) - c * x * torch.sin(c * x)

show_trace(gd(2,f_grad), f, title='non-convex eta=2', reset=True, show=False)
show_trace(gd(0.2,f_grad), f, title='non-convex eta=0.2')

epoch 10,x:-1.528166
epoch 10,x:7.295479

多元梯度下降 \(\pmb{x}\leftarrow \pmb{x}-\eta\nabla f(\pmb{x})\)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

def train_2d(trainer,steps=20,f_grad=None): #兼容后面，GD实际上没有用的s1,s2
    x1,x2,s1,s2 = -5,-2,0,0
    results = [(x1,x2)]
    for i in range(steps):
        if f_grad:
            x1,x2,s1,s2 = trainer(x1,x2,s1,s2,f_grad)
        else: #兼容后面
            x1,x2,s1,s2 = trainer(x1,x2,s1,s2)
        results.append((x1,x2))
    print(f'epoch{i+1}, x1:{float(x1):f}, x2:{float(x2):f}')
    return results

def show_trace_2d(f, results, title='2D optimization trace'):
    x1_vals, x2_vals = zip(*results)
    
    x1_min, x1_max = min(x1_vals), max(x1_vals)
    x2_min, x2_max = min(x2_vals), max(x2_vals)
    pad1 = max(1.0, (x1_max - x1_min) * 0.2)
    pad2 = max(1.0, (x2_max - x2_min) * 0.2)
    
    x1_grid = np.linspace(x1_min - pad1, x1_max + pad1, 200)
    x2_grid = np.linspace(x2_min - pad2, x2_max + pad2, 200)
    X1, X2 = np.meshgrid(x1_grid, x2_grid)
    Z = f(X1, X2)
    
    plt.figure(figsize=(6, 5))
    contours = plt.contour(X1, X2, Z, levels=20, cmap='viridis')
    plt.clabel(contours, inline=True, fontsize=8)
    
    plt.plot(x1_vals, x2_vals, '-o', color='tab:red', linewidth=2, markersize=4, label='trajectory')
    plt.scatter([x1_vals[0]], [x2_vals[0]], color='tab:blue', s=60, label='start')
    plt.scatter([x1_vals[-1]], [x2_vals[-1]], color='tab:green', s=60, label='end')
    
    plt.xlabel('x1')
    plt.ylabel('x2')
    plt.title(title)
    plt.legend()
    plt.grid(alpha=0.3)
    plt.tight_layout()
    plt.show()

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

def f_2d(x1, x2):
    return x1**2 + 2 * x2**2

def gd_2d(x1, x2, s1, s2, f_grad):
    eta = 0.1
    g1, g2 = f_grad(x1, x2)
    return x1 - eta * g1, x2 - eta * g2, 0, 0

def f_2d_grad(x1, x2):
    return 2 * x1, 4 * x2

res_2d = train_2d(gd_2d, steps=20, f_grad=f_2d_grad)
show_trace_2d(f_2d, res_2d, title='GD on f(x1,x2)=x1^2+2x2^2')

epoch20, x1:-0.057646, x2:-0.000073

学习率的选取决定学习的效果，一些自适应方法可能不能直接用于深度学习

随机梯度下降

普通的梯度下降的损失函数是所有样本的和

$$L(\theta) = \sum_{i=1}^{N} L_i(\theta)$$

每次参数更新都需要重新计算\(N\)个样本梯度值和

$$\theta = \theta - \eta \cdot \nabla \left( \sum_{i=1}^{N} L_i(\theta) \right) = \theta - \eta \cdot \sum_{i=1}^{N} \nabla L_i(\theta)$$

当\(N\)的规模过大时，普通梯度下降的时空复杂度可能难以接受

既然计算所有\(N\)个样本太慢，那每次更新时，只随机抽取一小部分样本（甚至只有一个样本）来计算损失函数和估算梯度，会发生什么？

假设我们在每次迭代 \(t\) 时，从全部数据中随机均匀采样一个大小为 \(|B|\) 的子集 \(B_t\)（其中 \(B_t \subset \{1, ..., N\}\)）。我们用这个子集的平均梯度来近似整体梯度：

$$\nabla L(\theta) \approx \frac{1}{|B|} \sum_{i \in B_t} \nabla L_i(\theta)$$

此时，参数更新公式变为：

$$\theta = \theta - \eta \cdot \frac{1}{|B|} \sum_{i \in B_t} \nabla L_i(\theta)$$

特别地，当 \(|B|=1\) 时，即每次只随机选一个样本 \(i\)，这就是最原始的随机梯度下降（SGD）：

$$\theta = \theta - \eta \cdot \nabla L_i(\theta)$$

那用部分估计整体靠谱吗？

$$E\left[ \frac{1}{|B|} \sum_{i \in B_t} \nabla L_i(\theta) \right] =\frac{1}{|B|} \sum_{i \in B_t}E\left[ \nabla L_i(\theta) \right] = \frac{1}{N} \sum_{i=1}^{N} E\left[ \nabla L_i(\theta) \right]= \frac{1}{N} \sum_{i=1}^{N} \nabla L_i(\theta) = \nabla L(\theta)$$

所以说随机梯度是对完整梯度的无偏估计

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

def sgd(x1,x2,s1,s2,f_grad):
    g1,g2 = f_grad(x1,x2)
    # 增加随机噪声，实际中只用部分样本计算的梯度自带噪声
    g1 += torch.normal(0.0,1,(1,))
    g2 += torch.normal(0.0,1,(1,))
    eta_t = eta *lr()
    return (x1-eta_t*g1,x2-eta_t*g2,0,0)

def constant_lr():
    return 1

eta = 0.1
lr = constant_lr
res_2d = train_2d(sgd, steps=50, f_grad=f_2d_grad)
show_trace_2d(f_2d, res_2d, title='GD on f(x1,x2)=x1^2+2x2^2')

epoch50, x1:-0.401927, x2:-0.046643

尽管迭代了\(50\)次，效果看起来不如普通的梯度下降，那么剩下能改变的就是学习率了，固定的学习率无法兼具“启动快（此处不是鸡煲笑话），收敛稳”的效果。

为了解决这个矛盾，我们将学习率从常数 \(\eta\) 变为关于迭代步数 \(t\) 的函数 \(\eta_t\)。 SGD 的更新公式演变为：

$$\theta_{t+1} = \theta_t - \eta_t \cdot \nabla L_i(\theta_t)$$

在实际应用中，我们通常使用以下几种调度方式：

策略公式示例特点
指数衰减\(\eta_t = \eta_0 \cdot \gamma^t\)学习率随步数指数级下降，衰减速度快
分段常数每 30 轮 \(\eta\) 除以 10实现简单，便于手动控制关键阶段的精度
多项式衰减\(\eta_t = \eta_0 \cdot (1 - \frac{t}{T})^k\)随训练进度平滑下降，常用于深度学习
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

import math

def exponential_lr():
    global t
    t += 1
    return math.exp(-0.1 * t)
t = 1
lr = exponential_lr
res_2d = train_2d(sgd, steps=50, f_grad=f_2d_grad)
show_trace_2d(f_2d, res_2d, title='GD on f(x1,x2)=x1^2+2x2^2')

epoch50, x1:-0.788887, x2:0.064546


1
2
3
4
5
6
7
8
9

def polynomial_lr():
    global t
    t += 1
    return (1 + 0.1 * t) ** (-0.5)

t = 1
lr = polynomial_lr
res_2d = train_2d(sgd, steps=50, f_grad=f_2d_grad)
show_trace_2d(f_2d, res_2d, title='GD on f(x1,x2)=x1^2+2x2^2')

epoch50, x1:0.108062, x2:0.041646

随机梯度下降只用一个样本进行更新，这也带来了劣势。首先是向量运算无法充分利用 GPU 的矩阵并行计算能力，其次是单样本梯度估计的方差较大，导致收敛路径震荡剧烈。为解决这两个问题，实际使用时通常用小批量随机梯度下降

单个样本的方差是

$$\text{Var}(\hat{g}) = \text{Var}(g_i) = \sigma^2$$

估计量是 \(m\) 个样本梯度的平均值

$$\hat{g}_{\text{m}} = \frac{1}{m} \sum_{j=1}^{m} g_{i_j}$$

要计算这个平均值的方差,需要利用方差的两个性质，假设样本独立同分布：

  1. \(\text{Var}(cX) = c^2 \text{Var}(X)\)
  2. 若 \(X, Y\) 独立，\(\text{Var}(X+Y) = \text{Var}(X) + \text{Var}(Y)\)

推导过程如下：

$$ \begin{aligned} \text{Var}(\hat{g}_{\text{m}}) &= \text{Var}\left( \frac{1}{m} \sum_{j=1}^{m} g_{i_j} \right) \\ &= \frac{1}{m^2} \text{Var}\left( \sum_{j=1}^{m} g_{i_j} \right) \quad \leftarrow \text{性质 1 } \\ &= \frac{1}{m^2} \sum_{j=1}^{m} \text{Var}(g_{i_j}) \quad \leftarrow \text{性质 2} \\ &= \frac{1}{m^2} \cdot m \cdot \sigma^2 \quad \leftarrow \text{共有 } m \text{ 个项，每项方差为 } \sigma^2 \\ &= \frac{\sigma^2}{m} \end{aligned} $$

所以说，当\(m\)增大时，梯度方差是降低的

动量法

AdaGrad算法

RMSProp算法

Adadelta算法

Adam算法