정보가 전송되는 과정에서 전달 채널의 잡음 때문에 원래의 정보가 수신자에게 깨끗하게 전송되지 못한다. 이 때 전송되는 메시지의 용량이 채널의 용량보다 작다면 정보 전달이 잡음 없이 이루어질 수 있음이 섀넌에 의해 증명되었고, 소울라스 코드는 이러한 섀넌의 한계에 도달하기 위한 한가지 방법이다. 소울라스 코드를 만드는 과정은 다음과 같다.

$N$개의 비트로 이루어진 전송하고자 하는 정보를 $\vec\xi\in\{\pm1\}^N$이라 하자. 이를 $M$개의 비트 $\mathbf J^0=\{J_1^0,J_2^0,\dots,J_M^0\}$로 변환한 뒤 상대방에게 전송한다. 이 때 변환은 각 $J_a^0$마다 $\vec\xi$에서 무작위로 몇 개의 비트를 골라 부분집합 $\partial a$를 만든 뒤 그 원소들을 곱하는 것으로 정의한다. 이를 수식으로 쓰면 $$J_a^0 = \prod_{i\in\partial a}\xi_i$$ 이다. 그리고 정보를 전송하는 과정에서 들어가는 잡음은 각 비트를 확률 $p$로 뒤집을 수 있다고 가정하면 전송하고자 하는 메시지에 대한 수신자가 실제로 받게 되는 메시지의 조건부 확률은 $$P(J_a\vert J_a^0) = p\delta(J_a+J_a^0)+(1-p)\delta(J_a-J_a^0)$$ 가 된다. 이렇게 해서 수신자는 $\mathbf J$를 송신자로부터 받고 이를 이용해서 원래의 메시지를 복원해내야 한다. 수신자가 복원한 메시지를 $\vec\sigma$로 쓴다면, 복원 과정은 해밀토니안 $$H(\sigma) = -\sum_{a=1}^M J_a\prod_{i\in\partial a}\sigma_i$$ 를 가지고 $$P(\sigma\vert\mathbf J) = Z^{-1}\exp\left[ -\beta H(\sigma) \right]$$ 를 계산해서 가장 그럴듯한 $\sigma$를 찾아내는 것으로 이해할 수 있다. 에너지가 최소화되는 것은 $\prod_{i \in \partial a} \sigma_i = J_a$일 때이다.

위에서 언급했던 조건부 확률을 계산하려면 분배함수 $Z=\sum_{\vec\sigma}e^{-\beta H(\vec\sigma)}$를 계산해야 하는데 이 과정의 계산복잡도는 $2^N$로 매우 크다. 하지만 공동 방법을 이용하면 희박한 인자 그래프 모형에 대한 분배함수를 $=O(N)$까지 줄여 계산할 수 있다.

이를 위해 먼저 위 코드를 인자 그래프로 나타내어보자. 아래 그림에서 동그라미는 $\vec\sigma$에 해당하는 스핀 변수, 네모는 $\mathbf J$에 해당하는 기능 노드, 연결선은 변환 규칙에 따라 긋는다.

원래 그래프에 아래처럼 새로운 기능 노드 $a$를 추가한다면

전체 해밀토니안은 $$H^{\text{new}} = H^{\text{old}} - J_a\prod_{i\in\partial a}\sigma_i$$ 가 되고, 분배함수는 \begin{align*} Z^{\text{new}}=&\sum_{\{\sigma_i\}}\exp\left(-\beta H^{\text{old}}+\beta J_a\prod_{i\in\partial a}\sigma_i\right)\\ =&Z^{\text{old}}\sum_{\{\sigma_i\}}\frac{\exp(-\beta H^{\text{old}})}{Z^{\text{old}}}\exp\left(\beta J_a\prod_{i\in\partial a}\sigma_i\right)\\ =&Z^{\text{old}} \sum_{\{\sigma_i\vert i\in\partial a\}} \left\{ \exp\left(\beta J_a\prod_{i\in\partial a}\sigma_i\right) \times \left[ \sum_{\{\sigma_i\vert i\not\in\partial a\}}\frac{\exp(-\beta H^{\text{old}})}{Z^{\text{old}}} \right] \right\} \end{align*} 가 된다. 여기서 $\{\sigma_i\vert i\in\partial a\}$는 노드 $a$에 인접한 스핀 변수들의 집합을 의미한다. 첫 번째 합은 추가된 기능 노드 $a$에 직접 연결된 변수 노드들에 관한 것이고 두 번째 합은 그 외의 부분을 다룬다.

