追記情報

  • 2017.12.19:Chainer3.2.0 の Optimizer とのパラメータ対応,Optimizer の流儀について追記.
  • 2018.2.12:AdaMax, Nadam, Eve, GD by GD, AdaSecant について追記.

はじめに

明治大学総合数理アドベントカレンダー17日目です.今回は,深層学習のオプティマイザを述べます.オプティマイザのまとめページとしてAdaGrad,RMSProp,AdaDelta,Adam,SMORMS3というものがあるのですが,それに新たなオプティマイザを加えて紹介してみます(2017年12月時点).

前提知識

  • 勾配降下法・ミニバッチ学習(オンライン学習)
  • 平均二乗誤差・交差エントロピー
  • 不偏推定量
  • 深層学習に関する基礎知識

本日紹介する最適化手法

  • 確率的勾配降下法(SGD)
  • MomentumSGD
  • ネステロフの加速法(NAG) (1983)
  • AdaGrad (2011)
  • RMSprop (2012)
  • AdaDelta (2012)
  • Adam (2014)
  • RMSpropGraves (2014)
  • SMORMS3 (2015)
  • AdaMax (2015)
  • Nadam (2016)
  • Eve (2016)
  • Santa (2016)
  • GD by GD (2016)
  • AdaSecant (2017)

記号について

  • [1]は後の参考文献と対応している番号である.
  • ベクトルはbold体$\mathbf{a}$のように表す.
  • ベクトルの要素ごとの積は$\mathbf{a}\mathbf{b}$のように通常の積と表す.本来$\mathbf{a}\odot\mathbf{b}$と表すべきだが,書きやすさを選んだ.
  • ベクトルの要素ごとの商は$\mathbf{a}/\mathbf{b}$のように通常の商と同じように表す.本来$\mathbf{a}\oslash\mathbf{b}$と表すべきだが,書きやすさを選んだ.
  • スカラーとベクトルの間で演算を行っていた場合,スカラー$s$はすべての要素が1のベクトル$\mathbf{1}$との積$s\mathbf{1}$を指しているものとする.
  • 最適化するパラメータは$\mathbf{w}$で表す.
  • 最適化に用いる評価関数は$E(\mathbf{w})$で表す.平均二乗誤差や交差エントロピーを考えれば良い.
  • $t$はイテレーションを表す.ミニバッチ学習において,(1エポックにおけるバッチ数)$\times$(エポック数)$=$(イテレーション数)であり,何番目のイテレーションかを指す.
  • $\eta$は学習率(learning rate),$\mathbf{g}$は評価関数の勾配である.

確率的勾配降下法(SGD, Stochastic Gradient Descent)

ご存知の通り,次のアルゴリズムで表せる.

\mathbf{g}^{(t)}=\nabla E(\mathbf{w}^{(t)})\\
\Delta\mathbf{w}^{(t)}=-\eta\mathbf{g}^{(t)}\\
\mathbf{w}^{(t+1)}=\mathbf{w}^{(t)}+\Delta\mathbf{w}^{(t)}

収束の不安定性・遅さから深層学習のような高次元の問題で使われることはない.

Chainer3.2.0 におけるアップデート関数は次のようになっている.

chainer.optimizers.sgd.py
def update_core_cpu(self, param):
    grad = param.grad
    if grad is None:
        return
    param.data -= self.hyperparam.lr * grad

また,アルゴリズムとの変数の対応は次の通りである.

  • lr (input) : 学習率$\eta$
  • grad : 評価関数の勾配$\mathbf{g}$
  • data : パラメータ$\mathbf{w}$

MomentumSGD

SGDは収束が遅く,また振動や鞍点に陥る問題が発生しやすい[1].そういった問題を克服するため提案されたのが MomentumSGD である.MomentumSGD では,一期前の勾配情報$\Delta\mathbf{w}_{t-1}$を用いる.谷の間で振動する場合,一期前の勾配情報を用いることで振動を抑制できる.フラットな斜面の場合も収束するまでの時間を短くすることができる.また,安定した収束が得られることでも知られており,これ以後紹介する収束が早い最適化アルゴリズムを差し置いて使われることもある.アルゴリズムは,以下で表せる.

