Belief Propagation 알고리즘

한 때, 병렬 그래프 연산과 알고리즘에 심취한 적이 있다. 그중에 신뢰 전파(Belief Propagation) 알고리즘에 대해 적어본다. 이 알고리즘은 Graphical model에서 inference problem의 근사해를 추정하는 기법으로, Graph 상에 관측된 특정한 확률변수의 분포가 주어졌을 때, 직간접적으로 영향 받는 모든 관측되지 않은 확률 변수의  Marginal distribution을 추정하는 기법이다.

즉, 아래와 같은 Poly Tree 구조 안에 C 노드와 E 노드가 Evidence가 주어졌을 때, \( P(B|C,E) = ? \)



알고리즘은 각 노드 간 Down or Upward Message Passing과 Data Fusion 단계를 거쳐 각 노드의 확률 분포를 추정하기 때문에 병렬 연산을 위해서 Bulk Synchronous Parallel 모델이 대단히 적합하다 할 수 있다.

문득, Google의 DistBelief는 이러한 분산 베이지안 네트워크의 메시지 전달 방식이라 지어진게 아닌가 싶다. 그나저나 요즘의 나는 트리 탐색 구현 정도나 할 수 있을까 모르겠네?

No comments:

Post a Comment

무한의 세계

무한 집합의 크기 Cardinality , 즉 원소의 개수를 수학에서는 '농도'라고 말한다. 유한 집합의 크기는 그대로 원소의 개수 이지만, 무한 집합의 경우는 원소의 개수를 낱낱이 셈하는 것은 불가능하기 때문에 '농도'라...