認知システム論 知識と推論(3) 不確実な知識の表現と確率推論 事後確率と信念改訂 同時分布からの事後確率計算 ベイズの規則

Slides:



Advertisements
Similar presentations
PRML読書会第11回 8.4 グラフィカルモデルによる推論 SUHARA YOSHIHIKO (id:sleepy_yoshi)
Advertisements

1 小暮研究会2 第1章ベイジアンアルゴリズ ム 2値選択 ベルヌーイ試行 尤度原理 同一性 交換可能性 尤度についてのまとめ 環境情報学部3年 渡邊洋一.
1 線形代数学. 2 履修にあたって 電子情報システム学科 必修 2005 年度1セメスタ開講 担当 草苅良至 (電子情報システム学科) 教官室: G I 511 内線: 2095 質問等は上記のいずれかに行なうこと。 注意計算用のノートを準備すること。
2016 年度 計量経済学 講義内容 担当者: 河田 正樹
潜在クラス分析入門 山口和範. 内容 条件付独立 シンプソンのパラドックス 対数線形モデルにおける表現 局所独立 潜在変数モデル Lem 入門.
統計学入門2 関係を探る方法 講義のまとめ. 今日の話 変数間の関係を探る クロス集計表の検定:独立性の検定 散布図、相関係数 講義のまとめ と キーワード 「統計学入門」後の関連講義・実習 社会調査士.
0章 数学基礎.
プログラミング言語論 第10回(演習) 情報工学科 木村昌臣   篠埜 功.
第1回 確率変数、確率分布 確率・統計Ⅰ ここです! 確率変数と確率分布 確率変数の同時分布、独立性 確率変数の平均 確率変数の分散
セキュアネットワーク符号化構成法に関する研究
確率と統計 平成23年12月8日 (徐々に統計へ戻ります).
確率・統計Ⅰ 第12回 統計学の基礎1 ここです! 確率論とは 確率変数、確率分布 確率変数の独立性 / 確率変数の平均
全加算回路 A, Bはそれぞれ0または1をとるとする。 下位桁からの繰り上がりをC1とする。(0または1)
確率・統計Ⅰ 第11回 i.i.d.の和と大数の法則 ここです! 確率論とは 確率変数、確率分布 確率変数の独立性 / 確率変数の平均
Pattern Recognition and Machine Learning 1.5 決定理論
Microsoft Excel 2010 を利用した 2項分布の確率計算
5.チューリングマシンと計算.
5.チューリングマシンと計算.
白井ゼミ 豊田秀樹(2008)『データマイニング入門』 (東京図書)第7章
論理式の表現を数学的に取り扱いやすくするために代数学の助けを借りる.
人工知能特論2011 資料No.6 東京工科大学大学院 担当教員 亀田弘之.
データ構造と アルゴリズム 第二回 知能情報学部 新田直也.
第2章補足Ⅱ 2項分布と正規分布についての補足
人工知能概論 第6章 確率とベイズ理論の基礎.
「データ学習アルゴリズム」 第2章 学習と統計的推測 報告者 佐々木 稔 2003年5月21日 2.1 データと学習
統計数理 石川顕一 10/17 組み合わせと確率 10/24 確率変数と確率分布 10/31 代表的な確率分布
正規性の検定 ● χ2分布を用いる適合度検定 ●コルモゴロフ‐スミノルフ検定
最尤推定によるロジスティック回帰 対数尤度関数の最大化.
(ラプラス変換の復習) 教科書には相当する章はない
【小暮研究会2】 「ベイズのアルゴリズム」:序章 【1,2:計量経済分析と統計分析】 【 3:ベイズ定理】
ガウス過程による回帰 Gaussian Process Regression GPR
第6章 連立方程式モデル ー 計量経済学 ー.
独立成分分析 1.問題は何か:例:解法:全体の見通し 2007/10/17 名雪 勲.
確率・統計Ⅰ 第3回 確率変数の独立性 / 確率変数の平均 ここです! 確率論とは 確率変数、確率分布 確率変数の独立性 / 確率変数の平均
混合ガウスモデルによる回帰分析および 逆解析 Gaussian Mixture Regression GMR
モデルの逆解析 明治大学 理工学部 応用化学科 データ化学工学研究室 金子 弘昌.
確率伝搬法と量子系の平均場理論 田中和之 東北大学大学院情報科学研究科
独立成分分析 5 アルゴリズムの安定性と効率 2007/10/24   名雪 勲.
Basic Tools B4  八田 直樹.
6. ラプラス変換.
第2日目第1時限の学習目標 順列、組み合わせ、確率の入門的知識を学ぶ。 (1)順列とは? (2)組み合わせとは? (3)確率とは?
第3回 アルゴリズムと計算量 2019/2/24.
東北大学 大学院情報科学研究科 応用情報科学専攻 田中 和之(Kazuyuki Tanaka)
予測に用いる数学 2004/05/07 ide.
量子系における 確率推論の平均場理論 田中和之 東北大学大学院情報科学研究科
25. Randomized Algorithms
統計解析 第1回 条件付き独立性と確率的グラフィカルモデル 本講義の全体像
様々な情報源(4章).
母分散の信頼区間 F分布 母分散の比の信頼区間
東北大学 大学院情報科学研究科 応用情報科学専攻 田中 和之(Kazuyuki Tanaka)
ベイジアンネットワーク概説 Loopy Belief Propagation 茨城大学工学部 佐々木稔
4. システムの安定性.
第3章 線形回帰モデル 修士1年 山田 孝太郎.
経営学研究科 M1年 学籍番号 speedster
最尤推定・最尤法 明治大学 理工学部 応用化学科 データ化学工学研究室 金子 弘昌.
5.チューリングマシンと計算.
ポッツスピン型隠れ変数による画像領域分割
ガウス分布における ベーテ近似の理論解析 東京工業大学総合理工学研究科 知能システム科学専攻 渡辺研究室    西山 悠, 渡辺澄夫.
物理フラクチュオマティクス論 応用確率過程論 (2006年4月11日)
東北大学 大学院情報科学研究科 応用情報科学専攻 田中 和之(Kazuyuki Tanaka)
統計力学と情報処理 ---自由エネルギーの生み出す新しい情報処理技術--- 2003年8月14日前半
4.プッシュダウンオートマトンと 文脈自由文法の等価性
ベイジアンネットワーク概説 第3章 ベイジアンネットワークモデルの 数学的基礎 3.1 ベイジアンネットワークモデルの概要
確率と統計 確率編- 平成20年10月29日(木).
確率と統計 確率編- 平成19年10月25日(木) 確率と統計2007.
コストのついたグラフの探索 分枝限定法 A*アルゴリズム.
香川大学工学部 富永浩之 情報数学1 第5-2章 命題論理式の 同値変形とカルノー表 香川大学工学部 富永浩之
Microsoft Excel 2010 を利用した 2項分布の確率計算
オブジェクト指向言語論 第六回 知能情報学部 新田直也.
確率統計学 (データ解析学) 書き込み式ノート(Ver.1) 担当教員:綴木 馴.
Presentation transcript:

