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 \underset{h_i}{\max }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 \underset{h}{\max }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.