Week 7.8 Potential Function and Clique Graph

Belief 가 Propagation 되는 형태를 유사하게 활용해서 우리가 원하는 확률값을 찾아내는 내용이다.

1. Potential Function

Potential Function은 PDF(Probability Distribution Function)을 만들고 싶지만 아직 몇가지 조건이 부족하여

PDF는 아니지만 PDF가 될 잠재력을 가진 함수라 한다.

 

아래의 Bayesian Network에서  예를 들어보자.

우선 Bayesian Network에서 아래와 같이 구조적으로 정의할수 있다.

1. Clique : 전체Bayesian Network에서 Fully connected 된 subset

• AB가 하나의 Clique
• BC가 하나의 Clique
• CD가 하나의 Clique

 

2. Separator : Clique Node 사이의 공동의 random variable

 

이제 Potenctial function 을 정의 해보겠다. 2가지 방법으로 해보겠다. 아래의 방법은 임의로 정한것이다.

 

1. Clique 마다 Potential function 을 정의

2. Link 마다 Potential function 을 정의 

 

Full joint Probability가 Potential function 을 이용해 어떻게 표현되는지 알아보자. 아래와 같이 표현될수 있는데

[식 1]

어떻게 이렇게 되는지 2가지 방벙으로 알아보겠다.

 

아래의 식 두개( [식2], [식3])를 동일하게 만들려고 조작해보자

[식 2]

 

[식 3]

1. 아래와 같이 set up 하면 위의 [식 1]이 만족한다.

 

2. 이번에는 아래와 같이 joint probability 형태로 set up 하고 위의 [식 1]이 성립함을 증명해보자.

[식 3]을 위의 set up을 이용하면

 

P(A,B) X P(B,C) X P(C,D) / P(B) X P(C) = P (A|B) X P(B|C)XP(C|D)XP(D) 가 된다.

 

여기서의 문제점은 실제는 우리가 가진 정보는 Conditional probability 정보이다.

Joint probability 정보는 가지고 있지 않다.

 

2. Absorption in Clique Graph

Clique Graph에서의 absorption 의 operation을 알아보자. (확률에 대한 Inference를 할수 있다.)

 

 

1. Potential funtion을 잡아보자.

 

2. ψ가 Observation 에 의해 바뀐다고하면 변경된 ψ는 뒤의 ψ에도 영향을 준다. 

쉽게 설명하면 Potential function P(A,B)에서 A가 관측되어 (Observation ) B가 바뀐다. 즉 Clique ψ(A,B)가 바뀌게 되어  Separator B에도 영향을 준다. 그럼 또 Separator B가 변경되어 뒤의 Clique ψ(B,C)가 변경되고 뒤로 계속 쭉쭉 전파된다.

 

이것을 Belief Propagation 이라 한다. (Observation 이 Clique를 통해 Propagation 한다는 의미)

위의 그림에서 P(A,B) 가 있었다치고, A가 관측되어 P(A=1,B)로 변경되었다고 해보자. 그럼 Clique ψ(A,B)가 변경되고 Seperator B는 marginalization 해서 아래와 같이 바뀌게 된다.

그리고 뒤의 Clique ψ(B,C)는 아래 식을 통해 변경된다.(뒤에 star 가 붙게 된다.)

 

 

그러면 Belief는 어떻게 Propagation 하는지 알아보자.

이것은 Absorption rule을 통해 수행하게된다.

Observation 에 의해 새로이 변경된 Clique와 Separator를 *를 붙여 표현해보자.

그리고 새로 update 되는 Potential function 에 대해 아래와 같이 정의를 내린다.

그러면 아래의 식을 만족하게 되어 , Belief가  ψ(A,B) 에서 ψ(C,D)까지 영향을 줄수 있게 된다.