認知システム論 知識と推論(3) 不確実な知識の表現と確率推論 事後確率と信念改訂 同時分布からの事後確率計算 ベイズの規則 認知システム論 知識と推論(3)   知識を表現し,それを用いて推論する 不確実な知識の表現と確率推論  事後確率と信念改訂  同時分布からの事後確率計算  ベイズの規則  ベイジアンネット

Posterior probability 1.事後確率と信念改訂(1/4) 事 前 確 率 Prior probability P(A) = 何の情報もない場合に,       エージェントが「Aである」と信じる信念の強さ 証 拠 Evidence 信 念 の改 訂 Belief revision B である事実を知る 事 後 確 率 Posterior probability AとBの時間的な前後関係はどうでもよい  不確実な情報を確率を用いてモデル化し,エージェントの意思決定に結びつけるための基礎技術を学ぼう.  純粋数学においては,「確率」はある種の公理を満たす数値として抽象的に定義されているだけで,応用する上での解釈は示されていない.よくある解釈は,サイコロの1の目が出る確率が1/6であるというのは,「6回のうち1回はその目が出ること」というように,試行を何度も繰り返して得られる統計的な解釈と結びつけている.しかし,「明日,雨が降る確率は20%」という場合,明日という日は歴史上でただ1日しかなく,試行を繰り返せるものではないし,全く同じ気象条件の日がこれまで何度もあったという解釈もやや苦しい.  人工知能で確率を応用する場面では,確率P(A)は,何の情報もない場合に,事前にエージェントが「Aである」ことを信じている信念の強さを表していると解釈する.いま,エージェントが「Bである」ことを知ったとしよう.すると,その知識を知った事後においては,エージェントがもつ「Aである」と信じる信念の強さが変わってくるかもしれない.これを信念の改訂という.その新しい信念の強さを,条件付き確率P(A|B)によってモデル化する.すなわち,   P(A|B) = 知っていることがBのみであるときに,エージェントが「Aである」と信じる信念の強さ  P(A)を事前確率,Bを証拠,条件付き確率P(A|B)のことを事後確率と呼ぶ.事前確率と証拠から事後確率の計算を行うような情報処理は,一般に,確率推論と呼ばれている. 条件付き確率 P(A|B) = 知っていることがBのみであるときに,       エージェントが「Aである」と信じる信念の強さ

