Reasoning under uncertainty

Probability as a model of belief

Definition. When an agent cannot be certain, it assigns probabilities to the possible states of the world. A joint distribution $P(X_1, \dots, X_n)$ gives a probability to every combination of values; from it, any question can be answered:

• Marginalisation (summing out): $P(X) = \sum_y P(X, Y = y)$.
• Conditioning: $P(X \mid Y) = \dfrac{P(X, Y)}{P(Y)}$.
• Product rule: $P(X, Y) = P(X \mid Y)\,P(Y)$, and the chain rule $P(X_1, \dots, X_n) = \prod_i P(X_i \mid X_1, \dots, X_{i-1})$.
• Bayes' rule: $P(H \mid E) = \dfrac{P(E \mid H)\,P(H)}{P(E)}$.

The full joint table over $n$ Boolean variables has $2^n$ entries, which is too many. Independence assumptions make the model small.

Independence and conditional independence

• $X$ and $Y$ are independent if $P(X, Y) = P(X)P(Y)$, equivalently $P(X \mid Y) = P(X)$.
• $X$ and $Y$ are conditionally independent given $Z$ if $P(X, Y \mid Z) = P(X \mid Z)\,P(Y \mid Z)$, equivalently $P(X \mid Y, Z) = P(X \mid Z)$: once $Z$ is known, $Y$ tells us nothing more about $X$.

Exam point. Neither implies the other. Two symptoms of the same disease are usually dependent, but conditionally independent given the disease. Two independent causes of one effect become dependent once the effect is observed ("explaining away").

Bayesian networks

Definition. A Bayesian network is a directed acyclic graph: one node per random variable, an edge $X \to Y$ meaning $X$ directly influences $Y$, and for each node a conditional probability table (CPT) $P(X \mid \text{Parents}(X))$. The joint distribution factorises as

$P(X_1, \dots, X_n) = \prod_{i=1}^{n} P(X_i \mid \text{Parents}(X_i)).$

Size. A Boolean node with $k$ Boolean parents needs $2^k$ independent numbers (one $P(X = \text{true})$ per parent combination). A network is usually far smaller than the $2^n - 1$ numbers of the full joint.

Reading independence from the graph. Each node is conditionally independent of its non-descendants given its parents. For a path through a middle node $B$:

• Chain $A \to B \to C$: $A$ and $C$ are dependent, but independent given $B$.
• Fork $A \leftarrow B \to C$: dependent, but independent given $B$.
• Collider $A \to B \leftarrow C$: $A$ and $C$ are independent, but become dependent given $B$ (or given any descendant of $B$).

This is d-separation: two nodes are conditionally independent given evidence $E$ if every path between them is blocked.

Solved examples

Example 1: number of parameters. Network: $A \to C \leftarrow B$, $C \to D$, all Boolean. $A$ and $B$ have no parents: 1 number each. $C$ has 2 parents: $2^2 = 4$. $D$ has 1 parent: 2. Total 8, against $2^4 - 1 = 15$ for the full joint.

Example 2: a joint probability. Rain $R$ → WetGrass $W$, with $P(R) = 0.2$, $P(W \mid R) = 0.9$, $P(W \mid \neg R) = 0.1$. Then

$P(R, W) = 0.2 \times 0.9 = 0.18, \quad P(W) = 0.18 + 0.8 \times 0.1 = 0.26, \quad P(R \mid W) = \frac{0.18}{0.26} \approx 0.69 .$

Exact inference: variable elimination

Goal. Compute $P(\text{Query} \mid \text{evidence})$. The naive way sums the full joint over all hidden variables: exponential work.

Variable elimination writes the query as a sum of products of CPTs and pushes each sum inside as far as it goes, so it is computed once and reused:

1. Fix the evidence values in the CPTs.
2. Choose an order for the hidden variables.
3. For each hidden variable $Z$: multiply all factors that mention $Z$, then sum $Z$ out, giving a new factor.
4. Multiply the remaining factors and normalise.

The cost depends on the size of the largest factor created, which depends on the elimination order. On a polytree (no undirected cycles) inference is linear in the size of the network; in general it is NP-hard.

Solved example

Example 3. Chain $A \to B \to C$ with $P(a) = 0.5$, $P(b \mid a) = 0.8$, $P(b \mid \neg a) = 0.2$, $P(c \mid b) = 0.9$, $P(c \mid \neg b) = 0.3$. Find $P(c)$.

1. Eliminate $A$: $P(b) = 0.5 \times 0.8 + 0.5 \times 0.2 = 0.5$, so $P(\neg b) = 0.5$.
2. Eliminate $B$: $P(c) = 0.5 \times 0.9 + 0.5 \times 0.3 = 0.6$.

$P(c) = 0.6$. Summing $A$ out first left a small factor over $B$ alone, instead of a table over all of $A, B, C$.

Approximate inference by sampling

When exact inference is too costly, estimate probabilities from random samples drawn from the network.

• Prior (forward) sampling: sample each variable in topological order from its CPT given the sampled parents. The fraction of samples with $X = x$ estimates $P(x)$.
• Rejection sampling: generate prior samples and discard those that disagree with the evidence; estimate the query from the rest. Correct, but wasteful when the evidence is unlikely (most samples are rejected).
• Likelihood weighting: fix the evidence variables to their observed values and sample only the others; weight each sample by the product of $P(e \mid \text{parents})$ over the evidence variables. No samples are wasted.
• Gibbs sampling (MCMC): start from any state consistent with the evidence and repeatedly resample one non-evidence variable given its Markov blanket; after a burn-in period the states are samples from the posterior.

All of these become exact as the number of samples grows (they are consistent estimators).

Example 4: a likelihood weight. In Example 2 with evidence $W = \text{true}$: a sample with $R = \text{true}$ gets weight $P(W \mid R) = 0.9$; one with $R = \text{false}$ gets $0.1$.

Working with a joint table

Example 5. Weather $W$ is Sunny or Rain, and Traffic $T$ is Heavy or Light. The joint distribution is:

	Heavy	Light
Sunny	0.2	0.4
Rain	0.3	0.1

• Marginals: $P(\text{Heavy}) = 0.2 + 0.3 = 0.5$ and $P(\text{Rain}) = 0.3 + 0.1 = 0.4$.
• Conditional: $P(\text{Rain} \mid \text{Heavy}) = 0.3 / 0.5 = 0.6$.
• Independence? $P(\text{Rain})\,P(\text{Heavy}) = 0.4 \times 0.5 = 0.2$, but $P(\text{Rain}, \text{Heavy}) = 0.3$. Dependent: rain makes heavy traffic more likely.
• Normalisation trick: $P(W \mid \text{Heavy}) = \alpha\,\langle 0.2, 0.3\rangle = \langle 0.4, 0.6\rangle$, where $\alpha = 1/0.5$. We can compute the unnormalised numbers first and scale them so they sum to 1. The value $P(\text{evidence})$ is never needed separately.

Bayes' rule in more depth

Odds form. Posterior odds = prior odds × likelihood ratio:

$\frac{P(H \mid E)}{P(\neg H \mid E)} = \frac{P(H)}{P(\neg H)} \times \frac{P(E \mid H)}{P(E \mid \neg H)} .$