Many-Pairs Mutual Information for Adding Structure to Belief Propagation Approximations

Arthur Choi, Adnan DarwicheAAAI 2008 · OpenReview

Abstract

Iterative Belief Propagation (IBP) is a fundamental tool in probabilistic reasoning, yet it often struggles with "loopy" networks. This paper introduces a novel "soft d-separation" (sd-sep) metric to efficiently identify which edges to add back into simplified Bayesian networks to improve approximations. By treating nodes on a path as "valves" and calculating an upper bound on mutual information, the proposed method achieves up to a 640x speedup over traditional mutual information calculations while maintaining high accuracy in edge selection.

Introduction

Iterative Belief Propagation (IBP) is a cornerstone of modern AI, used in applications from turbo decoding to computer vision. However, IBP is an approximation that often struggles with networks containing undirected cycles. A powerful way to improve IBP is through Generalized Belief Propagation (GBP), which handles certain regions of a network exactly.

A specific framework called ED-BP views IBP as a process of deleting edges until a complex network becomes a simple "polytree." To improve the approximation, we want to "recover" the most important deleted edges. The standard way to rank these edges is by calculating Mutual Information (MI). However, calculating MI for every possible pair of variables in a large network is computationally crushing, as it requires running the BP algorithm many times.

Methodology: Soft d-Separation

The authors introduce Soft d-Separation (sd-sep), which turns the binary d-separation test into a quantitative measure of how much information can flow between two nodes. In a polytree, there is only one path between any two nodes. The authors treat this path as a "pipe" and every node on it as a "valve."

The pipe and valve analogy: nodes on a path act as valves that bound information flow.

Key technical components include:

  • Valve Bounds: They prove that the mutual information between two endpoints is bounded by the "tightest" valve on the path.
  • For Sequential ($→ W →$) or Divergent ($← W →$) valves, the flow is bounded by the Entropy of $W$.
  • For Convergent valves ($N_1 → W ← N_2$), the flow is bounded by the Mutual Information between the parents ($N_1$ and $N_2$).
  • Single-Pass Computation: Because these bounds only require local marginals (which BP calculates in a single run), the entire "soft" connectivity of the network can be mapped out extremely quickly.

Experimental Setup

The authors evaluated their method on several well-known Bayesian network benchmarks:

  • Medical/Diagnostic: Alarm, Diabetes, Munin (1-4), Mildew, and Emdec (a noisy-or network).
  • General: Win95pts (printer troubleshooting) and Pigs (pedigree analysis). These networks range from small models to very large ones with complex parameter spaces.

Results and Discussion

The proposed sd-sep heuristic demonstrates exceptional efficiency and fidelity across all tested benchmarks.

Performance comparison across benchmarks showing significant speedups in edge ranking time and competitive KL error.
  • Massive Speedups: As shown in the table above, the proposed method was 641.99x faster than calculating true Mutual Information on the Diabetes network and 157.26x faster on Mildew.
  • High Fidelity Ranking: Empirical analysis shows that for the "high-value" edges (the ones that matter most for recovery), the soft d-separation score tracks the true MI very closely.
  • Improved Approximations: When using these scores to add structure back into the model, the resulting approximations (measured by KL-divergence) were often as good as, or even slightly better than, those produced by the much slower true MI heuristic.

Key Insights

  • The Bottleneck Principle: Correlation between distant variables is limited by the node on the path with the least uncertainty (lowest entropy).
  • Heuristic Efficiency: You don't need the exact Mutual Information to improve a model; you just need a good ranking of which edges are most important. Soft d-separation provides an upper bound that preserves this ranking surprisingly well.

Limitations and Future Work

The current formal proofs for these bounds rely on the unique paths found in polytrees. While the authors suggest a "maximal set of node-disjoint paths" approach for general loopy networks, this extension is more complex. Additionally, soft d-separation is an upper bound, not an exact value; in cases where true MI is very low, the bound can become "loose." Future work could explore adaptive recovery, where edges are re-ranked after each recovery step.

Summary updated

Abstract

We consider the problem of computing mutual information between many pairs of variables in a Bayesian network. This task is relevant to a new class of Generalized Belief Propagation (GBP) algorithms that characterizes Iterative Belief Propagation (IBP) as a polytree approximation found by deleting edges in a Bayesian network. By computing, in the simplified network, the mutual information between variables across a deleted edge, we can estimate the impact that recovering the edge might have on the approximation. Unfortunately, it is computationally impractical to compute such scores for networks over many variables having large state spaces. So that edge recovery can scale to such networks, we propose in this paper an approximation of mutual information which is based on a soft extension of d-separation (a graphical test of independence in Bayesian networks). We focus primarily on polytree networks, which are sufficient for the application we consider, although we discuss potential extensions of the approximation to general networks as well. Empirically, we show that our proposal is often as effective as mutual information for the task of edge recovery, with orders of magnitude savings in computation time in larger networks. Our results lead to a concrete realization of GBP, admitting improvements to IBP approximations with only a modest amount of computational effort.
BibTeX
@inproceedings{choi2008many,
  author = {Arthur Choi and Adnan Darwiche},
  title = {{Many-Pairs Mutual Information for Adding Structure to Belief Propagation Approximations}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2008},
  url = {https://openreview.net/forum?id=SyNx5JZdbH},
}
Figure