Is probabilistic inference always tractable?

No. Exact inference in general Bayesian networks is NP-hard, and its cost grows with the network's treewidth. For networks that are trees or have low treewidth, exact inference is efficient; otherwise approximate methods such as sampling or loopy belief propagation are used.

What is the difference between exact and approximate inference?

Exact inference, such as variable elimination or the junction-tree algorithm, computes the true posterior probabilities. Approximate inference, such as Monte Carlo sampling or loopy belief propagation, estimates them, which is necessary when exact computation is too expensive for a large or densely connected model.

Probabilistic Inference

Probabilistic inference is the computation of the probability of query variables given observed evidence in a probabilistic model, the central reasoning task over Bayesian and Markov networks.

Definition

Probabilistic inference computes a posterior distribution, such as the probability of one or more query variables conditioned on observed evidence, from a specified probabilistic model, either exactly or by approximation.

Scope

This topic covers the algorithms that answer probabilistic queries in graphical models: exact methods such as variable elimination, belief propagation in trees, and the junction-tree (clique-tree) algorithm; and approximate methods such as loopy belief propagation and Monte Carlo sampling (rejection sampling, likelihood weighting, and Markov chain Monte Carlo). It addresses the computational hardness of inference and the trade-offs between exactness and scalability. The structure of the models themselves is covered under Bayesian networks.

Core questions

How is a conditional or marginal probability computed from a joint model without enumerating the full distribution?
How does variable elimination exploit factorization to compute exact answers efficiently?
When is exact inference intractable, and what approximate methods are used instead?
How do sampling-based methods estimate posterior probabilities?

Key concepts

marginal and conditional queries
variable elimination
belief propagation (message passing)
junction tree and treewidth
loopy belief propagation
rejection sampling and likelihood weighting
Markov chain Monte Carlo
exact vs. approximate inference

Key theories

Belief propagation: In tree-structured networks, exact posteriors can be computed by passing local messages between neighboring nodes; Pearl's belief propagation performs this distributed computation and, applied to loopy graphs, gives a widely used approximate inference method.
Junction-tree (clique-tree) inference: Exact inference in general networks can be organized by clustering variables into a tree of cliques and propagating messages over it, giving correct answers in time exponential only in the largest clique (the treewidth).
Approximate inference by sampling: When exact inference is infeasible, Monte Carlo methods such as likelihood weighting and Markov chain Monte Carlo draw samples consistent with the evidence to estimate posterior probabilities, trading guaranteed exactness for scalability.

Clinical relevance

Inference algorithms are what make probabilistic models usable: they power diagnosis and decision-support systems, error-correcting codes (via belief propagation), computer vision, speech recognition, and bioinformatics, by computing the probabilities of hidden variables given observed data.

History

Pearl's belief propagation (1980s) gave exact inference for tree networks, and Lauritzen and Spiegelhalter's 1988 junction-tree method extended exact inference to general networks via local computations on cliques. The recognition that exact inference is NP-hard in general spurred extensive work on sampling and variational approximations.

Key figures

Judea Pearl
Steffen L. Lauritzen
David J. Spiegelhalter
Daphne Koller

Seminal works

pearl1986
lauritzen1988

Frequently asked questions

Is probabilistic inference always tractable?: No. Exact inference in general Bayesian networks is NP-hard, and its cost grows with the network's treewidth. For networks that are trees or have low treewidth, exact inference is efficient; otherwise approximate methods such as sampling or loopy belief propagation are used.
What is the difference between exact and approximate inference?: Exact inference, such as variable elimination or the junction-tree algorithm, computes the true posterior probabilities. Approximate inference, such as Monte Carlo sampling or loopy belief propagation, estimates them, which is necessary when exact computation is too expensive for a large or densely connected model.