[AI] Bayes’ Nets (1)

이 글은 포스텍 이근배 교수님의 CSED442 인공지능 수업의 강의 내용과 자료를 기반으로 하고 있습니다.

오랜만에 쓰는 인공지능 글이다.

하도 일이 많아서 글이 많이 밀렸다.

이번주는 과제가 없어서 이번주 안에 밀린 양을 다 쓸 예정이다.

1. Probability

베이즈 네트워크에 대해 들어가기 전에, 베이즈 네트워크의 핵심이 되는 독립에 대해서 배워야 한다.

Independence

두 확률 변수가 독립이면 아래와 같은 관계가 성립한다.

• $\forall x,y : P(x,y)=P(x)P(y)$

• $\forall x,y : P(x\vert y)=P(x)$

이를 아래와 같은 기호로 표시한다.

$X \mathrel{\unicode{x2AEB}} Y$

Conditional Independence

$X$가 $Z$가 주어졌을 때 $Y$에 대해 독립이라면 아래와 같은 관계가 성립한다.

• $\forall x,y,z: P(x,y\vert z)=P(x\vert z)P(y\vert z)$

• $\forall x,y,z: P(x\vert z,y)=P(x\vert z)$

이를 조건부 독립이라고 하며, 아래와 같은 기호로 표시한다.

$X\mathrel{\unicode{x2AEB}} Y \vert Z$

개인적으로 이 개념을 처음 봤을 때 직관적으로 와닿지 않았었다.

우선 수식의 의미부터 간단히 알아보자.

$\forall x,y,z: P(x,y\vert z)=P(x\vert z)P(y\vert z)$

이 수식은 독립의 $\forall x,y : P(x,y)=P(x)P(y)$ 수식과 거의 유사한 의미이다.

다만, $z$가 주어진 경우에만 쪼갤 수 있다! 라고 이해하면 된다.

$\forall x,y,z: P(x\vert z,y)=P(x\vert z)$

이 수식도 독립의 $\forall x,y : P(x\vert y)=P(x)$ 수식과 거의 유사한 의미이다.

다만, $z$가 주어진 경우에만 $y$를 무시할 수 있다! 라고 이해하면 된다.

수식적으로 이해는 했으니, 직관적으로 조건부 독립이 무슨 소리인지 이해해보자.

Traffic, Umbrella, Raining 이라는 세 개의 사건이 주어졌다고 해보자.

세 사건 간의 연관관계는 위의 그래프와 같다.

Raining이 주어지지 않았을 때, Traffic과 Umbrella는 독립일까?

그렇지 않다.

예를 들어, Traffic이 있다고 해보자. 그러면 Raining이 있을 확률이 올라가므로, Umbrella의 확률도 올라가게 된다.

반대로 Traffic이 없으면 raining의 확률이 내려가고, 이에 따라 umbrella의 확률도 내려간다.

그렇다면 raining이 주어지면, Traffic과 Umbrella는 독립일까?

그렇다.

예를 들어, Raining이 있다고 해보자. 그러면 Traffic이 어떻던 간에, 이미 raining은 정해져 있으므로 traffic의 사건이 umbrella에게 영향을 끼치 못한다.

따라서 우리는 Umbrella는 Raining이 주어졌을 때, T에 대해 독립이다 라고 말할 수 있는 것이다.

PPT에 있는 chain rule과 ghostbuster 부분은 이후 베이즈 네트워크를 이해하면 자연스레 이해가 될 것이므로 생략한다.

2. Bayes’ Nets

Probabilistic Model

우리가 만들고자 하는 것은 확률 모델이다.

모델이란 현실을 추상화한 것을 말하는데, 모델링을 하는 이유는 좀 더 쉽게 계산을 하기 위해서이다.

예를 들어 자동차의 움직임에 대한 모델링을 한다고 하자.

모델을 만드는 가장 단순무식한 방법은 joint distribution table을 만드는 것이다.

그러면 자동차의 움직임에 관여하는 요소들; 배터리 수명, 배터리 충전 상태, 기름 충전 상태, 경고등 상태 등등 을 추려낸 다음, 이것에 대해서 full joint distribution table을 만들면 된다.

