ハマーズリー・クリフォード定理

ハマースリー・クリフォードの定理は、確率論、数理統計学、統計力学における結果であり、マルコフネットワーク（マルコフ確率場とも呼ばれる）によって生成される事象として厳密に正の確率分布を表現できる必要十分条件を与える。これは確率場に関する基本定理である。^{[1]これは、厳密に正の}質量または密度を持つ確率分布が無向グラフGに関してマルコフ特性の 1 つを満たすのは、それがギブス確率場である場合、つまりその密度がグラフのクリーク（または完全なサブグラフ）上で因数分解できる場合のみであることを述べている。

マルコフ確率場とギブス確率場の関係は、統計力学の文脈において、ローランド・ドブルシン^[2]とフランク・スピッツァー^[3]によって提唱された。この定理は、1971年に未発表論文で同値性を証明したジョン・ハマーズリーとピーター・クリフォードにちなんで名付けられた。 ^{[4] [5]}包含排他原理を用いたより単純な証明は、 1973年にジェフリー・グリメット^[6]、プレストン^[7]、シャーマン^[8]によって独立に示され、 1974年にはジュリアン・ベサグによって更なる証明が行われた。^[9]

証明の概要

任意のギブスランダムフィールドがすべてのマルコフ特性を満たすことを示すための単純なマルコフネットワーク。

ギブス確率場があらゆるマルコフ性を満たすことを示すのは容易です。この事実の例として、以下をご覧ください。

右の図では、与えられたグラフ上のギブス確率場は の形をしています。変数と が固定されている場合、大域的マルコフ性により、は と の間に障壁を形成するため、次が成り立ちます（条件付き独立性 を参照）。 ${\displaystyle \Pr(A,B,C,D,E,F)\propto f_{1}(A,B,D)f_{2}(A,C,D)f_{3}(C,D,F)f_{4}(C,E,F)}$ ${\displaystyle C}$ ${\displaystyle D}$ ${\displaystyle A,B\perp E,F|C,D}$ ${\displaystyle C,D}$ ${\displaystyle A,B}$ ${\displaystyle E,F}$

およびが定数で、およびです。これは が成り立つことを意味します。 ${\displaystyle C}$ ${\displaystyle D}$ ${\displaystyle \Pr(A,B,E,F|C=c,D=d)\propto [f_{1}(A,B,d)f_{2}(A,c,d)]\cdot [f_{3}(c,d,F)f_{4}(c,E,F)]=g_{1}(A,B)g_{2}(E,F)}$ ${\displaystyle g_{1}(A,B)=f_{1}(A,B,d)f_{2}(A,c,d)}$ ${\displaystyle g_{2}(E,F)=f_{3}(c,d,F)f_{4}(c,E,F)}$ ${\displaystyle A,B\perp E,F|C,D}$

局所マルコフ性を満たすすべての正の確率分布がギブス確率場でもあることを証明するには、異なる因数分解を組み合わせる手段を提供する次の補題を証明する必要があります。

補題1は、この図に示すように因数分解を組み合わせる手段を提供します。この図では、集合間の重なりは無視されていることに注意してください。

補題1

で検討中のすべての確率変数の集合を表し、およびで任意の変数集合を表すものとします。（ここで、任意の変数集合 が与えられている場合、は からの変数への任意の割り当ても表します。） ${\displaystyle U}$ ${\displaystyle \Theta ,\Phi _{1},\Phi _{2},\dots ,\Phi _{n}\subseteq U}$ ${\displaystyle \Psi _{1},\Psi _{2},\dots ,\Psi _{m}\subseteq U}$ ${\displaystyle X}$ ${\displaystyle X}$ ${\displaystyle X}$

もし

${\displaystyle \Pr(U)=f(\Theta )\prod _{i=1}^{n}g_{i}(\Phi _{i})=\prod _{j=1}^{m}h_{j}(\Psi _{j})}$

関数およびに対して、関数およびが存在し、 ${\displaystyle f,g_{1},g_{2},\dots g_{n}}$ ${\displaystyle h_{1},h_{2},\dots ,h_{m}}$ ${\displaystyle h'_{1},h'_{2},\dots ,h'_{m}}$ ${\displaystyle g'_{1},g'_{2},\dots ,g'_{n}}$

${\displaystyle \Pr(U)={\bigg (}\prod _{j=1}^{m}h'_{j}(\Theta \cap \Psi _{j}){\bigg )}{\bigg (}\prod _{i=1}^{n}g'_{i}(\Phi _{i}){\bigg )}}$

