Computing Upper and Lower Bounds on Likelihoods in Intractable Networks

2013/02/13 by Tommi Jaakkola, Michael I. Jordan, Jaakkola, Tommi S. +1
Computer Science · Decision Sciences · #Artificial Intelligence (cs.AI) #Bayesian Modeling and Causal Inference #FOS: Computer and information sciences #Machine Learning and Algorithms #Multi-Criteria Decision Making

paper · pdf · doi:10.48550/arxiv.1302.3586

openalex publication_date 2013/02/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We present deterministic techniques for computing upper and lower bounds on marginal probabilities in sigmoid and noisy-OR networks. These techniques become useful when the size of the network (or clique size) precludes exact computations. We illustrate the tightness of the bounds by numerical experiments.

Citations

• Approximating probabilistic inference in Bayesian belief networks is NP-hard
• Connectionist learning of belief networks

Related

• Large Deviation Methods for Approximate Probabilistic Inference
• Lower Bound Bayesian Networks - An Efficient Inference of Lower Bounds\n on Probability Distributions in Bayesian Networks
• Efficient Approximations for the Marginal Likelihood of Incomplete Data\n Given a Bayesian Network
• Automated Analytic Asymptotic Evaluation of the Marginal Likelihood for Latent Models
• Novel Bounds on Marginal Probabilities