Bayes' Rule and Naive Bayes

This builds on Quantifying Uncertainty, which laid out degrees of belief, the full joint distribution, and plain independence. There we left off needing a subtler tool: a way to turn a model of how causes produce effects into an answer about which cause is present, and a way to fold in several observations at once without the joint distribution exploding. Both come from one equation and one refinement of independence.

Bayes' rule

Write the product rule both ways — $P(a\wedge b)=P(a\mid b)P(b)$ and $P(a\wedge b)=P(b\mid a)P(a)$ — set the right-hand sides equal, and divide. The result is Bayes' rule.

On its face Bayes' rule computes one conditional from three other numbers, which looks like a step backwards. It matters in a specific, common situation: we perceive an effect and want to infer its unknown cause. Rewriting the rule with those roles,

The quantity $P(\text{effect}\mid \text{cause})$ is causal knowledge — how the world works, how a cause produces its symptoms. The quantity we want, $P(\text{cause}\mid \text{effect})$, is diagnostic — reasoning from symptom back to cause. Bayes' rule turns the first into the second.

For example, take the medical version. Meningitis ($m$) causes a stiff neck ($s$) about $70\%$ of the time, so $P(s\mid m)=0.7$ is the doctor's causal knowledge. The priors are $P(m)=1/50000$ and $P(s)=0.01$. Then

Fewer than $1$ in $700$ stiff-necked patients has meningitis — even though meningitis strongly indicates a stiff neck, the disease stays rare because its prior is tiny compared with the prior on stiff necks. The prior matters: dropping it (a common intuitive error) inflates the estimate by orders of magnitude.

Why prefer Bayes' rule to just storing the diagnostic number $P(m\mid s)$ directly? Because causal knowledge is more stable than diagnostic knowledge. If an epidemic strikes, the prior $P(m)$ jumps, and with it the correct posterior $P(m\mid s)$. A doctor who memorized $P(m\mid s)$ from pre-epidemic statistics has no way to update it. A doctor who computes it from $P(s\mid m)$, $P(m)$, and $P(s)$ sees at once that it should rise in step with $P(m)$ — because the causal fact $P(s\mid m)$, how meningitis affects the body, is unchanged by the epidemic.¹

If we do not have $P(s)$ we can avoid it by computing the posterior for both values of the query and normalizing, exactly as in the joint-table example:

A worked medical test: the base-rate trap

The meningitis numbers were handed to us. In practice the causal quantities come from a diagnostic test described by two rates, and the arithmetic exposes a common error. Suppose a disease $D$ has prevalence$P(d)=0.001$ — one person in a thousand has it. A test $T$ for it has sensitivity (true-positive rate) $P(t\mid d)=0.99$: it catches $99\%$ of sick people. Its specificity (true-negative rate) is $P(\neg t\mid \neg d)=0.99$, so its false-positive rate is $P(t\mid \neg d)=0.01$. You test positive. What is the probability you are sick, $P(d\mid t)$?

The reflex answer is about $99\%$ — the test is $99\%$ accurate. It is wrong by almost two orders of magnitude, and Bayes' rule shows why. Compute the two unnormalized terms:

Now normalize over the two values of $D$; their sum is $P(t)$:

A positive result raises the probability of disease from $0.1\%$ to about $9\%$ — higher than the prior, but nowhere near $99\%$. The reason is entirely in the base rate. The disease is so rare that the $0.01$ false-positive rate, applied to the huge healthy majority, produces about ten times as many false alarms as there are true positives. Reasoning with a concrete population makes this unmistakable: out of $100,000$ people, $100$ are sick and $99$ of them test positive; of the $99,900$ healthy, $1\%$ — about $999$ — also test positive. So $99+999=1098$ people test positive, and only $99$ of them are sick: $99/1098\approx 9\%$, matching the Bayes computation exactly.

