======개요====== 인자 그래프(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).$$ 그래프로는 아래처럼 표현된다. {{:수학:factor_graph1.png?400|}} $x_1$, $x_2$ 등에 해당하는 노드들은 변수 노드(variable node), $f_a$, $f_b$ 등에 해당하는 노드들은 인자 노드(factor node) 혹은 함수 노드(function node)라고 불릴 것이다. ======합/곱 셈법====== =====간단한 예===== 다음처럼 트리 구조를 가지는 인자 그래프를 생각해보자. {{:수학:factor_graph2.png?600|}} 이때 $\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*} \mu_{a \to 2} (x_2) &=& \sum_{x_1} f_a(x_1, x_2)\\ \mu_{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*} \mu_{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*} \mu_{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]\\ &=& \mu_{c \to 3} (x_3) \mu_{d\to 3} (x_3). \end{eqnarray*} 정리하면 \begin{eqnarray*} p(x_2) &=& \underbrace{\left[ \sum_{x_1} f_a(x_1, f_2) \right]}_{\mu_{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]}_{\mu_{c\to 3}(x_3)} \underbrace{\left[ \sum_{x_5} f_d(x_3, x_5) \right]}_{\mu_{d\to 3}(x_3)} \right\}}_{\mu_{3\to b}(x_3)} \right)}_{\mu_{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} \mu_{\alpha \to i}(x_2).$$ 위 트리의 예에서는 $2$ 주변의 인자 노드들이 $\partial 2 = \{ a,b\}$이므로 $$p(x_2) = \mu_{a\to 2}(x_2) \mu_{b \to 2} (x_2).$$ - 인자 $\alpha$로부터 변수 $i$로 오는 메시지는, $\alpha$ 주변의 변수 노드들 중 $i$를 제외한 나머지 변수들에 대해 더한다: $$\mu_{\alpha \to i} (x_i) = \sum_{\partial \alpha \backslash \{i\}} f_{\alpha} (\mathbf{x}_{\partial \alpha}) \prod_{k \in \partial \alpha \backslash \{i\}} \mu_{k \to \alpha} (x_k).$$ 여기에서 $\mathbf{x}_{\partial \alpha}$는 전체 $\mathbf{x}$ 중에서 인자 노드 $\alpha$ 주변에 있는 것만 적었음을 의미한다. 앞의 예에서 $\alpha=b$이고 $i=2$라고 했을 때, $b$ 주변의 변수 노드들이 $2$와 $3$이지만 ($\partial b = \{2, 3\}$), 여기에서 $x_2$를 제외해야 하므로 $x_3$에 대해서만 합한다($\partial b \backslash \{2\} = \{3\}$): $$\mu_{b \to 2} (x_2) = \sum_{x_3} f_b(x_2, x_3) \mu_{3 \to b} (x_3).$$ 만일 $f_b$에 $x_2$, $x_3$ 말고도 $x_5$가 추가로 달려있었다면 $$\mu_{b \to 2} (x_2) = \sum_{x_3}\sum_{x_5} f_b(x_2, x_3, x_5) \mu_{3 \to b} (x_3) \mu_{5 \to b} (x_5).$$ - 변수 $i$로부터 인자 $\alpha$로 오는 메시지는, $i$ 주변의 인자 노드들 중 $\alpha$를 제외한 나머지 인자들에 대해 메시지들을 곱한다: $$\mu_{i \to \alpha}(x_i) = \prod_{\beta \in \partial i \backslash \{\alpha\}} \mu_{\beta \to i}(x_i) = \frac{p(x_i)}{\mu_{\alpha \to i}(x_i)}.$$ 앞의 예에서 $i=3$이고 $\alpha=b$라고 하면 $\partial 3 = \{b, c, d\}$이지만 여기서 $f_b$를 제외해야 하므로 $\partial 3\backslash \{b\} = \{c, d\}$이어서: $$\mu_{3 \to b} (x_3)= \mu_{c \to 3} (x_3) \mu_{d\to 3} (x_3) = \frac{p(x_3)}{\mu_{b\to 3}(x_3)}.$$ =====덧붙여===== ====잎 노드==== 계산은 잎 노드에서 보내는 메시지로부터 시작한다. 잎 노드가 변수 노드 $i$라면 거기에 연결된 단 하나의 링크를 통해 보내는 메시지의 값은 $\mu_{i\to \alpha}(x_i) = 1$이고, 잎 노드가 인자 노드 $\alpha$라면 이 노드가 보내는 메시지의 값은 $\mu_{\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*} \mu_{1\to a}(x_1) &=& 1\\ \mu_{a\to 2}(x_2) &=& \sum_{x_1} f_a(x_1, x_2)\\ \mu_{4\to c}(x_4) &=& 1\\ \mu_{c\to 2}(x_2) &=& \sum_{x_4} f_c(x_2, x_4)\\ \mu_{2\to b}(x_2) &=& \mu_{a\to 2}(x_2) \mu_{c\to 2}(x_2)\\ \mu_{b\to 3}(x_3) &=& \sum_{x_2} f_b(x_2, x_3) \mu_{2\to b}(x_3). \end{eqnarray*} 그 다음에는 화살표의 반대 방향으로, 즉 루트에서 잎으로 메시지를 전달한다. \begin{eqnarray*} \mu_{3\to b}(x_3) &=& 1\\ \mu_{b\to 2}(x_2) &=& \sum_{x_3} f_b(x_2,x_3)\\ \mu_{2\to a}(x_2) &=& \mu_{b\to 2}(x_2) \mu_{c\to 2}(x_2)\\ \mu_{a\to 1}(x_1) &=& \sum_{x_2}f_a(x_1,x_2)\mu_{2\to a}(x_2)\\ \mu_{2\to c}(x_2) &=& \mu_{a\to 2}(x_2) \mu_{b\to 2}(x_2)\\ \mu_{c\to 4}(x_4) &=& \sum_{x_2} f_c(x_2,x_4) \mu_{2\to c}(x_2). \end{eqnarray*} 이로부터 모든 노드에서의 주변화 분포를 구할 수 있다. 예를 들어 $p(x_2)$는 아래와 같다: \begin{eqnarray*} p(x_2) &=& \mu_{a\to 2}(x_2) \mu_{b\to 2}(x_2) \mu_{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=(i,j)$가 있어서, $$f_{(i,j)} (\sigma_i, \sigma_j) = \exp\left(\beta J_{ji} \sigma_i \sigma_j / \sqrt{N} \right).$$ 외부 장 $h$가 걸려 있다면 각 변수 노드마다 잎 노드로서 인자 노드를 붙이고 해당하는 함수는 $f_{(i)} (\sigma_i) = \exp (\beta h \sigma_i)$로 한다. {{:수학:factor_graph4.png?400|}} ====인자 노드의 연결선 수가 둘 이하일 때==== 이 물리적 예들처럼 인자 노드의 연결선 수가 언제나 하나 또는 두 개일 때를 생각해보자. 변수 노드 $i$로부터 인자 노드 하나를 거쳐 연결된 다른 변수 노드들의 집합을 $\hat\partial i$라고 부르면, 아래 그림에서는 $\hat\partial 0 = \{1, 2, 3, 4\}$이다. {{:수학:factor_graph5.png?400|}} 이 트리 구조에 합/곱 셈법을 적용하면 메시지는 \begin{eqnarray*} \mu_{0\to(0,1)} &=& \mu_{(0,2)\to 0} \mu_{(0,3)\to 0} \mu_{(0,4)\to 0} \mu_{(0,5)\to 0}\\ &=& \left[\sum_{x_2} f_{(0,2)}(x_0,x_2) \mu_{2\to(0,2)}(x_2)\right] \left[\sum_{x_3} f_{(0,3)}(x_0,x_3) \mu_{3\to(0,3)}(x_3)\right] \left[\sum_{x_4} f_{(0,4)}(x_0,x_4) \mu_{4\to(0,4)}(x_4)\right] f_{(0)}(x_0)\\ &=& f_{(0)}(x_0) \prod_{k \in \hat\partial 0 \backslash \{1\}} \left[ \sum_{x_k} f_{(0,k)}(x_0,x_k) \mu_{k\to(0,k)}(x_k) \right] \end{eqnarray*} 이고, 일반적으로는 다음처럼 적을 수 있다: $$\mu_{i\to(i,j)}(x_i) = f_{(i)}(x_i) \prod_{k \in \hat\partial i \backslash \{j\}} \left[ \sum_{x_k} f_{(i,k)}(x_i,x_k) \mu_{k\to(i,k)}(x_k) \right].$$ 또한 주변화된 분포는 $$p(x_i) = f_{(i)}(x_i) \prod_{k \in \hat\partial i} \left[ \sum_{x_k} f_{(i,k)}(x_i,x_k) \mu_{k\to(i,k)}(x_k) \right]$$ 이며, 만일 아직 정규화가 되어 있지 않다면 정규화 상수는 $Z = \sum_{x_i} p(x_i)$여서 결과적으로 $$p(x_i) = \frac{1}{Z} f_{(i)}(x_i) \prod_{k \in \hat\partial i} \left[ \sum_{x_k} f_{(i,k)}(x_i,x_k) \mu_{k\to(i,k)}(x_k) \right].$$ ====온사거 보정항==== 비록 트리는 아니지만 이 결과가 [[물리:셰링턴-커크패트릭_모형|셰링턴-커크패트릭 모형]]에 근사적으로 적용된다고 가정하자. 하나의 스핀은 다른 스핀 모두와 연결되어 있으므로 $\hat\partial i = \{1,2,\ldots, N\} - \{i\}$이다. \begin{eqnarray*} p(\sigma_i) &\approx& \frac{e^{\beta h\sigma_i} \prod_{k\neq i} \sum_{\sigma_k} \exp\left( \frac{1}{\sqrt{N}} \beta J_{ik} \sigma_i \sigma_k \right) \mu_{k\to (i,k)} (\sigma_k) }{\sum_{\tau=\pm 1} e^{\beta h\tau} \prod_{k\neq i} \sum_{\sigma_k} \exp\left( \frac{1}{\sqrt{N}} \beta J_{ik} \tau \sigma_k \right) \mu_{k\to (i,k)} (\sigma_k)}. \end{eqnarray*} 여기에서 $J_{ik}$는 평균이 $0$이고 분산이 $J^2$인 정규 분포에서 추출한 난수이다. 위 식의 일부분을 아래처럼 간단히 표기해보자: $$\mathbb{E}_i \exp\left( \sigma_i \sum_{k\neq i} \frac{1}{\sqrt{N}} \beta J_{ik} \sigma_k \right) = \prod_{k\neq i} \sum_{\sigma_k} \exp\left( \frac{1}{\sqrt{N}} \beta J_{ik} \sigma_i \sigma_k \right) \mu_{k\to (i,k)} (\sigma_k).$$ $N=3$으로 스핀들이 $\sigma_0$, $\sigma_1$, 그리고 $\sigma_2$라고 하자. $i=0$일 때에는 아래와 같이 전개된다: \begin{eqnarray*} \mathbb{E}_0 \exp\left( \sigma_0 \sum_{k\neq 0} \frac{1}{\sqrt{N}} \beta J_{0k} \sigma_k \right) &=& \prod_{k\neq 0} \left\{ \exp\left[ \sigma_0 \frac{1}{\sqrt{N}} \beta J_{0k} (+1) \right] \mu_{k\to (0,k)} (+1) + \exp\left[ \sigma_0 \frac{1}{\sqrt{N}} \beta J_{0k} (-1) \right] \mu_{k\to (0,k)} (-1) \right\}\\ &=& \exp\left\{ \sigma_0 \left[ \frac{1}{\sqrt{N}} \beta J_{01} (+1) + \frac{1}{\sqrt{N}} \beta J_{02} (+1) \right] \right\} \mu_{1\to (0,1)} (\sigma_1=+1) \mu_{2\to (0,2)} (\sigma_2=+1)\\ &+& \exp\left\{ \sigma_0 \left[ \frac{1}{\sqrt{N}} \beta J_{01} (+1) + \frac{1}{\sqrt{N}} \beta J_{02} (-1) \right] \right\} \mu_{1\to (0,1)} (\sigma_1=+1) \mu_{2\to (0,2)} (\sigma_2=-1)\\ &+& \exp\left\{ \sigma_0 \left[ \frac{1}{\sqrt{N}} \beta J_{01} (-1) + \frac{1}{\sqrt{N}} \beta J_{02} (+1) \right] \right\} \mu_{1\to (0,1)} (\sigma_1=-1) \mu_{2\to (0,2)} (\sigma_2=+1)\\ &+& \exp\left\{ \sigma_0 \left[ \frac{1}{\sqrt{N}} \beta J_{01} (-1) + \frac{1}{\sqrt{N}} \beta J_{02} (-1) \right] \right\} \mu_{1\to (0,1)} (\sigma_1=-1) \mu_{2\to (0,2)} (\sigma_2=-1). \end{eqnarray*} 즉 어떤 물리량에 $\mathbb{E}_i$가 걸려 있다면 스핀 $i$에 연결된 이웃 스핀 $k$들의 가능한 모든 배치(configuration)에 대해 더하는데, $k$들로부터 오는 메시지들을 가중치로 곱하여 더한다. 이 표기법을 사용하면 다음처럼 적을 수 있다: $$p(\sigma_i) \approx \frac{e^{\beta h\sigma_i} \mathbb{E}_i \exp\left( \sigma_i \sum_{k\neq i}\frac{1}{\sqrt{N}} \beta J_{ik} \sigma_k \right)}{\sum_{\tau=\pm 1} e^{\beta h\tau} \mathbb{E}_i \exp\left( \tau \sum_{k\neq i} \frac{1}{\sqrt{N}} \beta J_{ik} \sigma_k \right)}.$$ 이때 분모는 다음처럼 쓸 수 있는데, \begin{eqnarray*} \sum_{\tau=\pm 1} e^{\beta h\tau} \mathbb{E}_i \exp\left( \tau \sum_{k\neq i} \frac{1}{\sqrt{N}} \beta J_{ik} \sigma_k \right) &=& e^{+\beta h} \mathbb{E}_i \exp\left( +\sum_{k\neq i} \frac{1}{\sqrt{N}} \beta J_{ik} \sigma_k \right) + e^{-\beta h} \mathbb{E}_i \exp\left( -\sum_{k\neq i} \frac{1}{\sqrt{N}} \beta J_{ik} \sigma_k \right)\\ &=& \mathbb{E}_i \cosh\left( \sum_{k\neq i} \frac{1}{\sqrt{N}} \beta J_{ik} \sigma_k + \beta h\right) \end{eqnarray*} 왜냐하면 메시지로부터 오는 가중치들이 맞대응되는 항들마다 동일하게 걸리기 때문이다. 이제 $m_i \equiv \langle \sigma_i \rangle = p(\sigma_i = +1) - p(\sigma_i = -1)$로 스핀의 기댓값을 적어보면, \begin{eqnarray*} m_i &\approx& \frac{e^{+\beta h} \mathbb{E}_i \exp\left( +\sum_{k\neq i} \frac{1}{\sqrt{N}} \beta J_{ik} \sigma_k \right) - e^{-\beta h} \mathbb{E}_i \exp\left( -\sum_{k\neq i} \frac{1}{\sqrt{N}} \beta J_{ik} \sigma_k \right)}{e^{+\beta h} \mathbb{E}_i \exp\left( +\sum_{k\neq i} \frac{1}{\sqrt{N}} \beta J_{ik} \sigma_k \right) + e^{-\beta h} \mathbb{E}_i \exp\left( -\sum_{k\neq i} \frac{1}{\sqrt{N}} \beta J_{ik} \sigma_k \right)}\\ &=& \frac{\mathbb{E}_i \sinh\left( \sum_{k\neq i} \frac{1}{\sqrt{N}} \beta J_{ik} \sigma_k + \beta h\right)}{\mathbb{E}_i \cosh\left( \sum_{k\neq i} \frac{1}{\sqrt{N}} \beta J_{ik} \sigma_k + \beta h\right)}. \end{eqnarray*} $\mathbb{E}_i$가 분자와 분모에 모두 등장하므로 $\mu_{k\to (i,k)}$에 상수를 곱해도 무방하다. $\mathbb{E}_i 1 = 1$이 되게끔 정규화 $$\mu_{k\to (i,k)}(\sigma_k = +1) + \mu_{k\to (i,k)}(\sigma_k = -1) = 1$$ 을 시행하고 아래의 양을 정의하자: $$m_{k\to i} \equiv \mathbb{E}_i \sigma_k.$$ 앞서의 $N=3$의 예에서 $i=0$이고 $k=1$이라면 \begin{eqnarray*} m_{1 \to 0} &=& +\mu_{1\to (0,1)} (\sigma_1=+1) \times \mu_{2\to (0,2)} (\sigma_2=+1)\\ && + \mu_{1\to (0,1)} (\sigma_1=+1) \times \mu_{2\to (0,2)} (\sigma_2=-1)\\ && - \mu_{1\to (0,1)} (\sigma_1=-1) \times \mu_{2\to (0,2)} (\sigma_2=+1)\\ && - \mu_{1\to (0,1)} (\sigma_1=-1) \times \mu_{2\to (0,2)} (\sigma_2=-1)\\ &=& \mu_{1\to (0,1)} (\sigma_1=+1) - \mu_{1\to (0,1)} (\sigma_1=-1), \end{eqnarray*} $k=2$라면 \begin{eqnarray*} m_{2 \to 0} &=& +\mu_{1\to (0,1)} (\sigma_1=+1) \times \mu_{2\to (0,2)} (\sigma_2=+1)\\ && - \mu_{1\to (0,1)} (\sigma_1=+1) \times \mu_{2\to (0,2)} (\sigma_2=-1)\\ && + \mu_{1\to (0,1)} (\sigma_1=-1) \times \mu_{2\to (0,2)} (\sigma_2=+1)\\ && - \mu_{1\to (0,1)} (\sigma_1=-1) \times \mu_{2\to (0,2)} (\sigma_2=-1)\\ &=& \mu_{2\to (0,2)} (\sigma_2=+1) - \mu_{2\to (0,2)} (\sigma_2=-1) \end{eqnarray*} 이다. 따라서 $m_{k\to i}$는 변수 노드 $k$에서 인자 노드 $(i,k)$로 보내는 메시지가 $\sigma_k=\pm 1$에서 보이는 값의 차이라고 할 수 있다. 이는 값이 $+1$일 확률이 $\mu_{k\to (i,k)} (\sigma_k=+1)$이고 $-1$일 확률이 $\mu_{k\to (i,k)} (\sigma_k=-1)$인 이항 분포의 평균과 같다. 다음과 같은 양을 정의하면 $$X_i \equiv \sum_{k\neq i}^N \frac{1}{\sqrt{N}} \beta J_{ik} \left(\sigma_k - m_{k\to i}\right)$$ 정의에 의해 $\mathbb{E}_i X_i = 0$이다. 분산을 계산해보면 다시금 이항 분포를 따르는 난수들의 합과 같은 결과를 준다: $$\gamma_i^2 \equiv \mathbb{E}_i X_i^2 = \frac{4}{N} \sum_{k\neq i}^N \beta^2 J_{ik}^2 \left[ \mu_{k\to (i,k)}(\sigma_k=+1) \times \mu_{k\to (i,k)}(\sigma_k=-1)\right].$$ 몇 차 모멘트를 계산하든, 이항 분포를 따르는 난수들의 합에 대한 계산과 동일한 과정을 거친다. 중심 극한 정리에 의해, $N$이 충분히 클 때 $X_i$가 정규 분포를 따를 것이라고 할 수 있다. 이 사실을 이용해 $m_i$의 분자를 계산해보면 다음과 같다: \begin{eqnarray*} && \mathbb{E}_i \sinh \left( \sum_{k\neq i} \frac{1}{\sqrt{N}} \beta J_{ik} \sigma_k + \beta h \right)\\ &=& \mathbb{E}_i \sinh \left[ \sum_{k\neq i} \frac{1}{\sqrt{N}} \beta J_{ik} m_{k\to i} + \beta h + \frac{1}{\sqrt{N}} \beta J_{ik} (\sigma_k-m_{k\to i}) \right]\\ &=& \frac12 \exp \left( \sum_{k\neq i} \frac{1}{\sqrt{N}} \beta J_{ik} m_{k\to i} + \beta h \right) \mathbb{E}_i \exp \left[ \sum_{k \neq i} \frac{1}{\sqrt{N}} \beta J_{ik} (\sigma_k-m_{k\to i}) \right] - \frac12 \exp \left( -\sum_{k\neq i} \frac{1}{\sqrt{N}} \beta J_{ik} m_{k\to i} - \beta h \right) \mathbb{E}_i \exp \left[ -\sum_{k \neq i} \frac{1}{\sqrt{N}} \beta J_{ik} (\sigma_k-m_{k\to i}) \right]\\ &\approx& \frac12 \exp \left( \sum_{k\neq i} \frac{1}{\sqrt{N}} \beta J_{ik} m_{k\to i} + \beta h \right) e^{\gamma_i^2/2} - \frac12 \exp \left( -\sum_{k\neq i} \frac{1}{\sqrt{N}} \beta J_{ik} m_{k\to i} - \beta h \right) e^{\gamma_i^2/2}\\ &=& e^{\gamma_i^2/2} \sinh \left( \sum_{k\neq i} \frac{1}{\sqrt{N}} \beta J_{ik} m_{k\to i} + \beta h \right). \end{eqnarray*} 이때 다음 적분을 활용했다: $$\frac{1}{\sqrt{2\pi}\gamma_i} \int e^x \exp\left(-\frac{x^2}{2\gamma_i^2}\right) dx = e^{\gamma_i^2/2}.$$ 마찬가지로 $m_i$의 분모까지 계산해보면 $$e^{\gamma_i^2/2} \cosh \left( \sum_{k\neq i} \frac{1}{\sqrt{N}} \beta J_{ik} m_{k\to i} + \beta h \right)$$ 로서 $e^{\gamma_i^2/2}$는 상쇄되어 아래의 식을 얻게 된다: $$m_i \approx \tanh \left( \beta h + \sum_{k\neq i} \frac{1}{\sqrt{N}} \beta J_{ik} m_{k\to i} \right).$$ 이제 $m_k$와 $m_{k\to i}$ 사이의 관계를 얻기 위해 다음처럼 적는다: \begin{eqnarray*} m_k &\approx& \tanh \left( \beta h + \sum_{j\neq k} \frac{1}{\sqrt{N}} \beta J_{jk} m_{j\to k} \right)\\ &=& \tanh \left( \beta h + \sum_{j\neq k,i} \frac{1}{\sqrt{N}} \beta J_{jk} m_{j\to k} + \frac{1}{\sqrt{N}} \beta J_{ik} m_{i\to k} \right)\\ &\approx& \tanh \left( \beta h + \sum_{j\neq k,i} \frac{1}{\sqrt{N}} \beta J_{jk} m_{j\to k} \right) + \frac{1}{\sqrt{N}} \beta J_{ik} m_{i\to k} \left[ 1-\tanh^2 \left( \beta h + \sum_{j\neq k,i} \frac{1}{\sqrt{N}} \beta J_{jk} m_{j\to k} \right) \right]\\ &\approx& m_{k\to i} + \frac{1}{\sqrt{N}} \beta J_{ik} m_{i\to k} \left( 1-m_{k\to i}^2 \right). \end{eqnarray*} 마지막 줄에서 첫 항이 $m_{k\to i}$으로 표현되는 이유는 이렇다: 그 앞 줄의 첫째 항을 보면 $j=i$인 경우가 셈에서 빠지는데, 이는 마치 그 부분을 계산할 때에만 잠시 $J_{ik}=0$으로 놓은 것과 같다. 앞서 셈법의 요약 3번을 보면 $p(\sigma_k)$와 $\mu_{k\to (i,k)}(\sigma_k)$ 사이에는 밀접한 관련이 있는데, 바로 $\mu_{(i,k)\to k}(\sigma_k)=1$로 놓으면 두 양이 같아진다. 이 역시 $J_{ik}=0$으로 놓는 것으로 생각할 수 있다. 즉 $j=i$를 빼고서 계산한 것은 $p(\sigma_k)$ 대신에 $\mu_{k \to (i,k)}(\sigma_k)$를 가지고 평균하는 것과 같다. 따라서 그 항은 $m_k$ 대신에 $m_{k\to i}$를 준다. 중요한 사실은, $m_k-m_{k\to i}$이 $1/\sqrt{N}$ 정도라는 점이다. 이 결과를 $m_i$에 관한 위의 식에 다시 대입하고 $1/N$보다 고차인 항을 무시하면, $$m_i \approx \tanh \left[ \beta h + \sum_{k\neq i} \frac{1}{\sqrt{N}} \beta J_{ik} m_k - \beta^2 m_i \sum_{k\neq i} \frac{J_{ik}^2}{N} \left(1-m_k^2\right) \right].$$ $m_{k\to i}$는 $J_{ik}$로부터 영향을 받지 않는 항인데, $N$이 매우 크면 $m_k$ 역시도 그러할 것으로 생각할 수 있다. 통계적으로 독립인 변수들의 경우 $\langle XY \rangle = \langle X \rangle \langle Y \rangle$로 분리된다. $\langle J_{ik}^2 \rangle = J^2$이므로 \begin{eqnarray*} m_i &\approx& \tanh \left[ \beta h + \sum_{k\neq i} \frac{1}{\sqrt{N}} \beta J_{ik} m_k - \beta^2 m_i \sum_{k\neq i} \frac{J^2}{N} \left(1-m_k^2\right) \right]\\ &\approx& \tanh \left[ \beta h + \sum_{k\neq i} \frac{1}{\sqrt{N}} \beta J_{ik} m_k - \beta^2 m_i J^2 \left( 1 - \frac{1}{N} \sum_{k=1}^N m_k^2\right) \right]. \end{eqnarray*} [[물리:평균장_이론|평균장 이론]]에서 기대되는 바와 비교하면 $\tanh$ 안에 항이 하나 더 들어있는 것을 알게 되는데, 이를 온사거 보정항(Onsager correction term)이라고 부른다. ====복제 대칭 해==== 나아가 다음의 양을 정의하고 $$q \equiv \lim_{N\to\infty} \frac{1}{N} \sum_{k=1}^N m_k^2$$ 우변에 들어갈 $m_k$에 대한 식을 다시 보면, $$m_k = \tanh \left( \beta h + \sum_{j\neq k} \frac{1}{\sqrt{N}} \beta J_{jk} m_{j\to k} \right)$$ $m_{j \to k}$는 $J_{jk}$와 무관하고, $\sum_{j\neq k} \frac{1}{\sqrt{N}} J_{jk} m_{j\to k}$이 $J_{jk}$들의 합으로서 정규 분포를 따를 것인데 그 분산의 근사적인 값이 바로 $J^2 q$로 주어진다: $$\frac{1}{N} \sum_{j\neq k} m_{j\to k}^2 \approx \frac{1}{N} \sum_j m_j^2 \approx q.$$ 따라서 $\phi(z)$를 평균 $0$와 분산 $1$인 정규 분포라고 하면, 이로부터 $z$를 얻고 $J\sqrt{q}z$를 $\tanh^2$ 안에 대입한다: \begin{eqnarray*} q &=& \lim_{N\to\infty} \frac{1}{N} \sum_{k=1}^N m_k^2\\ &=& \lim_{N\to\infty} \frac{1}{N} \sum_{k=1}^N \tanh^2 \left( \beta h + \beta \sum_{j\neq k} \frac{1}{\sqrt{N}} J_{jk} m_{j\to k} \right)\\ &=& \int \tanh^2 \left( \beta h + \beta J \sqrt{q} z \right) \phi(z) dz. \end{eqnarray*} 이는 [[물리:복제_대칭_해|복제 대칭 해]]에서 얻은 결과와 동일한 것으로서, 고온에서 성립하는 식이다. =====$p$-스핀 유리 모형===== [[물리:p-스핀_유리_모형|$p$-스핀 유리 모형]]은 [[물리:셰링턴-커크패트릭_모형|셰링턴-커크패트릭 모형]]를 일반화하여 $p$개의 스핀이 함께 상호작용하는 모형이다. 본래는 계 안에서 임의로 어떤 $p$개의 스핀을 잡아도 상호작용이 존재하는 모형이다. 그러나 근사식을 유도하기 위해 먼저 공간적으로 트리 구조를 이루고 있다고 가정하자. $p=3$을 예로 들어 어떤 변수 노드 $x_0$를 중심으로 인자 그래프를 그리면 다음과 같은 모양이 될 것이다. {{:수학:factor_graph6.png?400|}} \begin{eqnarray*} p(x_0) &=& \left[\sum_{x_1,x_2} f_{(0,1,2)}(x_0,x_1,x_2) \mu_{1\to(0,1,2)}(x_1) \mu_{2\to(0,1,2)}(x_2) \right] \times \left[\sum_{x_3,x_4} f_{(0,3,4)}(x_0,x_3,x_4) \mu_{3\to(0,3,4)}(x_3) \mu_{4\to(0,3,4)}(x_4) \right]\\ && \times \left[\sum_{x_5,x_6} f_{(0,5,6)}(x_0,x_5,x_6) \mu_{5\to(0,5,6)}(x_5) \mu_{6\to(0,5,6)}(x_6) \right] \times \left[\sum_{x_7,x_8} f_{(0,7,8)}(x_0,x_7,x_8) \mu_{7\to(0,7,8)}(x_7) \mu_{8\to(0,7,8)}(x_8) \right] \times f_{(0)} (x_0) \end{eqnarray*} 정규화가 미리 되어있지 않다고 하면 분모에 정규화 상수를 써주고 스핀에 대한 표기법으로 적어주자. 모든 스핀이 연결된 상황에서도 위의 식이 성립한다고 보기 때문에 근사식이다. 편의상 $p=3$이라고 하고 적은 다음 일반화할 것이다. 그리고 앞 절과 달리, 평균 $0$이고 분산이 $J^2 p! / N^{p-1}$인 정규분포에서 무작위로 결합상수들을 추출하였다고 가정하여 $N$에 대한 의존성을 결합상수 안에 집어넣을 것이다. 결합상수에 달린 인덱스에 중복이 있으면 모두 $0$으로 간주한다. 즉 $J_{iij} = J_{ijj} = \ldots = 0$이다. 그리고 동일한 $p$ 스핀 집합을 여러 번 셈하는 일을 피하기 위해, 좌변에 고정된 $i$를 제외한 나머지 $k_1$, $k_2$ 등의 인덱스는 오름차순으로 정렬한다. \begin{eqnarray*} p(\sigma_i) &\approx& \frac{e^{\beta h \sigma_i} \prod_{k_1