Simple Algorithm
Artificial Intelligence · Hidden Layer · 24 min

Bayesian Networks

Compact joint distributions from conditional independence.

Thirty yes-or-no variables have a joint distribution with more than a billion entries. If each variable depends directly on at most three others, a Bayesian network stores the same distribution in at most 240 numbers, and the graph alone tells you which variables are independent. This lesson builds the machinery: the factorization, d-separation, exact inference by variable elimination, and sampling when exact inference is too expensive.

What you’ll learn

  • Derive the factorization P(x1,…,xn)=∏iP(xi∣pai)P(x_1,\dots,x_n)=\prod_iP(x_i\mid\mathrm{pa}_i) from the chain rule, count its parameters, and prove that it is equivalent to the local Markov property.
  • Decide conditional independence with d-separation by analyzing chains, forks and colliders, and identify a node's Markov blanket.
  • Run variable elimination on a query, bound its cost by the induced width, and explain why exact inference is NP-hard in general but linear-time on polytrees.
  • Estimate posteriors by rejection sampling, likelihood weighting and Gibbs sampling, predict when each one fails, and learn CPTs from complete data by counting.

From the chain rule to a graph

A Bayesian network is a directed acyclic graph (DAG) whose nodes are random variables X1,…,XnX_1,\dots,X_n, together with one conditional probability table (CPT) per node, P(Xi∣Pai)P(X_i\mid\mathrm{Pa}_i), where Pai\mathrm{Pa}_i is the set of XiX_i's parents. The network represents one joint distribution:

P(x1,…,xn)=∏i=1nP(xi∣pai)P(x_1,\dots,x_n)=\prod_{i=1}^nP(x_i\mid\mathrm{pa}_i)
Lowercase letters are values, and pai\mathrm{pa}_i is the value that the assignment x1,…,xnx_1,\dots,x_n gives to XiX_i's parents. Each factor is one CPT entry, so evaluating the joint at one point takes nn table lookups.
DerivationWhere the product comes from, and what it saves
  1. P(x1,…,xn)=∏i=1nP(xi∣x1,…,xi−1)P(x_1,\dots,x_n)=\prod_{i=1}^nP(x_i\mid x_1,\dots,x_{i-1})

    Number the variables in a topological order of the graph, parents before children. The chain rule holds for every distribution:

  2. P(xi∣x1,…,xi−1)=P(xi∣pai)P(x_i\mid x_1,\dots,x_{i-1})=P(x_i\mid\mathrm{pa}_i)

    The network's modeling assumption: given its parents, each variable is conditionally independent of its other predecessors. The parents are among the predecessors, so each chain-rule factor shrinks to a CPT entry:

  3. ∑i=1n(ri−1) qinumbers, instead of∏i=1nri−1\sum_{i=1}^n(r_i-1)\,q_i\quad\text{numbers, instead of}\quad\prod_{i=1}^nr_i-1

    A variable with rir_i values whose parents have qi=∏j∈Pairjq_i=\prod_{j\in\mathrm{Pa}_i}r_j joint configurations needs (ri−1) qi(r_i-1)\,q_i numbers, so the network needs

  4. P(j,m,a,¬b,¬e)=0.90×0.70×0.001×0.999×0.998≈0.000628P(j,m,a,\neg b,\neg e)=0.90\times0.70\times0.001\times0.999\times0.998\approx0.000628

    In the alarm network of the Input Layer that is 1+1+4+2+2=101+1+4+2+2=10 numbers instead of 25−1=312^5-1=31. Any entry of the joint is a product of five of them, for example a false alarm that both neighbors report:

CPTs grow exponentially in the number of parents, so models with many causes use structured CPTs. In a noisy-OR, each true parent jj independently fails to trigger the effect with probability qjq_j, so P(x=false∣pa)=∏j: paj=trueqjP(x=\text{false}\mid\mathrm{pa})=\prod_{j:\,\mathrm{pa}_j=\text{true}}q_j: kk numbers instead of 2k2^k.

Check your understanding

