수학:인자_그래프

Differences

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

Link to this comparison view

Both sides previous revision Previous revision
Next revision		 Previous revision
수학:인자_그래프 [2026/03/25 12:03] – [셈법의 요약] admin수학:인자_그래프 [2026/03/25 15:00] (current) – [간단한 예] admin
Line 10: Line 10:
  
 ======합/곱 셈법====== ======합/곱 셈법======
-====간단한 예====+=====간단한 예=====
 다음처럼 트리 구조를 가지는 인자 그래프를 생각해보자. 다음처럼 트리 구조를 가지는 인자 그래프를 생각해보자.
  
Line 49: Line 49:
 각각의 변수 $x_1, \ldots, x_5$가 $K$ 가지의 값을 가질 수 있다고 하면, 모든 $x_2$에 대해 $p(x_2)$를 구하려면 이 방법으로는 $K^5$에 비례하는 횟수의 계산이 필요하다. 각각의 변수 $x_1, \ldots, x_5$가 $K$ 가지의 값을 가질 수 있다고 하면, 모든 $x_2$에 대해 $p(x_2)$를 구하려면 이 방법으로는 $K^5$에 비례하는 횟수의 계산이 필요하다.
  
-반면 메시지 전달 형식으로 정리한 식에서는 각각의 메시지를 계산하는 데 $K^2$에 비례하는 계산 횟수가 필요할 뿐이다.+반면 메시지 전달 형식으로 정리한 식에서는 각각의 메시지를 계산하는 데 $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).$$   - 어떤 변수 노드 $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).$$   - 인자 $\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$로부터 인자 $\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$이고, 잎 노드가 변수 노드 $i$라면 거기에 연결된 단 하나의 링크를 통해 보내는 메시지의 값은 $m_{i\to \alpha}(x_i) = 1$이고,
 잎 노드가 인자 노드 $\alpha$라면 이 노드가 보내는 메시지의 값은 $m_{\alpha \to i} = f_\alpha(x_i)$이다. 잎 노드가 인자 노드 $\alpha$라면 이 노드가 보내는 메시지의 값은 $m_{\alpha \to i} = f_\alpha(x_i)$이다.
  
-===모든 노드에 대한 주변화===+====모든 노드에 대한 주변화====
 그래프의 모든 변수 노드에서 주변화 분포를 구하고자 할 때, 앞의 방법을 모든 변수 노드에 대해 반복하는 것은 비효율적이다. 이때에는 먼저 임의로 변수 노드 혹은 인자 노드를 루트로 지정하고 잎에서부터 루트로 메시지를 전달한다. 아래 그림의 예를 생각해보자. 그래프의 모든 변수 노드에서 주변화 분포를 구하고자 할 때, 앞의 방법을 모든 변수 노드에 대해 반복하는 것은 비효율적이다. 이때에는 먼저 임의로 변수 노드 혹은 인자 노드를 루트로 지정하고 잎에서부터 루트로 메시지를 전달한다. 아래 그림의 예를 생각해보자.
  
Line 97: Line 97:
 특정 노드 하나에 대해 구할 때와 비교해서, 모든 노드에 대해 구할 때 필요한 계산량은 고작 두 배에 불과하다. 특정 노드 하나에 대해 구할 때와 비교해서, 모든 노드에 대해 구할 때 필요한 계산량은 고작 두 배에 불과하다.
  
 +====정규화====
 +결합 확률분포가 정규화된 채 주어지지 않은 경우, 먼저 합/곱 셈법을 사용해 아무 변수 노드 $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).   * Christopher Bishop, //Pattern Recognition and Machine Learning// (Springer, New York, 2006).
  • 수학/인자_그래프.1774407813.txt.gz
  • Last modified: 2026/03/25 12:03
  • by admin