Overview

Belief Propagation은 전체 결합확률을 직접 계산하지 않고 변수 간에 정보를 전달하여 필요한 posterior probability 또는 marginal probability를 효율적으로 계산하는 방법이다.

Message Passing

Message Passing은 그래프의 노드들이 이웃 노드에게 자신의 정보를 함수 형태의 메시지로 전달하고, 전달받은 메시지를 이용하여 확률적 추론을 수행하는 방법이다.

$X_1 - X_2 - X_3$

이 그래프에서 $X_1$은 $X_2$를 통해 $X_3$와 연결되어 있다. 이때, 복잡한 $P(X_1, X_2, X_3)$를 한번에 계산하는 것이 아니라 $X_1$에서 $X_2$로, $X_2$에서 $X_3$로 전달되는 정보를 message를 통해 단순하게 계산할 수 있다.

Message

Message는 한 노드가 다른 노드에게 전달하는 확률적 정보이다.

• 수학적 표현

  $m_{1→2}(x_2)$

  • $x_1$이 $x_2$에게 보내는 메시지

Belief Propagation

Belief Propagation(BP)은 특정한 구조의 그래프에서 Message Passing을 이용하여 각 변수의 Marginal Distribution을 계산하는 알고리즘이다.

• Tree 구조에서는 정확하게 marginal probability를 계산할수 있지만, cycle이 있는 그래프에서는 정확한 추론을 보장하지 않는다.

Sum-Product Algorithm

Sum-Product Algorithm은 Belief Propagation에서 일반적으로 사용하는 알고리즘이다.

다음 Factor Graph가 있을 때,

$X_1 - f_1 - X_2 - f_2 - X_3$

두 종류의 메시지가 존재한다.

1. Variable → Factor: 자신에게 들어온 다른 모든 메시지를 곱해서 전달

   $\displaystyle m_{X → f}(X) = \prod_{g \in N(X)\backslash f} m_{g → X}(X)$

   • $N(X)$: $X$와 연결된 factor들의 집합

2. Factor → Variable: 다른 변수들의 상태를 모두 합하여 $X_i$에 대한 정보를 만듦

   $\displaystyle m_{f → X}(X) = \sum_{\bold x_{N(f)\backslash X}} f(\bold x_{N(f)}) \prod_{Y \in N(f)\backslash X} m_{Y → f}(Y)$

3. 최종 Belief 계산

   $\displaystyle b(X) \propto \prod_{f \in N(X)} m_{f→X} (X)$

   $\displaystyle \therefore P(X=x) = \frac {b(x)} {\sum_{x'}b(x')}$