Overview

Factor Graph는 Variable과 factor를 분리하여 확률분포의 factorization을 표현하고, 이를 기반으로 효율적인 추론을 수행하기 위한 그래프 표현법이다.

Factor Graph

Factor Graph(인자 그래프)는 복잡한 확률분포를 Variable과 Factor로 분해하여 표현하는 bipartite graph(이분 그래프)이다.

• 그래프 표현

  $X_1 - f_1 - X_2 - f_2 - X_3$

  • $X$: Variable Nodes, 변수
  • $f$: Factor Nodes, 함수
  • $X$와 $f$ 간 연결: 해당 factor가 그 variable을 포함한다는 의미

• 수학적 표현

  $P(X_1, X_2, X_3) \propto f_1(X_1, X_2) f_2(X_2, X_3)$

• Edge

  Factor Graph는 Variable과 Factor 사이에만 edge가 존재한다.

  

  • Variable - Factor - Variable 형태이다.
  • Variable - Variable 또는 Factor - Factor는 연결되지 않는다.

Factorization

Factor Graph는 확률분포를 여러 factor의 곱으로 표현하는 것이 핵심이다. 일반적으로 다음과 같이 표현할 수 있다.

$\displaystyle P(X_1, …, X_n) = \frac 1 Z \prod_{k=1}^K f_k(X_k)$

여기서 $Z$는 normalization constant이다.

$\displaystyle Z = \sum_{x_1,…,x_n} \prod_{k=1}^{K} f_k(x_k)$

따라서

$\displaystyle P(x_1,…,x_n) = \frac {\prod_k f_k(x_k)} {Z}$