前回の記事でよく知られている勾配降下法のアルゴリズムを書きました。

しかし私が勾配降下法のコードを書いて遊ぶときには、最近は次のアルゴリズムを使っています。

前回の差分に係数を乗じたのが次の差分になりますが、その係数は前回の勾配と今回の勾配の比 $\frac{g(x_t)}{g(x_{t-1})}$ から計算できる値 $\alpha(\frac{g(x_t)}{g(x_{t-1})})$ です。関数 $\alpha(z)$ の定義中に怪しげなハードコーディングされた数値がありますが、次元を持ったパラーメータはありません。

説明
例
まとめ
ソースコード
2020/08/16 追記
2020/09/22 追記

説明

このアルゴリズムの説明のためにまずは $\alpha(z)$ を恒等関数 $\alpha(z) = z$ としたときのアルゴリズムを示します。

これはAdadeltaに似ていて、次元を持ったパラメータがないというメリットをAdadeltaから引き継いでいます。

$\alpha(z) = \frac{2}{1 + \exp^{k(1 - 3z)}} - \frac{1}{2}$ はグラフにするとこんな形をしています。中心付近は恒等関数の傾きを少しだけ急にしたもので、中心から離れるとなめらかに頭打ちになるようにしたものです。シグモイド関数の中心をずらして、少し傾きを急にしたものでもあります。

f:id:suzuki-navi:20200521215723p:plain

シグモイド関数 $\frac{1}{1 + \exp^{-z}}$ と似ていますが、シグモイド関数の値域 0〜1 を少し広く少し上の -0.5〜1.5 にずらし、横方向の中心もずらし、傾きを少し急の1.5付近にし、 $\alpha(0) = 0$ となるように調整したのがこの関数です。

αのポイントその1

$z$ が -0.3 ぐらいから 1.0 ぐらいまでは $\alpha(z)$ は $z$ とほぼ比例した値になっています。傾きは1よりも大きいため、勾配が同じ値が続いている場合に徐々に降下が加速していく効果があります。学習率が小さすぎる場合に自動で大きくしてくれることになります。

αのポイントその2

$z$ が1よりも大きいと $\alpha(z)$ は徐々に1.5に頭打ちになります。勾配が急激に大きくなってもそれに合わせて差分も急激に大きくすることはせずに、今まで通りのペースで降下していくことを意味します。勾配が急激に大きくなったからといって最適値が遠のいたことにはならないためです。この機能がないと、 $f(x) = -\frac{1}{x^2+0.001}$ のような最適値の近くが崖みたいになっている問題では、最適値にある程度近づいたら突然ぜんぜん違う場所に跳ね飛ばされてしまいます。正の方向で頭打ちにすることで跳ね飛ばされてしまうのを防ぐことができます。

αのポイントその3

$z$ が負の方向に0から離れても $\alpha(z)$ は-0.5が下限となります。 $z$ が負というのは、最適値を通り過ぎたことを意味するので、中間地点に戻るためです。これは学習率が大きすぎる場合に自動で小さくしてくれることにもなります。もし $\alpha(z)$ が-1になってしまうと、前回の場所に戻ってしまい意味がないし、-1よりも小さな値ではさらに戻りすぎてしまい、最適値から遠くに跳ね飛ばされてしまいます。

注意

前回の勾配と前回の差分を使うので、初回計算時の「前回の勾配」 $g_{-1}$ と「前回の差分」 $x_0 - x_{-1}$ を適当に決める必要があります。これが他の既存のアルゴリズムにはない次元を持ったパラメータとなりますが、大きくずれていたとしても徐々に調整されます。

例

最急降下法で成功する例

$f(x)=x^2$ の最適値をシンプルな最急降下法で $\eta=0.2$ で試したときの例です。1列目の整数はステップ数で0は初期のランダム値です。2列目は $f(x)$ 、3列目は $x$ です。

0 +0.3978 +0.6307
1 +0.1432 +0.3784
2 +0.0516 +0.2271
3 +0.0186 +0.1362
4 +0.0067 +0.0817
5 +0.0024 +0.0490
6 +0.0009 +0.0294
7 +0.0003 +0.0177
8 +0.0001 +0.0106
9 +0.0000 +0.0064

最急降下法で同じパラメータでも別の最適化問題に適用すると失敗する例

$f(x)=1000x^2$ を同じく最急降下法で $\eta=0.2$ で試したときの例です。発散してしまうのがわかります。

