確率的グラフィカルモデル (probabilistic graphical model) は確率分布を表したグラフです (ここで言う「グラフ」とは棒グラフや折れ線グラフとかのことではなく,ノードと辺で構成されるグラフのことです). 確率変数の間の依存関係をわかりやすく可視化することで, 訓練アルゴリズムの設計や各種解析などに役立ちます. 画像のノイズ除去や自然言語処理などに応用されていて,機械学習では結構重要な位置付けです. 今回は,グラフィカルモデルの一種であるマルコフ確率場が私の修論に利用できそうなので,調べてみました. この記事では,グラフィカルモデルの応用ではなく,基礎的な話を主に取り扱います. 数式たっぷりです.記事の内容を理解するためには,グラフと機械学習・確率論に関する基礎知識が必要です.

グラフィカルモデルでは,ノードは確率変数に対応し,辺は確率変数間の依存関係に相当します. ここで言う依存関係とは,確率変数が独立か否かということです. 知っての通り,確率変数 $x$, $y$ が独立であるならば,$p(x,y) = p(x) p(y)$ というように,周辺確率 (marginal probability) を2つの確率の積に分解することができます. グラフィカルモデルでは,独立ではない確率変数(ノード)間を辺で結ぶことで, どの確率変数が依存しているのかを表現します(厳密には,ただの独立性ではなく, 条件付き独立性ですが,それについては後述します). しかし,「独立ではない」だけでは,情報が大雑把すぎて,あまり意味がないので, もう少し具体的な依存関係を考えることが普通です. グラフィカルモデルは次の2種類に大別されます.

  • ベイジアンネットワーク (Bayesian network):有向グラフ(辺が方向を持つグラフ) で表現されるグラフィカルモデルで,「$x$ から $y$ への辺」は条件付き確率 (conditional probability) $p(y | x)$ を表します.主に,確率変数間の因果関係を表現するのに向いているそうです.
  • マルコフ確率場 (Markov Random Field; MRF):無向グラフ(辺が方向を持たないグラフ) で表現されるグラフィカルモデルです.マルコフ確率場は,ベイジアンネットワークよりも比較的緩い束縛関係の表現に便利だそうです.

今日は,マルコフ確率場の話だけして,ベイジアンネットワークの話はしません.

マルコフ確率場の例

ループがあると少し話がややこしいので,今日は次の図ような木構造を持つ無向グラフを考えてみます. 図中でどのノードが根であるかは,あまり意味がないので,明示していません(根とそれ以外のノードを区別して扱う必要がない).

![マルコフ確率場の例](/img/MRF-tree-example.png)

この図中の $x_i$ は確率変数であり(グラフィカルモデルでは,各ノードに確率変数が割り当てられます), $f_i$, $g_{ij}$ はそれぞれ,ノードと辺のエネルギーを計算する関数で, $f_i(x_i)$ は確率変数 $x_i$ (の実現値)のエネルギー,$g_{ij}(x_i, x_j)$ は $x_i$ と $x_j$ (の実現値) を組合せたときのエネルギーを計算します(起こる確率の小さい組合せほどエネルギーが大きく, 起こる確率が大きい組合せほどエネルギーが小さい).$f_i$, $g_{ij}$ を具体的にどんな関数にするかは, あまり重要ではないので,この記事では特に決めません.グラフ上の全てのノードと辺のエネルギーの合計値は

となります(この $E$ もエネルギー関数と言います). マルコフ確率場は,統計力学と関わりが深く,「エネルギー」という用語も統計力学に関連したものです. 自然界では,エネルギーが大きい状態は不安定で,放っておくと,勝手に何らかの形でエネルギーを放出して, エネルギーの低い状態になります(例えば,放熱による熱エネルギーの喪失など). なので,一般に,エネルギーの大きい状態は観測されるにくく,逆に,エネルギーの低い状態は観測される確率が高くなります. ここで,$x_1, \dots, x_4$ の観測確率(同時確率)は,次のように表され,高エネルギーが低確率, 低エネルギーが高確率に対応していることが理解できます.

