External Memory

プログラミング周辺知識の備忘録メイン

Adadelta Optimizerについて

AdadeltaはAdagradの弱点を改善したアルゴリズムということで、試した。

Adadeltaは以下のようにして、最小値を得る。


以下で出てくる、
 E[g^2]_n と  E[\Delta x^2]_n
はそれぞれ減衰係数\rhoを含んだ0-nまでの勾配とパラメータ更新の際の差の二乗和である。


  • inital parameter : x_1を設定。
  • また、

  \displaystyle E[g^2]_0=0,\ E[\Delta x^2]_0=0
とそれぞれと初期化する。


  • 勾配g_nを計算する。
  • 勾配の減衰二乗和を更新する。

  \displaystyle E[g^2]_n = \rho\,E[g^2]_{n-1} + (1-\rho)\,g_n^2


  • 二乗和の平方根をとる。εはゼロ割を防いだり、更新値の改善のための定数です。

 \displaystyle RMS[g]_n = \sqrt{E[g^2]_0 + \epsilon}


  •  \Delta x_nを更新する。

  \displaystyle \Delta x_n=-\frac{RMS[\Delta x]_{n-1}}{RMS[g]_n}g_n


  • パラメータの減衰二乗和を更新する。

  \displaystyle E[\Delta x^2]_n = \rho\,E[\Delta x^2]_{n-1} + (1-\rho)\,\Delta x_n^2


  • パラメータを更新する。

  \displaystyle x_{n+1} = x_n + \Delta x_n


勾配計算に戻るループ。


Adagradと比較すると、以下の点で異なることがわかる。
・学習率が撤廃されたのでその設定に煩わされることがなくなった。
(ρやε、RMS[Δx]に定数を掛けることである程度調整可能ではある。)

・収束速度が大幅に落ちてしまうということがなくなり、
勾配等の値からの影響が低減された。

 \Delta x_nの更新においてnが一つズレていることは
急に大きく勾配が変化する場合に耐性がある。

Python検証

import numpy as np

div = 1000000
R = np.pi

def f(x):
    return (x-0.7)**2

def g(x):
    return np.sin(x-np.pi/2-0.7)+1

def adadelta(init):
    eps = 1e-5
    e = 1e-8
    N = 1000
    r = 0.95
    v = np.linspace(0,R,div)
    diff = np.gradient(f(v),R/div)
    difg = np.gradient(g(v),R/div)
    x1 = x2 = round(div/R * init) 
    Eg = Edx = dx = 0.0
    
    for i in range(N):
        
        Eg = r * Eg + (1-r) * diff[np.int(x1)]**2
        RMSg = np.sqrt(Eg + e)
        RMSdx = np.sqrt(Edx + e)
        Edx = r * Edx + (1-r) * dx**2
        dx = -RMSdx / RMSg * diff[np.int(x1)]
        n_x1 = (x1*R/div + dx)*div/R
        #n_x1 = x1 - div/R * RMSdx * diff[np.int(x1)] / RMSg
            
        
        if abs(n_x1 - x1)*R/div < eps:
            print(i+1,end="  ")
            break
        
        x1 = n_x1
        if i==N-1 :print(N,end=" ")
    
    Eg = Edx = dx = 0
    for i in range(N):
        
        Eg = r * Eg + (1-r) * difg[np.int(x2)]**2
        RMSg = np.sqrt(Eg + e)
        RMSdx = np.sqrt(Edx + e)
        Edx = r * Edx + (1-r) * dx**2
        dx = -RMSdx / RMSg * difg[np.int(x2)]
        n_x2 = (x2*R/div + dx)*div/R
        #n_x2 = x2 - div/R * RMSdx * difg[np.int(x2)] / RMSg
            
        
        if abs(n_x2 - x2)*R/div < eps:
            print(i+1,end="  ")
            break
        
        x2 = n_x2
        if i==N-1 :print(N,end=" ")
        
    return f(x1/div*R) + g(x2/div*R),x1/div*R,x2/div*R


print("{0[0]:.4f}, {0[1]:.4f}, {0[2]:.4f}".format(adadelta(0.5)))

結果

ε値
更新回数(f(x),g(x)) f(x)+g(x)最小値 最小値時のパラメータ

ε = 1e-8
774 772 0.0000, 0.6999, 0.6999
ε = 1e-6
171 171 0.0000, 0.6999, 0.6999
ε = 1e-4
27 28 0.0000, 0.7000, 0.7000
ε = 1e-2
1000 4 0.0000, 0.6999, 0.7000


ρを0.95前後、εを極端に大きくしなければ問題なさそうに見えます。


Gradientdescent、Adagradと比較すると
Adadeltaは初期設定をせずとも堅牢でお手軽であり、
optimizerとしての性能も前二つに劣らないように見える。
どれを使うべきか迷う場合Adadeltaは無難な選択かと思う。


TensorFlowのtf.train.AdadeltaOptimizerには学習率に関する引数がある。
元文献https://arxiv.org/pdf/1212.5701v1.pdfでは1.0との記載がある一方、
tf.train.AdadeltaOptimizerのデフォルト引数は0.001です。
これはRMS[Δx]の係数か何かでしょうか。


追記 2017/7/30
更新時にΔxに学習率を掛けてた。RMS[Δx]の係数でも結果は同じ。
以下はAdadeltaのソースコード
tensorflow/training_ops.cc at master · tensorflow/tensorflow · GitHub