マルチカノニカル法のソースを表示

'''マルチカノニカル法'''（{{lang-en-short|multicanonical algorithm}}）とは、統計学および物理学において、[[マルコフ連鎖モンテカルロ法]]におけるサンプリング法の一つで、[[メトロポリス・ヘイスティングス法]]により複数の局所安定点を持つ被積分関数を[[積分法|積分]]するときに用いられる。サンプリングを[[状態密度]]の逆数に従って行う<ref name="Berg"/>。状態密度はあらかじめ[[ワン・ランダウ法]]などの他の方法により計算しておく。<ref name="Landau"/>イジングモデルやスピングラスなどのスピン系において重要なアルゴリズムである<ref name="Berg"/><ref name="Newmann"/><ref name="Dayal"/>。'''マルチカノニカルアンサンブル'''（{{lang-en-short|multicanonical ensemble}}）、'''マルチカノニカルサンプリング'''（{{lang-en-short|multicanonical sampling}}）、'''フラットヒストグラム法'''（{{lang-en-short|flat histogram}}）とも。

[[極値|<nowiki/>]]
== 背景 ==
たとえばスピン系などの自由度の大きい系をシミュレートする場合、{{仮リンク|モンテカルロ積分|en|Monte Carlo integration}}が必要とされる。この積分法では、[[Importance sampling|<nowiki/>]]{{仮リンク|重点サンプリング法|en|Importance_sampling}}、とくに[[メトロポリス・ヘイスティングス法|メトロポリス法]]が非常に重要である<ref name="Newmann"/>。しかし、メトロポリス法では {{Mvar|β}} を[[逆温度]]として <math>\exp(-\beta E)</math> に従ってサンプリングを行なうため、エネルギー障壁 <math>\Delta E</math> を乗り越えることはその大きさに対して指数関数的に困難となる<ref name="Berg"/>。[[Potts model|<nowiki/>]]{{仮リンク|ポッツモデル|en|Potts model}}のような複数の局所安定点を持つ系では、このメトロポリス法はある特定の局所安定点に囚われてしまい、取り扱いが困難となる<ref name="Newmann"/>。このため、他のサンプリング法によるアプローチが必要となる。

== 概要 ==
マルチカノニカル法では、メトロポリス・ヘイスティングス法を用いるが、メトロポリス法におけるサンプリング分布 <math>\exp(-\beta E)</math> の代わりに、状態密度の逆数を用いる<ref name="Berg"/>。このように選ぶことで、平均的な意味において、エネルギー毎に等しい状態数をサンプリングできる。言い換えれば、エネルギーに対して「フラットなヒストグラム」を得ることができる。このことから、エネルギー障壁を乗り越えることが困難ではなくなる。メトロポリス法と比べて優れている点としてもう一つ、サンプリングが系の温度によらないことから、全ての温度における熱力学的変数を推計することができる（「マルチカノニカル」とはここから来ている）。このことは一次[[相転移]]を研究する上において大きな利点となる<ref name="Berg"/>。

マルチカノニカル法の実行上において最大の問題は、状態密度を予め知る必要があることである<ref name="Landau"/><ref name="Newmann"/>。マルチカノニカルサンプリングにおいて重要な貢献の一つとして、[[ワン・ランダウ法]]が挙げられる。このアルゴリズムは、収束するまで状態密度を計算しつづけることで、漸近的にマルチカノニカル集合を得ることができる<ref name="Landau"/>。

マルチカノニカル法の応用範囲は物理系のみに留まらない。コスト関数 {{Mvar|F}} が定義できる抽象的な系にも適用することができる。 {{Mvar|F}} に対する状態密度を用いることにより、多次元空間上の積分や最小値探索に用いることができる<ref name="Lee"/>。

== 動機 ==
ある系とその位相空間 <math>\Omega</math> （系のコンフィギュレーション <math>\boldsymbol{r}\in \Omega</math> により張られる空間）とその位相空間上定義される「コスト」関数 {{Mvar|F}} 、 そのスペクトル <math>\Gamma</math>: <math>F(\Omega) = \Gamma = [\Gamma_\min, \Gamma_\max]</math> を考える。

