Geometry and factorization of multivariate Markov chains with applications to MCMC acceleration and approximate inference

이 논문은 **다변량 마르코프 체인 (Multivariate Markov Chains)**의 전이 행렬 (transition matrices) 에 대한 기하학적 구조와 **분해 가능성 (factorizability)**을 분석하고, 이를 MCMC 가속화 및 근사 추론에 적용하는 방법을 제시합니다. 저자들은 유도된 체인이 정보 기하학 (Information Geometry) 관점에서 **KL 발산 (Kullback-Leibler divergence)**에 대한 정보 투영 (information projection) 으로 해석될 수 있음을 증명하며, 이를 통해 엔트로피율의 하부 모듈성 (submodularity) 과 Han-Shearer 유형의 부등식을 유도합니다.

주요 내용과 기술적 요약은 다음과 같습니다.

---

1. 연구 배경 및 문제 정의

• 문제: 다변량 상태 공간 (Product space) $X = X^{(1)} \times \dots \times X^{(d)}$ 위에서 정의된 마르코프 체인 $P$가 주어졌을 때, 이 체인과 가장 가까운 **독립적인 마르코프 체인 (Product chain)**은 무엇이며, 그 거리는 어떻게 정의할 수 있는가?
• 목표:
  1. 주어진 체인 $P$와 독립 체인 사이의 '거리'를 정보 발산 (f-divergence) 을 통해 정의하고, 그 기하학적 성질을 규명한다.
  2. 이 이론을 바탕으로 MCMC 알고리즘 (예: Swapping Algorithm) 의 **혼합 시간 (Mixing time)**을 단축하는 새로운 샘플러를 설계한다.
  3. 고차원 상태 공간에서의 필터링 (Filtering) 문제를 해결하기 위해 계산 비용을 줄이는 근사 필터를 제안한다.

2. 주요 방법론 및 이론적 기여

2.1. 독립성까지의 거리와 정보 투영 (Distance to Independence)

• 정의: 주어진 전이 행렬 $P$와 $\pi$-정적 분포 하에서, 각 좌표 $i$에 대한 전이 행렬 $L_i$들의 텐서 곱 $\bigotimes L_i$로 구성된 독립 체인과의 거리를 다음과 같이 정의합니다.
  $$I^\pi_f(P) := \min_{L_i \in \mathcal{L}(X^{(i)})} D^\pi_f(P \parallel \bigotimes_{i=1}^d L_i)$$
  여기서 $D^\pi_f$는 $\pi$에 대한 f-발산입니다. 특히 KL 발산 ($f(t)=t \ln t$) 인 경우, 이 거리는 **상호 정보량 (Mutual Information)**의 일반화로 해석됩니다.
• 피타고라스 항등식 (Pythagorean Identity): KL 발산의 경우, 가장 가까운 독립 체인은 각 좌표의 마진 전이 행렬 (Marginal transition matrix) $P^{(i)}_\pi$의 텐서 곱 $\bigotimes P^{(i)}_\pi$임을 증명했습니다.
  $$D^\pi_{KL}(P \parallel \bigotimes L_i) = D^\pi_{KL}(P \parallel \bigotimes P^{(i)}_\pi) + \sum D^{\pi(i)}_{KL}(P^{(i)}_\pi \parallel L_i)$$
  이는 $P$를 독립 체인 공간으로 투영한 것이 $P^{(i)}_\pi$임을 의미하며, 이는 **정보 투영 (Information Projection)**의 개념과 일치합니다.

2.2. Leave-S-out 및 Keep-S-in 전이 행렬

• 개념: $S$는 좌표의 부분집합일 때, $S$를 제외한 나머지 좌표에 대한 전이 행렬을 Leave-S-out, $S$만 남긴 전이 행렬을 Keep-S-in으로 정의합니다.
• Rao-Blackwellization 유사성: 이러한 투영된 체인들은 원래 체인 $P$의 조건부 기대값으로 해석될 수 있으며, 통계적 효율성을 높이는 Rao-Blackwellization 과 유사한 성질을 가집니다.
• 혼합 시간 비교: 투영된 체인 $P^{(S)}$는 원래 체인 $P$보다 **스펙트럼 갭 (Spectral gap)**이 크고, **혼합 시간 (Mixing time)**이 짧다는 것을 증명했습니다. 즉, 투영을 통해 체인의 수렴 속도가 가속화됩니다.
• 하부 모듈성 (Submodularity): 엔트로피율 $H(P^{(S)})$와 독립성까지의 거리 $I^\pi(P^{(S)})$가 집합 $S$에 대해 하부 모듈성 (submodular) 또는 초가부 모듈성 (supermodular) 성질을 가짐을 보였습니다.