배터리 수명	기름 충전 상태	경고등	…	P(B, O, L, …)
0	0	0	…	0.01
1	1	1	…	0.01
2	2	1	…	0.01

이런 식으로 말이다.

그런데 이게 현실적일까? 요소가 한 10개만 되어도 한눈에 담을 수 없을 정도로 표가 커질 것이다.

그래서 모델을 표시할 다른 방법이 필요했고, 그게 바로 베이즈 네트워크이다.

베이즈 네트워크의 핵심은 독립을 이용해서 좀 더 간결하게 확률 모델을 표현하는 것이다.

아직 베이즈 네트워크를 배우진 않았지만, 한번 자동차의 움직임에 대한 모델을 베이즈 네트워크를 이용해서 표시해보면 대충 아래처럼 나온다.

full joint distribution 방식은 사건 간의 연관관계를 전혀 활용하지 않았다.

베이즈 네트워크는 사건 간의 연관관계(local interaction)를 적극적으로 활용한다.

예를 들어, 위의 베이즈 네트워크는 아래의 연관관계를 활용하고 있다.

• 베터리가 죽는 사건은 배터리의 수명과 관계가 있다.

• 배터리가 충전이 안되어있는 사태는 배터리가 죽었거나 충전이 안되는 사건과 관계가 있다.

이때 이 관계를 독립을 사용해서 formal하게 표현할 수 있기 때문에 우리가 앞서 독립에 대해 배웠던 것이다.

Intuition

우리가 앞선 예제에서 베이즈 네트워크에 대해 배웠던 것을 정리하면 아래와 같다.

• 노드는 확률 변수(interaction)를 의미한다.
• 화살표는 연관관계(interaction)를 의미한다.

나중에 배우겠지만, 정확하게는 화살표는 conditional independence를 의미한다.

잠깐 퀴즈!

베이즈 네트워크가 full joint distribution과 다를바가 없을 땐 언제일까?

정답은 전부 독립일 때이다.

이렇게 모든 확률 변수가 독립이라면, 확률 변수 간에 어떠한 관계도 없으므로 베이즈 네트워크가 함축할 수 있는 정보가 없다.

퀴즈 2!

아래 상황의 베이즈 네트워크를 구하자.

잘 생각해보면 꽤 당연하다. 답은 이렇다.

이쯤되면 베이즈 네트워크가 확률변수 간의 연관관계를 표현한다는 것을 알았을 것이다.

그럼 이제 베이즈 네트워크의 formal한 정의에 대해서 알아보자.

Semantics

베이즈 네트워크는 세 가지 성질에 의해 정의된다.

• A set of nodes, one per variable $X$

• A directed acyclidc graph

• A conditional distibution for each node

  이전에는 연관관계라고 모호하게 표현했던 것을 좀 더 정확하게 정의할 수 있다.

  

  어떤 노드 $X$가 $A_1, \cdots, A_n$를 부모로 가진다는 말은 $X$가 $P(P\vert A_1, \cdots , A_n)$라는 conditional distribution을 가진다는 의미이다.

곧, 베이즈 네트워크란 그래프 + Local conditional probabilities라고 할 수 있다.

Probabilities in BNs

한 가지 놀라운 사실은 베이즈 네트워크는 joint distribution을 implicit하게 인코딩하고 있다는 점이다.

분명 우리가 정의한건 Local conditional distribution 밖에 없는데, 이것들을 잘 조합하면 joint distribution을 만들어낼 수 있다는 것이다.

만드는 방법은 간단하다. Local conditional distribution을 전부 다 곱하면 된다!

근데 그렇다고 막 아무 순서대로 곱해서 되는 건 아니다. 되도록 하는 순서가 있다.

간단한 예제를 통해 이해도를 높여보자.

보다시피 아무 순서대로나 막 곱하면 당연히 안되고, $x_1=cavity$이어야만 한다.

왤까? 수식의 증명을 통해 알아보자.

증명 과정은 간단하다.

1. Apply chain rule

   

