Prml8章

written

グラフィカルモデル

確率的グラフィカルモデルについて考える。確率的グラフィカルモデルでは、各ノードが確率変数を表す。ここでは、有向グラフからなるベイジアンネットワークと無向グラフからなるマルコフ確率場について考える。

ベイジアンネットワーク

ベイジアンネットでは、あるノードにおける確率は、 \[p(x)=\prod_{k=1}^{K}p(x_{k}|pa_{k})\] で表される。\(pa\)は親ノードの集合を表す。またすべてのノード対についてエッジを持つ場合全結合という。ベイジアンネットワークを用いると、様々なモデルをグラフィカルモデルとして捉えることができる。

条件付き独立性

グラフィカルモデルのいいところは、目で見るだけで関係がわかることである。これを有効分離という。条件付き独立性がわかると、モデルの縮小や、計算の効率化などができるようになる。グラフィカルモデルでの、条件付き独立性は、tail-to-tail、head-to-tail、head-to-headで分けられる。

tail-to-tail

条件となるノードを親に持つ集合。条件となるノードが観測されてなければ、独立ではなく、観測されていると独立になる。

head-to-tail

条件となるノードを子にもつノードと親にもつ集合。条件となるノードが観測されてなければ、独立ではなく、観測されていると独立になる。

head-to-head

条件となるノードを子にもつ集合。条件となるノードとその子が観測されてなければ、独立ではない。観測されていないと独立

有効分離

Cを条件ノードの集合としたとき、A、Bで表されるノード集合が独立であるかどうかを判断することを考える。 AからBへのすべての経路について考える。ここで、

集合Cに含まれるノードでhaed-to-tailまたは、tail-to-tailである
head-to-headで、自身あるいは、そのすべての子がCに含まれない

のうちいずれかを満たす経路は遮断されているという。AからBへのすべての経路が遮断されていると有効分離であるといえる。

マルコフブランケット

あるノードを残りのグラフから孤立させるための最小集合。観測されたあるノードの親と観測されたその子と観測された子の共同親からなる。

マルコフ確率場

無向グラフによって表される確率的グラフィカルモデル。ベイジアンネットワークと同じように、因数分解性と条件付き独立性を持っている。無向グラフの場合の条件付き独立は、あるノード集合と別のノード集合を結ぶ経路にノードが含まれているか否かで決まる。もしノードが含まれていたら条件付き独立となる。無向グラフの因数分解にはクリークという概念が必要になる。クリークとは、全結合なノードのこと、あるグラフでこれ以上ノードが追加できないクリークを極大クリークという。ある同時確率を無向グラフで、因子分解するとポテンシャル関数\(\psi_{C}\)を用いて、 \[p(x)=\frac{1}{Z}\prod_{C}\psi_{C}(x_{C})\] \[Z=\sum_{x}\prod_{C}\psi_{C}(x_{C})\] で表される。ポテンシャル関数は、確率関数でなくてもいいので、正則化が必要になる。またポテンシャル関数である条件は、任意の変数に対して正であること。例としてエネルギー関数\(E(x_{C})\)を用いて \[\psi_{C}(x_{C})=\exp\{-E(x_{C})\}\] で表されるボルツマン分布などがある。また、ベイジアンネットとマルコフ確率場は相互変換が可能である。変換の仕方は、最初に、親同士のリンクを張り、有向だった辺を無向にする。親同士のリンクを張ることをモラル化といい、できたグラフをモラルグラフという。次に、条件付き因子を対応するクリークに当てはめる。グラフと分布の関係について考える。あるグラフがある分布が満たす条件付き独立をすべて表現するとき、グラフを依存性マップと言う。あるグラフが持つ条件付き独立をある条件付き分布がすべて満たすなら、グラフを独立性マップと言う。独立性マップでも、依存性マップでもあるものを完全マップという。グラフィカルモデルの考え方は、有向グラフと無向グラフが混ざったものにも使え、そのグラフを連結グラフという。

グラフィカルモデルにおける推論

