기술 요약: 이산적 이중 난해 문제(Discrete Doubly Intractable Problems)를 위한 공액 일반화 베이즈 추론

1. 문제 정의

본 논문은 이산적 통계 모델에서 흔히 발생하는, 우도(likelihood)와 사후 분포(posterior distribution)가 모두 정규화되지 않은 형태(unnormalized form)로만 존재하는 **이중 난해 문제(doubly intractable problems)**를 다룬다. 구체적으로, 모델의 우도 $p_\theta(x) = \tilde{p}_\theta(x)/Z(\theta)$의 정규화 상수(partition function) $Z(\theta)$는 상태 공간의 합산이 매우 크거나 무한하여 계산하거나 효율적으로 근사할 수 없다.

표준적인 베이즈 추론에서는 사후 분포가 우도와 사전 분포의 곱에 비례한다. 그러나 $Z(\theta)$가 난해할 경우, 사후 분포의 정규화 상수는 데이터와 파라미터의 함수로서 이 또한 난해해진다. 기존의 해결책들은 대개 다음과 같다:

• 보조 변수를 이용한 MCMC (예: Exchange 알고리즘): 계산 비용이 많이 들고 튜닝이 필요하다.
• 근사법 (예: 의사 우도(pseudo-likelihood), 변분 베이즈(variational Bayes)): 편향(bias)이나 오설정(misspecification)을 초래할 수 있다.
• 이산 피셔 발산(Discrete Fisher Divergence, DFD) (Matsubara et al., 2023)과 같은 발산을 사용하는 일반화 베이즈 추론(Generalized Bayesian Inference, GBI): DFD-Bayes는 $Z(\theta)$를 계산하지 않아도 되지만, **공액 사후 분포(conjugate posteriors)**를 생성하지 못한다. 결과적으로 여전히 MCMC 샘플링이 필요하며, 이는 고차원에서의 느린 혼합(mixing), 다봉성(multi-modality), 수렴 확인의 필요성 등의 문제를 겪는다.

핵심 과제는 GBI의 계산 효율성을 유지하면서도, 공액성(conjugacy)(폐쇄형 또는 깁스 기반 업데이트)을 달성함으로써 이산 난해 모델에서 MCMC를 제거하는 방법을 개발하는 것이다.

2. 방법론

2.1 로그 비율 매칭(Log-Ratio Matching, LRM) 발산

저자들은 일반화 사후 분포를 구축하기 위해 **로그 비율 매칭(LRM)**이라는 새로운 통계적 발산을 제안한다.