つまり、 はをさらに因数分解するためのテンプレートを提供します。 ${\displaystyle \prod _{j=1}^{m}h_{j}(\Psi _{j})}$ ${\displaystyle f(\Theta )}$

補題1の証明

をさらに因数分解するためのテンプレートとしてを用いるには、 の外側にあるすべての変数を固定する必要があります。そのために、を の変数（ に含まれない変数）への任意の固定割り当てとします。任意の変数集合 に対して、を の変数（ の変数のうち の変数を除く）に限定した割り当てとします。 ${\displaystyle \prod _{j=1}^{m}h_{j}(\Psi _{j})}$ ${\displaystyle f(\Theta )}$ ${\displaystyle \Theta }$ ${\displaystyle {\bar {\theta }}}$ ${\displaystyle U\setminus \Theta }$ ${\displaystyle \Theta }$ ${\displaystyle X}$ ${\displaystyle {\bar {\theta }}[X]}$ ${\displaystyle {\bar {\theta }}}$ ${\displaystyle X\setminus \Theta }$ ${\displaystyle X}$ ${\displaystyle \Theta }$ さらに、 のみを因数分解するには、の変数について他の因数を意味のないものにする必要がある。これを行うには、因数分解は ${\displaystyle f(\Theta )}$ ${\displaystyle g_{1}(\Phi _{1}),g_{2}(\Phi _{2}),...,g_{n}(\Phi _{n})}$ ${\displaystyle \Theta }$ ${\displaystyle \Pr(U)=f(\Theta )\prod _{i=1}^{n}g_{i}(\Phi _{i})}$ 次のように再表現される。 ${\displaystyle \Pr(U)={\bigg (}f(\Theta )\prod _{i=1}^{n}g_{i}(\Phi _{i}\cap \Theta ,{\bar {\theta }}[\Phi _{i}]){\bigg )}{\bigg (}\prod _{i=1}^{n}{\frac {g_{i}(\Phi _{i})}{g_{i}(\Phi _{i}\cap \Theta ,{\bar {\theta }}[\Phi _{i}])}}{\bigg )}}$ 各 について、の外側にあるすべての変数はによって規定された値に固定されています。 ${\displaystyle i=1,2,...,n}$ ${\displaystyle g_{i}(\Phi _{i}\cap \Theta ,{\bar {\theta }}[\Phi _{i}])}$ ${\displaystyle g_{i}(\Phi _{i})}$ ${\displaystyle \Theta }$ ${\displaystyle {\bar {\theta }}}$ それぞれについて と する と ${\displaystyle f'(\Theta )=f(\Theta )\prod _{i=1}^{n}g_{i}(\Phi _{i}\cap \Theta ,{\bar {\theta }}[\Phi _{i}])}$ ${\displaystyle g'_{i}(\Phi _{i})={\frac {g_{i}(\Phi _{i})}{g_{i}(\Phi _{i}\cap \Theta ,{\bar {\theta }}[\Phi _{i}])}}}$ ${\displaystyle i=1,2,\dots ,n}$ ${\displaystyle \Pr(U)=f'(\Theta )\prod _{i=1}^{n}g'_{i}(\Phi _{i})=\prod _{j=1}^{m}h_{j}(\Psi _{j})}$ 最も重要なことは、に割り当てられた値が によって規定された値と矛盾しない場合、にないすべての変数が からの値に固定されると が「消える」ということです。 ${\displaystyle g'_{i}(\Phi _{i})={\frac {g_{i}(\Phi _{i})}{g_{i}(\Phi _{i}\cap \Theta ,{\bar {\theta }}[\Phi _{i}])}}=1}$ ${\displaystyle \Phi _{i}}$ ${\displaystyle {\bar {\theta }}}$ ${\displaystyle g'_{i}(\Phi _{i})}$ ${\displaystyle \Theta }$ ${\displaystyle {\bar {\theta }}}$ に含まれないすべての変数をからの値に固定すると、 ${\displaystyle \Theta }$ ${\displaystyle {\bar {\theta }}}$ ${\displaystyle \Pr(\Theta ,{\bar {\theta }})=f'(\Theta )\prod _{i=1}^{n}g'_{i}(\Phi _{i}\cap \Theta ,{\bar {\theta }}[\Phi _{i}])=\prod _{j=1}^{m}h_{j}(\Psi _{j}\cap \Theta ,{\bar {\theta }}[\Psi _{j}])}$ 以来、 ${\displaystyle g'_{i}(\Phi _{i}\cap \Theta ,{\bar {\theta }}[\Phi _{i}])=1}$ ${\displaystyle f'(\Theta )=\prod _{j=1}^{m}h_{j}(\Psi _{j}\cap \Theta ,{\bar {\theta }}[\Psi _{j}])}$ 貸し出すと 次のようになります: ${\displaystyle h'_{j}(\Theta \cap \Psi _{j})=h_{j}(\Psi _{j}\cap \Theta ,{\bar {\theta }}[\Psi _{j}])}$ ${\displaystyle f'(\Theta )=\prod _{j=1}^{m}h'_{j}(\Theta \cap \Psi _{j})}$ 最終的に次のようになります。 ${\displaystyle \Pr(U)={\bigg (}\prod _{j=1}^{m}h'_{j}(\Theta \cap \Psi _{j}){\bigg )}{\bigg (}\prod _{i=1}^{n}g'_{i}(\Phi _{i}){\bigg )}}$

頂点、、によって形成されるクリークは、、 、の交差点です。${\displaystyle x_{1}}$ ${\displaystyle x_{2}}$ ${\displaystyle x_{3}}$ ${\displaystyle \{x_{1}\}\cup \partial x_{1}}$ ${\displaystyle \{x_{2}\}\cup \partial x_{2}}$ ${\displaystyle \{x_{3}\}\cup \partial x_{3}}$

補題1は、 の2つの異なる因数分解を組み合わせる手段を提供する。局所マルコフ性は、任意の確率変数 に対して、次を満たす因数およびが存在することを意味する。 ${\displaystyle \Pr(U)}$ ${\displaystyle x\in U}$ ${\displaystyle f_{x}}$ ${\displaystyle f_{-x}}$

${\displaystyle \Pr(U)=f_{x}(x,\partial x)f_{-x}(U\setminus \{x\})}$

ノード の近傍はどこにあるか。補題1を繰り返し適用すると、最終的にはクリークポテンシャルの積に因数分解される（右の図を参照）。 ${\displaystyle \partial x}$ ${\displaystyle x}$ ${\displaystyle \Pr(U)}$

証明の終わり

参照

• マルコフ確率場
• 条件付きランダムフィールド

注記

1. Lafferty, John D.; Mccallum, Andrew (2001). 「条件付きランダムフィールド：シーケンスデータのセグメント化とラベリングのための確率モデル」.第18回国際機械学習会議 (ICML-2001) 論文集. Morgan Kaufmann. ISBN 9781558607781. 2014年12月14日閲覧。ランダムフィールドの基本定理（Hammersley & Clifford 1971）による
2. Dobrushin, PL (1968)、「条件付き確率とその規則性の条件による確率場の記述」、確率論とその応用、13 (2): 197– 224、doi :10.1137/1113026
3. スピッツァー、フランク（1971）、「マルコフ確率場とギブスアンサンブル」、アメリカ数学月刊誌、78（2）：142-154、doi：10.2307/2317621、JSTOR  2317621
4. Hammersley, JM; Clifford, P. (1971), 有限グラフと格子上のマルコフ場(PDF)
5. Clifford, P. (1990)、「統計におけるマルコフ確率場」、Grimmett, GR; Welsh, DJA (編)、Disorder in Physical Systems: A Volume in Honour of John M. Hammersley、オックスフォード大学出版局、pp.  19– 32、ISBN 978-0-19-853215-6, MR  1064553 , 2009年5月4日取得
6. Grimmett, GR (1973)、「ランダムフィールドに関する定理」、ロンドン数学会誌、5 (1): 81– 84、CiteSeerX 10.1.1.318.3375、doi :10.1112/blms/5.1.81、MR  0329039 
7. プレストン、CJ（1973）、「一般化ギブス状態とマルコフ確率場」、応用確率の進歩、5（2）：242-261、doi：10.2307/1426035、JSTOR  1426035、MR  0405645
8. シャーマン、S.（1973）、「マルコフ確率場とギブス確率場」、イスラエル数学ジャーナル、14（1）：92-103、doi：10.1007/BF02761538、MR  0321185
9. Besag, J. (1974)、「空間相互作用と格子システムの統計分析」、Journal of the Royal Statistical Society、シリーズB、36 (2): 192– 236、JSTOR  2984812、MR  0373208

さらに読む

• グリメット、ジェフリー（2018）、「7.」、グラフ上の確率（第2版）、ケンブリッジ大学出版局、ISBN 9781108438179
• ランゲス、ヘルゲ、「ハマーズリー・クリフォード定理と現代統計学への影響」（PDF）、ノルウェー科学技術大学数学科学部