This is the general shape of screening: a test can be excellent (high sensitivity and specificity) and a positive result still mean the patient probably does not have the disease, whenever the disease is rare enough. Dropping the prior — treating $P(d\mid t)$ as if it equalled the sensitivity $P(t\mid d)$ — is the base-rate fallacy, the very mistake Bayes' rule forces you not to make: the prior $P(d)$ appears explicitly in the numerator and again inside the normalizer. The same computation governs spam filters, fraud alarms, and any rare-event detector: the rarer the event, the more the base rate dominates the test.

Combining evidence: conditional independence and naive Bayes

Bayes' rule handles one piece of evidence cleanly. But real diagnosis piles up symptoms — a toothache and a catch and an X-ray shadow — and the naive way of folding them all in brings back the exponential table we were trying to escape. The fix is the conditional independence promised at the end of the previous lesson: once the common cause is fixed, the symptoms stop informing each other, and the evidence combines by simple multiplication. Consider a dentist who observes both a toothache and a catch and wants $\mathbf{P}(Cavity\mid toothache\wedge catch)$. Bayes' rule reformulates it as $\alpha \mathbf{P}(toothache\wedge catch\mid Cavity)\mathbf{P}(Cavity)$ — but now we need the joint likelihood of the two symptoms for each value of $Cavity$, and with $n$ symptoms there are $2^n$ such combinations to store. We are back to an exponential table. This is what led researchers away from probability theory in the first place: combining evidence naively seems to require a full joint over all the evidence.

The solution is a refinement of independence. $Toothache$ and $Catch$ are not independent — both are more likely when there is a cavity. But they are independent once we fix whether there is a cavity. The cavity is the common cause of both; a toothache reflects the state of the nerve, a catch reflects the geometry the probe meets, and given the cavity neither tells us anything further about the other.

With $Toothache\perp Catch\mid Cavity$, the troublesome joint likelihood factors, $\mathbf{P}(toothache\wedge catch\mid Cavity)=\mathbf{P}(toothache\mid Cavity)\mathbf{P}(catch\mid Cavity)$, and the query collapses to a product of per-symptom terms:

Each symptom now contributes its own factor, and we never build the exponential joint. This pattern — one cause directly influencing several effects that are conditionally independent given the cause — is common enough to have a name.

Carry real numbers through to see the factoring work. Suppose $P(cavity)=0.2$, and given a cavity the two symptoms have $P(toothache\mid cavity)=0.6$ and $P(catch\mid cavity)=0.9$; without a cavity, $P(toothache\mid \neg cavity)=0.1$ and $P(catch\mid \neg cavity)=0.2$. Observing both symptoms, the two unnormalized terms are

Normalizing, $P(cavity\mid t\wedge c)=0.108/(0.108+0.016)\approx 0.871$. Two mutually reinforcing symptoms push the belief from a prior of $0.2$ to about $0.87$ — and we combined them by multiplying two one-symptom tables, never building the joint over both. Each symptom multiplied in its own likelihood ratio: the toothache contributed $0.6/0.1=6$, the catch $0.9/0.2=4.5$, so together they shifted the prior odds $0.2/0.8=0.25$ to posterior odds $0.25\times 6\times 4.5=6.75$, i.e. a probability of $6.75/7.75\approx 0.871$. The odds form of Bayes' rule shows exactly why conditionally independent evidence combines by multiplying likelihood ratios.

The saving is substantial. For $n$ effects conditionally independent given the cause, the representation needs one prior $\mathbf{P}(C)$ and $n$ conditional tables $\mathbf{P}(E_i\mid C)$ — size $O(n)$ rather than $O(2^n)$. Conditional independence, unlike absolute independence, is common: most large probabilistic domains decompose into weakly connected pieces because each variable is directly affected by only a few others. This decomposition of a huge joint into small, locally connected factors is one of the most important developments in the recent history of AI.²

