[ML개론] (23) Potential Function & Belief Propagation Algorithm

normalized되지 않았다든지의 이유로 PDF가 아닌 함수를 potential function이라 부른다. 가령 P(A,B,C,D)=P(A|B)P(B|C)P(C|D)P(D)와 같이 PDF이기에 factorization될 수 있는 node들이 존재하는 반면, potential fn이기에 위와같이 표기되지 못하는 함수들이 존재한다. 이는 NN에 있어 치명적인데, NN의 output값이 확률의 형태, 즉 0과 1 사이의 값이어야만 하는데 만일 적분값이 1이 되지 못한다면 이는 softmax를 통해 normalize 작업을 거쳐야 비로소 활용된다. 즉 potential fn의 형태로 weight을 곱하고 ReLU 등을 거치고 최종적으로 이를 normalize해주어 확률값을 도출해내는 것이다. 그 과정에서 potential fn이 활용된다. 

 

potential fn은 다음과 같이 활용된다. P(A,B,C,D)가 clique와 seperator의 함수로 표현되어야만 한다면, clique 함수 곱이 분자에 seperator 함수 곱이 분모에 위치해야 한다. 그럼 이를 P(A,B,C,D)=P(A|B)P(B|C)P(C|D)P(D)와 matching시키기 위한 작업이 필요하다. 가령 위 그림의 첫번째 사례와 같이 그대로 대입하는 경우가 있다. 또한 joint prob.과 conditional prob.의 관계를 활용하여 우회적인 방식으로 P(A|B)...의 형태를 만드는 경우도 있다. 

 

우리는 Potential fn을 활용하여 Absoprtion rule을 사용할 수 있다. 만약 이전의 clique graph와 같이 (A,B)-B-(B,C)로 엮인 clique graph가 존재한다고 가정해보자. 이들은 potential fn의 형태로 존재하기 때문에 정확한 PDF를 모른다. 이런 상황에 놓여있을 때 활용하는 것이 absoprtion rule이다.

만약 Ψ(A,B)=P(A,B), Ψ(B,C)=P(B,C), ∅(B)=P(B)로 설정했을 때, 우린 P(B)를 Ψ(A,B)를 A로 marginalize out해준 함수, Ψ(B, C)를 C로 marginalize out해준 함수, P(B)=∅(B)라고 생각할 수 있다. 이 때 P(A=1,B)라는 관측치가 생겼다면 우리의 psi fn은 belief를 전후로 전달하면서 이전에 추정한 psi_fn을 업데이트하며 추정한다. 

 

만약 Ψ(A=1,B)과 같이 기존 Ψ(A,B)에서 새로운 관측이 발생했다면, 이를 seperator fn ∅*(B)으로 belief를 propagate하여 update할 수 있다. 이 때 업데이트된 seperator fn은 ∅*(B)= Σ_a Ψ*(A,B)와 같이 정의된다. updated seperator fn을 통해 seperator를 공유하는 psi_fn도 업데이트된다. 이 때 Ψ*(B,C)=Ψ(B,C) * (∅*(B)/∅(B))과 같이 정의된다. 

 

앞서 말했듯이 새로운 observation이 기존에 추정해둔 함수의 추정에 영향을 주면서 업데이트가 진행된다. 

clique에 대한 update rule은 Σ_c Ψ*(B,C) = Σ_c Ψ(B,C) * (∅*(B)/∅(B))로 정의된다고 했는데, Ψ(B,C)=P(B,C)라는 점에서 Σ_c Ψ(B,C)는 P(B)이며, ∅(B)=P(B)이기 때문에 ∅*(B)가 최종적으로 살아남는다. 그럼 ∅*(B)=Σ_a Ψ*(A,B)이기 때문에 Σ_a Ψ*(A,B)=Σ_c Ψ*(B,C)=∅*(B)가 되며 이는 맨 처음에 설정한 P(B)와 같다. 

 

그럼 clique graph에서의 absoprtion rule을 활용한 belief propagtation을 살펴보자.

P(A|B), P(B|C)는 주어졌을 때 P(B)는 무엇일까? 

우선, potential fn을 Ψ(A,B)=P(A|B), Ψ(B,C)=P(B|C)P(C), ∅(B)=1로 가정한다. 

둘째, ∅*(B)=Σ_a Ψ(A,B) = Σ_a P(A|B) = 1로 seperator update

셋째, Ψ*(B,C) = Ψ(B,C) * (∅*(B)/∅(B)) = P(B|C)P(C) = P(B,C)로 clique update

넷째, ∅**(B) = Σ_c Ψ(B,C) = Σ_c P(B,C) = P(B)로 seperator update

다섯, Ψ*(A,B) = Ψ(A,B) * (∅**(B)/∅*(B)) = P(A|B)P(B) = P(A,B)로 clique update

여섯, ∅***(B) = Σ_a Ψ*(A,B) = P(B) : 이 때 local consistency maintained, update 종료

 

그럼 최종적으로 P(A|B)-1-P(B|C)P(C)로 추정했던 potential fn이 P(A,B)-P(B)-P(B,C)로 업데이트 되었음을 알 수 있다. 

 

아무래도 belief propagation은 most probable assignment, 즉 observation이 있을때 우리가 알지 못하는 hidden variable에 대한 추정에 유용하다.

첫째, ∅*(B)=Σ_a Ψ(A,B) = Σ_a P(A|B)δ(A=1)=P(A=1|B)이 된다. δ(A=1)은 A=1일 때 1, 아니면 0을 반환하는 함수로, 이전에는 A로 marginalize out하면 1이 도출되던것과 달리 이젠 P(A=1|B)만 도출된다. 

둘째, Ψ*(B,C) = Ψ(B,C) * (∅*(B)/∅(B)) = P(B|C=1)P(C=1)P(A=1|B)로 clique가 update된다.

셋째, ∅**(B) = Σ_c Ψ*(B,C)δ(C=1) = P(B|C=1)P(C=1)P(A=1|B)로 update

넷째, Ψ*(A,B) = Ψ(A,B) * (∅**(B)/∅*(B)) = P(A=1|B) * (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)

다섯은 local consistency가 maintained되기 때문에 update를 멈춘다. 

 

이럼 P(B)를 기존에 알고있던 conditional prob.인 P(B|C=1)P(C=1)P(A=1|B)로 구할 수 있게 된다.