AI · Uncertain knowledge and reasoning

13 · Probabilistic Reasoning

Bayesian networks factor a joint distribution into local conditional probabilities. Evidence can then update beliefs through exact or approximate inference.

A graphical model for uncertainty

13.1 Representing Knowledge in an Uncertain Domain

Choose random variables and dependencies that capture the structure of the domain. A Bayesian network pairs a directed acyclic graph with a conditional probability table for each variable.

13.2 The Semantics of Bayesian Networks

The graph encodes conditional independence: each variable is independent of its non-descendants given its parents. The joint probability is the product of all local conditionals.

13.3 Exact Inference in Bayesian Networks

Exact inference sums over hidden variables and normalizes. Variable elimination avoids repeated work by combining and summing factors in a chosen order.

13.4 Approximate Inference for Bayesian Networks

Sampling methods estimate answers when exact computation is too expensive; their estimates can improve with more representative samples.

13.5 Causal Networks

A causal interpretation supports interventions, written do(X=x), which set a variable externally rather than merely observing it. This differs from conditioning on X=x.

Key terms and an enumeration trace

A Bayesian network is a DAG plus one conditional probability table (CPT) per variable; each variable is independent of its non-descendants given its parents. The factorization is P(x₁,…,xₙ)=∏ᵢP(xᵢ|Parents(Xᵢ)). Exact inference sums probabilities of assignments consistent with a query and evidence, then normalizes. Intervention changes a causal mechanism; observation conditions on an outcome.

For this demo’s query P(Rain|Wet), enumerate all four (Rain, Sprinkler) assignments. Wet-and-rain mass is 0.2×0.1×0.99 + 0.2×0.9×0.90 = 0.1818. Total wet evidence also includes the two no-rain cases, giving 0.253; divide to get about 71.9%. Changing evidence to dry replaces each wet likelihood by its complement and recomputes both sums.

Sampling approximations trade exactness for scalable estimates. Variable elimination can reuse intermediate factors, but exact inference remains exponential in the network’s worst-case induced width; graph structure—not just variable count—matters.

Exact enumeration

Rain, sprinklers, and wet grass

The graph factors P(R,S,W)=P(R)P(S)P(W|R,S). The displayed probabilities are illustrative; all hidden assignments are summed exactly.

Evidence observed

Posterior belief

Enumeration complexity

Let N be the number of binary network variables. Full-joint enumeration checks 2^N assignments; evaluating the network factorization takes O(N) per assignment. General time: O(N·2^N). Auxiliary space: O(N) to hold or recurse over one assignment (this implementation streams the two loop variables and uses O(1) temporary scalars). For this exact three-node network, the loops inspect four parent assignments, so both runtime and working memory are O(1).

The posterior bar and text are a fixed-size visualization (O(1) UI memory). These bounds are for exact enumeration with finite binary variables and nonzero evidence probability; they are not sampling or variable-elimination bounds.