マルコフ確率場

物理学と確率論の分野では、マルコフ確率場（MRF）、マルコフネットワーク、または無向グラフモデルは、無向グラフで記述されるマルコフ特性を持つ確率変数の集合です。言い換えれば、確率場がマルコフ特性を満たす場合、その確率場はマルコフ確率場であると言われます。この概念は、シェリントン-カークパトリックモデルに由来します。^{[ 1 ]}

マルコフネットワーク（MRF）は、依存関係の表現においてベイジアンネットワークと類似していますが、ベイジアンネットワークは有向かつ非巡回的であるのに対し、マルコフネットワークは無向かつ巡回的である可能性があるという点が異なります。したがって、マルコフネットワークはベイジアンネットワークでは表現できない特定の依存関係（巡回的依存関係など）を表現できますが、一方で、ベイジアンネットワークでは表現できる特定の依存関係（誘導的依存関係など）は表現できません。マルコフ確率場の基となるグラフは、有限または無限の場合があります。

確率変数の同時確率密度が厳密に正である場合、それはギブスランダム場とも呼ばれます。これは、ハマーズリー・クリフォードの定理によれば、適切な（局所的に定義された）エネルギー関数のギブス測度で表現できるためです。典型的なマルコフランダム場はイジングモデルです。実際、マルコフランダム場はイジングモデルの一般的な設定として導入されました。^{[ 2 ]}人工知能の分野では、マルコフランダム場は画像処理やコンピュータビジョンにおけるさまざまな低レベルから中レベルのタスクをモデル化するために使用されます。^{[ 3 ]}

無向グラフが与えられた場合${\displaystyle G=(V,E)}$ランダム変数の集合${\displaystyle X=(X_{v})_{v\in V}}$インデックス${\displaystyle V}$に関してマルコフ確率場を形成する${\displaystyle G}$それらが局所マルコフ特性を満たす場合：

ペアワイズマルコフ性：隣接していない任意の2つの変数は、他のすべての変数が与えられた場合、条件付きで独立である。

${\displaystyle X_{u}\perp \!\!\!\perp X_{v}\mid X_{V\smallsetminus \{u,v\}}}$

局所マルコフ性：ある変数は、その近傍の変数が与えられた場合、他のすべての変数から条件付きで独立である。

${\displaystyle X_{v}\perp \!\!\!\perp X_{V\smallsetminus \operatorname {N} [v]}\mid X_{\operatorname {N} (v)}}$

どこ${\textstyle \operatorname {N} (v)}$は、の近傍の集合である。${\displaystyle v}$、 そして${\displaystyle \オペレーター名 {N} [v]=v\cup \オペレーター名 {N} (v)}$閉鎖された近隣地域${\displaystyle v}$。

グローバルマルコフ性：変数の任意の2つの部分集合は、分離部分集合が与えられた場合、条件付き独立である。

${\displaystyle X_{A}\perp \!\!\!\perp X_{B}\mid X_{S}}$

ノードからのすべてのパス${\displaystyle A}$ノードへ${\displaystyle B}$通過する${\displaystyle S}$。

グローバルマルコフ特性はローカルマルコフ特性よりも強く、ローカルマルコフ特性はペアワイズマルコフ特性よりも強い。^{[ 4 ]}ただし、上記の3つのマルコフ特性は正の分布（関連する変数に非ゼロの確率のみを割り当てる分布）に対しては同等である^{[ 5 ] 。}

3つのマルコフ特性間の関係は、以下の定式化において特に明確である。

• ペアワイズ: 任意の${\displaystyle i,j\in V}$等しくなく、隣接していない、${\displaystyle X_{i}\perp \!\!\!\perp X_{j}|X_{V\smallsetminus \{i,j\}}}$。
• ローカル:${\displaystyle i\in V}$そして${\displaystyle J\subset V}$含まないまたは隣接しない${\displaystyle i}$、${\displaystyle X_{i}\perp \!\!\!\perp X_{J}|X_{V\smallsetminus (\{i\}\cup J)}}$。
• グローバル: あらゆる${\displaystyle I,J\subset V}$交差または隣接していない、${\displaystyle X_{I}\perp \!\!\!\perp X_{J}|X_{V\smallsetminus (I\cup J)}}$。

任意の確率分布のマルコフ性を確立することは困難な場合があるため、一般的に使用されるマルコフ確率場のクラスは、グラフのクリークに従って因数分解できるものである。