この確率分布はボルツマン分布 (Boltzmann distribution) と呼ばれていて, $\exp(-E(x_1, \dots, x_4))$ はポテンシャル関数 (potential function) と呼ばれます. $Z$ は同時確率が $\sum_{x_1} \dots \sum_{x_4} p(x_1, \dots, x_4) = 1$ を満たすための規格化定数で重要な意味はありません. 式(1)を式(2)に代入して,$\exp(a+b) = \exp(a)\exp(b)$ という性質を使うと, 次の式(3)が得られます(この式は後で使うので,今のうちに導出しておきます).

\begin{align} p(x_1, x_2, x_3, x_4) & = \frac{1}{Z} \exp(- f_1(x_1) - \dots - f_4(x_4) - g_{12}(x_1,x_2) - \dots - g_{14}(x_1,x_4)) \
& = \frac{1}{Z} \exp(-f_1(x_1)) \dots \exp(-f_4(x_4)) \exp(-g_{12}(x_1,x_2)) \dots \exp(-g_{14}(x_1,x_4)) \
& = \frac{1}{Z} F_1(x_1) F_2(x_2) F_3(x_3) F_4(x_4) G_{12}(x_1,x_2) G_{13}(x_1,x_3) G_{14}(x_1,x_4) \tag{3} \end{align
}

最後の式変形では,$F_i(x_i) = \exp(-f_i(x_i))$, $G_{ij}(x_i,x_j) = \exp(-g_{ij}(x_i,x_j))$ とおきました(これらもポテンシャル関数と呼ばれます).

物理が苦手で「エネルギーとかよくわからん!」という人は, 統計力学の用語であることを意識しすぎないほうが良いかもしれません. 統計力学との関連性を無視しても,マルコフ確率場を大まかに理解することはできます. 直感的に,エネルギー関数は単純に「データの観測されにくさ」を表していて, 同時確率そのものと大差ない情報だと思って構いません. エネルギー関数は「観測されやすさ」の指標ではないので,確率とは逆の概念ですが, 両方とも「観測頻度」に関する情報なので,本質的には同種の情報です. 実際,同時確率の最大化とエネルギー関数の最小化は等価ですし, 大した違いはありません.

今回は,式(1)のようにエネルギー関数を決め打ちしましたが,解く問題によって色々な定義の仕方があります. ただし,式(2)は,どんな問題を解く場合でも共通です(ただし,ノード数は 4 以外でも良いです).

条件付き独立性

先程,辺で繋がっていない確率変数は,条件付き独立であるという話をしました. 確率変数 $z$ の下で, $x$ が $y$ に対して 条件付き独立 (conditional independence) であるとは,

が成り立つことです.この式を利用すると,

という式を導くことができます.マルコフ確率場の理解には,前者より後者の式の方が重要です. この式は,$z$ が与えられた時に,$x$ と $y$ が独立であると言っていて,ただの独立性よりも少し制限されています.

マルコフ確率場において,ノード $i,j$ が辺で繋がれていないならば, $x_i$, $x_j$ 以外の確率変数が与えられた時に,$x_i$, $x_j$ は条件付き独立になります. 試しに,先程のマルコフ確率場の例で,この性質が成り立つか確認してみます. ノード3とノード4は辺で繋がっていないので,

が成り立つはずです.式(4)の右辺は,

となり,式(4)の左辺は,

\begin{align} p(x_3 | x_1, x_2) p(x_4 | x_1, x_2) & = \frac{p(x_1, x_2, x_3)}{p(x_1, x_2)} \cdot \frac{p(x_1, x_2, x_4)}{p(x_1, x_2)} \
& = \frac{\sum_{z_4} p(x_1, x_2, x_3, z_4)}{\sum_{z_3} \sum_{z_4} p(x_1, x_2, z_3, z_4)} \cdot \frac{\sum_{z_3} p(x_1, x_2, z_3, x_4)}{\sum_{z_3} \sum_{z_4} p(x_1, x_2, z_3, z_4)} \
& = \frac{F_3(x_3) G_{13}(x_1,x_3)}{\sum_{z_3} F_3(z_3) G_{13}(x_1,z_3)} \cdot \frac{F_4(x_4) G_{14}(x_1,x_4)}{\sum_{z_4} F_4(z_4) G_{14}(x_1,z_4)} \
& = p(x_3, x_4 | x_1, x_2) \end{align
}

