PRML 読書会 #11 資料(max-sum アルゴリズム)

機械学習 読書会 PRML
「パターン認識と機械学習」(PRML)読書会 #11 で担当する 8.4.5「max-sum アルゴリズム」の資料です。

8.4.5 max-sum アルゴリズム

  • 8.3 まで
    • モデルを表現するツールとしてグラフィカルモデルを使う
  • 8.4 以降、周辺化や同時分布の大域最大解を求めるツールとしてのグラフィカルモデル
    • 8.4.4 積和(sum-product) : 周辺分布を求める
    • 8.4.5 max-sum : 同時分布の大域最大確率と、それを与える変数の値を求める

max-sum algorithm

同時分布の最大解を求めるツール

  • sum-product algorithm において
  • 因子(local function) の対数を取り
  • sum を max におきかえ
    • 単調増加なlogと交換可能 \ln(\max_x p(x))=\max_x(\ln p(x))
    • 非負な係数に対して分配則が成立 {}^\forall a\geq 0, \max(ab,ac)=a\max(b,c)
  • product を sum におきかえ

★注意★

  • sum-product で求められる周辺分布それぞれを最大にする変数が同時分布を最大化するとは限らない
  • 「負の対数」を取って min-sum と呼ばれていることもある*1

max-sum algorithm の手順

  • tree graph 上のメッセージパッシング
  • sum-product と異なり、「片道」
    • 最大値を与える変数が必ずしも一意でないため、逆向きのメッセージパッシングで得られる変数集合が求めるものでない場合がある
  • 「帰り」はトレリス図などを用いる

Step 1: 最初のメッセージ

  • 葉ノードが変数ノードの場合
    • \mu_{x\rightarrow f}(x)=0
  • 葉ノードが因子ノードの場合
    • \mu_{f\rightarrow x}(x)=\ln f(x)

Step 2: メッセージパッシング

  • 因子ノードから変数ノードへ
  • \mu_{\!f\rightarrow x}(x)=\max_{x_1,...,x_M}{\left[\ln f_1(x,x_1,...,x_M)+ \sum_{m \in {\rm ne}(f_s) \setminus x} ^ {\rule{0}{13}} { \mu_{x_m\rightarrow f}(x_m) }\right]}
    • μ : メッセージ(x の関数)
    • {x_1, ... , x_M} : {因子 f にリンクする変数}＼x
    • ne(f) : 因子 f にリンクする変数の添え字の集合
  • 変数ノードから因子ノードへ
  • \mu _{x\rightarrow f}(x) = \sum_{l \in {\rm ne}(x) \setminus f}{ \mu _{f_l \rightarrow x}(x)}
    • ne(x) : 変数 x にリンクする因子の添え字の集合

Step 3: 大域最大確率

  • メッセージパッシングの終点に変数ノード x を選び、x で以下を計算する
    • 終点＝xにリンクする全ての因子ノードからのメッセージを受け取る

\ln p^{\max} = \max_{x \rule{0}{16}}{\left[ \sum_{s \in {\rm ne}(x)} ^ {\rule{0}{13}}{ \mu _{f_s \rightarrow x}(x)}\right] }

  • ★PRML(8.97) には 'ln' がないけど、必要なはず

Step 4: バックトラック

  • 最大確率を与える変数の値を求める
    • 最大値を与える変数が必ずしも一意でないため、sum-product と同様に逆向きのメッセージパッシングを行うと、得られる変数集合が求めるものでない場合がある
  • Step 2 において、因子から変数への各メッセージにおいて、各 x に対して最大値を与えた変数の値を記録しておく
    • 複数ある場合はランダムに(どれでもいい！)

\phi(x_n) = \arg\max_{x_{n-1}} {\left[ \ln f_{n-1,n}(x_{n-1}, x_n) + \mu_{x_{n-1} \rightarrow f_{n-1,n}}(x_n)\rule{0}{13} \right] }

  • p^max を得た後、(トレリス図を使うなどして)リンクを逆向きにたどって、変数の値を順に拾っていく


cyclic graph の場合は？

  • acyclic(tree graph) なら、有限回の操作でアルゴリズムが終了(Ex.8.29 有限回の操作で「保留メッセージ」*2が存在しなくなる)
    • →大域最大解
    • →HMMでは Vitervi algorithm として知られる(PRML 13.2)
  • cyclic なら、操作が終了しない(Ex.8.28 少なくとも１つの保留メッセージが常に存在)
    • →ほとんどのアプリケーションにおいて妥当な時間内に近似局所解へ収束(8.4.7)

