Source-linked AI summary
Exponentially Weighted Moving Average Charts for Detecting Concept Drift
Gordon J. Ross, Niall M. Adams, Dimitris K. Tasoulis, David J. Hand
TL;DR
Concept drift detection in streaming classification requires computationally efficient methods that can adapt to changing distributions while controlling false positives. ECDD uses an EWMA chart to monitor classification errors, operates online with O(1) overhead, and performs competitively with other methods.
Problem
Streaming classifiers need drift detection methods that handle changing distributions efficiently and provide an indication when drift occurs.
Method
ECDD monitors a classifier’s binary error stream with an EWMA chart, using online control limits and optional warning thresholds.
Results
ECDD performs similarly to PC and SPRT, while incorporating warning thresholds improves its performance further.
Takeaways & Limitations
ECDD can be incorporated into streaming classifiers without storing data and allows the false-positive detection rate to be controlled.
Takeaways & Limitations
On real data, ECDD’s false-positive rate can be controlled, whereas suitable ARL0 values for PC and SPRT lack an obvious determination without known change points.
Abstract
from arXiv · showhide
Classifying streaming data requires the development of methods which are computationally efficient and able to cope with changes in the underlying distribution of the stream, a phenomenon known in the literature as concept drift. We propose a new method for detecting concept drift which uses an Exponentially Weighted Moving Average (EWMA) chart to monitor the misclassification rate of an streaming classifier. Our approach is modular and can hence be run in parallel with any underlying classifier to provide an additional layer of concept drift detection. Moreover our method is computationally efficient with overhead O(1) and works in a fully online manner with no need to store data points in memory. Unlike many existing approaches to concept drift detection, our method allows the rate of false positive detections to be controlled and kept constant over time.
1. Introduction
Streaming classification requires online methods that process high-volume, time-ordered data efficiently while adapting to changing optimal classification rules. The proposed ECDD approach detects abrupt concept drift from classifier errors using a modular, single-pass EWMA-based detector with O(1) overhead and controllable false positives.
- Streaming classification: Streaming methods process time-ordered data arriving too quickly and abundantly for conventional statistical methods, requiring computational efficiency.The criteria include processing each point once, discarding it rather than storing it, and keeping update complexity constant.
- Concept drift: Concept drift occurs when the optimal classification rule changes with stream dynamics; this paper assumes abrupt changes while briefly considering gradual drift experimentally.Streaming classifiers must adapt so that drift does not cause a significant performance decrease.
- Limitations of existing detectors: Existing drift detectors are often non-single-pass, computationally growing, or unable to control their false-positive rate.These limitations make them unsuitable for frequent, large-volume streams and complicate judging whether detected changes are genuine.
- Proposed approach: ECDD converts classifier correctness feedback into a Bernoulli error stream and detects increases in its misclassification probability beyond sampling variability.The method targets two-class classification, with extension to multiple classes identified as possible.
- Proposed approach: The approach is single pass, adds only O(1) overhead, and allows the false-positive detection rate to be controlled.The paper adapts EWMA change detection to concept drift rather than requiring classifier-specific intrinsic properties.
- Proposed approach: The detector uses an EWMA chart and can operate alongside any classifier because it relies only on the classifier’s error stream.The underlying classifier is treated as a black box, enabling modular deployment with decision trees, neural networks, or support vector machines.
2. Background
The paper applies EWMA monitoring to Bernoulli misclassification errors, using recent weighted estimates to detect abrupt increases in error probability. A control limit determines when deviation from the pre-change level is large enough to flag drift, with assumptions about pre- and post-change error rates.
- EWMA background: EWMA charts detect increases in the mean of a random-variable sequence by comparing observations before and after a change point.The standard formulation initially assumes the pre-change mean and stream standard deviation are known.
- EWMA background: The EWMA estimator forms a recent estimate by progressively downweighting older observations, with λ controlling the emphasis on recent data.Its mean and standard deviation can be derived independently of the distribution of the observations.
- EWMA change detection: Before a change, Z_t fluctuates around µ_0; after the mean changes to µ_1, Z_t moves away from µ_0 toward µ_1.This movement provides the basis for detecting a change.
- EWMA change detection: The control limit L specifies how far Z_t must diverge from µ_0 before the EWMA chart flags a change.L is selected to achieve a desired Average Run Length, where ARL_0 measures expected time between false positives.
- Bernoulli EWMA: For classification, the error stream is modeled as Bernoulli variables whose parameter p_t is the probability of misclassification, so drift becomes an increase in p_t.The paper assumes p_t takes p_0 before the change and p_1 afterward, and focuses on drift that increases error rate.
- Bernoulli EWMA: In the Bernoulli setting, a change in p_t also changes the standard deviation, requiring separate pre-change and post-change standard deviations.The pre-change EWMA standard deviation follows from elementary Bernoulli-distribution properties.
3. Concept Drift Detection
The method estimates the pre-change error rate online, uses EWMA sensitivity to detect changes, and selects time-varying control limits to maintain a desired false-positive rate. Polynomial approximations make this control-limit selection fast during monitoring.
- EWMA estimation: The ˆp0,t estimator uses all observations equally and represents the pre-change error rate, while Zt emphasizes recent observations and responds faster to changes.The two estimators separate a slowly changing baseline from a responsive current estimate.
- EWMA estimation: The detector flags drift when the distance between the responsive and pre-change estimators exceeds a threshold based on the EWMA standard deviation.The standard deviation is estimated after substituting the online error-rate estimate for the unknown pre-change rate.
- Control limits: A constant false-positive rate requires a time-varying control limit Lt when p0 is unknown, because the stream variance depends on the estimated pre-change error rate.Repeated Monte Carlo recalculation at every update would be too computationally expensive.
- Parameter choice: The usual recommendation is λ ∈[0.1, 0.3], and the paper uses λ = 0.2 as suitable across a wide range of drift-detection problems.The optimal value depends on pre- and post-change error rates, which are usually unknown in advance.
- Control limits: Polynomial approximations map estimated p0 to control limits for a desired ARL0, with the approximation computed once before monitoring and lookup requiring O(1) time.A degree 7 polynomial is reported as adequate for an accurate fit.
- Control limits: The lookup functions apply across base classifiers and data streams without recomputation for each monitoring task.Classifiers with the same misclassification rate receive the same threshold from the table.
4. The Complete ECDD Algorithm
ECDD processes each classification error online, updates its estimators, selects a control limit for the desired ARL0, and flags drift when the EWMA exceeds that limit. ECDD-WT adds a warning threshold that retains recent observations for possible classifier retraining.
- ECDD: ECDD converts each prediction into Xt, updates the online error-rate and standard-deviation estimates, and selects Lt from a polynomial table for the current estimated p0.The procedure then updates Zt and tests it against the control limit.
- ECDD: ECDD flags concept drift when Zt > ˆp0,t + LtˆσZt.The subsequent classifier response depends on the particular classifier; the paper assumes a complete reset for its experiments.
- Warning threshold: After a warning threshold Wt = 0.5Lt is crossed, subsequent observations are retained and used to retrain the classifier if drift is later flagged.This implementation is called ECDD-WT.
- Warning threshold: The choice W = 0.5 is empirically motivated and may be changed because it represents an assumption about how long drift takes to detect.Higher W is associated with quickly detected, larger drifts, while lower W suits longer detection delays.
5. Experiments
Experiments compare ECDD with PC and SPRT across synthetic, gradual-drift, and real data using streaming LDA and KNN classifiers. ECDD is competitive while offering low overhead and controllable false positives, though detector performance depends on the drift regime and false-positive rate.
- Experimental setup: ECDD, PC, and SPRT were evaluated on synthetic and real data with streaming LDA and KNN base classifiers.The experiments also consider gradual drift and compare detector parameter settings through ARL0.
- Computational cost: ECDD has low computational overhead, while PC is much more costly unless the underlying classifier has a special form.This constrains the situations in which PC can be deployed.
- Synthetic data: Any concept drift detector substantially improves classification over unsupported base classifiers, but the preferred ARL0 depends on change timing.ARL0 = 600 performs better when changes occur after 200 observations, whereas ARL0 = 100 performs better after 50 observations because fewer false positives occur before the change.
- Synthetic data: ECDD gives similar performance to PC and SPRT, while warning thresholds improve its performance further.The reported comparisons did not optimize ARL0 for any detector.
- Gradual Drift: ECDD is competitive with SPRT on gradual drift but is outperformed by PC, whose advantage must be weighed against higher overhead and uncontrolled false positives.The comparison is reported for modified GAUSS and SINE streams with gradual drift.
- Real-world data: On Electricity data, concept drift detection significantly improves accuracy for both LDA and KNN, with KNN achieving greater accuracy.The reported results also state that all three methods have identical performance under their best parameter settings.
6. Conclusions
ECDD detects concept drift in streaming classification using an EWMA chart over classification errors, while remaining modular, online, and computationally efficient.
- ECDD detects concept drift from a classifier’s error stream using an Exponentially Weighted Moving Average chart.
- The method can run with any streaming classifier that provides feedback about prediction correctness.
- ECDD requires no stored data and adds only O(1) overhead to the classifier.
- The approach controls the rate of false-positive concept-drift detections in a way other approaches do not.
- Experimental analysis found that ECDD performs competitively with other state-of-the-art methods.