となり,条件付き独立であることが確認できました(他のノードについても,同様の手順で確認できます).

ここで,なぜ $p(x_3,x_4) = p(x_3, x_4)$ のような(普通の)独立性ではなく, あえて,条件付き独立性を扱うのか疑問に思う人がいるかもしれません. そもそも,普通の独立性は成立しません.なぜなら,$x_3$ と $x_4$ は直接は繋がっていないものの, $x_1$ を介して間接的に繋がっていて,互いに影響し合っているため, 完全に独立にはなりません. 式(3)の条件付き独立性では,$x_1$ と $x_2$ を固定することで, 間接的な影響を排除した上で,$x_3$ と $x_4$ の独立性を考えているので,成立します. つまり,直感的には,普通の独立性は「直接的・間接的影響を考慮した独立性」であり, 条件付き独立性は「直接的影響のみを考慮した独立性」ということになります. 普通の独立性は,2つの確率変数間を繋ぐパスが一切存在しない状況でのみ,成立します.

周辺確率の計算(積和アルゴリズム)

マルコフ確率場では,積和アルゴリズムという方法で周辺確率を効率的に求めることができます. まずは,$x_4$ の周辺確率を求めてみましょう. 周辺確率は,同時確率の和を取ればよいので,

となります.この式に式(3)を代入して,因数分解すると,

という式が得られます.ここで,ノード $j$ からノード $i$ へのメッセージ (message) $\mu_{j \to i}(x_i)$ を次のように定義します.

\begin{align} \mu_{2\to1}(x_1) & = \sum_{x_2} F_2(x_2) G_{12}(x_1,x_2) \
\mu_{3\to1}(x_1) & = \sum_{x_3} F_3(x_3) G_{13}(x_1,x_3) \
\mu_{1\to4}(x_4) & = \sum_{x_1} F_1(x_1) G_{14}(x_1,x_4) \mu_{2\to1}(x_1) \mu_{3\to1}(x_1) \end{align
}

すると,式(4)は次のように書けます.

先程定義したメッセージの式をよく見ると,子ノードから親ノードに向かってメッセージを伝搬しているように見えます. 図で書くと,次のようなイメージ.

![マルコフ確率場におけるメッセージ伝搬](/img/MRF-tree-marginal-probability.png)

基本的に,同様の方法で,他の確率変数に関する周辺確率も求めることができます. ノード $i$ に接続されているノードの集合を $V_i$ として,もう少し一般的に書くと, メッセージと周辺確率は次のようになります.

$x_i$ の周辺確率を求める場合は,ノード $i$ を根ノードだと思って, 葉から根に向かってメッセージを伝搬します. このメッセージの伝搬はメッセージパッシング (message passing) と呼ばれています. グラフの構造が木であれば,積和アルゴリズムで厳密な周辺確率を計算することができます. 木構造ではない場合は,グラフ中にループがあるので,メッセージが同じ所をぐるぐる回ってしまい, (愚直に処理すると)メッセージパッシングが終わらなくなる可能性があります(グラフによっては収束することもあります). ループがある時は,工夫が必要ですが,この記事ではそこまで説明しません.

同時確率の最大化(max-sum アルゴリズム)

同時確率の最大化は,max-sum アルゴリズム,もしくはViterbi アルゴリズムと呼ばれる方法で実現できます. まず,max-sum アルゴリズムの前に,max-product アルゴリズムを導出します. max-product アルゴリズムの導出は簡単で,同時確率を最大値を,式(4)と同じ手順で因数分解するだけです (どのノードを根ノードと見るかで,因数分解の結果が変わってきますが,計算結果はt同じ値になります).

