--- title: Quantifying Uncertainty module: Uncertainty moduleNumber: 4 lessonNumber: 1 order: 401 summary: > Logic breaks down in any domain where the rules have exceptions you cannot enumerate — the qualification problem. Probability replaces truth values with degrees of belief that obey Kolmogorov's axioms, and the full joint distribution becomes a knowledge base from which any query is answered by summing entries: marginalization, conditioning, and normalization. Independence factors that joint into smaller pieces — the first step toward a calculus of rational belief that an agent can actually compute with. topics: [Uncertainty] sources: - book: AIMA ref: "Ch. 13 — Quantifying Uncertainty; §13.1 Acting under Uncertainty; §13.2 Basic Probability Notation" - book: AIMA ref: "§13.3 Inference Using Full Joint Distributions; §13.4 Independence" --- The [logical agents](/artificial-intelligence/logic-and-planning/propositional-logic) 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 $$ Toothache \;\Rightarrow\; Cavity. $$ 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 \lor GumProblem \lor Abscess \lor \ldots$, 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.[^aima-qual] ## 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.[^aima-three] > **Definition (The three sources of uncertainty).** _Laziness:_ listing the > complete set of antecedents or consequents for an exceptionless rule is too much > work, and the resulting rules are too unwieldy to use. _Theoretical ignorance:_ > the science of the domain may have no complete theory. _Practical ignorance:_ > even given a complete theory, we may lack the specific facts about a case, > because not all the tests have been or can be run. 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. $$ % caption: The qualification problem. A crisp rule needs an unbounded list of % preconditions to be exceptionless; probability instead attaches one number, a % degree of belief, and sidesteps the enumeration entirely. \begin{tikzpicture}[>=stealth, font=\small, box/.style={draw, minimum width=34mm, minimum height=12mm, align=center, font=\footnotesize}, qual/.style={draw, black, minimum width=27mm, minimum height=8mm, align=center, font=\scriptsize}] \definecolor{acc}{HTML}{2348F2} \node[box] (rule) at (0,0) {rule: Toothache $\Rightarrow$\\Cavity}; \node[qual] (q1) at (-3.0,-2.2) {unless gum disease}; \node[qual] (q2) at (0,-2.2) {unless abscess}; \node[qual] (q3) at (3.0,-2.2) {unless ... (no end)}; \draw[->, black] (rule) -- (q1); \draw[->, black] (rule) -- (q2); \draw[->, black] (rule) -- (q3); \node[box, draw=acc, text=acc, thick] (prob) at (8.4,0) {P(Cavity given\\Toothache) = 0.8}; \node[font=\scriptsize, text=acc, align=center, anchor=north] at (8.4,-1.05) {one number,\\no list to f\/inish}; \draw[->, acc, thick] (2.1,0) -- (5.9,0) node[midway, above, font=\scriptsize, text=black] {summarize}; \end{tikzpicture} $$ 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.[^aima-degree] 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 $\lnot cavity$. > **Definition (Random variable).** A variable $X$ with a domain of mutually > exclusive, exhaustive values it may take. An assignment $X = x_i$ (or its > shorthand) is a proposition; the connectives of propositional logic combine such > propositions, e.g. $P(cavity \mid \lnot toothache \land teen) = 0.1$. ### 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. > **Definition (Kolmogorov's axioms).** Every possible world has a probability > between $0$ and $1$, and the probabilities of the full set of worlds sum to $1$: > $\;0 \le P(\omega) \le 1$ for every $\omega$, and $\sum_{\omega \in \Omega} > P(\omega) = 1$. The probability of a proposition $\phi$ is the sum over the > worlds in which it holds: $\;P(\phi) = \sum_{\omega \models \phi} P(\omega)$. 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, $$ P(\lnot a) \;=\; \sum_{\omega \models \lnot a} P(\omega) \;=\; \sum_{\omega \in \Omega} P(\omega) - \sum_{\omega \models a} P(\omega) \;=\; 1 - P(a), $$ 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: $$ P(a \lor b) \;=\; P(a) + P(b) - P(a \land b). $$ $$ % caption: The sample space as an event space. Each proposition is the set of % worlds where it holds; $P(a \lor b)$ counts the union, so the overlap $P(a % \land b)$ must be subtracted once — the inclusion-exclusion principle. \begin{tikzpicture}[>=stealth, font=\small] \definecolor{acc}{HTML}{2348F2} \definecolor{red}{HTML}{C0392B} % the whole sample space \draw[black] (-0.3,-0.3) rectangle (7.5,4.0); \node[anchor=north east, font=\footnotesize, text=black] at (7.4,3.9) {sample space}; % event a \fill[acc!12] (2.4,1.85) ellipse (2.1 and 1.45); \draw[acc, thick] (2.4,1.85) ellipse (2.1 and 1.45); \node[text=acc, font=\footnotesize] at (1.35,1.85) {event a}; % event b \fill[red!10] (4.7,1.85) ellipse (2.1 and 1.45); \draw[red, thick] (4.7,1.85) ellipse (2.1 and 1.45); \node[text=red, font=\footnotesize] at (5.75,1.85) {event b}; % overlap label \node[font=\scriptsize, text=black] at (3.55,1.85) {a and b}; % a couple of worlds as dots \fill[black] (0.9,0.4) circle (1.4pt); \node[font=\scriptsize, anchor=west, text=black] at (1.05,0.4) {a world w}; \end{tikzpicture} $$ 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.[^aima-definetti] ### 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": $$ P(a \mid b) \;=\; \frac{P(a \land b)}{P(b)}, \qquad P(b) > 0. $$ 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 \land b$, a fraction $P(a \land b) / P(b)$. Multiplying through gives the **product rule**, often easier to remember: for $a \land b$ to hold, $b$ must hold and $a$ must hold given $b$. > **Algorithm (Product rule).** $\;P(a \land b) = P(a \mid b)\,P(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 $\langle P(sunny), P(rain), P(cloudy), P(snow)\rangle$ 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. > **Definition (Full joint distribution).** The distribution $\mathbf{P}(X_1, > \ldots, X_n)$ over all combinations of values of all the random variables in the > domain. Because a possible world is an assignment to every variable, and every > proposition's probability is a sum over the worlds where it holds, the full joint > completely determines the probability model: it answers, in principle, every > query about the domain. ## 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$. $$ % caption: The full joint distribution over $Toothache$, $Cavity$, $Catch$. The % eight cells sum to 1; every query is a sum of a subset of them. Adding a row % marginalizes out the other variables (the $cavity$ row totals $0.2$); a % conditional restricts to the columns consistent with the evidence. \begin{tikzpicture}[>=stealth, font=\footnotesize] \definecolor{acc}{HTML}{2348F2} % column headers \node[font=\scriptsize, text=black] at (2.55,3.15) {toothache}; \node[font=\scriptsize, text=black] at (6.05,3.15) {no toothache}; \node at (1.6,2.55) {catch}; \node at (3.5,2.55) {no catch}; \node at (5.1,2.55) {catch}; \node at (7.0,2.55) {no catch}; % row headers \node[anchor=east] at (0.5,1.7) {cavity}; \node[anchor=east] at (0.5,0.7) {no cavity}; % grid \draw[black] (0.7,0.2) rectangle (7.9,2.2); \draw[black] (0.7,1.2) -- (7.9,1.2); \foreach \x in {2.6,4.55,6.5} \draw[black] (\x,0.2) -- (\x,2.2); % cavity row (highlighted) \node[text=acc] at (1.6,1.7) {0.108}; \node[text=acc] at (3.5,1.7) {0.012}; \node[text=acc] at (5.1,1.7) {0.072}; \node[text=acc] at (7.0,1.7) {0.008}; % no-cavity row \node at (1.6,0.7) {0.016}; \node at (3.5,0.7) {0.064}; \node at (5.1,0.7) {0.144}; \node at (7.0,0.7) {0.576}; % marginal arrow \draw[->, acc, thick] (8.2,1.7) -- (9.1,1.7); \node[text=acc, anchor=west, font=\scriptsize] at (9.15,1.7) {sum = P(cavity) = 0.2}; \end{tikzpicture} $$ **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: $$ P(cavity) \;=\; 0.108 + 0.012 + 0.072 + 0.008 \;=\; 0.2. $$ In general, for disjoint sets of variables $\mathbf{Y}$ and $\mathbf{Z}$, $$ \mathbf{P}(\mathbf{Y}) \;=\; \sum_{\mathbf{z}} \mathbf{P}(\mathbf{Y}, \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: $$ P(cavity \mid toothache) \;=\; \frac{P(cavity \land toothache)}{P(toothache)} \;=\; \frac{0.108 + 0.012}{0.108 + 0.012 + 0.016 + 0.064} \;=\; 0.6. $$ Computing the complementary query the same way gives $P(\lnot 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, $$ \mathbf{P}(Cavity \mid toothache) \;=\; \alpha\, \mathbf{P}(Cavity, toothache) \;=\; \alpha\,\langle 0.12, 0.08\rangle \;=\; \langle 0.6, 0.4\rangle. $$ We never needed the value of $P(toothache)$. We summed the joint entries for $cavity$ and $\lnot 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 $$ \mathbf{P}(X \mid \mathbf{e}) \;=\; \alpha\, \mathbf{P}(X, \mathbf{e}) \;=\; \alpha \sum_{\mathbf{y}} \mathbf{P}(X, \mathbf{e}, \mathbf{y}). $$ > **Algorithm (Inference by enumeration).** To answer $\mathbf{P}(X \mid > \mathbf{e})$ from the full joint: for each value $x$ of $X$, sum the joint entries > matching $x$ and $\mathbf{e}$ over all values $\mathbf{y}$ of the hidden > variables; collect these into a vector and normalize so it sums to $1$. 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 $$ P(cloudy \mid toothache, catch, cavity) \;=\; P(cloudy), $$ 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\}$. > **Definition (Independence).** Variables $X$ and $Y$ are independent when > knowledge of one leaves belief in the other unchanged. Equivalently: > $\;\mathbf{P}(X \mid Y) = \mathbf{P}(X)$, or $\mathbf{P}(Y \mid X) = > \mathbf{P}(Y)$, or $\mathbf{P}(X, Y) = \mathbf{P}(X)\,\mathbf{P}(Y)$. The three > forms are equivalent, and the last shows the consequence: the joint > **factors** into a product. 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. $$ % caption: Independence factors a large joint into separate joints on disjoint % subsets. Dental variables and weather share no arrow, so the 32-entry joint is % the product of an 8-entry dental table and a 4-entry weather table. \begin{tikzpicture}[>=stealth, font=\footnotesize] \definecolor{acc}{HTML}{2348F2} % the big joint \node[draw, thick, ellipse, minimum width=52mm, minimum height=17mm, align=center] (big) at (0,2.4) {Cavity Toothache Catch Weather\\(32 entries)}; % decomposed pieces \node[draw, acc, thick, ellipse, minimum width=40mm, minimum height=15mm, align=center] (dental) at (-2.6,-0.6) {Cavity Toothache\\Catch (8)}; \node[draw, thick, ellipse, minimum width=22mm, minimum height=13mm, align=center] (wx) at (2.7,-0.6) {Weather\\(4)}; \draw[->, black, thick] (big) -- (dental); \draw[->, black, thick] (big) -- (wx); \node[font=\scriptsize, text=black] at (0.05,1.05) {factors into}; \end{tikzpicture} $$ 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](/artificial-intelligence/uncertainty/bayes-rule-and-naive-bayes), which inverts causal models into diagnostic ones and shows how conditional independence lets evidence combine without an exponential blowup. [^aima-qual]: **Russell & Norvig**, _Artificial Intelligence: A Modern Approach_ (3rd ed.), §13.1.1 — Summarizing uncertainty: the toothache/cavity example and why neither $Toothache \Rightarrow Cavity$ nor $Cavity \Rightarrow Toothache$ can be made exceptionless in propositional logic. [^aima-three]: **Russell & Norvig**, §13.1.1 — the three reasons logic fails for judgmental domains: laziness, theoretical ignorance, and practical ignorance. [^aima-degree]: **Russell & Norvig**, §13.1 — degree of belief and probability theory; the shared ontological but differing epistemological commitments of logic and probability, and probability as a summary of laziness and ignorance. [^aima-definetti]: **Russell & Norvig**, §13.2.3 — Probability axioms and their reasonableness: Kolmogorov's axioms and de Finetti's argument that beliefs violating them admit a guaranteed-loss combination of bets.