An Importance Sampling Algorithm Based on Evidence Pre-propagation

Changhe Yuan, Marek J. DruzdzelUAI 2003

TL;DR

This paper introduces EPIS-BN, a novel importance sampling algorithm for Bayesian networks that significantly improves inference accuracy, especially in challenging diagnostic scenarios with unlikely evidence. By leveraging loopy belief propagation to construct a more accurate importance function, EPIS-BN outperforms existing state-of-the-art methods without the need for costly learning stages.

What Problem Does This Paper Address?

Bayesian networks are powerful tools for modeling probabilistic relationships, but performing exact inference (calculating probabilities of events) can be computationally intractable for large, complex networks. Approximate inference methods, particularly stochastic sampling algorithms, are often used as a practical alternative. However, these methods struggle when faced with "diagnostic reasoning" scenarios, especially when the observed evidence is highly improbable. In such cases, standard sampling algorithms often generate many samples that are incompatible with the evidence, leading to poor accuracy within reasonable computational budgets. Existing importance sampling algorithms, while better, often rely on learning an "importance function" that can be time-consuming and may not always converge to the optimal solution. This paper aims to address this by developing an importance sampling algorithm that directly computes a good approximation of the optimal importance function.

Methods

The core innovation of EPIS-BN lies in its approach to constructing an effective importance function. Instead of learning it, EPIS-BN uses two key techniques:

  • Loopy Belief Propagation (LBP): This algorithm is adapted to approximate the "messages" (beliefs about evidence) passed between nodes in a Bayesian network, even in networks with cyclic dependencies (loops). While LBP doesn't guarantee convergence to exact posteriors in loopy networks, it provides a surprisingly accurate approximation. EPIS-BN uses these approximate messages to compute an "importance conditional probability table" (ICPT) for each node, which serves as a component of the overall importance function.
  • ε-cutoff Heuristic: This technique, borrowed from a previous algorithm (AIS-BN), involves setting small probabilities in the computed importance function to a small threshold (ε) and adjusting larger probabilities to compensate. This is used in EPIS-BN to ensure that the tails of the importance function don't decay too quickly, a crucial factor for accurate sampling, especially with unlikely evidence.

The algorithm proceeds by first running LBP to approximate the necessary messages, then calculating the importance function based on these messages, and finally applying the ε-cutoff heuristic. Samples are then drawn from this importance function, and their weights are computed.

Datasets

The authors evaluated EPIS-BN on three large, real-world Bayesian networks:

  • ANDES: A network with 233 nodes, characterized by a deep structure and high connectivity.
  • CPCS: A network modeling a subset of internal medicine, featuring many small probabilities.
  • PATHFINDER: A network with 135 nodes.

The experiments involved generating 75 test cases for each network, with varying numbers of evidence nodes and evidence probabilities (often extremely small, on the order of 10⁻¹⁰ to 10⁻⁴⁰).

Key Insights and Ideas

  • Directly computing, not learning, the importance function is viable: The paper demonstrates that by intelligently using approximate inference techniques like LBP, one can bypass the computationally expensive learning phase of previous importance sampling algorithms.
  • Loopy Belief Propagation is a powerful tool for importance function approximation: The success of EPIS-BN hinges on LBP's ability to provide good approximations of network beliefs, even in the presence of loops. This suggests LBP has broader applications beyond just approximate inference.
  • The ε-cutoff heuristic's role is nuanced: While beneficial in some cases, the ε-cutoff heuristic's effectiveness can be network-dependent. For very deep networks with large loops (like ANDES), LBP alone might already provide a sufficiently good importance function, making ε-cutoff less impactful or even detrimental.
  • Unlikely evidence is a major challenge for sampling: The paper strongly reinforces that diagnostic reasoning with rare evidence is a critical bottleneck for many approximate inference methods.

Key Results

  • Significant Accuracy Improvement: EPIS-BN consistently outperformed AIS-BN (the state-of-the-art at the time) across all tested networks, achieving up to an order of magnitude better precision in Hellinger's distance and Mean Square Error (MSE).
  • Speed Advantage: EPIS-BN's LBP pre-processing step was significantly faster than AIS-BN's learning stage (e.g., 0.5 seconds vs. 7.7 seconds for ANDES). When considering the total time (pre-processing + sampling), EPIS-BN offered a substantial speedup for achieving comparable or better accuracy.
  • Robustness: While the improvement was most pronounced on the challenging ANDES network, EPIS-BN also showed consistent gains on CPCS and PATHFINDER.
  • LBP is the primary driver of improvement: Experiments isolating the roles of LBP and ε-cutoff showed that LBP was responsible for the majority of the performance gains.

Limitations and Future Work

  • Optimal parameter tuning: The optimal propagation length for LBP and the threshold for ε-cutoff are network-dependent and require empirical tuning. The authors provide recommended values based on their experiments.
  • Role of ε-cutoff: The paper acknowledges that the precise role and optimal application of the ε-cutoff heuristic still require further understanding, especially in relation to network structure and probability distributions.
  • LBP convergence: While EPIS-BN doesn't require LBP to fully converge, further research into techniques that improve LBP's stability and convergence properties could lead to even better performance.
  • Generalizing ε-cutoff: The authors suggest that exploring alternative or refined heuristics for adjusting the importance function's tails could be a fruitful area of research.

Summary updated

BibTeX
@inproceedings{yuan2003importance,
  author = {Changhe Yuan and Marek J. Druzdzel},
  title = {{An Importance Sampling Algorithm Based on Evidence Pre-propagation}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2003},
}
Figure