モンテカルロ法と生物の進化のアナロジー
投稿日: Oct 13, 2015 2:42:53 PM
ツイッターで「ＭＣＭＣと生物の進化は似てる」みたいな呟きがあったので，「いや本当に似てるのは逐次モンテカルロとか粒子フィルターのような粒子が分裂・消滅する方法（リサンプリングを伴う方法）のほう」と書きこんだら反響があったので，専門家には常識と思いますが，少し解説します．
いちばん類似性がはっきりするのは粒子フィルタで平滑化，すなわちその時点より過去だけでなく，未来まですべてのデータを仮定して推定を行う場合です．オンラインでなく，全部のデータを得た時点で，振り返って全体を推定しなおすという意味です．カルマンフィルタなら式の導出がめんどうになるだけですが，粒子フィルタではそうはいかず，色々なテクが提案されています．それはなぜか，という話．
粒子フィルタで平滑化を簡単に実装しようと思ったら，分裂・消滅の結果，最後の時刻に生き残っている粒子たちの「尻尾」，すなわち過去の時刻に辿った経路の集まりを「同時事後分布からのサンプル」と思えばよいようと考えるかもしれません．なぜそれがダメなのでしょうか．そこで出てくるのが木村資生の中立説とのアナロジーです．
簡単な例として，時系列の最初のほうで「同じくらい確かな解釈」に相当する経路がＡ，Ｂ２組あったとしましょう．ここで「組」というのは，ある時刻にある箇所の近傍を通過する経路の集まりを意味します．その後は全くデータがなく，すべての経路が同じだけの重みを受け取る（中立的）としましょう．すると，時系列がどんなに長くても，組Ａ，組Ｂの事後確率は同じはずです．
ところが，ここで，時系列が十分長くて，Ａ，Ｂを分けるのに使った時刻からずっとたっても計算が続き，何回も何回もリサンプリングの操作が（いまの場合意味がないのですが）行われるとします．すると，状況は「中立説」で出てくる壺からの復元抽出と一致します．そこで，粒子の数をＮとしたとき，1-exp(-t/2N) ｔ：ステップ数で決まる割合で「固定」が起きます．すなわち，ＡとＢの一方だけが生き残り，他方の事後確率は本来は0.5なのにゼロと計算されることになります（木村の有名な式では固定までの期間は2Nでなく4Nですが，係数が2倍なのは各個体に染色体が２本あるからですね）．これをみると，平滑化する時系列の長さに比例して粒子数Ｎを多くしなければいけないことがわかります．
実際の粒子フィルタではアダプティブに分裂・消滅を行わせるので，データが全然なければ，リサンプリングもなしになります．しかし，データが少しでもあればウェイトがついて分裂・消滅が起きるので，それに応じて上と同じことが起きてくるはずです．とくにデータの変化点などで大量に消滅がおきれば，見た目の個数は保っていても，その瞬間には有効な個数が減るので，いっそう悪いことになります．これは，集団遺伝学でいえば，集団のサイズの小さい時期があれば多様性が減少する，というのに対応するわけです．
このような現象に対応するものはＭＣＭＣにはありません．逆に事後確率の大きいほうに揺らぎながら行く，という「適応的」な面はどっちにもあります．上級コースになると，ＭＣＭＣと逐次モンテカルロは組み合わせて使うこともできますが，最初のうちは違いのほうに着目したほうがよいでしょう．たとえば，ＭＣＭＣは仮想時間無限大で収束しますが，逐次モンテカルロは粒子数無限大で収束します．
＊ ＊ ＊ ＊ ＊
まあ，生物の進化にインスパイアされた「遺伝的アルゴリズム」とか「進化計算」という分野が別にあるわけで，そこで行われていることと逐次モンテカルロや粒子フィルタがよく似ているというのも周知なわけです．
遺伝的アルゴリズムではデータ解析にかかわらずいろいろな分野での最適化を扱います．
また生物の「性」に関係する「遺伝子の不等交差」に対応する部分がアルゴリズムに組み込まれています．実はこの部分を逐次モンテカルロに取り入れるというのは複数の人が主張しているのですが，単に入れると，与えられた分布での期待値にバイアスが入り，それを避けようとしてメトロポリス・ヘイスティングス棄却を付加すると棄却が多くなり効率が悪くなるので，いまひとつのことが多いようです．これは余談ですが．
さて，ここまで読んで，おやっと思った人も多いと思います．遺伝的アルゴリズムのほうが用途でも手法でも一般性があるのに，なんだか内輪でしか流行っていないように見えるのはなぜでしょう．
実際には遺伝的アルゴリズムのような手法は結構あちこちで使われていると思うのですが，逐次モンテカルロの方がよいニッチを取ったと思えるのは，ベイズ統計や状態空間モデルという，しっかりした確率的枠組みと応用のある分野にフォーカスした点ではないかと思います．
特に「粒子の状態の多様性」に「事後分布の拡がり」，具体的にはベイズ信頼区間のような解釈がつくのがポイント高いです．遺伝的アルゴリズムでは，目的が最適化といっておいて，でも解や粒子の多様性も重要，みたいに２段構えみたいになるのではないかと思います．その代わり，逐次モンテカルロでは確率分布をゆがめる交差はタダではできなくなりますが，遺伝的アルゴリズムはそこに固執しすぎた面もありそうです．
なお，「遺伝的アルゴリズムのほうが歴史的に古いんじゃないの」という人もいると思いますが，実は物理のほうでは拡散モンテカルロとかグリーン関数モンテカルロとか粒子を分裂させる方法が１９６０年代の終わりごろからあります．「計算統計２」の伊庭による補論をみてください．あるいは英語でよければこちら arxiv.org/pdf/cond-mat/0008226