인자 그래프(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*} 앞의 항을 $f_1 \to x_2$의 메시지, 뒤의 항을 $f_2\to x_2$의 메시지라고 하자: \begin{eqnarray*} m_{f_1 \to x_2} (x_2) &=& \sum_{x_1} f_a(x_1, x_2)\\ m_{f_2 \to x_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*} 그런데 $f_2 \to x_2$의 메시지는 다시 다음처럼 나누어 쓸 수 있다: \begin{eqnarray*} m_{f_2 \to x_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_{x_3 \to f_2} (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_{f_c \to x_3} (x_3) m_{f_d\to x_3} (x_3). \end{eqnarray*} 정리하면 \begin{eqnarray*} p(x_2) &=& \underbrace{\left[ \sum_{x_1} f_a(x_1, f_2) \right]}_{m_{f_a \to x_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_{f_c\to x_3}(x_3)} \underbrace{\left[ \sum_{x_5} f_d(x_3, x_5) \right]}_{m_{f_d\to x_3}(x_3)} \right\}}_{m_{x_3\to f_b}(x_3)} \right)}_{m_{f_b\to x_2}(x_2)} \end{eqnarray*}

• 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/