[PRML] 8.4.4 Sum-Product Algorithm

그래프에서 추론문제는 몇몇 노드들이 관측되었을 대, 하나의 노드 또는 여러 개의 노드들의 사후 분포를 계산하는 것이다.

인자 그래프를 바탕으로 트리 구조 그래프 추론 문제를 해결하는 알고리즘이 합-곱 알고리즘이다.

 

 

이 파트에서 가정은 다음과 같다.

• 모델에 존재하는 모든 랜덤변수들은 이산(discrete) 랜덤변수이다. 
• 따라서 주변화(marginalize)는 합산 시그마 기호를 통해 표현하게 된다. 

 

 

먼저 합의 법칙에서 주변확률을 구하기 위해서는 다음과 같이 결합확률을 특정 랜덤변수에 대해서 주변화를 진행했다.

$$ p(x) = \sum_y p(x, y) $$ 

 

그래프 상의 랜덤변수들이 $\mathbf x = \{x_1, x_2, x_3, ..., x_n\}$으로 주어졌을 때, 합의 법칙을 활용해서 그래프 상의 특정 랜덤변수 노드 $x$의 주변확률분포 $p(x)$를 구하는 방식은 다음과 같다. 

$${p(x) = \sum_{\mathbf x \backslash x} p(\mathbf x)} $$

$x \backslashmathbf x$ 기호는 $x$를 제외한 모든 변수들을 지칭하는 것이다. 핵심 아이디어는 인자그래프 표현식을 사용해서 $p(\mathbf x)$를 치환하고, 그 후 덧셈과 곱셈들을 교환해서 효율적인 알고리즘을 구하는 것이다.

 

 위 그림에서 그래프의 일부를 살펴보자. 그래프가 트리구조로 인해 결합 분포가 인자들의 묶음으로 분할될 수 있는 것이 보인다. 왼쪽의 그룹은 변수 노드 $x$의 이웃 인자 노드들 각각과 연관되어 있다. 따라서 결합 분포는 다음과 같이 곱셈의 형태로 표현 가능하다.

$$ p(\mathbf x) = \prod_{s \in ne(x)} F_s(x, X_s) $$