External Memory

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

Gradient descent optimizerとAdagrad optimizer

先日のTensorFlowで最適化法について知識があまりなかったので少しだけ調べた。

Gradient descent optimizerとAdagrad optimizer

先日使ったoptimaizerはGradient descentとAdagrad。
これらは次元ごとに分離して最小値が得られる。

最急降下法は以下の数列が収束することにより、\displaystyle f(x)の最小値を求めるアルゴリズム

\displaystyle \mathrm{x_{n+1}} = {\mathrm{x_n}} - \eta\,{\mathrm{grad}}\,f{(\mathrm{x_n})}
\displaystyle \eta : learning rate(学習率)


Adagradの場合は以下のようになる。

\displaystyle \mathrm{x_{n+1}} = \mathrm{x_n} - \frac{\eta}{\sqrt{G_n + \epsilon}} \,\mathrm{grad}\,f(\mathrm{x_n})

\displaystyle G_n : 0からnまでのgrad[f(x)]の二乗和、\displaystyle \epsilon : ゼロ割防止のための項


Adagradに関する文献
http://www.jmlr.org/papers/volume12/duchi11a/duchi11a.pdf

元文献だが、かなり内容が専門的なので読み通すことすら困難だった。

https://arxiv.org/pdf/1212.5701v1.pdf

こちらのほうが概要的で易しい。
AdadeltaメインでAdagradの初期学習率の選択に関する問題と学習率の低下の問題を回避しようとしている。


Gradient descent とAdagradの数式を比較すると
Adagradの方は学習率が動的ループが進めば進むほど学習率は低下するので
うまくいけば大域では幅広く最小値を探し出し、
最小値付近で素早く収束すると予想できる。

また初期の勾配が大きいと学習率の低下が大きいので、
繊細な学習率の初期設定が必要。

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 gradientdecent(init,rate):
    eps = 1e-5
    N = 1000
    v = np.linspace(0,R,div)
    arrf = f(v)
    arrg = g(v)
    diff = np.gradient(arrf,R/div)
    difg = np.gradient(arrg,R/div)
    x1 = x2 = round(div/R * init) 
    
    for i in range(N):
            
        n_x1 = x1 - rate * div/R * diff[np.int(x1)]
        
        if abs(n_x1 - x1)*R/div < eps:
            print("{0}\ngradientdicent {1}".format(rate,i+1),end="  ")
            break
        x1 = n_x1
        if i==N-1 :print("{0}\ngradientdicent {1}".format(rate,N),end=" ")
    
        
    for i in range(N):
            
        n_x2 = x2 - rate * div/R * difg[np.int(x2)]
        
        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

def adagrad(init,rate):
    eps = 1e-5
    e = 1e-8
    N = 1000
    v = np.linspace(0,R,div)
    arrf = f(v)
    arrg = g(v)
    diff = np.gradient(arrf,R/div)
    difg = np.gradient(arrg,R/div)
    x1 = x2 = round(div/R * init) 
    sum_x1 = sum_x2 = 0
    
    for i in range(N):
        
        sum_x1 += diff[np.int(x1)]**2
        n_x1 = x1 - (rate * div/R * diff[np.int(x1)]/np.sqrt(sum_x1+e))
        
        if abs(n_x1 - x1)*R/div < eps:
            print("adagrad       ",i+1,end="  ")
            break
        
        x1 = n_x1
        if i==N-1 :print("adagrad       ",N,end="  ")

    
        
    for i in range(N):
        
        sum_x2 += diff[np.int(x2)]**2
        n_x2 = x2 - (rate * div/R * difg[np.int(x2)]/np.sqrt(sum_x2+e))
        
        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

ratelist = [0.001,0.01,0.1,0.2,0.3,0.4,0.5,0.7,1]

for i in ratelist:
    print("({0[0]:.4f},{0[1]:.4f},{0[2]:.4f)}".format(gradientdecent(0.5,i)))
    print("({0[0]:.4f},{0[1]:.4f},{0[2]:.4f)}\n\n".format(adagrad(0.5,i)))

結果

学習率
最適化法 更新回数(f, g)(最小値, f収束値x, g収束値x)

0.001
gradientdicent  1000  1000  (0.0034, 0.6730, 0.6262)
adagrad     1000   1000  (0.0346, 0.5581, 0.5299)

0.01
gradientdicent  298   529  (0.0000, 0.6995, 0.6990)
adagrad    537   1000   (0.0001, 0.6989, 0.6878)

0.1
gradientdicent  39  74   (0.0000, 0.7000, 0.6999)
adagrad     17   49  (0.0000, 0.7000, 0.6999)

0.2
gradientdicent  19   39   (0.0000, 0.7000, 0.7000)
adagrad    2   17   (0.0000, 0.7000, 0.7000)

0.3
gradientdicent  12   26  (0.0000, 0.7000, 0.7000)
adagrad    11   9   (0.0000, 0.7000, 0.7000)

0.4
gradientdicent  8   19   (0.0000, 0.7000, 0.7000)
adagrad    12   3  (0.0000, 0.7000, 0.7000)

0.5
gradientdicent  2  15  (0.0000, 0.7000, 0.7000)
adagrad    12   8   (0.0000, 0.7000, 0.7000)

0.7
gradientdicent  13   10  (0.0000, 0.7000, 0.7000)
adagrad    11   12  (0.0000, 0.7000, 0.7000)

1
gradientdicent  1000  3   (0.0403, 0.4992, 0.7000)
adagrad    10   12   (0.0000, 0.7000, 0.7000)


パラメータをコントロールして目当ての値で最小に収束するようにしたが、
sin関数は別の凹へ移動してしまうことがあったので、
局所的な最小値(極小)で収束してしまう特徴はどちらでもありそうです。

またgradientdecentでは学習率を上げると発散しそうな特徴も見られた。

adagradの場合は徐々に学習率が減少するので、発散を防ぎ、
より確実に速く収束する可能性はあるが、
収束が遅くなることもあるのがデータから見て取れる。


先日のTensorFlow機械学習結果で正答率が低かったのは
対数関数をフィット出来なかったからだろうか??