読者です 読者をやめる 読者になる 読者になる

りんごがでている

何か役に立つことを書きます

JuliaによるNelder-Meadアルゴリズムの実装

Optim.jlというJuliaの関数最適化パッケージの出力が気になったのでプルリクエストを投げたら、ちょっと議論になり色々Nelder-Meadアルゴリズムを調べる事になってしまい、その副作用で少し詳しくなったのでJuliaで実装を書いてみました。Optim.jlの実装より高速だと思います。そのパッケージがこちらです: ANMS - Adaptive Nelder-Mead Simplex Optimization

Nelder-Mead法というのは、ご存じの方はご存知のように、n変数の関数の最適化をする際にn+1点からなるsimplex(単体)を変形させながら最小値をgreedyに探索するアルゴリズムです。

アルゴリズム自体は1960年代がある古い古い方法で、数々の亜種が存在します。 今回実装したのはそのうちの比較的新しい Adaptive Nelder-Mead Simplex (ANMS) (Gao and Han, 2010) というものです。 これは、simplexの変形に関わるパラメータを関数の次元によって変えることで、より関数の評価回数が少なくて済むようになっています。 実装自体も最初のパラメータを次元に応じて変える以外はとくに特別なことはしていないため、とても簡単です。

詳細は元論文に譲りますが、simplexの変形は以下の5つからなります。

  1. Relection:  x_r = c + \alpha (c - x_h)
  2. Expansion:  x_e = c + \beta (x_r - c)
  3. Contraction:
    1. Outside:  x_c = c + \gamma (x_r - c)
    2. Inside:  x_c = c - \gamma (x_r - c)
  4. Shrink:  x_i = x_l + \delta (x_i - x_l) \quad \text{for} \quad i \ne l

ここで、 x_h は最大値を取る頂点("h"igh)、 x_l は最小値を取る頂点("l"ow)、 cは最大値を取る頂点を除くsimplexの全頂点の平均("c"entroid)として定義されています。また、 \alpha, \beta, \gamma, \deltaは変形のパラメータになります。 各頂点の値によって、上の変形のうちのひとつを選択し、新しいsimplexとします。 それを繰り返すことで、徐々にsimplexを最小値付近に近づけて行き、ある収束条件や最大反復回数を満たしたところで終了とします。 そのsimplexの動きから、アメーバ法などと言われることもあります。

Reflectionの図

Nelder Mead1 Simplexの動きの図

ANMSでは、nを関数の次元として、変形のパラメータを以下のように取ります。

  •  \alpha = 1.0
  •  \beta = 1.0 + \frac{2}{n}
  •  \gamma = 0.75 - \frac{1}{2n}
  •  \delta = 1.0 - \frac{1}{n}

これらの次元に応じたパラメータにより、高次元の関数ではあまり効率的でない変形が起きにくいようになっています。

さらに、今回書いた実装では、

  • simplexの頂点を関数値に応じてソートし、 x_l x_hなど必要な頂点をすぐに取ってこれるようにしている
  • shrink以外の変形では、1頂点のみしか移動しないため、平均 cの計算を差分のみ行う

ようにして、高次元でさらに高速になるようにしています。

一気呵成に書き上げてまだよく検証していませんが、実装も200行ほどとコンパクトでコメントも多めに入れたので、効率的な実装の参考などにお役立て下さい。

https://github.com/bicycle1885/ANMS.jl/blob/master/src/ANMS.jl

参考