[AI] 9. Bayes' Net - Representation, Conditional Independence

 

Independence 

확률 모델의 목적은 Joint 확률을 구하는 것인데, Bayes' Net의 목적은 어떤 변수가 Independence를 구하는 것이다. 왜냐하면 Joint 확률은 앞서 말했듯 일반적으로 계산량이 매우 많다. 하지만 만약 두 사건의 Joint 확률을 구하는데 그 두 사건이 독립적인 사건이라면 단순히 두 사건 확률을 곱해주기만 하면 된다. 즉 계산량이 확연히 줄어든다. conditional 확률도 마찬가지다.

즉, Joint 확률을 구하는 것이 확률 모델의 목적인데, Joint 확률을 효과적으로 계산하기 위해서는 Independence를 알면 훨씬 쉬워지며, 그 원리를 활용한 것이 Bayes' Net이다.

Conditional Independence

때론 기존에는 서로 독립적이지 않았던 사건들이 특정 조건이 갖춰지면 독립관계가 될 수도 있다.

• 치통 → 충치 → 의사 진단 : 충치가 있는지 모른 상태에서 병원에 가면 의사가 진단하는데 충분한 영향을 미친다. 하지만 충치가 어디에 있는지 확실히 알고 있으면 치통이 있든 없든 의사의 진단에는 충치만 영향을 미친다.
• 불 → 연기 → 센서 : 불이나면 센서가 사건을 인식한다. 사실 이 사건은 센서가 연기를 인식하는 것이다. 그래서 연기가 났다는 것을 인식할 수 있다면 불이 난 것은 몰라도 센서가 울리는 사건에는 전혀 영향을 미치지 않는다.
• 비 → 우산, 비 → 교통량 : 우리가 비오는 확률을 모른다면 사람들이 우산을 쓰고 있을 때 교통량이 많을 것이라 유추할 수 있다. 하지만 비가 온다는 것을 인지한 순간 우산을 쓴 사건과 교통량이 늘어나는 사건과는 독립적인 사건이 된다.

다소 모호한 표현과 사례이지만, 기억할 것은 서로 dependence하던 사건들이 특정 사건의 확률을 알게 되면 independence한 사건으로 계산할 수 있게 된다는 것이다. 마지막 사례를 예로 들어보자.

만약 독립적인 관계가 없다면 Chain rule에 의해서 P(Umbrella | Rain, Traffic), 즉 비와 교통량이 우산을 쓰는 것에 미치는 영향을 계산할 수 있어야 한다. 하지만 conditional 독립관계를 가정하면 비가 교통량에 미치는 영향, 비가 우산에 미치는 영향만 알면 문제를 풀 수 있게된다. (P(x | y, z) 처럼 여러 사건이 연계된 conditional 확률을 구하는 행위 자체가 굉장히 힘들다. conditional independence를 가정하면 P(x | y, z) = P(x)P(y | x)P(y | z)로 2개 사건의 conditional 확률을 구하는 문제로 만들 수 있다.)

Bayes' Net

앞서 간단히 언급했듯, 확률 모델은 full joint distribution table을 완성시켜야 하는데, joint 확률을 구하는 것이 굉장히 어렵다. Bayes' net은 이 문제점을 해결하기 위해 conditional probabilities(local distribution)를 이용한 graphical model이다. 왜 graphical model이라 불리는지는 곧 이해하게 될 것이다.

1. Representation

Graphical Model Notation

Bayes' net은 사건을 node와 arc로 이루어진 graph로 사건을 표현한다. 위 그림을 보면 Node는 변수(variable)에 해당하고 arc는 두 사건간의 관계(interaction)을 의미한다. node는 assign 될 수 있는 domain이 있는데, 전체적으로 CSP의 표기법과 유사하다. 그리고 애초에 독립적인 사건은 arc로 이어지지 않는다. 실제로 위 그림처럼 날씨가 충치에 영향을 미치지 않는다고 표현하였다. 

(graph의 설계는 문제를 제기한 domain knowledge가 큰 영향을 미친다. 만약 날씨가 충치에 영향을 미친다고 생각한다면 그건 또 다른 문제가 되듯, graph를 설계하는 것은 기초이면서 가장 중요한 행위이다.)

