computational complexity of graphical model inference
(40 minutes to learn)
Summary
The major inference problems for graphical models (marginalization, MAP assignment, and partition function) are all intractable in the worst case. In particular, marginalization and partition function computation are both #P-complete, and MAP inference is NP-complete.
Context
This concept has the prerequisites:
Core resources (read/watch one of the following)
-Paid-
→ Probabilistic Graphical Models: Principles and Techniques
A very comprehensive textbook for a graduate-level course on probabilistic AI.
Location:
Section 9.1, pages 288-292
See also
- When exact inference is infeasible, we must resort to approximate inference algorithms, such as:
- loopy belief propagation , which applies the BP update rules on non-tree graphs
- Markov chain Monte Carlo , a sampling-based method
- variational inference , which tries to find a tractable approximation to the posterior