Naive Bayes

Background

Rooted in Bayes theorem (1763) applied to classification by mid-20th century statisticians
Despite its 'naive' independence assumption, achieves strong results on text classification
Online and streaming-friendly: model updates by simply counting new examples

The Concept

Naive Bayes applies Bayes theorem with the strong assumption that all features are conditionally independent given the class label. This lets it estimate class probabilities by multiplying individual feature likelihoods - which is fast, interpretable, and surprisingly effective.

How it Links

The Bayes theorem foundation connects to Bayesian inference, Gaussian mixture models, and probabilistic generative models
Independence assumption is related to mean-field approximations in variational inference
Gaussian NB connects to LDA (Linear Discriminant Analysis) when classes share the same covariance

Concrete Example

Spam detection: the model estimates P(word|spam) for every word from labeled emails. For a new email, it multiplies the probabilities of all its words given spam vs given not-spam. The class with the higher product wins - completely ignoring word order but still very effective.

Prerequisites

Math you need: probability basics, Logistic regression, Bias, variance, over/under-fitting, Evaluation metrics

Learning outcomes

State Bayes theorem and apply it to derive the naive Bayes posterior.
Recognize the conditional-independence assumption and explain why it is almost always wrong yet still useful.
Pick the right variant - Gaussian, Multinomial, or Bernoulli - based on feature type, and derive the MLE for each.
Apply Laplace / Lidstone smoothing and explain why it is mandatory for sparse text features.
Compare naive Bayes with logistic regression along the Ng-Jordan small-vs-large-n crossover, and explain the Domingos-Pazzani argument for robustness.

TL;DR

Naive Bayes applies Bayes theorem $P(y \mid x) \propto P(x \mid y) P(y)$ under the conditional-independence assumption $P(x \mid y) = \prod_{j} P(x_j \mid y)$ [5]. This factorization decouples per-feature parameter estimation, so MLE reduces to counting. Three standard variants cover almost every real use: Gaussian (continuous features), Multinomial (token counts), Bernoulli (binary occurrence). Laplace smoothing $\hat{p}(x_j \mid y) = (n_{jy} + \alpha) / (n_y + \alpha V)$ prevents zero probabilities from killing the posterior on unseen tokens. The independence assumption is almost always violated, yet naive Bayes routinely beats more flexible models on small datasets - Ng & Jordan 2001 prove that NB has lower asymptotic error than logistic regression up to a sample-size crossover where LR catches up, and Domingos & Pazzani 1997 show that NB’s probability estimates can be wildly miscalibrated while its classification is still optimal under zero-one loss because argmax is robust to monotone distortion [2][1]. This is the first sharp example of “wrong model, right decisions”.

Intuition

A naive Bayes classifier asks: given the feature vector $x = (x_1, \dots, x_d)$ , which class $y$ makes it most likely? Bayes theorem inverts the conditional:

P(y \mid x) = \frac{P(x \mid y)\, P(y)}{P(x)} \propto P(x \mid y)\, P(y).

The denominator $P(x)$ is the same for every class, so we can drop it for classification. The hard part is modeling the joint $P(x \mid y)$ over $d$ correlated features. Naive Bayes makes one drastic assumption to dodge this:

P(x \mid y) = \prod_{j=1}^{d} P(x_j \mid y).

That is the naïveté: features are conditionally independent given the class. It is almost always false (in spam, “viagra” and “free” co-occur far more often than independence would predict), yet the model trained under this assumption is among the best classifiers you can run on small text datasets.

Why a wrong probability model can still classify correctly

Naive Bayes is wrong about the posterior probabilities in proportion to how badly conditional independence is violated. But classification only needs the argmax of the posterior, and argmax is invariant to any monotone transformation of the scores. As long as the wrong probabilities preserve the right ranking of classes, the classifier is still optimal under zero-one loss [1]. This decoupling - “estimating probabilities well” vs “ranking classes correctly” - is the right way to think about all generative classifiers.

Math

Bayes theorem and the naive Bayes posterior

Bayes theorem refresher

For random variables $X$ and $Y$ with joint density $p(x, y)$ ,

