Importance Sampling for General Hybrid Bayesian Networks

Changhe Yuan, Marek J. DruzdzelAISTATS 2007

Introduction

Bayesian Networks (BNs) are a cornerstone of probabilistic reasoning, yet their application to "General" Hybrid Bayesian Networks (GHBNs) remains a significant challenge. GHBNs incorporate both discrete and continuous variables with arbitrary probability distributions and complex deterministic constraints. While mathematically expressive, these models often break traditional inference algorithms. This paper introduces HEPIS-BN (Hybrid EPIS-BN), an importance sampling algorithm designed to provide robust and accurate inference in these demanding scenarios.

The Limitations of Current Methods

Standard approaches to hybrid models often rely on restrictive assumptions, such as Conditional Linear Gaussians (CLGs), which fail to capture real-world non-linearities. Alternatively, flexible methods like Likelihood Weighting (LW) suffer from two critical flaws:

  1. The Curse of Unlikely Evidence: When observed evidence is rare, LW generates samples that rarely match the evidence, leading to high variance and slow convergence.
  2. Deterministic Constraints: In models with deterministic equations (e.g., $C = f(A, B)$), the probability of randomly sampling values that satisfy the constraint is zero, rendering standard sampling ineffective.

The HEPIS-BN Framework

HEPIS-BN addresses these issues through three integrated technical innovations:

1. Hybrid Loopy Belief Propagation (HLBP)

To overcome the "unlikely evidence" problem, HEPIS-BN uses HLBP to pre-process the network. By performing a few iterations of belief propagation, the algorithm estimates the shape of the posterior distribution. This estimate serves as a sophisticated importance function (proposal distribution), guiding the sampler toward high-probability regions from the start.

2. Delayed Importance Function Generation

In GHBNs, a child node's distribution often depends on its continuous parents. HEPIS-BN employs a "lazy" evaluation strategy, waiting until parent variables are instantiated during the sampling process before finalizing the child's proposal distribution. This allows the algorithm to handle arbitrary functional relationships between variables.

3. Soft Arc Reversal for Deterministic Nodes

To handle deterministic constraints, the researchers introduced "soft arc reversal." Instead of sampling a deterministic node and hoping it matches the evidence, the algorithm treats the deterministic relationship as an algebraic equation. It solves for one of the parent variables in terms of the evidence and other parents, effectively reversing the logic of the arc and ensuring every sample is valid.

Experimental Evaluation

The algorithm was evaluated on several benchmark models, including the Emission Network (an atmospheric model) and the Augmented Crop Network, which features non-linear deterministic equations.

Figure 5: Comparison of posterior distribution estimations for the DustEmission variable. HEPIS-BN closely tracks the exact posterior, whereas Likelihood Weighting (LW) and Normal Approximation fail to capture the multi-modal nature of the distribution.

Performance Analysis

The results demonstrate that HEPIS-BN significantly outperforms Likelihood Weighting in both accuracy and robustness. As shown in Figure 5, HEPIS-BN accurately recovers complex, multi-modal posterior distributions where other methods fail.

Figure 6: Convergence of Hellinger distance over the number of samples for two test scenarios. HEPIS-BN consistently achieves lower error rates and faster convergence compared to standard Likelihood Weighting.

Quantitatively, the algorithm maintains a low Hellinger distance (error) even as evidence becomes increasingly unlikely—a scenario where LW's performance typically collapses. While HEPIS-BN requires more computation per sample due to the HLBP and equation-solving steps, its high sample quality leads to faster overall convergence to the correct posterior.

Conclusion

HEPIS-BN represents a major advancement for inference in General Hybrid Bayesian Networks. By combining predictive belief propagation with algebraic constraint solving, it enables accurate reasoning in models that were previously considered computationally intractable. Future work will focus on scaling these techniques to massive real-world models with thousands of variables.

Summary updated

BibTeX
@article{yuan2007importance,
  author = {Changhe Yuan and Marek J. Druzdzel},
  title = {{Importance Sampling for General Hybrid Bayesian Networks}},
  journal = {AISTATS},
  year = {2007},
}
Figure