ギブスサンプリングのソースを表示

[[統計学]]と[[統計物理学]]において、'''ギブスサンプリング'''（{{lang-en-short|Gibbs sampling, Gibbs sampler}}）は、直接サンプリングが難しい確率分布の代わりにそれを近似するサンプル列を生成する[[MCMC]]法（{{en|Markov chain Monte Carlo algorithm}}）の1つである。この生成された数列は、[[同時分布]]や[[周辺分布]]や[[期待値]]などの積分計算を近似するために用いられる。通常は観測として与えられている変数に関してはサンプリングをする必要はない。ギブスサンプリングは統計的推定やベイズ推定の手法として頻繁に用いられている。ランダムアルゴリズムであり、{{仮リンク|変分ベイズ法|en|Variational Bayesian methods}}（{{en|variational Bayes}}）や[[EMアルゴリズム]]（expectation-maximization algorithm）のような[[統計的推定]]法のための決定論的な方法の代替法である。

他のMCMC法と同様に、ギブスサンプリングはサンプルのマルコフ連鎖を生成する。得られるサンプル列が[[マルコフ連鎖]]であるため、例えば100番目毎にサンプルを選ぶといったサンプルが十分に独立とみなせるように気をつけるべきである。それに加え、サンプル列の始めの方の値は目的の分布を精確には表していないため、初期値を与えたすぐ後は[[burn-in]]期間としてサンプルを捨てるべきである。

== 導出 ==
ギブスサンプリングは[[メトロポリス・ヘイスティングス法]]の1つである。[[同時分布]]より周辺化された[[条件付き確率分布]]から、与えられた[[確率分布]]に従ったサンプルをサンプリングする。同時確率<math>(x_1, \dotsc, x_n)</math>から確率変数<math>\boldsymbol{X} = \{x_1, \dotsc, x_n\}</math> を<math>\left.k\right.</math>サンプル得たい。<math>n</math>次元の<math>i</math>番目のサンプルを<math>\boldsymbol{X}^{(i)} = \{x_1^{(i)}, \dotsc, x_n^{(i)}\}</math>とする。

手順は以下の通りである。
#初期値<math>\boldsymbol{X}^{(0)}</math>を設定する。
#条件付き確率<math>p(x_j|x_1^{(i)},\dotsc,x_{j-1}^{(i)},x_{j+1}^{(i-1)},\dotsc,x_n^{(i-1)})</math>から<math>i</math>番目のサンプル<math>x_j^{(i)}</math>をサンプリングする。
#<math>i</math>が<math>k</math>以下であれば<math>i=i+1</math>して2へ。それ以外だと終了。

サンプルは他の変数に条件付けされた分布からサンプリングされるが、他の変数には新しいサンプルを使用すべきである。つまりは、1ステップ毎に1変数をサンプルし、新しいサンプルに入れ替えていく。このサンプル集合は、全ての変数に関する同時分布を近似する。

それに加え、全てのサンプルに関して平均をとることで期待値を近似することができる。

以下は注意点である。
*初期値の設定にEMアルゴリズムなどを用いたり、ランダムに決めてもいい。しかし初期値の設定に敏感にならなくても、burn-inの期間を設ければ問題ではない。
*サンプリング初期の値を捨てる期間（''burn-in period''）を設けることがよく行われる。また、期待値を計算するときには<math>n</math>番目毎の値しか用いないといったこともよく行われる。この理由には2つある。1つは生成されるサンプル列はマルコフ連鎖でありサンプル間にある程度の相関が存在するため独立なサンプルではない。もう1つはマルコフ連鎖の定常分布は目的の分布になるが初期値から定常分布に到達するまでには時間がかかる。 自己相関の量や<math>n</math>をアルゴリズムで決定することもできるが、それは黒魔術的である。
*[[焼きなまし法]](Simulated Annealing)はサンプリングの初期によく用いられる。しかしサンプル空間の移動が遅くサンプルの相関が強くなってしまう。その他の自己相関を減少させる方法には ''collapsed Gibbs sampling''や''blocked Gibbs sampling''、''ordered overrelaxation''などがある。

===条件付き分布と同時分布の関係===
他のすべての変数が与えられたときのある変数に関する条件付き確率は同時確率に比例する。
:<math>p(x_j|x_1,\dotsc,x_{j-1},x_{j+1},\dotsc,x_n) = \frac{p(x_1,\dotsc,x_n)}{p(x_1,\dotsc,x_{j-1},x_{j+1},\dotsc,x_n)} \propto p(x_1,\dotsc,x_n)</math>

ここで''比例する''とは、分母が<math>x_j</math>の関数ではなく、<math>x_j</math>がどんな値であれ分母が定数であることである。周辺化定数は同時確率を<math>x_j</math>に関して周辺化した値である。

:<math>
p(x_1,\dotsc,x_{j-1},x_{j+1},\dotsc,x_n)
= \int p(x_1,\dotsc,x_n) dx_j
</math>

実用上、確率変数<math>x_j</math>の条件付き分布を求めるためのもっとも簡単な方法はグラフィカルモデルの変数のうち<math>x_j</math>の関数ではない値を独立とみなして因子化すればいい。