P(Y = y \mid X = x) = \frac{P(X = x \mid Y = y)\, P(Y = y)}{P(X = x)} = \frac{P(X = x \mid Y = y)\, P(Y = y)}{\sum_{y'} P(X = x \mid Y = y')\, P(Y = y')}.

The numerator is $P(x, y)$ ; the denominator is the marginal $P(x)$ . Bayes theorem inverts the conditional, exchanging the roles of likelihood $P(x \mid y)$ and posterior $P(y \mid x)$ .

The naïveté assumption

The exact joint $P(x \mid y)$ over $d$ features needs $\Theta(2^{d})$ parameters in the binary case (one for each cell of the joint table). Naive Bayes replaces this with the product of marginals:

P(x \mid y) = \prod_{j=1}^{d} P(x_j \mid y).

Now we only need $d$ univariate distributions per class. The number of parameters scales as $O(d K)$ instead of $O(2^{d} K)$ for $K$ classes, so the model is feasible even when $d$ is in the thousands - the typical case for text.

Predictive rule

Combining,

\hat{y}(x) = \arg\max_{y \in \mathcal{Y}}\; P(y) \prod_{j=1}^{d} P(x_j \mid y).

For numerical stability we work in log-space:

\hat{y}(x) = \arg\max_{y}\; \log P(y) + \sum_{j=1}^{d} \log P(x_j \mid y).

The decision function is linear in the log-feature-likelihoods - that is the structural reason naive Bayes is closely related to logistic regression (the discriminative analogue), as Ng & Jordan made precise [2].

The three standard variants and their MLEs

Gaussian naive Bayes (continuous features)

Model each $x_j \mid y = c$ as a univariate Gaussian:

p(x_j \mid y = c) = \frac{1}{\sqrt{2\pi \sigma_{jc}^{2}}}\,\exp\!\left(-\frac{(x_j - \mu_{jc})^{2}}{2 \sigma_{jc}^{2}}\right).

The class-conditional MLE on the training data with $n_c$ examples in class $c$ :

\hat{\mu}_{jc} = \frac{1}{n_c}\sum_{i : y_i = c} x_{ij}, \qquad \hat{\sigma}_{jc}^{2} = \frac{1}{n_c}\sum_{i : y_i = c} (x_{ij} - \hat{\mu}_{jc})^{2}.

Class prior is $\hat{P}(y = c) = n_c / n$ . In practice we add a small variance floor $\varepsilon$ to avoid division by zero on degenerate features (sklearn’s var_smoothing).

Multinomial naive Bayes (token counts)

For text-style data with feature $x_j$ a count of token $j$ in the document, model the document as a multinomial draw of $\sum_j x_j$ tokens from a per-class vocabulary distribution. The class-conditional MLE is

\hat{p}(\text{token } j \mid y = c) = \frac{n_{jc}}{n_c},\qquad n_{jc} = \sum_{i : y_i = c} x_{ij},\;\; n_c = \sum_{j} n_{jc}.

The likelihood of a document $x$ given class $c$ is, up to a constant in $\arg\max$ ,

p(x \mid y = c) \propto \prod_{j=1}^{V} \hat{p}(\text{token } j \mid c)^{x_j}.

McCallum & Nigam 1998 give the canonical comparison of this multinomial event model with the Bernoulli event model below; the multinomial wins on most text-classification benchmarks once vocabulary size grows past a thousand [3].

Bernoulli naive Bayes (binary occurrence)

For text where features are binary “did token $j$ appear?” indicators, model each $x_j \mid y = c$ as a Bernoulli with parameter $p_{jc}$ . The MLE counts the fraction of documents in class $c$ that contain token $j$ :

\hat{p}_{jc} = \frac{\#\{i : y_i = c \text{ and } x_{ij} = 1\}}{n_c}.

The likelihood of $x$ given $c$ is

p(x \mid y = c) = \prod_{j=1}^{V} \hat{p}_{jc}^{x_j}\, (1 - \hat{p}_{jc})^{1 - x_j}.

Bernoulli NB explicitly penalizes missing tokens (via the $(1 - \hat{p}_{jc})$ factor), which the multinomial model ignores. It tends to win on short documents where absence is informative [3].

Laplace / Lidstone smoothing

The zero-probability problem

If a token $j$ does not appear in any class- $c$ training document, the MLE gives $\hat{p}(j \mid c) = 0$ . Then any test document containing token $j$ has $P(y = c \mid x) = 0$ , which (a) is structurally wrong since absence in a finite sample does not prove zero probability and (b) propagates as $\log 0 = -\infty$ that wipes out the posterior.

Laplace add-one smoothing

Add a pseudo-count $\alpha = 1$ to every token-class pair:

\hat{p}(j \mid c) = \frac{n_{jc} + 1}{n_c + V},

where $V$ is the vocabulary size. This is the Laplace (or add-one) estimator. Probabilistically it is the posterior mean under a uniform Dirichlet prior $\mathrm{Dir}(1, \dots, 1)$ over the per-class vocabulary distribution.

Lidstone generalization

Generalize to any pseudo-count $\alpha \in (0, 1]$ :

\boxed{\;\hat{p}(x_j \mid y = c) = \frac{n_{jc} + \alpha}{n_c + \alpha V}\;}

Smaller $\alpha$ trusts the data more (less smoothing); larger $\alpha$ pulls every probability toward the uniform $1/V$ . The choice is a hyperparameter selected by cross-validation; sklearn’s default is $\alpha = 1$ (MultinomialNB(alpha=1.0)).

When you must smooth

Always for text, because real vocabularies have a long tail and any held-out document will contain training-rare tokens.
Not strictly required for Gaussian NB, because a Gaussian density never returns exactly zero. But variance smoothing is a related fix when a feature is constant within a class.

Generative vs discriminative: the Ng-Jordan crossover

Naive Bayes models the joint $P(x, y)$ via $P(x \mid y)\, P(y)$ and is therefore generative. Logistic regression models the conditional $P(y \mid x)$ directly and is discriminative. Both have the same parametric form for the decision boundary in the binary case (a hyperplane in $x$ ), but they fit it differently.

Why NB and logistic regression are a matched pair

For binary classification with discrete features, naive Bayes induces the posterior

\log \frac{P(y=1 \mid x)}{P(y=0 \mid x)} = \log \frac{P(y=1)}{P(y=0)} + \sum_{j=1}^{d} \log \frac{P(x_j \mid y=1)}{P(x_j \mid y=0)},

which is linear in the per-feature log-likelihood ratios. Logistic regression directly parameterizes a linear log-odds:

\log \frac{P(y=1 \mid x)}{P(y=0 \mid x)} = w_0 + \sum_{j=1}^{d} w_j x_j.

When the conditional-independence assumption is exactly true and the per-feature distributions are correctly specified, both models converge to the same Bayes-optimal decision boundary. The difference is the loss function used to fit the parameters, and it is what gives the two methods their distinctive small-vs-large-sample behaviour.

Ng & Jordan 2001 proved that on a fixed problem with $n$ training examples and $d$ features [2]:

Asymptotic ( $n \to \infty$ ) error. Logistic regression matches or beats naive Bayes if the conditional-independence assumption is wrong (the typical case). NB has a non-zero asymptotic bias because it cannot represent the true posterior; LR converges to the true posterior in the limit.
Finite-sample error. Naive Bayes converges to its (biased) asymptote at rate $O(\sqrt{(\log d) / n})$ , while logistic regression converges at the slower rate $O(\sqrt{d / n})$ . So for small $n$ , NB is closer to its limit, and that limit can be better than LR’s halfway-converged estimate.

The practical consequence is a crossover: there is a sample size $n^\star$ (depending on $d$ and the data) below which NB beats LR and above which LR catches up and pulls ahead. On text-classification benchmarks with $n^\star$ in the hundreds, NB is the right baseline for tiny datasets and LR takes over once you have a few thousand labeled documents.

Bias-variance picture

Naive Bayes is high bias, low variance: the conditional-independence factorization aggressively constrains the model class, so there is little to fit and few parameters to overfit. Logistic regression is moderate bias, moderate variance: it has more flexibility (no independence assumption) but more parameters to estimate from the same data. In small- $n$ regimes, the variance term dominates and NB’s high-bias-low-variance package wins.

Domingos & Pazzani: why a “wrong” model still wins

Naive Bayes’ independence assumption is almost always violated, yet it beats far more flexible models on a striking number of real datasets. Domingos & Pazzani 1997 explained why [1]:

Classification only needs the argmax of the posterior, not the posterior itself.
Many monotone distortions of the per-class scores leave the argmax unchanged.
The conditional-independence assumption tends to produce miscalibrated but co-monotone posteriors: the highest-scoring class under NB is often the same as the highest-scoring class under the true joint distribution.

A simple two-class example makes the point: if features $x_1$ and $x_2$ are perfectly correlated under both classes, NB double-counts their evidence and produces overconfident posteriors. But because both classes are overcounted in the same direction, the winning class is unchanged. NB classifies correctly while reporting probabilities of $0.99$ when the truth is $0.6$ - bad calibration, correct decision.

The Domingos-Pazzani result formalizes this with sufficient conditions on the feature dependence structure under which NB attains the Bayes-optimal classifier under zero-one loss. The takeaway is the same lesson as in many classical-ML stories: estimating probabilities well and ranking classes correctly are different problems, and NB nails the second while flunking the first.

Algorithm

Step	Operation
1	Estimate class priors P(y = c) = n_c / n.
2	For each class c and each feature j, estimate P(x_j \| y = c) using the appropriate variant (Gaussian mu / sigma, multinomial proportion, Bernoulli rate).
3	Apply Laplace / Lidstone smoothing to prevent zero probabilities (mandatory for multinomial / Bernoulli, optional for Gaussian).
4	At test time, compute log P(y = c) + sum_j log P(x_j \| y = c) for each class c.
5	Predict argmax over c. Optionally exponentiate and normalize for posterior probabilities, but treat them with suspicion.

# Multinomial naive Bayes pseudocode (sklearn-style)
def fit_multinomial_nb(X, y, alpha=1.0):
    classes = np.unique(y)
    log_prior = {c: np.log((y == c).sum() / len(y)) for c in classes}
    V = X.shape[1]
    log_likelihood = {}
    for c in classes:
        n_c = X[y == c].sum(axis=0) + alpha               # smoothed counts per token
        log_likelihood[c] = np.log(n_c / n_c.sum())
    return log_prior, log_likelihood
 
def predict_multinomial_nb(log_prior, log_likelihood, X):
    classes = list(log_prior.keys())
    scores = np.stack([X @ log_likelihood[c] + log_prior[c] for c in classes], axis=1)
    return np.array(classes)[np.argmax(scores, axis=1)]

Implementations

Three idiomatic implementations of naive Bayes for text. The numpy version counts tokens per class with Laplace smoothing in about thirty lines; the sklearn-mnb version is the production one-liner for token-count features; the sklearn-gnb version handles continuous features with the Gaussian variant.

python

import numpy as np

def fit_multinomial_nb(X, y, alpha=1.0):
  """From-scratch multinomial NB with Laplace smoothing.
  X is (n, V) integer count matrix, y is (n,) integer labels.
  """
  classes = np.unique(y)
  n, V = X.shape
  log_prior = np.zeros(len(classes))
  log_likelihood = np.zeros((len(classes), V))
  for k, c in enumerate(classes):
      Xc = X[y == c]
      log_prior[k] = np.log(Xc.shape[0] / n)
      counts = Xc.sum(axis=0) + alpha           # smoothed token counts
      log_likelihood[k] = np.log(counts / counts.sum())
  return classes, log_prior, log_likelihood

def predict_multinomial_nb(model, X):
  classes, log_prior, log_likelihood = model
  scores = X @ log_likelihood.T + log_prior     # (n_test, n_classes)
  return classes[np.argmax(scores, axis=1)]

# Tiny spam-filter example (token id, count) per document.
# Pretend vocabulary = {'free', 'meeting', 'viagra', 'project'}, V = 4.
X = np.array([
  [3, 0, 2, 0],   # spam
  [2, 0, 1, 0],   # spam
  [1, 0, 3, 0],   # spam
  [0, 2, 0, 3],   # ham
  [0, 3, 0, 2],   # ham
  [0, 1, 0, 4],   # ham
])
y = np.array([1, 1, 1, 0, 0, 0])
model = fit_multinomial_nb(X, y, alpha=1.0)

X_new = np.array([[2, 1, 1, 0],   # mostly spam tokens
                [0, 2, 0, 2]])  # mostly ham tokens
print("Predictions:", predict_multinomial_nb(model, X_new))  # [1, 0]

About 30 lines of numpy. The matrix multiply X @ log_likelihood.T is the entire predict-time computation - linear in n, V, and the number of classes.

Run the from-scratch multinomial NB on a tiny spam-filter example live in the browser:

Idle (packages: numpy)

import numpy as np

def fit_multinomial_nb(X, y, alpha=1.0):
  classes = np.unique(y)
  n, V = X.shape
  log_prior = np.zeros(len(classes))
  log_likelihood = np.zeros((len(classes), V))
  for k, c in enumerate(classes):
      Xc = X[y == c]
      log_prior[k] = np.log(Xc.shape[0] / n)
      counts = Xc.sum(axis=0) + alpha
      log_likelihood[k] = np.log(counts / counts.sum())
  return classes, log_prior, log_likelihood

def predict_multinomial_nb(model, X):
  classes, log_prior, log_likelihood = model
  scores = X @ log_likelihood.T + log_prior
  return classes[np.argmax(scores, axis=1)]

# Tiny vocabulary: ['free', 'meeting', 'viagra', 'project'].
X = np.array([
  [3, 0, 2, 0],
  [2, 0, 1, 0],
  [1, 0, 3, 0],
  [0, 2, 0, 3],
  [0, 3, 0, 2],
  [0, 1, 0, 4],
])
y = np.array([1, 1, 1, 0, 0, 0])
model = fit_multinomial_nb(X, y, alpha=1.0)

X_new = np.array([
  [2, 1, 1, 0],
  [0, 2, 0, 2],
  [1, 0, 0, 2],
])
preds = predict_multinomial_nb(model, X_new)
print("Predictions :", preds.tolist())
classes, log_prior, log_likelihood = model
scores = X_new @ log_likelihood.T + log_prior
post = np.exp(scores - scores.max(axis=1, keepdims=True))
post = post / post.sum(axis=1, keepdims=True)
print("Posteriors  :", np.round(post, 3).tolist())

(no output yet)

Naive Bayes vs logistic regression on text

Property	Naive Bayes	Logistic Regression
Family	Generative: models P(x \| y) P(y).	Discriminative: models P(y \| x) directly.
Decision boundary	Linear in log-likelihood-ratios; same form as LR under independence.	Linear in features; fit by MLE on the conditional likelihood.
Small-n behaviour	Wins: O(sqrt(log d / n)) finite-sample rate; aggressive bias floor.	Loses: O(sqrt(d / n)) rate; needs more data to converge.
Large-n behaviour	Plateaus at a non-zero asymptotic error (independence is wrong).	Catches up and surpasses NB; converges to true posterior in the limit.
Calibration	Poor: probabilities cluster near 0 or 1 due to independence violations.	Good: trained directly on log-likelihood, so probabilities track empirical rates.
Training cost	O(n d) one pass: just count.	O(n d) per IRLS iteration; many iterations until convergence.
Sparse high-d text	Strong baseline; pairs naturally with TF-IDF or counts.	Equally strong with L2; slower to fit but better calibrated.
Handles missing features	Trivially: drop the missing factor from the product.	Requires imputation.

Real-world uses

Naive Bayes and the spam wars

Naive Bayes was the algorithm of the early-2000s spam wars. Paul Graham’s 2002 essay A Plan for Spam popularized “Bayesian filters” for end users; the classifier was cheap to update online as users marked messages, robust to adversarial token-level evasion (because even a few strong-evidence tokens dominate the log-posterior), and interpretable enough to give users per-token “spamminess” explanations. SpamAssassin’s Bayes plug-in and POPFile both shipped multinomial NB variants. By 2010 the spam-filter front line had moved to ensembles and deep models, but every modern filter still has a Bayesian-inspired component somewhere in its scoring stack.

Domain	System	Why naive Bayes
Spam filtering	SpamAssassin Bayes plug-in, POPFile, early Gmail spam classifier	Cheap online updates, interpretable per-token scores, holds up under adversarial token tweaks.
Text classification	News topic categorization, sentiment analysis with bag-of-words / TF-IDF	Strong baseline with very little code; sets the bar that more elaborate models must beat.
Genomics	Variant calling, sequence-based classification on small labeled corpora	Tiny labeled samples and many features (k-mers); the Ng-Jordan crossover sits firmly in NB territory.
Medical triage / diagnostic systems	Pathfinder for lymph-node disease (Heckerman 1992), early diagnostic expert systems	Probabilistic interpretability matters for clinicians; conditional independence is a clean modeling assumption.
Real-time content moderation	First-pass keyword / token classifier in moderation pipelines	Predict-time is a single matrix multiply; latency budget is microseconds.

Pitfalls

Probabilities are over-confident

Independence violations cause naive Bayes to multiply correlated evidence as if it were independent. The result is a posterior that pushes hard toward 0 or 1 even when the truth is closer to 0.5. Never treat predict_proba from a multinomial NB as a calibrated probability; if you need calibration, run CalibratedClassifierCV on top with isotonic or sigmoid calibration, or just use logistic regression.

Zero counts kill the posterior without smoothing

A single token unseen in class $c$ during training drives $P(x \mid y = c)$ to zero, so $P(y = c \mid x) = 0$ regardless of the other evidence. Always apply Laplace ( $\alpha = 1$ ) or Lidstone ( $\alpha \in (0, 1)$ ) smoothing for multinomial / Bernoulli NB, and tune $\alpha$ by cross-validation on real text workloads. Gaussian NB has a related issue when a feature is constant within a class - sklearn’s var_smoothing handles it.

Correlated features dominate the score

A pair of perfectly correlated features contributes twice to the log posterior under naive Bayes, even though they carry the same evidence. Heavily redundant features (e.g. multiple TF-IDF variants of the same token, or near-duplicate columns in tabular data) skew NB hard. Drop or collapse correlated features before fitting, or switch to logistic regression which handles correlation through joint estimation.

Use it as your first text-classification baseline

Multinomial NB plus a CountVectorizer is the cheapest competitive baseline on any text task. Train time is one pass; predict time is a sparse matrix multiply. If a more elaborate model (LSTM, transformer fine-tune) cannot beat this baseline by a meaningful margin, the problem is feature engineering or label noise, not model capacity.

Interview Q&A

Derive the MAP estimate for Gaussian naive Bayes.research

Assume continuous features with $x_j \mid y = c \sim \mathcal{N}(\mu_{jc}, \sigma_{jc}^{2})$ and class prior $P(y = c) = \pi_c$ . Given training data $\{(x_i, y_i)\}_{i=1}^{n}$ , the joint log-likelihood (assuming independent examples and conditional independence across features) is

\log p(\{x_i, y_i\} \mid \theta) = \sum_{i=1}^{n} \log \pi_{y_i} + \sum_{i=1}^{n} \sum_{j=1}^{d} \log \mathcal{N}(x_{ij} \mid \mu_{j,y_i}, \sigma_{j,y_i}^{2}).

For each class $c$ , the parameters $(\mu_{jc}, \sigma_{jc}^{2})$ appear only in the inner Gaussian terms over the subset $\{i : y_i = c\}$ . With $n_c = \#\{i : y_i = c\}$ ,

\hat{\mu}_{jc} = \frac{1}{n_c} \sum_{i : y_i = c} x_{ij}, \qquad \hat{\sigma}_{jc}^{2} = \frac{1}{n_c} \sum_{i : y_i = c} (x_{ij} - \hat{\mu}_{jc})^{2}, \qquad \hat{\pi}_c = \frac{n_c}{n}.

Predictions use Bayes theorem with these MLE plug-ins:

\hat{y}(x) = \arg\max_{c}\; \log \hat{\pi}_c + \sum_{j} \log \mathcal{N}(x_j \mid \hat{\mu}_{jc}, \hat{\sigma}_{jc}^{2}).

For MAP estimates with a Normal-Inverse-Gamma prior on $(\mu_{jc}, \sigma_{jc}^{2})$ , the closed-form posterior mean of $\mu_{jc}$ shrinks $\hat{\mu}_{jc}$ toward the prior mean by a factor that depends on the prior strength (a standard conjugate-prior calculation; see Bishop 2006 ch. 2) [5]. In practice sklearn just adds a small var_smoothing floor to the variance, which is the simplest such regularizer.

When does naive Bayes beat logistic regression? Reference the Ng-Jordan result.onsite

Ng & Jordan 2001 analyzed the binary case where naive Bayes and logistic regression have the same parametric decision boundary [2]. Their result is two-pronged:

Asymptotic error. As $n \to \infty$ , logistic regression converges to the true conditional posterior (it directly maximizes $P(y \mid x)$ likelihood), while naive Bayes converges to a biased posterior that assumes conditional independence. So in the limit, LR matches or beats NB whenever independence is wrong, which is essentially always.
Finite-sample rates. NB converges to its (biased) limit at rate $O(\sqrt{(\log d) / n})$ , while LR converges at the slower rate $O(\sqrt{d / n})$ . With $d$ features, the gap matters: NB has only logarithmic dependence on $d$ .

The consequence is a crossover point $n^\star$ : below $n^\star$ , NB is closer to its limit and beats halfway-converged LR; above $n^\star$ , LR has converged closer to its better limit and pulls ahead. On the text-classification benchmarks they study, $n^\star$ is in the hundreds for small vocabularies and grows with $d$ .

The practical rule: NB is the right baseline when $n \ll d$ (typical for small text corpora and many-feature genomics), and LR with proper regularization takes over once $n$ is large enough to estimate $d$ parameters well.

Why does naive Bayes still work when conditional independence is violated? Cite Domingos & Pazzani.onsite

The independence assumption gives wrong posterior probabilities, but classification only needs the argmax of those posteriors, not their absolute values. Many monotone distortions of the per-class scores leave the argmax unchanged, so the classifier can be Bayes-optimal even when the probability estimates are miscalibrated.

Domingos & Pazzani 1997 made this precise [1]. They show that naive Bayes attains the Bayes-optimal classifier under zero-one loss in surprisingly broad regimes - including when features are perfectly correlated, when the distribution is far from the assumed parametric family, and on real-world datasets where the independence assumption fails badly.

The intuition: correlated features cause NB to double-count evidence, but typically in the same direction for the winning class. The winning class is therefore preserved while the gap between top-two scores grows; the result is overconfident probabilities and correct labels.

This is the cleanest classical example of the lesson “estimating probabilities well and ranking classes correctly are different problems”. NB nails the second; if you need the first, calibrate post hoc or switch to logistic regression.

Why is Laplace smoothing necessary for multinomial NB on text?phone

Without smoothing, the maximum-likelihood estimate $\hat{p}(j \mid c) = n_{jc} / n_c$ is exactly zero for any token $j$ that did not appear in any class- $c$ training document. Then for any test document containing token $j$ , the likelihood $P(x \mid y = c) = \prod_j P(x_j \mid c)^{x_j}$ has a factor of zero, so $P(y = c \mid x) = 0$ regardless of every other token. In log-space the contribution is $-\infty$ , which numerically wipes out the posterior.

This is structurally wrong: absence of a token in a finite training sample is not evidence that the token has zero probability under that class. Laplace add-one smoothing replaces the MLE with

\hat{p}(j \mid c) = \frac{n_{jc} + 1}{n_c + V},

which is the posterior mean under a uniform Dirichlet prior over the per-class vocabulary distribution. Lidstone generalizes the pseudo-count to any $\alpha \in (0, 1]$ for finer control. The smoothing parameter is tuned by cross-validation; sklearn defaults to $\alpha = 1$ .

Real text vocabularies have a long tail, so unseen tokens at test time are the rule rather than the exception. Smoothing is therefore mandatory in practice [3][5].

Sketch the bias-variance picture for naive Bayes.onsite

Naive Bayes is the textbook example of high bias, low variance:

Bias. The conditional-independence factorization $P(x \mid y) = \prod_j P(x_j \mid y)$ aggressively constrains the model class. The true joint $P(x \mid y)$ almost always has dependencies that NB cannot represent, so even with infinite data NB converges to a posterior that systematically misses correlated-feature structure. The asymptotic error is non-zero.
Variance. With per-feature univariate distributions, the parameter count is $O(d K)$ for $K$ classes and $d$ features - far smaller than the $O(2^{d} K)$ of a full joint model or even the $O(d K)$ of logistic regression with regularization. There are very few parameters to fit, so they are estimated precisely from a small training sample.

The practical consequence is that NB sits firmly on the low-variance end of the bias-variance trade-off. In small- $n$ regimes the variance term dominates the test error, and NB’s tight constraint pays off (cf. the Ng-Jordan crossover). In large- $n$ regimes the bias floor catches up and discriminative methods win.

The same calculus explains why ensembling NB rarely helps: averaging many NB classifiers reduces variance, but variance was never the problem - the bias floor stays put [4].

Check yourself

Score: 0 / 5(0 answered)

1. Naive Bayes assumes:
2. Why is Laplace smoothing applied in multinomial NB?
3. Per Ng and Jordan 2001, when does naive Bayes beat logistic regression?
4. Per Domingos and Pazzani 1997, why does naive Bayes work despite the independence assumption being wrong?
5. Which NB variant is most appropriate for text features that are token *counts* per document?

Build it yourself

A short evening project to internalize naive Bayes:

Implement multinomial NB from scratch in numpy on a tiny labeled spam corpus (10-20 emails). Confirm Laplace smoothing prevents zero posteriors when a test email contains a token that only appeared in the other class.
On a slightly larger text corpus (e.g. 20-newsgroups two-class subset), plot test accuracy of multinomial NB and L2-regularized logistic regression as a function of training-set size from $n = 50$ to $n = 5000$ . Look for the Ng-Jordan crossover.
Construct a synthetic 2-D dataset where features are perfectly correlated within each class. Fit naive Bayes and a true joint-Gaussian classifier. Compare the probabilities (NB will be wildly miscalibrated) and the labels (both will be near-optimal). This is the Domingos-Pazzani picture in two dimensions.
Stretch: implement a Complement NB (sklearn’s ComplementNB) and compare to standard MNB on an imbalanced text corpus. Complement NB estimates token weights from the complement of each class, which corrects MNB’s bias toward majority classes.

Interactive Demo

Naive Bayes Spam Classifier Demo

Word probabilities in spam vs ham documents

Type a test message:

What to try: Type “free money prize” to see spam indicators, or “meeting report team” for ham indicators.

References

Domingos, P. and Pazzani, M. (1997). On the optimality of the simple Bayesian classifier under zero-one loss. Machine Learning 29(2-3), 103-130. doi:10.1023/A:1007413511361
Ng, A. Y. and Jordan, M. I. (2001). On Discriminative vs. Generative classifiers: A comparison of logistic regression and naive Bayes. Advances in Neural Information Processing Systems 14 (NeurIPS). https://papers.nips.cc/paper_files/paper/2001/hash/7b7a53e239400a13bd6be6c91c4f6c4e-Abstract.html
McCallum, A. and Nigam, K. (1998). A comparison of event models for naive Bayes text classification. AAAI-98 Workshop on Learning for Text Categorization. https://aaai.org/papers/0007-ws98-05-007-a-comparison-of-event-models-for-naive-bayes-text-classification/
Hastie, T., Tibshirani, R., and Friedman, J. (2009). The Elements of Statistical Learning, 2nd ed.. Springer. https://hastie.su.domains/ElemStatLearn/
Bishop, C. M. (2006). Pattern Recognition and Machine Learning. Springer. ISBN 978-0-387-31073-2

Support Vector Machines Clustering (K-Means, DBSCAN, GMM)