Quantifying Uncertainty

The logical agents of the previous module believe each sentence to be true, false, or unknown, and they act by deducing what must follow. That works when the rules hold without exception. It fails when the rules have exceptions — which, outside of puzzles and theorem-proving, is nearly always.

Consider a dentist trying to diagnose a patient by the rules of propositional logic. The obvious rule is

It is wrong: not every toothache is a cavity — there is gum disease, an abscess, impaction, and a long tail of rarer causes. So we weaken it to a disjunction, $Toothache\Rightarrow Cavity\vee GumProblem\vee Abscess\vee \dots$, and now the right-hand side is an unbounded list we can never finish. Turning the implication around into a causal rule, $Cavity\Rightarrow Toothache$, is no better: not every cavity hurts. To make that true we would have to load the left side with every precondition a cavity needs in order to cause pain — exposed nerve, no anaesthetic, and so on — again without end.¹

Why logic fails: the qualification problem

To state any rule about the physical world so that it is exceptionless, you must attach every qualifying condition under which it could fail — and there are always more conditions than you can list. This is the qualification problem, and it has no purely logical solution.

Russell and Norvig identify three sources of the problem.²

The connection between a toothache and a cavity is not a logical consequence in either direction. That is typical not just of medicine but of law, business, automobile repair, and most domains where an agent has to act on incomplete knowledge. A logical agent, forced to answer true / false / unknown, can only say unknown, which is useless for choosing an action. What the agent can honestly supply is a degree of belief: a number between 0 and 1 that grades how strongly the evidence supports the proposition.

The ontological commitment is the same as logic's — the world is made of facts that either hold or not. What changes is the epistemological commitment: where a logical agent believes each fact true, false, or has no opinion, a probabilistic agent holds a numerical degree of belief in $[0,1]$, with $0$ for certainly false and $1$ for certainly true.³ Probability provides a way of summarizing the uncertainty that comes from laziness and ignorance, and that summary is precisely what a rational agent needs in order to compare plans that are not guaranteed and still choose one.

A subtle point: at the time of diagnosis there is no uncertainty in the actual world — the patient either has a cavity or does not. The probability $0.8$ is not a statement about the tooth; it is a statement about the agent's knowledge state. That is why probabilities are written relative to evidence. Before any evidence we have the prior $P(Cavity)$; after observing the toothache we have the posterior $P(Cavity\mid Toothache)$; if we later learn of gum disease the number moves again. None of these contradict each other — each is a separate assertion about a different state of knowledge.

Basic notation

Before we can compute with degrees of belief, we need a language to write them in. The notation borrows almost everything from familiar tools: the true/false propositions of logic, and the variables-with-values of constraint satisfaction. This section fixes the vocabulary — random variables, sample spaces, the axioms — used by the arithmetic in the rest of the lesson.

Random variables are the building blocks; by convention their names begin with an uppercase letter. Each has a domain, the set of values it can take. A Boolean variable like $Cavity$ has domain $\{true,false\}$; $Weather$ might have domain $\{sunny,rain,cloudy,snow\}$; a variable can even be continuous. We abbreviate the proposition $Cavity=true$ as $cavity$ and $Cavity=false$ as $\neg cavity$.

The sample space and the axioms

Probabilistic assertions are about possible worlds. The set of all possible worlds is the sample space $\Omega$; its elements $\omega$ are individual possible worlds, and they are mutually exclusive and exhaustive — exactly one $\omega$ is the actual case. A fully specified probability model assigns a number $P(\omega )$ to each world, subject to the basic axioms.

An event (or proposition) is a set of possible worlds — those in which the proposition holds — and its probability is the total probability of that set. Everything else about probability follows from these axioms. The relationship between a proposition and its negation drops out immediately,

as does the inclusion–exclusion principle for a disjunction, obtained by noting that summing the $a$-worlds and the $b$-worlds double-counts their overlap:

The axioms are not an arbitrary convention. De Finetti's theorem shows that any agent whose degrees of belief violate these axioms is exposed to a Dutch book — a set of bets, each of which it accepts as fair, that together guarantee it loses money no matter how the world turns out. Rational belief has to obey the axioms of probability, on pain of certain loss.⁴

Prior, conditional, and joint probability

Probabilities like $P(Cavity)$ that refer to a degree of belief in the absence of any other information are prior or unconditional probabilities. Once we have observed some evidence we want the conditional or posterior probability, written with a vertical bar for given:

The definition makes sense from the axioms: observing $b$ rules out every world where $b$ is false, leaving a set of total probability $P(b)$; within that set the $a$-worlds are the ones satisfying $a\wedge b$, a fraction $P(a\wedge b)/P(b)$. Multiplying through gives the product rule, often easier to remember: for $a\wedge b$ to hold, $b$ must hold and $a$ must hold given $b$.

