접합 트리 알고리즘

1. 개요

접합 트리 알고리즘 Junction Tree Algorithm
목적	그래프 모형의 모든 주변분포를 정확히 계산
준비	도덕화 → 삼각화 → 최대 클리크 → 클리크 나무
핵심 성질	달리는 교집합(running intersection)
전파	모으기(collect) + 나누기(distribute), 간선당 메시지 2개
비용	최대 클리크 크기에 지수적 (트리폭 + 1)
제안	로리첸·슈피겔할터 (1988)

순환이 있어서 메시지가 빙빙 돈다고? 노드를 뭉쳐서 나무로 만들면 된다. 대가는 뭉친 덩어리 크기의 지수함수다.

접합 트리 알고리즘(junction tree algorithm, 클리크 트리·조인 트리 알고리즘)은 순환이 있는 베이지안 네트워크나 마르코프 확률장을 변수 묶음(클리크)들의 나무로 바꾼 뒤, 그 나무 위에서 메시지를 한 번 모으고 한 번 나눠 모든 변수의 사후 주변분포를 정확히 얻는 추론 알고리즘이다. 1988년 로리첸과 슈피겔할터가 흉부 질환 진단 예제와 함께 발표했고, 셰이퍼·셰노이(1990)와 HUGIN 그룹(옌센 외)이 변형을 정리했다.

믿음 전파는 나무 모양 그래프에서만 정확하다. 순환이 있으면 근사(루피 BP)가 되거나 발산한다. 접합 트리는 이 문제를 그래프를 바꿔서 푼다. 순환을 만드는 변수들을 하나의 “슈퍼 노드”로 묶으면 묶음 사이의 연결은 나무가 되고, 나무 위의 BP는 다시 정확해진다. 묶음의 크기만큼 표가 커지는 것이 대가다. 그 크기를 좌우하는 그래프 양이 트리폭이고, 이 문서의 절반은 사실 “트리폭을 어떻게 작게 잡느냐”의 이야기다. 그리고 그 이야기는 희소 행렬의 촐레스키 분해에서 채움(fill-in)을 줄이는 이야기와 놀랄 만큼 똑같다.

2. 준비 단계 — 그래프를 나무로

1. 도덕화. 베이지안 네트워크라면 같은 자식을 둔 부모끼리 선을 잇고 화살표를 지운다. 조건부 확률표 $p(v\mid\mathrm{pa}(v))$ 하나가 $\{v\}\cup\mathrm{pa}(v)$ 전체에 걸친 함수이므로, 그 변수들이 반드시 한 클리크에 함께 들어가야 하기 때문이다. d-분리의 도덕화 판정과 같은 연산이다.

2. 삼각화. 길이 4 이상의 순환마다 지름길(현)이 있도록 간선을 더한다. 이런 그래프를 현 그래프(chordal graph)라 한다. 실제로는 소거 순서를 하나 정하고, 변수를 하나씩 지우며 그 이웃끼리 모두 잇는다. 이때 새로 생기는 간선이 채움 간선이다. 가우스 소거로 희소 대칭 행렬을 분해할 때 생기는 채움 패턴과 정확히 같은 그래프 연산이다.

3. 최대 클리크. 현 그래프의 극대 클리크는 소거 과정에서 “지우는 변수 + 그 순간의 이웃”으로 바로 나온다.

4. 클리크 나무. 클리크를 노드로, 두 클리크의 교집합 크기를 간선 가중치로 둔 그래프에서 최대 신장 트리를 고르면 아래 성질을 만족하는 나무가 된다(최소 신장 트리의 부호만 바꾼 문제다).

달리는 교집합 성질. 어떤 변수 $v$ 가 두 클리크 $C_i, C_j$ 에 함께 들어 있으면, 둘 사이 나무 경로 위의 모든 클리크에도 $v$ 가 들어 있다.

이 성질이 있어야 국소 메시지만 주고받아도 같은 변수에 대한 믿음이 나무 전체에서 일관된다. 인접한 두 클리크의 교집합 $S_{ij}=C_i\cap C_j$ 를 분리 집합(separator)이라 부른다.

3. 전파 — 모으기와 나누기

각 조건부 확률표(또는 인자)를 그 변수들을 담은 클리크 하나에 곱해 넣어 클리크 퍼텐셜 $\psi_C$ 를 만든다. 관측된 변수는 해당 값 외 성분을 0으로 만드는 지시함수를 곱한다. 그 다음 셰이퍼-셰노이 방식이면 클리크 $i$ 가 이웃 $j$ 에게 보내는 메시지는