Bayes' Net semantics

즉, Bayes' Net은 원인(Cause)이 되는 parents node로 부터 결과(Effect)가 child node인 DAG(directed acyclic graph) 이다. 그리고 목적은 결과가 주어졌을 때 그 원인이 어디서 부터 왔는지를 찾는 것이고, 그 의미는 P(결과 | 원인1, 원인2, 원인3)으로 표현이 가능하다. 이 값들을 table형태로 정리하는 것이 CPT(Conditional Probability Table)이고, CPS를 data로부터 알아 내는 것이 바로 Bayes' Net Learning이다. 때론 CPT는 사람이 준다고 가정하고 Topology(=graph)를 학습하는 경우도 많다.

그리고 가장 핵심은 conditional independence를 찾아서 위 식처럼 full joint 확률을 local distribution의 곱으로 풀게하는 것이다. 간단한 예를 보자.

만약 위와 같은 문제를 푼다면 P(+r, -t) = P(+r) P(+r | -t) 처럼 prior 확률과 conditional 확률의 곱(local distribution)으로 구할 수 있다.

마찬가지로 이 문제도 chain rule로 풀면 다소 복잡해질 수 있지만, graph가 주어지면 local distribution으로 이루어진 CPT로 full joint 확률을 구할 수 있다.

Causality

수학적으로는 P(x, y)나 P(y, x)나 같고 P(x | y)나 P(y | x)는 같다. 하지만 domain knowledge에 맞게 graph를 설계 해야지만 graph가 심플해지고 문제를 풀기 쉽다. 하지만 causality 하지 않더라도 수학적으로 문제를 푸는데는 지장이 없다. 

2. Conditional Independence

Bayes' Net은 joint확률을 local distribution의 곱으로 풀기 위해 conditional independence를 가정하기 때문에 제대로 이해할 필요가 있다.

D-separation

기계적으로 PC가 topology만 보고 dependency를 알 수 있게 하는 알고리즘이 D-separation 알고리즘이다. D-separation 알고리즘의 가장 기본은 3개 노드를 묶어서 dependency를 확인하는 것이다.

1) Causal Chains

3개 node가 연속적인 chain 일 때 causal chain이라 하며, 중간 사건이 알려지면 나머지 사건은 독립이 된다. Y가 알려지면서 X, Z가 독립되면서 Blocking 된다 라고도 한다.

2) Common Cause

1개 노드개 2개의 child를 가질 때 common cause라 하는데, common cause가 주어지면 마찬가지로 child가 독립이 된다.

3) Common Effect (v-structures)

Common Cause와 반대로 2개의 parent를 가질 때는 child가 알려졌을 때 오히려 dependency가 생긴다. 이 현상을 Explaining out 이라고도 부른다.

General Case

위에서 언급된 case들이 복합적으로 작용하는 것이 일반적인데, 당황하지 말고 triple로 묶어서 D-separation을 적용하면 Active(dependence), Inactive(Independence, blocking)인지 알 수 있다. 정확히 이해 했다면 아래 예제들을 이해할 수 있을 것이다. (Blocking → Yes)

• T가 주어지면 R, T, B는 active해진다.. 하지만 L, T'입장에서는 중간사건 R, T가 알려졌음으로 inactive(blocking)된다.

• T나 T'이 주어지지 않는 이상 v-structure는 blocking 된다. 즉 L과 B는 inactive이다.

• T가 주어지면 v-structure는 active 된기 때문에 v-structure에 연결된 L, B는 active된다.

• T'이 주어진 것은 T가 주어진 것이나 마찬가지다. 그래서 v-structure는 active된다.

• T가 주어져서 v-structure가 active 해 졌지만 중간 노드인 R이 주어짐으로써 blocking 된다.

T-R-D causal chain이지만 T-S-D는 v-structure이다. 두 조건을 모두 만족시켜야한다.

• S가 주어지지 않으면 active된다.

• R이 주어지고 S가 주어지지 않으면 blocking 된다.

• R, S가 모두 주어지면 v-structure가 active 된다.

• 이 경우는 independence가 없다.