Does the algorithm learn the probabilities?

No. In this use, it computes with the supplied probabilistic model.

Can it answer a query about several variables?

Yes. Retain those variables and eliminate the other hidden variables.

What if the evidence probability is zero?

Ordinary conditional normalization is undefined; the model or evidence requires examination rather than returning a fabricated posterior.

AI Glossary / Graphs and symbolic AI / Advanced

Variable elimination

Definition

Variable elimination is a method for computing with a factored model by removing variables one at a time while preserving their effect on the remaining calculation. In probabilistic inference, it multiplies the factors involving a hidden variable and sums over that variable's values. Repeating this process can produce an exact marginal or posterior distribution without first constructing the complete joint table.

What it means

A model may contain many variables, while a particular question concerns only a few. Unobserved variables still influence the answer, but their individual values need not appear in the final result. Variable elimination accounts for their possibilities and stores the resulting contribution as a new factor.
“Elimination” therefore does not mean deleting inconvenient information or declaring an unknown variable false. It means replacing a collection of factors with a mathematically equivalent summary for the calculation. The idea also appears in constraint satisfaction and optimization. Here the focus is probabilistic sum-product elimination.

How it works

Start with factors describing the joint distribution. Restrict factors to the observed values of evidence variables. Choose an order for the hidden variables, retaining the query variables.
For each hidden variable Z, collect every current factor containing Z, multiply them, and sum the product over Z. Replace the collected factors with the resulting factor, whose scope no longer includes Z. Factors that do not contain Z remain available for later steps.
After all hidden variables are eliminated, multiply the remaining factors. For a posterior query, normalize the resulting values over the query variables, provided the evidence has positive probability.
Elimination order does not change the exact result, but it can greatly change intermediate factor sizes and resource requirements. Those sizes depend on the connections among variables and their domain sizes, not merely the total number of variables.

Three practical examples

A maintenance model estimates a machine fault from a received report while the internal alarm state is unobserved. Elimination sums over possible alarm states rather than assuming that a report perfectly reveals the alarm.
A logistics network estimates a late-arrival probability from known conditions while intermediate disruption variables remain uncertain. Factored inference can reuse the model's structure instead of enumerating every complete scenario explicitly.
A small exact model provides a reference answer for evaluating an approximate inference implementation. Agreement on such cases helps identify mistakes in conditioning, factor multiplication, or normalization before larger tests are attempted.

Think of it this way

Imagine combining several accounting sheets that all depend on one temporary category, then totaling over that category. The resulting sheet preserves its contribution to the final totals while no longer listing it separately. Simply throwing away the original sheets would lose the contribution; proper elimination replaces them with the necessary summary.

Worked example

Consider a toy Bayesian network F→A→R. F is a machine fault, A an alarm state, and R a received positive report. All variables are binary. The model assumes R depends on F only through A.
Set P(F=true)=0.1. The alarm probabilities are P(A=true|F=true)=0.8 and P(A=true|F=false)=0.2. Reporting probabilities are P(R=true|A=true)=0.9 and P(R=true|A=false)=0.1. Complementary probabilities follow by subtraction from one.
Observe R=true and ask for P(F=true|R=true). The factors are P(F), P(A|F), and P(R=true|A). To eliminate A, multiply the last two and sum over A, producing g(F).
For F=true, g(true)=0.8 × 0.9 + 0.2 × 0.1 = 0.74. For F=false, g(false)=0.2 × 0.9 + 0.8 × 0.1 = 0.26. These are report likelihoods conditional on F, not posterior fault probabilities.
Multiply by the prior: the unnormalized values are 0.1 × 0.74 = 0.074 for F=true and 0.9 × 0.26 = 0.234 for F=false. Their sum is 0.308, the evidence probability. Normalization gives 0.074/0.308 = 37/154, approximately 0.2403, for the posterior fault probability.
Direct enumeration of all eight assignments to F, A, and R gives the same answer. The hidden alarm has disappeared from the final factor, but its possible states have both contributed.

Illustrative case study

In a fictional equipment-support tool, an initial implementation removes an unobserved alarm variable and its associated tables before answering a fault query. It then returns a result that barely responds to the received report.
The review team replaces that deletion with the multiply-and-sum operation in the worked example. It checks the resulting factor against a complete enumeration on the small model and verifies that the final posterior values sum to one. The team also verifies that positive reports can occur without a fault, as represented by the conditional probabilities.
When the model expands, reviewers compare elimination orders and monitor intermediate factor sizes. They preserve the distinction between computational correctness and model accuracy: an exact answer under a poorly calibrated alarm model can still be unsuitable for real decisions.

Common misconceptions and mistakes

“Eliminate means ignore.” The variable's contribution must be retained in the replacement factor.
“A hidden variable is an observed negative value.” Unknown and false are different conditions.
“Every intermediate factor is a normalized probability distribution.” General factors need not sum to one.
“A favorable elimination order changes the correct posterior.” It changes computational cost, while exact arithmetic yields the same result.
“Exact inference guarantees an accurate real-world prediction.” Exactness concerns the specified model; its assumptions and parameters may still be wrong.

Business use

Variable elimination is useful when a probabilistic model is structured enough for exact inference to fit the available time and memory. Evaluate representative queries and evidence patterns, since they can lead to different intermediate computations.
Inspect the largest factors and test practical ordering heuristics before committing to a deployment design. If resource needs remain excessive, consider an appropriately validated approximation or a revised model. Maintain small cases with independently computed answers as a check on implementation changes. Separately assess probability calibration and conditional-independence assumptions; improving computational efficiency does not compensate for a model that omits a relevant influence.

Check your understanding

Which variable is summed out in the example?

Answer: A, the unobserved alarm state.

Why is 0.74 not the answer?

Answer: It is P(R=true|F=true), before incorporating the fault prior and normalizing.

What does the normalizer 0.308 represent?

Answer: The probability of the observed positive report under the model.

Related terms

Learn next

Eliminate two hidden variables in different orders and compare intermediate factor sizes. Then distinguish sum-product inference from maximization-based tasks, where the operations and ordering requirements can differ.

Factor

Sources

Poole and Mackworth, Variable Elimination for Belief Networks: https://artint.info/2e/html2e/ArtInt2e.Ch8.S4.SS1.html University of California, Berkeley, CS 188, Exact Inference in Bayes Nets: https://inst.eecs.berkeley.edu/~cs188/textbook/bayes-nets/elimination.html

Previous: Variable byte encoding Next: Variable importances