3. 알고리즘적 응용 및 결과

3.1. MCMC 가속화: 투영 샘플러 (Projection Sampler)

• 기존 방법의 한계: Lifted MCMC 나 Swapping Algorithm 은 고차원 또는 다중 모드 (Multimodal) 분포에서 혼합이 느리거나 국소 최적점에 갇히는 문제가 있습니다.
• 제안 방법: Swapping Algorithm 에서 가장 높은 온도 (또는 첫 번째 좌표) 를 매 단계마다 **정적 분포 (Stationary distribution) 에서 재샘플링 (Resampling)**하는 방식을 도입합니다. 이는 $P^{(1)}$ (Keep-1-in) 또는 $P^{(-1)}$ (Leave-1-out) 투영 체인을 구현하는 것과 동일합니다.
• 이론적 성과:
  • 제안된 투영 샘플러는 기존 Swapping Algorithm 대비 혼합 시간이 $d$ (차원) 와 $k$ (온도 개수) 에 비례하여 가속화됨을 증명했습니다.
  • 특히 $d$-온도 Swapping Algorithm 의 경우, 투영 샘플러는 $O(d \cdot N)$만큼의 속도 향상을 보입니다 ($N$은 상태 공간 차원).
• 실험 결과: 바이모달 (Bimodal) 타겟 분포에 대한 수치 실험에서, 기존 알고리즘은 한 모드에 갇히는 반면, 투영 샘플러는 두 모드 사이를 효과적으로 이동하여 정확한 분포를 샘플링함을 확인했습니다.

3.2. 근사 추론: 팩터드 필터링 (Factored Filtering)

• 문제: Ising Hidden Markov Model (HMM) 과 같은 고차원 필터링 문제에서 정확한 필터링은 상태 공간 크기가 $2^d$로 지수적으로 증가하여 계산 불가능합니다.
• 제안 방법: 예측 단계에서 결합된 전이 커널 $P$를 KL 투영된 곱 형태 (Product form) $\hat{P} = \bigotimes P^{(i)}$로 근사합니다.
  • 계산 효율성: 정확한 필터는 $O(2^d)$의 비용이 들지만, 제안된 팩터드 필터는 $O(d)$의 선형 비용으로 계산 가능합니다.
  • 오차 추정: 근사 오차는 독립성까지의 거리 $I^\pi(P)$로 정량화할 수 있으며, 이는 필터의 정확도를 진단하는 지표로 사용됩니다.
• 실험 결과: 다양한 차원 ($L \times L$ 격자) 에서 실험한 결과, 팩터드 필터는 높은 차원에서도 실시간으로 실행 가능한 반면, 정확한 필터는 $L=5$ 이상에서 계산이 불가능해졌습니다. 또한, 독립성 거리가 실제 오차와 강한 상관관계를 보였습니다.

4. 결론 및 의의

이 논문은 마르코프 체인의 정보 기하학적 구조를 체계적으로 분석하여 다음과 같은 기여를 했습니다:

1. 이론적 통찰: 다변량 마르코프 체인의 분해 가능성과 독립성 거리를 정보 투영의 관점에서 정립하고, Han-Shearer 부등식과 엔트로피율의 하부 모듈성을 유도했습니다.
2. 알고리즘 혁신: MCMC 의 혼합 속도를 획기적으로 개선하는 투영 샘플러를 제안하여, 기존 알고리즘의 한계를 극복하는 구체적인 방법을 제시했습니다.
3. 확장성 있는 추론: 고차원 필터링 문제를 해결하기 위한 선형 시간 팩터드 필터를 개발하여, 근사 오차를 정량적으로 추적 가능한 상태로 만들었습니다.

이 연구는 통계 물리학, 기계 학습 (MCMC, 필터링), 정보 이론의 교차점에서 마르코프 체인의 효율적인 설계와 분석을 위한 강력한 이론적 틀과 실용적 도구를 제공합니다.