Skip to content
Tutorials Center
My learning

Topics

Lesson 33 of 46 ยท Probabilistic Reasoning

Bayesian Networks

Learn Bayesian networks: structure and conditional probability tables, d-separation, exact inference by enumeration and variable elimination, and sampling, with Python code.

At the end of Probability for AI we hit a wall. A full joint distribution over n yes/no variables needs 2^n numbers, which is impossible for any realistic problem, and it is also unnatural: nobody can estimate a billion probabilities by hand. A Bayesian network (or belief network) solves both problems at once. It stores the joint distribution as a set of small tables, one per variable, by recording only which variables directly influence which.

In this lesson you will build a small medical-diagnosis network, read its independence assumptions with d-separation, and answer queries three ways: exact enumeration, variable elimination and sampling.

Structure and conditional probability tables

A Bayesian network has two parts.

  1. A directed acyclic graph (DAG). Each node is a random variable. An arrow from X to Y means X directly influences Y; X is a parent of Y.
  2. A conditional probability table (CPT) for each node, giving P(node | parents). A node with no parents has an ordinary prior.

Our example is a simplified clinic. Smoking and air pollution raise the chance of a lung disease; the disease, in turn, causes a cough and an abnormal X-ray.

graph TD
    S["Smoker"] --> D["Disease"]
    P["Pollution"] --> D
    D --> C["Cough"]
    D --> X["Xray"]

Causes point to effects: Smoker and Pollution cause Disease, and Disease causes the symptoms.

The key theorem is the chain rule for Bayesian networks: the joint probability is the product of each node's CPT entry given its parents.

P(x1, ..., xn) = ฮ  P(xi | parents(xi))

For our five variables:

P(S, P, D, C, X) = P(S) ยท P(P) ยท P(D | S, P) ยท P(C | D) ยท P(X | D)

A boolean node with k parents needs 2^k numbers, so the whole network stores 1 + 1 + 4 + 2 + 2 = 10 numbers instead of 2^5 โˆ’ 1 = 31. The savings are small here, but with 30 variables and at most 3 parents each, the network needs at most 30 ร— 8 = 240 numbers instead of about a billion.

Building the network in Python

The class below stores each CPT as a dictionary that maps a tuple of parent values to P(variable = True). Variables are added in topological order (parents before children), which lets us evaluate the chain rule with a simple loop. The query function ask uses inference by enumeration: for every value of the query variable, it sums over all hidden variables, then normalizes.

Python A Bayesian network and inference by enumeration

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Read the posteriors from top to bottom. Without evidence the disease has a 3.8% chance. A cough alone raises it to 17.4%, because coughs have other causes too. A cough and an abnormal X-ray raise it to 79.1%, and a smoker with both symptoms reaches 90.9%. Each new piece of evidence moves the belief in the direction that common sense expects, and the amounts follow from Bayes' rule rather than from hand-tuned rules. An abnormal X-ray with no cough gives only 14.3%: the missing cough counts against the disease, so evidence for and against combines.

d-separation: reading independence from the graph

The graph encodes conditional independence assumptions. d-separation (directional separation) is the rule that reads them off. Two sets of variables are d-separated by a set of observed variables Z when every path between them is blocked. Each three-node pattern on a path behaves in one of three ways:

Pattern Name Path is blocked when
A โ†’ B โ†’ C chain B is observed
A โ† B โ†’ C fork (common cause) B is observed
A โ†’ B โ† C collider (common effect) B and all its descendants are not observed

The collider is the surprising one. Smoker and Pollution are independent when we know nothing, but once we observe Disease (or even a symptom, which is a descendant of Disease), the path opens and they become dependent. This is the "explaining away" effect from the previous lesson: if a patient has the disease and is a smoker, pollution becomes a less necessary explanation.

A simple test for d-separation uses the moral graph. Keep only the ancestors of the variables involved, connect each pair of parents that share a child ("marry" them), drop the arrow directions, remove the observed nodes and check whether the two variables are still connected. If not, they are d-separated.

Python Testing d-separation on the clinic network

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The output matches the three patterns. Cough and X-ray are dependent when nothing is observed (a fork through Disease: a cough hints at disease, which hints at an abnormal X-ray) and independent once Disease is known. Smoker and Pollution are independent a priori, but observing the collider Disease, or its descendant Cough, makes them dependent.

