Online Naive Bayes
- Introduced by
- Adapted from traditional Naive Bayes; incremental form established by the data-stream mining community (Domingos, Hulten, and others, circa 2000)
- Year
- 2000s
- Type
- Probabilistic classifier (online/incremental)
- Family
- Machine learning
What does it do?
Online Naive Bayes is an incremental adaptation of the classical Naive Bayes classifier that updates its class-conditional statistics one observation (or one mini-batch) at a time, making it well suited to data streams, very large datasets that cannot be held in memory, and settings where the model must adapt continuously as new labeled examples arrive.
The intuition behind the method
Classic Naive Bayes reads all training data at once, computes class priors and feature likelihoods, and then freezes its parameters. Online Naive Bayes instead maintains running counts or sufficient statistics (means, variances, feature frequencies) that are updated incrementally with each new example. Because the Naive Bayes conditional independence assumption means the likelihood factorises into per-feature terms, each feature's statistics can be updated independently and cheaply, making the model naturally suited to one-pass learning over streams without sacrificing the probabilistic prediction mechanism.
History
Naive Bayes has roots in Bayesian statistics going back to the 18th century, but its use as a text classifier was popularised in the 1990s (e.g., McCallum & Nigam, 1998). The online/incremental variant gained systematic attention with the data-stream mining community in the early 2000s, notably through work by Domingos and Hulten on mining high-speed data streams (KDD 2000). It is now a standard component of stream-processing toolkits and is exposed directly in scikit-learn through the partial_fit API.
When to use it
Use Online Naive Bayes when data arrives as a stream or is too large to load into memory at once, when fast, low-memory incremental updates are needed, or when the model must adapt continuously to new examples (e.g., text classification of live feeds, spam filtering, or event classification in IoT pipelines). It is also a strong baseline for high-dimensional sparse text data (bag-of-words, TF-IDF) in streaming settings. Do not use it when the conditional independence assumption is severely violated and there is enough data to train a more expressive model in batch mode, when features are highly correlated and capturing interactions is critical, or when class distributions are extremely imbalanced without correction.
Limitations and considerations
- The naive conditional independence assumption is rarely satisfied exactly and can hurt accuracy when features are strongly correlated.
- Cannot learn feature interactions; each feature contributes independently to the posterior.
- Concept drift requires explicit forgetting mechanisms (e.g., sliding windows, decay factors) since the default model accumulates all historical evidence.
- Gaussian Naive Bayes assumes unimodal, roughly Gaussian per-class feature distributions, which may not hold.
Source conditions do not replace independent scientific review or validation by an analysis engine.
Strengths
- Processes one example at a time with O(1) update cost per feature, making it extremely fast and memory-efficient for streaming data.
- Naturally probabilistic: outputs calibrated class-posterior probabilities, not just hard labels.
- Scales to very high-dimensional feature spaces (e.g., text) without a significant speed penalty.
- No need to store historical data; the model is defined entirely by its sufficient statistics.
- Simple to implement and reason about; the conditional independence assumption often works better than expected in practice.
Applications
- Real-time spam and phishing detection on email or message streams.
- Incremental text classification over live news feeds or social media.
- Sensor event classification in IoT systems where data arrives continuously.
- Baseline classifier for high-dimensional bag-of-words or TF-IDF feature spaces.
- Online sentiment analysis on streaming customer reviews or social posts.
- Any classification task too large to fit in memory where a fast probabilistic model is acceptable.
How it works
How it works
Class priors P(C_k) = N_k / N are initialised from whatever labeled data is available at startup (or set to uniform). The per-feature sufficient statistics — counts for categorical features, running mean and variance for Gaussian features — are initialised similarly.
Formula
P(C_k) = N_k / N
When a new labeled example (x, y) arrives, the class count N_y is incremented by one and the sufficient statistics for each feature x_i under class y are updated: counts are incremented for Bernoulli or Multinomial features, and running mean and variance are updated using Welford's online algorithm for Gaussian features. No old examples need to be re-visited.
At prediction time (or after each update), the per-feature likelihoods P(x_i | C_k) are computed from the current sufficient statistics. For Gaussian Naive Bayes the Gaussian PDF is evaluated; for Multinomial or Bernoulli variants, smoothed frequency ratios are used.
Formula
P(x_i | C_k)
The posterior probability for each class is computed as the product of the class prior and all per-feature likelihoods, then the class with the highest posterior is returned. Because logarithms are used in practice, this becomes a sum and avoids numerical underflow.
Formula
\hat{y} = \arg\max_k P(C_k) \prod_i P(x_i | C_k)Common pitfalls
- Forgetting to apply Laplace (add-one) smoothing for Multinomial/Bernoulli variants, which causes zero-probability issues for unseen feature values.
- Ignoring concept drift: without a forgetting or windowing strategy the model slowly becomes outdated on non-stationary streams.
- Using Gaussian Naive Bayes for count data (e.g., word counts) instead of Multinomial Naive Bayes.
- Treating model probabilities as perfectly calibrated without checking; isotonic regression or Platt scaling may be needed.
- Evaluating only on accuracy when class imbalance is present; use precision, recall, and F1 per class.
Frequently asked questions
How does Online Naive Bayes handle concept drift?
By default it accumulates all evidence, so it adapts slowly to drift. To react faster, apply a sliding window (only count recent examples), exponential forgetting (weight older observations less), or reset the sufficient statistics when drift is detected.
Which variant should I use — Gaussian, Multinomial, or Bernoulli?
Use Multinomial or Bernoulli Naive Bayes for text (count or binary feature vectors) and Gaussian Naive Bayes for continuous features that are approximately normally distributed within each class. The online update logic differs slightly, but all variants support incremental updates.
Is Online Naive Bayes competitive with more complex online models?
On high-dimensional sparse text, it is often competitive with online logistic regression or online SVM, with lower computational cost. On dense, lower-dimensional, or highly correlated feature sets, online logistic regression or gradient boosting typically outperform it.
How should I evaluate an online classifier?
Use prequential (test-then-train) evaluation: predict each example before updating the model, then update. This gives an unbiased estimate of streaming performance without a separate hold-out set.
Can I initialise Online Naive Bayes from a batch-trained model?
Yes. Train a batch Naive Bayes model on an initial dataset to get good starting sufficient statistics, then switch to incremental updates. This warm-start approach avoids the cold-start inaccuracy of a randomly initialised model.
Related methods
Sources
Domingos, P. & Hulten, G. (2000). Mining high-speed data streams. Proceedings of the 6th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 71–80. ACM.
Open DOI referenceCopied.Online machine learning. Wikipedia.
Open publication referenceCopied.