Analysis of Bayesian Networks via Prob-Solvable Loops

Ezio Bartocci, Laura Kovács, Miroslav Stankovic

Introduction

Bayesian Networks (BNs) are fundamental tools in probabilistic modeling, yet reasoning with them remains computationally demanding. Exact inference is NP-hard, and approximate methods like rejection sampling often suffer from inefficiency. Furthermore, standard BN tools struggle with automated sensitivity analysis—determining how small parameter changes affect outcomes—and the long-term behavior of Dynamic BNs (dynBNs).

This research introduces a novel framework that bridges the gap between probabilistic graphical models and program verification. By encoding BNs as "Prob-solvable loops," a specific class of probabilistic programs, the authors leverage automated moment-based invariant generation to solve inference, sensitivity, and filtering problems with high automation.

Methodology: From Graphs to Loops

The core innovation lies in treating a BN not as a static graph, but as a probabilistic program. A standard BN is viewed as a loop that executes once, while a Dynamic BN is a loop that iterates $n$ times.

Prob-Solvable Loops and MBIs

The framework relies on Prob-solvable loops, where variable assignments are polynomial and distributions are well-behaved. This structure allows for the automatic generation of Moment-Based Invariants (MBIs)—closed-form equations describing statistical moments (mean, variance, etc.) at any iteration.

Encoding a Discrete Bayesian Network (disBN) as a Prob-solvable loop for the 'Grass' example.

As shown in Figure 1, a discrete BN (like the "Grass" model) can be translated into a loop. The tool MORA then extracts recurrence relations from this code and solves them to find exact moments. This approach replaces millions of Monte Carlo simulations with the solution of linear recurrence equations.

Handling Continuous and Dynamic Models

The authors extended the theory of Prob-solvable loops to support Conditional Linear Gaussian (clgBN) networks. In these models, continuous variables (like weight loss) can have means that depend linearly on discrete parents (like drug dosage).

Encoding a Conditional Linear Gaussian Bayesian Network (clgBN) for the 'Rats' drug trial example.

Figure 6 demonstrates this for a drug trial model. By encoding the Gaussian dependencies as polynomial updates within the loop, the framework can compute exact expected weight loss and variance, even when parameters are symbolic.

Key Insights

  • Symbolic Sensitivity Analysis: Because the method generates symbolic equations rather than numerical estimates, sensitivity analysis becomes mathematically trivial. One can calculate exactly how much an output shifts when an input parameter (e.g., $a$ or $b$) changes.
  • Exact Solutions for Dynamic BNs: For dynamic models, the tool produces closed-form expressions for moments as a function of time $n$. For example, in an "Umbrella" dynBN, the probability of rain on day $n$ can be expressed as $\mathbb{E}[R] = \frac{1}{2}((2/5)^n + 1)$, allowing for immediate analysis of steady-state behavior ($n \to \infty$).
  • Sampling Efficiency: The method can analytically determine the "Expected Number of Samples" required for rejection sampling, providing insights into when traditional sampling methods will fail due to rare evidence.

Results and Performance

The MORA tool was evaluated on 28 problems across six benchmarks (including Alarm, Asia, and Rats). Most solutions were computed in under 2 seconds, with complex sensitivity analyses for large networks like "Alarm" completing in less than 4 seconds. This demonstrates that the symbolic recurrence-based approach is both highly efficient and versatile.

Conclusion and Future Work

By recasting Bayesian Networks as probabilistic programs, this work provides a powerful automated alternative to traditional inference engines. While currently limited to polynomial updates and linear Gaussian dependencies, future work aims to expand the class of Prob-solvable loops to handle non-linear arithmetic and more complex control flow, further broadening the scope of automated probabilistic reasoning.

Summary updated

Abstract

Prob-solvable loops are probabilistic programs with polynomial assignments over random variables and parametrised distributions, for which the full automation of moment-based invariant generation is decidable. In this paper we extend Prob-solvable loops with new features essential for encoding Bayesian networks (BNs). We show that various BNs, such as discrete, Gaussian, conditional linear Gaussian and dynamic BNs, can be naturally encoded as Prob-solvable loops. Thanks to these encodings, we can automatically solve several BN related problems, including exact inference, sensitivity analysis, filtering and computing the expected number of rejecting samples in sampling-based procedures. We evaluate our work on a number of BN benchmarks, using automated invariant generation within Prob-solvable loop analysis.
BibTeX
@inproceedings{bartocci2020analysis,
  author = {Ezio Bartocci and Laura Kovács and Miroslav Stankovic},
  title = {{Analysis of Bayesian Networks via Prob-Solvable Loops}},
  booktitle = {ICTAC},
  year = {2020},
  doi = {10.1007/978-3-030-64276-1\_12},
}
Figure