.. _sec_adadelta:

Adadelta
========


Adadelta は AdaGrad (:numref:`sec_adagrad`)
のもう一つの変種である。主な違いは、学習率が座標ごとに適応的に変化する度合いを小さくしている点にある。さらに、伝統的には、変化量そのものを将来の変化の較正に用いるため、学習率を持たない手法だとされている。このアルゴリズムは
:cite:t:`Zeiler.2012`
で提案された。ここまでの前節までのアルゴリズムの議論を踏まえると、かなり素直に理解できる。

アルゴリズム
------------

要するに、Adadelta は 2 つの状態変数を使う。\ :math:`\mathbf{s}_t`
は勾配の 2
次モーメントのリーキー平均を保持し、\ :math:`\Delta\mathbf{x}_t`
はモデル自体のパラメータ変化の 2
次モーメントのリーキー平均を保持する。なお、他の文献や実装との互換性のため、著者らの元の記法と命名をそのまま用いている（モメンタム、Adagrad、RMSProp、Adadelta
で同じ目的の変数を表すのに、わざわざ異なるギリシャ文字を使うべき実質的な理由はない）。

以下に Adadelta の技術的詳細を示す。ここでのパラメータを :math:`\rho`
とすると、 :numref:`sec_rmsprop` と同様に次のリーキー更新を得る。

.. math::

   \begin{aligned}
       \mathbf{s}_t & = \rho \mathbf{s}_{t-1} + (1 - \rho) \mathbf{g}_t^2.
   \end{aligned}

:numref:`sec_rmsprop` との違いは、再スケールした勾配
:math:`\mathbf{g}_t'` を用いて更新を行う点である。すなわち、

.. math::

   \begin{aligned}
       \mathbf{x}_t  & = \mathbf{x}_{t-1} - \mathbf{g}_t'. \\
   \end{aligned}

では、再スケールした勾配 :math:`\mathbf{g}_t'`
とは何だろうか。次のように計算できる。

.. math::

   \begin{aligned}
       \mathbf{g}_t' & = \frac{\sqrt{\Delta\mathbf{x}_{t-1} + \epsilon}}{\sqrt{{\mathbf{s}_t + \epsilon}}} \odot \mathbf{g}_t, \\
   \end{aligned}

ここで :math:`\Delta \mathbf{x}_{t-1}` は、再スケールした勾配
:math:`\mathbf{g}_t'`
の二乗のリーキー平均である。\ :math:`\Delta \mathbf{x}_{0}` を :math:`0`
に初期化し、各ステップで :math:`\mathbf{g}_t'`
を用いて更新する。すなわち、

