| Next revision | Previous revision |
| 신경망:공동_방법 [2022/12/05 14:43] – created jiwon | 신경망:공동_방법 [2023/09/05 15:46] (current) – external edit 127.0.0.1 |
|---|
| |
| =====공동 방법(cavity method)===== | =====공동 방법(cavity method)===== |
| 복원 과정에서 분배함수 $Z=\sum_{\vec\sigma}e^{-\beta H(\vec\sigma)}$를 계산해야 하는데 이 과정의 계산복잡도는 $2^N$로 매우 커서 메시지의 길이가 조금만 길어져버리면 계산할 수 없게 된다. 하지만 공동 방법(cavity method)를 이용하면 희박한 인자 그래프 모형에 대해 계산복잡도를 $=O(N)$까지 줄일 수 있다. | 위에서 언급했던 조건부 확률을 계산하려면 분배함수 $Z=\sum_{\vec\sigma}e^{-\beta H(\vec\sigma)}$를 계산해야 하는데 이 과정의 계산복잡도는 $2^N$로 매우 크다. 하지만 공동 방법(cavity method)를 이용하면 희박한 인자 그래프 모형에 대한 분배함수를 $=O(N)$까지 줄여 계산할 수 있다. |
| |
| 이를 위해 먼저 위 코드를 인자 그래프로 나타내어보자. 아래 그림에서 동그라미는 $\vec\sigma$에 해당하는 스핀 변수, 네모는 $\mathbf J$에 해당하는 수신한 메시지, 연결선은 변환 규칙에 따라 긋는다. | 이를 위해 먼저 위 코드를 인자 그래프로 나타내어보자. 아래 그림에서 동그라미는 $\vec\sigma$에 해당하는 스핀 변수, 네모는 $\mathbf J$에 해당하는 기능 노드, 연결선은 변환 규칙에 따라 긋는다. |
| |
| | {{ :신경망:fig2.1.png?500 |}} |
| |
| {{:신경망:fig2.1.png?600}} | 원래 그래프에 아래처럼 새로운 기능 노드 $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 |
| |
| |