Chapter13.2.3
- 1. 第16回PRML読書会 発表資料 13.2.3 HMMの積和アルゴリズム 2010/07/17 Presented by takmin
- 2. この章で言いたいこと ? 積和アルゴリズムでもフォワード-バックワード アルゴリズムが导出できる
- 3. おさらい：積和アルゴリズム ? グラフィカルモデルにおける各ノード x n の周 辺分布 p ( xn ) を求めるアルゴリズム ? 有向/無向グラフを因子グラフに変換し，各 ノードからメッセージを計算しながら伝搬する p(z1 ) p(z 2 ) p ( z n ?1 ) p(z n ) p ( z n ?1 ) 求まる
- 4. おさらい：積和アルゴリズム ? 因子グラフ – 確率モデルを因数分解の形で表したグラフ p( x1 , x2 , x3 , x4 , x5 ) ? f1 ( x1 , x2 ) f 2 ( x2 , x3 , x4 ) f 3 ( x4 , x5 ) x5 x3 x1 変数 ノード 因子 f 3 ( x4 , x5 ) f 2 ( x2 , x3 , x4 ) f1 ( x1 , x2 ) ノード x4 x2
- 5. おさらい：積和アルゴリズム ? 因子グラフの作り方 f ( x1 , x2 , x3 ) p( x1 ) p ( x2 ) ? p( x3 | x1 , x2 ) p( x1 ) p( x2 ) p( x3 | x1 , x2 ) 有向グラフ 因子グラフ
- 6. おさらい：積和アルゴリズム ? 因子グラフの作り方 f a ( x1 ) ? p( x1 ) f b ( x2 ) ? p ( x 2 ) p( x1 ) p ( x2 ) f c ( x1 , x2 , x3 ) ? p( x3 | x1 , x2 ) p( x3 | x1 , x2 ) 有向グラフ 因子グラフ
- 7. おさらい：積和アルゴリズム ? メッセージの伝搬 – 各変数ノード，因子ノードでの計算結果を伝搬し ていき，各変数ノードにおける分布 p ( xn ) を求め る x5 x3 x1 ?x ? f 5 3 ?f ?x ? f 1 1 2 ? x3 f3 ?f f2 f1 3 ? x4 ?x ? f 2 2 ? f ?x x4 ?x ? f 4 2 x2 1 1
- 8. おさらい：積和アルゴリズム 1. 始点（葉ノード）を決めて，メッセージの伝搬 を開始する – 始点が変数ノードの場合 ? x? f ? x ? f ( x) ? 1 (8.70) x f – 始点が因子ノードの場合 ? f ?x ? f ? x ( x) ? f ( x) (8.71) f x
- 9. おさらい：積和アルゴリズム 2. 各ノードでメッセージを計算 – 変数ノードの場合 ?x m ? fs ( xm ) ? ?? l?ne( xm ) f s f l ? xm ( xm ) (8.69) f1 ? f ?x m 1 ? ? ?x m? fs fl ? ? ? xm fs fL ?
- 10. おさらい：積和アルゴリズム 2. 各ノードでメッセージを計算 – 因子ノードの場合 ? f ? x ( x) ? ??? f s ( x, x1 ,?, xM ) s ?? xm ? f s ( xm ) x1 xM m?ne( f s ) x x1 (8.66) ?x ? f s 1 ? ? f ?x ? s xm ? ? ? fs x xM ?
- 11. おさらい：積和アルゴリズム 3. メッセージが根ノードに達したら，葉ノードに 向けて逆向きにメッセージを伝搬していく (a)葉ノードから根ノードへ (b)根ノードから葉ノードへ
- 12. おさらい：積和アルゴリズム 4. 逆伝播メッセージが葉ノードまで達したら， 各変数ノードの周辺分布 p ( xn ) を以下の式で 求める p( xn ) ? ? ? f s ? xn ( xn ) (8.63) s?ne( xn ) fs ? f ?x s f1 fS x
- 13. おさらい：積和アルゴリズム 5. 各因子ノードに接続された周辺の変数群 x s の同時分布は以下の式で求める p(x s ) ? f s (x s ) ?? i?ne( f s ) xi ? f s ( xi ) (8.72) xi ?x ? f i s fS
- 14. HMMの積和アルゴリズム ? HMMを因子グラフへ変換 有向グラフ 観測値は因子ノードに 入れてしまう 因子グラフ
- 15. HMMの積和アルゴリズム ? HMMを因子グラフへ変換 HMM ?N ? N p(x1 ,?, x N , z1 ,?, z N ) ? p(z1 ) ?? p(z n | z n?1 )?? p(x n | z n ) ? n?2 ? n?1 (13.6)
- 16. HMMの積和アルゴリズム ? HMMを因子グラフへ変換 ? N ? N p(x1 ,?, x N , z1 ,?, z N ) ? p(z1 ) ?? p(z n | z n ?1 )?? p(x n | z n ) ? n?2 ? n ?1 N ? h(z1 )? f n (z n ?1 , z n ) n?2 h(z1 ) ? p(z1 ) p(x1 | z1 ) (13.45) f n (z n ?1 , z n ) ? p(z n | z n ?1 ) p (x n | z n ) (13.46)
- 17. HMMの積和アルゴリズム 1. 始点（葉ノード）を決めて，メッセージの伝搬 を開始する ? h ?z 1 h z1 ?h?z (z1 ) ? h(z1 ) 1
- 18. HMMの積和アルゴリズム 1. 始点（葉ノード）を決めて，メッセージの伝搬 を開始する – フォワード-バックワードアルゴリズムとの比較 積和アルゴリズム ?h?z (z1 ) ? h(z1 ) ? p(z1 ) p(x1 | z1 ) 1 (13.45) ? (z1 ) ? ? f n ?z n (z1 ) フォワード-バックワードアルゴリズム ? (z1 ) ? p(z1 ) p(x1 | z1 ) (13.37)
- 19. HMMの積和アルゴリズム 2. 各ノードでメッセージを計算 – 変数ノードの場合 ?z n ? f n?1 (z n ) ? ?? f l ?z n l?ne( z n ) f n?1 (z n ) (8.69) ? ? f n ?z n ( z n ) (13.47) ?f n ?z n ?z n? f n ?1 fn zn f n ?1
- 20. HMMの積和アルゴリズム 2. 各ノードでメッセージを計算 – 因子ノードの場合 ?f n ?z n (z n ) ? ? f s (z n , z m ) ?? zm ? fn (z m ) (8.66) zm m?ne( f n ) z n ? ? f n (z n ?1 , z n ) ? z n?1 ? f n (z n ?1 ) (13.48) z n?1 ?z n?1 ? f n ?f n ?z n z n ?1 fn zn
- 21. HMMの積和アルゴリズム 2. 各ノードでメッセージを計算 変数ノード： ?z n ? fn (z n?1 ) ? ? f n?1 ?z n?1 (z n?1 ) (13.47) 因子ノード： ?f n ?z n (z n ) ? ? f n (z n?1 , z n ) ? z n?1 ? f n (z n?1 ) (13.48) z n?1 ?f n ?z n (z n ) ? ? f n (z n?1 , z n ) ? f n?1 ?z n?1 (z n?1 ) (13.49) z n?1
- 22. HMMの積和アルゴリズム 2. 各ノードでメッセージを計算 – フォワード-バックワードアルゴリズムとの比較 積和アルゴリズム ?f n ?z n (z n ) ? ? f n (z n ?1 , z n ) ? f n?1 ?z n?1 (z n ?1 ) (13.49) z n?1 (13.46) ? ? p(z n | z n ?1 ) p(x n | z n ) ? f n?1 ?z n?1 (z n ?1 ) z n?1 ? (z n ) ? ? f n ?z n (z n ) フォワード-バックワードアルゴリズム ? (z n ) ? p(x n | z n )? ? (z n?1 ) p(z n | z n ?1 ) (13.36) z n?1
- 23. HMMの積和アルゴリズム 2. 各ノードでメッセージを計算 – フォワード-バックワードアルゴリズムとの比較 ? (z n ) ? ? f n ?z n (z n ) (13.50)
- 24. HMMの積和アルゴリズム 3. メッセージが根ノードに達したら，葉ノードに 向けて逆向きにメッセージを伝搬していく – 根ノードの始点が変数ノード ?z N ? fN (z N ) ? 1 (8.70) ?z N ? fN fN zN
- 25. HMMの積和アルゴリズム 3. メッセージが根ノードに達したら，葉ノードに 向けて逆向きにメッセージを伝搬していく – フォワード-バックワードアルゴリズムとの比較 積和アルゴリズム ?z N ? fN (z N ) ? 1 (8.70) ? (z N ) ? ? z N ? fN (z N ) フォワード-バックワードアルゴリズム ? (z N ) ? 1 (13.37)
- 26. HMMの積和アルゴリズム 3. メッセージが根ノードに達したら，葉ノードに 向けて逆向きにメッセージを伝搬していく ?z n ? fn (z n ) ? ? f n?1 ?z n (z n ) ? ? f n?1 (z n , z n?1 ) ? z n?1 ? f n?1 (z n?1 ) (13.51)’ z n?1 ?z n ? fn ?f n?1 ? z n ?z n?1 ? f n?1 fn zn f n ?1 z n ?1
- 27. HMMの積和アルゴリズム 3. メッセージが根ノードに達したら，葉ノードに 向けて逆向きにメッセージを伝搬していく – フォワード-バックワードアルゴリズムとの比較 積和アルゴリズム ?z n ? fn (z n ) ? ? f n ?1 (z n , z n ?1 ) ? z n?1 ? f n?1 (z n ?1 ) (13.51)’ z n?1 (13.46) ? ? p(z n ?1 | z n ) p(x n ?1 | z n ?1 ) ? z n?1 ? f n?1 (z n ?1 ) z n?1 ? (z n ) ? ? z n ? fn (z n ) フォワード-バックワードアルゴリズム ? (z n ) ? ? ? (z n?1 ) p(x n?1 | z n?1 ) p(z n?1 | z n ) (13.38) z n?1
- 28. HMMの積和アルゴリズム 3. メッセージが根ノードに達したら，葉ノードに 向けて逆向きにメッセージを伝搬していく – フォワード-バックワードアルゴリズムとの比較 ? (z n ) ? ? z n ? fn (z n ) (13.52)’
- 29. HMMの積和アルゴリズム 4. 逆伝播メッセージが葉ノードまで達したら， 各変数ノードの周辺分布 p ( z n ) を以下の式で 求める p ( z n ) ? ? ? f s ?z n ( z n ) (8.63)’ s?ne( z n ) ? ? f n ?z n (z n ) ? f n?1 ?z n (z n ) ?f n ?z n ?f n?1 ? z n fn zn f n ?1
- 30. HMMの積和アルゴリズム 周辺分布 p ( z n ) は既に観測変数 X ? ?x1 , ? , x N ? により条件付けられているので， p(z n , X) ? ? f n ?z n (z n )?z n ? f n (z n ) ? ? (z n )? (z n ) (13.53) p(z n , X) ? (z n )? (z n ) ? (z n ) ? ? (13.54) p(X) p( X) (13.33)と同じγ (zn)が導けた！
- 31. HMMの積和アルゴリズム 5. 各因子ノードに接続された周辺の変数群 x s の同時分布は以下の式で求める p(x s ) ? f s (x s ) ?? i?ne( f s ) xi ? f s ( xi ) (8.72) p(z n?1 , z n ) ? f n (z n?1 , z n )?z n ? f n (z n )?z n?1 ? f n (z n?1 ) ?z n?1 ? f n ?z n ? fn z n ?1 fn zn
- 32. HMMの積和アルゴリズム 演習13.11 ξ (zn-1, zn)を導く p(z n?1 , z n , X) ? f n (z n?1 , z n ) ?z n ? f n (z n ) ?z n?1 ? f n (z n?1 ) ? p(z n | z n?1 ) p(x n | z n ) ? (z n )? (z n?1 ) p(z n ?1 , z n , X) ? (z n ?1 , z n ) ? p(z n ?1 , z n | X) ? p ( X) ? (z n ?1 ) p(x n | z n ) p(z n | z n ?1 ) ? (z n ) ? p ( X) (13.43)と同じξ (zn-1, zn)が導けた！
- 33. まとめ ? 積和アルゴリズムでもフォワード-バックワード アルゴリズムと同じことができた。
- 34. ご静聴ありがとうございました。