• 매칭 세트(Matching Sets): 데이터 포인트 $x$에 대해, 매칭 세트 $M(x)$는 인접한 상태들의 유한 집합 $\{M_j(x)\}_{j \in J}$로 정의된다. 이 집합은 데이터 구조(예: 격자에서의 비트 반전 또는 카운트 증가)를 기반으로 구성된다.
• 정의: 데이터 생성 과정 $q_0$와 모델 $p_\theta$ 사이의 LRM 발산은 모델과 데이터의 로그 비율 간의 제곱 차이의 기댓값으로 정의된다:
  $$D_{LRM}(q_0 \| p_\theta) = \mathbb{E}_{x \sim q_0} \left[ \frac{1}{|M(x)|} \sum_{x' \in M(x)} \left( \log \frac{p_\theta(x')}{p_\theta(x)} - \log \frac{q_0(x')}{q_0(x)} \right)^2 \right]$$
• 핵심 속성: 다른 발산들과 달리, $D_{LRM}$은 비율 $p_\theta(x')/p_\theta(x)$가 $Z(\theta)$를 상쇄하기 때문에 $Z(\theta)$에 의존하지 않는다.
• 이론적 타당성: 매칭 세트가 상태 공간에 대해 **연결된 그래프(connected graph)**를 유도한다는 가정하에, $D_{LRM}(q_0 \| p_\theta) = 0$인 것은 $q_0 = p_\theta$인 것과 동치이다.

2.2 LRM-Bayes 사후 분포

LRM 발산을 사용하여, 저자들은 데이터 $\{x_i\}_{i=1}^n$과 추정된 확률 질량 함수 $\hat{q}$(통상적으로 라플라스 평활화 사용)를 기반으로 하는 손실 함수 $L_{LRM}(\theta)$와 그에 대응하는 추정량 $\hat{L}_{LRM}^n(\theta)$를 정의한다. LRM-Bayes 사후 분포는 다음과 같이 정의된다:
$$\hat{\pi}_M^\beta(\theta; \{x_i\}) \propto \exp\left( -\beta n \hat{L}_{LRM}^n(\theta) \right) \pi(\theta)$$
여기서 $\beta > 0$은 스케일링 파라미터이다.

2.3 지수 가족을 위한 공액성

주요 이론적 돌파구는 이산 지수 가족 모델 $p_\theta(x) \propto \exp(\eta(\theta)^\top T(x) + B(x))$에 대해 LRM 손실이 자연 파라미터 $\eta(\theta)$에 대해 **이차 형식(quadratic)**이라는 점이다.

• 손실 구조: $\hat{L}_{LRM}^n(\theta) = \eta(\theta)^\top \Lambda_n \eta(\theta) - 2\eta(\theta)^\top \nu_n + C$.
• 공액 업데이트: 만약 사전 분포 $\pi(\eta)$가 지수 이차 형식(예: 다변량 가우시안)이라면, 사후 분포 또한 다변량 가우시안(또는 파라미터 공간이 제한된 경우 절단된 가우시안)이 된다.
• 계산적 함의: 이를 통해 MCMC 없이 폐쇄형 추론(평균 및 공분산 행렬 계산)이 가능하다.
• 부분 공액성(Partial Conjugacy): 손실이 일부 파라미터에 대해서만 이차 형식인 모델(예: 자기회귀 시계열 또는 호스슈 사전 분포를 가진 모델)의 경우, 이 방법은 해당 블록에 대한 **정확한 깁스 업데이트(exact Gibbs updates)**를 가능하게 하여 표준 방식에 비해 MCMC 혼합 속도를 크게 향상시킨다.

3. 주요 기여

1. 새로운 발산: 난해한 정규화 상수를 우회하고 지수 가족에 대해 이차 손실을 유도하는 로그 비율 매칭(LRM) 발산을 도입하였다.
2. 공액 일반화 사후 분포: LRM-Bayes가 이산 난해 지수 가족에 대해 공액 사후 분포를 생성함을 입증하였으며, 이는 DFD와 같은 이산 발산으로는 달성할 수 없었던 속성이다.
3. 계산 효율성: 본 방법은 비용이 많이 드는 MCMC 샘플링을 폐쇄형 행렬 연산 또는 빠른 깁스 업데이트로 대체하여 계산 시간을 수십 배 단축한다.
4. 이론적 보장: 완만한 정규성 조건 하에서 LRM-Bayes 사후 분포가 점근적으로 가우시안이며 실제 손실의 최소값으로 집중됨을 보여주는 사후 일관성(posterior consistency) 및 **베른슈타인-폰 미제스 정리(Bernstein-von Mises theorem)**를 증명하였다.
5. 유연성: 복잡한 사전 분포(예: 호스슈, 스파이크-앤-슬랩) 및 시계열 모델을 지원하여, 특정 파라미터 블록에 대한 정확한 업데이트를 가능하게 하는 부분 공액성을 제공한다.

4. 실험 결과

본 방법은 다음과 같은 까다로운 이산 난해 모델들에 대해 평가되었다:

• 단변량 Conway-Maxwell-Poisson (CMP):
  • LRM-Bayes는 표준 MCMC 및 DFD-Bayes와 거의 동일한 사후 신뢰 영역을 생성하였다.
  • 속도: LRM은 중간 규모의 표본 크기에서 DFD-Bayes보다 100배 이상 빠르고, 표준 MCMC보다 20배 이상 빨랐다.
• 다변량 CMP 그래픽 모델 (유방암 데이터, $d=10, p=65$):
  • 표준 베이즈 추론은 계산적으로 불가능했다.
  • LRM-Bayes는 신뢰할 수 있는 사후 예측 분포를 제공하였다.
  • 속도: LRM은 DFD-Bayes보다 35배 이상 빨랐다 (약 2초 vs 31분).
  • 희소성: 이 방법은 호스슈 및 스파이크-앤-슬랩 사전 분포를 성공적으로 통합하여, 정확한 깁스 업데이트를 유지하면서 희소성을 유도하였다.
• 자기회귀 카운트 시계열 (범죄 데이터):
  • 자기회귀 파라미터 $\phi$는 메트로폴리스-헤이스팅스(Metropolis-Hastings)를 통해 업데이트하고, 다른 파라미터는 정확한 깁스 단계를 통해 업데이트하는 부분 공액성을 입증하였다.
  • 속도: LRM-Bayes는 약 1분 만에 혼합되었으나, 표준 근사 MCMC는 약 20분이 소요되었다 (20배 속도 향상).
• 마르코프 무작위장 (Ising 및 Potts 모델):
  • Ising 모델: LRM은 DFD 및 의사 우도 방법만큼 정확하게 파라미터를 회복하면서도 약 10배 더 빨랐다.
  • Potts 모델 (남극 빙하 데이터): LRM은 보조 변수 MCMC보다 35배 이상 빨랐으며, DFD/PL보다 현저히 빨랐다. 사후 분포는 다른 방법들과 유사했으나, 저자들은 데이터 자체가 이질적인 데이터에 대해 오설정되었음을 언급하였다.

5. 의의 및 주장

본 논문은 LRM-Bayes가 이산적 이중 난해 문제를 위한 계산 효율적인 대안을 제공한다고 주장한다. 그 의의는 다음과 같다:

• 격차 해소: 연속 영역의 KSD-Bayes(Matsubara et al., 2022)가 가진 계산적 이점을 이산 영역으로 확장하였으며, 이는 이전에 달성되지 못한 성과이다.
• 확장성: 공액성을 달성함으로써 MCMC 반복 횟수($T$)에 대한 의존성을 제거하여, 복잡도를 $O(ndpT)$에서$O(ndp^2 + p^3)$로 줄였다.
• 실용적 유용성: 이전에는 베이즈 분석을 수행하기에 너무 비용이 많이 들었던 복잡하고 유연한 모델(예: 고차원 그래픽 모델, 헤비 테일 사전 분포를 가진 시계열)의 적용을 가능하게 한다.
• 이론적 건전성: 이 방법은 단순한 휴리스틱이 아니라, 일관성과 정규성을 보장하는 엄격한 점근적 이론에 의해 뒷받침된다.

저자들은 참조 PMF($\hat{q}$)의 추정에 의존한다는 점과 매칭 세트 $M$의 선택이 사후 집중도에 영향을 미친다는 점을 언급하며 범위를 신중하게 설정하였으나, 스케일링 파라미터 $\beta$를 추정함으로써 이러한 민감도를 완화할 수 있다고 밝혔다. 본 연구는 시뮬레이션 기반 추론 및 잠재 변수 모델의 더 넓은 응용을 향한 단계로 자리매김하고 있다.