\mathbf{g}^{(t)}=\nabla E(\mathbf{w}^{(t)})\\
\Delta\mathbf{w}^{(t)}=\mu\Delta\mathbf{w}^{(t-1)}-(1-\mu)\eta\mathbf{g}^{(t)}\\
\mathbf{w}^{(t+1)}=\mathbf{w}^{(t)}+\Delta\mathbf{w}^{(t)}

ここで,$\mu$は一期前の勾配情報を伝える比率を示すハイパーパラメータで,$\mu=0.9,\eta=0.01$で使われることが多い.

Chainer3.2.0 においてアップデート関数は次のようになっている.

chainer.optimizers.momentum_sgd.py
def update_core_cpu(self, param):
    grad = param.grad
    if grad is None:
        return
    v = self.state['v']
    v *= self.hyperparam.momentum
    v -= self.hyperparam.lr * grad
    param.data += v

ここで,変数のアルゴリズムとの対応は以下の通りである.

  • lr (input) : 学習率$\eta$
  • momentum (input) : 一次モーメントの指数減衰率$\mu$
  • grad : 評価関数の勾配$\mathbf{g}$
  • v : パラメータの変化分$\Delta\mathbf{w}$
  • data : パラメータ$\mathbf{w}$

また,Chainer3.2.0 におけるアルゴリズムは,

\Delta\mathbf{w}^{(t)}=\mu\Delta\mathbf{w}^{(t-1)}-\eta\mathbf{g}^{(t)}\\

となっており,$(1-\mu)\eta$が$\eta$だけで表されていることに注意されたい.$1-\mu$を掛けるか否かは流儀があり,結局$\eta$を変えれば調節可能である.

ネステロフの加速法(NAG) (1983)