When a variable has more than two values we often want the whole vector of probabilities at once. Writing $\mathbf{P}(Weather)$ (bold $\mathbf{P}$) denotes the distribution $⟨P(sunny),P(rain),P(cloudy),P(snow)⟩$ over a fixed ordering of the domain — a probability distribution. For several variables the joint probability distribution $\mathbf{P}(X,Y)$ tabulates the probability of every combination of their values. The joint over all the variables in the domain is the full joint distribution, and it is the object everything in this lesson is built on.

Inference from the full joint distribution

Once the full joint distribution is written down, answering any probability question is addition: the joint is a lookup table, and each query sums the entries that match. Probabilistic inference — computing the posterior of a query given evidence — reduces to arithmetic. The distribution is the knowledge base; every answer is a sum of its entries.

Take the dentistry domain with three Boolean variables: $Toothache$, $Cavity$, and $Catch$ (the steel probe catches in the tooth). The full joint is a $2\times 2\times 2$ table of eight numbers that sum to $1$.

Marginalization (or summing out) extracts the distribution over a subset of variables by adding over the values of the rest. Summing the whole $cavity$ row of the table gives the unconditional probability of a cavity:

In general, for disjoint sets of variables $\mathbf{Y}$ and $\mathbf{Z}$,

where the sum runs over all value-combinations of $\mathbf{Z}$. A variant using the product rule, called conditioning, marginalizes with conditional probabilities instead: $\mathbf{P}(\mathbf{Y})={\sum }_{\mathbf{z}}\mathbf{P}(\mathbf{Y}\mid \mathbf{z})P(\mathbf{z})$.

For a conditional query we use the definition of conditional probability, then read the two joint terms off the table. The probability of a cavity given a toothache restricts attention to the four $toothache$ cells:

Computing the complementary query the same way gives $P(\neg cavity\mid toothache)=0.4$, and the two sum to $1$ as they must. Notice the denominator $P(toothache)$ was the same in both. This is the constant that forces the posterior distribution to sum to $1$, so we can treat it as a normalization constant $\alpha =1/P(toothache)$ and defer it. Writing the query distribution over $Cavity$ in one line,

We never needed the value of $P(toothache)$. We summed the joint entries for $cavity$ and $\neg cavity$, got $0.12$ and $0.08$ — the correct relative proportions — then divided by their total to normalize. This is the general inference-by-enumeration procedure. Let $X$ be the query variable, $\mathbf{e}$ the observed evidence, and $\mathbf{Y}$ the remaining unobserved (hidden) variables; then

This is correct and completely general, but it does not scale. For a domain of $n$ Boolean variables the full joint has $2^n$ entries, so the table itself is of size $O(2^n)$ and each query sums over $O(2^n)$ of them. With $n$ past a hundred — routine in real problems — the tabular full joint is not a practical tool. It is the theoretical foundation on which better methods are built, just as truth tables underlie DPLL. The rest of the lesson is about the structure that makes those better methods possible.

Independence

Inference-by-enumeration is correct but hopeless at scale, because the joint table is exponentially large. The rest of the lesson looks for structure that lets us shrink that table. The simplest kind of structure is when two variables have nothing to do with each other — knowing one tells us nothing about the other. That is independence.

Expand the dentistry domain with a fourth variable, $Weather$, and the joint blows up to $2\times 2\times 2\times 4=32$ entries. But the weather has nothing to do with anyone's teeth. Any sensible model asserts

and likewise for every combination — knowing the dental facts tells us nothing new about the sky. When this holds we say $Weather$ and the dental variables are independent, written $Weather\perp \{Toothache,Catch,Cavity\}$.

Independence lets the $32$-entry table be reconstructed from an $8$-entry table (the dental joint) and a $4$-entry table (the weather), because $\mathbf{P}(Toothache,Catch,Cavity,Weather)=\mathbf{P}(Toothache,Catch,Cavity)\mathbf{P}(Weather)$. The saving compounds: $n$ independent coin flips have a joint of $2^n$ entries, yet the whole thing collapses to a product of $n$ tiny single-variable distributions.

Independence dramatically shrinks the representation, but clean separation of whole variable sets is rare: any connection, however indirect, breaks it. The toothache–weather split is the easy case. What we usually need is a subtler, conditional version — variables that are dependent in general but come apart once some third fact is known. Getting there needs one more tool: Bayes' rule.

This continues in Bayes' Rule and Naive Bayes, which inverts causal models into diagnostic ones and shows how conditional independence lets evidence combine without an exponential blowup.