2. Assume conditional independences

   

   Assume 한다는 표현에 주의를 기울여야 한다.

   

   우리가 베이즈 네트워크에서 정의한 것은 각 노드가 parent에 대한 conditional distribution을 가진다는 것 밖에 없다.

   위 수식처럼 노드에 순서를 부여하지도 않았고, $x_i$의 부모가 $x_1, x_2, \cdots, x_{i-1}$ 중에 있다는 정의는 하지 않았다.

   그렇기에 Assume 한 것이다.

   Formal하게는 아래의 수식을 assume 하는 것이라 할 수 있다.

   $x_i \mathrel{\unicode{x2AEB}} \lbrace x_1, x_2, \cdots x_{i-1} \rbrace - parents(X_i) \vert parent(X_i)$

   곧, joint distribution을 구하기 위해서는 부모에 낮은 숫자를 부여하고, 낮은 순서대로 local distribution을 곱해야 한다.

3. Consequence

   

이로부터 알 수 있는 사실이 있다.

Not every BN can represent every joint distribution

베이즈 네트워크는 자신이 인코딩하고 있는 joint distribution과 일치하지 않는 joint distribution을 표현할 수 없다는 얘기이다.

예를 들어 위 그래프는 해당 conditional indepdency를 만족하는 joint distribution만 표현할 수 있다.

자 그럼 간단한 예제를 풀어보자.

이 친구의 joint distribution $P(+b,-e,+a,-j,+m)$은 어떻게 구할 수 있을까?

답은 $P(+b)P(-e)P(+a\vert +b, -e)P(-j\vert +a)P(+m \vert+a)$이다.

왜 이렇게 구해야 하는지 이해가 가면 이 파트를 잘 이해한 것이다.

Causality

한 가지 생각해봐야 할 점은 화살표가 의미하는게 인과관계(casuality)일까 아님 상관관계(correlation)일까?

흔히 인과관계라고 생각하기 쉬운데, 꼭 인과관계를 표현하고 있는 것은 아니다.

예를 들어, Raining과 Traffic에 대한 두가지 베이즈 네트워크를 살펴보자.

이런 식으로 인과관계를 표현하는 것이 훨씬 알아듣기 편하고, 올바른 베이즈 네트워크로 생각된다.

그러나, 보다시피 굳이 인과관계를 표현하지 않더라도 동일한 distribution을 얻는다.

이로부터 중요한 사실 하나를 얻는다.

베이즈 네트워크는 굳이 인과관계(casuality)를 표현할 필요는 없다

다만 인과관계로 표현하는 것이 화살표의 수를 줄일 수 있고, 더 이해하기 쉽고, 데이터도 모으기 쉽기 때문에 그렇게 하는 것이다.

기억하자. 우리가 정의한 것은 local conditional indepdence 밖에 없다!

3. Conditional Independences in BNs

Probabilities in BNs에서 알아봤듯이, 베이즈 네트워크는 자신이 인코딩하는 joint distribution만 표현 가능하다.

베이즈 네트워크가 인코딩 하고 있는 joint distribution을 알기 위해서는 네트워크가 assume하는 conditional independence를 정확히 이해해야 한다.

문제는, 우리가 정의한 local conditional indepdence외에도, 구조의 특이성에 의해 additional conditional independence가 생길 수 있다는 점이다.

예를 들어 아래의 베이즈 네트워크가 주어졌다고 해보자.

우선 Probabilities in BNs에서 배웠던 chain rule assumption이 있다.

• $P(x,y,z,w)=P(x)P(y\vert x)P(z\vert y)P(w\vert z)$

직관적으로, $y$가 고정되면 $x$의 영향이 $w$로 가지 못할 것 같다. 확인해보자.

• $P(w\vert x,y)\;?=\;P(w\vert y)$
• $P(w\vert x,y)=P(w,x,y)/P(x,y) \\ =\sum_z P(x)P(y\vert x)P(z\vert y)P(w\vert z)/P(x)P(y\vert x) \\ =\sum_z P(z\vert y)P(w\vert z)=\sum_z P(z\vert y)P(w\vert z,y)(\because assumption)\\ =P(w\vert y)$

놀랍게도, 그렇다.

이로부터 우리는 베이즈 네트워크에 숨어있는 additional conditional independence가 존재함을 알았다.

그럼 이걸 찾아낼 수 있는 방법이 있을까? 이걸 위처럼 일일이 수식으로 증명하기엔 너무 빡세다.

그래서 나온 것이 D-seperation이다.