例:お昼ご飯の同時分布*3

	○→○→○
	x1　x2　x3

A さんのお昼ご飯はお弁当(x1=0) または 外食(x1=1)。

	P(x_1=0) = 0.3

B さんのお昼ご飯はお弁当(x2=0) または 外食(x2=1)。
いつも A さんが食べるものにあわせて決めている。

	P(x2=0|x1=0) = 0.7
	P(x2=0|x1=1) = 0.4

C さんのお昼ご飯はお弁当(x3=0) または 外食(x3=1)。
いつも B さんが食べるものにあわせて決めている。

	P(x3=0|x2=0) = 0.0
	P(x3=0|x2=1) = 0.6


(解) 同時分布と周辺分布を求めると次の通り。


  • 周辺分布が最大になるのはそれぞれ x_1=1, x_2=1, x_3=1
  • 同時分布が最大になるのは x_1=1, x_2=0, x_3=1

Step 1 最初のメッセージ

因子グラフに変換。

	○→■−○−■−○
	x1　f1　x2　f2　x3

\mu _{x_1\rightarrow f_1}(x_1)=0

Step 2

	○−■→○→■−○
	x1　f1　x2　f2　x3

\begin{eqnarray} \mu_{f_1\rightarrow x_2}(x_2) &=& \max_{x_1}\left( \ln f_1(x_1, x_2)+\mu _{x_1\rightarrow f_1}(x_1) \right) \\ &=& \begin{eqnarray}\left\{\begin{array}{l}\ln 0.28 & (x_2=0, {\rm then } x_1=1)\\ \ln 0.42 & (x_2=1, {\rm then } x_1=1)\end{array}\right.\end{eqnarray}&(1)\end{eqnarray}
\mu_{x_2\rightarrow f_2}(x_2)=\mu _{f_1\rightarrow x_2}(x_2)

	○−■−○−■→○
	x1　f1　x2　f2　x3

\begin{eqnarray} \mu_{f_2\rightarrow x_3}(x_3) &=& \max_{x_2}\left( \ln f_2(x_2, x_3)+\mu _{x_2\rightarrow f_2}(x_2) \right)\\ &=& \begin{eqnarray}\left\{\begin{array}{l}\ln 0.252 & (x_3=0, {\rm then } x_2=1) \\ \ln 0.28 & (x_3=1, {\rm then } x_2=0)\end{array}\right.\end{eqnarray}&(2)\end{eqnarray}

Step 3

\ln p^{\max}=\max_{x_3}\mu_{f_2\rightarrow x_3}(x_3) = \ln 0.28 \; (x_3=1) (3)

Step 4

  • 式3 より x_3 = 1
  • 式2 より、x_3 = 1 を与える x_2 = 0
  • 式1 より x_2 = 0 を与える x_1 = 1
    • したがって同時分布の最大確率は 0.28(x_1=1, x_2=0, x_3=1)

トレリス図は板書

8.4.6 ジャンクションツリー

パス。

8.4.7 ループあり確率伝播

Kschischnang et al., 2001 "Factor graphs and the sum-product algorithm"

  • http://www.psi.toronto.edu/pubs/2001/frey2001factor.pdf
  • factor graph & sum-product と、そのアプリケーションを紹介する tutorial paper
    • forward/backward algorithm
    • Viterbi algorithm
    • decoding algorithms of turbo/LDPC/RA codes
    • ループがある場合の近似解の求め方(flood/serial schedule)
    • graph の変形(ループのつぶし方)
    • belief propagation
    • Kalman filter
    • DFT/FFT
  • 感想：ループあり factor graph は必要なのね。

ループあり確率伝播が、ある種の誤り訂正符号(Turbo code, LDPC)の復号アルゴリズムと等価

読んでない。

8.4.8 グラフ構造の学習

読んでない。

疑問

  • 「メッセージパッシング」と sum-product/max-sum と belief propagation と「フォワード／バックワード」の関係は？　どれかはどれかの special case？　or 一部？
  • メッセージパッシングは並列処理に向いてる？　通信量がボトルネックだったりする？

*1:むしろ min-sum と読んでいることの方が多い？

*2:ノードがメッセージを受け取っているが、そのメッセージを他のノードに送っていない

*3:この設定はフィクションであり、実在の団体・個人とは関係有りません。