Variable elimination is an exact inference algorithm for probabilistic graphical models that computes marginal and conditional marginal queries by exploiting the factorization of the joint distribution: summations are pushed as far inside the product of factors as possible so each sum ranges over the smallest table it can, rather than over the full exponential-size joint. Each elimination step marginalizes one variable out of the factors mentioning it and produces a new intermediate factor, which is equivalent to adding fill-in edges to the graph; the cost of the whole computation is governed by the size of the largest clique so created, called the induced width of the elimination ordering. The concept sits in the inference half of probabilistic graphical models — a subfield of machine learning and probabilistic reasoning — and applies uniformly to directed (Bayesian network) and undirected (Markov random field) representations once conditional distributions are recast as potentials.
Variable elimination is an exact inference algorithm for probabilistic graphical models that computes marginal and conditional marginal queries by exploiting the factorization of the joint distributi…