A binary node has four binary parents, and its CPT is a full table (no noisy-OR). How many independent numbers does the CPT contain?

  1. 4
  2. 16
  3. 32
  4. 31
Show the answer

B. 16

One number, P(X=true∣pa)P(X=\text{true}\mid\mathrm{pa}), for each of the 24=162^4=16 parent configurations; P(X=false∣pa)P(X=\text{false}\mid\mathrm{pa}) follows by subtraction.

Reading independence off the graph

The factorization implies many more independences than the local ones, and three-node patterns explain them all. In each, ask whether XX and ZZ are dependent, first marginally and then given the middle node YY:

PatternGraphXX and ZZ marginallyGiven YY
ChainX→Y→ZX\to Y\to Zdependent (in general)independent
Fork (common cause)X←Y→ZX\leftarrow Y\to Zdependent (in general)independent
Collider (common effect)X→Y←ZX\to Y\leftarrow Zindependentdependent: explaining away
"Dependent in general" means for almost every choice of CPTs; special numbers can make them independent by accident.
DerivationWhy the collider behaves the other way
  1. P(z∣x,y)=P(x) P(y∣x) P(z∣y)P(x) P(y∣x)=P(z∣y)P(z\mid x,y)=\frac{P(x)\,P(y\mid x)\,P(z\mid y)}{P(x)\,P(y\mid x)}=P(z\mid y)

    Chain. Once YY is known, XX adds nothing about ZZ:

  2. P(x,z)=P(x) P(z)∑yP(y∣x,z)=P(x) P(z)P(x,z)=P(x)\,P(z)\sum_yP(y\mid x,z)=P(x)\,P(z)

    Collider, marginally. Summing out the effect leaves the two causes' priors:

  3. P(x,z∣y)=P(x) P(z) P(y∣x,z)P(y)P(x,z\mid y)=\frac{P(x)\,P(z)\,P(y\mid x,z)}{P(y)}

    Collider, given YY. Now the CPT of YY couples them, and the joint factors as f(x) g(z)f(x)\,g(z) only if P(y∣x,z)P(y\mid x,z) happens to:

  4. P(b∣a)=0.374,P(b∣a,e)=0.0033;P(b∣j)=0.016,P(b∣j,e)=0.0029P(b\mid a)=0.374,\quad P(b\mid a,e)=0.0033;\qquad P(b\mid j)=0.016,\quad P(b\mid j,e)=0.0029

    Observing a descendant of the collider partly reveals it, so it couples the causes too. In the alarm network:

One consequence is used constantly. The Markov blanket of XX, made of its parents, its children and its children's other parents, d-separates XX from every other node: once the blanket is known, nothing else in the network carries information about XX.

Check your understanding

In the sprinkler network (Cloudy → Sprinkler, Cloudy → Rain, Sprinkler → WetGrass ← Rain), which statement does d-separation support?

  1. Sprinkler and Rain are independent, since neither is a parent of the other
  2. Sprinkler and Rain are independent given WetGrass
  3. Sprinkler and Rain are independent given Cloudy, and in general dependent given Cloudy and WetGrass
  4. Sprinkler and Rain are dependent given every set of the other variables
Show the answer

C. Sprinkler and Rain are independent given Cloudy, and in general dependent given Cloudy and WetGrass

Two paths join them. The fork S←C→RS\leftarrow C\to R is blocked by observing CC; the collider S→W←RS\to W\leftarrow R is open only if WW is observed. Given CC alone both are blocked, and in the built-in network P(Rain | Cloudy) stays 80% whatever the sprinkler did. Given CC and WW, the collider opens: P(Rain | Cloudy, WetGrass) = 97.6% falls to 81.5% when you also learn that the sprinkler ran.

Exact inference: variable elimination

A query asks for P(X∣e)P(X\mid\mathbf e), the distribution of a query variable given evidence e\mathbf e, with the remaining hidden variables Y\mathbf Y summed out: P(X∣e)=α∑yP(X,e,y)P(X\mid\mathbf e)=\alpha\sum_{\mathbf y}P(X,\mathbf e,\mathbf y), where α\alpha normalizes. Summing the full joint costs O(n 2n)\order{n\,2^n} for binary variables.

