기대 전파(Expectation propagation, EP)은 베이즈 머신러닝에서 정확하게 다루기 계산적으로 불가능한 확률 분포를 근사하는 데 사용되는 기법이다. 이 기법은 2001년 제17회 불확실성 인공지능 학회에서 발표된 토마스 밍카(Thomas Minka)의 논문에서 처음 소개되었다. 이 방법은 대상 분포의 인수분해 구조를 활용하여 복잡한 대상 분포에 대한 다루기 쉬운 근사를 찾도록 설계되었으며, Machine learning 및 관련 분야의 다양한 추론 문제에서 유용하게 사용된다.
EP의 핵심 아이디어는 다루기 어려운 분포 \(p(\mathbf{x})\)를 더 단순하고 다루기 쉬운 분포 \(q(\mathbf{x})\)로 근사하는 것이다. 이는 하나의 확률 분포가 두 번째 분포와 얼마나 다른지를 측정하는 쿨백-라이블러 발산(Kullback-Leibler divergence) \(\mathrm{KL}(p||q)\)을 최소화함으로써 달성된다. 이러한 발산 방향의 선택은 \(\mathrm{KL}(q||p)\)를 최소화하는 변분 베이즈 방법과의 주요 차이점이다. 실질적인 결과로, EP는 대상 분포의 전체적인 형태, 특히 모멘트를 일치시키는 데 초점을 맞추는 경향이 있으며, 대상이 작은 영역을 피하는 것보다는 전체적인 형태를 맞추는 데 중점을 둔다.
근사 분포 \(q(\mathbf{x})\)가 가우시안 \(\mathcal{N}(\mathbf{x}|\mu, \Sigma)\)으로 선택될 때, \(\mathrm{KL}(p||q)\)를 최소화하면 닫힌 형태의 해가 도출된다. 즉, 최적의 \(\mu\)와 \(\Sigma\)는 단순히 대상 분포 \(p(\mathbf{x})\)의 평균과 공분산이다. 모멘트 매칭(moment matching)으로 알려진 이 연산은 EP 알고리즘의 핵심이다. 실제로 EP는 근사의 개별 인자를 반복적으로 업데이트하여 수렴할 때까지 모멘트를 정제하며, 이를 통해 복잡한 인수분해 모델을 처리할 수 있다.
알고리즘 프레임워크
EP 알고리즘은 대상 분포의 각 인자에 대한 근사를 유지함으로써 작동한다. 초기에는 이러한 인자 근사가 단순한 형태, 종종 균일 분포나 가우시안 분포로 설정된다. 그런 다음 알고리즘은 각 인자를 반복하며, 현재 근사에서 해당 인자를 제거하고, 공동 분포(cavity distribution)를 계산한 후, 결과적으로 얻어진 기울어진 분포(tilted distribution)를 모멼트 매칭을 통해 다루기 쉬운 패밀리로 다시 투영한다. 이 과정은 근사가 안정화될 때까지 반복되며, 최종적으로 전체 대상을 근사하는 \(q(\mathbf{x})\)를 산출한다.
EP의 주목할 만한 강점은 제약 조건이나 이산 결과를 포함하는 모델에서 흔히 나타나는 지시 함수와 같은 비-가우시안 인자를 처리할 수 있는 능력이다. 모멘트 매칭 단계는 정확한 추론이 불가능한 경우에도 근사가 이러한 인자의 필수 통계량을 포착하도록 보장한다. 이러한 유연성 덕분에 EP는 Probabilistic graphical models 및 기타 구조적 예측 작업에서 근사 추론을 위한 인기 있는 선택이 되었다.
응용 분야
EP의 두드러진 응용 중 하나는 마이크로소프트 리서치가 온라인 게임용으로 개발한 순위 시스템인 TrueSkill의 메시지 전달 방정식 유도이다. TrueSkill은 플레이어의 실력을 가우시안 분포로 모델링하고 경기 결과에 따라 이러한 추정치를 업데이트한다. 승패 이벤트에서 발생하는 지시 함수는 직접 처리하기 어렵지만, EP는 이를 효율적으로 근사하는 방법을 제공하여 실시간 실력 추정과 매치메이킹을 가능하게 한다.
TrueSkill 외에도 EP는 Neural network 훈련과 같은 영역에서 가중치에 대한 베이즈 추론에 사용되거나, Large language model 맥락에서 불확실성 정량화에 적용되었다. 보정된 불확실성 추정치를 제공하는 능력 덕분에 Artificial intelligence 및 Deep learning 분야에서 모델의 확률적 해석이 점점 더 중요해짐에 따라 관련성이 높아지고 있다.
다른 방법과의 비교
EP는 최소화되는 쿨백-라이블러 발산의 방향에서 변분 베이즈 방법과 근본적으로 다르다. \(\mathrm{KL}(q||p)\)를 최소화하는 변분 방법은 더 보수적인 근사를 생성하는 경향이 있으며, 종종 대상의 분산을 과소평가한다. 반대로, EP가 \(\mathrm{KL}(p||q)\)를 사용하면 대상의 분산을 더 잘 포착하는 근사를 얻을 수 있지만, 어떤 경우에는 덜 안정적일 수 있다.
또 다른 관련 접근법은 마르코프 체인 몬테카를로(MCMC)로, 점근적으로 정확한 샘플을 제공하지만 계산 비용이 많이 들 수 있다. EP는 근사 오차를 도입하는 대신 종종 더 빠른 결정론적 대안을 제공한다. 이러한 절충 덕분에 EP는 샘플링이 비실용적인 대규모 문제에서 특히 매력적이다.
한계 및 확장
EP는 모든 모델에 대해 수렴이 보장되지 않으며, 그 성능은 인자 근사의 초기화에 따라 달라질 수 있다. 일부 설정에서는 모멘트 매칭 업데이트가 진동하거나 발산할 수 있어 감쇠(damping) 또는 기타 안정화 기술이 필요하다. 연구자들은 이러한 문제를 해결하기 위해 감쇠가 있는 기대 전파 및 분수 EP(fractional EP)와 같은 변형을 개발했다.
이러한 어려움에도 불구하고 EP는 베이즈 추론 도구 상자에서 널리 사용되는 도구로 남아 있다. 밍카의 원래 연구에서 제시된 이론적 기반은 Computer vision에서 Reinforcement learning에 이르기까지 수많은 확장과 응용에 영감을 주었다. 정확성과 계산 효율성 사이의 균형을 맞추는 이 방법의 능력은 Stanford AI Lab 및 기타 주요 기관에서 계속해서 활발한 연구 주제가 되고 있다.
같이 보기
- variational-inference
- Bayesian Inference
- moment-matching
- trueskill