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 low-treewidth graphs, if the proper elimination order is used. Factors. Enabling a key reduction in algorithmic complexity, a factor formula_1, also known as a potential, of variables formula_2 is a relation between each instantiation of formula_3 of  variables formula_1 to a non-negative number, commonly denoted as formula_5. 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. Basic Operations. Variable Summation. Algorithm 1, called sum-out (SO), or marginalization, eliminates a single variable formula_3 from a set formula_7 of factors, and returns the resulting set of factors. The algorithm collect-relevant simply returns those  factors in formula_7 involving variable formula_3. Algorithm 1 sum-out(formula_3,formula_7) return formula_17 Example Here we have a joint probability distribution. A variable, formula_3 can be summed out between a set of instantiations where the set formula_19 at minimum must agree over the remaining variables. The value of formula_3 is irrelevant when it is the variable to be summed out. After eliminating formula_21, 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 formula_21. Also worthy to note, the summing-out operation is commutative. Factor Multiplication. Computing a product between multiple factors results in a factor compatible with a single instantiation in each factor. Algorithm 2 mult-factors(formula_3,formula_7) Factor multiplication is not only commutative but also associative. Inference. The most common query type is in the form formula_38 where formula_39 and formula_40 are disjoint subsets of formula_41, and formula_40 is observed taking value formula_43. A basic algorithm to computing p(X|E = e) is called "variable elimination" (VE), first put forth in. Taken from, this algorithm computes formula_38 from a discrete Bayesian  network B. VE calls SO to eliminate variables one by one. More specifically, in Algorithm 2, formula_7 is the set C of conditional probability tables (henceforth "CPTs") for B, formula_39 is a list of query variables, formula_40 is a list of observed variables, formula_43 is the corresponding list of observed values, and formula_49 is an elimination ordering for variables formula_50, where formula_51 denotes formula_52. Variable Elimination Algorithm VE(formula_53) return formula_60 Ordering. Finding the optimal order in which to eliminate variables is an NP-hard problem. As such there are heuristics one may follow to better optimize performance by order: Variable