Reasoning Under Uncertainty
Bayesian Networks
Chapter 1 ended with a problem: the full joint distribution is exponentially large. The fix mirrors exactly how Module 3 handled logic's scaling problem — most
Jr Codex AI Notes
Level: Intermediate–Advanced Prerequisites: Chapter 1 Time to complete: ~30 minutes
Table of Contents
- Exploiting Structure to Escape the Exponential Blowup
- What is a Bayesian Network?
- Conditional Probability Tables (CPTs)
- Building a Bayesian Network in Code
- Computing the Joint Distribution from the Network
- Inference — Answering Queries
- Conditional Independence — Why This Works
- Summary & Next Steps
1. Exploiting Structure to Escape the Exponential Blowup
Chapter 1 ended with a problem: the full joint distribution is exponentially large. The fix mirrors exactly how Module 3 handled logic's scaling problem — most variables aren't directly related to most others, and a good representation should only encode the relationships that actually matter.
Key Insight
─────────────────────────────────────────
In most REAL domains, a variable directly depends on only a
FEW others, not ALL of them.
Example: "Alarm" depends on "Burglary" and "Earthquake" —
but NOT directly on, say, "Weather in Antarctica." Most
pairs of real-world variables are IRRELEVANT to each other.
A Bayesian network encodes ONLY the relevant dependencies,
dramatically shrinking the representation compared to the
full joint distribution.
─────────────────────────────────────────
2. What is a Bayesian Network?
A Bayesian network is a directed acyclic graph (DAG) where nodes are random variables and edges represent direct probabilistic dependence — each node stores a conditional probability table (Section 3) describing its distribution given its parents.
The Classic Burglary-Alarm Network
─────────────────────────────────────────
[Burglary] [Earthquake]
\ /
\ /
▼ ▼
[Alarm]
/ \
▼ ▼
[JohnCalls] [MaryCalls]
─────────────────────────────────────────
Reading the Graph's Meaning
─────────────────────────────────────────
Burglary and Earthquake are INDEPENDENT of each other (no edge)
Alarm DEPENDS ON both Burglary and Earthquake (both point to it)
JohnCalls DEPENDS ONLY on Alarm (not directly on Burglary/Earthquake)
MaryCalls DEPENDS ONLY on Alarm (same)
This structure encodes a real-world assumption: John and Mary
only know about the alarm sounding, not the burglary itself
directly — a REASONABLE simplification of reality.
─────────────────────────────────────────
3. Conditional Probability Tables (CPTs)
Each node's CPT specifies P(node | its parents) — for a node with no parents, this is just its prior probability.
# Nodes with NO parents — simple priors
P_Burglary = {"true": 0.001, "false": 0.999} # burglaries are rare
P_Earthquake = {"true": 0.002, "false": 0.998} # earthquakes are rarer
# Alarm's CPT — depends on BOTH Burglary and Earthquake
P_Alarm_given_parents = {
("true", "true"): {"true": 0.95, "false": 0.05}, # burglary AND earthquake
("true", "false"): {"true": 0.94, "false": 0.06}, # burglary, no earthquake
("false", "true"): {"true": 0.29, "false": 0.71}, # no burglary, earthquake
("false", "false"): {"true": 0.001, "false": 0.999}, # neither
}
# JohnCalls and MaryCalls each depend ONLY on Alarm
P_JohnCalls_given_alarm = {
"true": {"true": 0.90, "false": 0.10},
"false": {"true": 0.05, "false": 0.95},
}
P_MaryCalls_given_alarm = {
"true": {"true": 0.70, "false": 0.30},
"false": {"true": 0.01, "false": 0.99},
}Counting the Savings
─────────────────────────────────────────
Full joint distribution: 2^5 = 32 entries needed
This Bayesian network's CPTs:
P(Burglary): 1 number (2 entries, but they sum to 1)
P(Earthquake): 1 number
P(Alarm | B,E): 4 rows × 1 number each
P(JohnCalls | A): 2 rows
P(MaryCalls | A): 2 rows
Total: just 10 independent numbers — a THIRD of the full
joint distribution's size, and the savings grow FAR larger
as networks get bigger and sparser
─────────────────────────────────────────
4. Building a Bayesian Network in Code
class BayesianNetwork:
def __init__(self):
self.nodes = {} # name -> parent names
self.cpts = {} # name -> conditional probability table
def add_node(self, name, parents, cpt):
self.nodes[name] = parents
self.cpts[name] = cpt
def probability(self, node, value, parent_values):
"""Look up P(node=value | parents=parent_values) from its CPT."""
cpt = self.cpts[node]
if not self.nodes[node]: # no parents — cpt is a flat dict
return cpt[value]
key = tuple(parent_values[p] for p in self.nodes[node])
return cpt[key][value]
bn = BayesianNetwork()
bn.add_node("Burglary", [], P_Burglary)
bn.add_node("Earthquake", [], P_Earthquake)
bn.add_node("Alarm", ["Burglary", "Earthquake"], P_Alarm_given_parents)
bn.add_node("JohnCalls", ["Alarm"], P_JohnCalls_given_alarm)
bn.add_node("MaryCalls", ["Alarm"], P_MaryCalls_given_alarm)
p = bn.probability("Alarm", "true", {"Burglary": "true", "Earthquake": "false"})
print(p) # 0.945. Computing the Joint Distribution from the Network
A Bayesian network can still reconstruct any joint probability when needed — via the chain rule, using the graph's structure to simplify the calculation dramatically.
The Chain Rule for Bayesian Networks
─────────────────────────────────────────
P(x1, x2, ..., xn) = Π P(xi | parents(xi))
The joint probability of ALL variables equals the PRODUCT
of each variable's CPT value, given only ITS OWN parents —
not everything else in the network.
─────────────────────────────────────────
def joint_probability(bn, assignment):
"""
assignment: dict of variable -> value for ALL variables in the network
Computes P(assignment) using the chain rule over the network structure.
"""
probability = 1.0
for node in bn.nodes:
value = assignment[node]
parent_values = {p: assignment[p] for p in bn.nodes[node]}
probability *= bn.probability(node, value, parent_values)
return probability
full_assignment = {
"Burglary": "true", "Earthquake": "false", "Alarm": "true",
"JohnCalls": "true", "MaryCalls": "false",
}
p_specific_world = joint_probability(bn, full_assignment)
print(f"{p_specific_world:.6f}") # the probability of this EXACT scenarioThis directly answers Chapter 1's original question ("what's the probability of this specific combination?") but computed from a compact representation (Section 3's small CPTs) rather than a stored, exponentially-large table.
6. Inference — Answering Queries
The real value of a Bayesian network: answering a query like "given that both John and Mary called, what's the probability there's actually a burglary?" — directly extending Module 3, Chapter 4's inference concept to probabilistic reasoning.
from itertools import product
def enumerate_all(bn, query_var, evidence):
"""
A brute-force (but correct) inference method: sum over every possible
combination of the UNOBSERVED variables, consistent with the evidence.
"""
all_vars = list(bn.nodes.keys())
hidden_vars = [v for v in all_vars if v not in evidence and v != query_var]
results = {}
for query_value in ["true", "false"]:
total = 0.0
for combo in product(["true", "false"], repeat=len(hidden_vars)):
assignment = dict(evidence)
assignment[query_var] = query_value
assignment.update(dict(zip(hidden_vars, combo)))
total += joint_probability(bn, assignment)
results[query_value] = total
# Normalize so the two results sum to 1 (this is BAYES' RULE'S normalization, Ch.1)
normalizer = sum(results.values())
return {k: v / normalizer for k, v in results.items()}
evidence = {"JohnCalls": "true", "MaryCalls": "true"}
result = enumerate_all(bn, "Burglary", evidence)
print(result) # {'true': ~0.284, 'false': ~0.716} — burglary is now MUCH more likely
# than the 0.001 prior, given BOTH calls as evidenceWhat Just Happened, Conceptually
─────────────────────────────────────────
Starting belief: P(Burglary) = 0.001 (rare)
New evidence arrives: BOTH John AND Mary called — this is
strong evidence the alarm went off, which is itself evidence
of a burglary (or earthquake).
Updated belief: P(Burglary | both calls) ≈ 0.284 — dramatically
higher than the prior, exactly the Bayesian "prior → posterior"
update from Chapter 1, now computed automatically over an
entire NETWORK of interdependent variables.
─────────────────────────────────────────
This brute-force enumeration is correct but slow (exponential in the number of hidden variables) — real Bayesian network inference engines use much faster techniques (variable elimination, sampling-based approximate methods) that are beyond this introductory chapter's scope, but solve exactly this same query more efficiently.
7. Conditional Independence — Why This Works
The mathematical property that makes Bayesian networks valid and useful: a node is conditionally independent of its non-descendants, given its parents.
Conditional Independence, Concretely
─────────────────────────────────────────
JohnCalls is CONDITIONALLY INDEPENDENT of Burglary, GIVEN Alarm.
In plain terms: ONCE you know whether the alarm went off,
learning about the burglary directly gives you NO ADDITIONAL
information about whether John calls — Alarm already
"screens off" that connection entirely.
This is EXACTLY why JohnCalls' CPT only needs Alarm as a
parent, not Burglary and Earthquake too — a dramatic
simplification that's still mathematically EXACT, not
an approximation.
─────────────────────────────────────────
# Verifying this conditional independence property directly:
# P(JohnCalls | Alarm, Burglary) should equal P(JohnCalls | Alarm) alone
p_john_given_alarm_only = P_JohnCalls_given_alarm["true"]["true"] # 0.90
# Since JohnCalls' CPT doesn't even INCLUDE Burglary as an input,
# this conditional independence is BUILT INTO the network's structure
# by design, not something that needs separate verification each time.
print(p_john_given_alarm_only) # 0.90, regardless of Burglary's valueThis exact property is what allowed Section 3's compact CPTs to correctly reconstruct the full joint distribution in Section 5 — the network's graph structure isn't just a visualization convenience, it's an assertion of which conditional independencies hold, and the entire framework's correctness depends on that assertion matching reality reasonably well.
8. Summary & Next Steps
Key Takeaways
- Bayesian networks exploit conditional independence to represent a joint distribution compactly — encoding only the direct dependencies that actually matter, dramatically shrinking the representation versus Chapter 1's exponential full joint distribution.
- Each node's Conditional Probability Table (CPT) specifies its distribution given only its direct parents in the graph.
- The chain rule reconstructs any full joint probability as the product of each node's CPT value — computed from the compact representation, not a stored exponential table.
- Inference answers queries like "given this evidence, what's the updated probability of that variable?" — conceptually the same prior-to-posterior update from Chapter 1's Bayes' theorem, now automated across an entire network.
- The whole framework rests on conditional independence: a node depends only on its parents, screening off influence from more distant variables — a structural assumption, not just a computational convenience.
Concept Check
- Why does a Bayesian network need far fewer numbers than the full joint distribution to represent the same information?
- What does it mean for JohnCalls to be "conditionally independent" of Burglary, given Alarm?
- How does observing evidence (both John and Mary calling) change the network's belief about Burglary, and why does that connect back to Bayes' theorem from Chapter 1?
Next Chapter
→ Chapter 3: Naive Bayes & Probabilistic Inference
Jr Codex — 1-on-1 Personalized Coaching | Back to Module Index