Home > Archives > 2010-04

2010-04

NelderのSimplex法のクラスを書いてみた

自分が直面している問題の中に,最小二乗法のような最適化処理が含まれている場合,
それを解くための多くの真面目な(?)方法では
自分が最小化したい関数のGradient(関数を各パラメタで偏微分したもの)だとか
Hessian(それらをさらに偏微分したもの)だとかが必要になるので,
それらの大量の数式を計算するコードを用意せねばなりません.
そういった部分の実装は後でちゃんとやりたいという思いはあるのだけれども,
とりあえずまずは簡易的な実装で動きを見てみたい,ということが度々あります.

そんなときに使える方法として“Nelderの滑降シンプレックス法(Downhill Simplex Method)”があります.
この方法は,n次元のパラメタ空間の中に(n+1)個の頂点を持つSimplexとよばれる多面体みたいなものを用意して,これを頂点位置を変えながら変形させていくことでパラメタ値を更新していく,という探索法です.
他の方法と比べて遅いものの,
Gradient等を必要としないので比較的簡単に試してみることができるのが(+アルゴリズムが直感的に分かりやすいのも)利点です.
で,この滑降シンプレックス法を使う機会が結構でてきたりしたので,基本動作部分をクラスにまとめてみました.

適当に動かしてみたサンプルの動作が↓のグラフです.
Nelder_Simplex(クラスとそれを使う適当なサンプルのソースコード)

データ点群(青)に対してsin波形な関数の当てはめを行っています.
赤がてきとーに与えた初期値での関数の様子です.(本当は,初期値はてきとーではダメ.)
どう見てもデータ点群に対するまともな初期値とは言い難い状態ですが,
走らせてみるとそこそこ頑張ってくれて,オレンジ色のグラフのようになりました.
この結果は初期値と比べると断然良いですが,もう少し頑張れそうなのに途中で力尽きた感があります.
そこで,滑降Simplex法での探索を,この結果を新たな初期値として再出発させてみると,
今度は緑色のグラフの結果に収束しました.

このように,滑降Simplex法(に限らずだと思いますが)では探索途中で動けなくなってしまう場合があるため,
止まった地点でSimplexを再構築して再出発させてみる必要があります.

パラメタ個数が少なくて計算時間があまり問題にならない場合や,他の解き方があるのだけれどもその実装を用意するのがめんどくさい,とかいう場面では結構使えると思います.

y = A*sin(B*x+C)+D の当てはめ

y = A*sin(B*x+C)+D の当てはめ

by nakiusagi3

  • Comments (Close): 0
  • Trackbacks (Close): 0

全方位,正20面体

ソフトエンジニアの佐藤君が試作しているのは正20面体.
ただの正20面体ではありません.
全方位映像を当社の多面体展開ソフトウエアで画像処理し,紙に印刷しています.
この分野は,いろいろ面白い応用があるように考えています.
後ほどみなさんに詳しくご紹介して行く予定です.
全方位画像の展開図を切り出して行く様子.

sato-100424a

組み立ての途中.

sato-100424b

どんなものが出来るのか...ここから先はまだ秘密なのです.

作っている佐藤君は,当社のご近所にある岩手県立大学ソフトウエア情報学部卒.
趣味でガンプラを作るという彼は,手先も器用.
ソフト開発のみならず メカの組み立て作業でも,時々活躍してくれます.

  • Comments (Close): 0
  • Trackbacks (Close): 0

Home > Archives > 2010-04

Search
Feeds
Meta

Return to page top