[KOOC] 인공지능 및 기계학습 개론 7주차 - Bayesian Network

Chapter 7. Bayesian Network

• 목차

1. Probability
   • recover the probability concepts
   • recover the probability theorems
   • recover the concepts of the marginal and the conditional independencies
2. Bayesian networks
   • syntax and semantics of Bayesian Networks
   • how to factorize Bayesian networks
   • calculate a probability with given conditions
3. inference of Bayesian networks
   • calculate parameters of Bayesian networks
   • list the exact inference of Bayesian networks

 

 

7-1. theorems of Probability

bayesian network에 들어가기 전에, probability에 대한 복습을 하고자 한다.

 

• Conditional Probability

conditional probability란 특정 상황이 주어졌을 때의 확률을 구하는 것이다.

예를 들어, A와 B에 대한 상황이 존재한다고 생각해보자. B가 주어졌을 때의 A의 확률을 구한다는 것은 P(F=True)인 영역 속에서 P(H=True)인 영역에 해당한다.

이는 P(A = true | B = true) 와 같이 표현한다.

\[P(A = true | B = true) = \cfrac{P(A,B)}{P(B)}\]

 

• Joint Probability

비슷한 개념으로 Joint Probability라는 것이 있다. P(A = true, B = true) 와 같이 표현할 수 있고, 이는 A = true 와 B = true 인 확률을 나타낸다.

\[P(A = true, B = true) = P(A|B)P(B)\]

 

이 두 개념을 활용하여 개별 확률인 marginal probability를 구할 수 있다.

\[P(a) = \sum_b P(a,b) = \sum_b P(a|b)P(b)\]

 

만약, joint distribution인 P(a,b,c,d) 가 주어졌을 때, 우리는 P(b)에 대해 식을 세울 수 있다.

\[P(b) = \sum_a \sum_c \sum_d P(a,b,c,d)\]

또는, joint distribution을 통해 conditional probability를 구할 수 있다.

\[P(c|b) = \sum_a \sum_d P(a,c,d | b) = 1/P(b) \sum_a \sum_d P(a,c,d,b)\]

이 때, 1/P(b) 는 normalization constant(정규화 상수) 이다.

 

이렇게만 보면 joint probablity가 매우 강력한 개념이라 생각이 되지만, joint probability를 구하기 위해서는 개별 확률들을 알아야 하므로, feature의 개수와 개별 경우의 수에 따라 기하급수적으로 파라미터가 증가한다.

만약 feature 개수가 4개이고, 개별 feature이 true/false로 구성된다면 총 16-1 개의 파라미터를 구해야 한다.

 

joint probability의 또다른 특징으로는 chain rule 이다.

\[P(a,b,c,...z) = P(a|b,c,...,z)P(b,c,...,z) = P(a|b,c,...,z)P(b|c,...,z)P(c|...,z)...P(z)\]

 

 

• Independence

variable A와 B가 독립적일 때는 다음과 같은 관계가 성립된다.

• P(A|B) = P(A)
• P(A,B) = P(A)P(B)

• P(B

  A) = P(B)

 

따라서 P(C1,…,Cn) 의 joint distribution을 계산하는 것은 간단하다.

\[P(C_1,...,C_n) = \prod_{i=1}^n P(C_i)\]

 

• Conditional Independence & Marginal Independence
  • Marignal independence
    • P(A=true|B=true) > P(A=true) 라면 이 경우는 marginally independent가 아니다.
    • 즉, A와 B는 P(A) = P(A|B) 일때만 독립적이어야 한다.
  • Conditional Independence
    • P(A=true|B=true, C=true) = P(A=true|C=true) 이면, conditional independent하다.

 

 

7-2. Bayesian Network

이전에 Naive Bayes Classifier을 배웠고, 이에 대한 function을 정의했다.

\[f_{NB}(x) = argmax_{Y=y}P(Y=y) \prod_{1 \leq i \leq d} P(X_i = x_i | Y = y)\]

bayesian network는 graphical notation 한 특성을 가지고 있다. 즉

• random variable
• conditional independence
• obtain a compact representation of the full joint distribution

에 대한 정보가 들어있다.

 

• Syntax(문법)

bayesian network는

• acyclic(사이클이 존재x), directed graph
• nodes
  • random variable
  • P(X_i| Parents(X_i)) (e.g. P(X1|Y))
• link
  • Direct influence from the parent to the child

네트워크의 구조는 conditional independence를 가정하고 있다.

즉, toothache(치통)과 stench(악취)는 충치(cavity)와는 관계가 있지만, weather과는 관계가 없다. 따라서 weather은 variable과는 독립적이고, toothache와 stench는 cavity와 conditionally independent하다.

 

