PaperlayerView exact revision on arXiv

Source-linked AI summary

Concept Drift Detection for Streaming Data

Heng Wang, Zubin Abraham

arXiv:1504.01044v2stat.MLcs.LG

TL;DR

Changes in the joint distribution of predictors and response can undermine prediction models, while conventional detectors may miss important drift in imbalanced classification. LFR monitors four classifier rates and identifies examples associated with a new concept; across drift types, it is reported to outperform benchmark approaches on detection performance.

  • Problem

    In binary classification, drift can change the joint predictor-response distribution while leaving overall error unchanged, causing DDM to miss a drastic minority-class recall drop.

    Source: §I · p. 1

  • Method

    LFR monitors four classifier rates with a drift-detection framework that works with batches or streams and identifies examples from the new concept for relearning.

    Source: §I · p. 2, 1) Algorithm Outline · p. 3, §V · p. 9

  • Results

    LFR significantly outperforms benchmark approaches across drift types in early detection, detection rate or recall, and false-alarm performance.

    Source: §I · p. 2, 2) Imbalanced Dataset · p. 6, §V · p. 9

  • Takeaways & Limitations

    LFR’s rate-based monitoring can detect varied concept drifts, including cases where minority-class recall remains unchanged, and supports relearning from new-concept examples.

    Source: §V · p. 9

Abstract

from arXiv · show

Common statistical prediction models often require and assume stationarity in the data. However, in many practical applications, changes in the relationship of the response and predictor variables are regularly observed over time, resulting in the deterioration of the predictive performance of these models. This paper presents Linear Four Rates (LFR), a framework for detecting these concept drifts and subsequently identifying the data points that belong to the new concept (for relearning the model). Unlike conventional concept drift detection approaches, LFR can be applied to both batch and stream data; is not limited by the distribution properties of the response variable (e.g., datasets with imbalanced labels); is independent of the underlying statistical-model; and uses user-specified parameters that are intuitively comprehensible. The performance of LFR is compared to benchmark approaches using both simulated and commonly used public datasets that span the gamut of concept drift types. The results show LFR significantly outperforms benchmark approaches in terms of recall, accuracy and delay in detection of concept drifts across datasets.

I. INTRODUCTION

Concept drift challenges prediction models that assume stationarity, and existing detectors can miss important changes or be unsuitable for instant stream decisions. LFR is introduced to detect drift across varied settings, including imbalanced data.

I. INTRODUCTION

  • DDM can miss a threefold minority-class true positive rate decrease, from 0.75 to 0.25, when overall error does not change.This can leave a critical drop in defective-product detection unnoticed.Source: §I · p. 1
  • DDM-OCI assumes imbalanced-class drift changes minority-class recall, but drift can leave TPR, PPV, and F1 unchanged and still trigger false alarms.Such a drift may be detectable only if rates such as TNR or NPV are also considered.Source: §I · p. 1
  • EDDM and PerfSim are poorly suited to instant stream decisions because they require accumulating errors or collecting mini-batches before computing statistics,.An SVM-based approach also computes its measures assuming batch-arriving data.Source: §I · p. 1
  • LFR is presented to detect concept drift across variants, including imbalanced labels, with earlier detection, fewer false alarms, and better recall than existing approaches.It does not require batch-arriving data or depend on the underlying classifier.Source: §I · p. 2

II. PROBLEM FORMULATION

The paper frames binary-classification concept drift as change in the joint distribution of predictors and response. It motivates monitoring the classifier’s predicted labels and true labels as a lower-dimensional signal of that change.

II. PROBLEM FORMULATION

  • Concept drift in this setting is a change over time in the joint distribution P(X_t, y_t), where X_t contains predictors and y_t is binary.Testing the full multivariate stream can lose statistical power when predictor dimension is very large or drift magnitude is small.Source: §II · p. 2
  • The proposed approach monitors changes in P(f̂(X_t), y_t), because drift in that classifier-output distribution implies drift in P(X_t, y_t) with probability 1.This is presented as an alternative to testing the full multivariate variable (X_t, y_t),,.Source: §II · p. 2
  • A 2 × 2 confusion probability matrix represents the classifier’s joint outcomes for predicted and actual labels.Its cells correspond to true positives, true negatives, false positives, and false negatives.Source: §II · p. 2
  • The four monitored rates are TPR, TNR, PPV, and NPV, each computed from the relevant confusion-matrix counts.Under a stable concept, the rates remain unchanged; a significant rate change implies a change in the joint distribution of actual and predicted labels.Source: §II · p. 2