$$m_{i\to j}(S_{ij})=\sum_{C_i\setminus S_{ij}}\psi_{C_i}\prod_{k\in\mathcal N(i)\setminus\{j\}} m_{k\to i}$$

이다. 루트를 하나 정하고 잎에서 루트로 모으기, 루트에서 잎으로 나누기를 하면 간선마다 양방향 메시지가 한 번씩, 총 $2(|\mathcal C|-1)$ 개로 끝난다. 끝나면 각 클리크의 믿음 $\beta_C=\psi_C\prod_k m_{k\to C}$ 가 그 클리크 변수들의 결합 사후분포(정규화 전)이고, 정규화 상수는 증거 확률 $P(\text{증거})$ 다. HUGIN 방식은 분리 집합에 퍼텐셜 $\phi_S$ 를 저장해 두고 $\psi_j\leftarrow\psi_j\,\phi_S^{\text{새}}/\phi_S^{\text{옛}}$ 로 갱신한다. 나눗셈이 들어가는 대신 같은 곱을 다시 하지 않아 대체로 빠르다.

합 $\sum$ 을 $\max$ 로 바꾸면 같은 틀이 가장 그럴듯한 전체 배정(MAP)을 준다. 은닉 마르코프 모형에서 전방-후방 알고리즘이 비터비 알고리즘으로 바뀌는 것과 같다.

4. 작은 예로 검산

가장 작은 순환인 다이아몬드 $A\to B$, $A\to C$, $B\to D$, $C\to D$ 를 보자. 무방향으로 보면 $A\!-\!B\!-\!D\!-\!C\!-\!A$ 의 4-순환이라 BP가 정확하지 않다. 도덕화로 $B\!-\!C$ 가 이어지면 이미 현 그래프가 되고, 클리크는 $\{A,B,C\}$ 와 $\{B,C,D\}$, 분리 집합은 $\{B,C\}$ 다.

확률은 $P(A{=}1)=0.3$, $P(B{=}1\mid A)=(0.1,\,0.7)$, $P(C{=}1\mid A)=(0.2,\,0.6)$, $P(D{=}1\mid B,C)$ 는 $(B,C)=(0,0),(0,1),(1,0),(1,1)$ 에 대해 $0.05,\,0.6,\,0.7,\,0.95$ 로 두고 $D=1$ 을 관측했다. 클리크 퍼텐셜은 $\psi_1=P(A)P(B\mid A)P(C\mid A)$, $\psi_2=P(D{=}1\mid B,C)$ 이고 메시지는 각각 $2\times2$ 표 하나다.

양	전수 합산	접합 트리
$P(D=1)$	0.3660	0.3660 (두 클리크 모두)
$P(A=1\mid D=1)$	0.5811	0.5811
$P(B=1\mid D=1)$	0.6311	0.6311
$P(C=1\mid D=1)$	0.6585	0.6585

사전확률 $P(A{=}1)=0.3$ 이 $D$ 하나를 보고 0.58까지 오른다. 이 문서를 쓰며 파이썬으로 $2^4$ 항 전수 합산과 메시지 두 개짜리 전파를 각각 돌려 소수 넷째 자리까지 일치하는 것을 확인했다. 변수가 수백 개가 되면 전수 합산은 $2^{n}$ 이지만 접합 트리는 “클리크 수 × $2^{\text{클리크 크기}}$” 다.

5. 비용은 트리폭이 정한다

가장 큰 클리크의 크기가 $w+1$ 이면 표 하나가 $k^{w+1}$ 칸($k$ 는 변수당 상태 수)이고, 전체 비용은 대략 $|\mathcal C|\,k^{w+1}$ 이다. 모든 삼각화 중 최대 클리크 크기를 최소로 만든 값에서 1을 뺀 것이 그래프의 트리폭이다.

