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

Outline Introduction Independent assumption Consistent probabilities Evaluating networks Conclusion

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

Disease-test Bayesian network Introduction Causal Relationship

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))를 위한 조건부 확률 테이블

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가 존재 또는 두 노드가 관련 있다는 증거가 존재

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

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

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이 정의됨

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

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)

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에서 확률이 가장 높은 경우의 레이블

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

Exact inference Evaluating Networks

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

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

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

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

Information flows in merged computation Evaluating Networks

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

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

“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”