いくつかのノードが観測値によって固定された時に、残ったノードに関する事後確率を推論することを考える。まず連鎖のグラフについて考える。無向グラフのあるノード\(x_{n}\)における推定は、すべて観測されていないとすると \[p(x_{n})=\sum_{x_{1}}…\sum_{x_{N}}p(x)\] となる。これを、条件付き独立性を使うと、ポテンシャル関数の和の積になる。ここで、ポテンシャル関数の和を局所的なメッセージとして考え、積はメッセージを伝搬していると考えると、 \[p(x_{n})=\frac{1}{Z}\mu_{\alpha}(x_{n})\mu_{\beta}(x_{n})\] で表せる。Zは正則化項を表し、\(\mu_{\alpha}\)は、\(x_{1}\)から伝わるメッセージを表し、\(\mu_{\beta}\)は、\(x_{n}\)から伝わるメッセージを表す。観測値があった場合は、ポテンシャル関数の和ではなく、観測値のポテンシャル関数の単項になる。次にループを含まない木構造を持つグラフについて考える。まず因子グラフという考え方を導入する。因子グラフは、無向グラフの一種で、ノードは、変数ノードと因子ノードを持つ。因子ノードと変数ノード間のみリンクをもつ。この因子グラフを用いて木構造のグラフについて推論を行う。推論には、積和アルゴリズムなどがある。積和アルゴリズムについて考える。ある変数ノードxに入ってくるメッセージは、 \[p(x)=\prod_{s\in ne(x)}F_{s}(x,X_s)\] で表される。ne(x)は隣接してる因子ノードを表す。\(X_{s}\)は、因子ノードによってつながっている変数ノードを表す。この時周辺分布について考えると、 \[p(x)=\prod_{s\in ne(x)}\mu_{f_{s}\rightarrow x}(x)\] \[\mu_{f_{s}\rightarrow x}(x)=\sum_{X_{s}}F_{s}(x,X_{s})\] となる。変数ノードに入ってくるメッセージを因子ノードに入ってくるメッセージを用いて \[\mu_{f_{s}\rightarrow x}(x)=\sum_{x_{1}}…\sum_{x_{M}}f_{s}(x,x_{1}…x_{M})\prod_{m\in ne(f_{s})}\mu_{x_{m}\rightarrow f_{s}}(x_{m})\] \[\mu_{x_{m}\rightarrow f_{s}}(x_{m})=\sum_{X_{sm}}G(x_{m},X_{ms})\] となる。これらのメッセージをあるノードを根とし、初期ノードの値を1して、根から葉へ、葉から根へと流す。すべてのノードのメッセージが決まったので、任意の変数ノードの推定は、 \[p(x_{s})=f_{s}(x_{s})\prod_{i\in ne(f_{s})}\mu_{x_{i}\rightarrow f_{s}}(x_{i})\] でもとめられる。観測値があった場合は、各ノードの和ところが単項になる。ここで、木構造グラフのあるノードにおいて確率が最大となる変数の組を求めることを考える。これは、max-sumアルゴリズムや、max-productアルゴリズムなどで解ける。 max-productアルゴリズムは、積和アルゴリズムの和演算を最大値演算に変えたもの。 max-sumアルゴリズムは、積和アルゴリズムの対数をとり、和演算を最大値演算に変えたもの。単純に積和アルゴリズムのやり方を適応すると破綻する。そこで、葉からのメッセージを送る際に工夫をする。葉から初期メッセージは、０を渡す。そして各変数では、どの値が最大値を与えたかを \[\phi(x_{n})=\mathrm{argmax}_{x_{N}}[\ln f_{n-1,n}(x_{n-1},x_{n})+\mu_{x_{n-1}\rightarrow f_{n-1,n}}(x_{n})]\] で保存する。最大値をとる\(x_{n}\)が \[x_{N}=\mathrm{argmax}_{x_{N}}[\mu_{x_{n-1}\rightarrow f_{n-1,n}}(x_{n})]\] によって与えられ、それを元に、 \[x_{N-1}=\phi(x_{N})\] で葉まで辿っていき解を求める。葉まで辿っていくのをバックトラックという。最後にループを含むグラフについて考える。様々なアルゴリズムが存在するが、ここでは、積和アルゴリズムをループのあるグラフに使ったループあり確率伝播について考える。ループあり確率伝播では、メッセージを送るタイミングを変える必要がある。積和アルゴリズムでは、すべてのメッセージが届いてからメッセージを送信していたがループがあるとメッセージが届かないため、メッセージを送信できない。そこで、各時刻においてすべてのリンクのに両方向で、メッセージを送信するフラッディングスケジュールや、各時刻で一つしかメッセージを送信しない直列スケジュールなどがある。