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

Presentation on theme: "認知システム論 知識と推論（３） 不確実な知識の表現と確率推論 事後確率と信念改訂 同時分布からの事後確率計算 ベイズの規則"— Presentation transcript:

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

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

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

4 a,b,c,d,e∈{0,1} g1,g2,g3 ∈{normal,abnormal}
１．事後確率と信念改訂(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の４通りの組合せごとにe=0,1である確率をそれぞれ与えるわけである． 　さらに，入ってくるアークが１本もないノードについては，事前確率を与えることとする． 　このように，グラフと条件付き確率分布によって構築された確率モデルがベイジアンネット(Baysian network)と呼ばれるものである．その正式な定義は後に学ぶ． 　ベイジアンネットが与えられているとき，新たにわかった証拠から事後確率を計算するアルゴリズムが知られている．それを用いると，たとえば，スライドに書かれたような質問に対する解を効率良く求めることができる．証拠を表す確率変数を証拠変数(evidence variable)，事後確率を知りたい確率変数を質問変数(question variable)という．

5 １．事後確率と信念改訂(4/4) 医療診断の例題
１．事後確率と信念改訂(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%

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

7 ２．同時分布からの事後確率の計算(2/7) 周辺分布
２．同時分布からの事後確率の計算(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 の取りうる値の組合せのすべてについての同時確率の和である．スライドのような２次元の表の場合には，行方向の和，あるいは列方向の和がそれに当たる．通常，それらの和はこのスライドのように表の右端や下端などの「周辺」に表示されるので，周辺分布と呼ばれている． 　 XやYが複数個あるような多次元の場合も，これを自然に拡張して考える． P(Y) 0.4 0.6

8 ２．同時分布からの事後確率の計算(3/7) 条件付き確率
２．同時分布からの事後確率の計算(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)との比を求めるのである． 周辺分布

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

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

11 ２．同時分布からの事後確率の計算(6/7) 例題の解(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 条件付き確率を計算する． 　いま求めた同時分布を表にしてみた．ただし，表は実際の確率を５０倍した値を示している． 　ここで先ほど学んだ方法を使って条件付き確率を求めれば，答え（ノドが痛いときにカゼである確率）は25%となる． Ans.

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

13 ３．ベイズの規則(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

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

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

16 ４．ベイジアンネット(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)の３つの要素からなるものとして定義される． 　Vはグラフのノードの集合で，それぞれのノードは１つの確率変数を表している．Eは因果関係のある２つの確率変数を関連づけるアーク（有向辺）の集合である．ベイジアンネットでは，グラフG=(V,E)に巡回路（サイクル）を含むことは許されず，Gは有向非循環グラフ(directed acyclic graph: DAG)である． 条件付き確率表 (directed acyclic graph: DAG) (conditional probability table: CPT)

17 各ノード Ｘ ごとに その親ノードの集合を条件とする 条件付き確率表をつくる
４．ベイジアンネット(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 各ノード Ｘ ごとに その親ノードの集合を条件とする 条件付き確率表をつくる 　Pは条件付き確率表の集合である．これは，すべてのノードXごとに，P(X | parents(X))という形式の条件付き確率を与えるものである．ここで，parents(X)はXの親ノード（Xに入ってくるアークの根もとにあるノード）の集合である．親ノードの表す確率変数の取りうる値のすべての組合せに対して，X=1である確率を指定する必要がある．ちなみに，各組合せに対してX=0である確率は，１からX=1である確率を引くことによって求められる．

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

19 ４．ベイジアンネット(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である組合せ４通りについてだけ求めればよい．そのとき，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) である．この分子と分母は，周辺分布になっているので，引数に表記されていない変数の取り得るすべての値の組合せについて，同時確率を足し合わせて求められる． 最初の２項の和がP(A=1, B=1,C=0,E=1). 周辺分布 ４項の和が P(B=1,C=0,E=1)． その比がP(A=1 | B=1,C=0,E=1)．

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