Markov確率場

同義語:マルコフ確率場Markov random fieldMarkovネットワークMarkov network無向グラフィカルモデルundirected graphical model

概要

Markov確率場(Markov random field)とは、グラフの頂点に置いた確率変数の同時分布で、ある頂点集合が別の 2 つの頂点集合を分離するなら、それを与えて 2 つの集合の変数が条件付き独立になるものである。有限のグラフの上で、すべての配置に正の確率を与える分布については、これはグラフのクリークごとの因子の積に分解することと同値である(Hammersley–Clifford の定理)。正値の仮定を外すと同値は成り立たない。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: 確率空間, 条件付き確率, グラフ, クリーク

Markov 確率場(Markov random field)とは、グラフの頂点に確率変数を置いた同時分布で、グラフの辺で直接つながっていない変数どうしが、間にある変数を与えれば条件付き独立になるものである。Markov ネットワーク、無向グラフィカルモデルともいう(Bis06 §8.3、p. 383)。Markov連鎖 の「現在を与えれば過去と未来は独立」を、時間の直線から一般のグラフへ広げたものと考えるとよい。画像の隣り合う画素、格子の上のスピン(Isingモデル)、遺伝子の相互作用のように、順序はないが局所的に依存する多数の変数を扱うのに使う。
中心の結果は Hammersley–Clifford の定理 である。すべての配置に正の確率を与える分布について、グラフから読める条件付き独立性は、分布がグラフのクリークごとの因子の積に分解することと同値である。独立性という確率の言葉と、分解という代数の言葉が一致するので、分布を局所的なエネルギーの和で書ける。
この記事では、Markov 性の 3 つの形と因子分解を定義し、次を示す。

主張内容
prop-mrf-chain因子分解 ⇒ 大域 ⇒ 局所 ⇒ 対の Markov 性(正値の仮定なしで)
thm-mrf-hc正値なら 4 つとも同値で、ポテンシャルが Möbius 反転で求まる
prop-mrf-local局所特性は近傍だけで決まり、正値なら局所特性が分布を決める
ex-mrf-moussouris正値を外すと大域 Markov 性から因子分解が出ない
prop-mrf-gaussGauss 分布では精度行列の零の位置がグラフを与える

定義

$G=(V,E)$ を有限の単純無向グラフとする。各 $v\in V$ に空でない有限集合 $S_v$ をとり、$\Omega=\prod_{v\in V}S_v$ とする。$X=(X_v)_{v\in V}$ を $\Omega$ に値をとる確率変数、$P(x)=\Pr(X=x)$ をその分布とする。$A\subset V$ について $x_A=(x_v)_{v\in A}$ と書き、周辺の確率を $P(x_A)=\Pr(X_A=x_A)$ と書く。$\partial A$ を $A$ の外にあって $A$ のどれかの頂点と隣り合う頂点の集合とする。
互いに素な $A,B,C\subset V$ について、すべての配置で
$$ P(x_A,x_B,x_C)\,P(x_C)=P(x_A,x_C)\,P(x_B,x_C) $$
が成り立つとき、$C$ を与えて $X_A$ と $X_B$ は 条件付き独立 であるといい、$X_A\perp X_B\mid X_C$ と書く。確率が $0$ の配置があっても意味をもつようにこの形で定義する。$C$ が $A$ と $B$ を分離する とは、$A$ の頂点から $B$ の頂点へのどの道も $C$ の頂点を通ることをいう。

Markov 性

分布 $P$ について、次を定める。

  • (P) 対の Markov 性:隣り合わない異なる $u,v$ について $X_u\perp X_v\mid X_{V\setminus\{u,v\}}$。
  • (L) 局所 Markov 性:すべての $v$ について $X_v\perp X_{V\setminus(\{v\}\cup\partial v)}\mid X_{\partial v}$。
  • (G) 大域 Markov 性:互いに素な $A,B,C$ で $C$ が $A,B$ を分離するなら $X_A\perp X_B\mid X_C$。
    (G) をみたす分布を $G$ の上の Markov 確率場 という。

