Bayesian Networks — Section 7: Probabilistic Reasoning

A Bayesian network is a directed acyclic graph where:

Each node is a random variable.
Each edge $X \to Y$ means $X$ directly influences $Y$ .
Each node has a conditional probability distribution $P(X | \text{parents}(X))$ .

The joint distribution factorizes as:

P(X_1, \dots, X_n) = \prod_i P(X_i | \text{parents}(X_i))

Why this is a big deal

A joint distribution over $n$ binary variables has $2^n - 1$ free parameters. A Bayesian network can describe the same distribution using only $O(n \cdot 2^k)$ parameters where $k$ is the maximum number of parents. For graphs with bounded fanin, this is an exponential reduction.

Conditional independence

Reading the graph tells you which variables are conditionally independent. d-separation is the formal rule: $X$ and $Y$ are conditionally independent given $Z$ if every path between them is blocked by $Z$ (where "blocked" follows specific rules for chain, fork, and collider structures).

Bayes nets aren't just storage — they encode conditional independence assumptions that have semantic meaning.

Canonical example

The "alarm" network: a burglary or earthquake can trigger your alarm; if the alarm goes off, neighbors John and Mary may call. The graph is:

Burglary, Earthquake → Alarm
Alarm → JohnCalls, MaryCalls

If you observe JohnCalls and MaryCalls, you can infer (probabilistically) about the alarm, which tells you about burglary and earthquake. The math falls out from Bayes' rule on the factored distribution.

Inference tasks

Marginal: $P(X)$ — total probability of $X = x$ .
Conditional: $P(X | E)$ given evidence $E$ .
Most likely explanation (MAP): $\arg\max_X P(X | E)$ .
Most probable configuration: $\arg\max_{X,Y,...} P(X, Y, ... | E)$ .

Complexity

Exact inference in general Bayes nets is NP-hard. Polynomial in the size of the network only for tree-shaped graphs. For practical graphs, you use either:

Variable elimination / junction tree algorithms (exact when tree-width is small).
Sampling (next lesson).

Modern relevance

Bayes nets dominated structured probabilistic reasoning from the 1990s to 2010s. Deep learning ate a lot of that turf, but Bayes nets remain crucial for:

Decision support (medical diagnosis, fault detection).
Causal inference (Pearl's causality machinery).
Cases where data is scarce and structure can be elicited from experts.