.. _sec_momentum:
モメンタム
==========
:numref:`sec_sgd`
では、確率的勾配降下法を行うとき、すなわち勾配のノイズを含む変種しか利用できない最適化を行うときに何が起こるかを復習した。特に、ノイズのある勾配では、ノイズに直面したときの学習率の選び方にいっそう注意が必要であることに気づいた。これを急激に下げすぎると、収束が止まってしまう。逆に寛大すぎると、ノイズが最適解から私たちを押し戻し続けるため、十分によい解に収束できない。
基礎
----
この節では、実際によく現れるある種の最適化問題に対して、より効果的な最適化アルゴリズムを探る。
漏れのある平均
~~~~~~~~~~~~~~
前節では、計算を高速化する手段としてミニバッチSGDについて議論した。また、勾配を平均することで分散が減るといううれしい副作用もあった。ミニバッチ確率的勾配降下法は次のように計算できる。
.. math::
\mathbf{g}_{t, t-1} = \partial_{\mathbf{w}} \frac{1}{|\mathcal{B}_t|} \sum_{i \in \mathcal{B}_t} f(\mathbf{x}_{i}, \mathbf{w}_{t-1}) = \frac{1}{|\mathcal{B}_t|} \sum_{i \in \mathcal{B}_t} \mathbf{h}_{i, t-1}.
記法を簡単にするため、ここでは
:math:`\mathbf{h}_{i, t-1} = \partial_{\mathbf{w}} f(\mathbf{x}_i, \mathbf{w}_{t-1})`
を、時刻 :math:`t-1` に更新された重みを用いたサンプル :math:`i`
の確率的勾配降下法として用いた。ミニバッチ上で勾配を平均すること以上に、分散低減の効果を活かせたら理想的である。この目的を達成する一つの方法は、勾配計算を「漏れのある平均」に置き換えることである。
.. math:: \mathbf{v}_t = \beta \mathbf{v}_{t-1} + \mathbf{g}_{t, t-1}
ここで :math:`\beta \in (0, 1)`
とする。これは実質的に、その時点の勾配を複数の\ *過去*\ の勾配で平均したものに置き換えることを意味する。\ :math:`\mathbf{v}`
は\ *速度*\ と呼ばれる。これは、重い球が目的関数の地形を転がり落ちるときに過去の力を積分するのと同様に、過去の勾配を蓄積する。何が起きているかをより詳しく見るために、\ :math:`\mathbf{v}_t`
を再帰的に展開すると
.. math::
\begin{aligned}
\mathbf{v}_t = \beta^2 \mathbf{v}_{t-2} + \beta \mathbf{g}_{t-1, t-2} + \mathbf{g}_{t, t-1}
= \ldots, = \sum_{\tau = 0}^{t-1} \beta^{\tau} \mathbf{g}_{t-\tau, t-\tau-1}.
\end{aligned}
:math:`\beta`
が大きいと長い範囲の平均になり、小さいと勾配法に対するわずかな補正にとどまる。新しい勾配の置き換えは、もはや特定の1回の勾配降下で最急降下方向を指すのではなく、過去の勾配の重み付き平均の方向を指す。これにより、実際にその上で勾配を計算するコストを払わずに、バッチで平均することの利点の大部分を実現できる。この平均化手続きについては、後でさらに詳しく見直す。
上の考え方は、現在では\ *加速*\ 勾配法として知られる手法、たとえばモメンタム付き勾配法の基礎となった。これらは、最適化問題が悪条件である場合、すなわちある方向では他の方向より進みがずっと遅く、細い峡谷のように見える場合に、はるかに効果的であるという追加の利点を持つ。さらに、連続する勾配を平均することで、より安定した降下方向を得られる。実際、ノイズのない凸問題であっても加速が効くという点は、モメンタムが機能する重要な理由の一つであり、また非常によく効く理由でもある。
予想されるように、その有効性ゆえにモメンタムは深層学習およびそれ以外の最適化でも広く研究されている。詳細な解析と対話的アニメーションについては、たとえば
:cite:t:`Goh.2017`
による美しい\ `解説記事 `__\ を参照されたい。これは
:cite:t:`Polyak.1964` によって提案された。:cite:t:`Nesterov.2018`
には、凸最適化の文脈での詳細な理論的議論がある。深層学習におけるモメンタムが有益であることは、以前から知られている。詳細は、たとえば
:cite:t:`Sutskever.Martens.Dahl.ea.2013` の議論を参照されたい。
悪条件の問題
~~~~~~~~~~~~
モメンタム法の幾何学的性質をよりよく理解するために、勾配降下法を再び取り上げる。ただし、今回はかなり扱いにくい目的関数を用いる。
:numref:`sec_gd` では
:math:`f(\mathbf{x}) = x_1^2 + 2 x_2^2`\ 、すなわち中程度に歪んだ楕円体の目的関数を用いたことを思い出そう。ここでは、この関数を
:math:`x_1` 方向に引き伸ばすことでさらに歪める。
.. math:: f(\mathbf{x}) = 0.1 x_1^2 + 2 x_2^2.
前と同様に、\ :math:`f` の最小値は :math:`(0, 0)` にある。この関数は
:math:`x_1`
方向では\ *非常に*\ 平坦である。では、この新しい関数に対して前と同じように勾配降下法を行うと何が起こるか見てみよう。学習率は
:math:`0.4` とする。
.. raw:: html
.. raw:: html
.. raw:: latex
\diilbookstyleinputcell
.. code:: python
%matplotlib inline
from d2l import torch 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))
.. raw:: latex
\diilbookstyleoutputcell
.. parsed-literal::
:class: output
epoch 20, x1: -0.943467, x2: -0.000073
.. figure:: output_momentum_589405_3_1.svg
.. raw:: html
.. raw:: html
.. raw:: latex
\diilbookstyleinputcell
.. code:: python
%matplotlib inline
from d2l import mxnet as d2l
from mxnet import np, npx
npx.set_np()
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))
.. raw:: latex
\diilbookstyleoutputcell
.. parsed-literal::
:class: output
epoch 20, x1: -0.943467, x2: -0.000073
[07:15:33] ../src/storage/storage.cc:196: Using Pooled (Naive) StorageManager for CPU
.. figure:: output_momentum_589405_6_1.svg
.. raw:: html
.. raw:: html
.. raw:: latex
\diilbookstyleinputcell
.. code:: python
eta = 0.6
d2l.show_trace_2d(f_2d, d2l.train_2d(gd_2d))
.. raw:: html
.. raw:: html
.. raw:: latex
\diilbookstyleinputcell
.. code:: python
%matplotlib inline
from d2l import tensorflow as d2l
import tensorflow as tf
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))
.. raw:: latex
\diilbookstyleoutputcell
.. parsed-literal::
:class: output
epoch 20, x1: -0.943467, x2: -0.000073
.. figure:: output_momentum_589405_12_1.svg
.. raw:: html
.. raw:: html
.. raw:: html
.. raw:: latex
\diilbookstyleinputcell
.. code:: python
eta = 0.6
d2l.show_trace_2d(f_2d, d2l.train_2d(gd_2d))
.. raw:: latex
\diilbookstyleoutputcell
.. parsed-literal::
:class: output
epoch 20, x1: -0.387814, x2: -1673.365109
.. figure:: output_momentum_589405_18_1.svg
.. raw:: html
.. raw:: html
.. raw:: latex
\diilbookstyleinputcell
.. code:: python
eta = 0.6
d2l.show_trace_2d(f_2d, d2l.train_2d(gd_2d))
.. raw:: latex
\diilbookstyleoutputcell
.. parsed-literal::
:class: output
epoch 20, x1: -0.387814, x2: -1673.365109
.. figure:: output_momentum_589405_21_1.svg
.. raw:: html
.. raw:: html
.. raw:: latex
\diilbookstyleinputcell
.. code:: python
def momentum_2d(x1, x2, v1, v2):
v1 = beta * v1 + 0.2 * x1
v2 = beta * v2 + 4 * x2
return x1 - eta * v1, x2 - eta * v2, v1, v2
eta, beta = 0.6, 0.5
d2l.show_trace_2d(f_2d, d2l.train_2d(momentum_2d))
.. raw:: html
.. raw:: html
.. raw:: latex
\diilbookstyleinputcell
.. code:: python
eta = 0.6
d2l.show_trace_2d(f_2d, d2l.train_2d(gd_2d))
.. raw:: latex
\diilbookstyleoutputcell
.. parsed-literal::
:class: output
epoch 20, x1: -0.387814, x2: -1673.365109
.. figure:: output_momentum_589405_27_1.svg
.. raw:: html
.. raw:: html
.. raw:: html
.. raw:: latex
\diilbookstyleinputcell
.. code:: python
def momentum_2d(x1, x2, v1, v2):
v1 = beta * v1 + 0.2 * x1
v2 = beta * v2 + 4 * x2
return x1 - eta * v1, x2 - eta * v2, v1, v2
eta, beta = 0.6, 0.5
d2l.show_trace_2d(f_2d, d2l.train_2d(momentum_2d))
.. raw:: latex
\diilbookstyleoutputcell
.. parsed-literal::
:class: output
epoch 20, x1: 0.007188, x2: 0.002553
.. figure:: output_momentum_589405_33_1.svg
.. raw:: html
.. raw:: html
.. raw:: latex
\diilbookstyleinputcell
.. code:: python
def momentum_2d(x1, x2, v1, v2):
v1 = beta * v1 + 0.2 * x1
v2 = beta * v2 + 4 * x2
return x1 - eta * v1, x2 - eta * v2, v1, v2
eta, beta = 0.6, 0.5
d2l.show_trace_2d(f_2d, d2l.train_2d(momentum_2d))
.. raw:: latex
\diilbookstyleoutputcell
.. parsed-literal::
:class: output
epoch 20, x1: 0.007188, x2: 0.002553
.. figure:: output_momentum_589405_36_1.svg
.. raw:: html
.. raw:: html
.. raw:: latex
\diilbookstyleinputcell
.. code:: python
eta, beta = 0.6, 0.25
d2l.show_trace_2d(f_2d, d2l.train_2d(momentum_2d))
.. raw:: html
.. raw:: html
.. raw:: latex
\diilbookstyleinputcell
.. code:: python
def momentum_2d(x1, x2, v1, v2):
v1 = beta * v1 + 0.2 * x1
v2 = beta * v2 + 4 * x2
return x1 - eta * v1, x2 - eta * v2, v1, v2
eta, beta = 0.6, 0.5
d2l.show_trace_2d(f_2d, d2l.train_2d(momentum_2d))
.. raw:: latex
\diilbookstyleoutputcell
.. parsed-literal::
:class: output
epoch 20, x1: 0.007188, x2: 0.002553
.. figure:: output_momentum_589405_42_1.svg
.. raw:: html
.. raw:: html
.. raw:: html
.. raw:: latex
\diilbookstyleinputcell
.. code:: python
eta, beta = 0.6, 0.25
d2l.show_trace_2d(f_2d, d2l.train_2d(momentum_2d))
.. raw:: latex
\diilbookstyleoutputcell
.. parsed-literal::
:class: output
epoch 20, x1: -0.126340, x2: -0.186632
.. figure:: output_momentum_589405_48_1.svg
.. raw:: html
.. raw:: html
.. raw:: latex
\diilbookstyleinputcell
.. code:: python
eta, beta = 0.6, 0.25
d2l.show_trace_2d(f_2d, d2l.train_2d(momentum_2d))
.. raw:: latex
\diilbookstyleoutputcell
.. parsed-literal::
:class: output
epoch 20, x1: -0.126340, x2: -0.186632
.. figure:: output_momentum_589405_51_1.svg
.. raw:: html
.. raw:: html
.. raw:: latex
\diilbookstyleinputcell
.. code:: python
d2l.set_figsize()
betas = [0.95, 0.9, 0.6, 0]
for beta in betas:
x = d2l.numpy(d2l.arange(40))
d2l.plt.plot(x, beta ** x, label=f'beta = {beta:.2f}')
d2l.plt.xlabel('time')
d2l.plt.legend();
.. raw:: html
.. raw:: html
.. raw:: latex
\diilbookstyleinputcell
.. code:: python
eta, beta = 0.6, 0.25
d2l.show_trace_2d(f_2d, d2l.train_2d(momentum_2d))
.. raw:: latex
\diilbookstyleoutputcell
.. parsed-literal::
:class: output
epoch 20, x1: -0.126340, x2: -0.186632
.. figure:: output_momentum_589405_57_1.svg
.. raw:: html
.. raw:: html
.. raw:: html
.. raw:: latex
\diilbookstyleinputcell
.. code:: python
d2l.set_figsize()
betas = [0.95, 0.9, 0.6, 0]
for beta in betas:
x = d2l.numpy(d2l.arange(40))
d2l.plt.plot(x, beta ** x, label=f'beta = {beta:.2f}')
d2l.plt.xlabel('time')
d2l.plt.legend();
.. figure:: output_momentum_589405_63_0.svg
.. raw:: html
.. raw:: html
.. raw:: latex
\diilbookstyleinputcell
.. code:: python
d2l.set_figsize()
betas = [0.95, 0.9, 0.6, 0]
for beta in betas:
x = d2l.numpy(d2l.arange(40))
d2l.plt.plot(x, beta ** x, label=f'beta = {beta:.2f}')
d2l.plt.xlabel('time')
d2l.plt.legend();
.. figure:: output_momentum_589405_66_0.svg
.. raw:: html
.. raw:: html
.. raw:: latex
\diilbookstyleinputcell
.. code:: python
def train_momentum(lr, momentum, num_epochs=2):
d2l.train_ch11(sgd_momentum, init_momentum_states(feature_dim),
{'lr': lr, 'momentum': momentum}, data_iter,
feature_dim, num_epochs)
data_iter, feature_dim = d2l.get_data_ch11(batch_size=10)
train_momentum(0.02, 0.5)
.. raw:: html
.. raw:: html
.. raw:: latex
\diilbookstyleinputcell
.. code:: python
d2l.set_figsize()
betas = [0.95, 0.9, 0.6, 0]
for beta in betas:
x = d2l.numpy(d2l.arange(40))
d2l.plt.plot(x, beta ** x, label=f'beta = {beta:.2f}')
d2l.plt.xlabel('time')
d2l.plt.legend();
.. figure:: output_momentum_589405_72_0.svg
.. raw:: html
.. raw:: html
.. raw:: html
.. raw:: latex
\diilbookstyleinputcell
.. code:: python
def init_momentum_states(feature_dim):
v_w = d2l.zeros((feature_dim, 1))
v_b = d2l.zeros(1)
return (v_w, v_b)
.. raw:: html
.. raw:: html
.. raw:: latex
\diilbookstyleinputcell
.. code:: python
def init_momentum_states(feature_dim):
v_w = d2l.zeros((feature_dim, 1))
v_b = d2l.zeros(1)
return (v_w, v_b)
.. raw:: html
.. raw:: html
.. raw:: latex
\diilbookstyleinputcell
.. code:: python
train_momentum(0.01, 0.9)
.. raw:: html
.. raw:: html
.. raw:: latex
\diilbookstyleinputcell
.. code:: python
def init_momentum_states(features_dim):
v_w = tf.Variable(d2l.zeros((features_dim, 1)))
v_b = tf.Variable(d2l.zeros(1))
return (v_w, v_b)
.. raw:: html
.. raw:: html
.. raw:: html
.. raw:: latex
\diilbookstyleinputcell
.. code:: python
def sgd_momentum(params, states, hyperparams):
for p, v in zip(params, states):
with torch.no_grad():
v[:] = hyperparams['momentum'] * v + p.grad
p[:] -= hyperparams['lr'] * v
p.grad.data.zero_()
.. raw:: html
.. raw:: html
.. raw:: latex
\diilbookstyleinputcell
.. code:: python
def sgd_momentum(params, states, hyperparams):
for p, v in zip(params, states):
v[:] = hyperparams['momentum'] * v + p.grad
p[:] -= hyperparams['lr'] * v
.. raw:: html
.. raw:: html
.. raw:: latex
\diilbookstyleinputcell
.. code:: python
train_momentum(0.005, 0.9)
.. raw:: html
.. raw:: html
.. raw:: latex
\diilbookstyleinputcell
.. code:: python
def sgd_momentum(params, grads, states, hyperparams):
for p, v, g in zip(params, states, grads):
v[:].assign(hyperparams['momentum'] * v + g)
p[:].assign(p - hyperparams['lr'] * v)
.. raw:: html
.. raw:: html
.. raw:: html
.. raw:: latex
\diilbookstyleinputcell
.. code:: python
def train_momentum(lr, momentum, num_epochs=2):
d2l.train_ch11(sgd_momentum, init_momentum_states(feature_dim),
{'lr': lr, 'momentum': momentum}, data_iter,
feature_dim, num_epochs)
data_iter, feature_dim = d2l.get_data_ch11(batch_size=10)
train_momentum(0.02, 0.5)
.. raw:: latex
\diilbookstyleoutputcell
.. parsed-literal::
:class: output
loss: 0.246, 0.168 sec/epoch
.. figure:: output_momentum_589405_107_1.svg
.. raw:: html
.. raw:: html
.. raw:: latex
\diilbookstyleinputcell
.. code:: python
def train_momentum(lr, momentum, num_epochs=2):
d2l.train_ch11(sgd_momentum, init_momentum_states(feature_dim),
{'lr': lr, 'momentum': momentum}, data_iter,
feature_dim, num_epochs)
data_iter, feature_dim = d2l.get_data_ch11(batch_size=10)
train_momentum(0.02, 0.5)
.. raw:: latex
\diilbookstyleoutputcell
.. parsed-literal::
:class: output
loss: 0.243, 1.227 sec/epoch
.. figure:: output_momentum_589405_110_1.svg
.. raw:: html
.. raw:: html
.. raw:: latex
\diilbookstyleinputcell
.. code:: python
lambdas = [0.1, 1, 10, 19]
eta = 0.1
d2l.set_figsize((6, 4))
for lam in lambdas:
t = d2l.numpy(d2l.arange(20))
d2l.plt.plot(t, (1 - eta * lam) ** t, label=f'lambda = {lam:.2f}')
d2l.plt.xlabel('time')
d2l.plt.legend();
.. raw:: html
.. raw:: html
.. raw:: latex
\diilbookstyleinputcell
.. code:: python
def train_momentum(lr, momentum, num_epochs=2):
d2l.train_ch11(sgd_momentum, init_momentum_states(feature_dim),
{'lr': lr, 'momentum': momentum}, data_iter,
feature_dim, num_epochs)
data_iter, feature_dim = d2l.get_data_ch11(batch_size=10)
train_momentum(0.02, 0.5)
.. raw:: latex
\diilbookstyleoutputcell
.. parsed-literal::
:class: output
loss: 0.243, 1.148 sec/epoch
.. figure:: output_momentum_589405_116_1.svg
.. raw:: html
.. raw:: html
.. raw:: html
.. raw:: latex
\diilbookstyleinputcell
.. code:: python
trainer = torch.optim.SGD
d2l.train_concise_ch11(trainer, {'lr': 0.005, 'momentum': 0.9}, data_iter)
.. raw:: latex
\diilbookstyleoutputcell
.. parsed-literal::
:class: output
loss: 0.249, 0.130 sec/epoch
.. figure:: output_momentum_589405_126_1.svg
.. raw:: html
.. raw:: html
.. raw:: latex
\diilbookstyleinputcell
.. code:: python
d2l.train_concise_ch11('sgd', {'learning_rate': 0.005, 'momentum': 0.9},
data_iter)
.. raw:: latex
\diilbookstyleoutputcell
.. parsed-literal::
:class: output
loss: 0.244, 0.887 sec/epoch
.. figure:: output_momentum_589405_129_1.svg
.. raw:: html
.. raw:: html
.. raw:: latex
\diilbookstyleinputcell
.. code:: python
trainer = tf.keras.optimizers.SGD
d2l.train_concise_ch11(trainer, {'learning_rate': 0.005, 'momentum': 0.9},
data_iter)
.. raw:: latex
\diilbookstyleoutputcell
.. parsed-literal::
:class: output
loss: 0.247, 1.224 sec/epoch
.. figure:: output_momentum_589405_132_1.svg
.. raw:: html
.. raw:: html