유명한 예시를 하나 들어보자.

도둑(buglary)이 들거나, 지진(earthquake)이 발생했을 때, 알람(Alarm)이 울리는데, 알람이 울리면, 이웃인 John과 Mary가 전화를 하는 상황이다.

알람에 대한 확률은 P(A|B,E) 로 나타낼 수 있고, John이 전화하는 것에 대한 확률은 P(J|A), Mary가 전화할 확률은 P(M|A) 이다.

이 network에서의 Variable은 Burglary, Earthquake, Alarm, JohnCalls, MaryCalls, 모두이다.

 

정성적(Qualitative)인 요소로는

• 인과관계에 대한 사전정보
• 데이터로부터의 학습
• 네트워크의 구조

 

정량적(Quantitative)인 요소로는

• 조건부 확률 테이블(이미지에서의 우하단 표)

 

 

위의 구조는 간단했지만, 이러한 network를 복잡하게 구성할 수도 있다. 이럴 때, 지역적인 variable들에 대한 관계를 정의할 수 있다.

• Common parent
  • 동일한 parent variable을 가진 다른 variable에 대해서는 독립적이다. 즉, John이 전화할 확률과 Mary가 전화할 확률은 서로 독립적이다.
  • 𝐽 ⊥ 𝑀|𝐴
    • P(J,M|A) = P(J|A)P(M|A)
• Cascading
  • 연쇄작용으로서, 연결되어 있는 variable일 때, A가 주어졌다면, B와 M은 독립이다. mary가 전화할 확률은 A를 알고 있다면 B는 필요가 없다. 즉 direct influence에 대한 확률을 안다면 indirect influence variable과는 독립적이다.
  • B ⊥ M|A
    • P(M|B,A) = P(M|A)
• V-structure
  • B와 E는 공통의 child를 가지는 상황을 V-structure이라 하는데, A가 주어지지 않았다면, B와 M은 관계가 없으므로, 독립적이나, A가 주어진다면, B와 E는 관계가 생기는 것이므로 독립이 되지 않는다.
  • ~ (B ⊥ E|A)
    • P(B,E,A) = P(B)P(E)P(A|B,E)

 

이러한 복잡한 관계를 쉽게 이해하기 위해 Bayes Ball Algorithm 이라는 개념을 도입한다. 만약 $ X_A ⊥ X_B | X_C $ 를 확인하고자 할 때, 즉 X_C가 주어졌을 때, X_A와 X_B가 독립인지에 대해 판단하고자 할 때 사용할 수 있다.

공을 굴린다고 생각해서, 만약 방향이 -> 일 때, 오른쪽 variable이 주어진다면(회색) 공이 굴러가지지 않고, variable이 주어지지 않는다면(무색) 굴러갈 수 있다. 반대로 방향이 <- 이라면, 오른쪽 variable이 주어졌을 때는 굴러가지고, variable이 주어지지 않았을 때는 굴러갈 수 없다.

 

위의 local structure들에 적용해보자.

• Common parent

두 개의 variable이 공통의 한 개 parent를 가지는데, parent가 주어진다면, 공이 굴러갈 수 없으므로 이 두 variable은 독립적이고, 주어지지 않는다면, 독립이 아니다.

 

• Cascading

세 개의 variable이 연속적으로 존재하는데, 중간의 variable이 주어진다면, 나머지 두 개의 variable은 공이 굴러갈 수 없어서 독립이고, 주어지지 않는다면, 공이 굴러갈 수 있으므로 독립이 아니다.

 

• V-structure

두 개의 variable이 공통의 한 개 child를 가지는데, child가 주어진다면, V-structure은 common parent와 반대로, 공이 굴러 갈 수 있어서 두 variable은 독립이 아니다. 그러나 주어지지 않는다면 공이 굴러갈 수 없어서 독립이다.

 

간단한 예시를 들어보자.

x1~x6의 variable이 존재하고, 위와 같은 관계로 형성되어 있다고 해보자.

1. x2가 주어졌을 때, x1과 x4의 관계 (x1 ⊥ x4 | x2)

x2가 주어졌을 때, x1과 x4는 x2 방향으로는 cascading구조이므로 지나갈 수 없다. x3방향으로 지나간다 하더라도, x1과 x6는 v-structure구조이므로 지나갈 수 없다.

따라서 x1과 x4는 독립이다.

 

1. x1이 주어졌을 때, x2와 x5의 관계 (x2 ⊥ x5 | x1)