0 +473.7679 +0.6883
1 +75424317.2784 -274.6349
2 +12007626735041.4730 +109579.3171
3 +1911626183845337600.0000 -43722147.5210
4 +304332800094361640000000.0000 +17445136860.8665
5 +48450086107822480000000000000.0000 -6960609607485.7180
6 +7713302158451450000000000000000000.0000 +2777283233386802.0000
7 +1227965416927629500000000000000000000000.0000 -1108136010121334140.0000
8 +195493322340295550000000000000000000000000000.0000 +442146268038412300000.0000
9 +31122732409897394000000000000000000000000000000000.0000 -176416360947326500000000.0000

最急降下法でパラメータを適切に変更して成功する例

同じ $f(x)=1000x^2$ を $\eta=0.0002$ にして試したときの例です。 $\eta$ を問題に合わせて適切に設定すればうまく収束します。

0 +467.8934 +0.6840
1 +168.4416 +0.4104
2 +60.6390 +0.2462
3 +21.8300 +0.1477
4 +7.8588 +0.0886
5 +2.8292 +0.0532
6 +1.0185 +0.0319
7 +0.3667 +0.0191
8 +0.1320 +0.0115
9 +0.0475 +0.0069

自作アルゴリズムでパラメータを変更しなくてもどちらの問題に対しても成功する例

$f(x)=x^2$ と $f(x)=1000x^2$ を自作のアルゴリズムで試したときの例です。どちらもうまく収束しています。2つ目はいったん大きく通り過ぎてしまいますが、その後学習率が小さくなるように自動調整されています。

0 +0.9596 +0.9796 
1 +0.3209 +0.5665
2 +0.0407 +0.2017
3 +0.0000 +0.0057
4 +0.0000 -0.0013
5 +0.0000 +0.0003
6 +0.0000 -0.0001  
7 +0.0000 +0.0000 
8 +0.0000 -0.0000
9 +0.0000 +0.0000

0 +673.4935 +0.8207
1 +243131.1493 -15.5927
2 +54552.9726 -7.3860
3 +2009.8992 -1.4177
4 +40.1919 +0.2005
5 +2.3813 -0.0488
6 +0.1215 +0.0110
7 +0.0064 -0.0025
8 +0.0003 +0.0006
9 +0.0000 -0.0001

勾配が急激な問題での例

$f(x) = -\frac{1}{x^2+0.001}$ というグラフは以下のような形をしています。最適値付近が深い穴になっています。

f:id:suzuki-navi:20200521215810p:plain

中心付近を横方向は拡大、縦方向は縮小したグラフ。

f:id:suzuki-navi:20200521215831p:plain

シンプルな最急降下法だと、最適値付近の崖で遠くに跳ね飛ばされ、なだらかな領域に入ってしまい、その後はなかなか降下しません。

0 -2.4550 +0.6374
1 -1.2349 -0.8993
2 -8.0640 -0.3507
3 -0.0130 +8.7720
4 -0.0130 +8.7714  
5 -0.0130 +8.7708
6 -0.0130 +8.7702 
7 -0.0130 +8.7696 
8 -0.0130 +8.7690 
9 -0.0130 +8.7685 
10 -0.0130 +8.7679 
11 -0.0130 +8.7673 
12 -0.0130 +8.7667 
13 -0.0130 +8.7661 
14 -0.0130 +8.7655 
15 -0.0130 +8.7649  
16 -0.0130 +8.7643
17 -0.0130 +8.7637
18 -0.0130 +8.7631
19 -0.0130 +8.7625

自作アルゴリズムですと、崖で通り過ぎてしまうこともありますが挽回が速いです。

0 -1.1543 +0.9302     
1 -1.2183 +0.9054      
2 -1.3131 +0.8721                             
3 -1.4609 +0.8268                                                                                                           
4 -1.7099 +0.7641
5 -2.1859 +0.6756
6 -3.3267 +0.5474
7 -7.8056 +0.3565
8 -168.3036 +0.0703
9 -7.6971 -0.3591
10 -7.9418 -0.3534
11 -8.2849 -0.3460
12 -8.7787 -0.3360
13 -9.5170 -0.3226
14 -10.6837 -0.3043
15 -12.6921 -0.2789
16 -16.6705 -0.2429
17 -26.8675 -0.1903
18 -73.9997 -0.1119
19 -967.3288 +0.0058

まとめ

「前回の勾配」 $g_{-1}$ と「前回の差分」 $x_0 - x_{-1}$ を適当に決める必要はありますが、ステップを踏むごとに調整されていくので、ランダムな値でも、スケールが大きく間違っていてもだいたい大丈夫で安心感があります。適当というのは適切でなくてもいい加減でもたいていは大丈夫ということです。

差分の計算がちょっと複雑なのでので、計算量はちょっと多いかもしれないです。

自分のアルゴリズムがなんという名前のアルゴリズムに相当するのかはわからないです。だいたいうまくいく感じがあって、使い勝手がよくて、自作のコードではデフォルトでこれを使っています。