(G) を定義に採る文献が多いが(Gri18 (7.8)、p. 149 は $B=V\setminus(A\cup\partial A)$、$C=\partial A$ の形)、正値な分布では 3 つとも同じになる(thm-mrf-hc)。$\partial v$ を $v$ の Markov ブランケットともいう。

クリークによる因子分解

$\mathcal{K}$ を $G$ のクリーク(どの 2 頂点も隣り合う頂点集合。空集合を含める)の全体とする。
(F) $P$ が $G$ について 因子分解 するとは、関数 $\psi_K\colon\prod_{v\in K}S_v\to[0,\infty)$($K\in\mathcal{K}$)があって、$P(x)=\prod_{K\in\mathcal{K}}\psi_K(x_K)$ となることをいう。
$P>0$ なら、$\phi_K=\log\psi_K$ として $P(x)=\exp\sum_{K}\phi_K(x_K)$ と書ける。この形を $P$ の Gibbs 表示 といい、$\phi=(\phi_K)$ を ポテンシャル という。

有限の系の Gibbs 分布一般については Gibbs測度 の定義「Gibbs 測度(有限の系)」を見よ。因子分解は、そのハミルトニアンがクリークごとの和であることを要求している。

正値の仮定なしで成り立つこと

含意の列

どの分布についても (F) ⇒ (G) ⇒ (L) ⇒ (P) である。

(F) ⇒ (G). $C$ が $A,B$ を分離するとする。$\tilde A$ を $G-C$ で $A$ の頂点とつながる頂点の全体、$\tilde B=V\setminus(\tilde A\cup C)$ とすると、$A\subset\tilde A$、$B\subset\tilde B$ で、$\tilde A$ と $\tilde B$ の間に辺はない。したがって、どのクリークも $\tilde A\cup C$ か $\tilde B\cup C$ に含まれ、$P(x)=g(x_{\tilde A},x_C)\,h(x_{\tilde B},x_C)$ と書ける。$x_{\tilde B}$ や $x_{\tilde A}$ について和をとると、$\bar h(x_C)=\sum h$、$\bar g(x_C)=\sum g$ として
$$ P(x_{\tilde A},x_C)=g\bar h,\quad P(x_{\tilde B},x_C)=\bar gh,\quad P(x_C)=\bar g\bar h $$
である。よって $P(x)P(x_C)=gh\bar g\bar h=P(x_{\tilde A},x_C)P(x_{\tilde B},x_C)$ である。この等式を $\tilde A\setminus A$ と $\tilde B\setminus B$ の座標について和をとれば、$X_A\perp X_B\mid X_C$ を得る。
(G) ⇒ (L). $A=\{v\}$、$C=\partial v$、$B=V\setminus(\{v\}\cup\partial v)$ とする。$v$ から $B$ への道は $\partial v$ を通るので、$C$ は $A,B$ を分離する。
(L) ⇒ (P). $u,v$ が隣り合わないとする。$c=x_{\partial u}$、$R=V\setminus(\{u,v\}\cup\partial u)$、$r=x_R$、$a=x_u$、$b=x_v$ と書く。(L) は
$$ P(a,b,r,c)\,P(c)=P(a,c)\,P(b,r,c) $$
である。$b$ について和をとると $P(a,r,c)P(c)=P(a,c)P(r,c)$ である。$P(c)=0$ なら示すべき等式 $P(a,b,r,c)P(r,c)=P(a,r,c)P(b,r,c)$ の両辺は $0$ である。$P(c)>0$ なら 2 つの式から
$$ P(a,b,r,c)\,P(r,c)=\frac{P(a,c)P(b,r,c)P(r,c)}{P(c)}=P(a,r,c)\,P(b,r,c) $$
である。$(r,c)$ は $x_{V\setminus\{u,v\}}$ なので、これが (P) である。$\square$