D-separation

D-separation은 triple에 대한 indepdendence framework이다.

Triple에 대해서 안다면, 이후에 배울 active/inactive method를 통해 모든 베이즈 네트워크를 분석할 수 있다.

Casual Chain

첫 번째로 알아볼 것은 casual chain이다.

말 그대로 원인의 원인이 존재하는 것이다.

두 가지 경우의 independence에 대해 분석해보자.

1. $X\mathrel{\unicode{x2AEB}}Z?$

   당연하게도, 아니다.

   $Z$가 $Y$의 영향을 받고, $Y$가 $X$의 영향을 받으므로 $Z$는 $X$의 영향을 받을 수 밖에 없다.

   극단적인 케이스를 예시로 들어보겠다.

   • $P(+y\vert +x)$: $+x$면 무조건 $+y$이다
   • $P(-y\vert -x)$: $-x$면 무조건 $-y$이다
   • $P(+z\vert +y)$: $+y$면 무조건 $+z$이다
   • $P(-z\vert -y)$: $-y$면 무조건 $-z$이다

   이렇게 되면, $+x$일때 무조건 $+z$일 수 밖에 없다. 따라서 독립이 아니다.

2. $X\mathrel{\unicode{x2AEB}}Z \vert Y?$

   직관적으로도 보이지만, 그렇다

   간단히 증명해보자.

   

위 상황을 한 마디로 표현하면 아래와 같다.

Evidence along the chain “blocks” the influence

Common caues

두 번째로 알아볼 것은 Common caues이다.

말 그대로 공통의 원인이 존재하는 것이다.

두 가지 경우의 independence에 대해 분석해보자.

1. $X\mathrel{\unicode{x2AEB}}Z?$

   당연하게도, 아니다.

   $Z$가 $Y$의 영향을 받고, $X$가 $Y$에 영향을 간접적으로 주므로 $Z$는 $X$의 영향을 받을 수 밖에 없다.

   극단적인 케이스를 예시로 들어보겠다.

   • $P(+x\vert +y)$: $+y$면 무조건 $+x$이다
   • $P(-x\vert -y)$: $-y$면 무조건 $-x$이다
   • $P(+z\vert +y)$: $+y$면 무조건 $+z$이다
   • $P(-z\vert -y)$: $-y$면 무조건 $-z$이다

   이렇게 되면, $+x$일때 $+z$가 될 확률이 높아진다. 따라서 독립이 아니다.

2. $X\mathrel{\unicode{x2AEB}}Z \vert Y?$

   $X$의 영향이 $Y$가 고정됨으로써 막힐테니, 그렇다

   간단히 증명해보자.

   

위 상황을 한 마디로 표현하면 아래와 같다.

Observing the cause blocks influence between effects

Common effect

마지막으로 알아볼 것은 Common effect이다.

말 그대로 공통의 결과가 존재하는 것이다.

두 가지 경우의 independence에 대해 분석해보자.

1. $X\mathrel{\unicode{x2AEB}}Z?$

   놀랍게도, 그렇다!

   간단히 증명해보자.

   

2. $X\mathrel{\unicode{x2AEB}}Z \vert Y?$

   놀랍게도, 그렇지 않다.

   Effect $Z$가 결정되면서, 원인 $X, Y$끼리의 충돌이 생기기 때문이다.

   예를 들어, Traffic이 목격되었고, BallGame이 목격되었다면 Raining이 아닐 가능성이 높아지는 것이다.

이전의 두 상황과는 반대로 돌아간다는 것에 집중하자!

혼자 다른 탓에 아예 이름을 붙여서 v-structure 이라고 부르기도 한다.

위 상황을 한 마디로 표현하면 아래와 같다.

Observing an effect activates influence between possible causes

The General Case

이제 D-separation을 General Case로 확장해보자.

Reachability

매번 설명할 때, “~의 영향이 ~가 고정됨으로써 막히니까 ~에 영향을 못준다” 라고 말했었다.

이로부터 가장 간단하게 생각해볼 수 있는건 reachability를 따지는 것이다.

Evidence node는 막힌 노드로 생각한 다음, 방향을 무시하고 reachability를 따졌을 때 도달 불가능하면 conditionally independent 인 것이다.

