Large Deviation Methods for Approximate Probabilistic Inference

Abstract

We study two-layer belief networks of binary random variables in which the conditional probabilities Pr[childlparents] depend monotonically on weighted sums of the parents. In large networks where exact probabilistic inference is intractable, we show how to compute upper and lower bounds on many probabilities of interest. In particular, using methods from large deviation theory, we derive rigorous bounds on marginal probabilities such as Pr[children] and prove rates of convergence for the accuracy of our bounds as a function of network size. Our results apply to networks with generic transfer function parameterizations of the conditional probability tables, such as sigmoid and noisy-OR. They also explicitly illustrate the types of averaging behavior that can simplify the problem of inference in large networks.

Appears in Proceedings of the Fourteenth Conference on Uncertainty in Artificial Intelligence (UAI1998)

Cited by in corpus (16)

• Time-uniform Chernoff bounds via nonnegative supermartingales
• Concentration inequalities in the infinite urn scheme for occupancy counts and the missing mass, with applications
• On the sub-Gaussianity of the Beta and Dirichlet distributions
• On strict sub-Gaussianity, optimal proxy variance and symmetry for bounded random variables
• Exact value for subgaussian norm of centered indicator random variable
• The Kearns--Saul inequality for Bernoulli and Poisson-binomial distributions
• Tightening Exploration in Upper Confidence Reinforcement Learning
• Active Tuples-based Scheme for Bounding Posterior Beliefs
• Large-Sample Properties of Blind Estimation of the Linear Discriminant Using Projection Pursuit
• Subgaussian and strictly subgaussian random variable
• Novel Bernstein-like Concentration Inequalities for the Missing Mass
• Consistency of weighted majority votes
• Bregman Deviations of Generic Exponential Families
• On the Concentration of the Missing Mass
• Novel Deviation Bounds for Mixture of Independent Bernoulli Variables with Application to the Missing Mass
• Revisiting Concentration of Missing Mass