Bayesian Network 2006년 2학기 지식기반 시스템 응용 석사 3학기 송인지.

Presentation on theme: "Bayesian Network 2006년 2학기 지식기반 시스템 응용 석사 3학기 송인지."— Presentation transcript:

1 Bayesian Network 2006년 2학기 지식기반 시스템 응용 석사 3학기 송인지

2 Outline Introduction Independent assumption Consistent probabilities
Evaluating networks Conclusion

3 당신이 병에 걸렸을 확률? Introduction 당신은 병이 있다는 판정을 받았다. 이 검사의 오진율은 5%이다.
일반적으로 이 병에 걸릴 확률은 0.1%이다. 1970년대: 미국의 병원 의사 80%가 95%라고 답 P(질병|질병판정) = ? P(질병판정|질병X) = 0.05, P(질병X판정|질병) = 0.05 P(질병) = 0.001

4 Disease-test Bayesian network
Introduction Causal Relationship

5 Bayesian Networks Introduction 변수 집합 사이에 확률적 관계를 표현한 graphical model
조건부 확률들에 기반한 결합 확률 분포의 간략한 표현 Qualitative parts: graph theory DAG Vertices: 변수들 Edges: dependency or influence Quantitative part: probability theory 각 변수 Xi와 그의 부모 Pa(Xi)에 마다, P(Xi|Pa(Xi))를 위한 조건부 확률 테이블

6 d-Connection & d-Sepeartion
Independence Assumption 증거 노드 E에 대해 두 노드 q와 r 사이의 path가 d-connecting 이려면, path 안의 각 내부 노드 n이 다음과 같은 성질 중 하나를 충족 Linear or diverging: n의 어떤 노드도 E안에 포함X Converging: n 또는 그 하위 노드 중 하나라도 E안에 포함 만약 두 노드 사이에 d-connecting path가 없으면, 두 노드는 d-seperated 대략적으로 말해 Causal path가 존재 또는 두 노드가 관련 있다는 증거가 존재

7 Question 1: Is BP dependent on FO?
Independence Assumption Converging Node No! 만약 두 사건 사이에 아무 연관관계가 없지만, 같은 사건의 원인이 된다면, 두 사건은 독립 BN은 원인 판별에 주로 사용됨  converging nodes 자주 사용됨

8 Question 2: Is BP independent on FO?
Independence Assumption Evidence No! 두 노드 사이의 path에 증거 노드가 존재하는 경우는 Q1과 다름 BP의 확률이 증가하면 FO의 확률은 감소 가장 그럴 듯 한 원인을 원인 목록에서 제거하면, 덜 그럴 듯 하던 원인이 조금 더 그럴 듯 해짐

9 Nothing looks amiss? Consistent Probability P(a|b) = .7 P(b|a) = .3
P(a) = P(b)P(b|a)/P(b|a) = .5 * .7 / .3 = 1.16 > 1 BN의 또 다른 장점! 만약 일부의 필요한 확률 값들만 정해 주면, 전체 확률 테이블은 consistency를 유지 유일하게 distribution이 정의됨

10 Parameter saving in BN Consistent Probability
Complete distribution for doubled FO : 2N-1 = = 1023 Required value for doubled FO BN : 21

11 Detailed explanation Consistent Probability To define a network
Requires Joint distribution for all values For set of boolean var (a,b): P(a,b), P(∼a, b), P(a, ∼b), P(∼a, ∼b) For n boolean var: 2n-1 values Requires the probability of every node given all possible combinations of its parent 각각의 joint distribution  Chain rule 독립 가정 Chain rule 계산 쉬워짐 Marginal independence A⊥B ⇔ P(A|B) = P(A), P(B|A) = P(B) Conditional independence A⊥B|C ⇔ P(A|B,C) = P(A|C), P(B|A,C) = P(B|C)

12 Inference tasks Evaluating Networks Single Marginal: P(x) or P(x|y)
Subjoint: P(x,y) All Marginal: P(x) for all x Arbitary subset of queries: {P(x,y), P(z)} Boolean: P(X^Y) MPE(Most Probable Explanation): Full JPD에서 확률이 가장 높은 경우의 레이블 MAP(Maximum A posteriori Probability): Sub JPD에서 확률이 가장 높은 경우의 레이블

13 Inference methods Evaluating Networks Exact inference
Factoring Variable elimination Junction tree Approximate inference Simulation Search Model reduction

14 Exact inference Evaluating Networks

15 Factoring Evaluating Networks
단순한 greedy heuristics을 일반적으로 적용 – 계산 량이 적은 것을 우선적으로 선택 Single-query tasks에만 사용

16 Variable elimination Evaluating Networks
Query에 포함되지 않은 변수들의 삭제 순서를 정하고 변수들을 삭제해가며 계산 삭제 순서  NP-Hard Approximation methods: Minimum deficiency ordering (Connection이 가장 적은 노드 우선 삭제) Factoring과 마찬가지로 Single Marginal Query 전용

17 Unified computational tree
Evaluating Networks Multiple query를 위해 unified computational tree를 구성

18 Computation trees for P(Cold) & P(Cat)
Evaluating Networks

19 Information flows in merged computation
Evaluating Networks

20 Junction tree Evaluating Networks
모든 marginal task를 위해 structure sharing을 최대화 Tree 생성을 위해 elimination ordering 사용 Elegant! Simple! Well-understood! Efficient! P(A)*P(B|A)*P(C|A)

21 Approximate inference
Evaluating Networks Simulation 무작위로 생성된 샘플들을 바탕으로 추측 Search 가장 큰 확률 값 몇 개만 계산에 이용 Model reduction 변수나 연결선의 개수를 줄이는 방법 등 Searching example P(Cold=True) = .035/( ) = .04 ≒ .05 (True value)

22 “She ordered a milk shake. She picked up the straw”
Conclusion Knowledge base의 간략한 확률적 표현 불확실하고 복잡한 문제에 주로 사용됨 Mobile intelligence & BN ? Word-sense ambiguity “She ordered a milk shake. She picked up the straw”