ある量の位相空間上の平均値 <math>\langle Q\rangle</math> を計算するには、以下のような積分を実行する必要がある。
:<math>\langle Q\rangle = \frac{1}{V}\int_\Omega Q(\boldsymbol{r}) p(\boldsymbol{r}) \,\mathrm d\boldsymbol{r}</math>
ここで <math>p(\boldsymbol{r})</math> は体積あたりの重み、
:<math>p(\boldsymbol{r}) = \frac{1}{V}\int_\Omega p(\boldsymbol{r}) \,\mathrm d\boldsymbol{r}</math>
である。 {{Mvar|F}} に対する状態密度は以下のように与えられる。
:<math>\rho(f) = \frac{1}{V}\int_\Omega \delta(f - F(\boldsymbol{r})) \,\mathrm d\boldsymbol{r}</math>
これは、もし {{Mvar|Q}} と {{Mvar|p}} の両方が特定の状態には依存せず、以下のようにその状態における {{Mvar|F}} の値 <math>F(\boldsymbol{r}) = F_\boldsymbol{r}</math> にのみ依存するならば、
: <math>Q(\boldsymbol{r}) = Q(F_\boldsymbol{r}), p(\boldsymbol{r}) = p(F_\boldsymbol{r}),</math>
<math>\langle Q\rangle</math> の定義式を[[ディラックのデルタ関数|デルタ関数]]と ''f ''についての積分を追加することにより以下のように書き換えることができる。
:<math>
\begin{align}
 \langle Q\rangle & = \int_{\Gamma_\min}^{\Gamma_\max} \int_\Omega  Q(F_\boldsymbol{r}) p(F_\boldsymbol{r}) \delta(f - F_\boldsymbol{r}) \,\mathrm d\boldsymbol{r} \,df \\
 & = \int_{\Gamma_\min}^{\Gamma_\max} Q(f) p(f) \int_\Omega \delta(f - F_\boldsymbol{r}) \,\mathrm d\boldsymbol{r} \, df \\
 & = \int_{\Gamma_\min}^{\Gamma_\max} Q(f) p(f) \rho(f) \, \mathrm df \\
\end{align}
</math>
つまり、状態密度を知っていれば、それは <math>\Omega</math> 上の状態数の <math>\Gamma</math> への射影であるから、  {{Mvar|F}} の値についての一次元積分により、位相空間上の多次元積分そすることなく平均値が計算できることになる。

自由度の高い系については状態数が大きくなるため、解析的な表式を得ることは難しく、 <math>\langle Q\rangle</math> の計算も困難となる。この問題は多次元積分であるから、モンテカルロ積分がよく用いられる。最も単純な表式では、一様分布に従う {{Mvar|N}} 個のランダムな状態 <math>\boldsymbol{r}_i\in \Omega</math> を生成し、[[推定量]]
: <math>\overline{Q}_N = \frac{1}{N}\sum_{i = 0}^N Q(\boldsymbol{r}_i) p(\boldsymbol{r}_i)</math>
を用いて <math>\langle Q\rangle</math> を計算することができる。 <math>\overline{Q}_N</math> は[[大数の法則|強い大数の法則]]により、ほぼ確実に <math>\langle Q\rangle</math> に収束する。
: <math>\lim_{N\rightarrow\infty} \overline{Q}_N = \langle Q\rangle.</math>
収束に関するよくある問題のひとつとして、 {{Mvar|Q}} の分散が非常に大きい場合、妥当な結果を得るまでの計算コストが大きくなってしまうという問題がある。

収束を速くするための方法として、[[メトロポリス・ヘイスティングス法]]がある。モンテカルロ法は一般的に重点サンプリングを用いて推定量の収束を加速する。つまり、 <math>\overline{Q}_N</math> を適当な分布 <math>P(\boldsymbol{r})</math> （上述の {{Mvar|p}} とは異なることに注意）を用いて以下のように定義しなおす。
: <math>\overline{Q}_N = \frac{1}{X}\sum_{i = 0}^N Q(\boldsymbol{r}_i) P^{-1}(\boldsymbol{r}_i) p(\boldsymbol{r}_i)</math>
ここで、 <math>X = \sum_{i = 0}^N P^{-1}(\boldsymbol{r}_i)</math> である。

当然、 {{Mvar|P}} が一様分布のとき、推定量は一様サンプリングを用いた推定量と一致する。

重要な例として、コスト関数をエネルギーとみて'' P'' をある温度に対する[[ボルツマン分布|ボルツマン因子]]と一致させる選び方がある。
:<math>P(\boldsymbol{r}) = p_\text{Boltzmann}(\boldsymbol{r}) = \frac{e^{-\beta F(\boldsymbol{r})}}{\int_\Omega \, \mathrm d\boldsymbol{r} e^{-\beta F(\boldsymbol{r})}}</math>
このように選ぶと、コスト関数が低いような状態がよりサンプルされやすくなる。

