Bayesネットワーク

同義語:ベイジアンネットワークベイズネットワークBayesian network信念ネットワークbelief network有向グラフィカルモデルdirected graphical model

概要

Bayesネットワーク(Bayesian network)とは、有向非巡回グラフと、各変数の親を与えたときの条件付き確率の表の組であり、同時分布をそれらの積 $P(x)=\prod_vP(x_v\mid x_{\mathrm{pa}(v)})$ で与える確率モデルである。グラフから条件付き独立性を読む規則が $d$ 分離で、有限個の値をとる変数について、積への分解、各変数が親を与えれば非子孫と独立であること、$d$ 分離されたものが条件付き独立であることの 3 つは同値である。証明の鍵は、$d$ 分離を祖先の部分の道徳グラフでの分離に言い換えることにある。Markov 同値なグラフは骨格と v 構造が等しい。

$$\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確率場

家に警報器があり、泥棒が入っても地震が起きても鳴ることがあるとする。警報が鳴ったと聞けば泥棒を疑うが、そのあと地震があったと知れば、泥棒の疑いは大きく下がる。泥棒と地震はもともと無関係なのに、「警報が鳴った」という情報を通して互いに影響し合う。このような変数の間の依存関係を、矢印のグラフと各変数の「親が決まったときの条件付き確率」の表で表したものが Bayes ネットワーク である。
Bayes ネットワークの要点は、同時分布が「各変数の、親を与えたときの条件付き確率」の積に分解することと、グラフから条件付き独立性を読みとる規則(d 分離)があることである。この記事では主定理として、有限個の値をとる変数について、(F) 積への分解、(L) 各変数が親を与えれば親以外の非子孫と独立であること、(G) d 分離されたものは条件付き独立であること、の 3 つが同値であることを証明する。証明の鍵は、d 分離を「祖先の部分を無向グラフに直したときの分離」に言い換える補題で、そこから先は Markov確率場 の議論に帰着する。系として Markov ブランケットを求め、同じ独立性を表すグラフ(Markov 同値)の必要条件を示す。

定義

$V$ を有限集合とし、$G$ を $V$ を頂点とする 有向非巡回グラフ とする。辺 $u\to v$ があるとき $u$ を $v$ の 親、$v$ を $u$ の 子 という。$v$ の親の集合を $\mathrm{pa}(v)$、$v$ から辺の向きに沿ってたどれる頂点($v$ 自身を含めない)の集合を $\mathrm{de}(v)$(子孫)、$\mathrm{nd}(v):=V\setminus(\mathrm{de}(v)\cup\{v\})$ を 非子孫 という。$u\in\mathrm{de}(v)$ のとき $v$ を $u$ の 祖先 という。$S\subset V$ について、$S$ の頂点とその祖先の全体を $\mathrm{An}(S)$ と書く。$\mathrm{pa}(v)\subset H$(すべての $v\in H$)となる $H\subset V$ を 祖先的 という。$\mathrm{An}(S)$ は祖先的である。
各 $v\in V$ に空でない有限集合 $\mathcal X_v$ をとり、$X=(X_v)_{v\in V}$ を $\prod_v\mathcal X_v$ に値をとる確率変数、$P(x)=\Pr(X=x)$ とする。$A\subset V$ について $x_A=(x_v)_{v\in A}$、$P(x_A)=\Pr(X_A=x_A)$ と書く。条件付き独立は Markov確率場 と同じく、互いに素な $A,C,S$ について、すべての配置で
$$ P(x_A,x_C,x_S)\,P(x_S)=P(x_A,x_S)\,P(x_C,x_S) $$
が成り立つことと定め、$X_A\perp X_C\mid X_S$ と書く($S=\emptyset$ なら $P(x_\emptyset)=1$ と読み、普通の独立になる)。

Bayes ネットワーク

