MIT OCW, Machine Learning 16日目

Rohit Singh, Tommi Jaakkola, and Ali Mohammad. 6.867 Machine Learning. Fall 2006. Massachusetts Institute of Technology: MIT OpenCourseWare, https://ocw.mit.edu. License: Creative Commons BY-NC-SA.

• • Bayesian networks
    • Marginal independence and induced dependence
      • Explaining away
      • Bayesian networks and conditional independence
      • Graph and the probability distribution

Bayesian networks

Bayesian networkは確率的な情報を表現し,使うのに有用なモデルである. Bayesian networkは1. 有向グラフと,2. それに付随する確率分布からなる. グラフは確率変数たちの質的な関係(条件付き独立性)を表現し,確率分布は確率変数たちの量的な関係を記述する. HMMでforward-backward algorithmが効率的であったのはMarkov性ゆえであり,これをBayesian networkの場合にも一般化するため,確率変数同士の独立性,条件付き独立性,従属性を明確に記述するグラフは非常に重要である.
まずは単純なBayesian networkを挙げる(fig.1). 確率変数$x_1, x_2$は独立なコイントスの結果で,$0, 1$のどちらかの値を取る. また$x_3=\delta(x_1,x_2), \text{ Kronecker's delta}$で確率変数$x_3$を定義する. 状況設定から同時分布は

$$P(x_1, x_2, x_3) = P(x_1)P(x_2)P(x_3|x_1,x_2)\ \ \ \ (1)$$
とわかるが,同じ分布をfig.1のグラフだけから導ける. その前にいくつかの用語を定義する.
$x_1$から$x_3$への辺が有るから,$x_1$は$x_3$のparent(親)であり,$x_3$は$x_1$のchild(子)であるという. $x_2$もまた$x_3$の親であり,このとき$x_3$は$x_1$と$x_2$に従属する. グラフに合致した同時確率分布は必ず,それぞれの確率変数の親たちによって条件付けられた条件付き確立の積として書ける. よって(1)はfig.1のグラフと合致している.

Marginal independence and induced dependence

$$\begin{aligned} P(x_1, x_2) &= \sum_{x_3}P(x_1,x_2,x_3)=\sum_{x_3}P(x_1)P(x_2)P(x_3|x_1,x_2)\\ &=P(x_1)P(x_2)\sum_{x_3}P(x_3|x_1,x_2)=P(x_1)P(x_2) \end{aligned}$$
このように,他の確率変数を無視すると周辺分布が独立になるとき,marginary independentであるという. これはグラフからも見て取れる.

確率変数のもう一つの典型的な関係はinduced dependenceである. $x_1, x_2$の現れを与えられず,$x_3$の現れのみを与えられた場合を考える.$x_3=1$ならば$x_1=x_2=1$か$x_1=x_2=0$のどちらかに決まり,$x_3=0$ならば$x_2 = 1-x_1$に決まるから,$x_1$が決まれば$x_2$が決まるし,$x_2$が決まれば$x_1$が決まる. すなわち$x_3$が決定されると$x_1,x_2$はdependentな関係になる. これは後で述べる方法によってグラフから見て取れる.

marginal independence とinduced dependenceは現実のモデルでよく現れる.　fig.2cのfactorial Hidden Markov Modelはその例である. このモデルでは2つの周辺独立なMarkov chainが観測値を作り出している. 換言すれば,2つのMarkov chainが観測値によってのみ結び付けられているということである(induced dependence). このモデルからサンプリングするには,2つのMarkov modelから独立にサンプリングを行い,各時点において2つのstateから観測値をサンプリングする. fig.2cの同時分布は

$$P(x_1')P(x_1)P(y_1|x_1',x_1)P(x_2'|x_1')P(x_1|x_1)P(y_2|x_2,x_2')P(x_3'|x_2')P(x_3|x_2)P(y_3|x_3,x_3')$$
とfactorizationできる. このモデルは例えば二人が話しているのを1つのマイクで録音し,それぞれの人が何を話したか推測したり,2つのハプロタイプから生成された表現型からもとのハプロタイプを推測するのに利用できる.

Explaining away

また,Bayesian networkでうまく把握できる確立モデルにexplaning awayがある.Pearl, 1988による,強盗警報機の鳴る原因のモデル(fig.3)を例に見る. 4つの二値(0, 1)確率変数$A, B, E, R$があって,
$A$は警報機,$B$,$E$は地震,$R$はラジオで地震情報がなされていることを代表している.
$P(E=1)=P(B=1) \sim 0,P(A=1|E,B) \sim (E \lor B),P(R=1|E=1)\sim 1, P(R=1|E=0)=0$
を仮定する. fig.3で影のついた確率変数の情報のみを持っているとする.
$A=1$のみが解っているときを考える(fig.3.b).$E=1$か$B=1$の少なくとも一方が成立しているとわかるが,$E,B$ともに滅多に生じない事象だから,$B=E=1$は必ず起きないと仮定する. この仮定のもとで$R=1$の情報を得たら$E=1,B=0$を確信し,$B=1$を排除(explain away)できる. したがって

$$P(E=1|A=1,R=1) \sim 1, \ \ P(B=1|A=1,R=1)\sim 0$$
である. ここで$R,B$は$A=1$のもとで条件付き従属であることを使った.これもまたグラフから見て取れる性質である.

Bayesian networks and conditional independence

グラフはもともと変数の独立性をencodeしているから,その独立性をextractするための基準が必要である. Bayesian networkの場合,この基準をD-separtation criterionという.

例えば先程のモデルを拡張したfig.4aを考える.ここで$L$は,警報がなったので帰宅したという事象を代表する変数である. $R,B$は$A$のもとで独立か否かと言った問いに答えるための手順を考える.
1. 対象の変数のancestral graphを構成する. ここでは対象とは$R,B,A$であって,ancestral graphはこれらとともに,これらの変数に至る有向辺を何ステップでも辿って現れる変数全てを含む. 今の場合,ancestral graphはfig.4bである.
2. 得られたancestral graphにおいて,子ノードを共有するノード間に無向辺を加える. 3つ以上のノードが子ノードを共有する場合には,それらのつくる全てのペアについて辺を加える(fig.4c).これをmoralizeという.
3. 全ての有向辺を無向辺に置き換え,無向グラフ(fig.4d)を得る.

結果得られた無向グラフから,もとの問の答えを読み取れる. 得られた無向グラフから$A$とそれに結ばれた辺を取り去ったとき,$R$と$B$を結ぶpathが存在しなければ$R,B$は$A$によって条件付き独立であり,存在すれば条件付き独立であると言える. したがってfig.4dから,$R,B$は$A$によって条件付き従属である.

fig.1に立ち返り,D-separated criterionを使うと,fig.5によって$x_1,x_2$がmarginally independentであることが見て取れるし,fig.6から$x_1,x_2$が$x_3$によって条件付従属であることが見て取れる.

Graph and the probability distribution

以上の議論は,グラフとそれに対応付けられる確率分布がconsistentであるときにのみ成立する. consistentとは,グラフから見て取れる全ての(条件付き含む)独立性が,確率分布の上でも言えるということである. グラフから見て取れる独立性というのは数多く存在する.
$d$個のノードをもつ循環しないグラフ$G$が与えられたとき,

$$P(x_1,...,x_d)=\prod_{i=1}^d P(x_i| x_{{pa}_i})$$
はそのグラフとconsistentであることが知られている.ただし$pa_i$は$x_i$の親ノードの集合である.