10 - Bayesian Networks: Exact Inference

Course: COMP 341 Intro to AI - Koç University Instructor: Asst. Prof. Barış Akgün Topic: Inference by Enumeration and Variable Elimination

Where this fits. Lecture 09 gave us a compact representation: a DAG plus CPTs. But a model is only useful if we can ask it questions. This lecture answers P(Q | E = e) exactly — first with enumeration (the brute-force method from lecture 08, now phrased over a BN), then with variable elimination, which exploits the factorization from lecture 09 to avoid ever building the full joint. We end at a wall (exact inference is NP-hard), which motivates the sampling methods of lecture 11.

0 What Is Inference

Given observations (evidence), compute the probability of something you care about (the query):

• Mary called about the alarm — P(Burglary | Alarm, MaryCalled)?
• A student showed a medical report — P(Ill | Report)?

Setup: query variables Q, evidence E = e, hidden variables H (everything else). We want P(Q | E = e).

1 Running Example: The Alarm Network

2 The Four Methods

Key fact: exact inference in a general BN is NP-hard — a fundamental lower bound, not a weakness of any algorithm. This lecture covers the exact methods; lecture 11 covers sampling.

3 Inference by Enumeration

Using the BN factorization for the joint, any query is answered by select evidence → sum out hidden → normalize:

$P(Q \mid e) = \alpha \sum_h P(Q, e, h) = \alpha \sum_h \prod_i P(X_i \mid \text{Pa}(X_i))$

where α normalizes at the end (so you never compute P(e) directly).

Why it's slow: you effectively build the entire joint (2ⁿ rows) before summing out. With 30 hidden variables that's ~10⁹ terms per query. Variable elimination fixes exactly this waste.

4 Factors: The Building Block

A factor is a table mapping an assignment of some variables to a non-negative number. It's a generalized probability table — a CPT, a joint, or a partial product — and unlike a distribution it need not sum to 1. Fixing (observing) a variable removes it as a dimension, shrinking the table.

Two operations

Factor product (join). Multiply two factors on their shared variables — like a database join — producing a factor over the union of variables.

Elimination (sum-out). Sum a factor over all values of one variable, producing a smaller factor.

5 Enumeration as Factor Operations

Restated cleanly: (1) one factor per CPT, (2) apply evidence (restrict factors), (3) join all factors into the full joint, (4) eliminate all hidden variables, (5) normalize. Joining everything before eliminating is the inefficiency VE removes.

6 Variable Elimination (VE)

Core insight: interleave joining and summing-out. Eliminate a variable as soon as you have all factors mentioning it, keeping intermediate factors small. (Algebraic analogy: compute (u+v)(w+x)(y+z) as three factors, not by expanding into 8 terms.)

General Algorithm

VE(Query Q, Evidence E=e, BN):
  1. One factor per CPT.
  2. Instantiate evidence: restrict every factor mentioning an Eᵢ to its eᵢ rows.
  3. While hidden variables remain:
       a. Pick a hidden variable H.
       b. Collect all factors mentioning H.
       c. Join them → big factor.
       d. Sum out H → new factor.
       e. Replace the collected factors with the new one.
  4. Join all remaining factors.
  5. Normalize over Q.

Correct for any elimination order, but the order dramatically affects efficiency.

7 Elimination Ordering and Complexity

Ordering matters enormously. For a hub variable Z connected to a chain X₁…X_{n−1}: eliminating Z first forces a factor over all X's (2ⁿ entries); eliminating the chain left-to-right first keeps every factor at ≤ 4 entries. Exponential vs constant.

Treewidth. The best achievable maximum factor size is governed by the treewidth w of the network's undirected skeleton: best-case max factor is d^(w+1).

• Polytrees (singly-connected): w = 1 → factors ≤ d² → linear inference.
• Grids: w = O(√n).
• Complete graphs: w = n − 1 → fully exponential.

Finding the optimal order is itself NP-hard, so we use heuristics: min-degree (eliminate the least-connected variable) or min-fill (eliminate the one adding fewest new edges).

Cost is dominated by the largest factor generated: O(n · d^w) time, O(d^w) space. VE is never worse than enumeration (which is VE with the worst ordering). Exact inference is feasible for polytrees, small-treewidth networks, and small networks; large dense networks need approximate inference (lecture 11).

8 Enumeration vs VE Side-by-Side

9 Key Takeaways

• Inference asks P(Q | E = e); enumeration builds the full joint (O(dⁿ)) — correct but exponentially slow.
• A factor is a generalized table; two operations suffice — join (multiply on shared variables) and sum-out (eliminate one variable).
• VE interleaves them, never building the full joint; typically far faster.
• Ordering controls intermediate factor size (treewidth); optimal ordering is NP-hard, so use min-degree / min-fill heuristics.
• Exact inference is NP-hard in general; tractable for polytrees and small treewidth.

What's next. For large, densely connected networks (medical diagnosis, vision, thousands of variables), even VE blows up. Lecture 11 (Approximate Inference) gives up exactness for speed, estimating P(Q | e) by drawing samples instead of summing over all configurations.

End of Lecture 10 — COMP341 Intro to AI