Robots Atlas>ROBOTS ATLAS
Architecture

Naive Bayes

Historical
Category
Architecture
Abstraction level
Primitive
Operation level
ModelInferenceData
Use cases
Email spam filteringDocument classification and topic categorizationSentiment analysisMedical classification and preliminary diagnosisFast baseline in NLP benchmarks

How it works

1. Training: for each class C compute the prior P(C) as the class frequency in the training set. For each feature x_i compute the conditional probability P(x_i|C) from counts (multinomial) or distribution parameters (Gaussian). 2. Laplace smoothing: add a constant ฮฑ (default 1) to the numerator to avoid zero probabilities for unseen features. 3. Prediction: for a new example x apply the MAP rule โ€” choose the class that maximises P(C)ยทโˆP(x_i|C). In practice, log-sums are used to prevent underflow: log P(C) + ฮฃ log P(x_i|C). 4. Distribution variants: multinomial (token counts โ€” NLP), Bernoulli (binary features), Gaussian (continuous features โ€” assumes normality).

Problem solved

Classifying objects into categories requires a method that estimates the probability of class membership given observed features. Traditional approaches needed to model the full joint distribution of features โ€” computationally intractable in high dimensions. Naive Bayes addresses this by assuming conditional independence of features, reducing estimation complexity from exponential to linear.

Key mechanisms

Bayes' theorem: P(C|x) โˆ P(C)ยทโˆP(x_i|C)
Assumption of conditional feature independence given the class
Estimation of prior and conditional probabilities from training-data frequencies
Laplace / Lidstone smoothing for unseen features
MAP (maximum a posteriori) decision โ€” pick the class with the highest posterior
Distribution variants: Multinomial (counts), Bernoulli (binary), Gaussian (continuous)

Strengths & limitations

Strengths
โœ“Very fast training and prediction โ€” linear in the number of features
โœ“Minimal training-data requirements
โœ“Easy to implement and interpret
โœ“Strong text-classification performance despite the naive assumption
โœ“Native multi-class support
โœ“Low memory footprint
Limitations
โœ—The feature-independence assumption is almost always violated
โœ—Poorly calibrated posterior probabilities (extreme 0/1 values)
โœ—Zero-frequency problem โ€” requires smoothing
โœ—Limited ability to model feature interactions
โœ—Gaussian NB assumes normality of continuous features, which rarely holds
โœ—Worse than discriminative models (logistic regression, SVM) when data is abundant

Implementation

Implementation pitfalls
Zero probability โ€” unseen words zero out the entire distributionMedium

If a test word did not appear in training, P(word|class)=0 zeros out the entire probability product. Requires smoothing (Laplace/add-k) โ€” without it the classifier is useless on new text.

Feature independence assumption rarely holds in languageMedium

Words in a sentence are strongly correlated ("not" before "good" changes semantics). Violating the independence assumption degrades probability calibration โ€” the model may classify correctly but with wrong confidences.

Evolution

Original paper ยท 1961 ยท Marvin E. Maron
Automatic Indexing: An Experimental Inquiry
Marvin E. Maron
1961
Marvin Maron publishes "Automatic Indexing" โ€” an early use of a Bayesian classifier for automatic document categorization.
1973
Duda and Hart formalize Naive Bayes in the classic textbook "Pattern Classification and Scene Analysis".
1997
Domingos and Pazzani publish "On the Optimality of the Simple Bayesian Classifier under Zero-One Loss", explaining why NB works well despite the violated independence assumption.
1998
McCallum and Nigam compare multinomial vs Bernoulli NB for text classification โ€” the paper becomes a standard NLP reference.
2002
Paul Graham publishes "A Plan for Spam" โ€” Bayesian spam filters become ubiquitous in email clients.

Computational complexity

Computational characteristics
โ†’Training complexity: O(Nยทd), where N is the number of examples and d the number of features
โ†’Prediction complexity: O(dยทC), where C is the number of classes
โ†’Memory: O(dยทC) โ€” conditional-probability table
โ†’No optimization iterations โ€” training is a single pass of frequency counts
โ†’Trivially parallelizable across features and classes
Benchmark notes

In text classification (e.g. 20 Newsgroups, Reuters-21578) multinomial Naive Bayes typically reaches 70โ€“85% accuracy, trailing logistic regression and SVMs by a few points on larger datasets. In spam filtering it historically achieved >95% precision, kickstarting the era of Bayesian email filters. It is still used as an NLP baseline in research papers.