1.事後確率と信念改訂(2/4) 例 A=「2個のさいころの目がどちらも6」 P(A) = 1/36 一方の目は6  1つ前のスライドの事後確率P(A|B)の解釈においては,AとBが生起する時刻の前後関係については何も言っていないことに注意しよう.良くある状況設定は,Bは目前に生起している事象であり,Aは将来に生起する事象である.つまり,P(A|B)は,Bであるときに,将来Aとなる確率である。Aは将来の事象なので,Bという知識を利用して,確率的に予測するしかないわけである.たとえば,袋の中に赤玉と白玉を3個ずつ入れておき,最初に取り出したのが赤玉である(=事象B)ときに,2回目に取り出すのもまた赤玉である(事象A)確率は,P(A|B)=2/5となる。  反対に,Aが過去に生起したかもしれない事象で,Bが現時点で知り得た事象であるような応用も多い.つまり,現在の知識から過去を推定するわけである.このとき,P(A|B)は,Bであるときに,過去にAであった確率である。たとえば,犯行現場に残されたBという証拠を知ったうえで,犯行を犯した者がAであることの信念の強さをこれでモデル化できる.Bという証拠が発見されたとき,この条件付き確率の計算に基づいて,エージェント(探偵かもしれない)はAが犯人であるかどうかについての信念を改訂することができる.  これから学ぶ理論はどちらのタイプの応用にも使うことができるが,例題では後者のような応用を設定している.  最初の簡単な例として,「2個のさいころの目がどちらも6である」という事象をAとしよう.  何も情報がないとき,Aの事前確率はP(A)=1/36である.  ここで,一方の目が6であることをエージェントが知ったとする.このとき,Aの事後確率は,     P(A | 一方の目は6) = 1/6 となり,信念が改訂される. P(A | 一方の目は6) = 1/6

a,b,c,d,e∈{0,1} g1,g2,g3 ∈{normal,abnormal} 1.事後確率と信念改訂(3/4) 故障診断の例 a,b,c,d,e∈{0,1} g1,g2,g3 ∈{normal,abnormal} 事後確率 a=1,b=1のとき,e=1 だった.  ゲートg2が故障である確率 P(g2=abnormal | a=1,b=1,e=1)は? Q 証拠変数 質問変数 a b g1 c g2 d g3 e P(a) P(b) P(g1) P(c|a,b,g1) P(g2) P(g3) P(d|a,c,g2) P(e|d,g3) 条件付き確率 ベイジアンネット 事前確率  システムの確率モデルの例として,簡単な論理回路の故障診断を考えてみる.  スライドの回路で,a,b,c,d,eは信号の値を表す確率変数で,0または1の値をとる.g1,g2,g3は,各ゲートが正常か異常かを表す確率変数である.  これらの確率変数をノード(節点)とし,それらの間の因果関係(causal relationship)をアーク(有向辺)で表したグラフを描くと図のようになる.たとえば,eはdとg3の値に依存して決まるので,dとg3からeにアークが付けられている.  さらに,この構造に確率的な情報を付与する.具体的には,いま見たような直接的な依存関係ごとに条件付き確率分布を与える.たとえば,いま見たeとd,g3の依存関係は,条件確率分布P(e | d,g3)で表現する.すなわち,d=0,1とg3=normal.abnormalの4通りの組合せごとにe=0,1である確率をそれぞれ与えるわけである.  さらに,入ってくるアークが1本もないノードについては,事前確率を与えることとする.  このように,グラフと条件付き確率分布によって構築された確率モデルがベイジアンネット(Baysian network)と呼ばれるものである.その正式な定義は後に学ぶ.  ベイジアンネットが与えられているとき,新たにわかった証拠から事後確率を計算するアルゴリズムが知られている.それを用いると,たとえば,スライドに書かれたような質問に対する解を効率良く求めることができる.証拠を表す確率変数を証拠変数(evidence variable),事後確率を知りたい確率変数を質問変数(question variable)という.

1.事後確率と信念改訂(4/4) 医療診断の例題 1.事後確率と信念改訂(4/4) 医療診断の例題 カゼ ノド 60% カゼ(A=1) B=1 カゼでない(A=0) 20% Q カゼのときには,60%の確率でノドがいたい. カゼでないときには,20%の確率でノドがいたい.    10人に1人はカゼをひいている. ノドがいたいとき,カゼである確率はどの程度か.  医療診断の例を紹介する.  カゼのときには,60%の確率でノドがいたい. カゼでないときには,20%の確率でノドがいたい.10人に1人はカゼをひいている.では,ノドがいたいとき,カゼである確率はどの程度か.  求め方として,同時分布(simultaneous distribution)から計算する方法とベイズの規則(Bayes’ rule)を使う方法がある.次のスライド以降でその両方を見ていくことにする. A 同時分布から計算する方法と ベイズの規則を使う方法がある. いずれも,カゼである確率は,P(A=1|B=1)=25%

2.同時分布からの事後確率の計算(1/7) 同時分布 2.同時分布からの事後確率の計算(1/7)   同時分布 確率変数 (random variable) 授業では「命題」を表わすのに限定. 値は 0 または 1 確率分布 (probability distribution) Xについての関数.表で与えられる. 結合確率 (joint probability) 同時確率 (simultaneous probability)  このスライドは確率論の基本事項をまとめたものである.特に重要なのは,同時分布である.これは,いま考察の対象としている確率モデルに現れているすべての変数の取りうる値のすべての組合せごとに確率を関数または表で与えるものである. 同時分布  (simultaneous probability distribution) すべての変数の取り得る値の すべての組合せに対する確率の表

2.同時分布からの事後確率の計算(2/7) 周辺分布 2.同時分布からの事後確率の計算(2/7)   周辺分布 周辺分布 (marginal distribution) 同時分布 P(X,Y) Y=0 Y=1 X=0 0.1 0.2 X=1 0.3 0.4 P(X) 0.3 0.7  周辺分布 P(X) は,パラメータで指定された変数 X だけを残し,それ以外の変数 Y の取りうる値の組合せのすべてについての同時確率の和である.スライドのような2次元の表の場合には,行方向の和,あるいは列方向の和がそれに当たる.通常,それらの和はこのスライドのように表の右端や下端などの「周辺」に表示されるので,周辺分布と呼ばれている.   XやYが複数個あるような多次元の場合も,これを自然に拡張して考える. P(Y) 0.4 0.6

2.同時分布からの事後確率の計算(3/7) 条件付き確率 2.同時分布からの事後確率の計算(3/7)   条件付き確率 条件付き確率 (conditional probability) 条件付き確率分布 同時分布 P(X,Y) Y=0 Y=1 X=0 0.1 0.2 X=1 0.3 0.4 P(Y) 0.6  このスライドは,条件付き確率を説明している.  単に公式で覚えるのではなく,同時分布の表と関連付けて理解してほしい.たとえば,P(X=0|Y=1)の場合,条件部がY=1となっているので,同時分布表のY=1の全エントリだけを考察の対象とし,調べたい事象(X=0)の確率 P(X=0,Y=1)と条件を満たす全事象の確率P(Y=1)との比を求めるのである. 周辺分布

2.同時分布からの事後確率の計算(4/7) 連鎖公式 2.同時分布からの事後確率の計算(4/7)   連鎖公式 条件付き確率 連鎖公式 (chain rule)  条件付き確率の式から,連鎖公式と呼ばれる公式が得られる.むしろ,こちらの方が見慣れているかもしれない.XとYが共に起こる確率P(X,Y)は,Yが起こる確率P(Y)と,Yが起こったという条件のもとでXが起こる確率P(X|Y)の積である。  この公式は,変数が3個以上の場合にも自然に拡張できる.たとえば,変数が3個の場合,XとYとZが共に起こる確率P(X,Y,Z)は,Zが起こる確率P(Z)と,Zが起こったという条件のもとでYが起こる確率P(Y|Z)と,YとZが起こったという条件のもとでXが起こる確率P(X|Y,Z)の積である。

2.同時分布からの事後確率の計算(5/7) 例題の解(1) 2.同時分布からの事後確率の計算(5/7)   例題の解(1) カゼ ノド 60% カゼ(A=1) B=1 カゼでない(A=0) 20% A 連鎖公式を使って,同時分布を計算する.  では,さきほどの例題に戻って,答えを計算してみよう.  ここでは同時分布を用いて,すなおに事後確率(=条件付き確率)を求める方法を使う.  まず,連鎖公式を使って,同時分布の4つのエントリを計算する.

2.同時分布からの事後確率の計算(6/7) 例題の解(2) 2.同時分布からの事後確率の計算(6/7)   例題の解(2) カゼ ノド 60% カゼ(A=1) B=1 カゼでない(A=0) 20% 単位:1/50 同時分布 P(A,B) B=1 B=0 P(A) A=1 3 2 5 A=0 9 36 45 P(B) 12 38 50 条件付き確率を計算する.  いま求めた同時分布を表にしてみた.ただし,表は実際の確率を50倍した値を示している.  ここで先ほど学んだ方法を使って条件付き確率を求めれば,答え(ノドが痛いときにカゼである確率)は25%となる. Ans.

2.同時分布からの事後確率の計算(7/7) この方法の問題点 2.同時分布からの事後確率の計算(7/7)   この方法の問題点 同時分布 X1 X2 … Xn 確率 1 記憶領域の問題  同時分布表のサイズが指数的 計算時間の問題  周辺分布の計算時間が指数的  いまの例題で学んだような同時分布を用いて事後確率を計算する方法は,考え方はすなおでわかりやすいのだが,効率の面で問題がある. 必要なメモリの量と計算時間が,いずれも指数オーダーとなるのである.すなわち,変数の数がn個のとき,記憶領域の大きさや計算時間が,ほぼ2のn乗に比例するのである.したがって,変数の数が多いときには事実上使用できない.たとえば,変数が10個なら2の10乗=1キロという単位なのでまだだいじょうぶだろうが,変数が20個で2の20乗=1メガ,変数が30個で2の30乗=1ギガとなるあたりで,現在のコンピュータの能力ではほぼ限界に近いだろう.

