Week 7.4 Bayes Ball Algorithm (베이즈볼)

1. Typical Local Structures

 

Bayesian Network는 어떻게 설정하냐에 따라 거대한 구조로 만들수 있다.

지엽적인 관점에서 보면 Bayesian Network는 아래의 전형적인 Local 구조 3가지로 나눌수 있다.

 

1. Common Parent : Node들이 공통 Parent를 가진 경우

 

1) J ⊥ M | A 

P(A)가 given일때 (알람에 대한 특정 정보가 주어졌을때 ) , P(J)와P(M)은 독립이다. → A를 모르면 이렇게 구성할수 없다.

즉 P(J,M |A) = P(J|A) X P(M|A)

 

2. Cascading

1) B ⊥ M | A 

P(A)가 given일때 (알람에 대한 특정 정보가 주어졌을때 ) , P(B)와P(M)은 독립이다. 

→ P(M)은 B에 대한 정보는 필요없다. ( A의 정보를 아는 순간 P(B)는 P(M)에 전혀 상관없어진다.)

즉 P(M | B,A ) = P(M|A)

 

3. V - Structure : Parent가 Common child를 가진 경우

특정 정보(A)를 알면 둘사이(P(B)와 P(E))의 관계가 생겨 버린다. 

예) 알람이 울렸는데(P(A)에 대한 정보가 주어짐) 지진은 아니였다. 그럼 왜 울렸을까? 도둑에 의해 울렸다는것을 유추할수 있다.

그러면 알람이 울렸는지 안울렸는지 모른다고 하면(P(A)에 대한 정보가 주어지지 않음) , P(E)와 P(B)는 독립이다.

알람이 울렸다는 정보를 아는순간에 P(E)가 P(B)에 영향을 미치게 된다.

 

 

 

Cascading 은 P(A)가 관측되는 순간 P(B) 와 P(E)는 독립관계가 성립되고 , 

V - Structure는 P(A)가 관측되는 순간 P(B) 와 P(E)는 독립관계가 사라지게 된다.

 

2. Bayes Ball Algorithm 

Random variable A , B의 독립관계 파악을 위해 쓰인다.

독립관계를 알면 무엇이 좋을까? Joint Probability를 구할때 , Factorization 할때 Conditional Independent가 쓰이기 때문이다. ( 자세한 내용은 지난 강의 정리 내용 참조 - Link : Week7.2 Probability Theorems - Bayesian Network )

 

베이즈볼 알고리즘은 베이즈볼을 굴려서 A에서 B로 공이 굴러 가면 A와 B는 독립이 아니고

베이즈볼이 굴러가지 못하면 A와 B는 독립이다 라고 판단한다.

 

1) Cascading 구조의 Independent 한 경우

아래 가장 왼쪽 A , 가장 오른쪽을 B라하고 가운데를 C라 하자.

C가 관측되면 ( 정보가 주어지면 혹은 given일 경우) 원에 색을 칠하기로 하고 

A의 정보는 B에 아무런 영향을 주지 않는다. (위쪽에 설명함.)

 

즉 베이즈볼을 A에서 굴리면 B로 굴러가지 않는다. => A 와 B는 독립이다. 

아래 그림에서 빨간색 화살표는 베이즈 볼이 굴러갈수 없다는것을 의미한다.

2) Cascading 구조의 Independent 하지 않은 경우

 

C가 관측되지 않으면 A의 정보는 B에 영향을 준다.

즉 베이즈볼을 A에서 굴리면 B로 굴러간다. => A 와 B는 독립이 아니다. 

 

3) Common Parent 구조의 Independent 한 경우

C가 관측되면 A의 정보는 B에 영향을 준지 않는다.

즉 베이즈볼을 A에서 굴리면 B로 굴러가지 않는다. => A 와 B는 독립이다. 

 

4) Common Parent 구조의 Independent 하지 않은 경우

 

C가 관측되지 않으면 A의 정보는 B에 영향을 준다.

즉 베이즈볼을 A에서 굴리면 B로 굴러간다. => A 와 B는 독립이 아니다.

5) V - Structure 구조의 Independent 하지 않은 경우

 

C가 관측되면 A의 정보는 B에 영향을 준다.

즉 베이즈볼을 A에서 굴리면 B로 굴러간다. => A 와 B는 독립이 아니다.

6) V - Structure 구조의 Independent 한 경우

 

C가 관측되지 않으면 A의 정보는 B에 영향을 주지 않는다.

즉 베이즈볼을 A에서 굴리면 B로 굴러가지 않는다. => A 와 B는 독립이다. 

 

3. Markov Blanket

위의 베이즈볼 과 Typical local structure를 이해하고나면 Markov Blanket에 응용할수 있다.

 

A라는 Random variable이 Bayesian Network 안에 있다고 가정해보자.

아래의 12개의 random variable 중 주변 6개와의 관계를 알면 나머지와의 관계도 알수 있다는것이 Markov Blanket의 내용이다. 다시말하면 A가 Blanket안에 있는 random variable과 (아래 그림의 색깔 칠해진 동그라미들) Conditional Indepent 하면 Blanket 밖에 있는 random variable 과도 모두 Conditonal Independent 하다. 

 

Blanket 은 A기준으로 Parents , Childeren , Children's other parents 로 구성되어 있다.

아래 그림에서 1은 Parents , 2는 Children 3은 Children's other parents 이다.

 

 

1) Parenet 는 Cascading / Common parent 로 부터 오는 베이즈 볼을 막아준다.

    → A와 파란 원의 random variable과의 관계는  독립이다.

2) Children은 Cascading 으로 부터 오는 베이즈 볼을 막아준다. 

    → A와 빨간 원의 random variable과의 관계는  독립이다.

3) Children's other parent 가 필요한 이유는  만약 2가 관측되면 3으로 부터 베이즈 볼이 굴러올수 있기 때문에 (V-Structure 관계에 의해서) 3도 관측되어야 밖에 있는 Cascading 으로 부터 오는 베이즈볼을 막을수 있다.

    → A와 노란 원의 random variable과의 관계는  독립이다.