Bayes’ theorem, MAP, and naive Bayes

Bayes’ theorem: inverting a conditional

We can usually measure $p(E \mid h)$ — *how often the evidence shows up when a hypothesis is true* — but we want $p(h \mid E)$ — *how likely the hypothesis is given the evidence we saw*. Bayes’ theorem inverts the conditional: for a hypothesis $h_i$ drawn from a mutually exclusive, exhaustive set $H$, $$p(h_i \mid E) = \frac{p(E \mid h_i)\,p(h_i)}{\sum_k p(E \mid h_k)\,p(h_k)}.$$

Name every part — examiners ask for this:

- $p(h_i \mid E)$ — the posterior: what we want, our belief *after* seeing $E$. - $p(E \mid h_i)$ — the likelihood: how well $h_i$ predicts the evidence (usually measurable from data). - $p(h_i)$ — the prior: belief *before* the evidence (e.g. a disease’s base-rate prevalence). - $\sum_k p(E \mid h_k)\,p(h_k) = p(E)$ — the normalizing constant, the total probability of the evidence across all hypotheses, which forces the posteriors to sum to 1.

It is powerful because the easy-to-collect quantity (how often meningitis patients have headaches) yields the hard-to-collect one (what fraction of headache patients have meningitis).

MAP: drop the denominator

If all we want is the *most likely* hypothesis (not its exact probability), the denominator $p(E)$ is identical for every $h_i$, so it can be dropped. What remains is the maximum a posteriori (MAP) estimate: $$h_{\text{MAP}} = \arg\max_{h_i}\; p(E \mid h_i)\,p(h_i).$$ The result is no longer a true probability (it won’t sum to 1), but it correctly identifies the winner — and it is used pervasively in classification, speech recognition, and NLP.

The independence trick: naive Bayes

With several pieces of evidence $E = \{e_1,\dots,e_n\}$, the joint likelihood $p(E \mid h)$ needs a table that grows *exponentially* in $n$. Naive Bayes makes the simplifying assumption that the features are conditionally independent given the class: $$p(E \mid h) \approx \prod_i p(e_i \mid h).$$ This turns an exponential table into a *product of small per-feature estimates* — linear in $n$. Plugging that into MAP gives the classifier $$\text{predict}(E) = \arg\max_{h}\; p(h)\prod_i p(e_i \mid h).$$ The assumption is almost never literally true (symptoms correlate), yet the classifier works remarkably well — Domingos and Pazzani showed it only needs the *ranking* of hypotheses to be right, not the exact probabilities, and the ranking often survives even when independence is violated.

Worked example — a tiny spam classifier

Train on a few labeled messages, count how often each word appears in *spam* vs *ham*, add Laplace (+1) smoothing so an unseen word doesn’t zero out the whole product, then for a new message multiply the class prior by the per-word likelihoods and take the argmax. For the input "cheap meds now", the spam-laden words dominate and the model returns spam with a high posterior. The code exercise builds exactly this and prints the prediction with its normalized posterior.