記憶制限準ニュートン法、最適化手法の相互の関連性、そして私が感じたこと

授業を聞いててなかなか興奮したので、これまでのおさらいとともにメモメモ。

ニュートン法

ニュートン法は目的関数を2次で近似したものだったが、目的関数が2次でないと、ヘッセ行列が正定値行列になるとは限らず、ニュートン方向が降下方向になる保証がない。なので、実用上は、降下方向になるような他のアルゴリズムで動かしながら、最適解の近くにきたなーと判断すれば、ニュートン法に切り変えるということがされていたりするらしい(局所二次収束性を持っているから、最適解の近くだと収束が非常に速い)。

準ニュートン法

準ニュートン法は、ニュートン法の欠点である「降下方向になるか分からない」という欠点をどうにかしよう、という考えのもと作られたアルゴリズム。目的関数の勾配方向になるようなベクトルを作り出してやる。そのときに、勾配をテーラー展開によって近似し、ヘッセ行列の近似を計算できるようにした*1。このときに、セカント条件というものを満たすようにしないといけないが、この条件を満たすようなものは無数に存在する。それゆえに、様々な計算方法、アルゴリズムが提案されている。授業では対称ランクワン行列というものを使った方法があったし、教科書にはDFP公式、BFGS公式などがある(BFGS公式を使った準ニュートン法はRのoptim関数にも実装されている)。

ニュートン法は、局所二次収束という性質を持っていたが、準ニュートン法も(まあ、いろいろと条件を課すと)超1次収束という1次収束と2次収束の間くらいのスピードで収束するという性質を持っていて、これは現実的に使える速度らしい。

また、ヘッセ行列の近似ではなく、「どうせ逆行列求めるんだから、逆行列のほう近似すればよくね?」という発想のもとで考えられた方法もあり、Sherman-Morrison公式などがある。

記憶制限準ニュートン法

準ニュートン法の欠点としては、前回のヘッセ行列の近似、またはヘッセ行列の逆行列の近似を記憶しておかないといけないということがある。N次の最適化問題だとすると、メモリ領域として $O(N^2)$ 必要だということである。最近の解かないといけない問題は次元がすごく大きくなってきており(自然言語処理とかね)、現実的な問題だとそもそも動かせないという問題がある。。。

そこで、「陽に行列を持っておかないで、ベクトルでどうにかできないか?」という発想で生まれたのが、この記憶制限準ニュートン法である。行列とベクトルの積を、ベクトルの内積計算に落としてあげることで、行列を持つ必要がなくなる。ただ、この方法だとこれまでのベクトルの履歴を全部持っておかないといけないので、メモリに載せる量としては変わらない。ここまでは。

しかし、我々が解かないといけない問題は非線形最適化問題であり、「ずーっと前のベクトルの情報をいつまでも持っていても仕方がないだろjk」という考えのもとt期前までのベクトルの情報しか持たないでおこうというのが記憶制限準ニュートン法である。

記憶制限準ニュートン法の要点をまとめておくと

行列を陽に持ちたくないので、ベクトルの内積計算に落とす
ベクトルの履歴を全部持っておくのは無駄なので、tステップ前までしか持たないよ

というものである。

授業中「ニュートン法で近似、準ニュートン法で近似の近似、記憶制限準ニュートン法で近似の近似の近似。それでうまく動くんですかねえ?」という疑問というかそんなのが湧いたので、質問してみた。結論としてはうまくいきそうな感じである。なんでかというと、tステップ前までしか持たない、というのをやめればそれは形を変えた準ニュートン法と等価な方法であり、t=1とした場合は共役勾配法と等しくなる。つまり、何ステップ前まで覚えておくかのtというのをパラメータとして、共役勾配法と準ニュートン法の間をいったりきたりできる、ということである。そう説明ができるとなるとちゃんと動きそうな気がしてきた!!

そして、最近はどうなのか?

準ニュートン法までは行列が必要だったから、記憶制限準ニュートン法でベクトルだけにした。しかし、最近はもっと少なくできない?というさらに欲深い(?)方法が流行っている(らしい)。ベクトルよりさらに少なく、というともうスカラーしかなく目的関数の値の履歴のみを持つというものである。その方法の一つにNelder-Mead methodというのがある。これはこの前書いた。
www.yasuhisay.info
Optimaという最適化の人たちが読むらしいジャーナルがあるそうだが、それにも特集が組まれていたようである(印刷されたものが授業中に配られた)。まあ、最適化理論の研究をしている先生たちにとっては、関数値しか使わないとあんまり強いこが言えないので、(先生にとっては)面白くなさそうな感じではあったようだが。

この手法だと、ベクトルすらいらないので、100万変数とかあるような最適化問題も動かすことができるようになる。

考察

最適化理論の講義ではこれまで

大域的収束性、局所的収束性の定義
収束のスピードの仕方の種類
直線探索の方法(Armjo、Wolfe)
(一次モデルの)最急降下法
共役勾配法
ニュートン法
- 準ニュートン法
- 記憶制限準ニュートン法
Nelder-Mead method

などというものの理論を習ったり、自分で実装してみたりした。しかし、まあなんというか勉強すれば勉強するほど、問題に適した最適化手法を選択する必要があるなあ、というのを強く感じる結果となった。回帰みたいな問題であれば、上に書いたような手法使わなくても閉じた形で出てくるし、正則化項を付けても閉じた形で出てくるが、オンライン学習を使えば、とても簡単に実装までいくことができる。隠れ変数があるような問題では、対数尤度関数をそのまま上の手法に投げるととんでもなく大変なことになるが、EMアルゴリズムを使うと局所的収束性を保証できるようなものになって、現実に使えるような問題になる。

そんな感じで