III. CONCEPT DRIFT DETECTION FRAMEWORK

The framework treats the four classifier rates as test statistics and tests them continuously at each time step. User-defined warning and detection significance levels determine when evidence signals a possible or confirmed drift.

III. CONCEPT DRIFT DETECTION FRAMEWORK

  • The framework uses estimators of TPR, TNR, PPV, and NPV as test statistics for hypothesis tests at each time step.A stable concept is the null hypothesis; rejecting it indicates drift.Source: §III · p. 2
  • Warning and detection significance levels are compared with running test significance at every time step, making all timestamps decision points.With fixed decision spacing, Bonferroni-style simultaneous inference can control the familywise error rate.Source: §III · p. 2
  • The naive four-rate version uses empirical rate estimates, while LFR uses different estimators; both frameworks are described as outperforming DDM and DDM-OCI.The stated advantage is attributed to the more comprehensive detection framework.Source: §III · p. 2

A. Linear Four Rates algorithm (LFR)

LFR monitors four classifier rates with geometrically weighted statistics and simulation-derived bounds. It uses warning and detection signals to identify drift and extract examples from the new concept for model relearning.

A. Linear Four Rates algorithm (LFR)

  • LFR uses modified running statistics for the four rates, geometrically weighting recent classifier performance more heavily than historical performance.The statistics emphasize recent predictions and are described as more sensitive to drift than the naive rate estimates.Source: 1) Algorithm Outline · pp. 2–3
  • Monte Carlo samples approximate the statistic’s distribution under a stable concept; quantiles provide the warning and detection bounds.The underlying rate is estimated with P̂⋆ as a surrogate when generating the empirical distribution.Source: 1) Algorithm Outline · p. 3, 2) Analysis · p. 4
  • Users set time-decay, warning, and detection significance levels for each rate, and can prioritize rates independently.Warning significance δ⋆ exceeds detection significance ϵ⋆; distinct ϵ⋆ values allow different priorities across rates.Source: 1) Algorithm Outline · pp. 2–3
  • Crossing a warning bound marks a possible drift, while reaching a detection bound confirms it and triggers relearning from examples between the warning and detection times.If a warning does not progress to detection, the warning flag is erased; after detection, the monitoring cycle resets.Source: 1) Algorithm Outline · p. 3
  • Under a stable concept, the running statistic is a geometrically weighted sum of Bernoulli outcomes with underlying rate P⋆.The paper also states that the empirical rate estimator is the unique UMVUE under this stable-concept setting.Source: 2) Analysis · pp. 3–4
  • LFR takes O(1) time per monitored point when precomputed bounds are stored in a lookup table.The table avoids quantile calculations during stream monitoring.Source: 2) Analysis · p. 4

B. Na¨ıve Four Rates algorithm (NFR)

NFR sequentially monitors four estimated rates and raises warning or detection alarms when they exceed expected bounds. Its estimator gives greater weight to older predictions, and is MSE-consistent under a stable concept.

B. Na¨ıve Four Rates algorithm (NFR)

C. Comparison between NFR and LFR

LFR and NFR trade off detection power across time lags: LFR favors earlier detection, while NFR can have greater power at longer lags. The comparison also examines limiting power across drift magnitudes.

