Mixture Approximations to Bayesian Networks

Volker Tresp, Michael Haft, Reimar Hofmann

TL;DR

This paper proposes a method to approximate complex Bayesian Networks (BNs) using mixture models, effectively distilling a complex web of dependencies into a few human-interpretable "scenarios." By switching from the standard Kullback-Leibler (KL) divergence to a Mean Squared Error (MSE) cost function, the authors demonstrate that these approximations can be computed efficiently using the standard junction tree algorithm.

What Problem Does This Paper Address?

Bayesian Networks are celebrated for their modularity—you only need to specify local relationships between variables to build a sophisticated global model. However, this "locality" is a double-edged sword. As networks grow, it becomes nearly impossible for a human to grasp the "big picture" or understand the most likely global configurations (scenarios) the model implies.

Furthermore, while BNs are powerful, exact inference can be computationally heavy and unintuitive. The authors aim to bridge this gap by creating an "alternative view" of the BN: a mixture of simpler distributions that represent typical cases within the domain, making the model both easier to explain to stakeholders and faster for certain types of reasoning.

Methods

The core idea is to approximate the joint probability distribution of a BN, $P(x)$, with a mixture distribution $Q(x)$ composed of $M$ components. Each component is a simple product of independent binomial distributions (for binary variables).

The authors explore three ways to measure the "distance" between the true BN and the approximation:

  1. KL-Divergence: The standard information-theoretic measure. While "natural," it requires summing over exponentially many states, making it computationally infeasible for large networks.
  2. Backward KL-Divergence: Often used in mean-field approximations. It allows for local updates but finding the optimal mixture remains difficult.
  3. Mean Squared Error (MSE): The paper’s key contribution. The authors show that the MSE cost function results in quadratic update equations. Crucially, these equations can be solved efficiently using the junction tree algorithm.

By using MSE, the optimization becomes tractable for any network where standard exact inference is possible. Once the mixture is calculated, inference becomes a simple matter of reweighting the "scenarios" based on new evidence—a process that is both fast and transparent.

Datasets

The authors evaluate their approach using the "Chest Clinic" (or "Asia") network, a classic benchmark in the BN community. This 8-variable network models the relationships between lung diseases (tuberculosis, lung cancer, bronchitis), symptoms (dyspnoea, X-ray results), and risk factors (smoking, visiting Asia).

Key Insights and Ideas

  • Scenarios as Explanations: Instead of looking at raw conditional probability tables, the mixture model presents the user with "typical patients." For example, one component might represent "healthy non-smokers," while another represents "smokers with chronic bronchitis."
  • The MSE Advantage: The choice of distance measure isn't just a matter of preference; it dictates the algorithm's complexity. The discovery that MSE "plays nice" with the junction tree structure is the paper's primary "aha" moment.
  • Intuitive Inference: In a mixture model, evidence acts as a filter. If a patient has a positive X-ray, you simply increase the weight of the "sick" scenarios and decrease the "healthy" ones. This mirrors how human experts, like doctors, often reason through differential diagnosis.

Key Results

  • Rapid Convergence: As shown in Figure 1, the KL-distance between the true distribution and the approximation drops sharply with just a few components. For the Chest Clinic, 4 components capture almost all the essential information.
Figure 1: The mixture approximation using the KL­ distance. The x-axis indicates the number of mixture components and the y-axis the KL-distance between the mixture model and the Bayesian network.
  • Metric Consistency: The scenarios found by minimizing MSE were qualitatively and quantitatively very similar to those found by the (much slower) KL-divergence method.
  • Inference Accuracy: The mixture model provided marginal posterior probabilities within about 1% of the exact values for common evidence. Even with very unlikely evidence (e.g., a rare combination of symptoms), the MSE-based mixture remained useful, whereas other approximations like Expected MSE (ESE) struggled.

Limitations and Future Work

  • Junction Tree Dependency: The efficiency of the MSE approach relies on the junction tree algorithm. For massive, highly connected "loopy" networks where junction tree inference fails, this method also becomes intractable, leaving mean-field approximations as the only alternative.
  • Variable Types: The experiments focused on binary variables. While the authors suggest the math generalizes to discrete and Gaussian models, these were not empirically tested in this paper.
  • Choosing M: The paper does not provide a formal heuristic for choosing the number of mixture components ($M$), leaving it as a parameter for the user to tune based on the desired balance between simplicity and accuracy.

Summary updated

Abstract

Structure and parameters in a Bayesian network uniquely specify the probability distribution of the modeled domain. The locality of both structure and probabilistic information are the great benefits of Bayesian networks and require the modeler to only specify local information. On the other hand this locality of information might prevent the modeler - and even more any other person - from obtaining a general overview of the important relationships within the domain. The goal of the work presented in this paper is to provide an "alternative" view on the knowledge encoded in a Bayesian network which might sometimes be very helpful for providing insights into the underlying domain. The basic idea is to calculate a mixture approximation to the probability distribution represented by the Bayesian network. The mixture component densities can be thought of as representing typical scenarios implied by the Bayesian model, providing intuition about the basic relationships. As an additional benefit, performing inference in the approximate model is very simple and intuitive and can provide additional insights. The computational complexity for the calculation of the mixture approximations criticaly depends on the measure which defines the distance between the probability distribution represented by the Bayesian network and the approximate distribution. Both the KL-divergence and the backward KL-divergence lead to inefficient algorithms. Incidentally, the latter is used in recent work on mixtures of mean field solutions to which the work presented here is closely related. We show, however, that using a mean squared error cost function leads to update equations which can be solved using the junction tree algorithm. We conclude that the mean squared error cost function can be used for Bayesian networks in which inference based on the junction tree is tractable. For large networks, however, one may have to rely on mean field approximations.
BibTeX
@misc{tresp2013mixture,
  author = {Volker Tresp and Michael Haft and Reimar Hofmann},
  title = {{Mixture Approximations to Bayesian Networks}},
  year = {2013},
  eprint = {1301.6744},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1301.6744},
}
Figure