\begin{align} \max_{x_1,\dots,x_4}[ p(x_1, \dots, x_4) ] & = \max_{x_1} \dots \max_{x_4}[ p(x_1, \dots, x_4)] \
& = \frac{1}{Z} \max_{x_4} \left[ F_4(x_4) \max_{x_1} \left[ F_1(x_1) G_{14}(x_1,x_4) \max_{x_2} \left[ F_2(x_2) G_{12} \right] \max_{x_3} \left[ F_3(x_3) G_{13} \right] \right] \right] \end{align
}

式(4)と見比べると,$\sum_{x_i}$ を $\max_{x_i}$ で置き換えただけであることが解ります. なので,基本的に,積和アルゴリズムの和を最大値演算で置き換えれば,同様のメッセージパッシング規則を適用できます.

ただし,実用上,小さい値を持つ確率値をたくさん掛け算すると,アンダーフローを起こす可能性があります. こういう時は,確率の対数値を使って計算することで,掛け算を足し算に置き換えることができます ($\ln xy = \ln x + \ln y$). 対数を取った時のメッセージパッシング規則は

ただし,$x_r$ は根ノードです.これが max-sum アルゴリズムです. 同時確率の最大値のみを計算すれば良い場合は,上のメッセージパッシング規則を愚直に実行すれば良いだけなので,とても簡単です. ただし,同時確率の最大値を与える確率変数 $x_i$ の具体値 $x_i^\mathrm{max}$ が知りたいこともよくあります. この場合,上の式の計算に現れる最大値演算について,どの具体値が最大値を与えたのか(メッセージパッシングを行いつつ)記憶しておき, $x_1,\dots,x_4$ の具体値の組合せのうち,どれが最大になったのかを最後に計算する必要があります.

max-sum アルゴリズムにより,同時確率の最大値を与える確率変数の具体値を求める方法は, ちょっとだけ複雑です(一度理解してしまえば,大したことはないのですが). ここでは,これまで扱ってきた木構造グラフではなく,次の図(a)のような, 一直線のグラフで max-sum アルゴリズムを解説します. 確率変数 $x_1, x_2, x_3$ がそれぞれ離散値 A, B を取るとすると,組合せは, AAA, AAB, ABA, ABB, BAA, BAB, BBA, BBB の8種類になります. これらの具体値の組合せを,図(a)下のようなトレリス図 (trellis diagram) で表します.

![max-sum アルゴリズム](/img/MRF-tree-viterbi.png)

まず,図(b)のように,$x_3$ から $x_2$ に向かってメッセージパッシングを行うと,

  • $x_2 = A$ のときに最大値を与えた $x_3$ の具体値(ここでは,B とします)と,
  • $x_2 = B$ のときに最大値を与えた $x_3$ の具体値(ここでは,A とします)

が求まります.この2つをトレリス図に記録してきます. 同様に,図(c)のように,$x_2$ から $x_1$ に向かってメッセージパッシングを行うと,

  • $x_1 = A$ のときに最大値を与えた $x_2$ の具体値(ここでは,B とします)と,
  • $x_1 = B$ のときに最大値を与えた $x_2$ の具体値(ここでは,B とします)

が求まります.

  • もしも,最終的に確立を最大化する具体値が $x_1 = A$ ならば,根から葉に向かって, トレリス図のパスを辿る(バックトラックする; back-track)ことで, 確率の最大値を与える具体値は $(x_1,x_2,x_3) = (A,B,A)$ とわかります.
  • 逆に,最終的に確立を最大化する具体値が $x_1 = B$ ならば,同様にバックトラックして, $(x_1,x_2,x_3) = (B,B,A)$ が得られます.

このように,それまでのメッセージパッシングでどの組合せが最大値を与えたのかを, ノードごとに記録することで,同時確率の最大値を与える具体値の組合せを知ることができます. 木構造グラフについては,途中で枝分かれが入るだけで,基本的に同じ考え方が適用できます.

参考文献