有向非巡回グラフ $G$ と、各 $v\in V$ について関数 $k_v\colon\mathcal X_v\times\prod_{u\in\mathrm{pa}(v)}\mathcal X_u\to[0,1]$ で、親の値 $x_{\mathrm{pa}(v)}$ を固定するごとに $\sum_{x_v}k_v(x_v\mid x_{\mathrm{pa}(v)})=1$ となるもの(条件付き確率表)の組を Bayes ネットワーク という。
$$ P(x)=\prod_{v\in V}k_v\bigl(x_v\mid x_{\mathrm{pa}(v)}\bigr) $$
をその 同時分布 という(以下この式を (F) と呼ぶ)。一般に、分布 $P$ がこの形に書けるとき、$P$ は $G$ に沿って 分解する という。

分解の基本性質

(F) の右辺は確率分布である。さらに、$P$ が (F) の形のとき、$P(x_{\mathrm{pa}(v)})>0$ となる親の値では $P(x_v\mid x_{\mathrm{pa}(v)})=k_v(x_v\mid x_{\mathrm{pa}(v)})$ である。

祖先的な集合への周辺化を使う

主定理の節の lem-bn-ancestral を使う(その証明は条件付き確率表の積の和の計算だけで、(F) の右辺が分布であることを使わない)。$H=\emptyset$ に当てると、(F) の右辺のすべての配置にわたる和は空の積 $1$ に等しく、右辺は確率分布である。次に $H:=\mathrm{An}(\{v\})$ とすると、$H$ と $H\setminus\{v\}$ はどちらも祖先的である($v$ の祖先の親は $v$ でない。そうでなければ有向閉路ができる)。補題を両方に当てて比べると $P(x_H)=k_v(x_v\mid x_{\mathrm{pa}(v)})\,P(x_{H\setminus\{v\}})$ で、$H\setminus(\{v\}\cup\mathrm{pa}(v))$ の座標について和をとれば $P(x_v,x_{\mathrm{pa}(v)})=k_v(x_v\mid x_{\mathrm{pa}(v)})\,P(x_{\mathrm{pa}(v)})$ を得る。$\square$

グラフから独立性を読む規則

$G$ の 道 とは、隣り合う 2 頂点が(向きを問わず)辺で結ばれた相異なる頂点の列 $v_0,v_1,\dots,v_m$($m\ge1$)である。道の内部の頂点 $v_i$($0< i< m$)で、前後の辺がともに $v_i$ を向く($v_{i-1}\to v_i\leftarrow v_{i+1}$)ものを 合流点 という。

d 分離

$S\subset V$ とする。道の内部の頂点 $m$ で、(1) $m$ が合流点でなく $m\in S$ であるか、(2) $m$ が合流点で $m\notin\mathrm{An}(S)$($m$ も $m$ の子孫も $S$ に入らない)であるものが 1 つ以上あるとき、$S$ は道を 遮断する という。遮断されない道を($S$ について)活性な道 という。互いに素な $A,C,S\subset V$ について、$A$ の頂点と $C$ の頂点を結ぶどの道も $S$ が遮断するとき、$A$ と $C$ は $S$ で d 分離 されるという。

この定義は 因果推論 の定義「遮断と d 分離とバックドア基準」と同じである。3 頂点の道で読むと、鎖 $a\to b\to c$ と分岐 $a\leftarrow b\to c$ は $b$ を条件に入れると遮断され、合流 $a\to b\leftarrow c$ は $b$(またはその子孫)を条件に入れると活性になる。冒頭の警報の例は 3 番目の型である。

Markov 性

$G$ の上の分布 $P$ について次を定める。

  • (F) 分解:$P$ は $G$ に沿って分解する。
  • (L) 局所 Markov 性:すべての $v$ について $X_v\perp X_{\mathrm{nd}(v)\setminus\mathrm{pa}(v)}\mid X_{\mathrm{pa}(v)}$。
  • (G) 大域 Markov 性:互いに素な $A,C,S$ で、$A$ と $C$ が $S$ で d 分離されるなら $X_A\perp X_C\mid X_S$。

公式の表

