CtrlK
Naive Bayes is a family of probabilistic classification algorithms based on Bayes' theorem with a strong ("naive") assumption that all features are conditionally independent given the class label. Despite this simplifying assumption, which rarely holds in practice, Naive Bayes classifiers perform remarkably well on a wide range of tasks, particularly in text classification and spam filtering. They are among the simplest and most efficient supervised learning algorithms in machine learning.
Bayes' theorem describes how to update the probability of a hypothesis in light of new evidence. For a classification problem, it provides the posterior probability of a class y given observed features x = (x_1, x_2, ..., x_n):
P(y | x_1, x_2, ..., x_n) = P(x_1, x_2, ..., x_n | y) * P(y) / P(x_1, x_2, ..., x_n)
Where:
| Term | Name | Meaning |
|---|---|---|
| P(y | x_1, ..., x_n) | Posterior probability | The probability of class y given the observed features |
| P(x_1, ..., x_n | y) | Likelihood | The probability of observing the features given class y |
| P(y) | Prior probability | The probability of class y before observing any features |
| P(x_1, ..., x_n) | Evidence (marginal likelihood) | The total probability of observing the features across all classes |
The prior P(y) can be estimated from the frequency of each class in the training data. The evidence P(x_1, ..., x_n) is a normalizing constant that does not depend on the class, so it can be ignored when comparing classes. The main challenge is estimating the likelihood P(x_1, ..., x_n | y), which requires modeling the joint distribution of all features conditioned on the class.
Estimating the full joint probability P(x_1, x_2, ..., x_n | y) directly is intractable for high-dimensional data. With d binary features, there are 2^d possible feature combinations per class, requiring an exponential number of parameters.
The "naive" assumption simplifies this by assuming that all features are conditionally independent given the class:
P(x_1, x_2, ..., x_n | y) = P(x_1 | y) * P(x_2 | y) * ... * P(x_n | y) = product from i=1 to n of P(x_i | y)
This transforms the problem from estimating one joint distribution into estimating n individual feature distributions, each of which requires far fewer parameters.
The full Naive Bayes classification rule combines Bayes' theorem with the independence assumption:
y_hat = argmax_y P(y) * product from i=1 to n of P(x_i | y)
Since the evidence term P(x_1, ..., x_n) is the same for all classes, it cancels out during comparison. In practice, the products of probabilities are computed as sums of log-probabilities to avoid numerical underflow:
y_hat = argmax_y [log P(y) + sum from i=1 to n of log P(x_i | y)]
The independence assumption is almost always violated in real data. For instance, in text classification, the presence of the word "machine" makes the word "learning" more likely to appear. Nevertheless, Naive Bayes often produces accurate classifications because the predicted class depends on which class has the highest posterior probability, not on the exact probability values. Even when the probability estimates are poorly calibrated, the ranking of classes can still be correct.
Different variants of Naive Bayes differ in the assumptions they make about the distribution of P(x_i | y). The choice of variant depends on the nature of the feature data.
Gaussian Naive Bayes assumes that the continuous features associated with each class follow a normal distribution (Gaussian distribution). For each class y and feature x_i, the likelihood is modeled as:
P(x_i | y) = (1 / sqrt(2 * pi * sigma_y^2)) * exp(-(x_i - mu_y)^2 / (2 * sigma_y^2))
Where mu_y is the mean and sigma_y^2 is the variance of feature x_i for class y, both estimated from the training data.
When to use: Gaussian Naive Bayes is appropriate for datasets with continuous, real-valued features. It is commonly applied in medical diagnosis, iris species classification, and other tasks where features are measurements or sensor readings.
Advantages: Simple to implement; no discretization of features required; works well when the Gaussian assumption roughly holds.
Limitations: Performs poorly when features have heavy-tailed, multimodal, or highly skewed distributions that deviate significantly from the Gaussian assumption.
Multinomial Naive Bayes models the likelihood of features using a multinomial distribution. It is designed for discrete count data, where features represent frequencies or occurrence counts.
For a document represented as a vector of word counts x = (x_1, x_2, ..., x_n), the likelihood for class y is:
P(x | y) proportional to product from i=1 to n of P(w_i | y)^(x_i)
Where P(w_i | y) is the probability of word w_i appearing in a document of class y, estimated as:
P(w_i | y) = (count of w_i in documents of class y) / (total count of all words in documents of class y)
When to use: Multinomial Naive Bayes is the standard choice for text classification tasks, including document classification, sentiment analysis, and topic categorization. It works with bag-of-words and TF-IDF feature representations.
Advantages: Handles high-dimensional sparse data efficiently; naturally accounts for word frequency information; widely used and well-tested for natural language processing tasks.
Limitations: Assumes features are counts (non-negative integers); does not capture word order or semantic relationships.
Bernoulli Naive Bayes models features as binary (Boolean) variables, indicating the presence or absence of a feature. For text, this means each feature represents whether a particular word appears in a document, regardless of how many times.
The likelihood for class y is:
P(x | y) = product from i=1 to n of [P(x_i = 1 | y)^(x_i) * (1 - P(x_i = 1 | y))^(1 - x_i)]
A distinctive property of Bernoulli Naive Bayes is that it explicitly models the absence of features (when x_i = 0), penalizing the non-occurrence of features that are expected for a given class. Multinomial Naive Bayes, by contrast, simply ignores features with zero counts.
When to use: Bernoulli Naive Bayes is appropriate when features are binary. In text classification, it is best suited for short documents or small vocabularies where word presence/absence is more informative than word frequency.
Advantages: Explicitly penalizes absent features, which can improve classification when feature absence is informative; works well with binary feature vectors.
Limitations: Discards frequency information; the multivariate Bernoulli model tends to perform worse than the multinomial model when the vocabulary is large.
Complement Naive Bayes (CNB), introduced by Rennie et al. in 2003, addresses some of the issues with standard Multinomial Naive Bayes on imbalanced datasets. Instead of estimating the parameters for each class using documents belonging to that class, CNB uses the complement of each class (all documents not in the class) to estimate parameters. This approach often outperforms standard Multinomial Naive Bayes, especially on datasets with uneven class distributions.
| Variant | Feature Type | Distribution | Best For | Key Property |
|---|---|---|---|---|
| Gaussian | Continuous | Normal (Gaussian) | Numeric data, sensor data, measurements | Estimates mean and variance per class |
| Multinomial | Discrete counts | Multinomial | Text classification with word counts | Uses word frequency |
| Bernoulli | Binary (0/1) | Bernoulli | Short texts, binary feature presence | Penalizes absent features |
| Complement | Discrete counts | Complement of multinomial | Imbalanced text datasets | Uses complement class statistics |
Naive Bayes classifiers are among the most widely used algorithms for text classification. The standard pipeline for text classification with Naive Bayes involves:
Naive Bayes handles high-dimensional text data efficiently because training only requires a single pass through the data to collect word counts per class. The time complexity is O(n * d) for training and O(c * d) for classification, where n is the number of training examples, d is the vocabulary size, and c is the number of classes.
Consider classifying news articles into categories such as "Sports," "Politics," and "Technology." The Multinomial Naive Bayes classifier would:
One of the most famous applications of Naive Bayes is email spam filtering. The history of Bayesian spam filtering illustrates both the power and the practical appeal of the algorithm.
Bayesian approaches to spam filtering date back to at least 1998, when Sahami, Dumais, Heckerman, and Horvitz published one of the first scholarly papers on the topic, "A Bayesian approach to filtering junk e-mail." However, Bayesian spam filtering gained widespread popularity in 2002 when Paul Graham published his influential essay "A Plan for Spam." Graham demonstrated that a simple Bayesian classifier trained on a user's own email could achieve remarkably low false positive rates, outperforming the handcrafted rule-based filters that were standard at the time.
Graham's approach worked by computing the probability that a word appeared in spam versus legitimate email ("ham") and combining these individual probabilities using Bayes' theorem. The system learned from the user's own data, adapting to the specific types of spam they received. Following Graham's essay, Bayesian spam filters were incorporated into email clients such as Mozilla Thunderbird, SpamAssassin, SpamBayes, and others.
A Naive Bayes spam filter classifies an email as spam or ham based on the words it contains:
Words like "free," "winner," "click," and "unsubscribe" would have high P(word | spam), while words like a recipient's name or workplace would have high P(word | ham).
A practical problem arises when a word appears in test data but was never observed in one of the classes during training. In this case, P(x_i | y) = 0, and because Naive Bayes multiplies probabilities, a single zero probability makes the entire posterior zero, regardless of all other evidence. This is known as the zero-frequency problem.
Laplace smoothing (also called additive smoothing or Lidstone smoothing) addresses this by adding a small constant alpha to every count:
P(x_i | y) = (count(x_i, y) + alpha) / (count(y) + alpha * |V|)
Where:
| Symbol | Meaning |
|---|---|
| count(x_i, y) | Number of times feature x_i appears in class y |
| count(y) | Total count of all features in class y |
| alpha | Smoothing parameter |
| |V| | Size of the vocabulary (total number of distinct features) |
Common choices for alpha:
| Alpha Value | Name | Effect |
|---|---|---|
| 0 | No smoothing | Zero probabilities possible; can fail on unseen features |
| 0.5 | Jeffreys prior | Moderate smoothing |
| 1 | Laplace smoothing (add-one) | Each feature is "seen" at least once per class |
| Tuned value | Lidstone smoothing | Optimized via cross-validation |
When alpha = 1, the formula acts as if every word was observed one additional time in every class, ensuring that no probability estimate is zero. In practice, treating alpha as a hyperparameter and tuning it via cross-validation often yields better results than using a fixed value.
| Advantage | Explanation |
|---|---|
| Fast training and prediction | Training requires only a single pass through the data; prediction involves computing products of stored probabilities |
| Scales well to high dimensions | Handles thousands or millions of features (e.g., large vocabularies in text) without difficulty |
| Works well with small datasets | Requires relatively few training examples to estimate parameters reliably |
| Robust to irrelevant features | Irrelevant features contribute roughly equally to all classes, so they do not strongly affect classification |
| Easy to implement | The algorithm is straightforward and has few hyperparameters |
| Naturally handles multi-class problems | Extends directly to multiple classes without modification |
| Good baseline | Often provides a surprisingly strong baseline that more complex models struggle to beat |
| Interpretable | The learned probabilities are easy to inspect and understand |
| Disadvantage | Explanation |
|---|---|
| Independence assumption is unrealistic | Features in real data are almost always correlated; this can lead to poorly calibrated probability estimates |
| Poor probability estimates | While class rankings may be correct, the raw probability values are often unreliable |
| Sensitive to feature engineering | Performance depends heavily on how features are represented and selected |
| Cannot learn feature interactions | The independence assumption prevents the model from capturing relationships between features |
| Zero-frequency problem | Without smoothing, unseen features cause zero probabilities |
| Bias toward classes with more features | In text, longer documents tend to be favored unless normalization is applied |
Naive Bayes and logistic regression are both widely used for classification, but they represent fundamentally different approaches. Naive Bayes is a generative model that learns the joint probability P(X, y) and derives the decision boundary from it, while logistic regression is a discriminative model that directly learns the conditional probability P(y | X).
This distinction was formally analyzed by Andrew Ng and Michael Jordan in their 2001 NeurIPS paper, "On Discriminative vs. Generative Classifiers: A comparison of logistic regression and naive Bayes."
| Aspect | Naive Bayes | Logistic Regression |
|---|---|---|
| Model type | Generative | Discriminative |
| What it models | P(X, y) = P(X | y) * P(y) | P(y | X) directly |
| Feature independence | Assumes conditional independence | Does not require independence |
| Training speed | Very fast (closed-form parameter estimation) | Requires iterative optimization |
| Data efficiency | Reaches asymptotic performance with O(log n) examples | Reaches asymptotic performance with O(n) examples |
| Asymptotic accuracy | Lower (bounded by independence assumption) | Higher (no independence constraint) |
| Small dataset performance | Often better | May overfit |
| Large dataset performance | Often worse | Often better |
| Handling correlated features | Cannot model correlations | Handles correlations naturally |
| Probability calibration | Often poorly calibrated | Generally better calibrated |
| Regularization | Laplace smoothing | L1 (Lasso), L2 (Ridge) penalties |
Ng and Jordan's analysis revealed two important findings:
Asymptotic performance: With infinite training data, logistic regression achieves lower classification error than Naive Bayes when the independence assumption is violated (which is almost always the case in practice).
Convergence rate: Naive Bayes reaches its (higher) asymptotic error rate much faster, requiring only O(log n) training examples, whereas logistic regression requires O(n) examples to reach its (lower) asymptotic error. This means that Naive Bayes can outperform logistic regression when training data is scarce.
In practical terms: for small datasets where features are reasonably independent, Naive Bayes may be the better choice. For large datasets with correlated features, logistic regression (or other discriminative models) will typically outperform Naive Bayes.
Naive Bayes is a strong choice in the following scenarios:
The scikit-learn library provides implementations of all major Naive Bayes variants:
| Class | Variant | Typical Use Case |
|---|---|---|
| GaussianNB | Gaussian Naive Bayes | Continuous features |
| MultinomialNB | Multinomial Naive Bayes | Word counts, TF-IDF |
| BernoulliNB | Bernoulli Naive Bayes | Binary features |
| ComplementNB | Complement Naive Bayes | Imbalanced text classification |
| CategoricalNB | Categorical Naive Bayes | Categorical features |
Several extensions have been proposed to address the limitations of standard Naive Bayes: