Exact inference in probabilistic graphical models by variable elimination is exponential in the induced width of the elimination ordering, whose minimum over all orderings defines the tree width of the graph; finding an optimal ordering is NP-hard in general, though for trees a leaf-to-root ordering is optimal. Because variable elimination discards its intermediate factors, each new marginal query must be recomputed from scratch, which motivates belief propagation: a message-passing scheme that caches and incrementally reuses the intermediate factors so that many marginal queries can be answered from one round of computation. The same elimination machinery answers conditional queries as ratios of marginals, and yields MAP inference when the summation operator is replaced by maximisation with back-pointers recording the argmax at each step.
Exact inference in probabilistic graphical models by variable elimination is exponential in the induced width of the elimination ordering, whose minimum over all orderings defines the tree width of t…