東北大学 大学院情報科学研究科 応用情報科学専攻 田中 和之(Kazuyuki Tanaka)

Presentation on theme: "東北大学 大学院情報科学研究科 応用情報科学専攻 田中 和之(Kazuyuki Tanaka)"— Presentation transcript:

1 東北大学 大学院情報科学研究科 応用情報科学専攻 田中 和之(Kazuyuki Tanaka)
物理フラクチュオマティクス論 Physical Fluctuomatics 応用確率過程論 Applied Stochastic Process 第11回 確率推論におけるベイジアンネットと確率伝搬法 11th Bayesian network and belief propagation in statistical inference 東北大学 大学院情報科学研究科 応用情報科学専攻 田中 和之(Kazuyuki Tanaka) 物理フラクチュオマティクス論(東北大)

2 今回の本講義の講義ノート 田中和之著: ベイジアンネットワークの統計的推論の数理, コロナ社, 2009.
田中和之編著: 数理科学臨時別冊 SCG ライブラリ「確率的情報処理と統計力学　---様々なアプローチとそのチュートリアル---」，pp ，サイエンス社，2006． 物理フラクチュオマティクス論(東北大)

3 不確実性を伴うデータに耐えうる推論システム
ベイジアンネットと確率推論 ベイズの公式 確率モデル グラフィカルモデル 確率推論 医療診断 故障診断 ベイジアンネット 不確実性を伴うデータに耐えうる推論システム たくさんのノードが関連しあって集まっている． 計算困難を打破する高性能の近似アルゴリズムの必要性 物理フラクチュオマティクス論(東北大)

4 確率の知識（１） 事象Ａの起こる確率 事象Aと事象Bの結合確率 条件付き確率と結合確率 A B 物理フラクチュオマティクス論(東北大)

5 確率の知識（２） 事象 B の周辺確率 A B C D 周辺化 物理フラクチュオマティクス論(東北大)

6 確率推論に使う数学 A B C 因果独立の仮定 物理フラクチュオマティクス論(東北大)

7 簡単なベイジアンネットの例 問題 芝生がぬれているのは何故でしょうか？雨が降ったせいでしょうか？
それともスプリンクラーを動かしたせいでしょうか？ 物理フラクチュオマティクス論(東北大)

8 簡単なベイジアンネットの例 物理フラクチュオマティクス論(東北大)

9 簡単なベイジアンネットの例 物理フラクチュオマティクス論(東北大)

10 簡単なベイジアンネットの例 物理フラクチュオマティクス論(東北大)

11 簡単なベイジアンネットの例 回答：芝生がぬれているのは雨が降ったせいだと考えられます． 物理フラクチュオマティクス論(東北大)

12 ベイジアンネットと物理モデル（Ⅰ） ベイジアンネットで扱われるグラフィカルモデルは多体力を持つ磁性体の物理モデルに対応づけられる．
一言でいえば公式 z=exp(ln z) を使うということ． 具体的には を満たすように係数を決めると確かめられる． ベイジアンネットで扱われるグラフィカルモデルは多体力を持つ磁性体の物理モデルに対応づけられる． 物理フラクチュオマティクス論(東北大)

13 ベイジアンネットと物理モデル（Ⅱ） ベイジアンネットで扱われるグラフィカルモデルは多体力を持つ磁性体の物理モデルに対応づけられる．
物理フラクチュオマティクス論(東北大)

14 ベイジアンネットと物理モデル（Ⅲ） ベイジアンネットで扱われるグラフィカルモデルは多体力を持つ磁性体の物理モデルに対応づけられる．
物理フラクチュオマティクス論(東北大)

15 ベイジアンネットと物理モデル（Ⅳ） ベイジアンネットで扱われるグラフィカルモデルは多体力を持つ磁性体の物理モデルに対応づけられる．
物理フラクチュオマティクス論(東北大)