歴史的には、{{仮リンク|計算機による状態方程式計算|label=もともとのアイデア|en|Equation of State Calculations by Fast Computing Machines}}<ref name="Metropolis"/>では[[メトロポリス・ヘイスティングス法]]は熱浴に接続された系における平均値を計算するために用いていたため、状態の重みはボルツマン因子と一致していた。このような系では、上述した状態の選び方により物理系の研究がずいぶん進展した<ref name="Newmann"/>。

しかし、サンプリング分布を重み関数と一致させる必要は必ずしもない。重み関数と一致しないサンプリング分布を用いる理由の一つは、メトロポリス・ヘイスティングス法はコスト関数が複数の極小値を持つ場合に収束しないことである<ref name="Berg"/>。これは、このアルゴリズムが局所的ステップによるランダムウォークを用いているためである。つまり、ランダムウォークは通常、エネルギーの差分がオーダーひとつ分であるようなステップを実行する。このことから、このアルゴリズムにおいてある極小値近傍の領域から抜け出すための計算コストはコスト関数の極小値の値に対して指数関数的に増加する。つまり、極小値が深ければ深いほど、このアルゴリズムはそこに長く留まってしまい、そこから抜け出すのは（深さに対して指数関数的に）難しくなる。

これがマルチカノニカル法を導入する動機である。サンプル時にはコスト関数の極小値の存在を「見えなく」してやることによって、最小値近傍に囚われてしまうのを防ぐというアイデアである。

== マルチカノニアルアンサブル ==
マルチカノニカルアンサンブルとは、次のような重み関数を用いて重みづけサンプリングして得られるような統計集団である。
: <math>P(\boldsymbol{r}) = \frac{1}{\rho(F(\boldsymbol{r}))}</math>
ここで、
: <math> \rho(f) = \frac{1}{V}\int_\Omega \delta(F(\boldsymbol{r}) - f) \, d\boldsymbol{r}</math>
はコスト関数に対する状態密度である（{{Mvar|V}} は位相空間体積）。このような重み関数を選ぶことで、サンプリングされた状態に対応するコスト関数の値が {{Mvar|f}} になるような確率密度関数は以下のようになる。
:<math> P(f) = \frac{1}{f_\max - f_\min}\int_\Omega \delta(f - F(\boldsymbol{r})) P(\boldsymbol{r})\,\mathrm d\boldsymbol{r} = \frac{1}{f_\max - f_\min}\frac{1}{V}\rho(f) \int_\Omega \delta(f - F(\boldsymbol{r})) \, \mathrm d\boldsymbol{r} = \frac{1}{f_\max - f_\min} = \text{constant}</math>
このため、「フラットヒストグラム」法と呼ばれることもある。つまり、コスト関数のあらゆる値が均一にサンプリングされ、障壁は存在しなくなる。熱浴に接続された系の場合、次のような重要な利点も存在する。すなわち、サンプリングが温度に依存しないため、一回のシミュレーションにより全ての温度について研究することができる。このゆえに、マルチカノニカル（複数の温度）の名がある。

== トンネリング時間と致命的スローダウン ==
どんなモンテカルロ法もそうであるように、<math>P(\boldsymbol{r})</math> に従ってサンプリングされるサンプルには相関がある。相関の尺度として「トンネル時間」がよく使われる。トンネリング時間は、シミュレーションが {{Mvar|F}} のスペクトルの極小値と極大値の間を往復するまでにかかるマルコフ連鎖のステップ数と定義される。トンネリング時間を用いる動機の一つは、スペクトルを横断するならば状態密度の極大領域を通過するため、プロセスが脱相関されることである。また、往復させることでシミュレーションがスペクトルの全域を通過することを保証している。

{{Mvar|F}} に対するヒストグラムは平坦であるため、マルチカノニカル法は {{Mvar|F}} の値という一次元の線上における拡散過程（つまりランダムウォーク）とみることができる。このようなプロセスにおいては、[[詳細釣り合い]]条件により{{仮リンク|統計的ドリフト|label=ドリフト|en|Stochastic drift}}がないことが保証される<ref name="Robert"/>。このことから、局所的なダイナミクスにおいてはトンネリング時間は拡散プロセスと同じようにスケールすることになり、したがってトンネリング時間はスペクトルのサイズ {{Mvar|N}} の二乗に比例してスケールする。
: <math>\tau_{tt} \propto N^2</math>
しかし、イジングモデルを初めとするいくつかの系では、スケーリングが致命的にスローダウンし、 <math>N^{2+z}</math> （ここで <math>z>0</math> は系に依存する数）に比例してスケールするようになる<ref name="Dayal"/>。

