Exact Inference는 왜 그렇게 어려운가

Bayesian Network에서 $p(L)$을 구하려면 나머지 변수 전부를 합산해야 한다. 변수가 $n$개, 각 기수(cardinality)가 $d$라면 단순 열거는 $O(d^n)$. 그런데 왜 어떤 모델은 선형 시간에 풀리고, 어떤 모델은 슈퍼컴퓨터로도 몇 주가 걸리는가?

분배법칙이 Inference를 가능하게 한다

Variable Elimination(VE)의 핵심은 합산 순서의 재배치다. Joint distribution의 factorization $p(x) = \prod_f \phi_f(x_{N(f)})$이 있을 때, 합산을 관련 factor 안으로 밀어 넣으면 된다.

$\sum_{x_2, x_3} \phi_{12}(x_1, x_2)\, \phi_{23}(x_2, x_3)\, \phi_3(x_3) = \sum_{x_2} \phi_{12}(x_1, x_2) \underbrace{\sum_{x_3} \phi_{23}(x_2, x_3)\, \phi_3(x_3)}_{\tau(x_2)}$

$\tau(x_2)$를 먼저 계산해두면 $x_3$은 사라진다. 이것이 “variable을 eliminate한다”는 의미다. 알고리즘은 단순하다.

for each x_i in elimination order σ:
    Φ_i = {φ ∈ Φ : x_i ∈ scope(φ)}
    τ   = product of all φ in Φ_i
    τ'  = sum out x_i from τ
    Replace Φ_i with τ'
Result: product of remaining factors

이 과정이 정확히 $\sum_{x_{-q}} \prod_f \phi_f(x)$를 계산한다는 것은 귀납법으로 증명된다. Step $i$ 후 factor set이 $x_i$를 정확히 marginalize한 것과 동등하며, 이를 반복하면 query variable 하나만 남는다.

Treewidth — 복잡도의 근본 척도

VE의 비용은 어디서 나오는가? 각 elimination step에서 생성되는 intermediate factor의 크기다. 같은 graph에서도 어떤 순서로 제거하느냐에 따라 이 크기가 극적으로 달라진다.

Naive Bayes 구조에서 $Y$의 children $X_1, X_2, X_3, X_4$를 생각하자.

• 순서 $(X_1, X_2, X_3, X_4, Y)$: 매 step에서 intermediate factor의 크기가 $O(|Y|)$.
• 순서 $(Y, X_1, X_2, X_3, X_4)$: $Y$를 먼저 제거하면 $\tau_1(X_1, X_2, X_3, X_4) = \sum_Y p(Y) \prod p(X_i|Y)$. 크기 $O(|X|^4)$.

이 차이를 포착하는 개념이 treewidth다.

$\text{tw}(\mathcal{G}) = \min_\sigma \max_i |\{x_i\} \cup N_\sigma(x_i)| - 1$

Elimination order $\sigma$에서 각 step의 clique 크기의 최대값을 minimizing한 것. 수치로 보면:

Graph	Treewidth	Inference complexity
Tree	1	$O(n d^2)$
Cycle $C_n$	2	$O(n d^3)$
Grid $L \times L$	$L$	$O(L^2 d^{L+1})$
Complete $K_n$	$n-1$	$O(d^n)$

Grid의 treewidth가 $L$에 선형이라는 사실이 핵심이다. $256 \times 256$ 이미지의 pixel-level MRF는 treewidth $\approx 256$, 이를 exact하게 풀면 $d^{257}$ 연산이 필요하다. 이것이 이미지 segmentation에서 exact inference가 불가능한 이유다.

Junction Tree — 여러 Query를 한 번에

Single marginal은 VE로 충분하다. 하지만 모든 변수의 marginal이 필요하다면 VE를 $n$번 반복하는 것은 중복 계산이 심하다. **Junction Tree(JT)**는 이 문제를 해결한다.

구성 절차는 네 단계다.

Moralize BN → Triangulate (fill-in edges) → Find maximal cliques → Build clique tree with RIP

Running Intersection Property(RIP): 각 변수 $v$에 대해 $v$를 포함하는 clique들의 집합이 clique tree에서 connected subtree를 이룬다.

RIP가 왜 중요한가? Message passing의 correctness가 여기에 달려 있다. 변수 $v$에 대한 정보가 tree를 따라 일관되게 흘러야 하는데, RIP가 없으면 중간 clique에서 $v$의 정보가 끊길 수 있다.

Shafer-Shenoy message는 다음과 같이 정의된다.

$\mu_{i \to j}(x_{S_{ij}}) = \sum_{x_{C_i \setminus S_{ij}}} \pi_i(x_{C_i}) \prod_{k \in N(i) \setminus \{j\}} \mu_{k \to i}(x_{S_{ik}})$

Root에서 collect → distribute 두 pass를 마치면 tree가 calibrated 상태가 된다.

$\sum_{x_{C_i \setminus S_{ij}}} b_i(x_{C_i}) = \sum_{x_{C_j \setminus S_{ij}}} b_j(x_{C_j}) \quad \forall (i, j)$

인접 clique의 belief가 separator 위에서 일치한다는 뜻이다. 이 상태에서 임의 변수의 marginal을 $O(d^{\omega+1})$로 즉시 조회할 수 있다. 전처리(triangulation + message passing) 비용은 $O(n \cdot d^{\omega+1})$ — VE와 같은 복잡도로 모든 marginal을 동시에 얻는다.

복잡도의 벽 — NP-Hard와 #P-Hard

Treewidth가 bounded이면 inference는 polynomial이다. 하지만 일반 그래프에서는 어떤가?

#P가 NP보다 엄격히 어려운 이유는 Toda’s theorem에서 확인된다: polynomial hierarchy 전체가 #P oracle로 polynomial time이다. MAP는 “해 하나의 존재”, Marginal은 “모든 해의 가중합” — 후자가 근본적으로 더 어렵다.

Roth(1996)와 Dagum-Luby(1997)는 더 강한 결과를 보였다. Approximate marginal도 multiplicative factor 이내로 근사하는 것이 NP-hard라는 것이다. 이것이 variational inference와 MCMC가 이론적 보장 없이도 실용적으로 정당화되는 이유다 — exact도, 일반적 approximation도 불가능하기 때문에, 경험적으로 잘 작동하는 방법론이 선택지가 된다.

정리

• VE는 분배법칙으로 $O(d^n)$을 $O(n d^{w^*})$으로 줄인다. 핵심은 elimination ordering이다.
• Treewidth는 graph의 “tree-like 정도”를 측정하며, 정확히 inference 복잡도를 결정한다. Grid의 treewidth는 $L$에 선형이고, 이것이 image MRF에서 exact inference가 불가능한 구조적 이유다.
• Junction Tree는 전처리 한 번으로 모든 marginal을 calibrated belief에서 조회하게 한다. RIP가 message passing의 정확성을 보장한다.
• 일반 그래프의 exact marginal inference는 #P-hard이고 근사조차 NP-hard다. 이 벽이 variational inference와 MCMC의 이론적 존재 이유다.

이 복잡도 구조를 이해한 다음 자연스럽게 나오는 질문 — “그렇다면 어떻게 근사하는가?” — 는 Mean-Field Variational Inference에서 다룬다.