Variable elimination (VE) pushes each sum inward past the factors that do not mention its variable, and stores the intermediate tables, called factors. It is dynamic programming over the factorization.

DerivationP(Burglary | j, m) by variable elimination
  1. P(B∣j,m)=α P(B)∑eP(e)∑aP(a∣B,e) P(j∣a) P(m∣a)P(B\mid j,m)=\alpha\,P(B)\sum_eP(e)\sum_aP(a\mid B,e)\,P(j\mid a)\,P(m\mid a)

    Write the query with each sum pushed as far right as it can go:

  2. f1(a)=P(j∣a) P(m∣a)=(0.9×0.7, 0.05×0.01)=(0.63, 0.0005)f_1(a)=P(j\mid a)\,P(m\mid a)=(0.9\times0.7,\ 0.05\times0.01)=(0.63,\ 0.0005)

    The evidence turns the two call CPTs into one factor of aa alone, listed as (true, false):

  3. f2(b,e)=∑aP(a∣b,e) f1(a):f2(b,¬e)=0.94×0.63+0.06×0.0005≈0.5922,f2(¬b,¬e)≈0.00113f_2(b,e)=\sum_aP(a\mid b,e)\,f_1(a):\quad f_2(b,\neg e)=0.94\times0.63+0.06\times0.0005\approx0.5922,\quad f_2(\neg b,\neg e)\approx0.00113

    Sum out AA: multiply the factors that mention aa and sum. This creates a factor over BB and EE, for example

  4. f3(b)=∑eP(e) f2(b,e)≈0.5922,f3(¬b)≈0.001493f_3(b)=\sum_eP(e)\,f_2(b,e)\approx0.5922,\qquad f_3(\neg b)\approx0.001493

    Sum out EE, weighting by P(e)=0.002P(e)=0.002 (with f2(b,e)≈0.5985f_2(b,e)\approx0.5985 and f2(¬b,e)≈0.1831f_2(\neg b,e)\approx0.1831):

  5. P(B∣j,m)=α (0.001×0.5922, 0.999×0.001493)=α (0.000592, 0.001492)≈(0.284, 0.716)P(B\mid j,m)=\alpha\,(0.001\times0.5922,\ 0.999\times0.001493)=\alpha\,(0.000592,\ 0.001492)\approx(0.284,\ 0.716)

    Multiply by P(B)P(B) and normalize. The normalizer, 0.002080.00208, is P(j,m)P(j,m) itself:

text
function ELIMINATION-ASK(X, e, network, order):
    factors ← [CPT of each node, restricted to the evidence e]
    for each hidden variable Y in order:            # everything except X and the evidence
        related ← the factors that mention Y
        g ← SUM-OUT(Y, POINTWISE-PRODUCT(related))   # one new factor, without Y
        factors ← (factors − related) + [g]
    return NORMALIZE(POINTWISE-PRODUCT(factors))    # a table over X alone

Before eliminating anything, drop every variable that is not an ancestor of XX or of the evidence: its CPTs sum to 1. For P(JohnCalls∣b)P(\text{JohnCalls}\mid b), MaryCalls is irrelevant.

Eliminating YY creates a factor over all the variables that currently share a factor with YY, so the cost is set by the largest factor the ordering ever creates. If it has w+1w+1 variables, VE takes O(n d w+1)\order{n\,d^{\,w+1}} time for variables with dd values; ww is the induced width of the ordering. The smallest induced width over all orderings is the treewidth of the moral graph (connect every pair of co-parents, then drop the directions). Finding the best ordering is NP-hard, but greedy rules such as min-fill (eliminate the variable whose elimination adds the fewest new edges) work well in practice.

StructureTreewidthExact inference
Chain, or an HMM unrolled over TT steps with SS states1O(TS2)\order{TS^2}
Polytree (no cycles even ignoring directions)largest number of parentslinear in the total size of the CPTs
k×kk\times k gridabout kkexponential in kk
Arbitrary DAGup to n−1n-1NP-hard in general
Think first A hidden cause HH has nn children X1,…,XnX_1,\dots,X_n, none observed, each with dd values. For the query P(X1)P(X_1), compare eliminating HH first with eliminating it last.