主張内容根拠
分解$P(x)=\prod_vP(x_v\mid x_{\mathrm{pa}(v)})$def-bn-main、prop-bn-factor
主定理(F) $\iff$ (L) $\iff$ (G)thm-bn-main
祖先への周辺化祖先的な $H$ では $P(x_H)=\prod_{v\in H}k_v$lem-bn-ancestral
d 分離の言い換えd 分離 $\iff$ $\mathrm{An}(A\cup C\cup S)$ の道徳グラフで $S$ が $A,C$ を分離lem-bn-moral
Markov ブランケット$X_v\perp X_{\text{残り}}\mid X_{\mathrm{mb}(v)}$、$\mathrm{mb}(v)$ は親・子・子の他の親cor-bn-blanket
Markov 同値の必要条件骨格と v 構造が一致prop-bn-equivalence
d 分離の完全性d 分離されない組には、分解するのに独立でない分布があるrem-bn-complete(証明しない)

主定理

分解と Markov 性の同値

$G$ を有向非巡回グラフ、$P$ を $\prod_v\mathcal X_v$ 上の分布とする。$P$ について (F)、(L)、(G) は同値である。

証明のために 3 つの補題を用意する。

祖先的な集合への周辺化

$P$ が (F) の形 $P(x)=\prod_vk_v(x_v\mid x_{\mathrm{pa}(v)})$ で、$H\subset V$ が祖先的なら、$P(x_H)=\prod_{v\in H}k_v(x_v\mid x_{\mathrm{pa}(v)})$ である。

子のない頂点を 1 つずつ和で消す

$\lvert V\setminus H\rvert$ についての帰納法で示す。$V\setminus H$ が空でないとする。$t\notin H$ の子 $h$ が $H$ にあれば $t\in\mathrm{pa}(h)\subset H$ となって矛盾するので、$V\setminus H$ の頂点の子はすべて $V\setminus H$ にある。有向非巡回グラフ の定理「有向非巡回グラフの言い換え」の 3 の順で $V\setminus H$ の最後の頂点 $t$ をとると、$t$ は子をもたない。$x_t$ を含む因子は $k_t$ だけなので、$x_t$ について和をとると $\sum_{x_t}k_t=1$ により
$$ P(x_{V\setminus\{t\}})=\prod_{v\ne t}k_v(x_v\mid x_{\mathrm{pa}(v)}) $$
である。これはグラフ $G-t$ に沿う分解で、$H$ は $G-t$ でも祖先的なので、帰納法の仮定から結論を得る。$\square$

$G$ の祖先的な部分 $H$ の 道徳グラフ $(G_H)^{\mathrm m}$ とは、$H$ を頂点とし、$G$ の $H$ の中の辺の向きを忘れたものに、$H$ の中に共通の子をもつ 2 頂点(「親どうし」)を結ぶ辺を足した無向グラフである。$\{v\}\cup\mathrm{pa}(v)$($v\in H$)はこのグラフのクリークである。
d 分離を道徳グラフでの分離に言い換えるため、道の代わりに頂点の重複を許す列を使う。$G$ の 歩道 とは、隣り合う 2 頂点が辺で結ばれた頂点の列 $v_0,\dots,v_m$($m\ge1$、重複を許す)である。内部の各 出現 $v_i$($0< i< m$)について、前後の辺がともに $v_i$ を向くとき合流点という。歩道が $S$ について 活性 であるとは、合流点である内部の出現がすべて $\mathrm{An}(S)$ に属し、合流点でない内部の出現がすべて $S$ に属さないことをいう。重複のない歩道(道)では、これは def-bn-dsep の活性と同じである。

歩道から道へ

$a\ne c$、$a,c\notin S$ とする。$a$ から $c$ への $S$ について活性な歩道があれば、$a$ から $c$ への $S$ について活性な道がある。

最短の活性な歩道に重複がないことを示す

