Skip to content
Back to search results

Online Bagging

Introduced by
Oza, N. C. & Russell, S.
Year
2001
Type
Online ensemble (streaming bagging)
Family
Machine learning
Font size

What does it do?

Online Bagging is a streaming ensemble method introduced by Oza and Russell in 2001 that adapts the classical bootstrap aggregating (Bagging) framework to the online learning setting.

Instead of resampling a fixed dataset, each incoming instance is fed to every base learner a Poisson(1)-distributed number of times, faithfully approximating bootstrap sampling as the stream evolves. The result is a robust, incrementally updated ensemble that can handle concept drift and continuous data arrival without storing the entire dataset.

The intuition behind the method

Classical Bagging draws random bootstrap samples from a fixed dataset and trains one tree per sample. Online Bagging mimics this without ever seeing the whole dataset at once: when a new example arrives, it is passed to each base learner a random number of times drawn from a Poisson distribution with mean 1. On average each learner sees the example once — exactly what bootstrap resampling achieves in batch mode — but the randomness de-correlates the learners. Because no data needs to be stored, the ensemble can grow indefinitely with the stream and adjust naturally to shifting distributions over time.

History

Online Bagging was introduced by Nitesh Oza and Stuart Russell at AISTATS 2001 as a theoretical and practical extension of Breiman's 1996 Bagging algorithm to the online setting. The key insight — replacing bootstrap resampling with Poisson(1) weighting per instance — made the approximation mathematically rigorous. It became a foundational algorithm in the streaming machine learning literature and is the baseline ensemble in platforms such as MOA (Massive Online Analysis), which has driven most empirical evaluations of stream classifiers since 2010.

When to use it

Use Online Bagging when data arrives as a continuous stream and storing the full dataset is infeasible or prohibited (e.g., sensor logs, clickstreams, financial tick data, real-time monitoring). It is appropriate when you need classification or regression that updates with every new observation, tolerates mild concept drift, and remains memory-efficient. Do not use Online Bagging as a drop-in replacement for batch Random Forest on a fixed, small-to-medium dataset — batch ensembles with cross-validation will outperform it there. Also avoid it when the data stream exhibits severe abrupt drift without adding an explicit drift-detection mechanism.

Limitations and considerations

  • On static datasets, batch methods such as Random Forest or XGBoost consistently outperform Online Bagging because they can use full cross-validation and optimal splits.
  • Basic Online Bagging offers only limited resilience to severe concept drift; dedicated drift detectors (e.g., ADWIN) must be added externally.
  • Poisson weighting introduces extra variance per instance, which can slow convergence on short streams.
  • Interpretability is low: the ensemble of many incrementally grown trees is harder to inspect than a single decision tree.

Source conditions do not replace independent scientific review or validation by an analysis engine.

Strengths

  • Processes data one instance at a time with constant memory, enabling truly unbounded streams.
  • Poisson weighting provably approximates bootstrap resampling, giving ensemble variance reduction comparable to batch Bagging.
  • Naturally parallelisable: each base learner updates independently, making it suitable for distributed streaming architectures.
  • No hyperparameter as sensitive as tree depth — the ensemble self-regularises through diversity.
  • Extends straightforwardly to multi-class classification and regression without structural changes.

Applications

  • Real-time fraud detection on continuous transaction streams.
  • Predictive maintenance from sensor data streams in industrial IoT settings.
  • Click-through rate prediction in online advertising where user behaviour evolves continuously.
  • Network intrusion detection on high-throughput packet streams.
  • Environmental monitoring: incremental classification of air quality or weather sensor readings.

How it works

How it works

1

For each arriving instance, a weight k is sampled independently from a Poisson(1) distribution for every base learner. A weight of 0 means the learner skips this instance entirely; a weight of 2 means it learns from the instance twice. This stochastic weighting is the online analogue of bootstrap resampling and is the mathematical core of the algorithm.

Formula
k \sim \text{Poisson}(1)
2

Each base learner — typically an incremental decision tree such as a Hoeffding Tree — receives the current instance with its assigned weight and updates its internal model immediately. No instance is stored after processing. This single-pass property keeps memory bounded and allows the ensemble to scale to arbitrarily long streams.

3

When a prediction is required, all M base learners produce their individual output for the query instance. The ensemble combines these by majority vote for classification or by arithmetic mean for regression, giving the same aggregate logic as batch Bagging but computed on incrementally trained models.

Formula
\hat{y} = \text{mode/mean of } M \text{ base learners}

Common pitfalls

  • Evaluating Online Bagging with a held-out test set created before training begins — use prequential (test-then-train) evaluation instead, which is the standard in streaming machine learning.
  • Assuming the default number of base learners (often 10) is sufficient; ensembles of at least 50–100 learners are typically needed for stable predictions.
  • Ignoring concept drift: deploying Online Bagging on a drifting stream without drift detection leads to silent degradation of accuracy.
  • Comparing accuracy on a static benchmark to batch methods and concluding Online Bagging is inferior — the correct comparison is accuracy per instance seen on a streaming benchmark.
  • Using base learners that are not truly incremental (e.g., re-trained batch trees), which negates the memory and speed advantages of the online framework.

Frequently asked questions

Why Poisson(1) specifically?

A Poisson distribution with mean 1 approximates the number of times an observation appears in a bootstrap sample of size n as n approaches infinity. Using Poisson(1) per instance per learner replicates this limiting behaviour exactly, making the online approximation theoretically sound.

How does Online Bagging differ from Adaptive Random Forest?

Adaptive Random Forest (Gomes et al., 2017) extends Online Bagging by adding random feature subsampling at each split (like batch Random Forest) and integrating per-tree drift detectors that reset individual learners when concept drift is detected. Online Bagging is the simpler foundation; Adaptive Random Forest is the current state-of-the-art streaming ensemble built on top of it.

What base learner should I use?

The most common choice is the Hoeffding Tree (also called VFDT), which is the canonical incremental decision tree. It uses Hoeffding bounds to decide when enough data has been seen at a node to split, keeping the tree updatable without storing past instances.

How many base learners do I need?

Empirical benchmarks in the MOA framework suggest 50–100 base learners for stable ensemble performance on most streaming tasks. Fewer learners reduce compute cost but increase prediction variance, especially early in the stream.

How should I evaluate an Online Bagging classifier?

Use prequential evaluation: for each incoming instance, first predict its label, then update the model. Accuracy is computed as the running average of correct predictions. This avoids any look-ahead bias and reflects true deployment conditions.

Related methods

Sources

  1. Oza, N. C., & Russell, S. (2001). Online bagging and boosting. In Proceedings of the Eighth International Workshop on Artificial Intelligence and Statistics (AISTATS 2001), pp. 105–112.

    Open publication reference
    Copied.
  2. Bifet, A., Holmes, G., Kirkby, R., & Pfahringer, B. (2010). MOA: Massive Online Analysis. Journal of Machine Learning Research, 11, 1601–1604.

    Open publication reference
    Copied.