Message passing in Bayesian networks

Tom Minka, John Winn, Martin Szummer

Bayesian networks are a central tool in our group for analyzing data of various kinds; for example, hand-drawn ink, online game data, and digital photographs. Consequently we have put together a unified effort to improve and extend the fundamental computational methods for Bayesian networks, which underlie all the above applications. Specifically, we are developing novel numerical algorithms for computing probabilities and parameter estimates in Bayesian networks.

Bayesian networks are a graphical formalism for specifying probabilistic models. For example, in online game analysis, we have a large graph of games between all players on Xbox live. Each node of the graph is a player, and each edge is a game. Based on the game outcomes, we want to estimate each player's skill. Mathematically, this amounts to applying the laws of probability to determine the distributions of all unknown quantities, which is a calculus problem. But these integrals cannot be solved analytically; they must be approximated numerically. The way in which you approximate the integrals determines the speed and accuracy characteristics of the system. In the case of Xbox live, millions of games are played every day, and player rankings need to be updated after every game.

Our approach is based on message-passing. The intuition is that while all nodes of the graph are correlated, distant nodes are less correlated. We decompose the graph into parts, solve each part to high accuracy, and only exchange aggregate information between parts. For example, within one part, a variable may have a complex distribution, but only a simple summary of that variable (such as mean and variance) is transmitted to other parts. For some graphs, such as the game graph above, this approach is very effective.

Perhaps the best known message-passing algorithm is Belief Propagation, which was later generalized to Expectation Propagation. Since 2003, we have developed novel and more powerful message-passing algorithms, including:

• Variational message-passing (2004)
• Power EP (2004)
• Simultaneous graph partitioning and labeling (2005)
• Structured region graphs (2005)
• Divergence-based message-passing (2005)

We have also applied message-passing algorithms successfully to several tasks:

• TrueSkill™ player ranking
• Learning Object Classes with Unsupervised Segmentation
• Generative Affine Localisation and Tracking
• A Graphical Model for Simultaneous Partitioning and Labeling
• Diagram Structure Recognition by Bayesian Conditional Random Fields

Machine Learning and Perception —Machine Learning—Message Passing Methods