$a$ から $c$ への活性な歩道のうち最短のもの $W=(v_0,\dots,v_m)$ をとり、ある頂点 $x$ が $v_i=v_j=x$($i< j$)と 2 回現れるとして矛盾を導く。$W':=(v_0,\dots,v_i,v_{j+1},\dots,v_m)$ は $a$ から $c$ への、より短い歩道である($i=0$ や $j=m$ でも $v_0=a$、$v_m=c$ は変わらない)。つなぎ目以外の内部の出現は前後の辺が $W$ と同じなので条件を保つ。つなぎ目 $x$ が内部の出現($0< i$、$j< m$)のとき、前の辺を $e=\{v_{i-1},x\}$、後ろの辺を $e'=\{x,v_{j+1}\}$ とする。
つなぎ目が合流点でないとき。 $x\in S$ と仮定する。$W$ で $x$ の出現 $i$、$j$ はどちらも内部の出現で $S$ に属すので合流点であり、$e$ も $e'$ も $x$ を向く。するとつなぎ目は合流点になり矛盾。よって $x\notin S$。
つなぎ目が合流点のとき。 $x\notin\mathrm{An}(S)$ と仮定する。$W$ で $x$ の出現 $i$、$j$ は合流点でない。$e$ は $x$ を向くので、出現 $i$ の後ろの辺は $x\to v_{i+1}$ である。$e'$ も $x$ を向くので、出現 $j$ の前の辺は $x\to v_{j-1}$ である。部分の歩道 $v_i,\dots,v_j$ をたどると、最初の辺は矢印の向きに進み、最後の辺は矢印に逆らって進む。そこで、矢印に逆らって進む最初の辺 $\{v_r,v_{r+1}\}$($i< r< j$)をとると、$x=v_i\to v_{i+1}\to\cdots\to v_r\leftarrow v_{r+1}$ で、$v_r$ は $W$ の合流点の出現である。活性性から $v_r\in\mathrm{An}(S)$、一方 $v_r\in\mathrm{de}(x)$ なので $x\in\mathrm{An}(S)$ となり矛盾。
どちらの場合も $W'$ は活性で、$W$ の最短性に反する。よって $W$ は道である。$\square$

d 分離と道徳グラフでの分離

互いに素な $A,C,S\subset V$ について、$H:=\mathrm{An}(A\cup C\cup S)$ とする。$A$ と $C$ が $S$ で d 分離されることと、道徳グラフ $(G_H)^{\mathrm m}$ で $A$ の頂点から $C$ の頂点へのどの道も $S$ の頂点を通ることは同値である。

道徳グラフの道を活性な歩道に直す

