Treewidth in machine learning
Why exact inference is cheap on sparse models and hopeless on dense ones.
The junction-tree connection
Exact inference in a probabilistic graphical model — a Bayesian network or Markov random field — runs the junction-tree algorithm, and a junction tree is precisely a tree decomposition of the model's structure. The cost of inference is exponential in the size of the largest clique, which is the treewidth plus one.
This is why practitioners chase sparse, low-treewidth model structures: a model whose graph has treewidth 5 admits exact inference; one with treewidth 50 forces you into approximate methods like loopy belief propagation or variational inference.
The same meter again
Probabilistic inference, constraint satisfaction, and quantum-circuit simulation are the same computation — a sum-product over a network — and treewidth is the shared exponent in all three. The thesis treats this not as a coincidence but as the meter showing through three different substrates.
Questions
Why is exact inference sometimes infeasible?
Because its cost is exponential in treewidth. High-treewidth models force approximate inference; the width is the dividing line.
What is a junction tree?
A tree decomposition of a graphical model, used to organize exact inference as message passing between cliques.