11.6 Momentum
在 Section 11.4 中，我们提到，目标函数有关自变量的梯度代表了目标函数在自变量当前位置下降最快的方向。因此，梯度下降也叫作最陡下降（steepest descent）。在每次迭代中，梯度下降根据自变量当前位置，沿着当前位置的梯度更新自变量。然而，如果自变量的迭代方向仅仅取决于自变量当前位置，这可能会带来一些问题。对于noisy gradient,我们需要谨慎的选取学习率和batch size, 来控制梯度方差和收敛的结果。
An ill-conditioned Problem
Condition Number of Hessian Matrix:
where 
is the maximum amd minimum eignvalue of Hessian matrix.
让我们考虑一个输入和输出分别为二维向量
和标量的目标函数:
Maximum Learning Rate
- For
, according to convex optimizaiton conclusions, we need step size 
. - To guarantee the convergence, we need to have
.
Supp: Preconditioning
在二阶优化中，我们使用Hessian matrix的逆矩阵(或者pseudo inverse)来左乘梯度向量 
，这样的做法称为precondition，相当于将 
映射为一个单位矩阵，拥有分布均匀的Spectrum，也即我们去优化的等价标函数的Hessian matrix为良好的identity matrix。
与Section 11.4一节中不同，这里将
系数从
减小到了
。下面实现基于这个目标函数的梯度下降，并演示使用学习率为
时自变量的迭代轨迹。
%matplotlib inline import sys sys.path.append("/home/kesci/input") import d2lzh1981 as d2l import torch eta = 0.4 def f_2d(x1, x2): return 0.1 * x1 ** 2 + 2 * x2 ** 2 def gd_2d(x1, x2, s1, s2): return (x1 - eta * 0.2 * x1, x2 - eta * 4 * x2, 0, 0) d2l.show_trace_2d(f_2d, d2l.train_2d(gd_2d))
epoch 20, x1 -0.943467, x2 -0.000073
可以看到，同一位置上，目标函数在竖直方向（
轴方向）比在水平方向（
轴方向）的斜率的绝对值更大。因此，给定学习率，梯度下降迭代自变量时会使自变量在竖直方向比在水平方向移动幅度更大。那么，我们需要一个较小的学习率从而避免自变量在竖直方向上越过目标函数最优解。然而，这会造成自变量在水平方向上朝最优解移动变慢。
下面我们试着将学习率调得稍大一点，此时自变量在竖直方向不断越过最优解并逐渐发散。
Solution to ill-condition
- Preconditioning gradient vector: applied in Adam, RMSProp, AdaGrad, Adelta, KFC, Natural gradient and other secord-order optimization algorithms.
- Averaging history gradient: like momentum, which allows larger learning rates to accelerate convergence; applied in Adam, RMSProp, SGD momentum.
eta = 0.6 d2l.show_trace_2d(f_2d, d2l.train_2d(gd_2d))
epoch 20, x1 -0.387814, x2 -1673.365109
Momentum Algorithm
动量法的提出是为了解决梯度下降的上述问题。设时间步 
的自变量为 
，学习率为 
。
在时间步 
，动量法创建速度变量 
，并将其元素初始化成 0。在时间步 
，动量法对每次迭代的步骤做如下修改：
Another version:
其中，动量超参数 
满足 
。当 
时，动量法等价于小批量随机梯度下降。
在解释动量法的数学原理前，让我们先从实验中观察梯度下降在使用动量法后的迭代轨迹。
def momentum_2d(x1, x2, v1, v2): v1 = beta * v1 + eta * 0.2 * x1 v2 = beta * v2 + eta * 4 * x2 return x1 - v1, x2 - v2, v1, v2 eta, beta = 0.4, 0.5 d2l.show_trace_2d(f_2d, d2l.train_2d(momentum_2d))
epoch 20, x1 -0.062843, x2 0.001202
可以看到使用较小的学习率 
和动量超参数 
时，动量法在竖直方向上的移动更加平滑，且在水平方向上更快逼近最优解。下面使用较大的学习率 
，此时自变量也不再发散。
eta = 0.6 d2l.show_trace_2d(f_2d, d2l.train_2d(momentum_2d))
epoch 20, x1 0.007188, x2 0.002553
Exponential Moving Average
为了从数学上理解动量法，让我们先解释一下指数加权移动平均（exponential moving average）。给定超参数 
，当前时间步 
的变量 
是上一时间步 
的变量 
和当前时间步另一变量 
的线性组合：
我们可以对 
展开：
Supp
Approximate Average of 
Steps
令 
，那么 
。因为
所以当 
时，
，如 
。如果把 
当作一个比较小的数，我们可以在近似中忽略所有含 
和比 
更高阶的系数的项。例如，当 
时，
因此，在实际中，我们常常将 
看作是对最近 
个时间步的 
值的加权平均。例如，当 
时，
可以被看作对最近20个时间步的 
值的加权平均；当 
时，
可以看作是对最近10个时间步的 
值的加权平均。而且，离当前时间步 
越近的 
值获得的权重越大（越接近1）。
由指数加权移动平均理解动量法
现在，我们对动量法的速度变量做变形：
Another version:
由指数加权移动平均的形式可得，速度变量 
实际上对序列 
做了指数加权移动平均。换句话说，相比于小批量随机梯度下降，动量法在每个时间步的自变量更新量近似于将前者对应的最近 
个时间步的更新量做了指数加权移动平均后再除以 
。所以，在动量法中，自变量在各个方向上的移动幅度不仅取决当前梯度，还取决于过去的各个梯度在各个方向上是否一致。在本节之前示例的优化问题中，所有梯度在水平方向上为正（向右），而在竖直方向上时正（向上）时负（向下）。这样，我们就可以使用较大的学习率，从而使自变量向最优解更快移动。
Implement
相对于小批量随机梯度下降，动量法需要对每一个自变量维护一个同它一样形状的速度变量，且超参数里多了动量超参数。实现中，我们将速度变量用更广义的状态变量states表示。
def get_data_ch7(): data = np.genfromtxt('/home/kesci/input/airfoil4755/airfoil_self_noise.dat', delimiter='\t') data = (data - data.mean(axis=0)) / data.std(axis=0) return torch.tensor(data[:1500, :-1], dtype=torch.float32), \ torch.tensor(data[:1500, -1], dtype=torch.float32) features, labels = get_data_ch7() def init_momentum_states(): v_w = torch.zeros((features.shape[1], 1), dtype=torch.float32) v_b = torch.zeros(1, dtype=torch.float32) return (v_w, v_b) def sgd_momentum(params, states, hyperparams): for p, v in zip(params, states): v.data = hyperparams['momentum'] * v.data + hyperparams['lr'] * p.grad.data p.data -= v.data
我们先将动量超参数momentum设0.5
d2l.train_ch7(sgd_momentum, init_momentum_states(), {'lr': 0.02, 'momentum': 0.5}, features, labels)
loss: 0.243297, 0.057950 sec per epoch
将动量超参数momentum增大到0.9
d2l.train_ch7(sgd_momentum, init_momentum_states(), {'lr': 0.02, 'momentum': 0.9}, features, labels)
loss: 0.260418, 0.059441 sec per epoch
可见目标函数值在后期迭代过程中的变化不够平滑。直觉上，10倍小批量梯度比2倍小批量梯度大了5倍，我们可以试着将学习率减小到原来的1/5。此时目标函数值在下降了一段时间后变化更加平滑。
d2l.train_ch7(sgd_momentum, init_momentum_states(), {'lr': 0.004, 'momentum': 0.9}, features, labels)
loss: 0.243650, 0.063532 sec per epoch
Pytorch Class
在Pytorch中，torch.optim.SGD已实现了Momentum。
d2l.train_pytorch_ch7(torch.optim.SGD, {'lr': 0.004, 'momentum': 0.9}, features, labels)
loss: 0.243692, 0.048604 sec per epoch
<img src="https://cdn.kesci.com/rt_upload/061E57E1FC1240988C134FC43E749BEE/q5qodoy8py.svg">
