computational complexity of graphical model inference
(40 minutes to learn)
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.
This concept has the prerequisites:
Core resources (read/watch one of the following)
→ 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
- When exact inference is infeasible, we must resort to approximate inference algorithms, such as:
- create concept: shift + click on graph
- change concept title: shift + click on existing concept
- link together concepts: shift + click drag from one concept to another
- remove concept from graph: click on concept then press delete/backspace
- add associated content to concept: click the small circle that appears on the node when hovering over it
- other actions: use the icons in the upper right corner to optimize the graph placement, preview the graph, or download a json representation