Naive Bayes is one of the oldest machine-learning classifiers still in daily use. Early spam filters were built on it, it remains a strong baseline for text classification, and it trains in a single pass over the data. It is also our first generative classifier — it models how the data is generated in each class, rather than modelling the decision boundary directly.
From Bayes' theorem to a classifier#
For a class $c$ and features $\mathbf{x} = (x_1, \dots, x_d)$:
Estimating the full joint likelihood $P(\mathbf{x} \mid c)$ is hopeless in high dimensions — with 10,000 binary word features there are $2^{10{,}000}$ combinations. The naive assumption is that features are conditionally independent given the class:
The classifier predicts
We sum logarithms rather than multiply probabilities to avoid numerical underflow.
Three common variants#
| Variant | Feature type | $P(x_j \mid c)$ | Typical use |
|---|---|---|---|
| Gaussian NB | Continuous | $\mathcal{N}(x_j \mid \mu_{jc}, \sigma_{jc}^2)$ | Sensor data, simple numeric features |
| Multinomial NB | Counts | $\propto \theta_{jc}^{x_j}$ (word frequencies) | Document classification |
| Bernoulli NB | Binary | $\theta_{jc}^{x_j}(1 - \theta_{jc})^{1 - x_j}$ | Presence/absence of words; short texts |
Training is just counting (or computing means and variances) per class — one pass over the data, $O(nd)$.
Laplace smoothing#
If the word "lottery" never appeared in a legitimate email during training, $P(\text{lottery} \mid \text{ham}) = 0$, and a single occurrence would force the ham probability to zero regardless of all other evidence. Additive (Laplace) smoothing fixes this:
with $\alpha = 1$ (Laplace) or smaller values (Lidstone). In Bayesian terms this is the posterior mean under a symmetric Dirichlet prior — the pseudo-count idea from the MAP lecture.
Why does it work when the assumption is false?#
Words in a document are obviously not independent ("New" and "York" co-occur). Yet Naive Bayes classifies well. The reason: classification needs only the correct ranking of classes, not correct probabilities. Violations of independence distort the probability estimates — typically pushing them towards 0 or 1 — but often preserve which class scores highest. Domingos and Pazzani (1997) analysed conditions under which Naive Bayes remains optimal for classification despite dependence.
A text classifier in practice#
from sklearn.datasets import fetch_20newsgroups
from sklearn.feature_extraction.text import CountVectorizer, TfidfVectorizer
from sklearn.naive_bayes import MultinomialNB, ComplementNB
from sklearn.linear_model import LogisticRegression
from sklearn.pipeline import make_pipeline
from sklearn.metrics import accuracy_score
cats = ["sci.med", "sci.space", "rec.sport.hockey", "talk.politics.misc"]
train = fetch_20newsgroups(subset="train", categories=cats, remove=("headers", "footers", "quotes"))
test = fetch_20newsgroups(subset="test", categories=cats, remove=("headers", "footers", "quotes"))
models = {
"Multinomial NB": make_pipeline(CountVectorizer(stop_words="english"), MultinomialNB(alpha=0.1)),
"Complement NB": make_pipeline(TfidfVectorizer(stop_words="english"), ComplementNB(alpha=0.3)),
"Logistic reg.": make_pipeline(TfidfVectorizer(stop_words="english"), LogisticRegression(max_iter=2000)),
}
for name, m in models.items():
m.fit(train.data, train.target)
print(f"{name:<15} accuracy = {accuracy_score(test.target, m.predict(test.data)):.3f}")
# Most indicative words per class for Multinomial NB
nb = models["Multinomial NB"]
vocab = nb[0].get_feature_names_out()
for i, c in enumerate(train.target_names):
top = nb[1].feature_log_prob_[i].argsort()[-8:][::-1]
print(c, "->", ", ".join(vocab[top]))Naive Bayes is typically competitive with logistic regression here, trains in a fraction of a second, and its top words per class make it easy to inspect. Complement Naive Bayes often improves results on imbalanced text data.
Generative versus discriminative#
Naive Bayes is generative — it models $P(\mathbf{x}, c)$. Logistic regression is discriminative — it models $P(c \mid \mathbf{x})$ directly. In fact, Gaussian Naive Bayes with shared variances produces a decision rule of the same form as logistic regression. Ng and Jordan (2002) showed a classic trade-off:
- Naive Bayes approaches its (higher) asymptotic error faster — it wins with little data.
- Logistic regression has lower asymptotic error — it wins with more data.
Generative models can also handle missing features naturally (just omit the term) and can generate synthetic examples.
When to use Naive Bayes#
- A fast, strong baseline for text classification.
- Very high-dimensional sparse data with limited training examples.
- Streaming/online settings — counts update incrementally.
- Resource-constrained devices.