Continuous Function

Probability

Variable Elimination

Variable elimination answers exact Bayesian-network queries by joining only the needed factors, summing hidden variables away, and watching the largest intermediate table.

status: reviewimportance: importantdifficulty 4/5math: graduateread: 24mlive demo
Back to Probability

Concept Structure

Variable Elimination

01Intuition

Start with the picture, metaphor, or geometric mechanism.

02Math

Make the objects explicit and connect them with notation.

03Code

Mirror the equations with runnable implementation details.

04Interactive Demo

Manipulate the mechanism and watch the idea respond.

1prerequisites
2next concepts
5related links

Learner Contract

What this page should let you do.

You are here becauseVariable elimination answers exact Bayesian-network queries by joining only the needed factors, summing hidden variables away, and watching the largest intermediate table.

This Probability concept is the current idea: keep the same invariant visible across Intuition, Math, Code, Interactive Demo.

Before thisBayesian Networks (review)

1 prerequisite listed; refresh them before leaning on the math or code.

Bayesian Networks (review)
By the end4/4 sections ready | runnable code expected | live demo

Explain the mechanism, trace the main notation, and test one prediction in the live demo.

Do this firstIntuition

Read the intuition before the notation; the math should name a mechanism you already felt.

Then go nextJunction Tree Intuition (planned)

Follow this edge after making one prediction here; the next page should reuse the result, not restart the route.

Test the linkManipulate one control and predict the visible change.

Claim/source review status

Substantive review recorded

1/1 claims have bounded review metadata; still check caveats and source scope.Metadata-derived; review may be AI-assisted. Not a human certification.
Claims1/1 reviewed
Sources5 cited
Codeattached
Demolive
Reviewed2026-07-02
Updatedpage 2026-07-02

Learning item flow

4/4 sections readyAsk about thisResearch room
ConceptVariable EliminationProbabilityEquationVariable Elimination equation 1Exact equationCodeVariable Elimination runnable code 1Exact runnable codeDemoVariable Elimination interactive demoInteractive demoClaimVariable elimination answers a Bayesian-network query by conditioning...Exact claim checkSourceStanford CS228 Notes: Variable EliminationExact source
ConceptVariable EliminationProbability
5 sources attachedLocal snapshot ready
concept:probability/variable-elimination
CodenearbyPredictbefore revealRoomitem handoff
01IntuitionStart with the picture, metaphor, or geometric mechanism.02MathMake the objects explicit and connect them with notation.03CodeMirror the equations with runnable implementation details.04Interactive DemoManipulate the mechanism and watch the idea respond.
01

01

Intuition

Build the mental picture first so the rest of the page has something to attach to.

Section prompt

A Bayesian network gives us many small probability tables. Exact inference asks a larger question:

P(Late∣Cloudy=true).P(\text{Late}\mid \text{Cloudy}=\text{true}).

The blunt way is to build the whole joint table, filter the rows where Cloudy is true, add up every hidden variable, and normalize. That works for a toy network, but it teaches the wrong habit. The table grows exponentially with the number of variables.

Variable elimination keeps the local factorization alive. It starts with the conditional tables that mention the evidence, query, and hidden variables. Then it chooses one hidden variable at a time:

  1. join every factor that mentions that variable;
  2. sum the variable out of the joined factor;
  3. put the smaller factor back into the ledger.

The order matters. Eliminating Wet Grass first in the lab below creates a joined factor over

(S,R,W,T,L),(S,R,W,T,L),

which has 25=322^5=32 rows for binary variables. Eliminating Sprinkler first creates only an 88-row joined factor. Same query, same network, different cost.

That is the real lesson: variable elimination is not just an algorithm name. It is a way of pushing sums inward so we avoid the full joint table when the graph structure lets us.

02

02

Math

Translate the story into symbols, assumptions, and a derivation you can inspect.

Section prompt
Equation 1C=Cloudy,S=Sprinkler,R=Rain,W=Wet Grass,T=Traffic,L=Late.C=\text{Cloudy},\quad S=\text{Sprinkler},\quad R=\text{Rain},\quad W=\text{Wet Grass},\quad T=\text{Traffic},\quad L=\text{Late}.Equation 2P(C,S,R,W,T,L)=P(C) P(S∣C) P(R∣C) P(W∣S,R) P(T∣R) P(L∣W,T).P(C,S,R,W,T,L) = P(C)\,P(S\mid C)\,P(R\mid C)\,P(W\mid S,R)\,P(T\mid R)\,P(L\mid W,T).