道徳グラフでの分離 ⇒ d 分離。 対偶を示す。$a\in A$ から $c\in C$ への活性な道 $p$ があるとする。$p$ の合流点は $\mathrm{An}(S)$ に属す。合流点でない頂点からは、$p$ に沿って出ていく辺があり、その向きに $p$ をたどると端点か合流点に着くので、その頂点は $\mathrm{An}(A\cup C\cup S)$ に属す。よって $p$ の頂点はすべて $H$ にある。合流点が 2 つ隣り合うことはない(間の辺が両方を向くことはない)ので、$p$ の合流点でない頂点(端点を含む)を順に並べると、隣り合うものは $G$ の辺で結ばれるか、合流点 $m\in H$ を共通の子にもち道徳グラフの辺で結ばれる。これらは $S$ に属さないので、$(G_H)^{\mathrm m}$ の中に $S$ を通らない $a$ から $c$ への道がある。
d 分離 ⇒ 道徳グラフでの分離。 対偶を示す。$(G_H)^{\mathrm m}$ の中に $a\in A$ から $c\in C$ への道 $a=w_0,\dots,w_l=c$ で、どの $w_i$ も $S$ に属さないものがあるとする。$G$ の辺でない道徳グラフの辺 $\{w_i,w_{i+1}\}$ を、共通の子 $h\in H$ を通る $w_i\to h\leftarrow w_{i+1}$ に置き換えると、$G$ の歩道で次の 2 条件を満たすものが得られる。

  • (α) すべての頂点が $H$ に属し、始点は $A$、終点は $C$ にある。
  • (β) 合流点でない内部の出現は $S$ に属さない。
    (挿入した $h$ は合流点で、合流点でない出現は元の $w_i$ なので $S$ に属さない。)(α)(β) を満たす歩道のうち、$\mathrm{An}(S)$ に属さない合流点の出現(悪い合流点)の個数が最小のもの $W$ をとる。
    悪い合流点がなければ $W$ は活性で、lem-bn-walk により $A$ と $C$ を結ぶ活性な道があり、d 分離に反する。悪い合流点の出現 $y_0$ があるとする。$y_0\in H\setminus\mathrm{An}(S)$ なので $y_0\in\mathrm{An}(A\cup C)$ であり、有向道 $y_0\to y_1\to\cdots\to y_r\in A\cup C$($r\ge0$)がある。どの $y_t$ も $S$ に属さない(属せば $y_0\in\mathrm{An}(S)$)。$y_r\in A$ なら、新しい歩道を
    $$ y_r,\ y_{r-1},\ \dots,\ y_1,\ y_0,\ (W\text{ の }y_0\text{ の出現より後ろ}) $$
    とする。$y_1,\dots,y_{r-1}$ と $y_0$ は前の辺が自分から出ていくので合流点でなく、$S$ に属さないので (β) を満たし、すべて $H$ に属す。$W$ の後ろの部分の出現の状態は変わらない。この歩道は (α)(β) を満たし、悪い合流点は $W$ より少ない($y_0$ の出現と、それより前の出現がなくなる)。$y_r\in C$ なら、$W$ の $y_0$ の出現までの部分のあとに $y_1,\dots,y_r$ をつなぐ。どちらも $W$ の最小性に反する。$\square$
主定理

(F) ⇒ (G). $A$ と $C$ が $S$ で d 分離されるとし、$H:=\mathrm{An}(A\cup C\cup S)$ とする。lem-bn-ancestral により $P(x_H)=\prod_{v\in H}k_v(x_v\mid x_{\mathrm{pa}(v)})$ で、各因子は道徳グラフ $(G_H)^{\mathrm m}$ のクリーク $\{v\}\cup\mathrm{pa}(v)$ の関数である。よって $X_H$ の分布は $(G_H)^{\mathrm m}$ についてクリークの因子分解をもつ。lem-bn-moral により $(G_H)^{\mathrm m}$ で $S$ は $A$ と $C$ を分離するので、Markov確率場 の命題「含意の列」(因子分解 ⇒ 大域 Markov 性)から $X_A\perp X_C\mid X_S$ である。
(G) ⇒ (L). $v\in V$、$S:=\mathrm{pa}(v)$、$w\in\mathrm{nd}(v)\setminus\mathrm{pa}(v)$ とし、$v$ から $w$ への道 $p$ を $S$ が遮断することを示す。$p$ の最初の辺が $u\to v$ なら、$u\ne w$ なので $u$ は内部の頂点で、$u$ から辺が出ていくので合流点でなく、$u\in S$ だから $p$ は遮断される。最初の辺が $v\to u$ なら、$w\notin\mathrm{de}(v)$ なので、$p$ は最後まで矢印の向きには進めない。矢印に逆らう最初の辺の手前の頂点 $m$ は合流点で、$m\in\mathrm{de}(v)$ である。$m$ とその子孫はすべて $v$ の子孫で、非巡回性から $\mathrm{pa}(v)$ に属さないので、$m\notin\mathrm{An}(S)$ であり $p$ は遮断される。よって $\{v\}$ と $\mathrm{nd}(v)\setminus\mathrm{pa}(v)$ は $\mathrm{pa}(v)$ で d 分離され、(G) から (L) が従う。
(L) ⇒ (F). 位相的整列 で頂点を $v_1,\dots,v_N$ と並べ、$\mathrm{pr}(v_j):=\{v_1,\dots,v_{j-1}\}$ とおく。$\mathrm{pa}(v_j)\subset\mathrm{pr}(v_j)\subset\mathrm{nd}(v_j)$ である。(L) の等式を $\mathrm{nd}(v_j)\setminus\mathrm{pr}(v_j)$ の座標について和をとると、$X_{v_j}\perp X_{\mathrm{pr}(v_j)\setminus\mathrm{pa}(v_j)}\mid X_{\mathrm{pa}(v_j)}$ を得る。$k_v(x_v\mid x_{\mathrm{pa}(v)})$ を、$P(x_{\mathrm{pa}(v)})>0$ なら $P(x_v\mid x_{\mathrm{pa}(v)})$、そうでなければ $\mathcal X_v$ 上の一様分布と定める。この条件付き独立から、$P(x_{\mathrm{pr}(v_j)})>0$ のとき $P(x_{v_j}\mid x_{\mathrm{pr}(v_j)})=k_{v_j}(x_{v_j}\mid x_{\mathrm{pa}(v_j)})$ である。配置 $x$ を固定する。すべての $j$ で $P(x_{v_1},\dots,x_{v_j})>0$ なら、条件付き確率の積の公式から $P(x)=\prod_jk_{v_j}$ である。そうでなければ $P(x_{v_1},\dots,x_{v_j})=0$ となる最小の $j$ をとると、$P(x)=0$ で、$P(x_{\mathrm{pr}(v_j)})>0$ だから $k_{v_j}=P(x_{v_j}\mid x_{\mathrm{pr}(v_j)})=0$ なので右辺も $0$ である。$\square$