そのほかには、3つの場合が考えられる。
#分布が離散分布である場合、<math>x_j</math>の取りうる値すべてに関して確率を計算し、足しあわせることで周辺化定数を計算すればいい。
#分布が連続で既知の形を持つ場合、1次元の周辺化なので周辺化定数が計算可能である。
#その他の場合、周辺化定数は無視することができる。大抵のサンプリング法は周辺化定数がなくても問題ではない。

== 理論 ==
サンプル<math>\left.X\right.</math>を次元<math>\left.d\right.</math>のパラメータベクトル<math>\theta \in \Theta \,\!</math>に基づいた事前分布<math>g(\theta_1, \dotsc, \theta_d)</math>からサンプリングする。

<math>\left.d\right.</math>が大きい場合、数値積分を行ない<math>\left.\theta_i\right.</math>の周辺化分布を計算することは困難を伴う。

その周辺化分布の計算を<math>\left.\Theta\right.</math>空間上のマルコフ連鎖を生成することで代替する。以下の2ステップを繰り返す。
# <math>j</math>を選ぶ<math>1 \leq j \leq d</math>
# <math>g(\theta_1, \dotsc, \theta_{j-1}, \, \cdot \, , \theta_{j+1}, \dotsc, \theta_d)</math>の分布にしたがい、新しい変数<math>\left.\theta_j\right.</math>を選ぶ。

この2ステップは分布<math>\left.g\right.</math>にしたがう可逆なマルコフ連鎖を生成する。

これは以下の通り証明される。すべての<math>i \neq j</math> に関して<math>\left.x_i = y_i\right.</math>であれば、<math>x \sim_j y</math>と表す。<math>x \sim_j y</math> は同値関係である。<math>\left.p_{xy}\right.</math>は<math>x \in \Theta</math>から<math>y \in \Theta</math>へ遷移する確率の分布を表す。

よって遷移確率は
:<math>p_{xy} = \begin{cases}
\dfrac{1}{d} \dfrac{g(y)}{\sum_{z \in \Theta: z \sim_j x} g(z) } & x \sim_j y \\
0 & \text{otherwise}
\end{cases}
 </math>

したがって、 
:<math>
g(x) p_{xy} = \frac{1}{d}\frac{ g(x) g(y)}{\sum_{z \in \Theta: z \sim_j x} g(z) }
= \frac{1}{d}\frac{ g(y) g(x)}{\sum_{z \in \Theta: z \sim_j y} g(z) }
= g(y) p_{yx}
</math>

このように[[詳細つりあい条件]]は満たされる。

実用的には<math>\left.j\right.</math>はランダムに選ばれず、並びの順番で選ばれる。
また正確に言うと、これは非定常マルコフ連鎖を生成するが、各ステップは可逆であり、全体のプロセスは求めたい定常分布を与える。

== 手法の拡張 ==
ギブスサンプリングの拡張について説明する。これらの拡張はサンプル間の自己相関を減少させることで、計算コストを減らすことを目標に考えられている。

=== Blocked Gibbs sampler ===
'''blocked Gibbs sampler''' は個々の変数を考えるのではなく、変数を複数のグループに分割して条件づき分布を考える。
例えば、[[隠れマルコフモデル]]では[[forward-backward algorithm]]を使い、隠れ変数に関するマルコフ連鎖を生成する。

=== Collapsed Gibbs sampler ===
'''collapsed Gibbs sampler'''は周辺化分布の変数を積分消去する。たとえば、''A''、''B''、''C''の3つの変数があるとする。ギブスサンプリングでは''p''(''A''|''B'',''C'')、''p''(''B''|''A'',''C'')、''p''(''C''|''A'',''B'')からサンプリングすることになる。collapsed Gibbs samplerでは''A''をサンプリングする時には例えば''B''を積分消去した周辺化分布''p''(''A''|''C'')からサンプリングを行う。''A''に関して''B''が共役事前分布であったり、指数分布族であれば計算が容易にできる。詳しくは[[compound distribution]]、Liu (1994)を参考。<ref>{{cite journal
| last        = Liu
| first       = Jun S.
| year        = 1994
| month       = September
| title       = The Collapsed Gibbs Sampler in Bayesian Computations with Applications to a Gene Regulation Problem
| jstor        = 2290921
| journal     = Journal of the American Statistical Association
| volume      = 89
| issue       = 427
| pages       = 958–966
| doi         = 10.2307/2290921
}}</ref>

== ソフトウェア ==
* [[OpenBUGS]] (''Bayesian inference Using Gibbs Sampling'') ：複雑な統計モデルのベイズ推定にMCMC法を用いている
* [[Just another Gibbs sampler|JAGS]] (''Just another Gibbs sampler'') MCMC法を用いた階層ベイズモデルを推定できる
* [[Church (programming language)|Church]] ：任意の分布をギブスサンプリングする

== 参照 ==
{{Reflist}}

{{確率分布の一覧}}
{{Statistics-stub}}

{{DEFAULTSORT:きふすさんふりんく}}
[[Category:アルゴリズム]]
[[Category:モンテカルロ法]]
[[Category:数学に関する記事]]
[[Category:数学のエポニム]]