The naive Bayes model appears throughout applied AI. In natural-language processing it is the classic naive Bayes text classifier: the document's sentiment is the hidden cause, each word an effect assumed conditionally independent of the others given the sentiment, and a document is scored by the same product $\mathbf{P}(C){\prod }_i\mathbf{P}(wor{d}_i\mid C)$. The independence assumption is false — words are correlated — yet the classifier is hard to beat for the effort.

Toward Bayesian networks

The naive Bayes model is the simplest interesting case of a general idea: represent a joint distribution not as one exponential table but as a product of small local factors, each capturing how a variable depends on a handful of others. Naive Bayes hard-codes a single common cause with conditionally independent effects. Lift that restriction — let each variable depend on an arbitrary small set of parents, with conditional independencies read off the graph — and you get a Bayesian network: a directed graph whose structure encodes the conditional independencies, plus a small conditional table at each node.

The full joint factors along the graph, $\mathbf{P}(X_1,\dots ,X_n)={\prod }_i\mathbf{P}(X_i\mid parents(X_i))$, so a domain that would need $2^n$ numbers as a flat table often needs only a few dozen. That is the compact, factored representation the next lesson develops in full, and the engine behind reasoning over time and the decision-theoretic agents that close the module.

Probabilistic programming and Bayesian ML

Inference by enumeration is $O(2^n)$, and even the Bayesian networks of the next lesson are worst-case intractable to solve exactly. The developments that made probabilistic reasoning practical at scale, after AIMA's third edition, share a single move: give up on exact summation and sample instead, or approximate the posterior with optimization.

Approximate inference by sampling. Rather than sum every entry of a joint, draw many random possible worlds consistent with the evidence and estimate the posterior as a frequency. Markov-chain Monte Carlo methods make this efficient even in high dimensions; Hamiltonian Monte Carlo and its self-tuning variant the No-U-Turn Sampler (Hoffman & Gelman, JMLR 2014) are the samplers inside most modern Bayesian toolkits. For posteriors where sampling is too slow, variational inference turns the problem into optimization — fit a simple distribution to the true posterior by minimizing a divergence — and stochastic variants scale it to large data (Hoffman et al., Stochastic Variational Inference, JMLR 2013).

Probabilistic programming. The idea that unifies these is to treat a probabilistic model as a program: you write down the generative story in a language with random primitives, and a general-purpose inference engine computes posteriors over the program's latent variables. Stan (Carpenter et al., Journal of Statistical Software 2017) compiles a model to a tuned HMC sampler; Pyro (Bingham et al., JMLR 2019) builds probabilistic programs on top of a deep-learning framework so that neural networks and probabilistic models compose. The naive Bayes model of this lesson is one line in such a language; the same engine then handles models far too large to enumerate by hand.

The Bayesian view in machine learning. The same calculus reframes learning itself. A Bayesian treats model parameters $\theta$ as a random variable with a prior $P(\theta )$; data $\mathcal{D}$ updates it to a posterior $P(\theta \mid \mathcal{D})\propto P(\mathcal{D}\mid \theta )P(\theta )$ — Bayes' rule again, with parameters as the cause and data as the effect. Predictions average over the posterior instead of committing to one parameter setting, which yields calibrated uncertainty rather than a bare point estimate (MacKay's 1992 work on Bayesian neural networks is the early reference; the idea is standard in modern probabilistic ML). This is the direct ancestor of the probabilistic-learning methods later in the course, which is why the material here is foundational.³

Two cautions apply. Approximate methods trade a guarantee for speed: a sampler that has not mixed, or a variational family too simple to fit the true posterior, returns a confident but wrong answer, so diagnostics matter. And the choice of prior is a modeling decision, not a fact read off the data — a poorly chosen prior biases the posterior, which is a feature (it lets you inject knowledge) and a hazard (it lets you inject error) at once.

Probability completes the account of rational agency. Logic gave the agent a way to reason when it knew the rules exactly. Probability gives it the calculus of rational belief when it does not — degrees of belief that obey the axioms, updated by conditioning and Bayes' rule as evidence arrives, factored by independence into something an agent can actually compute.