16 ノード数とともに指数関数的に計算量が増加
より複雑なベイジアンネット L 重の for 文 定義に基づいて厳密に計算するプログラム ノード数とともに指数関数的に計算量が増加 このプログラムでは L=10個のノードで1秒かかるとしたら L=20個で約17分，L=30個で約12日，L=40個で約34年かかる． 物理フラクチュオマティクス論(東北大)

17 確率伝搬法 閉路を持たないグラフ上の確率モデルに対して厳密な結果を与える． 閉路を持つグラフ上の確率モデルでは近似アルゴリズムとなる．
８個程度のノードの簡単ではあるが閉路を含むグラフ上の確率モデルで確率伝搬法の構造を説明し，得られる近似結果と厳密な結果を比較してみる． 物理フラクチュオマティクス論(東北大)

18 閉路を持つグラフ上の確率モデルの結合確率
無向グラフ 有向 グラフ 物理フラクチュオマティクス論(東北大)

19 周辺確率分布 物理フラクチュオマティクス論(東北大)

20 この場合の確率伝搬法の基本方針 物理フラクチュオマティクス論(東北大)

21 確率伝搬法の固定点方程式 確率伝搬アルゴリズム 物理フラクチュオマティクス論(東北大)

22 Message を用いた周辺確率分布の近似表式
物理フラクチュオマティクス論(東北大)

23 Message Passing Algorithm
物理フラクチュオマティクス論(東北大)

24 繰り返し出力を入力に入れることにより，固定点方程式の解が数値的に得られる． 反復法
固定点方程式と反復法 固定点方程式 繰り返し出力を入力に入れることにより，固定点方程式の解が数値的に得られる． 反復法 物理フラクチュオマティクス論(東北大)

25 数値実験 Belief Propagation Exact 物理フラクチュオマティクス論(東北大)

26 数値実験 確率伝搬法 物理フラクチュオマティクス論(東北大)

27 線形応答理論 （人為的に小さなゆらぎを与えてその応答を見ることで詳細を知ることができる．） 物理フラクチュオマティクス論(東北大)

28 数値実験 物理フラクチュオマティクス論(東北大)

29 ベイジアンネットと確率伝搬法を用いた確率推論の概説 線形応答定理を用いた高次の推論システムへの発展
確率推論のまとめ ベイジアンネットと確率伝搬法を用いた確率推論の概説 線形応答定理を用いた高次の推論システムへの発展 ベイジアンネットの最近の動向 繁桝算男, 本村陽一, 植野真臣： ベイジアンネットワーク概説，培風館，2006． 本村陽一, 岩崎弘利：ベイジアンネットワーク技術．東京電機大出版，2006． 田中和之著: ベイジアンネットワークの統計的推論の数理, コロナ社, 2009. Microsoft社，Intel社，Nokia社などが実用化への研究 物理フラクチュオマティクス論(東北大)

30 演習問題11－1 以下の図と式の結合確率 Pr{X1,X2,…,X8} により与えられるベイジアンネットワークにおける各ノードごとに周辺確率 P(Xi) (i=1,2,…,8) の厳密な値を C 言語，Java または MatLab を用いて求めよ． 各条件付き確率表は 田中和之著: ベイジアンネットワークの統計的推論の数理, コロナ社, 2009 のp.50の図3.12と表3.11の値を用いよ． April, 2010 電気・通信・電子・情報工学実験D

31 演習問題11－2 以下の図と式の結合確率 Pr{X1,X2,…,X8} により与えられるベイジアンネットワークにおける各ノードごとに周辺確率 P(Xi) (i=1,2,…,8) の値を確率伝搬法により計算するプログラムを C 言語，Java または MatLab を用いて求めよ． 各条件付き確率表は「田中和之: ベイジアンネットワークの統計的推論の数理, コロナ社, 2009」のp.50の図3.12と表3.11の値を用いよ． ヒント：具体的なアルゴリズムは「田中和之: ベイジアンネットワークの統計的推論の数理, コロナ社, 2009」の7.2節参照． April, 2010 電気・通信・電子・情報工学実験D