逆向きはどれも一般には成り立たない(ex-mrf-counter、ex-mrf-moussouris)。

主定理

Hammersley–Clifford の定理

$P$ をすべての $x\in\Omega$ で $P(x)>0$ である分布とする。次は同値である。

  1. (F) 因子分解する。
  2. (G) 大域 Markov 性。
  3. (L) 局所 Markov 性。
  4. (P) 対の Markov 性。
    さらに、基準の配置 $o\in\Omega$ を 1 つとり、$x$ と $B\subset V$ について、$B$ の上で $x$ に、$B$ の外で $o$ に等しい配置を $x^B$ とし、
    $$ \phi_A(x)=\sum_{B\subset A}(-1)^{\lvert A\setminus B\rvert}\log P(x^B)\qquad(A\subset V) $$
    とおく。このとき $\phi_A(x)$ は $x_A$ だけで決まり、$\log P(x)=\sum_{A\subset V}\phi_A(x)$ である。(P) のもとで、$A$ がクリークでなければ $\phi_A=0$ である。
Möbius 反転と 4 点の恒等式

prop-mrf-chain により、4 ⇒ 1 と最後の主張を示せばよい。
展開。 $\phi_A(x)$ の定義の $x^B$($B\subset A$)は $x_A$ と $o$ だけで決まる。集合の束の上の Möbius反転 により、すべての $C\subset V$ で $\log P(x^C)=\sum_{A\subset C}\phi_A(x)$ である。$C=V$ とすると $\log P(x)=\sum_{A\subset V}\phi_A(x)$ を得る。
4 点の恒等式。 $u,v$ が隣り合わないとし、$z$ を $V\setminus\{u,v\}$ の上の配置とする。$a,a'\in S_u$、$b,b'\in S_v$ について
$$ P(a,b,z)\,P(a',b',z)=P(a,b',z)\,P(a',b,z) $$
である。実際 (P) と $P(z)>0$ から $P(a,b,z)=P(a,z)P(b,z)/P(z)$ で、左辺も右辺も $P(a,z)P(a',z)P(b,z)P(b',z)/P(z)^2$ に等しい。
クリークでない $A$ の項が消えること。 $A$ が隣り合わない $u,v$ を含むとし、$D=A\setminus\{u,v\}$ とおく。$B\subset A$ を $B\cap D=D'$ で分類すると
$$ \phi_A(x)=\sum_{D'\subset D}(-1)^{\lvert D\setminus D'\rvert}\log\frac{P(x^{D'\cup\{u,v\}})\,P(x^{D'})}{P(x^{D'\cup\{u\}})\,P(x^{D'\cup\{v\}})} $$
である。この 4 つの配置は $V\setminus\{u,v\}$ の上で一致し($z=(x^{D'})_{V\setminus\{u,v\}}$)、$u,v$ の値がそれぞれ $x_u$ か $o_u$、$x_v$ か $o_v$ になっている。4 点の恒等式で $a=x_u$、$a'=o_u$、$b=x_v$、$b'=o_v$ とすると対数の中は $1$ である。よって $\phi_A=0$ である。
因子分解。 $\log P(x)=\sum_{K\in\mathcal{K}}\phi_K(x_K)$ なので、$\psi_K=e^{\phi_K}$ として (F) を得る。$\square$

Hammersley と Clifford の 1971 年の結果は未公刊のノートにとどまった(Gri18 p. 152)。Gri18 Theorem 7.12(p. 150)は 2 値の場合を同じ包除の議論で示している。統計の側からの述べ方は ESL17 §17.2(p. 629)を見よ。

ポテンシャルの一意性

$\psi_K$ は一意でない。定数や共通の変数の関数を因子の間で移せる。しかし、$\phi_A(x)=0$(ある $v\in A$ で $x_v=o_v$ のとき)という正規化を課すと、ポテンシャルは一意で、上の $\phi_A$ に等しい。実際、$\phi_A$ はこの正規化をみたす($x_v=o_v$ なら $x^{B\cup\{v\}}=x^B$ なので、定義の和が組ごとに消える)。逆に $\log P=\sum_A\Phi_A$ で $\Phi_A$ が $x_A$ だけで決まり、正規化をみたすなら、$A\not\subset C$ の項は $x^C$ で消えるので $\log P(x^C)=\sum_{A\subset C}\Phi_A(x)$ であり、Möbius 反転で $\Phi_A=\phi_A$ である。

局所特性

因子分解の実用上の利点は、1 頂点の条件付き分布(局所特性)が近傍だけで計算でき、正規化定数が要らないことである。

局所特性

$P>0$ とする。

  1. $P=\exp\sum_K\phi_K$ なら、$\Pr(X_v=s\mid X_{V\setminus v}=x_{V\setminus v})$ は
    $$ \frac{\exp\sum_{K\ni v}\phi_K(s,x_{K\setminus v})}{\sum_{s'\in S_v}\exp\sum_{K\ni v}\phi_K(s',x_{K\setminus v})} $$
    に等しく、$x_{\partial v}$ だけで決まる。
  2. 頂点を $1,\dots,n$ と番号づけ、$o\in\Omega$ を固定する。$x\in\Omega$ について $y^{(i)}=(x_1,\dots,x_{i-1},\,\cdot\,,o_{i+1},\dots,o_n)$ の第 $i$ 座標を除いた配置を条件として
    $$ \frac{P(x)}{P(o)}=\prod_{i=1}^n\frac{\Pr(X_i=x_i\mid X_{V\setminus i}=y^{(i)})}{\Pr(X_i=o_i\mid X_{V\setminus i}=y^{(i)})} $$
    である。とくに、局所特性の全体が $P$ を決める。

1. 条件付き確率を比で書くと、$v$ を含まない $K$ の因子は分子と分母で打ち消す。$v$ を含むクリークの頂点は $\{v\}\cup\partial v$ に入る。
2. $i$ 番目の因子は、条件付き確率の定義から $P(x_1,\dots,x_i,o_{i+1},\dots,o_n)/P(x_1,\dots,x_{i-1},o_i,\dots,o_n)$ に等しい。積は順に打ち消し合い、$P(x)/P(o)$ になる。最後に $\sum_xP(x)=1$ で $P(o)$ が決まる。$\square$

1 は Gibbsサンプリング がそのまま使える理由である。頂点を順に局所特性で更新すると、分配関数を計算せずに $P$ を不変にする連鎖が作れる。一方、分配関数そのものの計算は一般に難しい。

例

道の上の Markov 確率場と Markov 連鎖

$G$ を道 $1-2-\dots-n$ とする。クリークは辺と頂点なので、正値な Markov 確率場は $P(x)=\prod_if_i(x_i,x_{i+1})$ の形で、$X$ は時間のどちらの向きにも Markov 連鎖である(Gri18 p. 147)。
$n=3$、2 値で、初期分布を一様、同じ値にとどまる確率を $\frac45$ とすると、$P(000)=P(111)=0.32$、$P(001)=P(011)=P(100)=P(110)=0.08$、$P(010)=P(101)=0.02$ である。$o=000$ として値 $1$ でのポテンシャルは
$$ \phi_{1}=\phi_{3}=\log\tfrac14\approx-1.3863,\quad\phi_{2}=\log\tfrac1{16}\approx-2.7726,\quad\phi_{12}=\phi_{23}=\log16\approx2.7726, $$
$\phi_{13}=\phi_{123}=0$、$\phi_\emptyset=\log0.32\approx-1.1394$ である。頂点 $1,3$ は隣り合わないので $\phi_{13}=0$ で、thm-mrf-hc のとおりである。

4 閉路の上のスピン系

$G$ を 4 閉路 $1-2-3-4-1$ とし、$\sigma\in\{\pm1\}^4$ に $P(\sigma)\propto\exp(\frac12\sum_{\{u,v\}\in E}\sigma_u\sigma_v)$ を与える(Isingモデル で $\beta=\frac12$、$h=0$)。分配関数は $Z\approx27.0488$ である。局所特性は $s=\sigma_2+\sigma_4$ だけで決まり、$\Pr(\sigma_1=+1\mid\text{残り})=e^{s/2}/(2\cosh(s/2))$ で、$s=2$ なら $\approx0.8808$、$s=0$ なら $0.5$ である。
対角の $\sigma_1,\sigma_3$ は隣り合わないが、$E[\sigma_1\sigma_3]\approx0.4085$ で、周辺では独立でない。独立になるのは $\sigma_2,\sigma_4$ を与えたときである。Markov 性は条件付きの主張で、遠くの変数の相関がないことは言っていない。

辺の因子だけでは足りない

3 頂点の完全グラフで、$x\in\{0,1\}^3$ に、$x_1+x_2+x_3$ が偶数なら $\frac3{16}$、奇数なら $\frac1{16}$ を与える。どの 2 変数も周辺で独立で一様だが、残りの 1 変数を与えると独立でないので、対の Markov 性からは辺を 1 本も除けない。$\phi_{123}(1,1,1)=\log\frac1{81}\approx-4.3944$ は $0$ でない。よって 3 変数の因子が要る。thm-mrf-hc の分解はクリーク全部にわたるもので、辺の因子だけで書けるとは限らない(ESL17 §17.2、p. 629 も完全グラフの高次の依存について注意している)。

Gauss の場合:精度行列

$X$ を $\mathbb{R}^V$ の正規分布 $N(\mu,\Sigma)$($\Sigma$ は正定値)、$Q=\Sigma^{-1}$ を 精度行列 とする。異なる $u,v$ について、$X_u$ と $X_v$ が残りの変数を与えて条件付き独立であることと $Q_{uv}=0$ は同値である。

$\mu=0$ としてよい。密度は $\exp(-\frac12\sum_{i,j}Q_{ij}x_ix_j)$ に比例する。残りを $z$ で固定すると、$(x_u,x_v)$ の条件付き密度は $\exp(-\frac12Q_{uu}x_u^2-\frac12Q_{vv}x_v^2-Q_{uv}x_ux_v+\ell_z(x_u,x_v))$($\ell_z$ は 1 次式)に比例する。これは 2 変量正規分布で、$x_ux_v$ の項がないことと積の形に分かれること、すなわち独立であることは同値である。$\square$

連続な変数では条件付き独立を条件付き密度で読む。$\Sigma$ の成分は周辺の共分散で、$Q$ の成分が条件付きの依存を表す。たとえば $\Sigma_{ij}=2^{-\lvert i-j\rvert}$($3$ 変数の Gauss過程、自己回帰)では $\Sigma$ に零はないが
$$ Q=\frac43\begin{pmatrix}1&-\frac12&0\\-\frac12&\frac54&-\frac12\\0&-\frac12&1\end{pmatrix} $$
で、$Q_{13}=0$ からグラフは道 $1-2-3$ である。多変量正規分布 では、周辺の共分散ではなく精度行列がグラフを決める。

反例:仮定を外すと成り立たないこと

thm-mrf-hc の仮定は正値だけである。外すと次の 3 つの含意がそれぞれ成り立たなくなる。

(P)・(L)・(G) の違い

(P) から (L) が出ない。 $G$ を 3 頂点で辺のないグラフとし、$X_1=X_2=X_3$ を公平な硬貨の値とする。残りの 1 変数を与えるとすべて決まるので (P) は成り立つ。(L) は $\partial v=\emptyset$ なので $X_1$ と $(X_2,X_3)$ の独立を要求し、成り立たない。
(L) から (G) が出ない。 $G$ を道 $1-2-3-4-5$ とし、$U$ を公平な硬貨の値、$X_1=X_2=X_4=X_5=U$、$X_3=0$ とする。各 $v$ で $X_{\partial v}$ を与えると残りは決まるか定数なので (L) は成り立つ($\partial3=\{2,4\}$、$\partial1=\{2\}$ などを順に見る)。$C=\{3\}$ は $\{1,2\}$ と $\{4,5\}$ を分離するが、$X_3$ は定数で $X_2=X_4$ なので (G) は成り立たない。

大域 Markov 性をみたし因子分解しない分布

$G$ を 4 閉路 $1-2-3-4-1$ とし、$x_1x_2x_3x_4\in\{0,1\}^4$ の次の 8 つの配置に確率 $\frac18$ を与える(ほかは $0$)。
$$ 0000,\ 1000,\ 1100,\ 1110,\ 1111,\ 0111,\ 0011,\ 0001. $$
この分布は (G) をみたすが (F) をみたさない。これは Moussouris の例である(Gri18 Exercise 7.2、p. 155)。

確かめを開く

(G):4 閉路で辺の両端でない頂点を分離する組は $A=\{1\},B=\{3\},C=\{2,4\}$ と $A=\{2\},B=\{4\},C=\{1,3\}$ だけである。$(x_2,x_4)$ を与えると、$00$ では $x_1\in\{0,1\}$ で $x_3=0$、$10$ では $x_1=1$ で $x_3\in\{0,1\}$、$01$ では $x_1=0$ で $x_3\in\{0,1\}$、$11$ では $x_1\in\{0,1\}$ で $x_3=1$ で、どれも片方が定数なので独立である。$(x_1,x_3)$ を与えた場合も同じである。

(F):クリークは辺と頂点と空集合なので、(F) なら頂点の因子を辺の因子へ入れて $P(x)=\psi_{12}(x_1,x_2)\psi_{23}(x_2,x_3)\psi_{34}(x_3,x_4)\psi_{41}(x_4,x_1)$ と書ける。$P(0000)>0$ から $\psi_{12}(0,0)$、$\psi_{41}(0,0)$ は正、$P(0011)>0$ から $\psi_{23}(0,1)$ は正、$P(1110)>0$ から $\psi_{34}(1,0)$ は正である。すると $P(0010)=\psi_{12}(0,0)\psi_{23}(0,1)\psi_{34}(1,0)\psi_{41}(0,0)>0$ となり、$0010$ が 8 つの配置にないことに反する。

外す条件反例成り立たなくなること
正値((P) ⇒ (L))$X_1=X_2=X_3$、辺なし(P) だが (L) でない
正値((L) ⇒ (G))道の上の $U,U,0,U,U$(L) だが (G) でない
正値((G) ⇒ (F))ex-mrf-moussouris(G) だが (F) でない
3 頂点以上のクリークの因子(辺の因子だけに制限)ex-mrf-parity完全グラフで (G) だが、辺の因子だけの積にならない

有向グラフと無限のグラフ

有向グラフ。 有向非巡回グラフ の上のモデルは $P(x)=\prod_vP(x_v\mid x_{\mathrm{pa}(v)})$ で与えられる。各因子は $\{v\}\cup\mathrm{pa}(v)$ の関数なので、辺の向きを忘れ、同じ子をもつ頂点(親どうし)の間にも辺を足した無向グラフについて (F) をみたし、prop-mrf-chain により (G) をみたす。ただし表せる独立性は同じではない。$X_1,X_2$ が独立で $X_3=X_1+X_2$ なら、周辺の独立 $X_1\perp X_2$ は有向グラフ $1\to3\leftarrow2$ で表せるが、無向グラフでは $X_1,X_2$ の間に辺が要り、周辺の独立は読めなくなる。有向の側の分離の規則は Bis06 §8.2、§8.3.1(pp. 378–384)にある。
無限のグラフ。 格子のような無限のグラフでは、全体の密度が定義できないので、有限の部分の条件付き分布で Gibbs 性を定める。これが Gibbs測度 の定義「DLR 方程式」で、同じポテンシャルに分布が複数ありうる(相転移)。この記事の定理は有限のグラフのものである。

関連項目

参考文献

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する