マルコフ確率場

物理学と確率の分野において、マルコフ確率場（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 \operatorname {N} [v]=v\cup \operatorname {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]より適切には、無限エネルギーが上の完全グラフに作用することを許可した場合でも。[ ^7]${\displaystyle V}$

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).}$

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

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

分割関数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 G=(V,E)}$

${\displaystyle X=(X_{v})_{v\in V}\sim {\mathcal {N}}({\boldsymbol {\mu }},\Sigma )}$

そのような

${\displaystyle (\Sigma ^{-1})_{uv}=0\quad {\text{iff}}\quad \{u,v\}\notin E.}$^[8]

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

マルコフ確率場の注目すべき変種の一つは条件付き確率場であり、各確率変数はグローバル観測値のセットによって条件付けられることもある。このモデルでは、各関数はクリークkへのすべての割り当てと観測値から非負の実数へのマッピングである。この形式のマルコフネットワークは、観測値の分布をモデル化しない識別分類器を生成するのにより適しているかもしれない。CRFは2001年にジョン・D・ラファティ、アンドリュー・マッカラム、フェルナンド・CN・ペレイラによって提案された。^[12]${\displaystyle o}$${\displaystyle \varphi _{k}}$ ${\displaystyle o}$

マルコフランダム場は、コンピュータグラフィックスからコンピュータビジョン、機械学習または計算生物学、^{[13] [14]}および情報検索に至るまで、さまざまな分野で応用されています。^[15] MRF は、柔軟で確率的な画像モデルを生成するために使用できるため、画像処理でテクスチャを生成するために使用されます。画像モデリングでは、特定の画像の適切な強度分布を見つけることがタスクであり、適合性はタスクの種類によって異なりますが、MRF は、画像とテクスチャの合成、画像の圧縮と復元、画像のセグメンテーション、2D 画像からの 3D 画像推論、画像登録、テクスチャ合成、超解像、ステレオマッチング、および情報検索に使用できるほど柔軟です。MRF は、エネルギー最小化問題として提起される可能性のあるさまざまなコンピュータビジョンの問題を解決するために使用できます。または、マルコフランダム場フレームワーク内で一連の識別機能を使用して異なる領域を区別し、領域のカテゴリを予測する必要がある問題です。^[16] マルコフ確率場はイジングモデルの一般化であり、それ以来、組み合わせ最適化やネットワークで広く使用されてきました。