그런데 이건 문제가 있다.

마지막에 배웠던 common effect를 감지할 수 없다는 것이다.

Common effect는 중간에 있는 노드가 evidence node일때 오히려 conditionally independent 하지 않기 때문이다.

따라서 이 알고리즘은 틀렸다!

Active / Inactive Paths

$X\mathrel{\unicode{x2AEB}}Y \vert Z$이려면 어떻게 되어야 할까?

직관적으로, $X$와 $Y$ 사이의 모든 경로가 $Z$에 의해 “d-seperated” 되어 있으면 될 것이다.

그러면 어느 경로로도 영향이 전파될 수 없으므로 conditionally independent 한 것이다.

그럼 경로가 d-seperated 되어있는지는 어떻게 판단해야 할까?

간단하다. 경로를 triple로 분해해서, 각 triple이 d-seperated인지 아닌지를 판단하면 된다.

이때, d-seperated triple을 inactive triple, 반대를 active triple이라고 한다.

• Active triple: NOT conditionally independent

• Inactive triple: Conditionally independent

추가된 점은 active triple의 네 번째 triple이다. 잘 기억해두자.

다시 논의로 돌아와서, 경로를 triple로 분해한 다음에 어떻게 해야 이 경로가 d-seperated 되어있는지 판단할 수 있을까?

간단하다, Triple 중에 단 하나라도 inactive triple이 있다면, 해당 path도 d-seperated 되어있다.

반대로 모든 triple이 active라면 해당 path는 d-seperated 되어있지 않다.

이때, d-seperated 된 path를 inactive path, 안 된 path를 active path라고 한다.

• Active path: Each triple is active

• Inactive path: One or more triple is inactive

드디어 개별 경로에 대해 판단하는 방법을 알았다.

이제 $X$와 $Y$ 사이에 존재하는 모든 경로에 대해 active / inactive를 판단해주면 된다.

이때 하나라도 active path가 있다면, 이 경로를 타고 영향이 전파될 것이므로 not conditionally independent 이다!

정리하자면 이렇다.

1. $Z$를 색칠한다 (Blocked node)
2. $X$에서 $Y$로 가는 경로를 모두 구한다.
3. 각 경로가 inactive path인지 active path인지 구한다
4. Active path가 없다면 condtionally independent 이다
5. Active path가 하나라도 있다면, dependent 이다.

Examples

간단한 예제이다.

• $R\mathrel{\unicode{x2AEB}}B$ : $RTB$가 v-structure이므로 true
• $R\mathrel{\unicode{x2AEB}}B \vert T$ : $RTB$가 v-structure인데, 중간 노드가 막혔으므로 false
• $R\mathrel{\unicode{x2AEB}}B \vert T^{\backprime}$ : $RTB$가 v-structure인데, 중간 노드의 자식이 막혔으므로 false

일부만 풀어보겠다.

• $L\mathrel{\unicode{x2AEB}}T^{\backprime} \vert T$ : $LRTT^{\backprime}$의 경로에서, $RTT^{\backprime}$ triple이 막혀있으므로 true
• $L\mathrel{\unicode{x2AEB}}B \vert T^{\backprime}$ : $RT^{\backprime}B$ v-structure가 막힌 상태로 존재하므로 false
• $L\mathrel{\unicode{x2AEB}}B \vert T,R$ : 헷갈릴 수도 있는데, triple에서 중앙만 보면 된다. $LRT$에서 중간 노드 $R$이 막혀있으므로 true

Strucuture Implications

드디어 우리는 베이즈 네트워크에 존재하는 모든 conditional independences을 알아낼 수 있게 되었다.

이 사실이 왜 중요할까? 여러번 말했지만,

Conditional independences가 표현할 수 있는 probability distribution을 결정짓기 때문이다!!

예를 들어, 위의 베이즈 네트워크들은 옆의 conditional independences를 만족시키는 probability distribution만 표현할 수 있다.

위 그림은 표현할 수 있는 distribution을 기준으로 베이즈 네트워크들을 나눈 그림이다.

보다시피, 아무 화살표가 없는 경우가 제일 빡세다.

화살표를 늘릴 수록 표현할 수 있는 distribution이 늘어난다!