マルコフ連鎖モンテカルロ法によるランダムサンプリング



  1. マルコフ連鎖モンテカルロ(Markov chain Monte Carlo)法とは?

  2. マルコフ連鎖 とは, 状態遷移が現在の状態のみに依存する 確率過程 である. (以降では,状態の個数が有限のマルコフ連鎖を扱う.) マルコフ連鎖は, 次のように有向グラフで表現される: 各頂点は一つの状態を,各辺は一つの遷移を, 更に,辺の重みはその辺に対応する状態遷移の確率を表す. 一方, モンテカルロ法 とは, サンプリング(やシミュレーション)を用いて 所望の値を求める計算手法のことである. 確率空間 (Ω,P) のサンプリングとは, 標本空間 Ω からある標本点を確率 P に従って抽出することである. サンプリングにマルコフ連鎖を用いた場合, そのモンテカルロ法は,特に, マルコフ連鎖モンテカルロ法 (Markov chain Monte Carlo methods,以降,MCMC 法と略す)と呼ばれる. 確率空間 (Ω,P) のサンプリングにマルコフ連鎖を用いるとは, 大まかには, 以下のようなアルゴリズムでサンプリングすることである:

    1. 次のようにマルコフ連鎖 M を構成する: i ) マルコフ連鎖の状態空間をサンプリングの標本空間 Ω とする. ii ) マルコフ連鎖の定常分布がサンプリングの確率 P となるように 状態遷移を構成する.
    2. 任意の状態からマルコフ連鎖 M を繰り返し適用する. (上で構成した状態遷移を繰り返し適用する.) ある一定の回数の M の適用後の状態(Ω のある標本点)を出力する.

  3. 理論計算機科学における MCMC 法 -- #P完全問題の近似

  4. MCMC 法は, 理論計算機科学(Theoretical Computer Science) において強力かつ重要な道具であり, 多くの研究者が注目を寄せている研究分野である. (一般的な MCMC 法は [1] を, 理論計算機科学における MCMC 法 は [2], [3], [4] を参照.)

    1979年,Leslie Valiant が #P と いう計算量クラスを定義した. これは, 制約を満たす解の個数を求める関数問題のクラスである. (PやNPなどは YES/NO 判定をする決定問題である.) 更に, #Pの中で「最も難しい」問題を#P完全と定義した. (詳しくは ここ を参照.) #Pの定義より, 充足可能性問題(SAT)の数え上げ (与えられる CNF 論理式の充足解の個数を求める問題) が#P完全であることは容易に確認できる. この他にも, 頂点彩色問題,独立頂点集合問題,ハミルトン閉路問題など, 多くのNP完全問題の数え上げが#P完全である. (ただし, すべてのNP完全問題の数え上げが#P完全となるかはまだ分かっていない.) 一方,これらとは異なり, 多項式時間計算可能な問題の数え上げが#P完全となることもある. 2-SAT 問題の数え上げ, 完全マッチング問題の数え上げがその代表である. 更に,例えば, 頂点彩色問題の数え上げにおいて, 頂点次数の最大が Δ であるようなグラフ の 2Δ-彩色の個数を求める問題も#P完全である. (この数え上げに対する決定問題, つまり, 頂点次数の最大が Δ であるようなグラフ に 2Δ-彩色が存在するか, という問題は多項式時間計算可能な問題である. なぜなら,そのようなグラフは (Δ+1)-彩色可能であるので.)

    ここで,以下の基本的な事実を確認しておく:

    #P完全問題が多項式時間で解けるなら, NP完全問題も多項式時間で解ける.
    このことは, P≠NP ならば#P完全問題は多項式時間で解けないことを意味する.

    MCMC 法は, このような#P完全問題を近似して(多項式時間で)解くことに用いられる. 例えば,次のような,基本的で重要なグラフの問題の数え上げを近似して 解くことに用いられる:

    1. 頂点彩色問題
    2. 独立頂点集合問題
    3. マッチング問題
    問題の解(頂点彩色問題ならば与えられたグラフの頂点彩色の全体) の上の一様分布を生成するためのサンプリングにマルコフ連鎖が用いられ, そのサンプリングアルゴリズムが, 解の個数(頂点彩色問題ならば頂点彩色の個数)を近似して求めることに 用いられる.(ただし, 例えば,頂点彩色問題の数え上げの場合, それができると示されたのは, 与えられるグラフの次数に制限がある場合である.詳細は次節を参照.) 更に,このようなグラフの問題の数え上げ以外にも, 数学・物理の分野で重要な関数の値の近似を求めることにも用いられる:
    1. 行列のパーマネント(permanent)
    2. 分配関数(partition function)
    3. Tutte 多項式(Tutte polynomial)
    4. 凸体の体積
    以上の数え上げ及び関数の値を求める問題はすべて#P完全である. (多項式時間で正確に求めることはかなり難しいと思われる.)

  5. 近似困難な#P完全問題

  6. このように,MCMC 法は, (多項式時間で正確に解くのが難しいと思われる)問題を 近似して解くことに用いられる. 一方で, 多くの#P完全問題が近似困難であることも示されている [5]. (ただし,この近似困難性は, NPが計算量クラス RP に包含されないことを仮定している.) 例えば, 頂点彩色問題の数え上げは, 与えられるグラフが任意であれば近似困難となる. (MCMC 法で頂点彩色問題の数え上げが近似して解けると示されたのは, 与えられるグラフの次数に制限がある場合である. 例えば, k-彩色の数え上げであれば, 与えられるグラフの頂点次数の最大が k/2 以下である場合である.) この他に, 独立頂点集合問題,ハミルトン問題,頂点被覆問題の数え上げは (一般には)近似困難である. もっと一般的に次の定理が成り立つ:

    定理(Dyer, Goldberg, Greenhill, and Jerrum, [5]) 任意のNP完全問題 A の数え上げ #A は近似困難である.
    この定理からは導かれない近似困難な問題も存在する. #2-SAT 問題がその代表である. (パスの数え上げや閉路の数え上げなども近似困難である.) このように多くの#P完全問題が近似困難である. これに比べれば, MCMC 法により近似可能であると示された#P完全問題は (残念ながら)少数である. (もっとも, MCMC 法は 少なくとも一つの解を多項式時間で見つけられることを前提としているので, 対応する決定問題がNP完全であれば, その数え上げに MCMC 法を適用するのはかなり難しい.)

    一方で, 近似可能か近似困難かが分かっていない問題が数多くある. 代表的な問題を以下にあげておく:

    1. 二部グラフにおける独立頂点集合の数え上げ (二部グラフにおける最大独立頂点集合問題は多項式時間計算可能)
    2. 半順序集合のイデアルの数え上げ
    3. 木の数え上げ(全域木の数え上げは多項式時間計算可能)
    4. 森の数え上げ
    5. 無向グラフにおけるオイラー閉路の数え上げ (有向グラフにおけるオイラー閉路の数え上げは多項式時間計算可能)

参考文献

  1. D. Levin, Y. Peres, and E. Wilmer, Markov Chains and Mixing Times, American Mathematical Society, 2008.
  2. M. Jerrum, Mathematical foundations of the Markov chain Monte Carlo method, Probabilistic Methods for Algorithmic Discrete Mathematics (M. Habib, C. McDiarmid, J. Ramirez-Alfonsin, and B. Reed, eds), Algorithms and Combinatorics 16, Springer-Verlag, pp. 116-165, 1998.
  3. M. Jerrum, Counting, Sampling and Integrating: Algorithms and Complexity (Lectures in Mathematics. ETH Zürich), Birkhauser Basel, 2003.
  4. R. Montenegro and P. Tetali, Mathematical Aspects of Mixing Times in Markov Chains, Foundations and Trends in Theoretical Computer Science 1(3), pp. 237-354, 2006.
  5. M. Dyer, L. Goldberg, C. Greenhill, and M. Jerrum, The Relative Complexity of Approximate Counting Problems, Algorithmica 38, pp. 471-500, 2004.

Last Update: 15/August/2011