Variable elimination

Variable elimination (VE) is a simple and general exact inference algorithm in probabilistic graphical models, such as Bayesian networks and Markov random fields. It can be used for inference of maximum a posteriori (MAP) state or estimation of conditional or marginal distributions over a subset of variables. The algorithm has exponential time complexity, but could be efficient in practice for the low-treewidth graphs, if the proper elimination order is used. Variable elimination (VE) is a simple and general exact inference algorithm in probabilistic graphical models, such as Bayesian networks and Markov random fields. It can be used for inference of maximum a posteriori (MAP) state or estimation of conditional or marginal distributions over a subset of variables. The algorithm has exponential time complexity, but could be efficient in practice for the low-treewidth graphs, if the proper elimination order is used. Enabling a key reduction in algorithmic complexity, a factor f {displaystyle f} , also known as a potential, of variables V {displaystyle V} is a relation between each instantiation of v {displaystyle v} of variables f {displaystyle f} to a non-negative number, commonly denoted as f ( x ) {displaystyle f(x)} . A factor does not necessarily have a set interpretation. One may perform operations on factors of different representations such as a probability distribution or conditional distribution. Joint distributions often become too large to handle as the complexity of this operation is exponential. Thus variable elimination becomes more feasible when computing factorized entities. Algorithm 1, called sum-out (SO), or marginalization, eliminates a single variable v {displaystyle v} from a set ϕ {displaystyle phi } of factors, and returns the resulting set of factors. The algorithm collect-relevant simply returns those factors in ϕ {displaystyle phi } involving variable v {displaystyle v} . Algorithm 1 sum-out( v {displaystyle v} , ϕ {displaystyle phi } ) Example Here we have a joint probability distribution. A variable, v {displaystyle v} can be summed out between a set of instantiations where the set V − v {displaystyle V-v} at minimum must agree over the remaining variables. The value of v {displaystyle v} is irrelevant when it is the variable to be summed out. After eliminating V 1 {displaystyle V_{1}} , its reference is excluded and we are left with a distribution only over the remaining variables and the sum of each instantiation. The resulting distribution which follows the sum-out operation only helps to answer queries that do not mention V 1 {displaystyle V_{1}} . Also worthy to note, the summing-out operation is commutative.