3.ベイズの規則(1/3) ベイズの規則 (Bayes' rule) 結果から原因を推測できる 因果関係 (causality) 原因 結果  いま見た効率の問題を解決するのが,以降で学ぶベイジアンネットである.その数学的基礎はベイズの規則と呼ばれる簡単な公式である.  このスライドでは,連鎖公式からベイズの規則     P(X|Y) = P(Y|X) P(X) / P(Y) を導いている.  確率変数XとYの間に,原因がXで結果がYであるような因果関係があるとしよう.ふつうは,原因Xが与えられたときに,結果Yが起こる条件付き確率P(Y|X)が与えられていることが多い.  ベイズの規則は,それを用いて,逆に,結果Yを知って原因Xを推定するための事後確率P(X|Y)を計算する公式となっている. 結果から原因を推測できる 因果関係 (causality) 原因 結果 X Y

3.ベイズの規則(2/3) 正規化 質問変数X の値には無関係 証拠変数Y を固定 正規化定数 分子だけ計算  ベイズの規則で証拠変数Yを固定し,質問変数Xの値をいろいろ(といってもこの授業では0と1)変えることを想定しよう.すると,分母のP(Y)はXに無関係な定数となるので,     P(X|Y) = αP(Y|X)P(X) と書くことができる.  したがって,Xの各値0,1に対して,ベイズの規則の分子だけ計算し,その和が確率の総和である1になるように,それぞれを定数倍(α倍)すればよい.この操作を正規化という. となるように,定数倍 (正規化)

A Ans. 3.ベイズの規則(3/3) 例題の解 カゼ ノド 60% カゼ(A=1) B=1 カゼでない(A=0) 20% ベイズの規則を使って,事後確率を計算する. 3/(3+9) 正規化  カゼとノドの例題に戻って,ベイズの規則を使って事後確率を計算すると,このスライドのように,ノドが痛いという証拠のもとで,カゼか否かの確率は 3:9 の比となるので,正規化すると,カゼの確率は25%となる.このように,実際には正規化定数αの値を直接求めなくても,ベイズの規則の分子の値に比例して,確率の総和である1を按分することで事後確率が求められる. Ans.

4.ベイジアンネット(1/5) 導入 (Bayesian network) ベイジアンネット = 有向非循環グラフ + 条件付き確率表 ベイジアンネット = 有向非循環グラフ + 条件付き確率表 P(B) P(E) B E P(D|E) P(A|B,E) A D 有向非循環グラフ P(C|A) C  ベイジアンネット(Bayesian network)は,確率モデルをグラフィカル(グラフ理論的)に表現するためのモデルともいえるもので,条件付き独立(conditional independence)と呼ばれる仮定を積極的に導入することによって,比較的アーク(有向辺)の数が少ないグラフによって確率モデルをビジュアルにわかりやすく表現できる.また,効率良いアルゴリズムによって事後確率の計算をすることができる.  数学的には,ベイジアンネットはつぎに述べる(V,E,P)の3つの要素からなるものとして定義される.  Vはグラフのノードの集合で,それぞれのノードは1つの確率変数を表している.Eは因果関係のある2つの確率変数を関連づけるアーク(有向辺)の集合である.ベイジアンネットでは,グラフG=(V,E)に巡回路(サイクル)を含むことは許されず,Gは有向非循環グラフ(directed acyclic graph: DAG)である. 条件付き確率表 (directed acyclic graph: DAG) (conditional probability table: CPT)

各ノード X ごとに その親ノードの集合を条件とする 条件付き確率表をつくる 4.ベイジアンネット(2/5) 条件付き確率表 Y Z Xの親ノードの集合 X Y Z X=1 X=0 1 0.95 0.05 0.9 0.1 0.3 0.7 0.01 0.99 各ノード X ごとに その親ノードの集合を条件とする 条件付き確率表をつくる  Pは条件付き確率表の集合である.これは,すべてのノードXごとに,P(X | parents(X))という形式の条件付き確率を与えるものである.ここで,parents(X)はXの親ノード(Xに入ってくるアークの根もとにあるノード)の集合である.親ノードの表す確率変数の取りうる値のすべての組合せに対して,X=1である確率を指定する必要がある.ちなみに,各組合せに対してX=0である確率は,1からX=1である確率を引くことによって求められる.

4.ベイジアンネット(3/5) 連鎖公式 ベイジアンネットの連鎖公式 P(B) P(E) B E ベイジアンネットでの約束 P(D|E) P(A|B,E) A D 同時分布は条件付き確率表の積になる  ベイジアンネットにおいては,同時分布は条件付き確率表(CPT)の積になると定義されている.したがって,サイズの巨大な同時分布を記憶しておく必要はなく,(比較的サイズの小さな)条件付き確率表(CPT)だけを記憶しておけば,同時分布の情報をいつでも簡単に計算できるのである.このような定義の背景には,「条件的独立」という数学的な仮定があり,理論的に重要なのだが,この授業ではその説明を省略する。 P(C|A) C 記憶領域の問題は解決!

4.ベイジアンネット(4/5) 例題 周辺分布 ベイジアンネットの連鎖公式 【例題】B=1,C=0,E=1のとき,A=1である確率の求め方を説明せよ. P(B) P(E) B E P(A,1,0,D,1)=P(C=0|A) P(A|B=1,E=1) P(B=1) P(D|E=1) P(E=1) =α P(C=0|A) P(A|B=1,E=1) P(D|E=1) P(D|E) P(A|B,E) A D を用いて, P(1,1,0,1,1),P(1,1,0,0,1),P(0,1,0,1,1),P(0,1,0,0,1) を計算する. P(C|A) C  図に示すノードA~Eからなるベイジアンネットが与えられているとしよう.条件付き確率表(CPT)も具体的に与えられているとする.B=1,C=0,E=1のとき,A=1である確率の求め方を考えてみよう.  基本的には,ベイジアンネットの連鎖公式を利用して同時分布を求めるのだが,この例ではB=1,C=0,E=1であることは知られているので,これは固定し,AとDがそれぞれ1,0である組合せ4通りについてだけ求めればよい.そのとき,A,Dに無関係な項P(B=1)とP(E=1)の積は一定なので,計算する必要はなく,αとおいておこう.  求めたい確率P(A=1 | B=1,C=0,E=1)は,条件付き確率の定義より,     P(A=1,B=1,C=0,E=1) /P(B=1,C=0,E=1) である.この分子と分母は,周辺分布になっているので,引数に表記されていない変数の取り得るすべての値の組合せについて,同時確率を足し合わせて求められる. 最初の2項の和がP(A=1, B=1,C=0,E=1). 周辺分布 4項の和が P(B=1,C=0,E=1). その比がP(A=1 | B=1,C=0,E=1).

4.ベイジアンネット(5/5) 多重結合と単結合 多重結合ネットワーク: 無向グラフが閉路を持つ (multiply-connected network) A 事後確率の計算はNP困難 →指数時間のアルゴリズムしかなさそう B C D 単結合ネットワーク: 無向グラフが閉路を持たない (singly-connected network) B E  このように同時分布が得られれば,どんな事後確率でも定義にしたがって計算できる.特に,全変数を網羅した同時分布を記憶するための大規模な表は必要がなく,各ノード毎の(小さな)条件付き確率表だけを記憶しておけばよい点で,記憶領域の問題が解決されている.しかし,事後確率の計算過程で必要となる周辺分布の計算のために,組合せ的に大量の計算時間を必要とするので,計算時間の問題はまだ解決されておらず,変数の数が多いときには実用的ではない.  そこで,ベイズの規則を利用した効率よい事後確率の計算法が研究されてきている.ただし,その効率はベイジアンネットのグラフの構造に依存する.  グラフが多重結合ネットワーク(無向グラフにしたときに閉路を持つ有向グラフ)のときには,その計算はNP困難であることが知られている.すなわち,コンピュータサイエンスの基礎的な部分に革命でも起こらない限り,指数時間のアルゴリズムしか存在しないと考えられている.それでも,少しでも効率よく計算できるような方法が研究されている.  グラフが単結合ネットワーク(無向グラフにしたときに閉路を持たない有向グラフ)のときには,ネットワークの規模に対して線形時間の効率良いアルゴリズムがある.すなわち,ノードやアークの数を増やしてベイジアンネットの規模を拡大しても,それに比例した程度の計算時間しかかからない.しかし,このアルゴリズムは複雑なので,この授業では内容を説明しない. ネットワークの規模に対して 線形時間のアルゴリズムがある A D C