Concept Drift and Adaptive Windows
How a streaming learner decides which past data still applies, why a fixed window is wrong in both directions, and the detectors that size the window from the data.
A model learning from a stream faces a question no batch learner has to answer: how much of the past is still true? Keep everything and the model averages over a relationship that has changed. Keep too little and it is fitted on noise. The window is the central hyperparameter of streaming learning and the whole problem is that its correct value changes over time.
Kinds of drift
Sudden drift is a discrete change: a pricing rule changes, a sensor is replaced, a competitor launches. The old data becomes wrong at a point in time, and the right response is to discard it.
Gradual drift is a slow transition where old and new regimes coexist for a period, so a hard cut discards useful data and keeping everything dilutes the new pattern.
Incremental drift is continuous slow movement with no boundary at all, where exponential forgetting fits better than any window.
Recurring drift returns to previous regimes, seasonally or cyclically, so old data becomes relevant again and discarding it permanently is a mistake. Retaining models per regime and switching between them is the appropriate structure.
Choosing a forgetting mechanism is choosing which of these you believe you face.
ADWIN
The adaptive windowing algorithm removes the need to choose a window length by maintaining a window and testing it for change. It considers every split of the window into two sub-windows, and if the means of any two sub-windows differ by more than a statistically justified bound, it concludes the distribution changed and drops the older part.
with \(\epsilon_{\text{cut}}\) derived from a Hoeffding bound and a confidence parameter. The window grows automatically while the stream is stationary, giving more data and better estimates, and shrinks automatically when it is not, giving adaptivity. The only parameter is a confidence level, which is far more interpretable than a window length (Bifet and Gavaldà, 2007, SDM).
An efficient implementation maintains a compressed exponential histogram rather than all raw values, so memory is logarithmic in the window length.
Drift detectors on error
An alternative watches the model's own error rate rather than the input distribution. DDM signals a warning when the error rate rises a specified number of standard deviations above its running minimum, and a drift when it rises further, at which point a new model is trained on data collected since the warning. This detects exactly the drift that matters, since it is defined by degraded performance, and it requires labels promptly.
When it breaks
Detection requires labels, and labels are often delayed. Error-based detectors are the most relevant and the least available. Unsupervised detection on the input distribution is available and detects covariate shift, which may not affect performance, so it is a proxy with the usual proxy problems.
Every detector trades false alarms against delay. A sensitive setting resets the model on noise, discarding good data and degrading performance; an insensitive one adapts too late. The confidence parameter is this trade and cannot be avoided.
Rebuilding on drift discards everything. Training a fresh model after each detection throws away transferable structure, and warm-starting from the previous model adapts faster while risking carrying the stale relationship forward.
Recurring drift defeats forgetting. A system that discards old regimes relearns them from scratch each cycle. Where recurrence is expected, a pool of models with a selection mechanism outperforms any single adaptive model.
12 flashcards for this concept
Click a card to reveal the answer.