TensorFlowのOptimizerを比較する（ベジェ曲線編）

「TensorFlowを使って、点列を補間するベジェ曲線を求める」というテーマで、[（その１）](http://qiita.com/cnloni/items/00292a962bb131da9787)と[（その２）](http://qiita.com/cnloni/items/5045b3e3a335cb933e23)では、TensorFlowの各種クラスと関数の効用を調べることができた。しかしながら、最適化の方法については、GradientDescentOptimizerという最急降下法を用いた最適化クラス（Optimizer）だけを使用していた。TensorFlowには、これを含めて８種類のOptimizerが用意されているのだが、実際にその用途と性能を比較見当した例は、あまり見当たらない。そこで、この記事では、ベジェ曲線を最適化するという問題を利用して、各種のOptimizerクラスを比較してみることにする。

>Deep Learningに即したOptimizerの比較を「[TensorFlowのOptimizerを比較する（mnist_expert編）](http://qiita.com/cnloni/items/d936cd8c532e3a4dd687)」として投稿したので、ご参考に

ところで、前の記事で考察したように、ベジェ曲線の最適化と言う問題には、２種類の最適化パラメータ（TensorFlowの用語で言えば、Variable）がある。

1. $\\{\boldsymbol{a}_k:k=0,3\\}$
2. $\\{t_i:i=0,N-1\\}$

ここで、1.はベジェ曲線の4個の制御点、2.はデータ点に対応する媒介変数（Nはデータ点の総数）である。これは、最適化の条件としては、相当に厳しい状況である。実際、GradientDescentOptimizerでは、２種類のパラメータを同時に最適化することはできなかった。しかし、これを逆手にとると、Optimizerの有効性を検証するには好適な環境とも言えるのである。そこで、ここでは２段階で、各種のOptimizerを検証する。

検証1. 制御点のみの最適化
検証2. 制御点と媒介変数の同時最適化

検証1.は、通常の最適化であり、構造的にもニューラルネットワークの最適化と類似している。

以下に、現段階でTensorFlowに登録されている８種類のOptimizerを示す。検証結果もここで示しておく。このうち、MomentumOptimizerは、momentumという引数を設定する必要があること、AdagradDAは、総ステップ数を引数として必要であることから、ここでは検証を行わなかった。また、上記のように、それぞれの方法で調整可能なデフォルト値のままである。なお、使用したTensorFlowのバージョンは、0.10.0rc0である。

| Optimizer | 検証１ | 検証２ | 寸評 | 論文へのリンク |
|:-------:|:-------:|:-------:|:-------:|:-------:|
| [GradientDescent](https://www.tensorflow.org/versions/r0.11/api_docs/python/train.html#GradientDescentOptimizer) | ○ | × | 学習係数が大きいと発散 | ー |
| [Adadelta](https://www.tensorflow.org/versions/r0.11/api_docs/python/train.html#AdadeltaOptimizer) | △ | × | 収束が遅い | [pdf](https://arxiv.org/pdf/1212.5701v1.pdf) |
| [Adagrad](https://www.tensorflow.org/versions/r0.11/api_docs/python/train.html#AdagradOptimizer) | ◎ | × | 収束が速い。 検証１はFtrl法と同じ | [pdf](http://www.jmlr.org/papers/volume12/duchi11a/duchi11a.pdf) |
| [Adam](https://www.tensorflow.org/versions/r0.11/api_docs/python/train.html#AdamOptimizer) | ◎ | △ | 最も収束性が優れる。 検証２はRMSProp法に類似 | [pdf](https://arxiv.org/pdf/1412.6980.pdf) |
| [Ftrl](https://www.tensorflow.org/versions/r0.11/api_docs/python/train.html#FtrlOptimizer) | ◎ | △ | Adam法に次いで良い。 検証１はAdagrad法と同じ | [pdf](https://www.eecs.tufts.edu/%7Edsculley/papers/ad-click-prediction.pdf) |
| [RMSProp](https://www.tensorflow.org/versions/r0.11/api_docs/python/train.html#RMSPropOptimizer) | △ | × | 収束が遅い | [pdf](http://www.cs.toronto.edu/%7Etijmen/csc321/slides/lecture_slides_lec6.pdf) |
| [AdagradDA](https://www.tensorflow.org/versions/r0.11/api_docs/python/train.html#AdagradDAOptimizer) | ー | ー |  ー | Adagradに同じ |
| [Momentum](https://www.tensorflow.org/versions/r0.11/api_docs/python/train.html#MomentumOptimizer) | ー | ー | ー | ー |

もちろん、ここで行った検証は「ベジェ曲線の最適化」という特定の問題に限ったことであり、それぞれの方法において調整が可能な特徴量についてはデフォルトのままである。さらに、この問題を機械学習にあてはめてみると、極めて少数の教師データ（19個）を使っていることになる。従って、ここで得た知見がニューラルネットワークの計算に、そのまま適用できるという保証はない。この検証で成績が悪かった方法も、大量の教師データに対してなら、うまく適用できる可能性がある。しかし、少なくとも、AdamOptimizerとFtrlOptimizerは、このような過酷な状況においても最適化を完了できた優れた方法であると言える。ブラックボックスになりがちなOptimizerに対して、限定的ではあるが、確かな情報を得ることができた。以下、検証の詳細を述べる。


## 検証１
[（その２）](http://qiita.com/cnloni/items/5045b3e3a335cb933e23)の図9のように得られた、データ点に対応する媒介変数の値$\\{t_i\\}$を固定し、制御点だけを最適化パラメータにした場合の収束の様子を、6種類の方法で比較する。

### GradientDescentOptimizer
GradientDescentOptimizerは、前の２つの記事で用いた最急降下法である。図10に、学習係数（learning_rate）の違いによる、収束の違いを示す。縦軸の$D$は、データ点とベジェ曲線の距離の２乗和の平均であり、最適化の目的関数である。機械学習のLoss関数に対応する。$D_0$は、収束値を表す。$D-D_0$の対数値が、いずれの場合も直線状になっている。これは、ステップを重ねるごとに指数関数的に収束していることを表している。薄い緑の領域は、収束値との誤差が１％以内の領域であり、この範囲に入れば収束したとみなすことにする（これ以降の図でも同様）。

![fig10.png](https://qiita-image-store.s3.amazonaws.com/0/52659/32444e20-4415-7c1b-d794-0e7f592f5f06.png)

ここで、

$$ D - D_0 = a \exp{(-\mu * steps)} \tag{1}$$

であるとき、$\mu$を収束率と呼ぶことにする。図10における直線の傾きが収束率である。収束率を学習係数に対してプロットしたのが、図11である。

![fig11.png](https://qiita-image-store.s3.amazonaws.com/0/52659/e10ef4d3-812b-68bd-811c-3effe0ea4508.png)

学習係数が6.7のあたりまで、収束率は学習係数に比例する。そして、学習係数が6.9以上では発散する。最急降下法は、$f$を多次元ベクトル$\boldsymbol{x}$の関数である目的関数としたとき、

$$ \boldsymbol{x_{n+1}} - \boldsymbol{x_n} = - \eta \cdot \nabla f \tag{2}$$

という表式で表現される。ここで、$\eta$は学習係数である。収束率と学習係数が比例することを見るために、最急降下法の簡単な例、$f=x^2$を考えてみる。この例では、収束率と学習係数は比例し、$\mu = 4\eta$の関係になる。同時に、$\eta>1$では発散が起こる。このように、図10は最急降下法の特徴的な振る舞いを示しているのである。

### AdagradOptimizer & FtrlOptimizer 
AdagradOptimizerの最適化の様子を図12に示す。Adagradは確率的勾配降下法のひとつである。最急降下法と同様に、非常にきれいな指数関数的収束を行うことが分かる。ところが、FtrlOptimizerによる結果も、図12とほとんど同じ結果が得られる。同じ図にプロットしても、線の太さに隠れてしまうほどである。

![fig12.png](https://qiita-image-store.s3.amazonaws.com/0/52659/91931ab6-736c-022f-d452-64cbcfb28afa.png)

この結果からもとめた収束率を、学習係数に対してプロットしたのが、図13である（但し、これらの方法で用いる学習係数と最急降下法の学習係数の定義は同じではない。従って、図11と図13の横軸を直接、比較することはできない）。図13に示されるように、ふたつのOptimizerで得られた収束率の値は、完全に同じ補間曲線上に乗る。FtrlOptimizerの背景であるFTRL-Proximal Algorithmは、特定の条件では確率的勾配降下法と同等になることが分かっているが、この結果も同じように理解するべきなのだろう。もっと厳しい条件である検証２では、ふたつの方法は異なった結果をもたらす。

![fig13.png](https://qiita-image-store.s3.amazonaws.com/0/52659/628d63ab-1839-e8da-6d17-9c8f9aafc292.png)

図13において、補間曲線は次の式で与えられる。係数は、$ a = 0.155, b = 1.4 \times 10^{-4}$である。非常によくフィットしていることが分かる。コードを詳細に調べていないので、現段階では、この補間表式が当てはまる理由は分かっていない。

$$ \mu = a (1 - \exp{(- b \eta^2)}) \tag{3}$$

### AdamOptimizer
AdamOptimizerも確率的勾配降下法のひとつであるが、他の方法より新しい（2015年に発表）。図14は、図10や図12と同じスケールで収束の様子を示したものである。特徴的なことは、収束が指数関数的ではないことである。特に学習係数が10を越すと、目的関数の減少が単調ではなくなる。これは、Adam法が他の方法に比べて、少し複雑なアルゴリズムになっていることを示している。そのアルゴリズムの故に、検証２のような困難な状況でも収束することができるのだろう。

![fig14.png](https://qiita-image-store.s3.amazonaws.com/0/52659/9ad02bc8-d686-9504-d13e-e1b9c0390643.png)

Adam法は指数関数的な減少ではないが、他の方法との比較のため、縦軸が[-2,5]の範囲を直線で補完した傾きとして収束率を定義する。求めた収束率と学習係数の関係を図15に示す。学習係数の小さい領域では、収束率は比例して増加するが、しだいに上昇率が大きくなり、$\eta=12.4$でピークを取り、急激に減少する。

![fig15.png](https://qiita-image-store.s3.amazonaws.com/0/52659/d568c16c-104a-509a-20ce-5796679357ad.png)

面白いのは、最適化の方法は違っても収束率の最大値が、ほぼ等しいことである、最急降下法では収束率の最大値が0.133、Adagrad法とFtrl法では0.155、Adam法では0.154になる。このように、最適化の方法によらず収束率の最大値が似た値を取るのは、対象となるシステムの性質が反映されているのだろう。

| Optimizer | 最大収束率（検証１） | 最大収束率（検証２） |
|:-------:|:-------:|:-------:|
| GradientDescent | 0.133 | × |
| Adadelta | 5.6 $\times 10^{-4}$ | × |
| Adagrad | 0.155 | × |
| Adam | 0.154 | 2.2 $\times 10^{-4}$ |
| Ftrl | 0.155 | 1.8 $\times 10^{-5}$ |
| RMSProp | 4.9 $\times 10^{-3}$ | × |

### AdadeltaOptimizer & RMSPropOptimizer
Adadelta法とRMSProp法は、ともに2012年に発表されたもので、Adagradの改良版である。Adadelta法（図16）では、最も収束値に近くなった後、すこし目的関数が大きくなる。これに対し、RMSProp法（図17）では、収束値に近づいた後、目的関数はほとんど同じ値に留まる。このような違いはあるが、どちらの方法も、完全には収束しない。学習係数を小さくするほど収束値に近づく傾向はあるが、逆に収束の速度が遅くなる。それでも、収束値との誤差１％以内を収束とみなせば、学習係数を小さい領域では収束範囲に収まる。

![fig16.png](https://qiita-image-store.s3.amazonaws.com/0/52659/d953243d-69a2-0b47-bc5d-424a36afbebb.png)

![fig17.png](https://qiita-image-store.s3.amazonaws.com/0/52659/2c507b02-b520-d97b-fa61-5ae99e35a9d8.png)

両方の方法はともに指数関数型の収束ではなく、しかも勾配が急激に変化するので、ここでは収束率を以下のように定義する。

$$ \mu = 11.8 / steps_{1\%} \tag{4}$$

ここで、$steps_{1\%}$は、目的関数の値が誤差1%以内に入った時点のステップ数である。11.8という値は、最急降下法において、この定義で導出した収束率(4)と、指数関数の係数として定義した収束率(1)が一致するように定めている。こうして定めた収束率を、学習係数に対してプロットしたのが、以下の図18と図19である。Adadelta法では、収束率が学習率の2/3乗に比例するが、RMSProp法では、最急降下法と同様に学習率に比例する。収束範囲内で最大の収束率は、Adadelta法で 5.6 $\times 10^{-4}$、RMSProp法で 4.9 $\times 10^{-3}$であり、いずれも、ここで調査した他の方法に比べて著しく小さい。少なくともこのシステムでは、Adadelta法とRMSProp法は、収束性が劣ると言っても良いだろう。

![fig18.png](https://qiita-image-store.s3.amazonaws.com/0/52659/3118538b-e11d-48d8-750f-de6f99474e96.png)

![fig19.png](https://qiita-image-store.s3.amazonaws.com/0/52659/6f5f73a9-4b4d-6943-bc40-1f9077554c6b.png)

但し、これだけの結果で、AdadeltaとRMSPropを否定するの間違っている。これはあくまでも、この問題に限った結果である。検証１は、教師データの数が高々20個ほどであり、教師データが大量の場合には、また違った結果になるだろう。教師データに対する最適化が行き過ぎると過学習を招くことがある。収束性があまり良くないと言っても、過学習を避ける効果が出ているのだと理解することもできる。

## 検証２
検証２は、制御点４点と媒介変数列の両方について、同時に最適化を行う。「[TensorFlowを使って、点列を補間するベジェ曲線を求める（その２）](http://qiita.com/cnloni/items/5045b3e3a335cb933e23)」で判明したように、最急降下法（GradientDescentOptimizer）では、制御点の最適化に対しては学習係数が5.0、媒介変数列の最適化については学習係数が0.00001と、最適な学習係数が5万倍も異なる。このような最適化パラメータの性質の大きな違いは、確率的勾配降下法でも、大きな影響があるはずであり、収束することが困難であろうと予想された。ところが、実際には、Ftrl法とAdam法では、なんとか収束してしまったのである。

### FtrlOptimizer
図20は、Ftrl法における目的関数の変化である。検証１の式(4)と同じく収束値の1%以内に入ると収束したと定義した場合、学習係数が1.2の周辺で収束する。但し、収束と言っても収束値の0.3%程度まで近づくのがせいぜいであって、収束範囲に入るまで少なくとも70万ステップを要する。検証１でも、学習係数が1程度でなら同程度の遅さであるから、検証２における違いは、学習係数が大きい場合に収束しない要因が存在することである。

検証１では、Ftrl法とAdagrad法は完全に同じ結果を示した。しかし、検証２では、Adagrad法は200万ステップでも収束しない。図20に、Adagrad法（学習係数1.2）の結果を載せている（黒線）。

![fig20.png](https://qiita-image-store.s3.amazonaws.com/0/52659/6e85aaee-586c-b629-677c-2095f98c085d.png)

式(4)の定義で求めたFtrl法の収束率を、学習係数に対してプロットしたのが、図21である。学習係数が0.95から1.55の領域で収束し、1.2で最大の収束率を取る。収束率の最大値が$1.8 \\times 10^{-5}$という極めて小さい値になっている。実質的に収束と言えるのか微妙な結果ではある。

![fig21.png](https://qiita-image-store.s3.amazonaws.com/0/52659/a119ff5c-12b7-fc83-cb97-3009f9446251.png)


### AdamOptimizer
図22に、Adam法の収束の様子を示す。目的関数の値と、その収束値との差の対数は、最初は緩やかに減少し、ある時点より急激に減少する。そして、ある値の付近で振動する。振動を除くと、縦軸の変化は、図17に示したRMSProp法の変化と良く似ている。

![fig22.png](https://qiita-image-store.s3.amazonaws.com/0/52659/2f10f9cb-aecc-eafc-1e7f-f63531144c14.png)

図23は、Adam法の収束率を学習係数に対してプロットしたものである。収束率は学習係数にほぼ比例する。この様子も、検証１におけるRMSProp法の振舞い（図19）と良くにている。実際、比例係数は、この場合が$2.2 \\times 10^{-4}$であり、図19では$2.5 \\times 10^{-4}$である。おそらく、収束を加速されるアルゴリズムがRMSProp法と類似しているのであろう。収束率の最大値は$2.2 \\times 10^{-4}$であり、Ftrl法に比べると10倍ほど大きな（収束が速い）値である。

![fig23.png](https://qiita-image-store.s3.amazonaws.com/0/52659/04d99844-f308-1ffc-e283-9dd675025569.png)

## 変更履歴
* 2018-12-26: 図21を更新した。(3)式の変数名を交換した（a <-> b）。別の記事から参照するため