C. Comparison between NFR and LFR

  • In one synthetic-stream run, LFR detected drift at t = 5167 against a true drift point of t = 5000, earlier than NFR.Figure 1 marks the true drift time and the LFR and NFR detection times.Source: C. Comparison between NFR and LFR · p. 5, Figure 1 · p. 5
  • For small time lags LFR has greater power, but for large lags NFR has greater power; the crossover reflects LFR’s larger variance.LFR’s update rule shifts its estimator toward the new rate at an exponential rate, boosting short-lag power; larger limiting variances degrade power at long lags when the rate change is small.Source: C. Comparison between NFR and LFR · pp. 5–6
  • Except when p⋆ = q⋆, LFR has greater power at small K and NFR has greater power at large K, favoring LFR when earlier detection matters.The authors note that earlier detection allows observers to adjust the model and avoid costs of incorrect predictions immediately.Source: C. Comparison between NFR and LFR · p. 6
  • At K = 200, LFR’s estimated limiting power is close to 1 when p⋆ and q⋆ differ substantially.Figure 4 presents the estimates across (p⋆, q⋆) pairs.Source: C. Comparison between NFR and LFR · p. 6, Figure 4 · p. 6

IV. EXPERIMENTS

The experiments compare LFR with NFR, DDM, and DDM-OCI on simulated and public datasets. Across the tested cases, LFR more often detects true drift points with fewer false alarms than NFR, even at a smaller detection significance level.

IV. EXPERIMENTS

  • The comparison covers LFR, NFR, DDM, and DDM-OCI across synthetic data and public datasets.The experiments include varied concept-drift types, including cases where baseline approaches perform poorly.Source: §IV · p. 6
  • The evaluation bootstraps 100 streams for each synthetic dataset and 100 permuted streams for each public dataset, then feeds each stream to every detector.Detection timestamps across the runs are visualized with overlapping histograms.Source: §IV · p. 6
  • Across synthetic and public datasets, LFR correctly identifies more true drift points with higher probability and fewer false alarms than NFR, even with a smaller ϵ⋆.The study considers three simulated class-balance datasets, three simulated class-imbalance datasets, and four public datasets spanning varied drift types.Source: §IV · p. 6

A. Synthetic Data

The synthetic experiments construct balanced and imbalanced streams with concept changes and assess whether detectors identify their change points. LFR performs well in an imbalanced scenario where DDM and DDM-OCI do not detect drift.

A. Synthetic Data

  • The synthetic evaluation generates streams with a change point at T/2 and considers six balanced and imbalanced scenarios.Balanced streams require equal class probabilities; imbalanced scenarios alter the class ratio.Source: A. Synthetic Data · p. 6, 1) Balanced Dataset · p. 6, 2) Imbalanced Dataset · p. 6
  • Balance1 changes overall accuracy while leaving TPR unchanged, and Balance2 has gradual drift while overall accuracy remains unchanged.Figures 5 and 6 show overlapping histograms of detection timestamps for these scenarios.Source: 1) Balanced Dataset · p. 6, Figure 5 · p. 7, Figure 6 · p. 7
  • For Imbalance1, LFR shows high early detection and trivial false alarms, while DDM and DDM-OCI produce no detection after the change point.In this scenario, the minority class changes while TPR and PPV remain unchanged; the passage notes that F1-based detectors cannot alarm on this drift.Source: 2) Imbalanced Dataset · p. 6
  • Imbalance2 keeps the class ratio and error rate unchanged, while Imbalance3 decreases TPR, PPV, and 1 − Perror.The supplied passages name these scenario conditions but do not report their detector outcomes.Source: 2) Imbalanced Dataset · p. 7

B. Public Datasets

Across public datasets, the experiments compare drift-detection timing and errors; LFR generally leads, though weaker USENET2 drift is detected with longer lag.

V. CONCLUSION

LFR detects concept drift and identifies data points from the new concept. Across drift types, it significantly outperforms benchmark approaches in early detection, detection rate, and false alarms.

  • Across drift types, LFR significantly outperformed benchmarks in early detection, high detection rate, and low false-alarm rate.Source: §V · p. 9
  • LFR detects concept drift and identifies data points belonging to the new concept.Source: §V · p. 9
  • LFR applies to batch and stream datasets, including imbalanced datasets, and is independent of the underlying statistical model.Source: §V · p. 9
  • LFR uses user-specified parameters described as intuitively comprehensible.Source: §V · p. 9
Loading 1504.01044v2…