인자 그래프(factor graph)란 함수를 인수분해하여 나타내기 위한 이분(bipartite) 그래프이다. 예를 들어 다음과 같은 인수분해로 표현되는 분포를 생각해보자: $$p(x_1, x_2, x_3, x_4) = f_a(x_1, x_2) f_b(x_1, x_2) f_c(x_2,x_3) f_d(x_3).$$ 그래프로는 아래처럼 표현된다.

$x_1$, $x_2$ 등에 해당하는 노드들은 변수 노드(variable node), $f_a$, $f_b$ 등에 해당하는 노드들은 인자 노드(factor node) 혹은 함수 노드(function node)라고 불릴 것이다.

다음처럼 트리 구조를 가지는 인자 그래프를 생각해보자.

이때 $\mathbf{x} \equiv (x_1, x_2, x_3, x_4, x_5)$로 정의하면, $$p(\mathbf{x}) = f_a(x_1, x_2) f_b(x_2, x_3) f_c(x_3, x_4) f_d(x_3,x_5).$$ 이제 주변화(marginalization)를 통해 어떤 특정 변수, 예를 들어 $x_2$에 대한 분포를 알아내고자 한다. 그런데 트리의 특성상 $x_2$를 지우면 그래프는 두 조각으로 쪼개지게 되므로 그 성질을 이용해서 식을 나누어 적을 수 있게 된다. \begin{eqnarray*} p(x_2) &=& \sum_{x_1} \sum_{x_3} \sum_{x_4} \sum_{x_5} f_a(x_1, x_2) f_b(x_2, x_3) f_c(x_3, x_4) f_d(x_3,x_5)\\ &=& \left[ \sum_{x_1} f_a(x_1, x_2) \right] \left[ \sum_{x_3} \sum_{x_4} \sum_{x_5} f_b(x_2, x_3) f_c(x_3, x_4) f_d(x_3,x_5) \right]\\ \end{eqnarray*} 앞의 항을 $a \to 2$의 메시지, 뒤의 항을 $b\to 2$의 메시지라고 부르자: \begin{eqnarray*} m_{a \to 2} (x_2) &=& \sum_{x_1} f_a(x_1, x_2)\\ m_{b \to 2} (x_2) &=& \sum_{x_3} \sum_{x_4} \sum_{x_5} f_b(x_2, x_3) f_c(x_3, x_4) f_d(x_3,x_5). \end{eqnarray*} 그런데 $b \to 2$의 메시지는 다시 다음처럼 나누어 쓸 수 있다: \begin{eqnarray*} m_{b \to 2} (x_2) &=& \left[ \sum_{x_3} f_b(x_2, x_3) \right] \left[ \sum_{x_4} \sum_{x_5} f_c(x_3, x_4) f_d(x_3,x_5) \right]. \end{eqnarray*} 이때 마찬가지로 다음처럼 정의할 수 있다: \begin{eqnarray*} m_{3 \to b} (x_3) &\equiv& \sum_{x_4} \sum_{x_5} f_c(x_3, x_4) f_d(x_3,x_5)\\ &=& \left[ \sum_{x_4} f_c(x_3, x_4) \right] \left[ \sum_{x_5} f_d(x_3,x_5) \right]\\ &=& m_{c \to 3} (x_3) m_{d\to 3} (x_3). \end{eqnarray*} 정리하면 \begin{eqnarray*} p(x_2) &=& \underbrace{\left[ \sum_{x_1} f_a(x_1, f_2) \right]}_{m_{a \to 2} (x_2)} \underbrace{\left( \sum_{x_3} f_b(x_2, x_3) \underbrace{\left\{ \underbrace{\left[ \sum_{x_4}f_c(x_3, x_4) \right]}_{m_{c\to 3}(x_3)} \underbrace{\left[ \sum_{x_5} f_d(x_3, x_5) \right]}_{m_{d\to 3}(x_3)} \right\}}_{m_{3\to b}(x_3)} \right)}_{m_{b\to 2}(x_2)}. \end{eqnarray*}

맨 처음 주변화의 식과 비교해보자. \begin{eqnarray*} p(x_2) &=& \sum_{x_1} \sum_{x_3} \sum_{x_4} \sum_{x_5} f_a(x_1, x_2) f_b(x_2, x_3) f_c(x_3, x_4) f_d(x_3,x_5) \end{eqnarray*} 각각의 변수 $x_1, \ldots, x_5$가 $K$ 가지의 값을 가질 수 있다고 하면, 모든 $x_2$에 대해 $p(x_2)$를 구하려면 이 방법으로는 $K^5$에 비례하는 횟수의 계산이 필요하다.

반면 메시지 전달 형식으로 정리한 식에서는 각 메시지 $m$을 계산하는 데 $K^2$에 비례하는 계산 횟수가 필요할 뿐이다.

• Christopher Bishop, Pattern Recognition and Machine Learning (Springer, New York, 2006).
• Erwin Bolthausen, The Thouless-Anderson-Palmer equation in spin glass theory
• Marc Mézard and Andrea Montanari, Information, Physics, and Computation (Oxford University Press, Oxford, 2009).
• https://mlg.eng.cam.ac.uk/teaching/4f13/2526/