科学と家事とプログラミング (python を中心に)

python 温度計測 湿度計測 DS18B20 USB9097

多変数最適化の Nelder-Mead は、なかなか使い勝手が良いのです

多変数最適化のアルゴリズムの一種である Nelder-Mead は、なかなか使い勝手の良いアルゴリズムですね。 汎用的に使える(対象が最小二乗に限定されない)ことに加えて、 微分情報を使わないところも魅力です。 評価関数の性格が多少悪くても、上手に最適をみつけてくれる、便利屋さんといったところでしょうか。

Nelder-Mead のお勧めバージョン

Nelder-Mead には、いろんな改良/拡張が存在しますが、 場合分けの見た目の安心感? から、以下の 5 種類の動作を含んだ設計がお勧めです。

  1. reflection
  2. expansion
  3. inside-contraction
  4. outside-contraction
  5. shrinking

細かく言うと、最悪, 2番悪, 最良 の 3点の情報を使って 7 通りに場合分けしたあと、 動作が同じになるところをまとめると、最終的に 5 ケースとなります。 例えば http://adl.stanford.edu/aa222/lecture_notes_files/chapter6_gradfree.pdf

アルゴリズムの妥当性と試験について

この手のアルゴリズムは、経験則の寄せ集め的なところがあって、 絶対的な正解という考え方には馴染まない気がします。 適用限界を明示するのが難しい。 あと設計やコーディングに間違いを含んでいても、 なんとなく動いてしまって、しかも、本来と異なる経路で最適値に収束したりして、 外部仕様を定めにくいですね。つまり、ブラックボックス的な試験設計は難しい。 開発手法(管理)の観点からは、興味深い対象かもしれません(扱いが難しいということ)。 というわけで、ホワイトボックス的な試験に重点を置くのが良さそうです。とにかく全てのパスを通す。 このとき、見やすい図を作って直感的に動作を確認するのは、 そう悪くない方法かと思ったりもします。例を下図に示します。

f:id:sken20k:20180513141435j:plain

適当な評価関数(2次元)を用意して、乱数で初期値を選ぶようにして、 見やすい図が得られるまで乱数のシードをいろいろ試しました。。 スライダーなどの GUI で初期値を選べるようにすると、おもしろいデモが 作れそうですね。

パラメータの一部を固定して評価したいとき

最適化の問題をあつかっていると、一部のパラメータを固定して推定したい。 という場面に出くわすことがあります。 パラメータの組み合わせ毎に最適化対象の関数を定義しはじめると、 評価関数だらけになってしまって、何をやってるのか分からなくなりがちです。 最適化のルーチンの I/F に手を加えて、要素毎に推定する/しないを指定するフラグを追加 しても良いのですが、 python のようなインタープリターを使うのであれば、 固定パラメータを補う関数を動的に生成するのも悪くないですね。 こうすれば、ベーシックな最適化ルーチンに手を加えずシンプルに保ったまま、 目的を達することができます。

落穂ひろい

Nelder-Mead 以外で、実用の見地から押さえておきたい最適化アルゴリズムは、 やっぱり Levenberg-Marquardt でしょう(LM法)。 適用できる問題は最小二乗形式に限定されますが、 変数の数が多めのデリケートな問題でも、良好な結果が得られることが多いですね。 推定誤差や correlation を評価がしやすいところもポイントが高いです。 注意が必要なのは、ダンピングファクターの初期値の調整くらいでしょうか。 実装にもよりますが、ダンピングファクターと収束判定の関係を理解していないと、 使いこなせない場面が、時々あります。 最適化ルーチンをブラックボックス的に利用するのは良いのですが、こういう 特性を理解した上でないと、使いこなせないこともある。 ブラックボックスの表面に、そういう細かな特性を認識できているかどうかで話が大分違ってきそうです。 個々のアルゴリズムや理論の前提条件や適用限界に注意を促したり、それらを身に付けるための方法論が 求められる。そう思う次第です。