(F) ⇒ (G) は GVP90 Theorem 1(p. 515)にあたる。そこでは、ある順序で「各変数は親を与えれば前の変数と独立」という独立性の一覧(recursive basis)から、条件付き独立性の満たす公理(graphoid の公理)だけを使って d 分離される組の独立性を導く、より一般の形で述べられている。ここでは道徳グラフを経由した証明を与えた。lem-bn-walk に当たる主張は同論文の Lemma 5(p. 517)にもあり、そこでは証明は別の文献に任されている。

d 分離の完全性

逆向きに、$A$ と $C$ が $S$ で d 分離されないなら、各変数の値の集合 $\mathcal X_v$ を適当にとれば($\mathcal X_v$ が 1 点の変数はどの変数とも独立なので、値の集合は選ぶ必要がある)、$G$ に沿って分解する分布で $X_A\perp X_C\mid X_S$ が成り立たないものがある(GVP90 Theorem 3 とその説明、p. 515)。したがって (G) は、グラフの形だけから読みとれる条件付き独立性をすべて尽くしている。ただし特定の分布は、グラフにない独立性を余分にもちうる(ex-bn-xor)。この記事では証明しない。

Markov ブランケット

$v$ の親、子、子の他の親をあわせた集合を $\mathrm{mb}(v)$ と書き、$v$ の Markov ブランケット という(Bis06 §8.2、pp. 382–383)。

Markov ブランケット

$P$ が $G$ に沿って分解するなら、すべての $v$ について $X_v\perp X_{V\setminus(\{v\}\cup\mathrm{mb}(v))}\mid X_{\mathrm{mb}(v)}$ である。とくに $P(x)>0$ なら、$P(x_v\mid x_{V\setminus\{v\}})$ は $x_v$ と $x_{\mathrm{mb}(v)}$ だけで決まり、
$$ P(x_v\mid x_{V\setminus\{v\}})\ \propto\ k_v(x_v\mid x_{\mathrm{pa}(v)})\prod_{w:\,v\in\mathrm{pa}(w)}k_w(x_w\mid x_{\mathrm{pa}(w)}) $$
(比例定数は $x_v$ によらない)である。

$H=V$ は祖先的なので、prf-bn-main の (F) ⇒ (G) と同じく $P$ は道徳グラフ $G^{\mathrm m}$ について因子分解する。$G^{\mathrm m}$ での $v$ の隣接頂点は、辺の親と子、および共通の子をもつ頂点(子の他の親)で、ちょうど $\mathrm{mb}(v)$ である。よって $\mathrm{mb}(v)$ は $v$ と残りを分離し、Markov確率場 の命題「含意の列」から独立性が従う。後半は、$P(x)=\prod_wk_w$ を $x_v$ について和をとった値で割ると、$x_v$ を含まない因子が約分されることによる。$\square$

