Differences

This shows you the differences between two versions of the page.

--- 수학:인자_그래프 [2026/03/24 21:30] – [믿음 전파 셈법] admin
+++ 수학:인자_그래프 [2026/03/25 15:00] (current) – [간단한 예] admin
@@ Line 9: / Line 9: @@
 $x_1$, $x_2$ 등에 해당하는 노드들은 변수 노드(variable node), $f_a$, $f_b$ 등에 해당하는 노드들은 인자 노드(factor node) 혹은 함수 노드(function node)라고 불릴 것이다.
-======메시지 전달======
+======합/곱 셈법======
+=====간단한 예=====
 다음처럼 트리 구조를 가지는 인자 그래프를 생각해보자.
@@ Line 22: / Line 22: @@
 &=& \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$의 메시지라고 하자:
+편의상 $f_\alpha$를 $\alpha$로, $x_i$를 $i$로 표기해서
+앞의 항을 $a \to 2$의 메시지, 뒤의 항을 $b\to 2$의 메시지라고 부르자:
 \begin{eqnarray*}
-m_{f_1 \to x_2} (x_2) &=& \sum_{x_1} f_a(x_1, x_2)\\
+m_{a \to 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).
+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*}
-그런데 $f_2 \to x_2$의 메시지는 다시 다음처럼 나누어 쓸 수 있다:
+그런데 $b \to 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].
+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_{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)\\
+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_{f_c \to x_3} (x_3) m_{f_d\to x_3} (x_3).
+&=& 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_{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)}
+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$에 비례하는 계산 횟수가 필요할 뿐이다. 더 간단한 예로 이야기하면, $ab+ac = a(b+c)$에서 좌변은 곱셈 두번과 덧셈 한번을 필요로 하지만 우변은 덧셈 한번과 곱셈 한번이면 충분하다.
+=====셈법의 요약=====
+  - 어떤 변수 노드 $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).$$
+  - 인자 $\alpha$로부터 변수 $i$로 오는 메시지는, $\alpha$ 주변의 변수 노드들 중 $i$를 제외한 나머지 변수들에 대해 더한다: $$m_{\alpha \to i} (x_i) = \sum_{\partial \alpha \backslash \{i\}} f_{\alpha} (\mathbf{x}_{\partial \alpha}) \prod_{k \in \partial \alpha \backslash \{i\}} m_{k \to \alpha} (x_k).$$ 여기에서 $\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).$$ 만일 $f_b$에 $x_2$, $x_3$ 말고도 $x_5$가 추가로 달려있었다면 $$m_{b \to 2} (x_2) = \sum_{x_3}\sum_{x_5} f_b(x_2, x_3, x_5) m_{3 \to b} (x_3) m_{5 \to b} (x_5).$$
+  - 변수 $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)$이다.
+====모든 노드에 대한 주변화====
+그래프의 모든 변수 노드에서 주변화 분포를 구하고자 할 때, 앞의 방법을 모든 변수 노드에 대해 반복하는 것은 비효율적이다. 이때에는 먼저 임의로 변수 노드 혹은 인자 노드를 루트로 지정하고 잎에서부터 루트로 메시지를 전달한다. 아래 그림의 예를 생각해보자.
+{{:수학:factor_graph3.png?400|}}
+이 인자 그래프가 표현하는 결합 확률분포는 $$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*}
+특정 노드 하나에 대해 구할 때와 비교해서, 모든 노드에 대해 구할 때 필요한 계산량은 고작 두 배에 불과하다.
+====정규화====
+결합 확률분포가 정규화된 채 주어지지 않은 경우, 먼저 합/곱 셈법을 사용해 아무 변수 노드 $x_i$에 대해서든 (정규화되지 않은) 주변화 분포 $\tilde{p}(x_i)$를 구한다. 그 다음 아래처럼 정규화 상수 $Z$를 구한다.
+$$Z = \sum_{x_i} \tilde{p}(x_i)$$
+변수 하나에 대해서만 정규화를 시행하면 되기 때문에 전체 변수에 대해 정규화를 시행하는 경우보다 계산적으로 효율적이다.
+======물리적인 예======
+=====이징 모형=====
+각각의 스핀이 가장 가까운 이웃과 상호작용하는 이징 모형이 온도 $T$의 열평형에서 보이게 되는 확률분포를 생각해보자.
+변수들은 격자의 각 지점에 놓인 $\sigma_i \in \left\{ +1, -1 \right\}$이며, 인자 노드 $a$는 연결된 두 스핀들 $i$와 $j$ 사이의 링크에 놓여서 다음과 같은 값을 준다:
+$$f_a (\sigma_i, \sigma_j) = \exp\left(\beta \sigma_i \sigma_j \right).$$
+여기에서 $\beta \equiv 1/(k_B T)$이다.
+=====셰링턴-커크패트릭 모형=====
+이 경우 모든 스핀쌍 $\sigma_i$와 $\sigma_j$ 사이에 연결선 $a$가 있어서,
+$$f_a (\sigma_i, \sigma_j) = \exp\left(\beta J_{ji} \sigma_i \sigma_j / \sqrt{N} \right).$$
+======같이 보기======
+  * [[물리:tap_방정식|TAP 방정식]]
+  * [[물리:셰링턴-커크패트릭_모형|셰링턴-커크패트릭 모형]]
 ======참고문헌======
   * Christopher Bishop, //Pattern Recognition and Machine Learning// (Springer, New York, 2006).