スケーリングを改善し、致命的スローダウンを克服するため、非局所的ダイナミクスが開発されている<ref name="Wolff"/>（[[ウォルフのアルゴリズム]]を参照）。しかし、イジングモデルのようなスピン系において致命的スローダウンに陥いらないような局所的ダイナミクスが存在するのかどうかという疑問はいまだに答えの出ない問題である。

== 出典 ==
{{Reflist|refs =
<ref name=Berg>{{Cite journal | last1 = Berg | first1 = B. | last2 = Neuhaus | first2 = T. | doi = 10.1103/PhysRevLett.68.9 | title = Multicanonical ensemble: A new approach to simulate first-order phase transitions | journal = Physical Review Letters | volume = 68 | issue = 1 | pages = 9–12 | year = 1992 | pmid =  10045099| pmc = |arxiv = hep-lat/9202004 |bibcode = 1992PhRvL..68....9B }}</ref>
<ref name=Landau>{{Cite journal | last1 = Wang | first1 = F. | last2 = Landau | first2 = D. | doi = 10.1103/PhysRevLett.86.2050 | title = Efficient, Multiple-Range Random Walk Algorithm to Calculate the Density of States | journal = Physical Review Letters | volume = 86 | issue = 10 | pages = 2050–2053 | year = 2001 | pmid =  11289852| pmc = |arxiv = cond-mat/0011174 |bibcode = 2001PhRvL..86.2050W }}</ref>
<ref name=Newmann>{{cite book
 |title= Monte Carlo Methods in Statistical Physics
 |last1=Newmann |first1=M E J
 |last2=Barkema |first2=G T
 |year= 2002 
 |publisher= Oxford University Press
 |location=USA
 |isbn=0198517971
 |url=
 |page=
 |pages=
 |ref=
}}
</ref>
<ref name=Lee>{{Cite journal | last1 = Lee | first1 = J. | last2 = Choi | first2 = M. | doi = 10.1103/PhysRevE.50.R651 | title = Optimization by multicanonical annealing and the traveling salesman problem | journal = Physical Review E | volume = 50 | issue = 2 | pages = R651 | year = 1994 | pmid =  | pmc = |bibcode = 1994PhRvE..50..651L }}</ref>
<ref name=Metropolis>{{Cite journal | last1 = Metropolis | first1 = N. | last2 = Rosenbluth | first2 = A. W. | last3 = Rosenbluth | first3 = M. N. | last4 = Teller | first4 = A. H. | last5 = Teller | first5 = E. | title = Equation of State Calculations by Fast Computing Machines | doi = 10.1063/1.1699114 | journal = The Journal of Chemical Physics | volume = 21 | issue = 6 | pages = 1087 | year = 1953 | pmid =  | pmc = |bibcode = 1953JChPh..21.1087M }}</ref>
<ref name=Robert>{{cite book
 |title=Monte Carlo statistical methods
 |last1=Robert |first1=Christian |authorlink1=
 |last2=Casella |first2=George |authorlink2=
 |year= 2004 
 |publisher=Springer
 |location=
 |isbn=978-0-387-21239-5
 |url=http://www.springer.com/statistics/statistical+theory+and+methods/book/978-0-387-21239-5
}}
</ref>
<ref name=Dayal>{{Cite journal | last1 = Dayal | first1 = P. | last2 = Trebst | first2 = S. | last3 = Wessel | first3 = S. | last4 = Würtz | first4 = D. | last5 = Troyer | first5 = M. | last6 = Sabhapandit | first6 = S. | last7 = Coppersmith | first7 = S. | title = Performance Limitations of Flat-Histogram Methods | doi = 10.1103/PhysRevLett.92.097201 | journal = Physical Review Letters | volume = 92 | issue = 9 | year = 2004 | pmid =  | pmc = |arxiv = cond-mat/0306108 |bibcode = 2004PhRvL..92i7201D }}</ref>
<ref name=Wolff>{{Cite journal | last1 = Wolff | first1 = U. | title = Collective Monte Carlo Updating for Spin Systems | doi = 10.1103/PhysRevLett.62.361 | journal = Physical Review Letters | volume = 62 | issue = 4 | pages = 361–364 | year = 1989 | pmid =  10040213| pmc = |bibcode = 1989PhRvL..62..361W }}</ref>
}}

{{デフォルトソート:まるちかのにかるほう}}
[[Category:計算物理学]]
[[Category:モンテカルロ法]]