x1이 주어졌을 때, x2와 x5는 v-structure 구조이므로, x6가 주어졌을 때만 지나갈 수 있다. x1방향으로 지나간다 하더라도, common parent 구조이므로 x1이 알려져 있지 않아야 지나갈 수 있다.

따라서 x1가 주어졌을 때는 x2와 x5는 독립이다.

 

1. x2,x3가 주어졌을 때, x1과 x6의 관계 (x1 ⊥ x6 | {x2,x3})

x2와 x3가 주어졌을 때, x1과 x6는 x2방향으로는 cascading 구조이므로 x2가 주어졌을 때는 지나갈 수 없다. x3방향으로 지나간다 하더라도, cascading 구조이므로 x3가 주어졌을 때는 지나갈 수 없다.

따라서 x2와 x3가 주어졌을 때는 x1와 x6는 독립이다.

 

1. x1,x6가 주어졌을 때, x2와 x3의 관계 (x2 ⊥ x3 | {x1,x6})

x1과 x6가 주어졌을 때, x2와 x3는 x1방향으로는 common parent 구조이므로 x1이 주어졌을 때는 지나갈 수 없다. x6방향으로 지나간다 하면, x2와 x5가 v-structure 구조이고, x6가 주어졌으므로 지나갈 수 있고, x6,x5,x3가 cascading 구조인 상황에서 x5가 주어지지 않았으므로 x3로 도착할 수 있다.

따라서 x1와 x6가 주어졌을 때는 x2와 x3는 독립이 아니다.

 

 

이러한 bayes ball algorithm을 활용하여 다양한 기법을 정의할 수 있다.

1. Markov Blanket

A라는 특정 variable이 bayesian network안에 존재한다고 할 때, 주변 특정 관계에 있는 variable만 알면, 나머지의 variable에 대해서는 conditional independent하다.

특정 관계에는 parents, children, children’s other parents 이다.

• parents -> cascading 관계에 있는 variable과 관련
• children -> cascading 관계에 있는 varable과 관련
• children’s other parents -> v-structure 관계에 있는 variable과 관련

 

 

1. D-Seperation(directly-seperated)

• Y가 주어졌을 때, Z와 X는 d-seperated 이다. (X ⊥ Z | Y)

 

 

bayesian network가 있을 때, 이러한 joint probability를 구할 때, conditional independent 를 고려하면 다음과 같이 단순화할 수 있다.

\[P(X) = \prod_i P(X_i | X_{\pi_i})\] \[P(X1,X2,X3,X4,X5,X6,X7,X8) = P(X1)P(X2)P(X3|X1)P(X4|X2)P(X5|X2)P(X6|X3,X4)P(X7|X6)P(X8|X5,X6)\]

이렇게 나타낼 수 있는 이유는 joint probability와 conditional probability의 관계와, cascading, common parent 등의 구조로 인해 가능하다.

 

오른쪽과 같이 $ \mu $ 와 $ \sigma $ 의 공통의 parent를 가지는, X 들이 있다고 하면, 사각형의 공간을 만들어 간단하게 표현할 수 있다. 수식도 간단하게 나타낼 수 있다.

\[P(D|\theta) = P(X_1,...,X_N|\mu, \sigma) = \prod_N P(X_1|\mu, \sigma)\]

 

 

7-3. Inference on Bayesian Networks

1. Likelihood

모든 variable, X = {X_1,…,X_N} 이 있을 때, X는 $ X_H$ 와 $ X_V $ 로 나눌 수 있다. $ X_V $는 evidence variable, 즉 관측된 variable이고, $ X_H $ 는 hidden variable, 즉 관측하지 않은 variable이다.

evidence value, $ x_V $ 에 대한 확률(Likelihood)은 다음고 같다.

\[P(x_V) = \sum_{X_H} P(X_H, X_V) = \sum_{x_1} \dots \sum_{x_k} P(x_1, ..., x_k, x_V)\]

bayesian network와 conditional probability table이 존재하면, Joint Probability를 구하는 것이 가장 적합하다. 따라서, 구하고자 하는 것이 아닌 X_H에 대해 marginalization을 수행하여, X_H에 대한 관계를 모두 포함시킨다.

도둑과 지진에 대한 알람 task에서의 P(X_H, X_V) 는 다음과 같다.

\[P(X_H, X_V) = P(B)P(E)P(A|B,E)P(M|A)P(J|A) = P(B,E,A,M,J)\]

 

2. Conditional Probability

B와 M에 대해 주어졌을 때 알람의 conditional probability를 구해보자. hidden variable을 또다시 2가지로 세분화할 수 있다.

X_H = {Y,Z}

