Bayesian Networks: Reasoning Under Uncertainty

Real agents never have complete certainty. Symptoms suggest diseases but do not prove them; sensors are noisy. Probability theory is the correct calculus for this situation, but a naïve joint distribution over $n$ binary variables needs $2^n - 1$ numbers. Bayesian networks, introduced by Judea Pearl in the 1980s, solve this by exploiting conditional independence. Pearl received the Turing Award for this work.

Definition#

A Bayesian network (BN) is a directed acyclic graph (DAG) in which:

• each node is a random variable $X_i$;
• each node has a conditional probability table (CPT) $P(X_i \mid \text{Parents}(X_i))$.

The network represents the joint distribution as a product of local factors:

If each variable has at most $k$ parents, the network needs $O(n\,2^k)$ numbers instead of $O(2^n)$ — an exponential saving.

The classic burglary example#

Pearl's example: your house has an alarm that can be triggered by a Burglary (B) or an Earthquake (E). Two neighbours, John (J) and Mary (M), may call you when they hear the alarm (A).

The structure is B → A ← E, A → J, A → M. Plausible CPTs:

Ten numbers specify a joint distribution over 32 outcomes.

Conditional independence and d-separation#

The graph encodes independence assumptions. Each node is conditionally independent of its non-descendants given its parents. More generally, d-separation tells us when two sets of variables are independent given evidence. Three patterns matter:

1. Chain $X \to Y \to Z$: $X$ and $Z$ are dependent, but independent given $Y$.
2. Fork $X \leftarrow Y \to Z$: common cause; independent given $Y$.
3. Collider $X \to Y \leftarrow Z$: $X$ and $Z$ are independent, but become dependent once $Y$ (or a descendant) is observed.

Exact inference by enumeration#

Query: what is $P(B \mid j, m)$, the probability of a burglary given both neighbours call? We sum out the hidden variables $E$ and $A$:

from itertools import product

P_B, P_E = 0.001, 0.002
P_A = {(True, True): .95, (True, False): .94, (False, True): .29, (False, False): .001}
P_J = {True: .90, False: .05}
P_M = {True: .70, False: .01}

def pr(p, v):  # probability that a Boolean variable with P(true)=p has value v
    return p if v else 1 - p

def joint(b, e, a, j, m):
    return pr(P_B, b) * pr(P_E, e) * pr(P_A[(b, e)], a) * pr(P_J[a], j) * pr(P_M[a], m)

unnorm = {b: sum(joint(b, e, a, True, True) for e, a in product([True, False], repeat=2))
          for b in [True, False]}
z = sum(unnorm.values())
print({b: round(v / z, 4) for b, v in unnorm.items()})   # {True: 0.2842, False: 0.7158}

Even when both neighbours call, the probability of a burglary is only about 28%, because burglaries are rare and the neighbours are unreliable. This is base-rate reasoning, and humans are notoriously bad at it.

Variable elimination#

Enumeration recomputes the same products many times. Variable elimination stores intermediate results as factors and sums out variables one at a time, like dynamic programming. Its cost depends on the elimination order; finding the best order is NP-hard, but good heuristics exist. For polytrees (singly connected networks) inference is linear in network size; in general, exact inference is #P-hard.

Approximate inference by sampling#

For large networks we sample:

• Prior (direct) sampling — sample each variable in topological order from its CPT.
• Rejection sampling — discard samples inconsistent with the evidence (wasteful when evidence is unlikely).
• Likelihood weighting — fix evidence variables and weight each sample by the likelihood of the evidence.
• Gibbs sampling (MCMC) — repeatedly resample one non-evidence variable given its Markov blanket (parents, children and children's parents).

Learning Bayesian networks#

Parameters (CPTs) can be learned from data by counting (maximum likelihood) or with Bayesian priors (e.g. adding pseudo-counts). Learning the structure is harder — a search over DAGs guided by a score such as BIC. Structure learning connects to the field of causal inference, where arrows are interpreted as causes and we ask what happens under interventions — another of Pearl's major contributions.