Note: d-separation says which independences are guaranteed by the structure. Variables that are not d-separated may still happen to be independent for particular numbers, but the structure does not promise it.

Variable elimination

Enumeration repeats work. In P(Disease | Cough, Xray) it recomputes the same sub-sums again and again. Variable elimination instead works with factors, tables over some variables, and eliminates hidden variables one at a time:

  1. Turn every CPT into a factor.
  2. Restrict each factor to the observed values of the evidence.
  3. For each hidden variable: multiply all factors that mention it, then sum it out, producing one new smaller factor.
  4. Multiply the remaining factors and normalize.

The cost depends on the elimination order: the largest intermediate factor decides the work. For tree-like networks a good order keeps every factor tiny, so inference is fast even for hundreds of variables. For densely connected networks, exact inference is NP-hard in the worst case.

Python Variable elimination with factors

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The two elimination steps never build a table larger than 8 rows, and the answer, 0.7913 for Disease = True, is the same as with enumeration. The advantage grows quickly with network size: enumeration is exponential in the number of hidden variables, while variable elimination is exponential only in the size of the largest factor.

Approximate inference by sampling

When exact inference is too expensive, we can sample instead. Generate random worlds from the network by sampling each variable given its already-sampled parents, then estimate probabilities by counting.

  • Rejection sampling throws away every sample that disagrees with the evidence. It is simple, but wasteful when the evidence is unlikely: here only about 3% of samples survive.
  • Likelihood weighting never rejects. It fixes the evidence variables to their observed values and gives each sample a weight, the probability of the evidence given the sampled parents. Estimates are weighted averages.

Both converge to the exact answer as the number of samples grows, and both are straightforward to implement. We use a fixed seed so the run is reproducible.

Python Rejection sampling and likelihood weighting

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

With 50,000 samples, likelihood weighting is within 0.003 of the exact value while rejection sampling, which keeps only 1,742 samples, is off by about 0.015. Different seeds give different digits, but the pattern of weighting being the steadier of the two holds in general. Sampling shines for large networks where exact inference is hopeless, and it generalizes to MCMC methods such as Gibbs sampling.

Building networks in practice

Networks come from three sources. Experts can draw the graph from causal knowledge, which is how many diagnostic systems were built. CPT numbers can be learned from data by counting (maximum likelihood), often with smoothing so unseen combinations do not get probability zero. The structure itself can also be learned from data, but this is much harder. Whatever the source, prefer the causal direction when drawing arrows: causes pointing to effects gives smaller CPTs and models that are easier to explain and to update. After this, Hidden Markov Models and Filtering extends the same idea to variables that change over time.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What does a Bayesian network store for each node?

    Each node stores a CPT conditioned on its parents; the product of the CPT entries gives the joint probability.
  2. 2. A boolean node has 3 boolean parents. How many probabilities does its CPT need?

    There are 2^3 = 8 combinations of parent values, and each needs P(node = true). P(node = false) is 1 minus that.
  3. 3. In the pattern Smoker -> Disease <- Pollution, when does observing Disease change the relationship between Smoker and Pollution?

    A collider blocks the path when it is unobserved, and opens it when it or a descendant is observed. This gives the explaining-away effect.
  4. 4. Why is likelihood weighting often better than rejection sampling?

    Rejection sampling wastes every sample that contradicts the evidence, which is most of them when evidence is unlikely. Likelihood weighting fixes the evidence and weights samples instead.
  5. 5. What determines the cost of variable elimination?

    Each step builds a factor over the neighbors of the eliminated variable. A good order keeps factors small.

Summary

  • A Bayesian network is a DAG plus a CPT per node; the joint is the product of P(node | parents).
  • Exploiting independence cuts the number of stored probabilities from exponential to roughly linear in the number of variables.
  • d-separation reads conditional independence off the graph: chains and forks are blocked by observing the middle node, colliders are opened by observing the node or its descendants.
  • Exact inference by enumeration is simple; variable elimination reuses sub-results and depends on the elimination order.
  • Sampling methods (rejection sampling, likelihood weighting) give approximate answers that converge as samples grow.
  • Draw arrows from causes to effects for compact, interpretable models.

Next: Hidden Markov Models and Filtering.