Adaptive Ensembles for Evolving Streams

A single adaptive model faces a binary choice the moment its drift detector fires: keep the current model and risk serving a stale relationship, or reset and serve something that has seen almost no data. Neither is good, and the detector is sometimes wrong. An ensemble turns that decision into a vote, which is the main reason the leaderboards for evolving-stream classification are dominated by ensembles rather than by single learners.

Bootstrap without a dataset

Batch bagging draws \(N\) examples with replacement from a dataset of size \(N\), so each base learner sees a given example \(k\) times where \(k\) is Binomial\((N, 1/N)\). As \(N\) grows that converges to Poisson(1). Online bagging exploits the limit directly: as each example arrives, every member trains on it with weight \(k \sim \text{Poisson}(1)\), so roughly 37 percent of members skip it, 37 percent see it once, and the rest see it repeatedly (Oza and Russell, 2001, Online Bagging and Boosting, AISTATS). No dataset, no resampling pass, same diversity mechanism.

Leveraging Bagging raises the Poisson parameter to \(\lambda = 6\) to push resampling harder, adds output randomisation through error-correcting codes, and gives each member an ADWIN detector so individual members reset independently. It was evaluated on streams up to ten million examples (Bifet, Holmes and Pfahringer, Leveraging Bagging for Evolving Data Streams, ECML PKDD 2010, LNCS 6321:135-150).

The warning state, and why it matters

Adaptive Random Forest is the design most people reach for. It combines Hoeffding trees, subspace randomisation applied locally at each split, and per-tree drift detection with two thresholds (Gomes et al., 2017, Adaptive Random Forests for Evolving Data Stream Classification, Machine Learning 106(9-10):1469-1495).

The two thresholds are the interesting part. When a tree's detector crosses the warning level, the forest starts a background tree for it and trains that tree on everything arriving from then on. When the detector crosses the drift level, the background tree replaces the incumbent. By then the replacement has been learning for however long the warning lasted, so the swap does not create a hole in the ensemble. A single model that resets on detection has no equivalent move: it serves an untrained model for exactly as long as retraining takes. Votes are weighted by each tree's own prequential accuracy, so a member that is losing its grip is discounted before its detector fires.

Streaming Random Patches makes the subspace choice global rather than per-split: each member gets one random subset of features plus Poisson-weighted resampling, which the authors show behaves differently from the local randomisation inside a random forest (Gomes, Read and Bifet, Streaming Random Patches for Evolving Data Stream Classification, IEEE ICDM 2019). It trades some speed for accuracy, and the extended treatment appeared in Knowledge and Information Systems in 2021.

When it breaks

The cost is linear in members and it is paid per example. A 100-tree forest is 100 counter updates and 100 traversals per arrival, and 100 trees of leaf statistics in memory. Streaming systems exist because the per-example budget is small, and an ensemble spends it a hundred times over. This is the single most common reason a published ensemble does not reach production.

False alarms compound. A detector that fires spuriously once per million examples per member fires a hundred times more often across a hundred members. Each false alarm throws away one member's learned structure. The ensemble absorbs this better than a single model does, which is a genuine benefit, but the waste is real and grows with the ensemble size.

Diversity decays. Members trained on the same stream with the same base learner converge toward each other. Poisson weighting and subspace selection slow this; they do not stop it. A long-running ensemble gradually becomes an expensive single model, and nothing in the standard metrics reveals that.

Everything here needs prompt labels. Per-member detectors watch each member's error, which requires the true label soon after the prediction. Where labels arrive weeks later, the detectors are measuring a distribution that is weeks stale and the warning state buys nothing (Gama et al., 2014, A Survey on Concept Drift Adaptation, ACM Computing Surveys 46(4):44).

No guarantees come with any of this. The regret bounds of online convex optimisation do not transfer to an ensemble of adaptive trees with reset policies. These methods are justified entirely by prequential benchmarks, mostly on synthetic generators, and the ranking between them shifts with the stream.