ネステロフの加速法(Nesterov's Accelerated Gradient method)は,MomentumSGD の修正版であり,さらに収束への加速を増したものである.勾配の値を評価する位置を$\mathbf{w}^{(t)}+\mu\mathbf{w}^{(t-1)}$とすることで,一期先の時刻を大雑把に見積もることができる[1,2].アルゴリズムは以下で表せる.

\mathbf{g}^{(t)}=\nabla E(\mathbf{w}^{(t)}+\mu\mathbf{w}^{(t-1)})\\
\Delta\mathbf{w}^{(t)}=\mu\Delta\mathbf{w}^{(t-1)}-(1-\mu)\eta\mathbf{g}^{(t)}\\
\mathbf{w}^{(t+1)}=\mathbf{w}^{(t)}+\Delta\mathbf{w}^{(t)}

ここで,パラメータ$\mu$は MomentumSGD と同様で,一期前の勾配情報を伝える比率を表すハイパーパラメータであり,$\mu=0.9,\eta=0.01$で与えられることが多い.

Chainer3.2.0 におけるアップデート関数は以下の通りである.

chainer.optimizers.nesterov_ag.py
def update_core_cpu(self, param):
    grad = param.grad
    if grad is None:
        return
    v = self.state['v']
    lr, momentum = self.hyperparam.lr, self.hyperparam.momentum

    v *= momentum
    v -= lr * grad
    param.data += momentum * momentum * v
    param.data -= (1 + momentum) * lr * grad

先ほど説明したアルゴリズムとは割と変わっている.具体的には,次のようになっている.

\mathbf{g}^{(t)}=\nabla E(\mathbf{w}^{(t)})\\
\Delta\mathbf{w}^{(t)}=\mu\Delta\mathbf{w}^{(t-1)}-\eta\mathbf{g}^{(t)}\\
\mathbf{w}^{(t+1)}=\mathbf{w}^{(t)}+\mu^2\Delta\mathbf{w}^{(t)}-(1+\mu)\eta\mathbf{g}^{(t)}

一期先を大雑把に見積もった$\nabla E(\mathbf{w}_t+\mu\mathbf{w}_{t-1})$をテイラー展開した感じになっているのかなと思う(確かめていないけど).変数の対応は以下の通りである.

  • lr (input):学習率$\eta$
  • momentum (input):一次モーメントの指数減衰率$\mu$
  • grad : 評価関数の勾配$\mathbf{g}$
  • v : パラメータの変化分$\Delta\mathbf{w}$
  • data : パラメータ$\mathbf{w}$

AdaGrad (2011)

MomentumSGD, NAG では振動抑制・収束加速に対する効果はあるが,収束方向に関する配慮がなかった.どういうことかというと,多次元の問題だと,勾配が急な方向には早く収束するが,勾配が緩やかな方向には収束に時間がかかることが起こり得る.それに対応するため,各次元ごとに学習率を調整していこうという手法が提案された.その先駆けとなったのが AdaGrad(Adaptive subGradient descent) である[1,3].アルゴリズムとしては,以下で表せる.

\mathbf{g}^{(t)}=\nabla E(\mathbf{w}^{(t)})\\
\Delta\mathbf{w}^{(t)}=-\frac{\eta}{\sqrt{\sum_{s=1}^t(\mathbf{g}^{(s)})^2}}\mathbf{g}^{(t)}\\
\mathbf{w}^{(t+1)}=\mathbf{w}^{(t)}+\Delta\mathbf{w}^{(t)}

第二式の$(\mathbf{g}^{(t)})^2$は要素ごとに二乗したベクトルを表しており,次元に応じて学習スピードが変化していることが窺える.今まで多く学習してきた次元の学習量は減るという仕組みである.また,ハイパーパラメータ$\eta=0.001$で与えられることが多い.

Chainer3.2.0 におけるアップデート関数は以下の通りである.

chainer.optimizers.ada_grad.py
def update_core_cpu(self, param):
    grad = param.grad
    if grad is None:
        return

    lr = self.hyperparam.lr
    eps = self.hyperparam.eps
    h = self.state['h']

    h += grad * grad
    param.data -= lr * grad / (numpy.sqrt(h) + eps)

Chainer3.2.0 においては発散防止のため,分母に$\varepsilon$が足されている.すなわち,

\Delta\mathbf{w}^{(t)}=-\frac{\eta}{\sqrt{\sum_{s=1}^t(\mathbf{g}^{(s)})^2}+\varepsilon}\mathbf{g}^{(t)}\\

となっている.変数の対応は以下の通りである.

  • lr (input):学習率$\eta$
  • eps (input):発散防止パラメータ$\varepsilon$
  • grad : 評価関数の勾配$\mathbf{g}$
  • h : 過去の勾配の総和$\sum_{s=1}^t(\mathbf{g}^{(s)})^2$
  • data : パラメータ$\mathbf{w}$

RMSprop (2012)

AdaGrad は次元に応じた学習率の変更を可能にしたが,最初に急な坂になっていて,その後も坂が続く次元に対応していなかった.どういうことかというと,一度学習率が0に十分近くなってしまった次元に関しては,まだ坂があってもほとんど更新されなくなってしまうことである.その改善策として提案されたのが RMSprop である[1].RMSprop では,初期の影響が$\rho^{t/2}$に応じて指数的減衰していく.アルゴリズムとしては以下で与えられている.

\mathbf{g}^{(t)}=\nabla E(\mathbf{w}^{(t)})\\
\mathbf{v}_t=\rho\mathbf{v}_{t-1}+(1-\rho)(\mathbf{g}^{(t)})^2\\
\Delta\mathbf{w}^{(t)}=-\frac{\eta}{\sqrt{\mathbf{v}_t+\varepsilon}}\mathbf{g}^{(t)}\\
\mathbf{w}^{(t+1)}=\mathbf{w}^{(t)}+\Delta\mathbf{w}^{(t)}

ここで,$\mathbf{v}_0=\mathbf{0}$とし,ハイパーパラメータ$\varepsilon=10^{-6},10^{-8},\eta=0.01$で与えられることが多い.また,$\rho$は前の情報をどれぐらい指数的に減衰して伝えるかを示すハイパーパラメータで,$\rho=0.99$で与えられることが多い.

Chainer3.2.0 におけるアップデート関数は以下の通りである.

chainer.optimizers.rmsprop.py
def update_core_cpu(self, param):
    grad = param.grad

    if grad is None:
        return
    hp = self.hyperparam
    eps = grad.dtype.type(hp.eps)
    if hp.eps != 0 and eps == 0:
        raise ValueError(
            'eps of RMSprop optimizer is too small for {} ({})'.format(
                grad.dtype.name, hp.eps))
    ms = self.state['ms']

    ms *= hp.alpha
    ms += (1 - hp.alpha) * grad * grad
    param.data -= hp.lr * grad / (numpy.sqrt(ms) + eps)

先ほどのアルゴリズムと違って,Chainer では$\varepsilon$をルートの外に出していることがわかる.すなわち,

\Delta\mathbf{w}^{(t)}=-\frac{\eta}{\sqrt{\mathbf{v}_t}+\varepsilon}\mathbf{g}^{(t)}

となっている.また,変数は以下の対応となっている.

  • lr (input):学習率$\eta$
  • alpha (input):二次モーメントの指数減衰率$\rho$
  • eps (input):発散防止パラメータ$\varepsilon$
  • grad : 評価関数の勾配$\mathbf{g}$
  • ms : 過去の勾配の二乗の指数移動平均$\mathbf{v}$
  • data : パラメータ$\mathbf{w}$

AdaDelta (2012)

RMSprop では次元数のミスマッチの問題が解消されていなかった.どういうことかというと,$\Delta\mathbf{w}$は次元量が長さであるが,$\mathbf{g}$はその勾配を取っているので,次元量は$1/$長さとなる.すなわち,次元量が違うもので計算していたので,スケール変換に対応できていなかったのである[1,4].これを解消したものが AdaDelta であり,ニュートン法を応用したものである.アリゴリズムは,以下で与えられる.

\mathbf{g}^{(t)}=\nabla E(\mathbf{w}^{(t)})\\
\mathbf{v}_t=\rho\mathbf{v}_{t-1}+(1-\rho)(\mathbf{g}^{(t)})^2\\
\mathbf{u}_t=\rho\mathbf{u}_{t-1}+(1-\rho)(\Delta\mathbf{w}^{(t)})^2\\
\Delta\mathbf{w}^{(t)}=-\frac{\sqrt{\mathbf{u}_{t-1}+\varepsilon}}{\sqrt{\mathbf{v}_t+\varepsilon}}\mathbf{g}^{(t)}\\
\mathbf{w}^{(t+1)}=\mathbf{w}^{(t)}+\Delta\mathbf{w}^{(t)}

ここで,$\mathbf{v}=\mathbf{u}=\mathbf{0}$とし,ハイパーパラメータ$\rho=0.95$が多く使われている.

Chainer3.2.0 におけるアップデート関数は以下の通りである.

chainer.optimizers.ada_delta.py
def update_core_cpu(self, param):

    grad = param.grad
    if grad is None:
        return
    msg, msdx = self.state['msg'], self.state['msdx']
    rho = self.hyperparam.rho
    eps = self.hyperparam.eps

    msg *= rho
    msg += (1 - rho) * grad * grad
    dx = numpy.sqrt((msdx + eps) / (msg + eps)) * grad
    msdx *= rho
    msdx += (1 - rho) * dx * dx
    param.data -= dx

変数の対応は以下の通りである.

  • rho (input):一次,二次モーメントの指数減衰率$\rho$
  • eps (input):発散防止パラメータ$\varepsilon$
  • grad:評価関数の勾配$\mathbf{g}$
  • msg:過去の勾配の二乗の指数移動平均$\mathbf{v}$
  • msdx:過去のパラメータ差分の二乗の指数移動平均$\mathbf{u}$
  • data:パラメータ$\mathbf{w}$

Adam (2014)

もっともよく使われている最適化アルゴリズムである.Adam も RMSprop の改良版であり,勾配に関しても以前の情報を指数的減衰させながら伝えることで,次元量の問題に対処している[5].Adam のアルゴリズムは,以下で与えられる.

\mathbf{g}^{(t)}=\nabla E(\mathbf{w}^{(t)})\\
\mathbf{m}_t=\rho_1\mathbf{m}_{t-1}+(1-\rho_1)\mathbf{g}^{(t)}\\
\mathbf{v}_t=\rho_2\mathbf{v}_{t-1}+(1-\rho_2)(\mathbf{g}^{(t)})^2\\
\hat{\mathbf{m}}_t=\frac{\mathbf{m}_t}{1-\rho_1^t}\\
\hat{\mathbf{v}}_t=\frac{\mathbf{v}_t}{1-\rho_2^t}\\
\Delta\mathbf{w}^{(t)}=-\frac{\eta}{\sqrt{\hat{\mathbf{v}}_t+\varepsilon}}\hat{\mathbf{m}}_t\\
\mathbf{w}^{(t+1)}=\mathbf{w}^{(t)}+\Delta\mathbf{w}^{(t)}

ここで,$\hat{\mathbf{m}}_t,\hat{\mathbf{v}}_t$は勾配,二乗勾配の不偏推定量となるように調整したものである.ハイパーパラメータは,$\eta=0.001,\rho_1=0.9,\rho_2=0.999,\varepsilon=10^{-8}$で与えられることが多い.

Chainer3.2.0 におけるアップデート関数は以下の通りである.

chainer.optimizers.adam.py
def update_core_cpu(self, param):
    grad = param.grad
    if grad is None:
        return
    hp = self.hyperparam
    eps = grad.dtype.type(hp.eps)
    if hp.eps != 0 and eps == 0:
        raise ValueError(
            'eps of Adam optimizer is too small for {} ({})'.format(
                grad.dtype.name, hp.eps))
    m, v = self.state['m'], self.state['v']

    m += (1 - hp.beta1) * (grad - m)
    v += (1 - hp.beta2) * (grad * grad - v)
    param.data -= self.lr * m / (numpy.sqrt(v) + eps)

Chainer3.2.0 における実装では,書き方が違うものの,アルゴリズムと異なるのは$\varepsilon$が平方根の外に出ていることである.すなわち,

\Delta\mathbf{w}^{(t)}=-\frac{\eta}{\sqrt{\hat{\mathbf{v}}_t}+\varepsilon}\hat{\mathbf{m}}_t

となっている.また,変数の対応は以下の通りである.

  • lr (input):学習率$\eta$
  • beta1 (input):一次モーメントの指数減衰率$\rho_1$
  • beta2 (input):一次モーメントの指数減衰率$\rho_2$
  • eps (input):発散防止パラメータ$\varepsilon$
  • grad:評価関数の勾配$\mathbf{g}$
  • m:過去の勾配の二乗の指数移動平均$\mathbf{m}$
  • v:過去の勾配の二乗の指数移動平均$\mathbf{v}$
  • data:パラメータ$\mathbf{w}$

Chainer3.2.0 の説明を読むと,入力変数にalphaとあるが,内部でalphaとしたりlrとしたり一貫性が保たれていない.

RMSpropGraves (2014)

Graves が提案した RMSprop の改良版アルゴリズムである[7].主に手書き文字認識の分野で用いられている(例えば[7]や[8])ので,手書き文字認識を専門的にやっている人は Chainer にクラスが用意されているので試してみると良い.アルゴリズムは,以下で与えられる.

\mathbf{g}^{(t)}=\nabla E(\mathbf{w}^{(t)})\\
\mathbf{m}_t=\rho\mathbf{m}_{t-1}+(1-\rho)\mathbf{g}^{(t)}\\
\mathbf{v}_t=\rho\mathbf{v}_{t-1}+(1-\rho)(\mathbf{g}^{(t)})^2\\
\Delta\mathbf{w}^{(t)}=-\frac{\eta}{\sqrt{\mathbf{v}_t-\mathbf{m}_t^2+\varepsilon}}\mathbf{g}^{(t)}\\
\mathbf{w}^{(t+1)}=\mathbf{w}^{(t)}+\Delta\mathbf{w}^{(t)}

ハイパーパラメータは,$\eta=0.0001,\rho=0.95,\varepsilon=10^{-4}$で与えられることが多い.

Chainer3.2.0 におけるアップデート関数は以下の通りである.

chainer.optimizers.rmsprop_graves.py
def update_core_cpu(self, param):
    grad = param.grad
    if grad is None:
        return
    n, g, delta = self.state['n'], self.state['g'], self.state['delta']
    hp = self.hyperparam

    n *= hp.alpha
    n += (1 - hp.alpha) * grad * grad
    g *= hp.alpha
    g += (1 - hp.alpha) * grad
    delta *= hp.momentum
    delta -= hp.lr * grad / numpy.sqrt(n - g * g + hp.eps)
    param.data += delta

Chainer3.2.0 ではモーメンタム項も加えられており,アルゴリズムは次のようになっている.

\Delta\mathbf{w}^{(t)}=\mu\Delta\mathbf{w}^{(t-1)}-\frac{\eta}{\sqrt{\mathbf{v}_t-\mathbf{m}_t^2+\varepsilon}}\mathbf{g}^{(t)}

また,変数の対応は以下の通りである.

  • lr (input):学習率$\eta$
  • alpha (input):勾配の1次,2次モーメントの指数減衰率$\rho$
  • eps (input):発散防止パラメータ$\varepsilon$
  • momentum (input):調整勾配の1次モーメント$\mu$
  • r:調整パラメータ$\rho$
  • grad:評価関数の勾配$\mathbf{g}$
  • g:過去の勾配の二乗の指数移動平均$\mathbf{m}$
  • n:過去の勾配の二乗の指数移動平均$\mathbf{v}$
  • delta:パラメータの差分$\Delta\mathbf{w}$
  • data:パラメータ$\mathbf{w}$

SMORMS3 (2015)

SMORMS3 は RMSprop の問題点を曲率と LeCun 法によって克服したものである[9].SMORMS3 のアルゴリズムは,以下で与えられる.

\mathbf{g}^{(t)}=\nabla E(\mathbf{w}^{(t)})\\
\mathbf{s}_{t}=1+(1-\boldsymbol{\zeta}_{t-1}\mathbf{s}_{t-1})\\
\boldsymbol{\rho}_t=\frac{1}{\mathbf{s}_t+1}\\
\mathbf{m}_t=\boldsymbol{\rho}_t\mathbf{m}_{t-1}+(1-\boldsymbol{\rho}_t)(\mathbf{g}^{(t)})\\
\mathbf{v}_t=\boldsymbol{\rho}_t\mathbf{v}_{t-1}+(1-\boldsymbol{\rho}_t)(\mathbf{g}^{(t)})^2\\
\boldsymbol{\zeta}_t=\frac{\mathbf{m}_t^2}{\mathbf{v}_t+\varepsilon}\\
\Delta\mathbf{w}^{(t)}=-\frac{\min\{\eta,\boldsymbol{\zeta}_t\}}{\sqrt{\mathbf{v}_t+\varepsilon}}\mathbf{g}^{(t)}\\
\mathbf{w}^{(t+1)}=\mathbf{w}^{(t)}+\Delta\mathbf{w}^{(t)}

大変変数が多いが,学習率が小さくなりすぎないように調整したと考えると良い.

Chainer3.2.0 におけるアルゴリズムは以下の通りである.

chainer.optimizers.smorms3.py
def update_core_cpu(self, param):

    grad = param.grad
    if grad is None:
        return
    mem, g, g2 = self.state['mem'], self.state['g'], self.state['g2']

    r = 1 / (mem + 1)
    g = (1 - r) * g + r * grad
    g2 = (1 - r) * g2 + r * grad * grad
    x = g * g / (g2 + self.hyperparam.eps)
    param.data -= grad * numpy.minimum(x, self.hyperparam.lr) \
        / (numpy.sqrt(g2) + self.hyperparam.eps)
    mem = 1 + mem * (1 - x)

    self.state['mem'], self.state['g'], self.state['g2'] = mem, g, g2

Chainer におけるアルゴリズムは$\varepsilon$が外に出ており,

\Delta\mathbf{w}^{(t)}=-\frac{\min\{\eta,\boldsymbol{\zeta}_t\}}{\sqrt{\mathbf{v}_t}+\varepsilon}\mathbf{g}^{(t)}

である.また,変数の対応は以下の通りである.

  • lr (input):学習率$\eta$
  • eps (input):発散防止パラメータ$\varepsilon$
  • r:調整パラメータ$\rho$
  • grad:評価関数の勾配$\mathbf{g}$
  • g:過去の勾配の二乗の指数移動平均$\mathbf{m}$
  • g2:過去の勾配の二乗の指数移動平均$\mathbf{v}$
  • x:調整パラメータ$\boldsymbol{\zeta}$
  • mem:調整パラメータ$\mathbf{s}$
  • data:パラメータ$\mathbf{w}$

AdaMax (2015)

Adam の開発者自身が Adam を無限次元ノルムに対応させたものとして定義している[8].アルゴリズムは以下で与えられている.

AdaMax.png

Nadam (2016)

ネステロフの加速法を Adam に取り入れたものが Nadam である[11].Nadam のアルゴリズムは以下で与えられている.

NAdam_algorithm.png

また,ロスが Adam よりも早く減っていることが見て取れる.

Nadam_result.png

Eve (2016)

Eve は,相対的変化が大きければ学習率を削減し,小さければ上昇させることでフラットエリアで学習を高速化できるよう Adam を改良したものである[13].アルゴリズムは以下で与えられる.

Eve_Algorithm.png

また,ロスが Adam や AdaMax より早く減衰することも示している.

Eve_result.png

Santa (2016)

ざっくりいうと,Santa(Stochastic AnNealing Thermostats with Adaptive Momentum)は,Adam や RMSprop に MCMC(マルコフ連鎖モンテカルロ)法を取り入れたものである.論文[14]では,Euler 型の Santa-E と SSS (対称分割法,Symmetric Separation Scheme)型の Santa-SSS について述べられている.その中でも,Santa-SSS が Adam より高い精度を示している.

Santa-E

Santa-E アルゴリズムは以下で与えられている.
Santa-E.png

ここで,今まで勾配を$\mathbf{g}_t$としていたが,$\tilde{\mathbf{f}}_t$で表されていることに注意されたい.Santa には exploration (探索)ステップと refinement (精錬)ステップがある.探索ステップはガウスノイズ$\boldsymbol{\zeta}$を載せながら最適解の近くまで探索するステップであり,精錬ステップはその後の学習をするステップである.MCMC というと計算量が肥大するのではないかと思った方もいるかもしれないが,見てわかる通り,従来まとめていたステップを分けただけであり,イテレーションあたりの計算量も必要メモリも微増である.

Santa-SSS

Santa-SSS アリゴリズムは以下で与えられている.
Santa-SSS.png

ここで,$\mathbf{g}_t$はフィッシャー情報量を表しており,Santa-SSS は mSGNHT を拡張したものになっている.また,このアルゴリズムの収束性は,リーマン情報幾何を学んでいる人は,論文[14]を読むと理解できると思う.

論文での結果は次の通りであった.
Santa-Result.png

見ての通り,Santa(Santa-SSS) が bunrin 期間を過ぎると,Adam 等の他のオプティマイザを寄せ付けない圧倒的な性能の良さを示していることがわかる.これは,Santa ではノイズを付加して探索することでパラメータ空間を限りなく探索して大域的な谷を見つけているからである.そのため,大域的極小解に近い極小解を得ているだけの他のアルゴリズムの追随を許していないのである.

GD by GD (2016)

GD by GD(Gradient Descent by Gradient Descent)は,最適化アルゴリズムも学習問題と捉え,学習して最適化構造を決めて行くものである[16].イメージ図は次のとおりである.

GDbyGD.png

最適化される Optimizee だけでなく,最適化する Optimizer もロス情報で最適化していこうという発想である.具体的には,LSTM optimizer を提案している.

optimizer_LSTM.png

また,この LSTM optimizer では loss が Adam 等より減りが早いという結果を得ている.

LSTM_loss.png

AdaSecant (2017)

AdaSecant はロスの曲率情報(2階微分)まで伝えて最適化しようというアイディアである[17].これまでにもヘシアンを活用しようというアイディアはあったが,逆行列の計算に時間的コストがかかる上,対角ヘシアンの逆行列はヘシアンの逆行列の対角化の近似として不適切であることも示されていた.

 AdaSecant では,Newton 法と準 Newton 法(quasi-Newton)がパラメータ空間でアフィン不変であることに目をつけた.また,確率的 rank-1 quasi-Newton 法となっており,アフィン変換に対するロバスト性が確保できている.アルゴリズム的には,勾配の secant 近似がヘシアンの対角成分の近似となっていることを活用している.アルゴリズムは次のとおりである.

AdaSecant_algorithm.png

loss が Adam 等より減衰していることも示されている.

AdaSecant_loss.png

最後に

  • AdaMax, Nadam, Eve, Santa, GD by GD, AdaSecant が Chainer 対応してくれると嬉しい.
  • ちなみに,Tensorflow はすでに AdaMax, Nadam の実装がなされている.
  • AdaMax 以降の数式書くのサボっているので気が向いたらまた更新するかも

参考文献

  1. 瀧雅人,機械学習スタートアップシリーズ これならわかる深層学習入門,講談社,2017.
  2. Yurri Nesterov. A method of solving a convex programming problem with convergence rate O(1/sqr(k)), http://www.cis.pku.edu.cn/faculty/vision/zlin/1983-A%20Method%20of%20Solving%20a%20Convex%20Programming%20Problem%20with%20Convergence%20Rate%20O(k%5E(-2))_Nesterov.pdf, 1983.
  3. John Duchi, Elad Hazen, Yoram Singer. Adaptive Subgradient Methods for Online Learning and Stochastic Optimization, http://www.jmlr.org/papers/volume12/duchi11a/duchi11a.pdf, 2011.
  4. Matthew D. Zeiler. ADADELTA: AN ADAPTIVE LEARNING RATE METHOD, https://arxiv.org/pdf/1212.5701.pdf, 2012.
  5. Diederik P. Kingma, Jimmy Lei Ba. ADAM: A METHOD FOR STOCHASTIC OPTIMIZATION, https://arxiv.org/pdf/1412.6980.pdf, 2015.
  6. Alex Graves, Generating Sequences With Recurrent Neural Network, https://arxiv.org/pdf/1308.0850.pdf, 2014.
  7. Karol Gregor, Ivo Danihelka, Andriy Mnih, Charles Blundell, Daan Wierstra. Deep AutoRegressive Networks, https://arxiv.org/pdf/1310.8499.pdf, 2014.
  8. Ganbin Zhou, Ping Luo, Rongyu Cao, Fen Lin, Bo Chen, Qing He. Mechanism-Aware Neural Machine for Dialogue Response Generation. aaai. 2017.
  9. Simon Funk. RMSprop loses to SMORMS3 - Beware the Epsilon!. http://sifter.org/~simon/journal/20150420.html, 2015.
  10. AdaGrad, RMSProp, AdaDelta, Adam, SMORMS3,https://qiita.com/skitaoka/items/e6afbe238cd69c899b2a.
  11. Timothy Dozat. INCORPORATING NESTEROV MOMENTUM INTO ADAM. https://openreview.net/pdf?id=OM0jvwB8jIp57ZJjtNEZ, 2016.
  12. OPTIMIZER 入門 ~線形回帰からAdamからEveまで,https://qiita.com/deaikei/items/29d4550fa5066184329a
  13. Jayanth Koushik & Hiroaki Hayashi. IMPROVING STOCHASTIC GRADIENT DESCENT WITH FEEDBACK, https://arxiv.org/pdf/1611.01505.pdf, 2016.
  14. Changyou Chen, David Carlson, Zhe Gan, Chunyuan Li, Lawrence Carin Bridging the Gap between Stochastic Gradient MCMC and Stochastic Optimization,http://proceedings.mlr.press/v51/chen16c.pdf, 2016.
  15. Chunyuan Li, Changyou Chen, Kai Fan and Lawrence Carin. High-Order Stochastic Gradient Thermostats for Bayesian Learning of Deep Models, https://www.cse.buffalo.edu/~changyou/PDF/msgnht_poster.pdf, n.d.
  16. Marcin Andrychowicz, Misha Denil, Sergio Gomez Colmenarejo, Matthew W. Hoffman, David Pfau, Tom Schaul, Brendan Shillingford, Nando de Freitas. Learning to learn by gradient descent by gradient descent. http://papers.nips.cc/paper/6461-learning-to-learn-by-gradient-descent-by-gradient-descent.pdf, 2016.
  17. Caglar Gulcehre, Jose Sotelo, Marcin Moczulski, Yoshua Brengio. A Robust Adaptive Stochastic Gradient Method for Deep Learning. https://arxiv.org/pdf/1703.00788.pdf, 2017.
Sign up for free and join this conversation.
Sign Up
If you already have a Qiita account log in.