How long, O Bayesian network, will I sample thee? A program analysis perspective on expected sampling times

DOI10.1007/978-3-319-89884-1_7zbMATH Open1418.68050arXiv1802.10433OpenAlexW2797914422MaRDI QIDQ2323973FDOQ2323973

Kevin Batz, Benjamin Lucien Kaminski, Christoph Matheja, Joost-Pieter Katoen

Publication date: 13 September 2019

Abstract: Bayesian networks (BNs) are probabilistic graphical models for describing complex joint probability distributions. The main problem for BNs is inference: Determine the probability of an event given observed evidence. Since exact inference is often infeasible for large BNs, popular approximate inference methods rely on sampling. We study the problem of determining the expected time to obtain a single valid sample from a BN. To this end, we translate the BN together with observations into a probabilistic program. We provide proof rules that yield the exact expected runtime of this program in a fully automated fashion. We implemented our approach and successfully analyzed various real-world BNs taken from the Bayesian network repository.

Full work available at URL: https://arxiv.org/abs/1802.10433

Recommendations

• Modeling and Reasoning with Bayesian Networks
• Bayesian inference by symbolic model checking
• A compositional approach to probabilistic knowledge compilation
• scientific article; zbMATH DE number 2096817
• A Bayesian analysis of simulation algorithms for inference in belief networks

zbMATH Keywords

program verificationweakest preconditionsprobabilistic programsexpected runtimes

Mathematics Subject Classification ID

Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.) (68N30) Specification and verification (program logics, model checking, etc.) (68Q60)

Cited In (8)

• Automatic Generation of Moment-Based Invariants for Prob-Solvable Loops
• Learning probabilistic termination proofs
• Model checking finite-horizon Markov chains with probabilistic inference
• Automatic Analysis of Expected Termination Time for Population Protocols
• Automatically finding the right probabilities in Bayesian networks
• Quantum weakest preconditions for reasoning about expected runtimes of quantum programs
• A denotational semantics for low-level probabilistic programs with nondeterminism
• Moment-based analysis of Bayesian network properties

This page was built for publication: How long, O Bayesian network, will I sample thee? A program analysis perspective on expected sampling times

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2323973)