後半の式は、Gibbsサンプリング で 1 変数ずつ値を引き直すときにそのまま使われる。

Markov 同値

2 つの有向非巡回グラフ $G,G'$(同じ頂点集合)が Markov 同値 であるとは、すべての互いに素な $A,C,S$ について「$G$ で d 分離」と「$G'$ で d 分離」が同値であることをいう。thm-bn-main と rem-bn-complete により、これは「各変数の値の集合をどうとっても、$G$ に沿って分解する分布の全体と、$G'$ に沿って分解する分布の全体が一致する」ことと同値である。$G$ の辺の向きを忘れた無向グラフを 骨格 といい、$u\to w\leftarrow v$ で $u,v$ が隣り合わないものを v 構造 という。

Markov 同値の必要条件

$G$ と $G'$ が Markov 同値なら、骨格が等しく、v 構造も等しい。

親の集合で分離する

分離する集合。 隣り合う $u,v$ は、内部の頂点のない道 $u,v$ をもつので、どの $S$ でも d 分離されない。隣り合わない $u,v$ については、非巡回性から一方は他方の子孫でない。$v\notin\mathrm{de}(u)$ とすると $v\in\mathrm{nd}(u)\setminus\mathrm{pa}(u)$ で、prf-bn-main の (G) ⇒ (L) の部分で示したとおり、$u$ と $v$ は $\mathrm{pa}(u)$ で d 分離される。よって「$u,v$ が隣り合う」は「どの $S$ でも d 分離されない」と同値で、Markov 同値なグラフの骨格は等しい。
v 構造。 $G$ に v 構造 $u\to w\leftarrow v$ があり、$G'$ では(骨格は同じで)$w$ がこの 3 頂点の道で合流点でないとする。$G'$ では、$u,v$ を d 分離する集合はかならず $w$ を含む(道 $u,w,v$ を遮断するには合流点でない $w$ を入れるしかない)。$G$ では、上の議論で $v\notin\mathrm{de}(u)$ として $S=\mathrm{pa}(u)$ が $u,v$ を d 分離し($u\notin\mathrm{de}(v)$ なら役を入れ替える)、$w$ は $u$(と $v$)の子なので $S$ に属さない。これは Markov 同値に反する。$\square$

逆に、骨格と v 構造が等しければ Markov 同値であることも知られている(Verma と Pearl による)。たとえば 3 頂点の鎖 $a\to b\to c$、逆向きの鎖 $a\leftarrow b\leftarrow c$、分岐 $a\leftarrow b\to c$ は Markov 同値で、どれも「$a\perp c\mid b$」だけを表す。合流 $a\to b\leftarrow c$ だけは「$a\perp c$」を表し、別の類になる。観察データから決められる矢印の向きは、v 構造の辺と、新しい v 構造や有向閉路を避けるために強制される辺に限られ、これが 因果推論 でグラフの向きを仮定として持ち込む理由である。

計算の手順

d 分離の判定は lem-bn-moral による。

  1. $H:=\mathrm{An}(A\cup C\cup S)$ を求め、$H$ の外の頂点を消す。
  2. $H$ の中で共通の子をもつ親どうしを辺で結び、すべての辺の向きを忘れる(道徳グラフ)。
  3. $S$ の頂点を消し、残りのグラフで $A$ から $C$ へ行けなければ d 分離されている。
    3 頂点の型条件なし$b$ を条件に入れる
    鎖 $a\to b\to c$活性(依存しうる)遮断($a\perp c\mid b$)
    分岐 $a\leftarrow b\to c$活性遮断
    合流 $a\to b\leftarrow c$遮断($a\perp c$)活性(説明による打ち消し)

例題

警報器と説明による打ち消し