Reuse the six binary variables from the Bayesian-network page:

C=Cloudy,S=Sprinkler,R=Rain,W=Wet Grass,T=Traffic,L=Late.C=\text{Cloudy},\quad S=\text{Sprinkler},\quad R=\text{Rain},\quad W=\text{Wet Grass},\quad T=\text{Traffic},\quad L=\text{Late}.

The joint distribution factorizes as

P(C,S,R,W,T,L)=P(C) P(S∣C) P(R∣C) P(W∣S,R) P(T∣R) P(L∣W,T).P(C,S,R,W,T,L) = P(C)\,P(S\mid C)\,P(R\mid C)\,P(W\mid S,R)\,P(T\mid R)\,P(L\mid W,T).

For the query P(L∣C=true)P(L\mid C=\text{true}), treat C=trueC=\text{true} as evidence and remove CC from the remaining factor scopes:

ϕS(S)=P(S∣C=true),\phi_S(S)=P(S\mid C=\text{true}), ϕR(R)=P(R∣C=true),\phi_R(R)=P(R\mid C=\text{true}), ϕW(W,S,R)=P(W∣S,R),ϕT(T,R)=P(T∣R),ϕL(L,W,T)=P(L∣W,T).\phi_W(W,S,R)=P(W\mid S,R), \quad \phi_T(T,R)=P(T\mid R), \quad \phi_L(L,W,T)=P(L\mid W,T).

The query is

P(L∣C=true)=α∑S,R,W,TϕS(S)ϕR(R)ϕW(W,S,R)ϕT(T,R)ϕL(L,W,T),P(L\mid C=\text{true}) = \alpha \sum_{S,R,W,T} \phi_S(S)\phi_R(R)\phi_W(W,S,R)\phi_T(T,R)\phi_L(L,W,T),

where α\alpha is the normalizing constant that makes the two values of LL sum to one.

Variable elimination chooses an order for the hidden variables S,R,W,TS,R,W,T. If the next variable is ZZ, collect the current factors that mention ZZ:

FZ={ϕ: Z∈scope(ϕ)}.\mathcal{F}_Z=\{\phi:\,Z\in \mathrm{scope}(\phi)\}.

Join them:

ψ(u)=∏ϕ∈FZϕ(uscope(ϕ)),\psi(\mathbf{u})=\prod_{\phi\in\mathcal{F}_Z}\phi(\mathbf{u}_{\mathrm{scope}(\phi)}),

then sum out ZZ:

τ(u∖Z)=∑Zψ(u).\tau(\mathbf{u}_{\setminus Z})=\sum_Z \psi(\mathbf{u}).

Replace FZ\mathcal{F}_Z with τ\tau and continue.

The expensive object is the joined factor ψ\psi, not the final answer. For binary variables, a joined factor with kk variables has

2k2^k

rows. The largest such scope is the practical warning sign. In larger graphs, this is the intuition behind induced width, treewidth, junction trees, and why exact inference can become impossible even when the original factors are small.

03

03

Code

Keep the implementation aligned with the notation so the algorithm is legible.