Eliminating HH first multiplies all n+1n+1 CPTs into one factor over X1,…,XnX_1,\dots,X_n before summing out HH: a table of dnd^n entries. Eliminating X2,…,XnX_2,\dots,X_n first is free, since each ∑xjP(xj∣h)=1\sum_{x_j}P(x_j\mid h)=1, and then ∑hP(h) P(x1∣h)\sum_hP(h)\,P(x_1\mid h) costs about d2d^2 operations. Same network, induced width n−1n-1 versus 1.

Approximate inference by sampling

When the treewidth is too large, estimate the posterior from samples instead. Each method below is consistent: its estimate converges to the exact posterior as the number of samples NN grows, with an error that shrinks like 1/N1/\sqrt N, though the constant in front can be enormous.

  • Prior (ancestral) sampling. Sample each variable from its CPT given its already-sampled parents, in topological order. Each run is an exact draw from the joint distribution.
  • Rejection sampling. Discard the samples that disagree with e\mathbf e and count among the rest. It is correct, but only a fraction P(e)P(\mathbf e) survives, and P(e)P(\mathbf e) typically shrinks exponentially with the number of evidence variables.
  • Likelihood weighting. Clamp the evidence variables to their observed values, sample only the others, and give each sample the weight w=∏jP(ej∣paj)w=\prod_jP(e_j\mid\mathrm{pa}_j): the probability of the evidence given its sampled parents.
  • Gibbs sampling. Start from any state that agrees with e\mathbf e, then repeatedly pick a non-evidence variable and resample it given its Markov blanket, P(xi∣mbi)∝P(xi∣pai)∏Yj∈ChiP(yj∣paj)P(x_i\mid\mathrm{mb}_i)\propto P(x_i\mid\mathrm{pa}_i)\prod_{Y_j\in\mathrm{Ch}_i}P(y_j\mid\mathrm{pa}_j). This is MCMC: a Markov chain whose stationary distribution is P(X∣e)P(\mathbf X\mid\mathbf e).
Predict before you look

You draw 10,000 samples from the alarm network by prior sampling, to estimate P(Burglary | JohnCalls, MaryCalls) by rejection. About how many samples agree with the evidence?

Show the answer

21

P(j,m)=0.00208P(j,m)=0.00208, the normalizer from the variable-elimination step, so about 21 samples survive, and about 6 of those contain a burglary. The estimate of 28.4% then rests on roughly six events, a relative error of order 1/6≈40%1/\sqrt6\approx40\%. Rejection sampling threw away 99.8% of its work.

python
import random

P_C = 0.5                                        # P(Cloudy)
P_S = {True: 0.1, False: 0.5}                    # P(Sprinkler | Cloudy)
P_R = {True: 0.8, False: 0.2}                    # P(Rain | Cloudy)
P_W = {(True, True): 0.99, (True, False): 0.9,   # P(WetGrass | Sprinkler, Rain)
       (False, True): 0.9, (False, False): 0.0}

def bern(p):
    return random.random() < p

def likelihood_weighting(n):
    """Estimate P(Rain = true | WetGrass = true)."""
    num = den = 0.0
    for _ in range(n):
        c = bern(P_C)                            # sample the unobserved nodes
        s = bern(P_S[c])                         # in topological order ...
        r = bern(P_R[c])
        w = P_W[(s, r)]                          # ... and weight by P(evidence | parents)
        num += w * r
        den += w
    return num / den

print(likelihood_weighting(100_000))             # exact: 0.4581 / 0.6471 = 0.708

Likelihood weighting on the sprinkler network. WetGrass is never sampled; it enters only through the weight. The exact answer, P(Rain∣WetGrass)=0.708P(\text{Rain}\mid\text{WetGrass})=0.708, comes from variable elimination (sum out Sprinkler, then Cloudy), and the estimate converges to it.

