Divergence measures and message passing

TLDR

The distinction between mean‑field methods and belief propagation lies in the divergence measure they minimize, exclusive versus inclusive Kullback‑Leibler, rather than the amount of structure modeled. This paper unifies message‑passing algorithms as approximations of complex Bayesian networks by simpler networks that minimize information divergence. Message‑passing arises from locally minimizing the chosen divergence at each factor. Analyzing these divergences reveals the solution types they favor, such as symmetry‑breaking, and shows how varying divergence measures, like alpha‑divergences, can trade complexity for performance.

Abstract

This paper presents a unifying view of messagepassing algorithms, as methods to approximate a complex Bayesian network by a simpler network with minimum information divergence. In this view, the difference between mean-field methods and belief propagation is not the amount of structure they model, but only the measure of loss they minimize (‘exclusive’ versus ‘inclusive’ Kullback-Leibler divergence). In each case, message-passing arises by minimizing a localized version of the divergence, local to each factor. By examining these divergence measures, we can intuit the types of solution they prefer (symmetry-breaking, for example) and their suitability for different tasks. Furthermore, by considering a wider variety of divergence measures (such as alpha-divergences), we can achieve different complexity and performance goals.