Bayesian Networks
Chapter Forty-One
Syllabus topic Module 1, "Bayesian Networks"
Pages 221 to 226 of 591
In one line
A Bayesian network draws the causes as arrows into their effects, and then each variable needs only a small table saying how it depends on its own parents.
In the wording a student can write in an examination: a Bayesian network is a directed acyclic graph whose nodes are random variables and in which an arrow from X to Y means X is a parent of Y. Each node carries a conditional probability table giving P(node | its parents) for every combination of parent values. The network represents the full joint distribution by the chain rule for Bayesian networks:
P(x1, x2, ..., xn) = product over i of P(xi | parents of xi)
and the conditional independence it asserts is that each variable is conditionally independent of its non-descendants given its parents.
What the graph claims
An arrow is not a claim about causation as such, and it is not a claim about correlation either. The precise claim is the one in the definition, and getting it right is worth marks: a variable is conditionally independent of its non-descendants given its parents.
Read it as an instruction: to predict a variable, its parents are all you need. Anything else that is not downstream of it adds nothing once the parents are known. The network is a set of statements of the form "given these, forget everything else", and each such statement is what removes rows from the joint table.
In practice arrows are drawn from cause to effect, because that direction produces the sparsest graph and the easiest tables to fill in. That is a modelling convention with a good reason, not part of the definition. A network with the arrows reversed can represent the same distribution, and will usually need far more numbers.
The four-node network
The standard example. A Burglary or an Earthquake can set off an Alarm, and if the alarm sounds a neighbour may Call.
| Node | Parents | Its table gives |
|---|---|---|
Burglary | none | one number: the prior |
Earthquake | none | one number |
Alarm | Burglary, Earthquake | four numbers, one per combination of parents |
Call | Alarm | two numbers |
Note what the graph says by what it does not contain. There is no arrow between Burglary and Earthquake: they are independent. There is no arrow from Burglary to Call: a burglary affects the call only through the alarm. That is the conditional independence, and it is what lets Call's table have two numbers instead of eight.
The chain rule, and one joint entry read off the network
# A Bayesian network: the graph, the conditional probability tables, the chain
# rule that reads a joint entry off it, and inference by enumeration.
from itertools import product
# The four-node network. Each node: its parents, and P(node = True | parents).
NET = {
"Burglary": ([], {(): 0.001}),
"Earthquake": ([], {(): 0.002}),
"Alarm": (["Burglary", "Earthquake"], {(True, True): 0.95,
(True, False): 0.94,
(False, True): 0.29,
(False, False): 0.001}),
"Call": (["Alarm"], {(True,): 0.90, (False,): 0.05}),
}
ORDER = ["Burglary", "Earthquake", "Alarm", "Call"]
def p_true(node, assignment):
parents, table = NET[node]
key = tuple(assignment[p] for p in parents)
return table[key]
def p_node(node, value, assignment):
t = p_true(node, assignment)
return t if value else 1 - t
def joint(assignment):
"""The CHAIN RULE: multiply each node's probability given its parents."""
out = 1.0
for node in ORDER:
out *= p_node(node, assignment[node], assignment)
return out
print("the network")
for node in ORDER:
parents, table = NET[node]
print(" %-10s parents: %s" % (node, ", ".join(parents) if parents else "none"))
print()
print("how many numbers does it need, against the full joint table?")
need = sum(2 ** len(NET[n][0]) for n in ORDER)
print(" the network: %d numbers" % need)
print(" the full joint over 4 binary variables: 2**4 - 1 = %d free numbers" % (2 ** 4 - 1))
print()
print("ONE JOINT ENTRY by the chain rule: burglary, no earthquake, alarm, call")
a = {"Burglary": True, "Earthquake": False, "Alarm": True, "Call": True}
terms = []
out = 1.0
for node in ORDER:
v = p_node(node, a[node], a)
terms.append("%.5f" % v)
out *= v
print(" " + " * ".join(terms) + " = %.9f" % out)
print()
print("INFERENCE BY ENUMERATION: P(Burglary | Call = True)")
tot = {True: 0.0, False: 0.0}
for b, e, al in product([True, False], repeat=3):
a = {"Burglary": b, "Earthquake": e, "Alarm": al, "Call": True}
tot[b] += joint(a)
print(" unnormalised: burglary %.9f, no burglary %.9f" % (tot[True], tot[False]))
s = tot[True] + tot[False]
print(" P(Call = True) = %.9f" % s)
print(" P(Burglary = True | Call = True) = %.6f %.3f%%"
% (tot[True] / s, 100 * tot[True] / s))
print(" P(Burglary = False | Call = True) = %.6f" % (tot[False] / s))
print()
print("the prior was 0.001, so one telephone call has multiplied the")
print("probability of a burglary by about %.0f times, and it is still only %.1f%%."
% ((tot[True] / s) / 0.001, 100 * tot[True] / s))Bayesian Networks
the network
Burglary parents: none
Earthquake parents: none
Alarm parents: Burglary, Earthquake
Call parents: Alarm
how many numbers does it need, against the full joint table?
the network: 8 numbers
the full joint over 4 binary variables: 2**4 - 1 = 15 free numbers
ONE JOINT ENTRY by the chain rule: burglary, no earthquake, alarm, call
0.00100 * 0.99800 * 0.94000 * 0.90000 = 0.000844308
INFERENCE BY ENUMERATION: P(Burglary | Call = True)
unnormalised: burglary 0.000849017, no burglary 0.051289959
P(Call = True) = 0.052138976
P(Burglary = True | Call = True) = 0.016284 1.628%
P(Burglary = False | Call = True) = 0.983716
the prior was 0.001, so one telephone call has multiplied the
probability of a burglary by about 16 times, and it is still only 1.6%.Bayesian Networks
Three things in that output.
The joint entry is read off the graph by multiplication. The probability of a burglary, no earthquake, the alarm sounding and a call is 0.001 0.998 0.94 * 0.90, which is 0.000844308. Each factor is one node's own number, looked up with its parents' values, and the multiplication is the chain rule.
The network needs 8 numbers where the joint needs 15. On four variables that is a modest saving. The saving grows with the graph's sparsity: a network of n Boolean variables in which no node has more than k parents needs at most n * 2k numbers against 2n - 1. At 30 variables with at most 3 parents each, that is 240 numbers against over a thousand million.
The answer to the query is 1.6 per cent. The prior was 0.1 per cent, so one telephone call multiplied the belief by about sixteen. And it is still small, which is the base rate effect of Bayes Theorem appearing again: burglaries are rare, false alarms are not, and one call is weak evidence.
Where the numbers come from, and why the direction matters
This is the practical argument for drawing arrows from cause to effect, and a paper can ask for it.
The tables the network needs are of the form P(effect | its causes). Those are exactly the numbers a person can estimate: how often does the alarm sound when there is a burglary and no earthquake? An engineer can answer that from the alarm's design, and it does not change when the neighbourhood's burglary rate changes.
Reverse an arrow and you need P(burglary | alarm), which depends on the burglary rate, the earthquake rate and the alarm's reliability all at once. It is a diagnostic number rather than a causal one, it is much harder to estimate, and it changes whenever anything else does.
So the causal direction gives numbers that are local, stable and obtainable, which is the real reason Bayesian networks are usable at all. The arithmetic does not care; the person filling in the tables does.
Reading independence off the graph
The three patterns from Conditional Independence are the three shapes a three-node network can take, and knowing them lets independence be read from the picture.
| In the network | Shape | Unconditionally | Given the middle |
|---|---|---|---|
Burglary and Call, through Alarm | a chain | dependent | independent given Alarm |
| Two symptoms of one cause | a common cause, or fork | dependent | independent given the cause |
Burglary and Earthquake, into Alarm | a common effect, a collider | independent | dependent given Alarm |
Bayesian Networks
Explaining away, in this network. Burglary and Earthquake are independent: no arrow joins them. Now suppose the alarm is known to be sounding. Learning that there was an earthquake makes a burglary less likely, because the earthquake accounts for the alarm. Evidence at a common effect creates a dependence between causes that had none, and this is the one pattern that behaves the opposite way from the other two.
The general rule that decides all cases at once is called d-separation, and it is not on MU's label; the three patterns above are what a paper asks for and they cover every question likely to be set.
Building one
A paper may ask how a network is constructed, and there is a procedure.
- Choose the variables, and an ordering in which causes come before effects.
- For each variable in that order, choose as parents the smallest set of earlier variables that it directly depends on, that is the smallest set given which it is conditionally independent of the other earlier ones.
- Fill in its conditional probability table.
Step 1 matters more than it looks. A bad ordering produces a correct network with far more arrows: order the burglary example as Call, Alarm, Burglary, Earthquake and the graph acquires extra edges and needs more numbers, while representing the same distribution. Causes first gives the sparsest graph, which is the same point as the direction argument above.
And the network is acyclic by construction, because each node's parents come earlier in the ordering. A cycle would make the chain rule meaningless.
Distinctions
| Bayesian network | Full joint distribution | |
|---|---|---|
| Stores | one small table per node | one number per atomic event |
| Numbers needed, 4 binary variables | 8 | 15 |
| Numbers needed, 30 variables, at most 3 parents | about 240 | over a thousand million |
| Complete | yes, it determines the joint | yes |
| Its numbers are obtainable | yes, they are local and causal | no |
| Causal direction | Diagnostic direction | |
|---|---|---|
| Tables give | P(effect given causes) | P(cause given effects) |
| Estimable by a person | yes | hard |
| Stable when other rates change | yes | no |
| Graph sparsity | sparser | denser |
| Chain and common cause | Common effect | |
|---|---|---|
| Unconditionally | dependent | independent |
| Given the middle node | independent | dependent |
| The phenomenon | explaining away |
What it does not mean
An arrow is not a claim that causation has been proved. The formal content is the conditional independence: a variable is independent of its non-descendants given its parents.
A missing arrow is a claim, and a strong one. The absence of an arrow from Burglary to Call says a burglary affects the call only through the alarm. Missing arrows are where a network's assumptions live.
Bayesian Networks
The network is not an approximation of the joint distribution. It represents it exactly. What it drops are the numbers the conditional independences make redundant.
More arrows are not better. A fully connected network is correct and needs as many numbers as the joint, so it buys nothing. The value is in what is absent.
Independent causes do not stay independent. Given a shared effect they become dependent, which is explaining away.
A cycle is not merely inelegant. The chain rule has no meaning on a cyclic graph, which is why the graph must be acyclic.
Quick revision
- A Bayesian network is a directed acyclic graph of random variables; each node has a conditional probability table for
P(node | parents). - Chain rule:
P(x1..xn) = product of P(xi | parents of xi). The claim it makes is that each variable is conditionally independent of its non-descendants given its parents. - The burglary network:
BurglaryandEarthquakewith no parents,Alarmwith both as parents,CallwithAlarm. 8 numbers against the joint's 15. - One joint entry:
0.001 0.998 0.94 * 0.90 = 0.000844308. P(Burglary | Call)is 1.628 per cent, against a prior of 0.1 per cent: one call multiplies the belief about sixteen times and it is still small.- Scale: n Boolean variables with at most k parents each need at most
n * 2knumbers. 30 variables, 3 parents: about 240 against over a thousand million.** - Arrows go from cause to effect because that makes the tables
P(effect | causes), which are local, stable and obtainable. The diagnostic direction needs numbers nobody can estimate and gives a denser graph. - Reading independence: chain and common cause are blocked by the middle; a common effect is opened by it, which is explaining away.
- Building one: order the variables with causes first, give each the smallest set of earlier parents it depends on, then fill the table. A bad ordering gives a correct but denser network.
Test yourself
1. Define a Bayesian network and state the chain rule for it. A directed acyclic graph whose nodes are random variables, each carrying a conditional probability table for the node given its parents. The joint distribution is the product over all nodes of the probability of each node given its parents.
2. What conditional independence does the graph assert? That each variable is conditionally independent of its non-descendants given its parents. Equivalently, to predict a variable, its parents are all that is needed.
Bayesian Networks
3. How many numbers does the four-node burglary network need, and how many does the full joint over the same variables need? Eight: one each for Burglary and Earthquake, four for Alarm with its two parents, and two for Call. The full joint over four Boolean variables needs 2 to the power 4 minus 1, which is 15.
4. Compute the probability of a burglary, no earthquake, the alarm sounding and a call. Multiply each node's probability given its parents: 0.001 times 0.998 times 0.94 times 0.90, which is 0.000844308.
5. Why are arrows drawn from cause to effect rather than the other way? Because the tables then hold numbers of the form P(effect | causes), which a person can estimate from the mechanism and which do not change when other rates in the domain change. The reverse direction needs diagnostic numbers that depend on everything at once, and it produces a denser graph.
6. What is explaining away, and where does it occur in this network? When two independent causes share an effect, observing the effect makes them dependent. In this network Burglary and Earthquake are independent, but once the alarm is known to be sounding, learning of an earthquake reduces the probability of a burglary, because the earthquake already accounts for the alarm.
7. Describe how a Bayesian network is constructed, and say what a bad variable ordering costs. Choose the variables and order them with causes before effects. For each in turn, take as parents the smallest set of earlier variables on which it directly depends, and fill in its conditional probability table. A bad ordering still gives a correct network, but with more arrows and therefore more numbers to supply, and the numbers themselves become harder to estimate.
The rest of this subject
These notes are cut from the University's printed syllabus. Open the syllabus itself, or the past papers, for the same subject.