2fa312de3ed3518b7e60.md

title	tags	author	slide
Hamiltonian Descent Methods を chainer で実装した	機械学習 Python Chainer	omi_UT	false

本記事では Hamiltonian Descent Methods を実装して動かすところまでをします。 GitHub レポジトリ

続きました

Hamiltonian Descent Methods (HDMs) とは

2018 年 9 月に Deepmind により発表された最適化手法です。原論文

内容は相当難しく、自分もかなりの部分を読み飛ばしています。日本語で解説されている記事として @ZoneTsuyoshi さんの Hamiltonian Descent Methods より広範なクラスで1次収束を達成する最適化手法 がありますので、気になる方はそちらを一読してきてからのほうが良いと思います。

数学的なありがたみを全部投げ捨てると、大事な部分は以下の 3 点になります。

• $x$ のほかに運動量 $p$ を更新する必要がある。
• First Explicit Method が次式で表される。

$$p_{i+1}=\delta p_i-\epsilon\delta\nabla f(x_i)\\\ x_{i+1}=x_i+\epsilon\nabla k(p_{i+1})$$

• 運動エネルギー $k$ を $k(p)=\varphi_2^1(\|p\|)=\sqrt{\|p\|^2+1}-1$ にするとなんとかなることがある。¹

実際にはこれが成立する数学的条件を考えていかないといけないのですが、とりあえずこれで実装します。

Chainer を使って実装

Chainer 公式の optimizer ディレクトリ 以下の SGD とか Adam とかの中身をパクりながら実装しました。² 実装に当たっては、山たー・優曇華院 さんによる Hamiltonian Descent Methodsの実装についての解説 上で紹介されている 実装 を参考にしています。

大事なのはここ。上の式をそのまま python で書いているだけです。 GPU 周りが全くわからなかったので CPU 版と同一ですが一応動きます…

    def update_core_gpu(self, param):
        grad = param.grad
        if grad is None:
            return
        hp = self.hyperparam
        p = self.state['p']
        
        p_ip1 = hp.delta * p - hp.epsilon * hp.delta * grad
        
        p_ip1var = Variable(p_ip1)

        sqsum = chainer.functions.sum(p_ip1var ** 2.0)
        kinetic = (1 + sqsum ) ** 0.5-1
        
        kinetic.backward()
        grad_k = p_ip1var.grad
        
        p = p_ip1
        param.data += hp.epsilon * grad_k

実験

MNIST を 500 次元の中間層 2 つ経由して 10 次元にします。途中で適宜 Relu を掛けます。training は 100 サンプルずつのバッチを使い 100 epoch。

optimizer だけを変更し、上の通りの HDM First Explicit Method と Adam のデフォルトとで比較します。 HDM のハイパーパラメータは $\epsilon = 1.0, \gamma = 2/3 (,\delta = (1+\gamma\epsilon)^{-1} = 0.6)$ です。 ³

今回 optimizer の質が見たいので main/loss だけを見ます。validation とか accuracy とかは無視で

結果

画像は全部 jupyter notebook の下の方に貼ってあるのを引っ張ってきてます。

片対数グラフで見てもちゃんと loss が減少している ただし速度は遅い。

#まとめ

• たぶん Chainer で動く HDM を実装した
• epoch 数で見ると収束が速い
  • 実装がまともなら実行時間で見てもよくなるのだろうか？　→なりました
  • MNIST だと loss が減るのが早すぎる気がした

Footnotes

1. Hamiltonian Descent Methods より広範なクラスで1次収束を達成する最適化手法
   
   relativistic kinetic と呼ばれ，微分すると， $$\nabla k(p)=\frac{p}{\sqrt{\|p\|^2+1}}$$ となり，様々な適応的勾配降下法で使われている形になる． ↩

2. [4] 番のブロック。 上手いことリンク張れるのかもしれませんが jupyter notebook の使い方わからないので…
   ついでに吐かせたログを消す方法も知らず ↩

3. $\epsilon$ が狂気の沙汰ですが $f$ ではなく $\nabla k$ にかかっている式の意味を考えたら 1 でもいいかなあと。$\gamma$ は適当。これでうまくいったので、よしとします。 ↩