우변의 마지막 합은, 기능 노드 $a$의 위치가 텅 비어 공동을 형성하고 있을 때의 확률 분포를 기술한다. $\{\sigma_i\vert i\in\partial a\}$는 그 공동이 가지는 경계라고 칭할 것이다. 위 그림의 예에서라면 $\{\sigma_i, \sigma_j, \sigma_k, \sigma_l\}$이다. 우변의 마지막 합은 $a$가 비어 있는 상태에서 그 경계에 놓인 것들을 제외한 나머지 스핀 변수들을 주변화(marginalization)하고 있고, 그 결과는 $\{\sigma_i\vert i\in\partial a\}$의 함수로 표현된 확률 분포이다. 이를 $P_{\text{cavity}}(\{\sigma_i\vert i\in\partial a\})$라고 하자.

만약 공동 경계에 놓인 변수 노드들 사이의 상관관계가 적다면 이를 $$P_{\text{cavity}}(\{\sigma_i\vert i\in\partial a\})\approx\prod_{i\in\partial a}q_{i\rightarrow a}(\sigma_i)$$ 와 같이 곱으로 쪼개어 적을 수 있을 것이다. 이때 $q_{i\rightarrow a}(\sigma_i)$는 기능 노드 $a$가 존재하지 않을 때의 $\sigma_i$의 분포이다. 이 근사는 전체 구조가 트리일 때 정확해진다.

공동 자기화(cavity magnetization)을 다음처럼 정의하자: \[ m_{i\rightarrow a} \equiv q_{i \rightarrow a} (\sigma_i=+1) - q_{i \rightarrow a} (\sigma_i=-1).\] 나아가 \[ 1= q_{i \rightarrow a} (\sigma_i=+1) + q_{i \rightarrow a} (\sigma_i=-1)\] 이므로, 두 식을 연립하면 $q_{i\rightarrow a}(\sigma_i) = (1+\sigma_i m_{i\rightarrow a})/2$이다. 이제 $\eta=\pm 1$일 때 $e^{\eta x}= \cosh x + \eta \sinh x = \cosh x ( 1+\eta \tanh x)$임을 이용하면, \begin{align*} Z^{\text{new}} =&Z^{\text{old}}\sum_{\{\sigma_i\vert i\in\partial a\}}\exp\left(\beta J_a\prod_{i\in\partial a}\sigma_i\right)P_{\text{cavity}}(\{\sigma_i\vert i\in\partial a\})\\ \approx&Z^{\text{old}}\sum_{\{\sigma_i\vert i\in\partial a\}} \left\{ \cosh \beta J_a \left[ 1+ \left( \prod_{i\in\partial a}\sigma_i \right) \tanh \beta J_a \right] \times \left( \prod_{i\in\partial a}\frac{1+\sigma_im_{i\rightarrow a}}2 \right) \right\}\\ =&Z^{\text{old}}\sum_{\{\sigma_i\vert i\in\partial a\}} \left\{ \cosh \beta J_a \left( \prod_{i\in\partial a}\frac{1+\sigma_im_{i\rightarrow a}}2 \right) + \sinh \beta J_a \left( \prod_{i\in\partial a}\sigma_i \right) \left( \prod_{i\in\partial a}\frac{1+\sigma_im_{i\rightarrow a}}2 \right) \right\}\\ =&Z^{\text{old}}\sum_{\{\sigma_i\vert i\in\partial a\}} \left\{ \cosh \beta J_a \left( \prod_{i\in\partial a}\frac{1+\sigma_im_{i\rightarrow a}}2 \right) + \sinh \beta J_a \left( \prod_{i\in\partial a}\frac{\sigma_i+m_{i\rightarrow a}}2 \right) \right\}. \end{align*} 우변의 항을 각각 나누어 아래와 같이 스핀에 대한 합을 하고 나면 다음과 같다: $$\sum_{\{\sigma_i\vert i\in\partial a\}}\prod_{i\in\partial a}\left(\frac{1+\sigma_im_{i\rightarrow a}}2\right) = \prod_{i\in\partial a} \left[ \sum_{\sigma_i = \pm 1} \left(\frac{1+\sigma_im_{i\rightarrow a}}2\right) \right] = \prod_{i\in\partial a} 1 = 1$$ $$\sum_{\{\sigma_i\vert i\in\partial a\}}\prod_{i\in\partial a}\left(\frac{\sigma_i+m_{i\rightarrow a}}2\right) = \prod_{i\in\partial a} \left[ \sum_{\sigma_i = \pm 1} \left(\frac{\sigma_i+m_{i\rightarrow a}}2\right) \right] = \prod_{i\in\partial a}m_{i\rightarrow a}.$$ 곱의 합을 합의 곱으로 바꾸었음에 주의한다. 결과적으로 분배함수는 \begin{align*} Z^{\text{new}} =&Z^{\text{old}}\cosh \beta J_a \left[ 1+ \left(\prod_{i\in\partial a}m_{i\rightarrow a} \right) \tanh \beta J_a \right] \end{align*} 가 된다.

마찬가지로 아래 그림의 회색 영역처럼 스핀 변수 $i$와 인접한 기능 노드들 $b \in \partial i$들을 한꺼번에 추가하는 경우도 생각해볼 수 있을 것이다.

이 때 새로운 해밀토니안은 $$H^{\text{new}} = H^{\text{old}} -\sum_{b\in\partial i}J_b\prod_{j\in\partial b}\sigma_j$$ 이고, 분배함수는 \begin{align*} Z^{\text{new}}=&\sum_{\sigma^{\text{old}}}\sum_{\sigma_i}\exp\left(-\beta H^{\text{old}} + \beta\sum_{b\in\partial i}J_b\prod_{j\in\partial b}\sigma_j\right)\\ =&\sum_{\sigma^{\text{old}}}\sum_{\sigma_i}\exp\left(-\beta H^{\text{old}} + \beta\sum_{b\in\partial i}J_b\sigma_i\prod_{j\in\partial b\backslash i}\sigma_j\right)\\ =&Z^{\text{old}}\sum_{\sigma^{\text{old}}}\sum_{\sigma_i}\frac{\exp\left(-\beta H^{\text{old}}\right)}{Z^{\text{old}}}\exp\left(\beta\sum_{b\in\partial i}J_b\sigma_i\prod_{j\in\partial b\backslash i}\sigma_j\right) \end{align*} 가 된다. $j \in \partial b \setminus i$는 기능 노드 $b$에 연결된 변수 노드들의 집합에서 $i$를 제외한 것을 의미한다. 위 그림의 예에서는 $\partial b \setminus i = \{m, n\}$이다. 이를 모든 $b \in \partial i$에 대해 반복하면서 합친 것이 $\{\sigma_j\vert j\in\partial b\backslash i;b\in\partial i\}$이다. 위의 그림에서라면 $\{j, k, l, m, n, \ldots\}$으로, 색칠된 원의 바로 바깥쪽 경계면에 있는 변수 노드들이다. 이 변수 노드들 외에는 모두 주변화함으로써 확률 분포 $P_{\text{cavity}}$를 적고, 이를 독립적인 확률들의 곱으로 근사한다: $$P_{\text{cavity}} \left( \{\sigma_j\vert j\in\partial b\backslash i;b\in\partial i\} \right) = \sum_{\{\sigma_j\vert j\in\partial b;b\not\in\partial i\}}\frac{\exp\left(-\beta H^{\text{old}}\right)}{Z^{\text{old}}}\approx \prod_{\substack{b\in\partial i,\\j\in\partial b\backslash i}}q_{j\rightarrow b}(\sigma_j).$$

그러므로 스핀 $\sigma_i=\pm 1$이 추가되었을 때 새롭게 얻어지는 분배함수는 \begin{align*} Z^{\text{new}}=&Z^{\text{old}}\sum_{\{\sigma_j\vert j\in\partial b\backslash i;b\in\partial i\}}\sum_{\sigma_i} P_{\text{cavity}} \left( \{\sigma_j\vert j\in\partial b\backslash i;b\in\partial i\} \right) \exp\left(\beta\sum_{b\in\partial i}J_b\sigma_i\prod_{j\in\partial b\backslash i}\sigma_j\right)\\ \approx&Z^{\text{old}}\sum_{\{\sigma_j\vert j\in\partial b\backslash i;b\in\partial i\}}\sum_{\sigma_i} \left( \prod_{\substack{b\in\partial i,\\j\in\partial b\backslash i}}q_{j\rightarrow b}(\sigma_j) \right) \exp\left(\beta\sum_{b\in\partial i}J_b\sigma_i\prod_{j\in\partial b\backslash i}\sigma_j\right)\\ =&Z^{\text{old}}\sum_{\{\sigma_j\vert j\in\partial b\backslash i;b\in\partial i\}}\sum_{\sigma_i} \left( \prod_{\substack{b\in\partial i,\\j\in\partial b\backslash i}}q_{j\rightarrow b}(\sigma_j) \right) \prod_{b\in\partial i} \exp\left(\beta J_b\sigma_i\prod_{j\in\partial b\backslash i}\sigma_j\right)\\ =&Z^{\text{old}}\sum_{\{\sigma_j\vert j\in\partial b\backslash i;b\in\partial i\}}\sum_{\sigma_i} \prod_{b\in\partial i} \left\{ \left[ \prod_{j\in\partial b\backslash i} q_{j\rightarrow b}(\sigma_j) \right] \exp\left(\beta J_b\sigma_i\prod_{j\in\partial b\backslash i}\sigma_j\right) \right\} \\ =&Z^{\text{old}}\sum_{\sigma_i} \prod_{b\in\partial i} \left\{ \sum_{\{\sigma_j\vert j\in\partial b\backslash i\}} \left[\prod_{j\in\partial b\backslash i}q_{j\rightarrow b}(\sigma_j) \right] \exp\left(\beta J_b\sigma_i\prod_{j\in\partial b\backslash i}\sigma_j\right)\right\} \end{align*} 로 쓸 수 있다. 마지막 줄로 넘어올 때에 곱의 합을 합의 곱으로 바꾸었음에 주의한다. 괄호 안의 항을 \begin{align*} \Lambda_{b\rightarrow i}^{\sigma_i} \equiv&\sum_{\{\sigma_j\vert j\in\partial b\backslash i\}} \left[ \prod_{j\in\partial b\backslash i}q_{j\rightarrow b}(\sigma_j) \right] \exp\left(\beta J_b\sigma_i\prod_{j\in\partial b\backslash i}\sigma_j\right)\\ =&\sum_{\{\sigma_j\vert j\in\partial b\backslash i\}} \left[ \prod_{j\in\partial b\backslash i}\frac{1+\sigma_jm_{j\rightarrow b}}2 \right] \cosh \beta J_b \left[ 1+ \left( \sigma_i\prod_{j\in\partial b\backslash i}\sigma_j \right) \tanh \beta J_b \right]\\ =&\sum_{\{\sigma_j\vert j\in\partial b\backslash i\}} \left[ \prod_{j\in\partial b\backslash i}\frac{1+\sigma_jm_{j\rightarrow b}}2 \right] \cosh \beta J_b + \sum_{\{\sigma_j\vert j\in\partial b\backslash i\}} \left[ \prod_{j\in\partial b\backslash i}\frac{1+\sigma_jm_{j\rightarrow b}}2 \right] \left( \sigma_i\prod_{j\in\partial b\backslash i}\sigma_j \right) \sinh \beta J_b \end{align*} 로 정의하고, 각 항을 나누어 계산하자. 먼저 인수분해를 통해 앞의 항에 있는 합과 곱을 간단히 계산할 수 있다: $$\sum_{\{\sigma_j\vert j\in\partial b\backslash i\}}\prod_{j\in\partial b\backslash i}\frac{1+\sigma_jm_{j\rightarrow b}}2 = \prod_{j\in\partial b\backslash i} \sum_{\sigma_j = \pm 1} \frac{1+\sigma_jm_{j\rightarrow b}}2 = \prod_{j\in\partial b\backslash i} 1 = 1.$$ 두번째 항에 들어있는 합과 곱은 다음처럼 계산한다: \begin{align*} \sum_{\{\sigma_j\vert j\in\partial b\backslash i\}} \left[ \prod_{j\in\partial b\backslash i}\frac{1+\sigma_jm_{j\rightarrow b}}2 \right] \left( \sigma_i\prod_{j\in\partial b\backslash i}\sigma_j \right) &= \sigma_i \sum_{\{\sigma_j\vert j\in\partial b\backslash i\}} \left[ \prod_{j\in\partial b\backslash i}\frac{1+\sigma_jm_{j\rightarrow b}}2 \right] \left( \prod_{j\in\partial b\backslash i}\sigma_j \right)\\ =&\sigma_i\sum_{\{\sigma_j\vert j\in\partial b\backslash i\}}\prod_{j\in\partial b\backslash i}\frac{\sigma_j+m_{j\rightarrow b}}2\\ =&\sigma_i \prod_{j\in\partial b\backslash i} \sum_{\sigma_j = \pm 1} \frac{\sigma_j+m_{j\rightarrow b}}2\\ =&\sigma_i\prod_{j\in\partial b\backslash i}m_{j\rightarrow b}. \end{align*} 따라서 다음처럼 정리되고 $$\Lambda_{b\rightarrow i}^{\sigma_i} = \cosh \beta J_b \left(1+\sigma_i\tanh \beta J_b \prod_{j\in\partial b\backslash i}m_{j\rightarrow b}\right)$$ 새로운 분배함수는 $$Z^{\text{new}} = Z^{\text{old}}\sum_{\sigma_i}\prod_{b\in\partial i}\Lambda_{b\rightarrow i}^{\sigma_i} = Z^{\text{old}}\left(\prod_{b\in\partial i}\Lambda_{b\rightarrow i}^++\prod_{b\in\partial i}\Lambda_{b\rightarrow i}^-\right)$$ 와 같이 쓸 수 있다.

기능 노드 $a$의 기여가 없을 때 $\sigma_i$의 기댓값을 구해보자: \[ m_{i\to a} = \frac{\sum_{\vec{\sigma}} \sigma_i \exp\left[ -\beta H_{i\to a}(\vec{\sigma}) \right]}{\sum_{\vec{\sigma}} \exp\left[ -\beta H_{i\to a}(\vec{\sigma}) \right]}. \] 이때 $H_{i\to a}$는 상호작용 $a$가 없는 해밀토니안이다. $H_\text{cavity}$를 원래의 계에서 변수 노드 $i$를 그 주변의 기능 노드들 $b\in \partial i$와 함께 제외한 계라고 정의하면, 다음의 관계가 성립한다: $$H_{i\to a} = H_\text{cavity} -\sum_{b\in\partial i\setminus a}J_b \sigma_i \prod_{j\in\partial b\setminus i}\sigma_j.$$ 그러니까 위에 있던 그림과 비교해 보면, 우변의 두 번째 항은 기능 노드 $b$ 주변의 점선으로 표시된 상호작용, 기능 노드 $c$ 주변의 점선으로 표시된 상호작용들을 $H_\text{cavity}$에 추가하는데, 기능 노드 $a$ 주변의 점선들은 추가하지 않았다.

$\mathcal{B} \equiv \{ \sigma_j \vert j \in \partial b\setminus i; b \in \partial i \setminus a\}$로 정의해 놓자. 즉 공동의 경계에 놓인 변수 노드들의 집합인데, $a$에 연결된 것들은 여기에서 뺀다. 위 그림의 예에서라면 $\mathcal{B} = \{m, n, \ldots\}$이다.

• 인자 그래프
• TAP 방정식
• 스핀 유리

• Haiping Huang, Statistical Physics of Neural Networks (Springer, 2021).
• Marc Mézard and Andrea Montanari, Information, Physics, and Computation (Oxford University Press, Oxford, 2009).