Markov確率場(Markov random field)とは、グラフの頂点に置いた確率変数の同時分布で、ある頂点集合が別の 2 つの頂点集合を分離するなら、それを与えて 2 つの集合の変数が条件付き独立になるものである。有限のグラフの上で、すべての配置に正の確率を与える分布については、これはグラフのクリークごとの因子の積に分解することと同値である(Hammersley–Clifford の定理)。正値の仮定を外すと同値は成り立たない。
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-gauss | Gauss 分布では精度行列の零の位置がグラフを与える |
$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$ の頂点を通ることをいう。
分布 $P$ について、次を定める。
(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)。
$P$ をすべての $x\in\Omega$ で $P(x)>0$ である分布とする。次は同値である。
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. 条件付き確率を比で書くと、$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$ を不変にする連鎖が作れる。一方、分配関数そのものの計算は一般に難しい。
$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 のとおりである。
$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 も完全グラフの高次の依存について注意している)。
$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$ を 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) は成り立たない。
$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アソシエイト)の紹介料で運営されています。 支援について / 寄付する