一連のランダム変数が与えられた場合${\displaystyle X=(X_{v})_{v\in V}}$、 させて${\displaystyle P(X=x)}$特定のフィールド構成の確率${\displaystyle x}$で${\displaystyle X}$つまり、${\displaystyle P(X=x)}$確率変数が${\displaystyle X}$特定の価値を帯びる${\displaystyle x}$。 なぜなら${\displaystyle X}$は集合であり、確率は${\displaystyle x}$は、共同分布に関して解釈されるべきである。${\displaystyle X_{v}}$。

この結合密度がクリーク上で因数分解できる場合${\displaystyle G}$として

${\displaystyle P(X=x)=\prod _{C\in \operatorname {cl} (G)}\varphi _{C}(x_{C})}$

それから${\displaystyle X}$に関してマルコフ確率場を形成する${\displaystyle G}$。 ここ、${\displaystyle \operatorname {cl} (G)}$は、${\displaystyle G}$最大クリークのみを使用する場合、定義は同等です。$\displaystyle \varphi _{C}}$これらは、因子ポテンシャルまたはクリークポテンシャルと呼ばれることもあります。ただし、用語に矛盾があることに注意が必要です。ポテンシャルという言葉は、しばしば対数に適用されます。$\displaystyle \varphi _{C}}$これは、統計力学では、${\displaystyle \log(\varphi _{C})}$配置のポテンシャルエネルギーとして直接解釈できる${\displaystyle x_{C}}$。

一部の MRF は因数分解しません。単純な例は、無限のエネルギーを持つ 4 つのノードのサイクル上に構築できます。つまり、ゼロ確率の構成です^{[ 6 ]}より適切には、無限のエネルギーが完全なグラフに作用することを許容します。${\displaystyle V}$[ ^{7 ]​}

MRFは、以下の条件のうち少なくとも1つが満たされる場合に因数分解される。

• 密度は厳密に正である（ハマーズリー・クリフォードの定理による）。
• このグラフは弦グラフである（ベイジアンネットワークと同等であるため）。

そのような因数分解が存在する場合、ネットワークの因数グラフを構築することが可能となる。

任意の正のマルコフ確率場は、特徴関数を持つ標準形の指数族として記述できる。${\displaystyle f_{k}}$完全同時分布は次のように書ける。

${\displaystyle P(X=x)={\frac {1}{Z}}\exp \left(\sum _{k}w_{k}^{\top }f_{k}(x_{\{k\}})\right)}$

表記法

${\displaystyle w_{k}^{\top }f_{k}(x_{\{k\}})=\sum _{i=1}^{N_{k}}w_{k,i}\cdot f_{k,i}(x_{\{k\}})}$

これは単にフィールド構成に関する内積であり、Zは分割関数です。

${\displaystyle Z=\sum _{x\in {\mathcal {X}}}\exp \left(\sum _{k}w_{k}^{\top }f_{k}(x_{\{k\}})\right).}$

ここ、$\displaystyle {\mathcal {X}}}$これは、ネットワークのすべてのランダム変数への値の可能な割り当ての集合を表します。通常、特徴関数は${\displaystyle f_{k,i}}$これらは、クリークの構成を示す指標として定義されます。${\displaystyle f_{k,i}(x_{\{k\}})=1}$もし${\displaystyle x_{\{k\}}}$これは、 k番目のクリークのi番目の可能な構成に対応し、それ以外の場合は 0 です。このモデルは、上記のクリーク分解モデルと同等です。${\displaystyle N_{k}=|\operatorname {dom} (C_{k})|}$は、クリークのカーディナリティであり、フィーチャの重みです。${\displaystyle f_{k,i}}$対応するクリーク因子の対数に相当します。${\displaystyle w_{k,i}=\log \varphi (c_{k,i})}$、 どこ${\displaystyle c_{k,i}}$はk番目のクリークのi番目の可能な構成、つまりクリークの定義域におけるi番目の値である。${\displaystyle C_{k}}$。

確率Pはしばしばギブス測度と呼ばれます。マルコフ場をロジスティック モデルとして表現することは、すべてのクリーク因子がゼロでない場合にのみ可能です。つまり、$\displaystyle {\mathcal {X}}}$確率は 0 と割り当てられます。これにより、行列代数の手法を適用できます。たとえば、行列のトレースは行列式の log であり、グラフの行列表現はグラフの接続行列から生じます。

分配関数Zの重要性は、エントロピーなどの統計力学の多くの概念がマルコフネットワークの場合に直接一般化され、それによって直感的な理解が得られる点にある。さらに、分配関数を用いることで、問題の解法に変分法を適用できる。すなわち、1 つまたは複数の確率変数に駆動力を与え、この摂動に対するネットワークの反応を調べることができる。例えば、グラフの各頂点vに対して、分配関数に駆動項J _{vを追加することで、次の式が得られる。}