DerivationWhy the weights are right
  1. S(z)=∏i: Xi∉EP(zi∣pai),w(z)=∏j: Xj∈EP(ej∣paj)S(\mathbf z)=\prod_{i:\,X_i\notin\mathbf E}P(z_i\mid\mathrm{pa}_i),\qquad w(\mathbf z)=\prod_{j:\,X_j\in\mathbf E}P(e_j\mid\mathrm{pa}_j)

    A sample assigns values z\mathbf z to the non-evidence variables, drawn from their CPTs with the evidence clamped, and then receives a weight:

  2. S(z) w(z)=∏i=1nP(xi∣pai)∣(z,e)=P(z,e)S(\mathbf z)\,w(\mathbf z)=\prod_{i=1}^nP(x_i\mid\mathrm{pa}_i)\Big|_{(\mathbf z,\mathbf e)}=P(\mathbf z,\mathbf e)

    Together the two products contain every CPT exactly once, so their product is the joint probability:

  3. ∑kwk [x(k)=x]∑kwk →N→∞ P(x,e)P(e)=P(x∣e)\frac{\sum_kw_k\,[x^{(k)}=x]}{\sum_kw_k}\ \xrightarrow[N\to\infty]{}\ \frac{P(x,\mathbf e)}{P(\mathbf e)}=P(x\mid\mathbf e)

    Hence the weighted count of samples with X=xX=x converges to N P(x,e)N\,P(x,\mathbf e), and normalizing gives the posterior. Likelihood weighting is importance sampling, with the network itself (evidence clamped) as the proposal distribution.

Learning the numbers, and where to go deeper

So far the CPTs were given. With NN complete records, the log-likelihood of the CPT entries θx∣pa\theta_{x\mid\mathrm{pa}} splits into independent terms, one per node and parent configuration:

log⁡P(D∣θ)=∑i=1n ∑pai ∑xiN(xi,pai) log⁡θxi∣pai⟹θ^x∣pa=N(x,pa)N(pa)\log P(\data\mid\theta)=\sum_{i=1}^n\ \sum_{\mathrm{pa}_i}\ \sum_{x_i}N(x_i,\mathrm{pa}_i)\,\log\theta_{x_i\mid\mathrm{pa}_i}\quad\Longrightarrow\quad\hat\theta_{x\mid\mathrm{pa}}=\frac{N(x,\mathrm{pa})}{N(\mathrm{pa})}
N(x,pa)N(x,\mathrm{pa}) counts the records in which the node has value xx and its parents have values pa\mathrm{pa}. Each inner sum is a multinomial log-likelihood, maximized by relative frequencies, so the maximum-likelihood CPTs are found by counting, one table at a time.

Rare parent configurations give zero or tiny counts. A Dirichlet prior adds pseudo-counts, (N(x,pa)+α)/(N(pa)+αr)\big(N(x,\mathrm{pa})+\alpha\big)/\big(N(\mathrm{pa})+\alpha r\big) for a node with rr values, which is the additive smoothing of Bayesian Reasoning. With missing values or hidden variables the likelihood no longer decomposes, and the EM algorithm alternates between inference (expected counts, computed with the algorithms above) and counting.

The graph can be learned from data too, but only up to a limit. Two DAGs with the same skeleton and the same v-structures (X→Z←YX\to Z\leftarrow Y with XX and YY not adjacent) encode exactly the same independences (Verma & Pearl, 1990), so no amount of observational data can tell X→Y→ZX\to Y\to Z from X←Y←ZX\leftarrow Y\leftarrow Z or X←Y→ZX\leftarrow Y\to Z. Only the collider X→Y←ZX\to Y\leftarrow Z stands apart, which is why colliders anchor causal discovery (Causal Inference).

