Take a Break
5:00
Inhale…
Give your mind a break — no phone, no music, just idle time or a quick walk.
Bayesian Networks: D-Separation, Variable Elimination, and Approximate Inferencing
Prerequisite Knowledge
This lecture builds on the following concepts from earlier lectures. If any of them feel unfamiliar, it is worth reviewing the linked notes before working through d-separation and variable elimination.
Previously Covered in This Subject
- Bayesian network fundamentals and construction — covered in Lecture 12
- Linearization and the chain rule — covered in Lecture 12
- Joint and conditional probability queries — covered in Lecture 12
- Conditional independence and the Markov blanket — covered in Lecture 12
- Joint probability distributions — covered in Lecture 11
13.1 Review of Bayesian Network Querying
13.1.1 Types of Queries and Inferencing
Hook — you already know how to answer questions from a Bayesian network, but only when the question is asked the right way. The moment a query lands directly on a dependent variable — "what is the chance I have a fever?" — the tables alone no longer answer it. This lecture opens by recapping exactly what queries we can answer directly, then spends the rest of the time on what to do with the ones we cannot.
A Bayesian network (or Bayes net) is a directed acyclic graph (DAG): each node represents a random variable, and each edge represents a direct conditional dependency from a parent to a child. Every node carries a conditional probability table (CPT) that quantifies how the node's values depend on its parents' values. This lecture builds on prior sessions covering Bayesian network creation, the chain rule, linearization, marginalization, and the burglary example. Before introducing two new techniques — d-separation and variable elimination — the professor re-establishes the query vocabulary, because every technique in this lecture exists to answer one of these query forms faster or more rigorously.
There are two fundamental forms of queries one can pose against a Bayesian network:
- Joint probability queries — e.g., "What is \(P(B, J, M)\)?" (the probability that all three variables take their stated values together). To answer these, we linearize the variables into a topological order, apply the chain rule to decompose the joint into a product of conditionals, and read values directly from the CPTs. Multiplication only, no summing, no normalizing.
- Conditional probability queries — e.g., "What is \(P(B \mid J, M)\)?" (the probability of B given that we already know J and M). These require converting the conditional into joint probability form using a probability identity, then applying marginalization over hidden variables to reduce the expression to computable joint probabilities, and finally dividing or normalizing.
The chain rule for Bayesian networks. The whole query-answering machinery rests on one formula: any joint probability factorizes along the network's edges.
\[ P(X_1, X_2, \ldots, X_n) = \prod_{i=1}^{n} P(X_i \mid \text{Parents}(X_i)) \]
Every symbol is named: \(X_1, \ldots, X_n\) are all the variables of the network, listed in linearized order (child before parent), and \(\text{Parents}(X_i)\) is the set of variables that have a directed edge into \(X_i\). The product runs over all \(n\) nodes. Because each factor is a conditional on the parents only, each factor's value can be read straight out of the corresponding CPT row.
Linearization orders variables so that every child appears before its parents when writing the chain rule. This order is what guarantees that when we expand a joint, every factor we need is already a CPT row we can look up — no factor ever depends on a variable that has not been named yet.
Marginalization sums out hidden (unobserved) variables from a joint distribution. For a conditional probability query, after converting to joint form using probability identities, we marginalize over hidden variables to get individual joint probability answers, then substitute back.
The professor's verbal description of the whole flow: "When it is joint, I will first write down the query, apply my chain rule, and in the chain rule I will actually go and look at what are the things which are irrelevant." And on marginalization: "For all the hidden variables also, I should take into account. I will get those different formulas when I eliminate all of my summations."
Recap of the recipe on the burglary network. The burglary network (Alarm \(A\), Burglary \(B\), Earthquake \(E\), JohnCalls \(J\), MaryCalls \(M\)) shows how the two query types differ in mechanics:
- Joint query \(P(B, J, M)\): linearize to \(J, M, B\) order, apply the chain rule to get \(P(J \mid B) \cdot P(M \mid B) \cdot P(B)\), read each factor from its CPT, and multiply. One pass, no sums.
- Conditional query \(P(B \mid J, M)\): rewrite as \(\frac{P(B, J, M)}{P(J, M)}\), expand each joint with the chain rule, marginalize (sum over) the hidden variables \(A\) and \(E\) that appear inside, and divide. The summing step is what a conditional query adds on top of a joint one.
The takeaway: joint = multiply and read; conditional = convert, marginalize, divide.
There are also different types of inferencing within a Bayesian network. These describe the direction of the reasoning, and they matter because the direction decides which conditional independencies we are allowed to exploit:
- Causal — reasoning from cause to effect (top-down). Example: "Given that it rained, how likely is the grass to be wet?"
- Diagnostic — reasoning from effect to cause (bottom-up). Example: "Given that the grass is wet, how likely is it that it rained?"
- Intercausal — reasoning between co-causes of a shared effect (the explaining away pattern). Example: two diseases that both cause a fever — knowing one explains the fever away and lowers belief in the other.
- Mixed intercausal — combining multiple evidence sources scattered across the network, some upstream and some downstream of the query.
Assumptions and scope. Every formula in this recap rests on the network being a correct DAG: the chain rule factorization is exact only when the graph really captures all the dependencies and the CPTs are true conditional probabilities. If an edge is missing (a real dependency was not drawn), the chain rule quietly undercounts; if a CPT row does not sum to 1, every downstream query is off. These are modeling errors, not arithmetic errors — no amount of careful marginalization repairs a network that was built wrong. The good news: within a correct network, enumeration-style answers are exact, which is the point of the professor's remark below.
Exact inferencing computes answers precisely using the Bayesian network's structure and CPTs — no approximation, no random sampling. Two techniques fall under exact inferencing: enumeration (already covered in prior classes: expand the full joint, multiply, sum, normalize) and variable elimination (the topic of section 13.3, which avoids redundant work by joining tables and dropping variables one at a time). The professor emphasizes that exactness has nothing to do with whether probabilities are involved: "Just because probabilities are involved, it doesn't mean it is approximate. We were exactly knowing the Bayesian network, and from there we applied the formulas, we got the answers."
Approximate inferencing trades precision for computational efficiency. When a Bayesian network has many nodes, exact computation can become intractable — the joint distribution is exponential in the number of variables. Approximate techniques generate random samples and estimate probabilities from those samples; the answer is close but not exact, and more samples mean closer. This lecture covers three approximate techniques: prior sampling, rejection sampling, and likelihood weighting.
Q: "Why do we multiply or sum for a joint query but normalize for a conditional?" A: For a joint query we only multiply — when we apply the chain rule to the linearized joint, every step is a product of CPT values, and we never sum and never normalize. For a conditional query we convert to joint form with a probability identity, and only then do we sum over the hidden variables (marginalization) and divide by the evidence probability to normalize. Those two extra operations — summing hidden variables and dividing — are exactly the difference between the two query types. The professor's guidance was to re-watch linearization and marginalization: "We did two concepts. One is called linearization and the other is called marginalization. We never did any normalization."
Recap + bridge. A joint query is answered by linearizing, applying the chain rule, and multiplying CPT values; a conditional query adds conversion to joint form, marginalization over hidden variables, and normalization. Both are exact, and both are what enumeration does. Two problems remain unsolved, and they are the agenda for this lecture: first, proving — rather than eyeballing — that a variable can be dropped from a query because it is conditionally independent (d-separation, section 13.2); second, answering queries that land directly on a dependent variable, where no CPT row gives the answer (variable elimination, section 13.3). After that, the lecture steps down from "exact always" to "approximate is good enough" with three sampling techniques (sections 13.4–13.6).
13.2 D-Separation and D-Connectedness
13.2.1 The Concept
Hook — can you prove a variable is irrelevant, or are you just guessing? Until now, when a chain-rule expansion contained a variable that seemed unrelated to the query, we "just cancelled" it by looking at the network. This section replaces that eyeballing with a graph algorithm that decides, once and for all, whether two nodes are conditionally independent given a set of evidence nodes.
In previous classes, we sometimes eliminated certain evidence variables from a chain rule expression because they were "not relevant" to the query. D-separation provides a rigorous graph-theoretic method to prove whether two nodes are conditionally independent given a set of evidence nodes. The professor frames it as moving from intuition to proof: "All these while we have been just going by our chart, we looked at the Bayesian network, we just immediately cancelled that this is not really useful. But now we are going to actually draw some diagrams and we are going to tell that this is not dependent, and this is dependent, and why something is not dependent."
D-separation (directional separation) answers the question: given a Bayesian network and a set of observed evidence variables, are two specific nodes conditionally independent? If they are d-separated — the graph becomes disconnected after the evidence is removed — they are conditionally independent. If they are d-connected — the graph remains connected — they are conditionally dependent.
Formalize. Conditional independence is written with the perpendicular symbol:
\[ X \perp Y \mid Z \]
meaning "X is conditionally independent of Y given Z." In words: once you know the value of \(Z\), knowing \(Y\) tells you nothing further about \(X\). If d-separation answers "yes," the pair is conditionally independent and we write \(X \perp Y \mid Z\); if it answers "no," the pair is conditionally dependent and the symbol is negated, \(X \not\perp Y \mid Z\). The professor introduces the symbol with exactly this rule: "This denotes conditional independence or not. If you put this symbol, it means they are conditionally independent. If you put this, it is not conditionally independent."
Scope — independence is always with respect to the evidence. D-separation never talks about unconditional dependence of the whole tree; it always conditions on the evidence in the query. The professor stresses: "D-separated is always with respect to the evidence... not for the whole tree." The same pair of nodes can be d-connected under one evidence set and d-separated under another — the evidence set is part of the question, not an afterthought.
13.2.2 The D-Separation Algorithm
The algorithm has five steps. The professor states: "I'll tell you the formula again. There are five steps."
The five-step procedure. Given a query — a pair of variables to test, plus the evidence set:
- Draw the nodes involved in the query. Take all variables mentioned in the probability query (both the query variable and the evidence variables) and represent them as nodes in a new graph.
- Add all parents and ancestors of those nodes. For each variable already in the graph, add its parents, then their parents, and so on, recursively, copying the corresponding edges from the original Bayesian network.
- Perform the "marry" operation. Look for any node in the graph that has two parents. If those two parents are not already connected by an edge, draw an edge between them. This edge is temporary — we are not modifying the original Bayesian network. The professor explains: "Those two nodes have an influence on one child. That is why we are connecting those two. Meaning we are not changing the original Bayesian network. Just for answering this d-separated or not, we are trying to add that temporarily."
- Remove the evidence nodes (NOT the query node). Delete the evidence variable(s) along with all edges connected to them. The professor is emphatic: "We don't remove the query. We always remove the evidence only."
- Check if the remaining graph is disconnected (disjoint). If the graph splits into separate disconnected components, d-separation is yes — the pair is conditionally independent. If the graph remains connected, d-separation is no — the pair is conditionally dependent.
Q: "In last example, we remove query?" A: "No, no, we don't remove query. We remove always the evidence only." The query node stays in the graph; only the evidence nodes are deleted in step 4. Forgetting this is the single most common mistake in the d-separation algorithm — check the question's evidence column before deleting anything.
Why the marry step exists. Two parents of one child are dependent on each other given the child — that is the classic explaining-away pattern (intercausal reasoning). If we did not connect them, the graph would show a path "stopping" at the child, and connectivity checks would wrongly report independence. Marrying the parents converts that hidden dependence into an explicit edge so the connectivity test can see it.
How this matches the standard textbook procedure. The five steps above are the professor's order of the standard procedure: build the ancestral subgraph of the query and evidence nodes (steps 1–2), moralize it by linking unlinked parents of a common child (step 3), replace directed links by undirected links, and check whether the evidence blocks every path between the two test nodes (steps 4–5). The textbook version replaces directed links with undirected ones before the connectivity check; the professor's version removes the evidence nodes outright — deleting a node is exactly what "blocking" does to every path that passes through it. The two formulations agree in every case.
13.2.3 Worked Example: Car, Weekend, Bars, Road, Festival
Setup. Consider a subset of a Bayesian network with the following variables and structure:
- \(W\) (Weekend) — root node, no parents
- \(B\) (Bars Full) — parent: \(W\)
- \(R\) (Road) — parent: \(W\), and also parent: \(F\)
- \(F\) (Festival) — root node, no parents
- \(C\) (Car getting routed) — parents: \(R\) and \(W\)
So the edges are \(W \to B\), \(W \to C\), \(R \to C\), \(W \to R\), \(F \to R\). The query: "What is the probability of car getting routed given that it is a weekend and bars are full?" — in probability notation, \(P(C \mid W, B)\).
We already know intuitively that \(C\) depends on \(W\) (its parent) but not on \(B\) (\(B\) is a sibling — neither an ancestor nor a descendant of \(C\)). Now we prove this rigorously with the five steps.
Step 1: The variables in the query are \(C\), \(W\), and \(B\). Draw these three nodes.
Step 2: Add parents and ancestors. For \(B\), the parent is \(W\) (already drawn). For \(C\), the parents are \(R\) and \(W\) — so add \(R\). For \(R\), the parent is \(F\) — so add \(F\). The graph now has nodes \(F, R, C, W, B\) with edges \(F \to R\), \(R \to C\), \(W \to C\), \(W \to B\) — and the original edge \(W \to R\) is already in the graph.
Step 3: Look for children with two parents. \(C\) has two parents: \(R\) and \(W\). They are not connected by an edge, so we draw the temporary marry edge \(R\)–\(W\). The graph now has one more edge between \(R\) and \(W\).
Step 4: We want to check whether \(C\) and \(B\) are conditionally independent given \(W\). The evidence is \(W\) (and \(B\), the other test node, stays). Remove \(W\): the edges \(W \to C\), \(W \to B\), \(W \to R\), and the married edge \(R\)–\(W\) all disappear. What remains: \(F\) connected to \(R\), \(R\) connected to \(C\) (via \(R \to C\)), and \(B\) isolated.
Step 5: The graph disconnects into two separate components — \(\{F, R, C\}\) form one component and \(\{B\}\) is alone. D-separation is yes, so \(C \perp B \mid W\): C and B are conditionally independent given W.
Sense-check. This matches intuition: once we know whether it is a weekend, whether the bars are full tells us nothing extra about whether the car gets routed — bars and routing are connected only through the weekend.
The alternative removal. Remove \(B\) instead of \(W\): only node \(B\) and edge \(W \to B\) disappear. The remaining graph still has \(F \to R\), \(R \to C\), \(W \to C\), \(W \to R\), and the married edge \(R\)–\(W\) — everything remains connected. D-separation is no, meaning \(C\) and \(W\) are conditionally dependent — which makes sense, because \(W\) is a direct parent of \(C\). The same graph, different evidence choice, different verdict: independence is always relative to the evidence.
Q: "R and W connected because of a common child C?" A: "That's correct. Why are we connecting R and W? That is the whole formula... those two nodes have an influence on one child. That is why we are connecting those two." The marry edge is temporary — it exists only for the d-separation check, and the original network is never modified.
13.2.4 Second Worked Example: R, L, C
Setup. The professor's second example reads off a slide table of the form "X, Y, evidence Z → d-separated yes/no" — the first entry is the query variable, the next two are the pair to test, and the evidence is given. The row worked in class is the query \(P(R \mid L, C)\). Reading the variables from the network used in the lecture:
- \(L\) — parent: \(C\)
- \(C\) — parents: \(R\) and \(W\) (Weekend)
- \(R\) — parent: \(F\) (Festival)
So the edges are \(F \to R\), \(R \to C\), \(W \to C\), \(C \to L\). The professor confirms the parent structure explicitly: "For L, there is a parent who is weekend" is corrected to "L has a parent, which is C"; "C has a parent which is weekend" and "R also has a parent which is festival"; and the marry step applies because "C has two parents, R and W, so I can connect them."
Step 1: Draw the query-and-pair nodes \(R\), \(L\), \(C\).
Step 2: Add parents and ancestors: \(R\)'s parent \(F\), \(C\)'s parents \(R\) and \(W\), \(L\)'s parent \(C\) (already drawn). The graph now has nodes \(F, R, C, W, L\) with edges \(F \to R\), \(R \to C\), \(W \to C\), \(C \to L\).
Step 3: Marry. \(C\) has two parents, \(R\) and \(W\), not yet connected — draw the temporary edge \(R\)–\(W\).
Case 1 — remove \(L\) (checking \(R\) vs \(C\) given \(L\)): Only the edge \(C \to L\) disappears. The rest — \(F \to R\), \(R \to C\), \(W \to C\), and the married edge \(R\)–\(W\) — remains fully connected: "I can go from F to R, from R to W, to C; I can go from anywhere to anywhere." D-separation is no, so \(R\) and \(C\) are conditionally dependent given \(L\).
Case 2 — remove \(C\) (checking \(R\) vs \(L\) given \(C\)): All three edges touching \(C\) disappear — \(R \to C\), \(W \to C\), and \(C \to L\). Now \(L\) has no remaining connections and sits alone, while \(\{F, R, W\}\) stay connected among themselves (via \(F \to R\) and the married edge \(R\)–\(W\)). The graph is disjoint, so d-separation is yes. The professor states the verdict precisely: "This R and L are D separated. That is, they are conditionally independent given C."
Sense-check. Once you know \(C\), the value of \(L\) (a child of \(C\)) carries no information about \(R\) — the only path between them ran through \(C\), and removing \(C\) severed it. In the other direction, without removing \(C\), \(R\) and \(C\) are directly linked by an edge, so of course they are dependent.
13.2.5 Third Example: Viral, Fever, Flu, Food Poisoning
Setup. In the medical Bayesian network — \(V\) (Viral) with \(V \to L\), \(L\) (Flu), \(D\) (Food Poisoning) with \(D \to F\), \(F\) (Fever) with parents \(L\) and \(D\) — consider the query \(P(V \mid F, L)\): query \(V\), evidence \(F\) and \(L\).
The professor asks: "Is V dependent on L and F or not? They are dependent, of course." Running the five steps confirms it: drawing \(V, F, L\) and their ancestors (the whole medical network), marrying \(L\) and \(D\) (the two parents of \(F\)), and removing the evidence nodes leaves the graph connected, so d-separation is no — \(V\) is dependent on \(F\) and \(L\).
But the interesting row is the conditional-independence claim hidden inside the network: "V is conditionally independent of L, if F is already known to you." In symbols, \(V \perp L \mid F\). Once you know the fever status, the flu status adds no information about viral infection beyond what the fever already tells you — the influence of \(V\) on \(L\) and of \(L\) on \(F\) is fully absorbed by observing \(F\). This is the Markov blanket property in action: \(F\) is a child of \(L\), and observing it screens off \(V\).
Similarly, for the last line of the table: if \(V\), \(D\), and \(L\) are all given, what is \(F\) dependent on? \(F\) depends on \(L\) (its parent) — the professor confirms, "It is dependent on L, that is correct" — because \(D\) is already known, and \(V\) affects \(F\) only through \(L\). Given \(L\), the viral status carries nothing extra about the fever.
13.2.6 Conditional Independence Notation
The professor introduces the notation symbol used throughout: "We also have this symbol. This denotes conditional independence or not. If you put this symbol, it means they are conditionally independent. If you put this, it is not conditionally independent."
The standard notation is:
\[ X \perp Y \mid Z \]
meaning "X is conditionally independent of Y given Z." The rule to apply it:
- If d-separation answers yes (graph disjoint after removing evidence), write \(X \perp Y \mid Z\).
- If d-separation answers no (graph still connected), write \(X \not\perp Y \mid Z\) — or simply state they are conditionally dependent.
Reading the symbol. \(X\) and \(Y\) are the two test variables; \(Z\) is the evidence set — the variables whose values we already know. Everything to the right of the \(\mid\) is the conditioning context; everything to the left is the pair being tested for independence.
Q: "What is the difference between disjoint and connected?" A: "That is a tree. After you remove, if those become two parts, different parts, that is disjoint. And connected means you can still traverse the tree. You can touch all the nodes." In short: disjoint = the remaining graph splits into separate components (d-separated, independent); connected = there is still a walk touching all remaining nodes (d-connected, dependent).
13.2.7 Connection to the Markov Blanket
The d-separation concept is fundamentally the same as the Markov blanket property discussed in previous classes. A node's Markov blanket consists of its parents, its children, and its children's other parents (its co-parents). Given its Markov blanket, a node is conditionally independent of every other node in the network — nothing outside the blanket matters once the blanket is known. The professor confirms the link: "In other words, this is the same thing as that Markov's tree. We have been talking about it in all the while in the previous classes also."
The two ideas are two views of one fact:
- The Markov blanket states the independence: which set of nodes screens a node off from everything else.
- D-separation provides the proof: how to verify any conditional independence claim on the graph, including claims far beyond a single node's blanket, using the five-step algorithm.
The algorithm's marry step is exactly the blanket's "children's other parents" clause: co-parents of a child become linked (temporarily) so their dependence is visible to the connectivity test. Nodes with more than one parent are so especially important in d-separation — they are the only nodes that trigger the marry operation.
13.2.8 Exam Notes on D-Separation
Exam note: D-separation is primarily a quiz-level concept — expect questions that hand you a small network and ask whether two nodes are conditionally independent given some evidence. The checklist for the exam:
- D-separation is always checked with respect to the evidence, not the whole tree.
- Always remove the evidence nodes, never the query node.
- If the graph becomes disjoint after removal, d-separation is yes (conditionally independent) → \(X \perp Y \mid Z\).
- If the graph remains connected, d-separation is no (conditionally dependent) → \(X \not\perp Y \mid Z\).
- The marry step is the only place students forget: whenever a node has two parents that are not already connected, connect them before removing evidence.
- Read the verdict pair correctly: the evidence column of the table tells you what to remove; the other two columns are the pair you are testing.
13.3 Variable Elimination
13.3.1 Motivation: Why Enumeration Is Not Enough
Enumeration works perfectly for joint and conditional probability queries where we can apply the chain rule, marginalization, and read directly from CPTs. But consider a different kind of query: "What is the probability of me having fever?" — \(P(\text{Fever})\).
The professor poses the challenge: "What is the probability of me having a fever? Is this answer there or not in my slide? Think carefully." The answer is no — the CPT for fever does not directly give \(P(\text{Fever})\). The CPT gives \(P(\text{Fever} \mid \text{Flu}, \text{Food Poisoning})\), a conditional probability given its parents. Fever is a dependent variable — its probability depends on its parents' values, so no single row of its CPT is a marginal.
The distinction is sharp:
- For independent variables (no parents), the CPT row is the answer: \(P(\text{Viral} = \text{true}) = 0.6\), \(P(\text{Food Poisoning} = \text{false}) = 0.9\) — read directly, because nothing conditions them.
- For dependent variables, the CPT does not contain the marginal probability. "When you have different dependent variables, their tables will not directly give you the answers. For a bigger query, like give me the probability of fever, you don't have the answer in the table."
The solution: variable elimination — systematically eliminate parent nodes by accounting for their information, converting a dependent variable into an independent one with a standalone table.
13.3.2 The Core Idea
Purpose. Variable elimination answers queries that land directly on a dependent variable — queries no CPT row can answer and that enumeration cannot reach without expanding a full joint. The professor articulates the goal: "If I make that node itself as independent, then can I answer that query? ... If I remove that parent, if I eliminate that parent itself, if I go ahead and remove this full viral — if I get the answer or a table for flu, then I will be able to answer if someone has flu or not."
Inputs & outputs. Input: a Bayesian network with CPTs (tables), and a query on a dependent variable. Output: a new standalone table for the queried variable (e.g., a table for Flu alone, then for Fever alone), from which the marginal probability can be read directly.
The non-negotiable rule — eliminate means account, not delete. Variable elimination does not simply remove a node and its table. It accounts for the parent's influence by merging tables. The professor is emphatic: "We are not just going to remove this table and tell that now flu is independent. No. We are going to account for that information." Dropping the table outright would throw away the probability mass the parent contributes; merging tables first preserves it.
Steps of the technique:
- Join the tables. Take the dependent variable's CPT and the table of the parent to be eliminated. Create a merged table containing every combination of the two variables' values. For each row, write the pair in linearized form (child before parent) and apply the chain rule: the joint equals the child-given-parent factor times the parent's own factor.
- Eliminate by marginalization. Sum (add) the rows of the merged table that share the same value of the surviving variable. This removes the eliminated variable while preserving its total influence.
- Repeat until the queried variable stands alone with its own table.
Why this is more than total probability. A student asks: "Is it like total probability?" The professor: "That is where we are heading." Variable elimination is related to total probability but uses the Bayesian network's structure to be far more efficient. If we used total probability directly (without the Bayesian network), we would have to account for all hidden variables — "a lot more math." With variable elimination, "you are not worried about those other hidden variables or other variables which are not in this blanket." Only variables connected to the query in the network's local neighborhood (its Markov blanket and their ancestors) ever enter the calculation.
13.3.3 Worked Example 1: Eliminating Viral to Get a Table for Flu
Setup. The medical Bayesian network:
- \(V\) (Viral) — \(P(V) = 0.6\), \(P(\neg V) = 0.4\)
- \(L\) (Flu) — \(P(L \mid V) = 0.8\), \(P(\neg L \mid V) = 0.2\); \(P(L \mid \neg V) = 0.01\), \(P(\neg L \mid \neg V) = 0.99\)
- \(D\) (Food Poisoning) — \(P(D) = 0.1\), \(P(\neg D) = 0.9\)
- \(F\) (Fever) — CPT depends on \(L\) and \(D\)
Label the tables: \(T_1\) = Viral table, \(T_2\) = Flu table, \(T_3\) = Food Poisoning table, \(T_4\) = Fever table.
Goal: Eliminate Viral (\(V\)) so that Flu (\(L\)) becomes an independent variable with its own standalone table.
Step 1: Join \(T_1\) and \(T_2\). We create a merged table with all combinations of \(L\) and \(V\). Since there are two binary variables, we get \(2^2 = 4\) rows. The order follows linearization: \(L\) (child) comes first, then \(V\) (parent). The four rows are \((L{=}T, V{=}T)\), \((L{=}T, V{=}F)\), \((L{=}F, V{=}T)\), \((L{=}F, V{=}F)\).
To compute each cell's probability, write the linearized form and apply the chain rule:
Row 1: \((L{=}T, V{=}T)\) — linearized form \(P(L, V)\), both true. Chain rule: \(P(L \mid V) \times P(V)\).
The professor's verbal description: "What is the probability of L given V? From this table you will get that answer. What is the probability of L given V is true? That is 0.8. And probability of V itself from this table, that is 0.6."
\[ P(L, V) = P(L \mid V) \times P(V) = 0.8 \times 0.6 = 0.48 \]
Row 2: \((L{=}T, V{=}F)\) — linearized form \(P(L, \neg V)\). Chain rule: \(P(L \mid \neg V) \times P(\neg V)\).
The professor explains the notation discipline: "What should I write inside the bracket? First, I should write it in linearized form, which means my L should come before my V, and then I look at that true and false value. Here, L is true, so I'll give L itself, and my V variable is F here, so it should be negation V."
\[ P(L, \neg V) = P(L \mid \neg V) \times P(\neg V) = 0.01 \times 0.4 = 0.004 \]
Row 3: \((L{=}F, V{=}T)\) — linearized form \(P(\neg L, V)\). Chain rule: \(P(\neg L \mid V) \times P(V)\).
\[ P(\neg L, V) = P(\neg L \mid V) \times P(V) = 0.2 \times 0.6 = 0.12 \]
Row 4: \((L{=}F, V{=}F)\) — linearized form \(P(\neg L, \neg V)\). Chain rule: \(P(\neg L \mid \neg V) \times P(\neg V)\).
\[ P(\neg L, \neg V) = P(\neg L \mid \neg V) \times P(\neg V) = 0.99 \times 0.4 = 0.396 \]
The merged table:
| \(L\) | \(V\) | \(P(L, V)\) |
|---|---|---|
| T | T | 0.48 |
| T | F | 0.004 |
| F | T | 0.12 |
| F | F | 0.396 |
Sense-check: the four probabilities sum to \(0.48 + 0.004 + 0.12 + 0.396 = 1.0\), as a full joint over two binary variables must.
Step 2: Eliminate \(V\) by marginalization. To get a standalone table for \(L\), sum over \(V\):
\[ P(L = T) = P(L, V) + P(L, \neg V) = 0.48 + 0.004 = 0.484 \]
\[ P(L = F) = P(\neg L, V) + P(\neg L, \neg V) = 0.12 + 0.396 = 0.516 \]
Now Flu has its own table:
| \(L\) | \(P(L)\) |
|---|---|
| T | 0.484 |
| F | 0.516 |
The professor's verbal description of the summing step: "Look at those rows. Which has flu alone as true? Where is it? It is this true and this row. Add those two probabilities: 0.48 and this one, and that will give you the answer for this."
Now if someone asks "What is the probability of having flu?" — \(P(\text{Flu}) = 0.484\). This value was not available in the original Bayesian network. By eliminating Viral and accounting for its influence through the chain rule and table merging, Flu became an independent variable with a direct answer. The professor emphasizes: "That 0.484 was not available in my Bayesian network. In my network that was not there, you could have not answered this. Because of variable elimination, since I removed this viral, I accounted for it. For flu itself, I have my single table. Now I can answer this query."
Q: "How does the last table — the standalone Flu table — come from the merged table?" A: Look at where Flu is true in the merged table — the rows where \(L = T\). Add those two probabilities (\(0.48 + 0.004 = 0.484\)) for the true value. Add both false values (\(0.12 + 0.396 = 0.516\)) for the false value. Now you have a single table that directly answers \(P(\text{Flu})\). The merging step is what "accounting for" the parent means: the Viral influence is folded into the sums before the Viral column disappears.
13.3.4 Worked Example 2: Eliminating Multiple Parents to Get a Table for Fever
Setup. The harder case. The query: "What is the probability of fever?" — \(P(\text{Fever})\).
Fever depends on two parents: Flu (\(L\)) and Food Poisoning (\(D\)). We must eliminate both parents to get a standalone table for Fever. After eliminating Viral (previous section), Flu has its own table (\(P(L) = 0.484\), \(P(\neg L) = 0.516\)). Food Poisoning still has its original table (\(P(D) = 0.1\), \(P(\neg D) = 0.9\)). Fever has its original CPT with rows \(P(F \mid L, D) = 0.9\), \(P(F \mid L, \neg D) = 0.8\), \(P(F \mid \neg L, D) = 0.7\), \(P(F \mid \neg L, \neg D) = 0.1\).
Step 1: Create the full merged table. Three variables (\(L\), \(D\), \(F\)), each binary, gives \(2^3 = 8\) rows. Write all combinations. The linearization order: "F should come first, because in linearization, the child should come first, so it should be fever, and then it can be L or D or D or L — it doesn't matter."
For each row, write in linearized form (child first) and apply the chain rule. The chain rule here is \(P(F, L, D) = P(F \mid L, D) \times P(L \mid D) \times P(D)\), but since \(L\) and \(D\) are independent (no path between them in the network), \(P(L \mid D) = P(L)\) — the professor confirms: "L and D — are they dependent or independent? They are independent, so you don't need to account for the D. You'll only take probability of L."
Row 1: \((F{=}T, L{=}T, D{=}T)\) — \(P(F, L, D) = P(F \mid L, D) \times P(L) \times P(D)\).
The professor: "What is the probability of F given LD? From which table will you get that? You'll get it from the 4th table. If L and D both are given, it means true and true... What is the value of F then? 0.9."
\[ P(F, L, D) = P(F \mid L, D) \times P(L) \times P(D) = 0.9 \times 0.484 \times 0.1 = 0.04356 \]
Row 2: \((F{=}T, L{=}T, D{=}F)\) — \(P(F, L, \neg D) = P(F \mid L, \neg D) \times P(L) \times P(\neg D)\)
\[ = 0.8 \times 0.484 \times 0.9 = 0.34848 \]
Row 3: \((F{=}T, L{=}F, D{=}T)\) — \(P(F, \neg L, D) = P(F \mid \neg L, D) \times P(\neg L) \times P(D)\)
\[ = 0.7 \times 0.516 \times 0.1 = 0.03612 \]
Row 4: \((F{=}T, L{=}F, D{=}F)\) — \(P(F, \neg L, \neg D) = P(F \mid \neg L, \neg D) \times P(\neg L) \times P(\neg D)\)
\[ = 0.1 \times 0.516 \times 0.9 = 0.04644 \]
Row 5: \((F{=}F, L{=}T, D{=}T)\) — \(P(\neg F, L, D) = P(\neg F \mid L, D) \times P(L) \times P(D)\)
\[ = 0.1 \times 0.484 \times 0.1 = 0.00484 \]
Row 6: \((F{=}F, L{=}T, D{=}F)\) — \(P(\neg F, L, \neg D) = P(\neg F \mid L, \neg D) \times P(L) \times P(\neg D)\)
\[ = 0.2 \times 0.484 \times 0.9 = 0.08712 \]
Row 7: \((F{=}F, L{=}F, D{=}T)\) — \(P(\neg F, \neg L, D) = P(\neg F \mid \neg L, D) \times P(\neg L) \times P(D)\)
\[ = 0.3 \times 0.516 \times 0.1 = 0.01548 \]
Row 8: \((F{=}F, L{=}F, D{=}F)\) — \(P(\neg F, \neg L, \neg D) = P(\neg F \mid \neg L, \neg D) \times P(\neg L) \times P(\neg D)\)
\[ = 0.9 \times 0.516 \times 0.9 = 0.41796 \]
Sense-check: the eight rows sum to \(1.0\) — the full joint over the three variables — which is a quick way to catch a wrong factor before eliminating anything.
Step 2: Eliminate Food Poisoning (\(D\)) by summing over it. Group rows by the surviving pair \((F, L)\) and add the two rows that differ only in \(D\):
- \(P(F{=}T, L{=}T) = 0.04356 + 0.34848 = 0.39204\)
- \(P(F{=}T, L{=}F) = 0.03612 + 0.04644 = 0.08256\)
- \(P(F{=}F, L{=}T) = 0.00484 + 0.08712 = 0.09196\)
- \(P(F{=}F, L{=}F) = 0.01548 + 0.41796 = 0.43344\)
The professor's verbal description of this step: "When you want to delete the full D column, consider where all you have TT for LNF. So you have those red color rows. Here you have TT, here you have TT. Add those values that will give you this row. Wherever you have FT, that is the blue color ones, FT and FT, add those two answers, you will get the 2nd row."
Reduced table (\(D\) eliminated):
| \(F\) | \(L\) | \(P(F, L)\) |
|---|---|---|
| T | T | 0.39204 |
| T | F | 0.08256 |
| F | T | 0.09196 |
| F | F | 0.43344 |
Step 3: Eliminate Flu (\(L\)) by summing over it. Group rows by \(F\) and add the two rows that differ only in \(L\):
- \(P(F{=}T) = 0.39204 + 0.08256 = 0.4746\)
- \(P(F{=}F) = 0.09196 + 0.43344 = 0.5254\)
The professor's verbal description: "If I want to get the answer for only fever from this table, I'll just add those two rows which have fever as true. These red, red, I'll get this answer. False, false, I'll add, I'll get this answer."
Standalone table for Fever:
| \(F\) | \(P(F)\) |
|---|---|
| T | 0.4746 |
| F | 0.5254 |
Answer: \(P(\text{Fever}) \approx 0.4746\) — the professor's slide reads 0.46, the difference being rounding in the slide's CPT values; with the tables stated above the computed value is 0.4746. Either way, the point stands: "Now I have a standalone table for fever. If someone asks me what is the probability of fever, I can tell 0.46."
13.3.5 Key Points on Variable Elimination
Q: "Can we solve this problem with joint probability formula without elimination?" A: "If you actually go and do joint probability formulas, you are actually doing something called total probability. Then what is the use of even having a Bayesian network? Since you have the Bayesian network, you can just eliminate and solve them quickly by two or three operations." The answer stays correct either way, but total probability forces you to account for every hidden variable; variable elimination only touches variables in the query's neighborhood — that is the whole point of having the network.
Scope — what total probability would cost. As the Q&A above says, doing the query by raw joint-probability expansion is correct but amounts to total probability: you would sum over every hidden variable in the network, even ones with no connection to the query. Variable elimination never does that — it only manipulates variables that are connected to the query through the graph ("you are not worried about those other hidden variables or other variables which are not in this blanket"), which is precisely the savings the Bayesian network buys.
Order of elimination does not matter. "Can I drop L first? Yeah, that also you can, but what is your goal at the end? You want to come to this situation." Eliminate \(L\) first and you get a table over \((D, F)\); then eliminate \(D\) and you reach \(F\) alone. Same destination, different intermediate table. The professor's slide sequence (eliminate \(D\), then \(L\)) is one valid order.
Column order does not matter. "Order of columns doesn't really matter, as long as you are mindful when you get the answer, you are applying your linearization." What matters is that each row's joint probability is written in linearized form (child before parent) before applying the chain rule — the physical left-to-right layout of the columns is arbitrary.
It is computationally efficient. "For your computer, is this lengthy or fast? It is just combining these values. It can do it in memory, drop a column. It's just basic ALU operations." Variable elimination is a form of dynamic programming: instead of re-expanding the whole joint for every query (as enumeration does), it builds intermediate merged tables once and reuses them, which is why it scales to networks where full enumeration is hopeless.
When to use variable elimination vs enumeration:
| Query type | Technique | Why |
|---|---|---|
| Joint, e.g. \(P(B, J, M)\) | Enumeration | Linearize, chain rule, read CPTs, multiply |
| Conditional, e.g. \(P(B \mid J, M)\) | Enumeration | Convert to joint via identity, marginalize hidden variables, normalize |
| Directly on a dependent variable, e.g. \(P(\text{Fever})\) | Variable elimination | No CPT row holds the marginal; eliminate parents by joining tables and summing out |
Q: "Why do we create 8 rows and how do we determine column order?" A: Eight rows because \(2^3\) — three binary variables means \(2^3 = 8\) combinations. Column order does not matter, as long as when you fill each row you apply the chain rule to the linearized form (child first). The row count rule generalizes: \(k\) binary variables in the joined tables give \(2^k\) rows.
13.3.6 Summary of Exact Inferencing
Recap. The professor provides the consolidated summary of exact inferencing:
- Joint probability query: Linearize, apply chain rule, simplify, read from CPTs.
- Conditional probability query: Convert to joint form using probability identities (the alpha/normalization approach), apply marginalization, multiply, get the answer.
- Query on a dependent variable: Apply variable elimination — systematically eliminate parent nodes by joining tables (using the chain rule) and summing out variables until the target variable is independent, then read its marginal from the final standalone table.
Bridge. Variable elimination turned the medical network into a set of standalone tables — in the limit, "if you remove all of these nodes and if you have only one account doing all of that information," the queried variable stands alone. That is the exact toolkit. But the professor flags the cost honestly: exact inference on large, dense networks can be heavy, and "in a lot of times, I don't want to completely do the math... I want to have less computation, and I want to have a quick answer." That trade-off is the doorway to the next three sections: approximate inferencing by sampling.
13.4 Approximate Inferencing: Prior Sampling
13.4.1 Motivation and Concept
Hook — what if a good-enough answer in one second beats a perfect answer in one hour? All the exact techniques so far demand real computation. Approximate inferencing says: don't do the full math; build a big random sample once, store it, and answer any query by simple counting. The answer is slightly off — but in most domains, slightly off is fine.
Exact inferencing computes precise answers but can be computationally expensive for big networks — the joint distribution grows exponentially with the number of nodes. In lots of domains, an approximate answer is good enough. The professor frames this as a software engineering trade-off: "In a lot of times, I don't want to completely do the math. I want to get the answer, I want to have less computation, and I want to have a quick answer. That answer might not always be perfect. It might be an approximate answer, but in a lot of domains, that approximate answer is good enough." And the meta-principle: "Software engineering at the end is all a trade-off."
Prior sampling generates a random sample set before any query is posed. The sample set is a table where each row represents one possible state of all variables in the Bayesian network. Once created, this table is stored in memory. When queries arrive, we simply count rows to estimate probabilities — no formulas, no CPT lookups at query time.
The professor: "In prior sampling, what we are trying to do is we will generate a sample... you can have 16 rows, you can have 100 rows, that's up to you. But once you have this table, that is called as your sample set. And you have done this prior to answering any query."
Purpose. Prior sampling answers probability queries — joint, conditional, or on dependent variables — with an approximate answer and near-zero query-time computation.
Inputs & outputs. Input: the Bayesian network's CPTs plus a stream of random values between 0 and 1 (one per table cell). Output: a sample table with \(N\) rows, one row per simulated world state.
Steps of the technique:
- Decide the sample size \(N\) — 8, 16, 100 rows, whatever the computation budget allows.
- Fill the table in reverse linearized order — parents before children, so that every cell for a child is filled using parents whose values are already known for that row.
- For each cell, use the timeline method: draw the parent-dependent CPT row for that variable; split the interval \([0,1]\) at the positive probability; drop the random value on the timeline; assign true if it falls in the positive segment, false otherwise.
- Store the table in memory (built before any query arrives).
- Answer any incoming query by counting rows and dividing by the appropriate denominator.
13.4.2 The Timeline Method for Generating Samples
To fill each cell in the sample table, we use randomly generated values (between 0 and 1) and the Bayesian network's CPTs. The method works as follows. For each variable, draw a "timeline" from 0 to 1. Partition this timeline according to the CPT probabilities — always with the positive (true) segment first, from 0 up to the probability value, and the negative (false) segment from that value to 1. The partition depends on the parent values already determined for this row.
Filling the Viral (\(V\)) column. The CPT for Viral: \(P(V) = 0.6\), \(P(\neg V) = 0.4\). Draw a timeline from 0 to 1: the segment 0 to 0.6 represents \(V =\) true; 0.6 to 1 represents \(V =\) false. Generate a random value; suppose it is 0.3. Where does 0.3 fall? Between 0 and 0.6 — so \(V =\) true for this row. The professor: "Take this randomly generated value, 0.3, and look at it in this timeline where it is — from 0 to 0.6, is it there? Or from 0.6 to 1 is it there? Where is it there? 0.3 lies here. What does that denote? It means viral is positive."
Filling the Flu (\(L\)) column, given \(V =\) true. Since \(V\) is already true for this row, we use the Flu CPT row where \(V =\) true: \(P(L \mid V) = 0.8\), \(P(\neg L \mid V) = 0.2\). Timeline: 0 to 0.8 is \(L =\) true; 0.8 to 1 is \(L =\) false. Generate a random value; suppose it is 0.2. It falls between 0 and 0.8 — so \(L =\) true. The professor: "Since my V is already true, I am in this row... the next randomly generated value is 0.2. Where does it fall in that timestamp? 0.2 lies here, which means L also is true."
Filling the Food Poisoning (\(D\)) column. \(D\) is an independent variable: \(P(D) = 0.1\), \(P(\neg D) = 0.9\). Timeline: 0 to 0.1 is \(D =\) true; 0.1 to 1 is \(D =\) false. Random value: 0.6. It falls between 0.1 and 1 — so \(D =\) false. The professor: "Zero to 0.1 is positive — me having food poison. Not having food poison is from 0.1 to one, and here I have got 0.6 as my value. 0.6 lies in that negative part. That is not having food poison. So for food poison, I should put false."
Filling the Fever (\(F\)) column, given \(L =\) true, \(D =\) false. Use the Fever CPT row where \(L =\) true and \(D =\) false: \(P(F \mid L, \neg D) = 0.8\), \(P(\neg F \mid L, \neg D) = 0.2\). Timeline: 0 to 0.8 is \(F =\) true; 0.8 to 1 is \(F =\) false. Random value: 0.58. It falls between 0 and 0.8 — so \(F =\) true. The professor: "L should be true and D is false, so in this table I will consider only L and D... which row is that? Second row... Now the 4th one which got generated randomly was 0.58. So 0.58 is between 0 to 0.8 — it is in the positive timeline."
Consistency of the timeline is a rule, not a preference. Always write the positive segment first (0 to the probability) and the negative second (probability to 1), for every node. A student suggested flipping the order per node; the professor rejected it: "Always go with the same pattern. If you follow for one node, first part you are considering true, then false — for all the nodes, follow that same pattern and you will be able to fill that table with these random values." Mixing orders across nodes is the fastest way to misread a random value.
Borderline values. If a random value lands exactly on a threshold (e.g., exactly 0.6 when the positive segment ends at 0.6), either assignment is acceptable — "borderline you can take either true or false... define your own rule... it doesn't matter. It's all approximate only." Just be consistent across the whole table.
13.4.3 Sample Table Construction
One complete row requires one random value per variable. For four variables (\(V, L, D, F\)), four random values fill one row. To create a sample set of 8 rows, you need \(8 \times 4 = 32\) random values.
The professor: "You are using this first value to fill this cell, this value for this cell, this value for this cell, and this 4th value for last cell. So one row over. Then you take four more generated numbers, fill the 2nd row. Again four more, fill the 3rd row, and so on."
The order of columns matters. Variables must be filled in reverse linearized order — parents before children. The professor explains: "It is in reverse linearized order. The parent will first come, then its children will come, and finally the child will come. So that when I come to fill that child, already all my parents' answers are known." Clarification on terminology: "Linearized means child should come first. OK, this is reverse linearized order." The table's column order is \(V, L, D, F\) — \(V\) and \(D\) first (no parents), then \(L\) (parent \(V\)), then \(F\) (parents \(L, D\)) — exactly so that each cell is filled from an already-known parent configuration.
Following the professor's four random draws (0.3, 0.2, 0.6, 0.58), row 1 is \(V = T, L = T, D = F, F = T\). Continuing the process for the remaining rows gives a complete 8-row sample set such as:
| Row | \(V\) | \(L\) | \(D\) | \(F\) |
|---|---|---|---|---|
| 1 | T | T | F | T |
| 2 | F | F | F | T |
| 3 | F | F | F | T |
| 4 | T | T | F | T |
| 5 | T | T | F | T |
| 6 | T | F | F | F |
| 7 | F | F | F | F |
| 8 | T | F | F | F |
The specific values depend on the random draws; what matters is the mechanics — and that the table is built before any query arrives. Duplicates are perfectly fine: "since there is random, nothing to do with duplicate and so on, it can have duplicates, no problem."
13.4.4 Answering Queries from Prior Samples
Once the sample table is built, answering queries is simple counting.
Query 1: \(P(\text{Flu})\) — count the rows where \(L =\) true and divide by total rows. In the table above, \(L = T\) in rows 1, 4, 5: \(P(\text{Flu}) \approx 3/8\).
Query 2: \(P(\text{Fever AND Flu})\) — count rows where both \(F =\) true and \(L =\) true, divide by total: rows 1, 4, 5 → \(P(F, L) \approx 3/8\).
Query 3: \(P(\text{Flu} \mid \text{Fever})\) — the denominator changes: only count rows where \(F =\) true (the given condition). \(F = T\) in rows 1–5 (five rows); among those, \(L = T\) in three. So \(P(L \mid F) \approx 3/5\). The professor: "Given F means F is true. So F is true in how many rows? One, two, three, four, five. That becomes your denominator. In how many do I have L as true? One, two, three — so that is 3/5."
Query 4: \(P(\neg V \mid F)\) — probability of not having viral given fever. Denominator: the five rows with \(F = T\). Among those, \(V = F\) in rows 2 and 3: \(P(\neg V \mid F) \approx 2/5\).
Query 5: \(P(L \mid V, \neg F)\) — denominator: rows where \(V = T\) and \(F = F\) — rows 6 and 8. In neither of those two rows is \(L = T\). So \(P(L \mid V, \neg F) \approx 0/2 = 0\). This is a valid answer: given a viral infection and no fever, the sampled worlds never showed flu.
Query 6: \(P(F \mid D)\) — probability of fever given food poisoning. This is where prior sampling fails. No row in the sample has \(D =\) true, so the denominator is zero: \(P(F \mid D) \approx 0/0\) — undefined. The professor: "For D, do we have any row which has D as true? No, so denominator itself, if it's zero, then what can I do? I can't answer that query. That is a problem of prior sampling."
13.4.5 The Problem with Prior Sampling
Prior sampling has a critical limitation: if the query's evidence variables have no matching rows in the sample, the denominator becomes zero and the query cannot be answered. This is especially problematic for rare events — if \(P(D) = 0.1\), a small sample set may easily contain no row where \(D =\) true (with 8 rows, the chance is \(0.9^8 \approx 0.43\), nearly a coin flip).
The professor: "In prior sampling technique, there is this one problem that I may get queries for which I don't have any rows satisfying. So I might be in a fix. I don't know what to do there."
One tempting solution is to generate more samples — but prior sampling is meant to be done offline, before queries arrive. You cannot keep regenerating when a query comes in: "You had decided that I want 10 rows... you generated this table, you put that in main memory, you deployed it. Now queries are coming on your way. Now you can't tell that, you know, I don't have this value, so I'll again regenerate." The fix is not "more rows at query time"; it is a different technique — rejection sampling (section 13.5) — that generates rows conditioned on the query instead.
Q: "How do we handle \(P(F \mid D)\) when no row has \(D =\) true in prior sampling?" A: You cannot answer — the denominator is zero. This is the fundamental problem of prior sampling, and it motivates rejection sampling: instead of pre-building a generic table, generate samples that satisfy the query's evidence from the start.
13.4.6 Advantages of Prior Sampling
Despite its limitation, prior sampling has a significant advantage: sample generation is done offline (a priori), so you can afford to generate a very large sample set.
Recap + trade-off. The professor: "In prior sampling technique, am I generating samples in runtime or am I doing it prior and keeping it in memory? In prior sampling, I'm doing it offline. I can generate many samples, keep it in memory, and then when a query comes, I will use that to answer. So I can afford to generate a lot of samples." This is a classic space-for-time trade: computation invested once, up front, buys instant query responses afterward.
This mirrors real-world empirical research: "We want to know how many people drink coffee, how many people prefer tea. You as a researcher are going to take a sample set. Sample set is up to you. If you are capable, you will do it with 1,00,000 people. If you are more capable, you can do it with 1 crore people." And it is conceptually the same as generating synthetic data — the professor endorses the student's remark: "It's like generating synthetic data. That's exactly correct."
Bridge. The zero-denominator failure leaves a clear design question: can we generate samples conditioned on the evidence of the query so that every row is usable? That is exactly what rejection sampling does — and what we turn to next.
13.5 Approximate Inferencing: Rejection Sampling
13.5.1 Concept and Motivation
Hook — flip the order: don't build the table first and hope; get the query first and build only what answers it. Prior sampling failed on \(P(F \mid D)\) because no pre-built row had \(D =\) true. Rejection sampling says: once the query is known, generate rows that match its evidence — and simply refuse to keep anything else.
Rejection sampling addresses the zero-denominator problem of prior sampling. Instead of generating samples a priori, we first receive the query, then generate samples that satisfy the query's evidence.
The professor: "Now I am telling you, first give me the query. I will generate samples which satisfies the query. That is called rejection sampling."
The idea: when generating random samples, if a row does not match the evidence specified in the query, reject it entirely and generate a new one. Only keep rows where the evidence variables have the required values. Everything else — the timeline method, the reverse linearized fill order, the parent-conditioned CPT lookups — stays identical to prior sampling; the only change is the filter.
Purpose. Answer conditional queries with evidence that might be rare in the prior — specifically, the queries prior sampling cannot touch because no sample row matches the evidence.
Inputs & outputs. Input: the query (which fixes the evidence values), the CPTs, and random values. Output: a sample table in which every row matches the query's evidence; estimates are computed by counting rows within that filtered table.
Steps of the technique:
- Receive the query and read off which evidence values every row must satisfy.
- Generate a row exactly as in prior sampling (timeline method, reverse linearized order).
- Check the evidence. If the row's evidence columns match the query, keep it; otherwise reject the entire row and start a new one. The rejection can happen as soon as a violating evidence value is determined — there is no point filling the remaining cells of a doomed row.
- Stop when enough valid rows have been collected.
- Answer by counting among the kept rows, exactly as in prior sampling.
Scope — when the filter helps and when it hurts. Rejection sampling is the right tool when the evidence is a specific value the prior rarely produces (e.g., \(D =\) true with \(P(D) = 0.1\)). But the textbook analysis gives the cost: the fraction of generated rows that survive is exactly the prior probability of the evidence, \(P(e)\). For complex problems with many evidence variables, that fraction is tiny — in real insurance networks it is typically between one in a thousand and one in ten thousand — and the number of samples needed to get a decent estimate grows exponentially with the number of evidence variables. The professor's version of the same warning: rejection sampling is query-specific, so every new query throws away the old sample set and starts again.
13.5.2 Worked Example
Query: \(P(\text{Fever} \mid D)\) — probability of fever given food poisoning. Evidence: \(D =\) true.
We generate random samples as before, but with a filter: whenever we determine that \(D =\) false for a row, we reject that entire row and start over. We only accept rows where \(D =\) true.
The professor: "If I get a D value as false, I will reject that full row. Why? Because my query itself told that my D is true. It's not a biased process, because the query itself says that I'm giving you that there is food poison. Then why should I generate samples where food poisoning is not happening?"
In the worked example, the first three generated rows all had \(D =\) false and were rejected. Only rows where \(D =\) true were kept and completed (the remaining cells — \(V\), \(L\), and \(F\) — filled with the usual timeline method using the parent configurations of each row).
After collecting enough valid rows (say 8 rows, all with \(D = T\)), we count how many have Fever = true. In the professor's example, 5 of the 8 kept rows have \(F = T\), giving the estimate
\[ P(F \mid D) \approx \frac{5}{8} = 0.625 \]
Sense-check. This is a conditional probability: every kept row has \(D = T\), so the denominator is the number of kept rows, not the total number of generated rows. The rejected rows never enter any count — they were never samples at all.
Consistency guarantee. Why is this estimate valid rather than a distortion? Because each kept row is drawn from the prior distribution restricted to the evidence: the relative frequency of \(F = T\) among rows with \(D = T\) converges to \(P(F \mid D)\) as the number of kept rows grows. The professor's shortcut: "My calculation of these values, that is not random, right? Only the sample generation is random. Once I have these rows, then I will use my probability distribution table, and I will calculate all these values, and still that is correct."
13.5.3 Another Example
Query: \(P(\text{Fever} \mid \neg \text{Flu}, \neg \text{Food Poisoning})\) — probability of fever given no flu and no food poisoning.
For this query, we must ensure \(L =\) false and \(D =\) false in every generated row. Any row where either \(L\) or \(D\) is true gets rejected.
The professor: "You will make sure that my L is having false and D is also having false. Because my query itself has told me that given there is no flu, there is no food poison. So only such samples I will select."
Then, among the kept rows (all with \(L = F, D = F\)), count rows where \(F =\) true and divide by the total number of kept rows to estimate \(P(F \mid \neg L, \neg D)\). Note this query's filter makes the process more wasteful than the single-evidence case: both \(L\) and \(D\) must land on their specified values before a row survives, so the acceptance rate is \(P(\neg L, \neg D)\), not \(P(D)\).
13.5.4 Trade-offs of Rejection Sampling
Recap + trade-off. Where does rejection sampling stand between the two techniques around it?
| Feature | Prior sampling | Rejection sampling |
|---|---|---|
| When samples are generated | Offline, before any query | Online, after the query |
| Evidence handling | None (rows unfiltered) | Reject rows not matching evidence |
| Zero-denominator risk | Yes (query may have no matching rows) | No (every kept row matches) |
| Reusable across queries | Yes — one table serves many queries | No — every query needs a fresh table |
| Sample size | Can be very large (offline budget) | Limited (runtime budget) |
| Wasted computation | None | Yes — rejected rows (and their random values) are thrown away |
Advantage: no zero-denominator problem. Since we generate samples matching the evidence, we are guaranteed to have valid rows for any query.
Disadvantage 1 — query-specific. "This is very query specific. You are giving me a query, then I'm going and generating. It's not like a very generic and scalable way." Every different query requires generating a fresh set of samples; you cannot precompute and reuse samples across queries.
Disadvantage 2 — online budget. Rejection sampling runs at query time, so you cannot afford as many samples as prior sampling. The professor: "Rejection sampling is where I already got a query. I'm online. I'm actually getting a query. I have to solve it, so I'm generating samples and then using my Bayesian network to answer the values and so on. So then I can't generate a lot." Small sample counts mean rougher estimates (the estimation error scales like \(1/\sqrt{n}\) in the number of kept samples).
Q: "Is rejection sampling biased since we only keep matching samples?" A: No, it is not biased. The filtering happens in sample generation only; the probability computation is untouched. Every kept row is a legitimate draw from the prior restricted to the evidence, so counting among kept rows converges to the true conditional probability. The professor's framing: "It's not a biased ceremony... the query itself says that I'm giving you that there is food poison. Then why should I generate samples where food poisoning is not happening?" The related real-world parallel: to estimate the survival rate after a rare catastrophe, you count only the events where the catastrophe actually happened — you do not average in the uneventful days.
Bridge. Rejection sampling eliminates the zero denominator but wastes every rejected row — including the random values invested in it. The third technique, likelihood weighting, keeps the "condition on the evidence" idea but removes the waste: instead of rejecting, it hard-codes the evidence in every row and compensates with a weight.
13.6 Approximate Inferencing: Likelihood Weighting
13.6.1 Concept and Motivation
Hook — why generate rows you know you will throw away? Rejection sampling discarded entire rows (and their random values) whenever the evidence did not match. Likelihood weighting asks: if the evidence is given, why not just hard-code it into every row and spend the random values only on the variables that genuinely need sampling?
Likelihood weighting improves upon rejection sampling by eliminating wasted computation. In rejection sampling, we generate full rows and then discard those that do not match the evidence — this wastes the random values used for non-evidence variables in rejected rows.
The key insight: "My D is true is given to me as an evidence. Then, why don't you put D = true in all these rows? And use this random generation only for the other variables."
In likelihood weighting:
- Hard-code the evidence variables in all rows (no randomization for them).
- Generate random values only for non-evidence variables, using the timeline method as before.
- Assign weights to each row to compensate for the hard-coded evidence — because a row whose evidence was simply typed in was never actually drawn with that evidence's probability.
Purpose. Same goal as the other two sampling techniques — estimate a conditional probability — but with no rejected rows at all: every generated row is used, weighted by the probability the hard-coded evidence would have had.
Inputs & outputs. Input: the query (which fixes the evidence), the CPTs, and random values for the non-evidence variables only. Output: a sample table whose rows all match the evidence, each carrying a weight; the query probability is the ratio of weighted counts.
Steps of the technique:
- Read the evidence from the query. These columns are hard-coded in every row.
- Fill the non-evidence variables in reverse linearized order with the timeline method, using the parent configurations (evidence values included) of each row.
- Compute each row's weight. Every non-evidence variable contributes 1 (its value was earned by sampling). Every hard-coded evidence variable contributes its CPT probability for that row's parent configuration.
- Answer the query: numerator = sum of weights of rows where the query condition holds; denominator = sum of weights of all rows.
13.6.2 Worked Example 1
Query: \(P(\neg \text{Fever} \mid D, \neg V)\) — probability of not having fever given food poisoning and no viral infection.
Evidence: \(D =\) true, \(V =\) false. These are hard-coded in every row. Non-evidence variables: \(L\) (flu) and \(F\) (fever) — random values are generated only for these.
Step 1: Create the table skeleton. Choose the sample size (e.g., 7 rows). Fill \(D = T\) and \(V = F\) in every row.
Step 2: Fill non-evidence variables using random values. For the first row, we need to fill \(L\) and \(F\).
Filling \(L\): \(V\) is already false (hard-coded), so we use the Flu CPT row where \(V =\) false: \(P(L \mid \neg V) = 0.01\), \(P(\neg L \mid \neg V) = 0.99\). Timeline: 0 to 0.01 is \(L =\) true; 0.01 to 1 is \(L =\) false. Random value: 0.3. It falls between 0.01 and 1 — so \(L =\) false. The professor: "From 0 to 0.01, it is positive. And from there till one, it is negative. So when I see 0.3, where should it fall? Is it falling between 0 to 0.01 or between 0.01 and 1? It's falling here, which means negative. So I will put F here."
Filling \(F\): \(L\) is false (just determined) and \(D\) is true (hard-coded), so we use the Fever CPT row where \(L =\) false, \(D =\) true: \(P(F \mid \neg L, D) = 0.8\), \(P(\neg F \mid \neg L, D) = 0.2\). Timeline: 0 to 0.8 is \(F =\) true; 0.8 to 1 is \(F =\) false. Random value: 0.2. It falls between 0 and 0.8 — so \(F =\) true. The professor: "By this time, I know L is F and D is true. That is this row. L is false, D is true. So using that, I will see that my 0.2 is here, 0.2 is between 0 to 0.8, so that is true."
Repeat for all 7 rows using successive random values (two per row — only \(L\) and \(F\) consume random values).
13.6.3 Computing Weights
Each row gets a weight based on how its variables were determined:
\[ w = \prod_{\text{non-evidence } Z} 1 \times \prod_{\text{evidence } E} P(E \mid \text{Parents}(E)) \]
Every symbol is named: the product runs over all variables; non-evidence variables \(Z\) contribute a factor of 1 each (their values were determined by actual sampling — "the hard work"); evidence variables \(E\) contribute their CPT probability for the value that was hard-coded, conditioned on that row's parents. The name comes from the fact that probabilities of evidence are called likelihoods — the weight is the product of likelihoods of the observed evidence.
- Non-evidence variables (computed via random values and timeline): weight contribution = 1. The professor: "For L and F — did I do the hard work and get that answer? I actually did the random values, looked at the tables, and finally determined its value. I did the hard work already. So give the weight as one."
- Evidence variables (hard-coded): weight contribution = the probability from the CPT for that hard-coded value. The professor: "For the other V and D, I had just hard-coded it. I have not done any hard work. I just hard-coded those values. So you will go and look at the tables."
For \(V =\) false: \(P(\neg V) = 0.4\) (from the Viral CPT, \(V\) has no parents). For \(D =\) true: \(P(D) = 0.1\) (from the Food Poisoning CPT, \(D\) has no parents).
Weight for each row = product of all weight contributions:
\[ w = P(\neg V) \times 1 \times P(D) \times 1 = 0.4 \times 1 \times 0.1 \times 1 = 0.04 \]
Since \(V\) and \(D\) are hard-coded identically in every row, and \(L\) and \(F\) always get weight 1, every row has the same weight: 0.04. The professor: "Will it be the same in all the rows? Yes, because in all the rows I have put F here for V. So this V is going to correspond to 0.4. D is going to be true here, so that's going to be 0.1. And in all the rows, L and F are computed by me. So that's a weight of 1."
Important clarification — weights are NOT probabilities. They are scaling factors that correct for hard-coding. The professor: "This one is not a probability, that is just a weight. Finally, what you get here, the 0.099 is what is the probability."
13.6.4 Answering Queries with Likelihood Weighting
Query: \(P(\neg \text{Fever} \mid D, \neg V)\).
- Numerator: sum of weights of rows where Fever = false.
- Denominator: sum of weights of all rows.
In the 7-row table, only the last row has \(F =\) false (the professor: "Which row has fever as false? Only this last row"). Every row weighs 0.04, so:
\[ P(\neg F \mid D, \neg V) = \frac{0.04}{7 \times 0.04} = \frac{0.04}{0.28} = \frac{1}{7} \]
Query: \(P(\text{Fever} \mid D, \neg V)\). Same table, same weights — "we don't need to recalculate weights because calculation of weights is just once." Six of the seven rows have \(F =\) true:
\[ P(F \mid D, \neg V) = \frac{6 \times 0.04}{7 \times 0.04} = \frac{6}{7} \]
Note on cancellation. When all rows share one weight, the weight cancels out of the ratio — the answer reduces to plain row counting, like prior sampling. The professor flags this is not always the case: "It is not getting always cancelled out... here it was 6 by 7... but look at this example [below]... the answers are still different." When weights vary per row, they must be carried through.
13.6.5 Worked Example 2: Different Weights
Query: \(P(\text{Fever} \mid D, \neg L)\) — probability of fever given food poisoning and no flu.
Evidence: \(D =\) true, \(L =\) false. Hard-coded in every row. Non-evidence: \(V\) and \(F\). Random values are generated only for these.
Filling \(V\): \(V\) is independent, so \(P(V) = 0.6\), \(P(\neg V) = 0.4\); random values decide \(V\) per row.
Filling \(F\): depends on \(L\) (false, hard-coded) and \(D\) (true, hard-coded). Every row uses the Fever CPT row \(P(F \mid \neg L, D) = 0.8\), \(P(\neg F \mid \neg L, D) = 0.2\), so \(F\) is sampled from that timeline.
Computing weights. Non-evidence variables (\(V\) and \(F\)) contribute 1. Evidence variables: \(D =\) true contributes \(P(D) = 0.1\) in every row; \(L =\) false contributes \(P(\neg L \mid V)\) — and here is the critical subtlety: \(P(\neg L \mid V)\) depends on the value of \(V\) in that row, which was randomly determined. The weight for the \(L\) evidence changes across rows.
- Rows where \(V =\) false: the Flu CPT row is \(P(L \mid \neg V) = 0.01\), so \(P(\neg L \mid \neg V) = 0.99\). Evidence weight: \(0.99 \times 0.1 = 0.099\).
- The row where \(V =\) true: the Flu CPT row is \(P(L \mid V) = 0.8\), so \(P(\neg L \mid V) = 0.2\). Evidence weight: \(0.2 \times 0.1 = 0.02\).
The professor explains the mechanics: "In the last row, viral became true. When viral became true, suddenly that last row alone, you are now going to the 1st row of the Flu CPT. In the first row, you have to look at what is my L — L value is false, which means the negation value is 0.2." And for the other rows: "For these three rows, my viral was false. So always I was lying in my second row of the Flu CPT. Since I was in my second row, whenever I had L as false, I took my 0.9... But my viral variable decided — should I look at the second row or first row."
A 4-row table consistent with the professor's walkthrough (two rows with \(V = F, F = T\); one with \(V = F, F = F\); one with \(V = T, F = F\)):
| Row | \(V\) | \(L\) | \(D\) | \(F\) | weight |
|---|---|---|---|---|---|
| 1 | F | F | T | T | \(1 \times 1 \times 0.1 \times 0.99 = 0.099\) |
| 2 | F | F | T | T | \(1 \times 1 \times 0.1 \times 0.99 = 0.099\) |
| 3 | F | F | T | F | \(1 \times 1 \times 0.1 \times 0.99 = 0.099\) |
| 4 | T | F | T | F | \(1 \times 1 \times 0.1 \times 0.2 = 0.02\) |
Final calculation. Numerator: rows where the query holds (\(F = T\)): \(0.099 + 0.099 = 0.198\). Denominator: all rows: \(3 \times 0.099 + 0.02 = 0.317\).
\[ P(F \mid D, \neg L) = \frac{2 \times 0.099}{3 \times 0.099 + 1 \times 0.02} = \frac{0.198}{0.317} \approx 0.625 \]
The professor: "These two answers 0.099 plus 0.099 becomes your numerator, but in denominator it's not the same; it's three times this, plus the last one is 0.02. So now the answer is different." Here the weights do not cancel — carrying them through changes the estimate, which is exactly the point of the method.
13.6.6 Comparing the Three Approximate Techniques
| Feature | Prior Sampling | Rejection Sampling | Likelihood Weighting |
|---|---|---|---|
| Sample generation | Offline (a priori) | Online (per query) | Online (per query) |
| Evidence handling | None (random) | Reject non-matching rows | Hard-code evidence |
| Wasted computation | None | Yes (rejected rows) | None |
| Zero-denominator risk | Yes | No | No |
| Reusable across queries | Yes | No | No |
| Sample size | Can be very large | Limited by runtime | Limited by runtime |
| Weights | All equal (1) | All equal (1) | May vary per row |
| Fill order | Reverse linearized | Reverse linearized | Reverse linearized |
The sample-size trade-off. The professor on prior vs rejection sampling: "In prior sampling, I'm doing it offline. I can generate many samples, keep it in memory. So I can afford to generate a lot of samples. But if I am in rejection sampling, I'm online. I'm actually getting a query. I have to solve it. So I can't generate a lot."
Prior vs likelihood — which table is bigger? The professor poses it as a class question: "Can someone tell me for prior sampling will you have more rows or for likelihood weighing you will have more rows in your table?" Answer: likelihood weighting produces more rows for the same random values. Since likelihood weighting hard-codes the evidence columns, each row consumes fewer random values — with the same stream of random numbers, you can fill more rows. The professor: "In likelihood weighing, I'm already hard coding 2 variables, so just with two more, I'll be able to create one row. But in prior sampling, I am not hard coding anything. So I will use a lot of my values, random generated values, even to fill one row of my table." (In the exam-question example with five variables — viral, flu, food poisoning, fever, dehydration — prior sampling consumes 5 random values per row while likelihood weighting on evidence \(\{V, H\}\) consumes only 3.)
When likelihood weighting degrades. The weight formula is correct for any network, but its efficiency depends on where the evidence sits. Evidence variables that are ancestors of the query steer the sampled variables in the right direction — the sampled values "pay attention" to them through their parents. Evidence that is downstream of the query (in the children) cannot steer the sampling of upstream variables at all: rows are drawn with no knowledge of that evidence, and most of them end up with near-zero weights. The estimate is then dominated by the few high-weight rows, so many more samples are needed. This is the same disease as rejection sampling's acceptance rate, in a milder form — all rows are kept, but most may count for almost nothing.
Q: "Are the weights in likelihood weighting probabilities?" A: No. The weights are just scaling factors, not probabilities. Each row's weight corrects for the hard-coded evidence; the final probability comes from dividing the sum of weights where the query is true by the total sum of all weights. The professor's correction: "This one is not a probability, that is just a weight. Finally, what you get here, the 0.099 is what is the probability."
Q: "Why do weights differ between rows when V changes?" A: Because the \(V\) value determines which CPT row to use for the dependent variable \(L\). When \(V =\) true, \(P(\neg L \mid V) = 0.2\); when \(V =\) false, \(P(\neg L \mid \neg V) = 0.99\). The weight depends on the actual CPT value for that row's parent configuration — a randomly sampled parent can silently switch the evidence's CPT row, and the weight must follow.
Q: "How do we draw the timeline and find ranges?" A: Draw the endpoints 0 and 1. The positive (true) segment runs from 0 to the probability value; the negative (false) segment runs from that value to 1. For example, 0.8 positive means 0 to 0.8 is true and 0.8 to 1 is false. Only the positive value is needed — the negative is always 1 minus the positive. (In exams, only the positive value may be given; compute the negative yourself.)
Recap. Likelihood weighting keeps rejection sampling's guarantee (no zero denominators) without its waste: evidence is hard-coded, only non-evidence variables consume random values, and each row is corrected by a weight that equals the CPT probability of the hard-coded evidence given its parents. Weights are scaling factors, not probabilities; they cancel only when identical across rows. Where the evidence depends on a randomly sampled variable, the weight becomes row-specific — multiply through rather than canceling. This closes the lecture's three approximate techniques, and the comparison table above is the compact summary of how they differ.
13.7 Exam Guidance Summary
13.7.1 Exam Question Format and Tips
Exam note — question format. Only one approximate inferencing technique and one exact inferencing technique will be asked. The professor: "Only one approximate inferencing technique and only one exact inferencing technique might be given. Might be. I don't know." The combined question (exact + approximate) is worth about 4 marks.
What to expect:
- A Bayesian network will be provided with CPTs. (The professor's exam-question example used five variables: viral infection \(V\), flu \(L\), food poisoning \(D\), fever \(F\), and dehydration \(H\), with evidence \(V\) and \(H\).)
- A query will be given — e.g., "What is the probability of \(\neg\)Fever given V and H?"
- For exact inferencing: use the conditional probability approach (convert to joint, marginalize, substitute). The type of inferencing (causal, diagnostic, intercausal, mixed) should be identified — with evidence both upstream and downstream of the query, the answer is mixed.
- For approximate inferencing: random values will be provided in the question. Use them to construct the sample table — you are told how many rows to make by how many random values exist.
Key exam tips:
- D-separation is primarily a quiz-level concept. Expect questions asking to determine conditional independence given some evidence. Follow the five steps: draw query nodes, add ancestors, marry co-parents, remove evidence (never the query), check disjoint vs connected.
- For variable elimination, show all intermediate steps — the full merged table, each elimination step, and the final standalone table. "If I have given you a Bayesian tree myself, I have given you the tables, but then I have asked you a query which is directly on a dependent variable... you will have to perform variable elimination, systematically eliminate the parents and make my dependent variable itself independent."
- For approximate inferencing, the number of random values given determines the sample size. Divide them into groups based on the number of variables (prior sampling: one random value per variable per row) or non-evidence variables (likelihood weighting: one per non-evidence variable per row). In the five-variable exam example, prior sampling consumes sets of five; likelihood weighting with evidence \(\{V, H\}\) consumes sets of three — so likelihood weighting yields a bigger table from the same random values.
- "Sequence is always left to right" for assigning random values to variables — the given values are consumed in order, one cell at a time.
- For likelihood weighting, evidence is always given in the question — that is what you hard-code. The professor: "Evidence is what we always go and hard-code in likelihood."
- The timeline method: always follow the same pattern for all nodes — positive segment first (0 to probability value), then negative segment (probability value to 1). Consistency is key.
- Borderline values (falling exactly on a threshold) can be assigned either true or false — define your own rule and be consistent. "It's all approximate only."
- In exams, only the positive probability value may be given. You must calculate the negative value as 1 minus the positive value. (Conversely, sometimes only the negative is given, e.g., "not viral" = 0.4 — compute the positive as 1 minus it, then build the timeline 0 to 0.6.)
Cross-module mental map. The professor provides the course arc that places this lecture: "Propositional logic, predicate logic — in those we learned about inferencing. Then we slowly told, okay, but the world is not always certain. There is uncertainty. So we need probabilities. Then probability, we told that we can draw the whole scenario as a Bayesian network and we can answer queries. If a query is directly asked on a dependent variable, we can do variable elimination. There is some more concepts around approximate inferencing, and we are done." In other words: logic gave us inference under certainty; probability added uncertainty; the Bayesian network is the model; enumeration and variable elimination are exact inference; prior sampling, rejection sampling, and likelihood weighting are approximate inference. That is the complete toolkit for this module.
What comes next. The next module combines uncertainty with time: "Now we have uncertainty also, and we have time series also. I have the probabilities of today's, yesterday's, the day before yesterday's, then what do we do?" That is the territory of Markov models and hidden Markov models — reasoning over sequences where the state at time \(t+1\) depends on the state at time \(t\).
13.8 Key Industry Applications
13.8.1 Real-World Connections
Bayesian networks in practice. Bayesian networks are used in medical diagnosis (as in the viral/flu/fever example of this lecture — the classic structure of a diagnostic system where a few root causes propagate uncertainty to observable symptoms), fraud detection (banks model transactions as evidence whose causes — legitimate spending vs fraud — are hidden), risk assessment (insurers combine independent risk factors that jointly influence claim probability), and any domain that needs structured reasoning under uncertainty: sensor networks, robotics localization, spam filtering, and fault diagnosis in machinery. The pattern is always the same: model the causal dependencies as a DAG, fill the CPTs, and let the inference machinery answer the queries.
The software engineering trade-off. The professor frames the entire exact-vs-approximate decision as an engineering call: "Software engineering at the end is all a trade-off." Exact inference (enumeration, variable elimination) gives precise answers at a computational cost that grows with the network; approximate inference (sampling) trades accuracy for speed and scalability. Choosing between them means weighing the computation budget, the accuracy required by the application, and the network size — the same kind of cost-benefit reasoning that drives every other engineering decision in a software project.
Synthetic data generation. Prior sampling is conceptually identical to generating synthetic data: draw random worlds from the model's distribution and store them. This is exactly how synthetic datasets are produced for testing, for augmenting scarce real data, and for Monte Carlo simulation — the professor endorses the connection: "It's like generating synthetic data. That's exactly correct." In industry, the same mechanism powers what-if analysis: simulate millions of plausible scenarios offline, then query the stored set instantly when a decision is needed.
Empirical experiments and sample design. Sample size selection in approximate inferencing mirrors how real research is done: "We want to know how many people drink coffee, how many people prefer tea. You as a researcher are going to take a sample set... if you are capable, you will do it with 1,00,000 people; if you are more capable, you can do it with 1 crore people." Choosing \(N\) is a deliberate balance of cost against statistical power — more samples mean tighter estimates, but each sample costs computation (or survey money). The \(1/\sqrt{N}\) error scaling tells the engineer exactly how much accuracy an extra budget buys.
Memory vs computation trade-off. The three sampling techniques are a clean illustration of a classic systems trade-off. Prior sampling invests computation upfront (offline) to enable fast query responses (online) — computation stored in memory as a reusable table. Rejection and likelihood weighting invest computation at query time to guarantee the evidence is represented — no reuse, but no precomputation either. This space-time trade-off is the same one that drives caching, precomputation, and materialized views in database and web systems: decide once what to pay for ahead of time and what to pay for per request.
ACI Lecture 13 notes
Sections Breakdown
Joint and conditional query recipes, the chain rule, linearization, and the exact-versus-approximate split.
A graph algorithm to prove conditional independence, with worked examples and the link to the Markov blanket.
Exact inference for queries on dependent variables by joining and marginalizing tables.
Building a sample table offline and answering queries by counting rows.
Query-first sampling that rejects non-matching rows and removes the zero-denominator failure.
Hard-coding evidence and weighting rows by the CPT probability of the evidence.
Exam format, which technique is asked, and how random values set sample sizes.
Real-world uses of Bayesian networks and the engineering trade-offs among the sampling techniques.
Exam Revision Notes
Below is the distilled, exam-ready core. Every entry comes from the full explanation above. Use this section for rapid review; return to the main notes when a point needs more context.
Review of Bayesian Network Querying
Must-know: Joint query: linearize, chain rule, multiply CPT values. Conditional query: convert to a joint via an identity, marginalize hidden variables, normalize. Exact inference is not approximate just because probabilities are involved.
\[P(X_1, \ldots, X_n) = \prod_{i=1}^{n} P(X_i \mid \text{Parents}(X_i))\]
⚠️ Top pitfall: Summing or normalizing in a joint query, or forgetting to marginalize hidden variables in a conditional query.
Self-check: How does answering P(B | J, M) differ from answering P(B, J, M)?
Connects to: D-separation, Variable elimination.
D-Separation and D-Connectedness
Must-know: Draw the query nodes, add parents and ancestors, marry unlinked co-parents of a common child, then remove the evidence nodes (never the query). Disjoint means conditionally independent; connected means dependent.
\[X \perp Y \mid Z \text{ means X is conditionally independent of Y given } Z.\]
⚠️ Top pitfall: Removing the query node instead of the evidence nodes, or forgetting the marry step for nodes with two parents.
Self-check: In the car/weekend/bars network, why is C independent of B given the weekend W?
Connects to: Query review, Variable elimination.
Variable Elimination
Must-know: To answer a query on a dependent variable, join tables via the chain rule in linearized order, then sum out each parent until the variable stands alone. Eliminating is accounting, not deleting.
\[P(L, V) = P(L \mid V) \cdot P(V); \quad P(L = \text{true}) = P(L, V) + P(L, \neg V) = 0.48 + 0.004 = 0.484\]
⚠️ Top pitfall: Deleting a table without accounting for the parent's influence, or writing the joint in the wrong (non-linearized) order.
Self-check: Why cannot P(fever) be read straight from the fever condition table?
Connects to: Query review, D-separation.
Approximate Inference: Prior Sampling
Must-know: Fill the sample table offline in reverse linearized order using the timeline method, then answer queries by counting rows. If no row matches the evidence, the denominator is zero and it cannot answer that query.
\[ \hat{P}(X \mid e) \approx \frac{\text{rows where } X \text{ true and } e \text{ matches}}{\text{rows where } e \text{ matches}} \]
⚠️ Top pitfall: Filling children before parents, or using an inconsistent timeline across nodes.
Self-check: Why can prior sampling not answer P(F | D) when no row has D true?
Connects to: Rejection sampling, Likelihood weighting.
Approximate Inference: Rejection Sampling
Must-know: Take the query first, generate rows online, reject rows whose evidence does not match, then count within the kept rows. No zero denominator, but query-specific and limited in sample size.
\[ \hat P(X \mid e) \approx \frac{\text{kept rows where } X \text{ true}}{\text{kept rows}}; \quad \text{acceptance rate} = P(e) \]
⚠️ Top pitfall: Counting rejected rows in the denominator, or believing the filter introduces bias into the computation.
Self-check: Why is rejection sampling not biased even though rows are discarded?
Connects to: Prior sampling, Likelihood weighting.
Approximate Inference: Likelihood Weighting
Must-know: Defeat the zero-denominator failure by hard-coding the evidence, sampling only the non-evidence variables, and weighting each row by the product of the CPT probabilities of the evidence.
\[ w = \prod_{E \in \text{evidence}} P(E \mid \text{Parents}(E)); \quad \hat P(X \mid e) = \frac{\sum w \text{ over rows with } X}{\text{total weight}} \]
⚠️ Top pitfall: Treating weights as probabilities, or forgetting that a sampled parent can switch the CPT row used to price the evidence.
Self-check: Why is P(fever | D, not L) not simply 2 / 4 in the four-row example?
Connects to: Prior sampling, Rejection sampling.
Exam Guidance Summary
Must-know: One exact and one approximate technique are examined (about four marks). Evidence is what you hard-code in likelihood weighting; the sequence is always left to right.
⚠️ Top pitfall: Forgetting to compute the negative probability as 1 minus the positive.
Self-check: How many random values does one likelihood-weighting row consume in the five-variable example?
Connects to: All sections of this lecture.
Key Industry Applications
Must-know: Bayesian networks drive medical diagnosis, fraud detection, and risk analysis. Prior sampling offline equals synthetic data plus fast queries; rejection and likelihood weighting are online and per-query.
Self-check: Why can prior sampling afford many more samples than rejection sampling?
Connects to: Prior, rejection, and likelihood-weighting sampling.