泥棒 $B$、地震 $E$、警報 $A$ の 2 値変数が $B\to A\leftarrow E$ の Bayes ネットワークをなし、$P(B=1)=0.01$、$P(E=1)=0.02$、$P(A=1\mid B,E)$ は $(B,E)=(1,1),(1,0),(0,1),(0,0)$ で $0.95,\ 0.90,\ 0.30,\ 0.01$ とする。警報が鳴ったときの泥棒の確率と、さらに地震があったと知ったときの泥棒の確率を求める。
使う公式:def-bn-main の (F) と Bayesの定理。
答え:$P(A=1)=0.024652$、$P(B=1\mid A=1)\approx0.3655$、$P(B=1\mid A=1,E=1)\approx0.0310$、$P(B=1\mid A=1,E=0)\approx0.4762$。合流 $B\to A\leftarrow E$ により $B\perp E$ だが、$A$ を条件に入れると $B$ と $E$ は依存し、地震という別の説明が見つかると泥棒の確率は約 $12$ 分の $1$($0.3655$ から $0.0310$)に下がる。

途中の計算を開く

$P(A=1)=\sum_{b,e}P(b)P(e)P(A=1\mid b,e)=0.000190+0.008820+0.005940+0.009702=0.024652$。$P(B=1,A=1)=0.000190+0.008820=0.009010$ で、$0.009010/0.024652\approx0.3655$。$E=1$ も知ると $\frac{0.01\cdot0.95}{0.01\cdot0.95+0.99\cdot0.30}=\frac{0.0095}{0.3065}\approx0.0310$。$E=0$ なら $\frac{0.01\cdot0.90}{0.01\cdot0.90+0.99\cdot0.01}=\frac{0.009}{0.0189}\approx0.4762$。

排他的論理和

$X,N$ を独立な公平な $0,1$ の変数とし、$Y:=X\oplus N$(2 を法とする和)とする。分布は $X\to Y\leftarrow N$ に沿って分解する。
答え:$P(Y=1\mid X=x)=\frac12$($x=0,1$)なので $X\perp Y$ である。$X$ と $Y$ は辺で結ばれ d 分離されないのに独立で、グラフにない独立性を分布が余分にもつ例である(rem-bn-complete は「どの分布でも」ではなく「ある分布で」独立でないことを主張している)。一方 $X\perp N$ だが、$Y$ を条件に入れると $N=X\oplus Y$ が決まるので $X$ と $N$ は依存する($P(X=1\mid Y=1,N=0)=1\ne\frac12$)。

使える条件と反例

外す条件反例成り立たなくなること
グラフが非巡回2 値の $u,v$ に $u\to v\to u$、$k_u(x_u\mid x_v)=k_v(x_v\mid x_u)=\mathbf 1_{\{x_u=x_v\}}$積の総和が $2$ で、(F) が分布を定めない(prop-bn-factor)
合流点の子孫も見る$X\to Y\leftarrow N$ に $Y\to W$($W=Y$)を足し、$W$ を条件に入れる$W$ は $Y$ を写すので $X$ と $N$ は依存する。子孫の条件を落とすと誤って独立とする
道徳グラフは祖先的な部分で作る$X\to Y\leftarrow N$ 全体の道徳グラフには辺 $X\!-\!N$ がある全体のグラフでは $X\perp N$ が読めない。$\mathrm{An}(\{X,N\})=\{X,N\}$ では辺がなく分離が読める
分布が忠実(グラフの独立性しかもたない)ex-bn-xord 分離されなくても独立でありうる

よくある誤り

誤り正しくはなぜ
条件に入れる変数を増やせば独立になりやすい合流点(とその子孫)を入れると依存が生じるex-bn-alarm
矢印を因果の向きと読むMarkov 同値なグラフは同じ分布の族を表すprop-bn-equivalence
d 分離されないなら依存している「依存しうる」だけex-bn-xor
(L) を「親を与えれば他のすべてと独立」と読む子孫とは独立にならない。全体と独立になるのは Markov ブランケットを与えたときcor-bn-blanket

関連項目

参考文献

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