인자 그래프(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_\alpha$를 $\alpha$로, $x_i$를 $i$로 표기해서 앞의 항을 $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) &=& \sum_{x_3} f_b(x_2, x_3) \left[ \sum_{x_4} \sum_{x_5} f_c(x_3, x_4) f_d(x_3,x_5) \right]. \end{eqnarray*} 이때 마찬가지로 마지막의 $\left[ \ldots \right]$를 다음처럼 정의할 수 있다: \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$에 비례하는 횟수의 계산이 필요하다.

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

1. 어떤 변수 노드 $i$에서의 주변화된 분포 $p(x_i)$는, 노드 $i$에 이웃한 인자 노드들로부터 들어오는 메시지들의 곱이다: $$p(x_i) = \prod_{\alpha \in \partial i} m_{\alpha \to i}(x_2).$$ 위 트리의 예에서는 $x_2$ 주변의 인자 노드들이 $\partial x_2 = \{ f_a,f_b\}$이므로 $$p(x_2) = m_{a\to 2}(x_2) m_{b \to 2} (x_2).$$
2. 인자 $\alpha$로부터 변수 $i$로 오는 메시지는, $\alpha$ 주변의 변수 노드들 중 $i$를 제외한 나머지 변수들에 대해 더한다: $$m_{\alpha \to i} = \sum_{\partial \alpha \backslash \{i\}} f_{\alpha} (\mathbf{x}_{\partial \alpha}) \prod_{\partial \alpha \backslash \{i\}} m_{i \to \alpha} (x_i).$$ 여기에서 $\mathbf{x}_{\partial \alpha}$는 전체 $\mathbf{x}$ 중에서 인자 노드 $\alpha$ 주변에 있는 것만 적었음을 의미한다. 앞의 예에서 $\alpha=b$이고 $i=2$라고 했을 때, $f_b$ 주변의 변수 노드들이 $x_2$와 $x_3$이지만 ($\partial f_b = \{x_2, x_3\}$), 여기에서 $x_2$를 제외해야 하므로 $x_3$에 대해서만 합한다($\partial f_b \backslash \{x_2\} = \{x_3\}$): $$m_{b \to 2} (x_2) = \sum_{x_3} f_b(x_2, x_3) m_{3 \to b} (x_3).$$
3. 변수 $i$로부터 인자 $\alpha$로 오는 메시지는, $i$ 주변의 인자 노드들 중 $\alpha$를 제외한 나머지 인자들에 대해 메시지들을 곱한다: $$m_{i \to \alpha}(x_i) = \prod_{\beta \in \partial i \backslash \{\alpha\}} m_{\beta \to i}(x_i) = \frac{p(x_i)}{m_{\alpha \to i}(x_i)}.$$ 앞의 예에서 $i=3$이고 $\alpha=b$라고 하면 $\partial x_3 = \{f_b, f_c, f_d\}$이지만 여기서 $f_b$를 제외해야 하므로 $\partial x_3\backslash \{f_b\} = \{f_c, f_d\}$이어서: $$m_{3 \to b} (x_3)= m_{c \to 3} (x_3) m_{d\to 3} (x_3) = \frac{p(x_3)}{m_{b\to 3}(x_3)}.$$

계산은 잎 노드에서 보내는 메시지로부터 시작한다. 잎 노드가 변수 노드 $i$라면 거기에 연결된 단 하나의 링크를 통해 보내는 메시지의 값은 $m_{i\to \alpha}(x_i) = 1$이고, 잎 노드가 인자 노드 $\alpha$라면 이 노드가 보내는 메시지의 값은 $m_{\alpha \to i} = f_\alpha(x_i)$이다.

그래프의 모든 변수 노드에서 주변화 분포를 구하고자 할 때, 앞의 방법을 모든 변수 노드에 대해 반복하는 것은 비효율적이다. 이때에는 먼저 임의로 변수 노드 혹은 인자 노드를 루트로 지정하고 잎에서부터 루트로 메시지를 전달한다. 아래 그림의 예를 생각해보자.

이 인자 그래프가 표현하는 결합 확률분포는 $$p(\mathbf{x}) = f_a(x_1,x_2) f_b(x_2,x_3) f_c(x_2,x_4)$$ 이며, 우리는 임의로 $x_3$를 루트로 정했다. 화살표 방향으로 메시지를 전달한 결과는 아래와 같다: \begin{eqnarray*} m_{1\to a}(x_1) &=& 1\\ m_{a\to 2}(x_2) &=& \sum_{x_1} f_a(x_1, x_2)\\ m_{4\to c}(x_4) &=& 1\\ m_{c\to 2}(x_2) &=& \sum_{x_4} f_c(x_2, x_4)\\ m_{2\to b}(x_2) &=& m_{a\to 2}(x_2) m_{c\to 2}(x_2)\\ m_{b\to 3}(x_3) &=& \sum_{x_2} f_b(x_2, x_3) m_{2\to b}(x_3). \end{eqnarray*} 그 다음에는 화살표의 반대 방향으로, 즉 루트에서 잎으로 메시지를 전달한다. \begin{eqnarray*} m_{3\to b}(x_3) &=& 1\\ m_{b\to 2}(x_2) &=& \sum_{x_3} f_b(x_2,x_3)\\ m_{2\to a}(x_2) &=& m_{b\to 2}(x_2) m_{c\to 2}(x_2)\\ m_{a\to 1}(x_1) &=& \sum_{x_2}f_a(x_1,x_2)m_{2\to a}(x_2)\\ m_{2\to c}(x_2) &=& m_{a\to 2}(x_2) m_{b\to 2}(x_2)\\ m_{c\to 4}(x_4) &=& \sum_{x_2} f_c(x_2,x_4) m_{2\to c}(x_2). \end{eqnarray*}

이로부터 모든 노드에서의 주변화 분포를 구할 수 있다. 예를 들어 $p(x_2)$는 아래와 같다: \begin{eqnarray*} p(x_2) &=& m_{a\to 2}(x_2) m_{b\to 2}(x_2) m_{c\to 2}(x_2)\\ &=& \left[ \sum_{x_1} f_a(x_1,x_2) \right] \left[ \sum_{x_3} f_b(x_2,x_3) \right] \left[ \sum_{x_4} f_a(x_2,x_4) \right]\\ &=& \sum_{x_1} \sum_{x_3} \sum_{x_4} f_a(x_1,x_2) f_b(x_2,x_3) f_c(x_2,x_4)\\ &=& \sum_{x_1} \sum_{x_3} \sum_{x_4} p(\mathbf{x}). \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/