[ML개론] (20) Bayes Ball Algorithm & Factorization

앞서 살펴본 Bayesian Network의 목적은 joint probability를 계산하기 위해서다. 그럼 node들간의 관계를 나타내는 Bayesian Network를 활용하여 joint probability 계산을 더욱 쉽게 해보자. 

 

우선 Bayes Ball Algorithm을 논하기에 앞서 Markov Blanket 개념을 알아보자. 

Markov Blanket이란 특정 node A에 대해 해당 node의 확률분포를 알기 위해서 필요한 최소한의 node집합을 뜻한다. 가령 node A를 알기 위해선 최소 A의 parent node, child node, child's other parent node가 필요하다. 따라서 node A 인근의 여타 node들의 집합을 markov blanket이라 명명하고, 그 정의에 의해 P(A|Blanket, B) = P(A|Blanket)임을 알 수 있다. A의 확률을 알 수 있는 최소한의 집합이니 이들에 대한 정보가 주어지면 A와 Blanket 밖의 node B는 서로 conditional independent하다. 

 

D-Seperation의 개념 또한 이와 같다. Y blanket 내부의 X node는 blanket 밖의 node Z와 conditional independent하다는 내용이다. 

 

정의에 의한 conditional independence 관계는 알겠으나 이것이 실제로 어떤 방식으로 그리 구현되는지에 대한 논리적 이해는 부족하다. 따라서 Bayes Ball Algorithm을 알아보며 이것이 왜 conditonal indepenent한지 알아보자. 

첫째, P(X4|X2,X1)=P(X4|X2)인가? 즉 X4와 X1은 서로 independent한가? 우선 evidence로 X2가 주어졌기 때문에 

cascading 구조에 의해 X1과 X4는 서로 조건부독립의 관계에 놓인다. 그러나 X1-X3를 통한 message passing을 살펴야한다. X1-X3-X5-X6까지 cascading에 의해 조건부독립인 node는 없다. 그러나 X5-X6-X2의 V-structure에서는 X6가 알려져야 message passing이 가능한데 X6에 대한 확률분포 정보가 없으니 X4로 message passing이 불가하다. 따라서 X1과 X4는 양방향으로 conditional independent하다. 

둘째, P(X2|X1) = P(X2, X5|X1)인가? common parent 구조에서 X1이 알려졌으니 X2와 X3는 서로 independent하다. X2-X6-X5-X3로 연결되는 path도 한번 생각해보자. 이 경우엔 X6가 알려져야 X2와 X5가 서로 dependent해지는데 X6에 대한 정보가 없으니 X2-X6-X5-X3 모두 independent한 관게에 놓인다.

셋째, P(X1, X6|X2,X3) = P(X1|X2,X3)인가? X1과 X6를 연결하는 양방향의 path는 X1-X2-X6, X1-X3-X5-X6의 cascading 밖에 없는데 path 가운데 node에 대한 정보가 알려져있으니 X1과 X6은 서로 independent하다. 

넷째, P(X2, X3|X1, X6) = P(X2|X1,X6)인가? X2와 X3는 X2-X1-X3의 common parent, X2-X6-X5-X3의 cascading과 V-structure가 결합된 구조로 연결되어있다. 우선 common parent의 경우 X1이 주어져있기에 둘은 independent해진다. V structure의 경우 공통된 자식인 X6에 대한 정보가 주어졌기 때문에 X2와 X5는 서로 dependent하며, X5와 X3는 cascading에 의해 dependent하기 때문에 X2와 X3는 dependent하다. 

이러한 구조로 구성된 markov blanket은 결국 message passing이 불가한 말단의 node가 경계를 이룬다. 

 

node의 수가 많아지면 parameter가 많아짐을 뜻하고, 이는 곧 Joint Probability의 원소가 많아짐을 뜻한다. 이 때문에 우리는 conditional prob을 활용하여 정보전달의 기능이 없는 conditional independent한 parameter를 축출한다. 

가령 P(X1,X2,X3)=P(X1|X2,X3)P(X2|X3)P(X3)로 표현될텐데 Bayesian network 상 given X2, X1와 X3가 conditionally independent하다고 가정해보자. 그럼 P(X1,X2,X3)=P(X1|X2)P(X2|X3)P(X3)로 X3 원소를 하나 줄일 수 있게 된다. 

 

mu, sigma를 공유하는 Xi node들에 대해 plate notation을 활용하여 표기한다. N개만큼 node를 그리기엔 손아프니까 문법상 plate 내부에 Xi를 하나만 표기한뒤 i=1~N으로 표현한다.