• Y : 관측이 되지 않았지만, 관심은 있는 variable (interested hidden variable)
• Z : 관측도 되지 않았고, 관심도 없는 variable (uninterested hidden variable)

B와 M은 관측이 되었으므로 X_V에 해당하고, A에 대해 구하고 싶으므로, Y는 A, 나머지는 Z에 해당한다.

그래서 관측된 variable들에 대한 interested hidden variable에 대한 식은 다음과 같다.

\[P(Y|x_V) = \sum_z P(Y, Z=z | x_V) = \sum_z \cfrac{P(Y, Z, x_V)}{P(x_V)} = \sum_z \cfrac{P(Y, Z, x_V)}{\sum_{y,z} P(Y=y, Z=z, x_V)}\]

full joint로 만들기 위해 Z를 삽입하고, P(x_V)에 대해서는 앞서 정의했으므로, x_V 가 주어졌을 때의 Y의 conditional probability는 위와 같다.

 

3. Most Probable Assignment

마지막으로, P(Y

x_V)가 최대가 될 파라미터를 구할 수 있다. ( $argmax_a P(A|B=true, M=true)$)

만약 P(A|B,E) 에 대한 posteriori를 구하면, prediction task에 해당하고, 반대로 P(B,E|A)에 대한 posteriori를 구하면 diagnosis task가 된다.

 

 

joint probability를 구하는 것이 중요한데, 이를 구하기 위해서는 너무 많은 곱셈과 덧셈이 존재한다.

\[P(a = true, b=true, mc=true) = \sum_{JC}\sum_{E} P(a,b,E,JC,mc) = \sum_{JC} \sum_{E} P(JC|a)P(mc|a)P(a|b,E)P(E)P(b)\]

 

조금 더 간단하게 구할 수 있는 방법은 없을까? 이러한 확률(P)를 함수의 형태로 생각해보자. 소문자가 evidence variable, 대문자가 hidden variable에 대한 값이다.

\[P(e,jc,mc,B,A) = P(e)\sum_B P(b)\sum_A P(a|b,e)P(jc|a)P(mc|a) => f_E(e)\sum_B f_B(b) \sum_A f_A(a,b,e) f_J(a) f_M(a)\]

MC에 대한 함수 $ f_m $ 와 JC에 대한 함수 $ f_j $ 를 곱해서 $ f_{JM} $ 을 만들 수 있다.

 

그리고, $ f_A $ 와 $ f_JM $ 을 결합하고, A에 대해 marginalization을 수행하게 되면, $ f_{\bar{A}JM}(b,e) $ 가 된다. 이렇게 계속 단순화시키면, $ f_E\bar{B}\bar{A}JM(e) $ 를 만들어 낼 수 있다.

 

 

이번에는 간단한 bayesian network인 A <- B <- C <- D 를 정의하고, 이에 대한 full joint를 구하면,

$ P(A,B,C,D) = P(A|B)P(B|C)P(C|D)P(D) $

가 된다. 이 때, A,B,C,D에 대한 network를 다르게 표현하고자 한다. clique와 separator 개념을 사용하여, 노드(clique)를 A,B/B,C/C,D 로 구성하고, 그 사이에 링크(separator)를 B,C 로 정의한다.

그리고나서, potential function 을 정의한다.

• potential function on nodes

\[\psi(a,b), \psi(b,c), \psi(c,d)\]

• potential function on links

\[\phi(b), \phi(c)\]

 

그 후, potential function을 활용하여 P(A,B,C,D)를 정의한다. 정의하는 방법에는 2가지가 있다.

1. $ P(A,B,C,D) = \cfrac{\prod_N \psi(N)}{\prod_L \phi(L)} = \cfrac{\psi(a,b)\psi(b,c)\psi(c,d)}{\phi(b)\phi(c)} $

• ψ(a,b) = P(A|B), ψ(b,c) = P(B|C), ψ(c,d) = P(C|D)P(D)
• φ(b) = 1, φ(c) = 1

 

1. $ P(A,B,C,D) = \cfrac{\prod_N \psi(N)}{\prod_L \phi(L)} = \cfrac{\psi(a,b)\psi(b,c)\psi(c,d)}{\phi(b)\phi(c)} $

• ψ(a,b) = P(A,B), ψ(b,c) = P(B,C), ψ(c,d) = P(C,D)
• φ(b) = P(B), φ(c) = P(C)

 

 

위의 potential function을 clique graph를 적용하게 되면

• P(B) = $ \sum_A \psi(A,B) $
  • A에 대해 marginalization을 수행하면 P(B)가 된다.
• P(B) = $ \sum_C \psi(B,C) $
• P(B) = φ(B)