Section prompt
Runnable code 1order_cases = { "efficient": ["S", "R", "W", "T"], "wet_first": ["W", "S", "R", "T"], "traffi...python
order_cases = {
    "efficient": ["S", "R", "W", "T"],
    "wet_first": ["W", "S", "R", "T"],
    "traffic_first": ["T", "W", "R", "S"],
}

factors = [
    ("P(S|C=true)", {"S"}),
    ("P(R|C=true)", {"R"}),
    ("P(W|S,R)", {"W", "S", "R"}),
    ("P(T|R)", {"T", "R"}),
    ("P(L|W,T)", {"L", "W", "T"}),
]

def rows(scope):
    return 2 ** len(scope)

def eliminate(order):
    live = [(name, set(scope)) for name, scope in factors]
    steps, largest = [], 0
    for z in order:
        used = [(name, scope) for name, scope in live if z in scope]
        kept = [(name, scope) for name, scope in live if z not in scope]
        joined = set().union(*(scope for _, scope in used))
        result = joined - {z}
        largest = max(largest, rows(joined))
        steps.append((z, sorted(joined), rows(joined), sorted(result)))
        live = kept + [(f"sum_{z}", result)]
    return largest, steps

for name, order in order_cases.items():
    largest, steps = eliminate(order)
    print(name, "largest joined factor:", largest, "rows")

The code intentionally tracks scopes and row counts, not probability values. That is enough to reveal the central mechanism: variable elimination can return an exact answer while its cost is controlled by the largest intermediate factor it creates.

04

04

Interactive Demo

Use direct manipulation to connect the explanation to a moving system.

Section prompt

Choose an elimination order, predict the largest joined factor, then reveal the ledger. The answer is hidden until you commit so the row-count explosion becomes something you reason through rather than something you merely read.

Live Concept Demo

Explore Variable Elimination

The stage is code-native and interactive. Use it to test the explanation against the mechanism.

difficulty 4/5graduatecode-aligned
Demo Prediction Checkpoint

Manipulate one control and predict the visible change.

Commit to what Variable Elimination should make visible before reading the result.

After The First Pass

Turn the concept into an inspected object.

Once the invariant is visible in the intuition, math, code, and demo, use these panels to inspect the mechanism visually, check source support, practice the idea, and attach a grounded research question.

Mechanism Storyboard

See the idea move before the page explains it

Variable elimination answers exact Bayesian-network queries by joining only the needed factors, summing hidden variables away, and watching the largest intermediate table.

Prediction open01 / Intuition
Prediction lens

Start with the picture, metaphor, or geometric mechanism.

Commit first

Before reading further, choose the kind of change Variable Elimination should make visible.

Visual Inquiry

Make the image answer a mathematical question

Variable elimination answers exact Bayesian-network queries by joining only the needed factors, summing hidden variables away, and watching the largest intermediate table.

4/4 stages readyLive demo connected
Prediction

Which visible object should carry the first intuition?

Commit first

Pick the cue that should make Variable Elimination easier to reason about before the page gives the answer.

Source Grounding

Canonical references for the mechanism on this page.

course-notes · 2026Stanford CS228 Notes: Variable EliminationStanford CS228

Grounds variable elimination as multiplying relevant factors, summing out hidden variables, and exposing order-dependent intermediate factor growth.

Open source
course-notes · 2026Berkeley CS188 Textbook: Variable EliminationUC Berkeley CS188

Supports the join-and-eliminate procedure and the contrast with constructing a full joint table.

Open source
documentation · 2026pgmpy Documentation: Variable Eliminationpgmpy

Open-source implementation reference for exact inference APIs and elimination-order heuristics such as induced width.

Open source
book · 2022Probabilistic Machine Learning: An IntroductionKevin P. Murphy

Probabilistic-ML reference for graphical-model inference and factor operations.

Open source
book · 2009Probabilistic Graphical Models: Principles and TechniquesDaphne Koller and Nir Friedman

Canonical PGM reference for exact inference, factor graphs, induced width, and junction-tree motivation.

Open source

Claim Review

Variable elimination answers exact Bayesian-network queries by joining only the needed factors, summing hidden variables away, and watching the largest intermediate table.

Status1 substantive review recorded

Claims without a substantive review badge still need exact source-support review.

Sources5 references

cs228-variable-elimination, berkeley-cs188-variable-elimination, pgmpy-variable-elimination, murphy-2022-probabilistic-ml, koller-friedman-2009-pgm

Local checks4 local checks

Use equations, runnable code, and demos to check whether the source support is operational.

Substantively reviewedVariable elimination answers a Bayesian-network query by conditioning evidence, repeatedly joining the factors that mention a hidden variable, summing that variable out, and normalizing; the computational cost is controlled by the largest intermediate factor scope created by the elimination order.Claim metadata: source checked

The sources support the page's finite discrete factor procedure, evidence-first restriction, join then sum-out update, order-dependent intermediate row counts, and the induced-width intuition that motivates junction-tree and message-passing methods.

Sources: Stanford CS228 Notes: Variable Elimination, Berkeley CS188 Textbook: Variable Elimination, pgmpy Documentation: Variable Elimination, Probabilistic Machine Learning: An Introduction, Probabilistic Graphical Models: Principles and TechniquesFinite binary teaching graph only; excludes continuous variables, numerical factor values beyond scope/row-count witnesses, MAP elimination, junction-tree calibration, approximate inference, and a GPT Pro publication pass.A bounded review summary is present; still check caveats and exact reference scope.

Checked Stanford CS228 for the algebra of moving sums inward through factor products and for order-dependent intermediate factors; checked Berkeley CS188 for the join/sum-out procedure and full-joint contrast; checked pgmpy docs for exact-inference APIs, elimination orders, and induced-width language; used Murphy and Koller/Friedman as book anchors for PGM inference context. GPT Pro publication critique remains pending because 127.0.0.1:51672 is unavailable.

Reviewer: codex-local-source-review; reviewed 2026-07-02
source-span-cs228-variable-eliminationsource-span-berkeley-cs188-variable-eliminationsource-span-pgmpy-variable-eliminationEquation 1Equation 2Runnable code 1Interactive demo

Source support candidates

course-notes 2026Stanford CS228 Notes: Variable Elimination

Grounds variable elimination as multiplying relevant factors, summing out hidden variables, and exposing order-dependent intermediate factor growth.

course-notes 2026Berkeley CS188 Textbook: Variable Elimination

Supports the join-and-eliminate procedure and the contrast with constructing a full joint table.

documentation 2026pgmpy Documentation: Variable Elimination

Open-source implementation reference for exact inference APIs and elimination-order heuristics such as induced width.

book 2022Probabilistic Machine Learning: An Introduction

Probabilistic-ML reference for graphical-model inference and factor operations.

Mechanism checks

Equation 1
C=Cloudy,S=Sprinkler,R=Rain,W=Wet Grass,T=Traffic,L=Late.C=\text{Cloudy},\quad S=\text{Sprinkler},\quad R=\text{Rain},\quad W=\text{Wet Grass},\quad T=\text{Traffic},\quad L=\text{Late}.
Equation 2
P(C,S,R,W,T,L)=P(C) P(S∣C) P(R∣C) P(W∣S,R) P(T∣R) P(L∣W,T).P(C,S,R,W,T,L) = P(C)\,P(S\mid C)\,P(R\mid C)\,P(W\mid S,R)\,P(T\mid R)\,P(L\mid W,T).
Runnable code 1order_cases = { "efficient": ["S", "R", "W", "T"], "wet_first": ["W", "S", "R", "T"], "traffi...Demo stateLive mechanism probe

Practice Loop

Try the idea before it explains itself

Variable elimination answers exact Bayesian-network queries by joining only the needed factors, summing hidden variables away, and watching the largest intermediate table.

Readiness0/3 checks ready
Predict

Before touching the demo, predict one visible change that should happen in Variable Elimination.

Hint 1

Reveal when your model needs a nudge.

Hint 2

Reveal when your model needs a nudge.

Hint 3

Reveal when your model needs a nudge.

Grounded research drawerClose
ConceptVariable EliminationProbability
Runnable code comparisonVariable Elimination runnable code 1order_cases = { "efficient": ["S", "R", "W", "T"], "wet_first": ["W", "S", "R", "T"], "traffi...Prediction before revealVariable Elimination interactive demoManipulate one control and predict the visible change.
Grounded room questionWhat is the smallest example that makes Variable Elimination click without losing the math?Local snapshot ready

Research Room

Attach the question to a claim, equation, code, or demo

Pick the concept, equation, source, runnable code, claim, misconception, or demo state before asking for help. The handoff keeps that page item in context.
Next local actionNo local draft saved yet

Open the draft below to save one note and next action in this browser.

conceptProbability

Variable Elimination

Attached question

What is the smallest example that makes Variable Elimination click without losing the math?

Local action draftNo local draft saved yetExpand only when ready to capture one local next action
Local action draft

This draft stays in this browser, attached to the selected learning item.

No local draft saved.
Evidence to inspect
  • References to inspect: attached references on this page.
  • Definition, prerequisite, and contrast concept links
  • The equation or runnable code that makes the concept operational
  • One demo state that shows the invariant instead of a slogan
What would resolve this
  • The learner can state the mechanism in their own words
  • The learner can name the prerequisite that would repair confusion
  • The learner can predict how the mechanism changes under one perturbation
Grounded AI handoff

I am working in Continuous Function's research reading room. Object: concept - Variable Elimination Selected item key: recorded for copy. Context: Probability Page anchor: recorded for copy. Open question: What is the smallest example that makes Variable Elimination click without losing the math? Evidence to inspect: - References to inspect: attached references on this page. - Definition, prerequisite, and contrast concept links - The equation or runnable code that makes the concept operational - One demo state that shows the invariant instead of a slogan What would resolve this: - The learner can state the mechanism in their own words - The learner can name the prerequisite that would repair confusion - The learner can predict how the mechanism changes under one perturbation Answer as a careful research tutor: stay source-grounded, separate verified evidence from assumptions, name the relevant math objects, and end with one next action.

View it in context
concept/concept-notebook/probability/variable-elimination concept:probability/variable-elimination