Sum a joint model without enumerating it all at once
A probabilistic model can be specified by several small tables. To answer a query, multiplying all of them into one giant table is valid but can be unnecessary. Variable elimination uses distributivity to sum hidden variables one at a time while retaining the interactions that remain relevant.
Definition 12.1.1
(Factor and factor product)
Assume finitely many discrete variables, each with a finite nonempty domain. A factor is a real nonnegative table on a specified subset of variables, its scope. The product of factors is evaluated by multiplying entries consistent with an assignment to the union of their scopes. A scalar is a factor with empty scope. A Bayesian network supplies factors on a directed acyclic graph; their product is its joint distribution. The following calculation also applies to other explicitly given nonnegative factor products, provided their normalization is handled separately.
Definition 12.1.2
(Restriction and the unnormalized query mass)
Fix query variables , observed variables with values , and hidden variables , all disjoint and covering the model variables. First restrict every factor containing evidence by substituting the corresponding observed values. Its scope loses those variables. For a query assignment , the desired unnormalized mass is
when the denominator is positive. If the factor product is a normalized joint distribution, this denominator is . More generally, for unnormalized weights with positive total , the induced distribution has and the same posterior ratio. If , the weights define no probability distribution. The first expression uses the original factors; after restriction the evidence arguments have already been substituted. If the denominator is zero, this posterior is undefined, not a zero vector to normalize.
The elimination step
Definition 12.1.3
(Elimination of a variable)
Choose a hidden variable . Collect all current factors whose scopes contain , say , and let be the union of their scopes. Replace them by the single factor
where each is the restriction of the current assignment to factor 's scope, with . Keep every factor not containing , including scalars. If no factor contains , summing it contributes the size of its domain as a scalar; ordinary network inputs normally retain a factor for each unobserved variable, but the convention makes the step explicit. Repeat for each variable in . Do not eliminate query variables before reading out their values.
Theorem 12.1.4
(Invariant of variable elimination)
Let the hidden variables be eliminated in any order, and let be the set eliminated so far. As a function of the variables outside , the product of the current factors equals the sum, over all assignments to , of the product of the restricted original factors. In particular, when the product of the remaining factors equals for every query assignment, whatever the order.
Proof
(Induction on the eliminated set)
Induct on the number of eliminated variables. For the current factors are the restricted original factors, and the claim is an identity. Suppose it holds for , and eliminate a further variable using the group of current factors whose scopes contain . Fix an assignment to the variables outside . No factor outside the group has in its scope, so the product of those factors does not depend on and factors out of the sum over :
The right side is the product of the new current factors at . The left side is the sum over of the product of the old current factors at . By the induction hypothesis that old product is the sum over of the original product, and finite sums can be rearranged, so the new product at is the sum over of the original product. This completes the induction. The argument concerns which variables occur in which scope; it asserts no probabilistic independence of random variables. When , every remaining scope lies in , and a query variable that occurs in no scope only extends the resulting function constantly.
Proof X-ray
Where the proof needs the whole group
The proof uses one structural fact: once the group is collected, no remaining factor has in its scope. That is what lets leave the sum over , and it holds only because the group contains every current factor that mentions . A single such factor left outside depends on and invalidates the step, so nothing weaker than complete collection suffices. The proof does not use acyclicity of the network; acyclicity affects only how large the scopes become.
The hidden variables may be eliminated in any order: finite sums and products can be rearranged, so exact arithmetic produces the same final masses. Intermediate factor scopes can nevertheless differ, changing time and storage. In floating-point arithmetic, different orders may also round differently. Rescaling a factor by a common positive constant preserves a final normalized posterior, but recovering the original evidence mass requires tracking all such constants; numerical underflow should not be confused with an exact zero.
Common mistake
(Reading scope as independence)
When is eliminated in the chain below, the factor stays outside the sum because is not in its scope. That is a statement about table arguments. It does not show that and are independent; they are not, since while .
A chain with observed evidence
Worked example 12.1.5
(Posterior of the first variable in a chain)
Consider binary variables with the explicitly assumed factorization
Let , , , and . The other binary probabilities are complements. We seek .
Restrict the last factor to , then eliminate hidden :
For , . For , . The remaining unnormalized masses are and . Hence the evidence has probability , and
Common mistake
(Reading an intermediate factor as a posterior)
The intermediate factor is a likelihood as a function of , not a posterior distribution over . Its two entries happen to sum to one in this example, but that is a numerical coincidence and does not make the posterior. Normalizing alone does not give the posterior: the prior still matters. Dividing by a common positive constant and then multiplying by the prior and normalizing at the end gives the same posterior, because that constant cancels.
Concept lensAlgorithmic
The chain elimination as a matrix–vector product
Let , with the first index for and the second for , and let . Then , because . Here
which matches the entries computed above. On a chain, eliminating the hidden variables from the evidence end is a sequence of matrix–vector products. When scopes are larger the tables are tensors and the same summation is a tensor contraction, which is why the elimination order governs the cost.
Worked example 12.1.6
(Posterior of the middle variable)
For the same chain, query with evidence , now eliminating the hidden variable . The factors containing are and , so
which gives and . Multiplying by the restricted factor gives the masses for and for . The total is , the same evidence probability as before, as the order independence in the invariant requires. Hence and .
Worked example 12.1.7
(Zero entries and impossible evidence)
Change the chain so that and . Then and , so the masses are and . The total is , so and . A zero table entry does not make the evidence impossible. Now also set . Every is , the total mass is , and is undefined: the model gives the observation probability zero, and the algorithm must report that instead of normalizing.
Counterexample mode
Eliminating a variable without its evidence factor
A tempting shortcut eliminates using only the factor , on the grounds that is a statement about . In the chain this gives for both values of , so the masses are the prior and , and the claimed posterior is . The correct value is . The omitted factor has in its scope, so it belongs to the group, and leaving it out discards the evidence. The repair is the rule of the elimination step: collect all current factors whose scope contains .
Cost and modeling limits
Proposition 12.1.8
(Cost of one elimination step)
Eliminate from a group of dense factors whose scopes have union . The step reads and multiplies at most table entries, and the new factor has entries.
Proof
(Counting assignments to the union scope)
There are assignments to . For each one, read one entry from each of the factors, multiply them, and add the product into the entry of for the assignment with removed. The factor is a dense table on .
An elimination order that creates large scopes can require exponentially many entries even when every original table is small. Variable elimination is exact for the specified model; it does not establish that the factorization or evidence accurately models the world.
Exercises
Quick check
(In the chain above, compute by summing over . Which probabilities must be complemented?)
Write .
Solution · Answer
. The complemented probabilities are , and . As a check, .
Quick check
(Why must an evidence value of probability zero be reported rather than normalized? What does a zero entry in an otherwise positive evidence total mean?)
The posterior is a mass divided by the evidence total; ask what the quotient is when the total is zero.
Solution · Answer
The posterior is . If the total is zero the quotient is : the model gives the observed evidence probability zero, so the conditional probability is undefined, and replacing it by a uniform vector would add an assumption. It must be reported. If the total is positive and , then has posterior probability zero under that evidence and the other entries are normalized as usual; this is a legitimate answer, for example when .
Quick check
(If a factor does not mention the eliminated variable, why can it remain outside that summation? Why does this not prove the variables in its scope are probabilistically independent of the eliminated variable?)
Write as , then look for a counterexample in the chain.
Solution · Answer
A factor without in its scope is a constant in the sum over , so distributivity gives ; this concerns table arguments only. Probabilistic independence is a property of the joint distribution. In the chain, stays outside the sum when is eliminated, yet , so and are dependent.