Key takeaways

  • A Bayesian network writes the joint distribution as ∏iP(xi∣pai)\prod_iP(x_i\mid\mathrm{pa}_i), with ∑i(ri−1)qi\sum_i(r_i-1)q_i numbers instead of ∏iri−1\prod_ir_i-1. The factorization is equivalent to the local Markov property: each node is independent of its non-descendants given its parents.
  • d-separation reads independence off the graph: chains and forks are blocked by observing the middle node, colliders are opened by observing them or a descendant. It is sound and complete for the independences that hold for every choice of CPTs.
  • Variable elimination sums out hidden variables one at a time; its cost is exponential only in the induced width of the ordering. Polytrees take linear time, but exact inference is NP-hard and #P-hard in general.
  • Rejection sampling keeps only a fraction P(e)P(\mathbf e) of its samples; likelihood weighting clamps the evidence and weights each sample by ∏jP(ej∣paj)\prod_jP(e_j\mid\mathrm{pa}_j); Gibbs sampling resamples each variable given its Markov blanket. With complete data, CPTs are learned by counting.

Check yourself

In the interactive lesson these are scored with your confidence, and what you miss comes back for review.

Question 1

A network has edges U→XU\to X, X→YX\to Y, Z→YZ\to Y, Y→WY\to W and V→WV\to W. What is the Markov blanket of YY?

  1. {X,Z}\{X,Z\}
  2. {X,Z,W}\{X,Z,W\}
  3. {X,Z,W,V}\{X,Z,W,V\}
  4. {U,X,Z,W,V}\{U,X,Z,W,V\}
Show the answer

C. {X,Z,W,V}\{X,Z,W,V\}

Parents X,ZX,Z, child WW, and the child's other parent VV. VV belongs because WW is a collider between YY and VV: once WW is in the conditioning set, VV carries information about YY. UU is screened off by XX.

Question 2

In the alarm network, which pair of variables is dependent given Alarm?

  1. JohnCalls and MaryCalls
  2. Burglary and JohnCalls
  3. Earthquake and MaryCalls
  4. Burglary and Earthquake
Show the answer

D. Burglary and Earthquake

Alarm is a collider on Burglary → Alarm ← Earthquake, so observing it opens the path: P(Burglary | alarm) = 37.4% falls to 0.33% once an earthquake is known. Every other pair is joined only through Alarm as the middle of a chain or fork, which observing Alarm blocks.

Question 3

The running time of variable elimination is exponential in which quantity?

  1. The number of variables in the network
  2. The number of evidence variables
  3. The size of the largest factor created, set by the induced width of the elimination ordering
  4. The number of edges in the network
Show the answer

C. The size of the largest factor created, set by the induced width of the elimination ordering

VE costs O(n d w+1)\order{n\,d^{\,w+1}}: linear in the number of variables and exponential only in the induced width ww. On a polytree, a good ordering keeps ww at the largest number of parents, so VE runs in linear time however large the network is.

Question 4

Exact inference is NP-hard in general. For which class of networks is it guaranteed to take time linear in the total size of the CPTs?

  1. Networks with at most three parents per node
  2. Polytrees
  3. Networks queried without any evidence
  4. Networks with at most 100 nodes
Show the answer

B. Polytrees

In a polytree, a good elimination ordering never builds a factor larger than the largest CPT, and Pearl's message passing computes every marginal in linear time. Loops are what make inference hard.

Question 5

In the sprinkler network with evidence WetGrass = true, likelihood weighting draws Cloudy = true, Sprinkler = false, Rain = true. What weight does this sample get?

  1. 0.9
  2. 0.99
  3. 0.8
  4. 0.36
Show the answer

A. 0.9

The weight is the probability of the clamped evidence given its sampled parents: P(WetGrass=true∣¬s,r)=0.9P(\text{WetGrass}=\text{true}\mid\neg s,r)=0.9. The sampled variables already appear in the right proportions, because they were drawn from their CPTs; weighting by their probabilities as well would count them twice.

Go deeper

Further reading

  • S. Russell & P. Norvig, Artificial Intelligence: A Modern Approach, 4th ed. (Pearson, 2020), chapter 13.
  • D. Koller & N. Friedman, Probabilistic Graphical Models: Principles and Techniques (MIT Press, 2009), chapters 3, 9 and 12.
  • J. Pearl, Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference (Morgan Kaufmann, 1988).
  • G. F. Cooper, "The computational complexity of probabilistic inference using Bayesian belief networks," Artificial Intelligence 42(2–3), 393–405 (1990).