.. math::

   \begin{aligned}
       \Delta \mathbf{x}_t & = \rho \Delta\mathbf{x}_{t-1} + (1 - \rho) {\mathbf{g}_t'}^2,
   \end{aligned}

また、数値安定性を保つために :math:`\epsilon`\ （\ :math:`10^{-5}`
のような小さな値）を加える。

実装
----

Adadelta では、各変数ごとに 2 つの状態変数 :math:`\mathbf{s}_t` と
:math:`\Delta\mathbf{x}_t`
を保持する必要がある。これにより、次の実装になる。



.. raw:: html

    <div class="mdl-tabs mdl-js-tabs mdl-js-ripple-effect"><div class="mdl-tabs__tab-bar "><a href="#pytorch-8de0ab08-0" onclick="tagClick('pytorch'); return false;" class="mdl-tabs__tab is-active">pytorch</a><a href="#mxnet-8de0ab08-1" onclick="tagClick('mxnet'); return false;" class="mdl-tabs__tab ">mxnet</a><a href="#jax-8de0ab08-2" onclick="tagClick('jax'); return false;" class="mdl-tabs__tab ">jax</a><a href="#tensorflow-8de0ab08-3" onclick="tagClick('tensorflow'); return false;" class="mdl-tabs__tab ">tensorflow</a></div>



.. raw:: html

    <div class="mdl-tabs__panel is-active" id="pytorch-8de0ab08-0">

.. raw:: latex

   \diilbookstyleinputcell

.. code:: python

    %matplotlib inline
    from d2l import torch as d2l
    import torch
    
    def init_adadelta_states(feature_dim):
        s_w, s_b = d2l.zeros((feature_dim, 1)), d2l.zeros(1)
        delta_w, delta_b = d2l.zeros((feature_dim, 1)), d2l.zeros(1)
        return ((s_w, delta_w), (s_b, delta_b))
    
    def adadelta(params, states, hyperparams):
        rho, eps = hyperparams['rho'], 1e-5
        for p, (s, delta) in zip(params, states):
            with torch.no_grad():
                # In-place updates via [:]
                s[:] = rho * s + (1 - rho) * torch.square(p.grad)
                g = (torch.sqrt(delta + eps) / torch.sqrt(s + eps)) * p.grad
                p[:] -= g
                delta[:] = rho * delta + (1 - rho) * g * g
            p.grad.data.zero_()



.. raw:: html

    </div>



.. raw:: html

    <div class="mdl-tabs__panel " id="mxnet-8de0ab08-1">

.. raw:: latex

   \diilbookstyleinputcell

.. code:: python

    %matplotlib inline
    from d2l import mxnet as d2l
    from mxnet import np, npx
    npx.set_np()
    
    def init_adadelta_states(feature_dim):
        s_w, s_b = d2l.zeros((feature_dim, 1)), d2l.zeros(1)
        delta_w, delta_b = d2l.zeros((feature_dim, 1)), d2l.zeros(1)
        return ((s_w, delta_w), (s_b, delta_b))
    
    def adadelta(params, states, hyperparams):
        rho, eps = hyperparams['rho'], 1e-5
        for p, (s, delta) in zip(params, states):
            # In-place updates via [:]
            s[:] = rho * s + (1 - rho) * np.square(p.grad)
            g = (np.sqrt(delta + eps) / np.sqrt(s + eps)) * p.grad
            p[:] -= g
            delta[:] = rho * delta + (1 - rho) * g * g



.. raw:: html

    </div>



.. raw:: html

    <div class="mdl-tabs__panel " id="jax-8de0ab08-2">

.. raw:: latex

   \diilbookstyleinputcell

.. code:: python

    data_iter, feature_dim = d2l.get_data_ch11(batch_size=10)
    d2l.train_ch11(adadelta, init_adadelta_states(feature_dim),
                   {'rho': 0.9}, data_iter, feature_dim);



.. raw:: html

    </div>



.. raw:: html

    <div class="mdl-tabs__panel " id="tensorflow-8de0ab08-3">

.. raw:: latex

   \diilbookstyleinputcell

.. code:: python

    %matplotlib inline
    from d2l import tensorflow as d2l
    import tensorflow as tf
    
    def init_adadelta_states(feature_dim):
        s_w = tf.Variable(d2l.zeros((feature_dim, 1)))
        s_b = tf.Variable(d2l.zeros(1))
        delta_w = tf.Variable(d2l.zeros((feature_dim, 1)))
        delta_b = tf.Variable(d2l.zeros(1))
        return ((s_w, delta_w), (s_b, delta_b))
    
    def adadelta(params, grads, states, hyperparams):
        rho, eps = hyperparams['rho'], 1e-5
        for p, (s, delta), grad in zip(params, states, grads):
            s[:].assign(rho * s + (1 - rho) * tf.math.square(grad))
            g = (tf.math.sqrt(delta + eps) / tf.math.sqrt(s + eps)) * grad
            p[:].assign(p - g)
            delta[:].assign(rho * delta + (1 - rho) * g * g)



.. raw:: html

    </div>



.. raw:: html

    </div>

:math:`\rho = 0.9` を選ぶと、各パラメータ更新の半減期は 10
になる。これはかなりうまく機能する傾向がある。結果は次のようになる。

.. raw:: latex

   \diilbookstyleinputcell

.. code:: python

    data_iter, feature_dim = d2l.get_data_ch11(batch_size=10)
    d2l.train_ch11(adadelta, init_adadelta_states(feature_dim),
                   {'rho': 0.9}, data_iter, feature_dim);


.. raw:: latex

   \diilbookstyleoutputcell

.. parsed-literal::
    :class: output

    loss: 0.244, 0.151 sec/epoch



.. figure:: output_adadelta_379e43_16_1.svg


簡潔な実装としては、高レベル API の Adadelta
アルゴリズムをそのまま使う。これにより、より簡潔な呼び出しを 1
行で書ける。



.. raw:: html

    <div class="mdl-tabs mdl-js-tabs mdl-js-ripple-effect"><div class="mdl-tabs__tab-bar "><a href="#pytorch-c85b91ad-0" onclick="tagClick('pytorch'); return false;" class="mdl-tabs__tab is-active">pytorch</a><a href="#mxnet-c85b91ad-1" onclick="tagClick('mxnet'); return false;" class="mdl-tabs__tab ">mxnet</a><a href="#tensorflow-c85b91ad-2" onclick="tagClick('tensorflow'); return false;" class="mdl-tabs__tab ">tensorflow</a></div>



.. raw:: html

    <div class="mdl-tabs__panel is-active" id="pytorch-c85b91ad-0">

.. raw:: latex

   \diilbookstyleinputcell

.. code:: python

    trainer = torch.optim.Adadelta
    d2l.train_concise_ch11(trainer, {'rho': 0.9}, data_iter)


.. raw:: latex

   \diilbookstyleoutputcell

.. parsed-literal::
    :class: output

    loss: 0.243, 0.121 sec/epoch



.. figure:: output_adadelta_379e43_20_1.svg




.. raw:: html

    </div>



.. raw:: html

    <div class="mdl-tabs__panel " id="mxnet-c85b91ad-1">

.. raw:: latex

   \diilbookstyleinputcell

.. code:: python

    d2l.train_concise_ch11('adadelta', {'rho': 0.9}, data_iter)


.. raw:: latex

   \diilbookstyleoutputcell

.. parsed-literal::
    :class: output

    loss: 0.242, 0.789 sec/epoch



.. figure:: output_adadelta_379e43_23_1.svg




.. raw:: html

    </div>



.. raw:: html

    <div class="mdl-tabs__panel " id="tensorflow-c85b91ad-2">

.. raw:: latex

   \diilbookstyleinputcell

.. code:: python

    # adadelta is not converging at default learning rate
    # but it is converging at lr = 5.0
    trainer = tf.keras.optimizers.Adadelta
    d2l.train_concise_ch11(trainer, {'learning_rate':5.0, 'rho': 0.9}, data_iter)


.. raw:: latex

   \diilbookstyleoutputcell

.. parsed-literal::
    :class: output

    loss: 0.245, 1.584 sec/epoch



.. figure:: output_adadelta_379e43_26_1.svg




.. raw:: html

    </div>



.. raw:: html

    </div>

まとめ
------

-  Adadelta
   には学習率パラメータがない。その代わりに、パラメータの変化率そのものを用いて学習率を適応させる。
-  Adadelta では、勾配とパラメータ変化の 2 次モーメントを保存するために
   2 つの状態変数が必要である。
-  Adadelta はリーキー平均を用いて、適切な統計量の逐次推定を維持する。

演習
----

1. :math:`\rho` の値を調整してみよ。何が起こるか。
2. :math:`\mathbf{g}_t'`
   を使わずにアルゴリズムを実装する方法を示せ。なぜそれがよい考えなのか。
3. Adadelta は本当に学習率不要なのか。Adadelta
   を破綻させる最適化問題を見つけられるか。
4. Adadelta と Adagrad、RMS prop
   を比較し、それらの収束挙動について議論せよ。