2012年10月31日水曜日

確率的系統樹探索を行うソフト

自分用メモも兼ねて。

最尤法で系統樹探索を行うプログラムだと大体山登り法が採用されているが、この山登り法は常に坂を上り続けることしかしないため(貪欲アルゴリズム)、系統樹空間が巨大で多峰だと局所的最適解に陥りやすい。

これを解決するため、複数の初期系統樹からの山登りとかをやったりするが、ほかにも「確率的探索法」を用いて系統樹探索を行うやり方もある。

系統樹探索において用いられる確率的探索法は3つあり、「ベイズ法」「遺伝的アルゴリズム」「焼き鈍し法」である。

ベイズ、GAはMr. BayesだったりGarliだったりがあるけど、焼き鈍し法についても実装したプログラムがあるようだ。

http://www.stat.osu.edu/~lkubatko/software/ssa/ssa.html

焼き鈍し法では、探索の初期において「尤度の山を下る」ことも許容する。これによって局所的最適解にトラップされることを防ぐわけだ。探索の終盤では山を下ることはほとんどせず、上を目指して上り続ける通常の山登り法にシフトする。

多分、焼き鈍しではベイズみたいに棄却率を用意して、それを探索の段階に応じて調整してるんだと思う。

ちょっとソースコード見て、自分の並列化しているプログラムに転用できそうだったら試してみようかな。

0 件のコメント: