신경망:공동_방법 [statphys]

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
=====소울라스 코드=====

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

$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$에서 무작위로 몇 개의 비트를 고른 뒤 이들을 곱하는 것으로 정의한다. 이를 수식으로 쓰면
$$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(-\beta H(\sigma))$$
를 계산해서 가장 그럴듯한 $\sigma$를 찾아내는 것으로 이해할 수 있다.

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

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

{{ :신경망:fig2.1.png?500 |}}

원래 그래프에 아래처럼 새로운 기능 노드 $a$를 추가한다면
{{ :신경망:fig2.2.png?500 |}}
전체 해밀토니안은
$$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\}}\exp\left(\beta J_a\prod_{i\in\partial a}\sigma_i\right)\sum_{\{\sigma_i\vert i\not\in\partial a\}}\frac{\exp(-\beta H^{\text{old}})}{Z^{\text{old}}}
\end{align*}
가 된다. 여기서 $\{\sigma_i\vert i\in\partial a\}$는 노드 $a$와 인접한 스핀변수를 의미한다. 만약 $a$와 인접한 노드들 사이의 상관관계가 적다면 우변의 마지막 항을
$$\sum_{\{\sigma_i\vert i\not\in\partial a\}}\frac{\exp(-\beta H^{\text{old}})}{Z^{\text{old}}}\equiv 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)를 이용해 $q_{i\rightarrow a}(\sigma_i) = (1+\sigma_i m_{i\rightarrow a})/2$로 쓰면,
\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\}}\cosh(\beta J_a)\left(1+\prod_{i\in\partial a}\sigma_i\tanh(\beta J_a)\right)\prod_{i\in\partial a}\frac{1+\sigma_im_{i\rightarrow a}}2\\
\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) = 1$$
$$\tanh(\beta J_a) \sum_{\{\sigma_i\vert i\in\partial a\}}\prod_{i\in\partial a}\left(\frac{\sigma_i+m_{i\rightarrow a}}2\right) = \tanh(\beta J_a)\prod_{i\in\partial a}m_{i\rightarrow a}$$
분배함수는
\begin{align*}
Z^{\text{new}}
=&Z^{\text{old}}\cosh(\beta J_a)\left(1+\tanh(\beta J_a)\prod_{i\in\partial a}m_{i\rightarrow a}\right)
\end{align*}
가 된다.

마찬가지로 아래 그림의 회색 영역처럼 스핀 변수 하나와 인접한 기능 노드들을 한꺼번에 추가하는 경우도 생각해볼 수 있을 것이다.
{{ :신경망:fig2.3.png?500 |}}
이 때 새로운 해밀토니안은
$$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*}
가 된다. 위에서와 같이
$$P_{\text{cavity}}(\{\sigma_j\vert j\in\partial b\backslash i;b\in\partial i\}) = \sum_{\{\sigma_j\vert j\not\in\partial b\backslash i;b\not\in\partial i\}}\frac{\exp\left(-\beta H^{\text{old}}\right)}{Z^{\text{old}}}\approx \left(\prod_{j\in\partial b\backslash i}\prod_{b\in\partial i}q_{j\rightarrow b}(\sigma_j)\right)$$
로 근사하면
\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}}(\{\sigma_j\vert j\in\partial b\backslash i;b\in\partial i\})\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_{j\in\partial b\backslash i}\prod_{b\in\partial 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_i}\prod_{b\in\partial i}\left[\sum_{\{\sigma_j\vert j\in\partial b\backslash i\}}\prod_{j\in\partial b\backslash i}q_{j\rightarrow b}(\sigma_j)\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\}}\prod_{j\in\partial b\backslash i}q_{j\rightarrow b}(\sigma_j)\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\}}\prod_{j\in\partial b\backslash i}\frac{1+\sigma_jm_{j\rightarrow b}}2\cosh(\beta J_b)\left(1+\sigma_i\prod_{j\in\partial b\backslash i}\sigma_j\tanh(\beta J_b)\right)
\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 = 1$$
\begin{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\sigma_i\sigma_j\tanh(\beta J_b)\\
=&\sigma_i\tanh(\beta J_b)\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\tanh(\beta J_b)\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)$$
와 같이 쓸 수 있다.

====참고문헌====
  * Haiping Huang, //Statistical Physics of Neural Networks// (Springer, 2021).