variable elimination

(1.7 hours to learn)

Summary

Variable elimination is a simple algorithm for marginalization and partition function computation in graphical models. It is based on interchanging sums and products in the definitions of marginals or partition functions. While it produces exact answers, the complexity blows up exponentially in the worst case.

Context

This concept has the prerequisites:

Goals

  • Does the order of elimination matter for directed graphical models? Undirected graphical models?
  • Is it usually necessary to keep track of the partition function when performing variable elimination in an undirected graphical model?

Core resources (read/watch one of the following)

-Free-

Coursera: Probabilistic Graphical Models (2013)

-Paid-

Supplemental resources (the following are optional, but you may find them useful)

-Paid-

See also

  • If we want to perform multiple queries, we go through lots of redundant calculations. Belief propagation gives a way of reusing the computations.
  • In Gaussian graphical models , variable elimination is [equivalent](gaussian_variable_elimination_as_gaussian_elimination) to [Gaussian elimination](gaussian_elimination) .