Improved Mean and Variance Approximations for Belief Net Responses via Network Doubling

Peter Hooper, Yasin Abbasi-Yadkori, Russell Greiner, Bret Hoehn

TL;DR

This paper introduces a novel "network doubling" technique to more accurately approximate the mean and variance of queries in Bayesian belief networks. By creating a "doubled network" with two independent replicates of the original network, the authors derive improved approximations that are more accurate than existing delta method approaches, especially for simpler queries.

What Problem Does This Paper Address?

Bayesian belief networks (BNs) are powerful tools for modeling complex probabilistic relationships between variables. When parameters within these networks are treated as random variables to account for uncertainty, queries (which are functions of these parameters) also become random variables. Quantifying this uncertainty, particularly the variance of a query, is crucial for understanding the reliability of BN predictions. Existing methods, like the delta method, provide approximations but can be inaccurate. This paper aims to develop more precise approximations for both the mean and variance of query responses, especially in scenarios with limited data where uncertainty is high.

Methods

The core innovation is the network doubling technique. The authors extend the idea of approximating a query's mean to approximating the query's squared value. This is achieved by constructing a "doubled network" that consists of two independent, identically distributed copies of the original network, sharing the same underlying parameters. This doubled network allows for the calculation of the expected value of the squared query, which, when combined with the expected value of the query itself, yields an approximation for the variance.

The paper also introduces adjustments to these approximations, particularly for discrete networks. These adjustments are motivated by large sample asymptotic theory and aim to improve accuracy by accounting for higher-order moments of the query distribution. The authors analyze four approximations for the mean ($\hat{q}_1, \hat{q}_2, \hat{q}_3, \hat{q}_4$) and four for the variance ($\hat{\sigma}^2_1, \hat{\sigma}^2_2, \hat{\sigma}^2_3, \hat{\sigma}^2_4$), with $\hat{q}_2$ and $\hat{\sigma}^2_2$ representing the direct network doubling approach, and $\hat{q}_3, \hat{q}_4, \hat{\sigma}^2_3, \hat{\sigma}^2_4$ being further refined versions.

Datasets

The paper does not introduce new datasets. Instead, it uses three small networks for evaluation:

  • Naïve Bayes networks (NB-2 and NB-4): These are standard BN structures with 2 and 4 features, respectively, plus a root variable.
  • Diamond network: A network with 4 variables.
  • Alarm network: A larger, more complex network with 37 variables, used to test performance on more intricate structures.

The experiments involve generating queries and simulating data from posterior distributions that satisfy BDe constraints, ensuring a consistent effective sample size across variables.

Key Insights and Ideas

  • Network Doubling for Variance: The most significant insight is that by creating a doubled network and calculating the expectation of the squared query, one can derive a more accurate variance approximation than the standard delta method. This elegantly sidesteps the need for complex derivative calculations.
  • Asymptotic Theory for Refinement: The paper leverages asymptotic theory to derive further improvements to the initial network doubling approximations. This demonstrates a principled way to enhance accuracy as the effective sample size grows.
  • Trade-off between Simplicity and Accuracy: The authors highlight that while the delta method is computationally simpler for complex networks, network doubling offers superior accuracy, especially for simpler queries or when the effective sample size is small.
  • Practical Implications for Uncertainty Quantification: More accurate variance approximations lead to more reliable confidence intervals (error bars) for query results, which is critical for decision-making based on BN models.

Key Results

  • Improved Accuracy: The network doubling method ($\hat{q}_2, \hat{\sigma}^2_2$) and its adjusted versions ($\hat{q}_3, \hat{q}_4, \hat{\sigma}^2_3, \hat{\sigma}^2_4$) consistently show higher accuracy than the delta method ($\hat{q}_1, \hat{\sigma}^2_1$) for approximating query means and variances, particularly in simpler networks and for simpler queries.
  • Faster for Simple Queries: Empirical timing results (Table 2) indicate that network doubling is faster than the delta method for simple queries (e.g., NB-4, Diamond networks), while the delta method is faster for complex queries (e.g., Alarm network).
  • Convergence Rates: Proposition 1 provides theoretical guarantees on the convergence rates of the approximations, showing that the mean approximations have errors approaching zero at rates of $m^{-1}$ or $m^{-3/2}$, and variance approximations have relative errors approaching zero at rate $m^{-1}$.

Limitations and Future Work

  • Computational Complexity: While network doubling is faster for simple queries, its computational complexity increases quadratically with the number of variables in the doubled network. This makes it less suitable for very large and complex networks compared to the delta method.
  • Discrete Networks Focus: The detailed adjustments and numerical results are primarily presented for discrete networks. The paper notes that extending these to continuous and hybrid networks is ongoing work.
  • Complete Data Assumption: The method assumes complete data for calculating posterior means.
  • Future Work: The authors plan to extend their methods to continuous and hybrid networks and further investigate computational efficiency. They also aim to compare the accuracies of the doubling and delta methods across these extended network types.

Summary updated

Abstract

A Bayesian belief network models a joint distribution with an directed acyclic graph representing dependencies among variables and network parameters characterizing conditional distributions. The parameters are viewed as random variables to quantify uncertainty about their values. Belief nets are used to compute responses to queries; i.e., conditional probabilities of interest. A query is a function of the parameters, hence a random variable. Van Allen et al. (2001, 2008) showed how to quantify uncertainty about a query via a delta method approximation of its variance. We develop more accurate approximations for both query mean and variance. The key idea is to extend the query mean approximation to a "doubled network" involving two independent replicates. Our method assumes complete data and can be applied to discrete, continuous, and hybrid networks (provided discrete variables have only discrete parents). We analyze several improvements, and provide empirical studies to demonstrate their effectiveness.
BibTeX
@inproceedings{hooper2009improved,
  author = {Peter Hooper and Yasin Abbasi-Yadkori and Russell Greiner and Bret Hoehn},
  title = {{Improved Mean and Variance Approximations for Belief Net Responses via Network Doubling}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2009},
  url = {https://openreview.net/forum?id=XK5RCU5B-eS},
}
Figure