Week 7.9 Simple Example of Belief Propagation

1. Potential funtion을 initializing 해보자

- Joint Probability는 모르는데 Conditional Probability는 알수 있다. 이것을 통해 Potential function을 초기화해보자.

그림.1

예제1 ) P(B) 에 대해 한번 알아보자.

Φ(B)를 지난 강의시간의 Absorption rule을 활용해 알아보자.

a에대해 marginalization out하면 모든 a에 대해 summation때문에 1이다.

 

그럼 Φ(B)(그림.1의 2)가 업데이트되었기때문에 Ψ(B,C)(그림.1의 3)를 업데이트 한번해보자.

그러면 P(b,c)에서 c에 대해서 marginalization out 하게되며 Φ*(B)가 나와야하는데, 안나온다.

왜냐면 우측(그림.1의 3)은 P(b,c)는 joint probabilty이고 , 왼쪽(그림.1의 1)은 Conditional probability로 초기세팅하여 ㅣlocal structure가 맞지 않다. 그래서  belief propagation을 이용해서 local consistency를  maintain해야한다.

이제 그림.1의 3을 왼쪽으로 propagation 해야한다.

즉 Φ*(B)를 또 업데이트하여 Φ**(B)가된다. c에 대해 marginalization out 하게되면 P(b)가 나오게된다.

 

이제는 Φ**(B) 를 통해 Ψ(B,C)를 Ψ*(B,C)로 업데이트 하자.

처음의 초기 시작은  알고 있는 정보를 활용한 Conditional probability 로 시작하였다. 이것을 belief propagation을 몇번 거치고 나니 , Joint probability형태로 만들어 지게 되었다. 

 

이제 Φ***(B) 로 업데이트를 해보면 P(b)가 나오는것을 알수 있다.

즉 belief propagation을 몇번 왔다갔다 하니깐 Φ**(B) = Φ***(B) = P(b) 임을 알수 있다. 즉 local consitency를 maintain 하고 있다. 더 이상 안변한다는 의미이다.

 

그러면 Most probable assignment에 대해 한번 알아보자. Conditional Probability를 이용하면된다. 관측이 있는 상황에서 우리가 알지 못하는데 , 관심있는 Hidden variable에 대한 assignment에 대해 알아보자. 

 

예제2 ) P(b|a=1, c=1) 에 대해 한번 알아보자.

a, c에 대한 관측이 있는 상황에서 b에 대한 확률을 알아보는것이다.

 

예제1의 문제에서는 Ψ(a,b)로 썻던 부분을 Ψ(a,b)δ(a=1)로쓰게 된다. 이것의 의미는 a가 1인 상황에서만의 Potential function(Ψ(a,b))만을 활용하겠다는 의미이다.

δ(a=1) 에 대해 좀더 자세히 알아보면 delta function 은 dirac delta function 라 하고 괄호 안의 condition일 경우엔 1이라는 값을 갖고 그 외의 경우에는 0이라는 값을 갖는 함수이다.

 

이제 우측으로 업데이트를 시키면 아래와 같이 된다. 아래도 관측치가 된것을 제약조건으로 변경하게 된다. ( P(b|c=1)*P(c=1) 부분)

다시 한번 belief propagation 에 의해 차례로 update 해보자.

 

즉  Φ**(B) = Φ***(B) 가 동일하기때문에 ocal consitency를 maintain 하고 있다고볼 수 있다.

P(b|c=1)P(c=1)P(a=1|b) 중 모르는 값이 없기 때문에 , P(b)를 계산할 수 있다.

 

즉 Belief propagation 을 통해서 확률의 계산을 좀더 효율적으로 할 수 있게 된다.