• 나무·사슬은 트리폭 1이다. 은닉 마르코프 모형의 전방-후방, 선형 가우스 상태공간의 칼만 필터+RTS 평활기가 정확히 이 경우의 접합 트리다(가우스판에서는 표 대신 평균·공분산이 오간다).
• $n\times n$ 격자의 트리폭은 $n$ 이다. 이진 변수 $32\times32$ 이징 모형이면 클리크 표가 $2^{33}$ 칸 근처라, 접합 트리로 정확히 푸는 것은 사실상 끝이다. 그래서 격자 모형은 마르코프 연쇄 몬테카를로나 변분 추론으로 간다.
• 최적 삼각화(트리폭 계산)를 찾는 것 자체가 NP-난해다(안보리 외 1987). 실전은 휴리스틱이다. 최소 채움(지울 때 새 간선이 가장 적게 생기는 변수부터), 최소 차수(이웃이 가장 적은 변수부터), 큰 그래프에는 중첩 절단을 쓴다.

마지막 줄은 최소차수 순서화와 중첩절단 문서의 내용과 같은 알고리즘이다. 희소 촐레스키에서 행렬의 비영 패턴 그래프를 소거할 때 생기는 채움 그래프는 현 그래프이고, 그 최대 클리크가 다중 프론트 솔버의 프론트 행렬, 클리크 나무가 소거 트리(정확히는 그 슈퍼노드판인 어셈블리 트리)다. 확률 추론과 희소 직접 솔버는 같은 조합론 문제를 서로 다른 반환(semiring)으로 푸는 셈이다.¹

일반 베이지안 네트워크의 정확 추론은 NP-난해이므로(쿠퍼 1990) 접합 트리가 “느린 것”은 알고리즘 잘못이 아니다. 트리폭이 작은 문제를 다항 시간에 푼다는 것이 이 알고리즘이 보장하는 전부이자 최선이다.²

6. 실전에서

• 한 번 컴파일, 여러 번 질의. 삼각화·클리크 나무 구축은 그래프 구조에만 의존하므로 미리 해 둔다. 증거가 바뀔 때마다 전파만 다시 하면 되고, 한 번 전파로 모든 변수의 주변분포가 나온다. 변수 하나만 필요하면 변수 제거가 더 싸지만, 전부 필요하면 접합 트리가 이긴다.
• 수치 안정. 증거가 많으면 증거 확률이 $10^{-300}$ 아래로 내려가 언더플로가 난다. 메시지마다 정규화하고 로그 상수를 따로 누적하거나, 로그 공간에서 log-sum-exp로 계산한다.
• 연속 변수. 가우스 변수는 표 대신 정준형 $(K,h,g)$ 를 써서 같은 틀이 돈다. 이산-연속 혼합은 강한 접합 트리라는 제약된 소거 순서가 필요하고, 비가우스 연속은 정확 추론이 거의 불가능해 표본추출로 넘어간다.
• 도구. HUGIN·Netica 같은 상용 도구와 pgmpy, libDAI 등 오픈소스가 구현을 제공한다. 공학 쪽에서는 고장 수목을 베이지안 네트워크로 옮긴 신뢰성 분석, 센서 융합, 구조 건전성 모니터링의 손상 진단 모형에서 쓰인다.³

7. 관련 문서

• 베이지안 네트워크 · 마르코프 확률장 · d-분리 · 믿음 전파
• 은닉 마르코프 모형 · 칼만 필터 · 이징 모형 · 변분 추론
• 촐레스키 분해 · 최소차수 순서화 · 중첩절단 · 소거 트리
• 변수 제거 · 트리폭 · 최소 신장 트리

8. Footnotes

1. 이 대응을 처음 보면 꽤 킹받는다. 통계 쪽 사람들이 “삼각화 휴리스틱”을 논문으로 쓰는 동안 수치선형대수 쪽 사람들은 “순서화 휴리스틱”을 논문으로 쓰고 있었고, 둘은 상당 기간 서로를 거의 인용하지 않았다. ↩

2. 로리첸-슈피겔할터 논문은 왕립통계학회 토론 논문으로 실려서, 본문 뒤에 수십 쪽짜리 토론자 코멘트와 저자 답변이 붙어 있다. 1988년 당시 통계학계가 “전문가 시스템에 확률을 제대로 쓰는 법”을 놓고 얼마나 뜨거웠는지 보여 주는 사료다. ↩

3. 실무자의 국룰: 모델러가 그린 그래프의 트리폭부터 재라. 화살표를 “혹시 모르니까” 하나씩 더 그리다 보면 트리폭이 2에서 15로 뛰고, 어제까지 밀리초에 끝나던 추론이 메모리 부족으로 죽는다. ↩