Overview

Loopy Belief Propagation의 문제를 보완한 Message Passing 알고리즘이다.

Junction Tree Algorithm

Junction Tree Algorithm(JTA)은 여러 변수를 하나의 Cluster로 묶어 Tree 구조로 만들어 Cluster Tree에서 Message Passing을 수행하는 알고리즘이다.

• Cycle을 가지고 있는 그래프를 Tree구조로 변환하여 추론할 수 있다.

• 진행 단계

  1. Triangulation

     Chord를 추가해서 cycle을 triangle으로 분해하는 과정이다.

  2. Maximal Clique 추출

     더 이상 다른 노드를 추가할 수 없는 clique를 구별하여 Maximal Clique를 추출하여 Junction Tree의 노드로 만든다.

  3. Junction Tree 구성

     Maximal Clique를 연결하고, 인접한 clique들의 교집합을 Separator로 정의한다. Separator는 정보 전달 통로의 역할을 한다.

  4. Message Passing

     $\displaystyle m_{i→j}(S_{ij}) = \sum_{C_i\backslash S_{ij}} \varPhi_i(C_i) \prod_{k \in N(i)\backslash j} m_{k→i}(S_{ki})$

  5. Marginal 계산

     $\displaystyle b_i \propto \varPhi_i(C_i) \prod_{k \in N(i)} m_{k→i}S(ki)$

     $\displaystyle \therefore P(X_i) = \sum_{X'} b_i(C_i)$

• 예제