A conditional probability, $P(Y\mid X_1,\mathrm{\dots },X_k)$ is a function from the variables $Y,X_1,\mathrm{\dots },X_k$ into non-negative numbers that satisfies the constraints that for each assignment of values to all of $X_1,\mathrm{\dots },X_k$ the values for $Y$ sum to 1. That is, given values to all of the variables, the function returns a number that satisfies the constraint:

With a finite set of variables with finite domains, conditional probabilities can be implemented as arrays. If there is an ordering of the variables (e.g., alphabetical) and the values in the domains are mapped into non-negative integers, there is a unique representation of each factor as a one-dimensional array that is indexed by natural numbers. This representation for a conditional probability is called a conditional probability table or CPT.

If the child variable is treated the same as the parent variables, the information is redundant; more numbers are specified than is required and a table could be inconsistent if it does not satisfy the above constraint. Using the redundant representation is common, but the following two methods are also used to specify and store probabilities:

• •

  Store unnormalized probabilities, which are non-negative numbers that are proportional to the probability. The probability can be computed by normalizing: dividing each value by the sum of the values, summing over all values for the domain of $Y$.

• •

  Store the probability for all-but-one of the values of $Y$. In this case, the probability of this other value can be computed to obey the constraint above. In particular, if $Y$ is binary, we only need to represent the probability for one value, say $Y=true$, and the probability for other other value, $Y=false$, can be computed from this.

A factor is a function from a set of random variables into a number. A factor $f$ on variables $X_1,\mathrm{\dots },X_j$ is written as $f(X_1,\mathrm{\dots },X_j)$. The variables $X_1,\mathrm{\dots },X_j$ are the variables of the factor $f$, and $f$ is a factor on $X_1,\mathrm{\dots },X_j$.

Conditional probabilities are factors that also obey the constraint of Equation 8.1. This section describes some operations on factors, including conditioning, multiplying factors and summing out variables. The operations can be used for conditional probabilities, but do not necessarily result in conditional probabilities.

Suppose $f(X_1,\mathrm{\dots },X_j)$ is a factor and each $v_i$ is an element of the domain of $X_i$. $f(X_1=v_1,X_2=v_2,\mathrm{\dots },X_j=v_j)$ is a number that is the value of $f$ when each $X_i$ has value $v_i$. Some of the variables of a factor can be assigned to values to make a new factor on the other variables. This operation is called conditioning on the values of the variables that are assigned. For example, $f(X_1=v_1,X_2,\mathrm{\dots },X_j)$, sometimes written as $f{(X_1,X_2,\mathrm{\dots },X_j)}_{X_1=v_1}$, where $v_1$ is an element of the domain of variable $X_1$, is a factor on $X_2,\mathrm{\dots },X_j$.

Factors can be multiplied together. Suppose $f_1$ and $f_2$ are factors, where $f_1$ is a factor that contains variables $X_1,\mathrm{\dots },X_i$ and $Y_1,\mathrm{\dots },Y_j$, and $f_2$ is a factor with variables $Y_1,\mathrm{\dots },Y_j$ and $Z_1,\mathrm{\dots },Z_k$, where $Y_1,\mathrm{\dots },Y_j$ are the variables in common to $f_1$ and $f_2$. The product of $f_1$ and $f_2$, written $f_1*f_2$, is a factor on the union of the variables, namely $X_1,\mathrm{\dots },X_i,Y_1,\mathrm{\dots },Y_j,Z_1,\mathrm{\dots },Z_k$, defined by:

The remaining operation is to sum out a variable in a factor. Given factor $f(X_1,\mathrm{\dots },X_j)$, summing out a variable, say $X_1$, results in a factor on the other variables, $X_2,\mathrm{\dots },X_j$, defined by

where $\{v_1,\mathrm{\dots },v_k\}$ is the set of possible values of variable $X_1$.

Given evidence $Y_1=v_1$, …, $Y_j=v_j$, and query variable or variables $Q$, the problem of computing the posterior distribution on $Q$ can be reduced to the problem of computing the probability of conjunctions:

The algorithm computes the factor $P(Q,Y_1=v_1,\mathrm{\dots },Y_j=v_j)$ and normalizes. Note that this is a factor only of $Q$; given a value for $Q$, it returns a number that is the probability of the conjunction of the evidence and the value for $Q$.

Suppose the variables of the belief network are $X_1,\mathrm{\dots },X_n$. To compute the factor $P(Q,Y_1=v_1,\mathrm{\dots },Y_j=v_j)$, sum out the other variables from the joint distribution. Suppose $Z_1,\mathrm{\dots },Z_k$ is an enumeration of the other variables in the belief network, that is,

and the variables $Z_i$ are ordered according to an elimination ordering.

The probability of $Q$ conjoined with the evidence is

By the chain rule and the definition of a belief network,

where $parents(X_i)$ is the set of parents of variable $X_i$.

The belief network inference problem is thus reduced to a problem of summing out a set of variables from a product of factors. The distribution law specifies that a sum of products such as $xy+xz$, can be simplified by distributing out the common factors (here $x$), which results in $x(y+z)$. The resulting form is more efficient to compute. Distributing out common factors is the essence of the VE algorithm. The elements multiplied together are called “factors” because of the use of the term in algebra. Initially, the factors represent the conditional probability distributions, but the intermediate factors are just functions on variables created by adding and multiplying factors.

To compute the posterior distribution of a query variable given observations

1. 1.

   Construct a factor for each conditional probability distribution.

2. 2.

   Eliminate each of the non-query variables:

   • •

     if the variable is observed, its value is set to the observed value in each of the factors in which the variable appears,

   • •

     otherwise the variable is summed out.

3. 3.

   Multiply the remaining factors and normalize.

To sum out a variable $Z$ from a product $f_1,\mathrm{\dots },f_k$ of factors, first partition the factors into those not containing $Z$, say $f_1,\mathrm{\dots },f_i$, and those containing $Z$, $f_{i+1},\mathrm{\dots },f_k$; then distribute the common factors out of the sum:

VE explicitly constructs a representation (in terms of a multidimensional array, a tree, or a set of rules) of the rightmost factor.

Figure 8.10 gives pseudocode for the VE algorithm. The elimination ordering could be given a priori or computed on the fly. It is worthwhile to select observed variables first in the elimination ordering, because eliminating these simplifies the problem.

This algorithm assumes that the query variable is not observed. If it is observed to have a particular value, its posterior probability is just 1 for the observed value and 0 for the other values.

To speed up the inference, variables that are irrelevant to answer a query given the observations can be pruned. In particular, any node that has no observed or queried descendants and is itself not observed or queried may be pruned. This may result in a smaller network with fewer factors and variables. For example, to compute $P(Alarm\mid Fire=true)$, the variables $Report$, $Leaving$ and $Smoke$ may be pruned.

The complexity of the algorithm depends on a measure of complexity of the network. The size of a tabular representation of a factor is exponential in the number of variables in the factor. The treewidth of a network, given an elimination ordering, is the maximum number of variables in a factor created by summing out a variable when using the elimination ordering. The treewidth of a belief network is the minimum treewidth over all elimination orderings. The treewidth depends only on the graph structure and is a measure of the sparseness of the graph. The complexity of VE is exponential in the treewidth and linear in the number of variables. Finding the elimination ordering with minimum treewidth is NP-hard, but there are some good elimination ordering heuristics, as discussed for CSP VE.

The moral graph of a belief network is the undirected graph where there is an arc between any two nodes that appear in the same initial factor. This is obtained by “marrying” the parents of a node, and removing the directions. If we prune as outlined in the previous paragraph, moralize the graph, and remove all observed variables, only those variables connected to the query in this graph are relevant to answering the query. The other variables can be pruned.

Many modern exact algorithms use what is essentially variable elimination, and they speed it up by preprocessing as much as possible into a secondary structure before any evidence arrives. This is appropriate when, for example, the same belief network may be used for many different queries, and where observations are added incrementally. The algorithms save intermediate results so that evidence is incrementally added. Unfortunately, extensive preprocessing, allowing arbitrary sequences of observations and deriving the posterior on each variable, precludes pruning the network. So for each application you need to choose whether you will save more by pruning irrelevant variables for each query and observation or by preprocessing before you have any observations.