${\displaystyle Z[J]=\sum _{x\in {\mathcal {X}}}\exp \left(\sum _{k}w_{k}^{\top }f_{k}(x_{\{k\}})+\sum _{v}J_{v}x_{v}\right)}$

J _vに関して形式的に微分すると、頂点vに関連付けられた確率変数X _vの期待値が得られます。

${\displaystyle E[X_{v}]={\frac {1}{Z}}\left.{\frac {\partial Z[J]}{\partial J_{v}}}\right|_{J_{v}=0}.}$

相関関数も同様に計算されます。2点相関は次のようになります。

${\displaystyle C[X_{u},X_{v}]={\frac {1}{Z}}\left.{\frac {\partial ^{2}Z[J]}{\partial J_{u}\,\partial J_{v}}}\right|_{J_{u}=0,J_{v}=0}.}$

残念ながら、ロジスティックマルコフネットワークの尤度は凸関数であるものの、モデルの尤度または尤度の勾配を評価するにはモデル内での推論が必要であり、これは一般的に計算上実行不可能である（下記の「推論」を参照）。

ベイジアンネットワークと同様に、ノードの集合の条件付き分布を計算することができる。${\displaystyle V'=\{v_{1},\ldots ,v_{i}\}}$別のノード群に値を与える${\displaystyle W'=\{w_{1},\ldots ,w_{j}\}}$マルコフ確率場において、可能なすべての割り当てを合計することによって${\displaystyle u\notin V',W'}$これは厳密推論と呼ばれます。ただし、厳密推論は#P完全問題であり、一般的には計算上扱いが困難です。マルコフ連鎖モンテカルロ法やループ信念伝播法などの近似手法の方が、実際にはより実行可能な場合が多いです。ツリー（ Chow–Liuツリーを参照）などのMRFの特定のサブクラスには、多項式時間推論アルゴリズムがあります。このようなサブクラスの発見は、活発な研究テーマです。効率的なMAP、つまり最も可能性の高い割り当て推論を可能にするMRFのサブクラスもあります。これらの例としては、連想ネットワークがあります。^{[ 9 ] [ 10 ]}もう1つの興味深いサブクラスは、分解可能なモデル（グラフが弦状の場合）です。MLEの閉形式があれば、数百の変数に対して一貫した構造を発見することができます。^{[ 11 ]}

マルコフ確率場の注目すべき変種の一つに条件付き確率場があり、これは各確率変数が一連の全体的な観測値に基づいて条件付けられる場合がある。${\displaystyle o}$このモデルでは、各関数が$\displaystyle \varphi _{k}}$これは、すべての割り当てからクリークkと観測値の両方へのマッピングです。${\displaystyle o}$非負の実数に。この形式のマルコフネットワークは、観測値の分布をモデル化しない識別分類器を生成するのに適している可能性があります。CRFは、 2001年にJohn D. Lafferty、Andrew McCallum、Fernando CN Pereiraによって提案されました。^{[ 12 ]}

マルコフ確率場は、コンピュータグラフィックスからコンピュータビジョン^{[ 13 ]} 、機械学習や計算生物学^{[ 2 ] [ 14 ]、情報検索[15]}まで、^{さまざまな分野}で応用されています。MRFは、柔軟で確率的な画像モデルを生成できるため、画像処理でテクスチャを生成するために使用されます。画像モデリングでは、与えられた画像の適切な強度分布を見つけることがタスクであり、適合性はタスクの種類に依存します。MRFは、画像とテクスチャの合成、画像の圧縮と復元、画像のセグメンテーション、2D画像からの3D画像推論、画像レジストレーション、テクスチャ合成、超解像、ステレオマッチング、情報検索に使用できるほど柔軟です。統計力学的手法は、ベイズ画像復元のためのMRFモデルの分析にも使用されています。田中和之と堀口剛は、カラー画像復元のための解けるMRFモデルと、グレースケール復元のための関連する反復計算方法を研究しました。^{[ 16 ] [ 17 ]}これらは、エネルギー最小化問題として定式化できるさまざまなコンピュータビジョン問題、またはマルコフ確率場フレームワーク内で識別特徴のセットを使用して異なる領域を区別して領域のカテゴリを予測する必要がある問題を解決するために使用できます。^{[ 18 ]} マルコフ確率場はイジングモデルの一般化であり、それ以来、組み合わせ最適化とネットワークで広く使用されています。