이 때, 만약 A가 관찰된다면, $ \phi(B) $ 값도 바뀔 것이고, 그렇다면, 그 뒤에 있는 B,C/C/C,D 에 대한 것들도 모두 바뀌게 된다. 이를 belief propagation이라 한다.

 

belief를 전파(propagation)하기 위해서는 Absorption(update) rule 을 적용해야 한다. update된 separator와 update된 clique를 다음과 같이 정의한다.

• φ^(B) = $ \sum_A \psi^(A,B) $
• ψ^(B,C) = $ \psi(B,C)\frac{\phi^(B)}{\phi(B)} $

 

이렇게 정의가 되면, 다음과 같이 적용된다.

이를 local consistency, 지역적 일관성이라 한다.

 

 

이제 실제 예제에 적용할 것인데, 우리는 conditional probability는 알고 있지만, joint probability는 모르는 상태이므로, 일전에 정의했었던 P(A,B,C,D)에서 conditional probability를 활용한 방식을 사용할 것이다.

 

1. P(b) 를 구해보자.

• $ \phi^*(b) = \sum_a \psi(a,b) = 1 $
  • absorption rule을 수행할 때, φ*(b)를 구하기 위해서 a에 대해 marginalization을 하면 된다.
  • 이렇게 되면, 모든 case에 대한 확률이 되므로 1이 된다.
• $ \psi^(b,c) = \psi(b,c)\frac{\phi^(b)}{\phi(b)} = P(b|c)P(c) \times 1 = P(b,c) $
  • 앞서 ψ*에 대해 정의했으므로 그대로 정의하고, 위에서 b separator에 대한 값은 둘다 1.
  • conditional probability의 정의에 따라 joint probability로 정의된다.
• $ \phi^{**}(b) = \sum_c \psi(b,c) = \sum_c P(b,c) = P(b) $
  • 이번에는 B,C 에서 A,B로 진행해본다.
  • 동일하게 c에 대해 marginalization을 수행하여 apsorption rule이 적용된 b를 계산한다.
• $ \psi^(a,b) = \psi(a,b)\frac{\phi^{**}(b)}{\phi^(b)} = \frac{P(a|b)P(b)}{1} = P(a,b) $
  • ψ*에 대해 앞서 정의했으므로, 그대로 정의하여 사용한다.
• $ \phi^{**}(b) = \sum_a \psi^(a,b) = P(b) $
  • A,B에서 B,C로 한번 더 진행해보면 동일한 값이 나오는 것을 확인할 수 있다.

 

1. P(b|a=1,c=1) 를 구해보자.

관측이 있는 상태에서 알지 못하는 variable에 대한 확률을 구하고, 추가로 확률이 최대가 되는 값을 찾는 것이 중요하다.

• $ \phi^*(b) = \sum_a \psi(a,b) \delta(a=1) = P(a = 1|b) $
  • 동일하게 a에 대해 marginalization을 수행하지만, a=1이라는 관측이 이미 있었으므로 a=1일 때의 값만 사용한다.
  • 이로 인해, 모든 case라서 나온 1이 아닌, a=1일때의 확률
• $ \psi^(b,c) = \psi(b,c)\frac{\phi^(b)}{\phi(b)} = P(b|c=1)P(c=1)\frac{P(a=1|b)}{1} $
  • 앞서 absorption rule에서 정의한 것을 사용하되, c=1이라는 관측이 있었으므로 이로 제한하여 사용한다.
• $ \phi^{**}(b) = \sum_c \psi(b,c) \delta(c=1) = ψ^*(b,c) = P(b|c=1)P(c=1)P(a=1|b) $
  • B,C에서 A,B로 진행하므로 φ**는 c를 marginalization을 수행한 것과 단다. 따라서 위에 것이 그대로 내려온다. «««< HEAD:_posts/Classlog/KOOC/2022-10-15-kooc_week7.md
• $ \psi^(a,b) = \psi(a,b)\frac{\phi^{**}(b)}{\phi^(b)} = P(a=1|b) \frac{P(b|c=1)P(c=1)P(a=1|b)}{P(a=1|b)} = P(b|c=1)P(c=1)P(a=1|b) $
  • absorption rule에서 정의한 것을 그대로 사용한다.
• $ \phi^{***}(b) = \sum_a \psi^*(a,b) \delta(a=1) = P(b|c=1)P(c=1)P(a=1|b) $
  • A,B에서 다시 B,C로 이동을 시켜보면 동일한 값이 나온다는 것을 알 수 있다.

이렇게 구해진 seperator로 P(b|a=1,c=1) 를 구할 수 있다.