PaperlayerView exact revision on arXiv

Source-linked AI summary

On the Reliable Detection of Concept Drift from Streaming Unlabeled Data

Tegjyot Singh Sethi, Mehmed Kantardzic

arXiv:1704.00023v1stat.MLcs.AIcs.LG

TL;DR

Concept drift can make classifiers obsolete, but supervised detection depends on costly labels and unsupervised feature monitoring can generate false alarms. The paper proposes MD3, which tracks classifier-margin uncertainty in unlabeled streams. Across drift-induced and cybersecurity datasets, MD3 achieved performance close to labeled detection while substantially reducing labeling and false alarms.

  • Problem

    Concept drift can degrade classifier performance, while supervised detection requires costly labels and unsupervised feature monitoring may signal changes irrelevant to classification.

  • Method

    MD3 incrementally monitors the number of unlabeled samples in a classifier’s uncertainty region, using margin density to signal drift.

  • Results

    MD3 produced less than 1% average accuracy difference from fully labeled detection on six drift-induced datasets and reduced false alarms by 71% on average versus HDDDM.

  • Takeaways & Limitations

    MD3 provides a label-efficient, incremental drift-detection scheme applicable across classifiers and domains, including adversarial cybersecurity streams.

  • Takeaways & Limitations

    MD3 performs poorly with L1-penalized logistic regression because feature minimization violates its premise of detecting coupled feature changes.

Abstract

from arXiv · show

Classifiers deployed in the real world operate in a dynamic environment, where the data distribution can change over time. These changes, referred to as concept drift, can cause the predictive performance of the classifier to drop over time, thereby making it obsolete. To be of any real use, these classifiers need to detect drifts and be able to adapt to them, over time. Detecting drifts has traditionally been approached as a supervised task, with labeled data constantly being used for validating the learned model. Although effective in detecting drifts, these techniques are impractical, as labeling is a difficult, costly and time consuming activity. On the other hand, unsupervised change detection techniques are unreliable, as they produce a large number of false alarms. The inefficacy of the unsupervised techniques stems from the exclusion of the characteristics of the learned classifier, from the detection process. In this paper, we propose the Margin Density Drift Detection (MD3) algorithm, which tracks the number of samples in the uncertainty region of a classifier, as a metric to detect drift. The MD3 algorithm is a distribution independent, application independent, model independent, unsupervised and incremental algorithm for reliably detecting drifts from data streams. Experimental evaluation on 6 drift induced datasets and 4 additional datasets from the cybersecurity domain demonstrates that the MD3 approach can reliably detect drifts, with significantly fewer false alarms compared to unsupervised feature based drift detectors. The reduced false alarms enables the signaling of drifts only when they are most likely to affect classification performance. As such, the MD3 approach leads to a detection scheme which is credible, label efficient and general in its applicability.

1. Introduction

Concept drift can degrade classifiers in changing data streams, while labeled detection is costly and existing unlabeled methods often raise false alarms by ignoring model-specific relevance. The paper proposes MD3, which monitors classifier uncertainty through margin density for incremental, unlabeled drift detection.

  • Concept drift changes data distributions and can degrade classifier performance over time, requiring detection and adaptation.
  • Continuous labeling for drift detection is impractical in streaming environments because it is time consuming, expensive, and sometimes unavailable.
  • Existing unlabeled detectors monitor feature-distribution changes without accounting for whether those changes affect the learned classifier’s performance.
  • MD3 uses the number of samples in a classifier’s uncertainty region, or margin, as an unlabeled signal for concept drift.
  • The paper extends margin-density drift detection across explicit-margin classifiers, ensembles, and classifiers such as decision trees, while introducing controlled drift induction and cybersecurity evaluations.

2. Review of research on concept drift detection

Prior drift detectors divide into supervised methods that monitor labeled performance and unsupervised methods that monitor unlabeled feature changes. The review covers sequential, statistical-process-control, window-based, and permutation-based approaches, along with their operating principles and trade-offs.

  • Supervised drift detectors monitor labeled performance metrics such as accuracy and F-measure, whereas unsupervised detectors monitor deviations in unlabeled feature values.
  • Sequential analysis methodologies: CUSUM and Page-Hinckley incrementally accumulate deviations in a univariate performance metric and signal alarms after threshold crossings.
  • Statistical Process Control: DDM, EDDM, STEPD, and EWMA monitor error rates, inter-error distances, accuracy differences, or moving averages to detect performance changes.
  • Window-based approaches: Window-based methods compare recent chunks or sliding windows with reference data, while ADWIN changes window length according to observed deviations.
  • Permutation-based methods: Permutation-based detection uses differences between training and testing accuracy within data chunks as evidence of non-stationarity.

2.2. Implicit drift detection methodologies

Implicit drift detectors use unlabeled data to identify changes, but their signals differ in what they monitor and how closely they reflect classification behavior. Novelty, multivariate distribution, and model-dependent methods each have important applicability or false-alarm limitations.

  • 2.2.1. Novelty detection / Clustering based methods: Novelty detectors use distance, density, or clustering to identify previously unseen regions and flag suspicious samples for evaluation.OLINDDA, MINAS, and DETECTNOD exemplify this family; some methods store, cluster, merge, or add emerging profiles.
  • 2.2.1. Novelty detection / Clustering based methods: Clustering-based novelty methods suffer from the curse of dimensionality and are mainly suitable for drifts that form new, clusterable regions.They are also problematic for binary data spaces, although they can support multiclass settings where classes appear or disappear.
  • 2.2.2. Multivariate distribution monitoring methods: Multivariate distribution monitors compare summarized feature distributions across data chunks using measures such as Hellinger distance, KL-divergence, correlation, or likelihood criteria.PCA-based approaches reduce the feature space monitored for computational efficiency in high-dimensional streams.
  • 2.2.2. Multivariate distribution monitoring methods: These feature-based methods can produce significant false alarms and miss drifts where P(Y|X) changes without a corresponding change in P(X).They are also ineffective for tracking minority-class changes in imbalanced datasets because those samples form a small share of the data.
  • 2.2.3. Model dependent drift detection methodologies: Model-dependent detectors monitor classifier posterior probabilities or margin uncertainty, reducing drift detection to a univariate stream for probabilistic models.They reduce false alarms but are limited by their dependence on probabilistic models and can react to changes away from the classifier margin.

2.3. Unlabeled drift detection in adversarial classification

Unlabeled drift detection is particularly useful in adversarial classification, where an attacker may initiate drift to subvert a system. Ensemble disagreement and margin-density signals provide ways to identify such changes without relying solely on labels.

  • 2.3. Unlabeled drift detection in adversarial classification: Unlabeled drift detection can serve as an automated early warning system when attackers initiate concept drift to subvert adversarial classification systems.The paper situates this use case alongside ensemble-based techniques that signal changes through model disagreement.
  • 2.3. Unlabeled drift detection in adversarial classification: Feature-bagged ensembles characterize adversarial activity by monitoring classifier agreement, with drift shifting agreement disproportionately toward the center of the [0,1] range.The cited malicious-PDF classification work links drift with changes in ensemble agreement scores.
  • 2.3. Unlabeled drift detection in adversarial classification: MD3 incorporates learned classifier information into unlabeled drift detection, aiming to signal changes that can affect classification while producing fewer false alarms.The approach is presented as combining label efficiency with the performance relevance associated with explicit drift detectors.

3. The Margin Density (MD) measure

Margin Density measures how many samples fall in a robust classifier’s uncertainty region, using explicit margins or ensemble disagreement. Changes near the classification boundary focus detection on distribution shifts most relevant to classification and reduce false alarms from irrelevant changes.

  • Motivation: Tracking samples near the classifier boundary emphasizes important features and their interactions instead of weighting changes in all features equally.This targets changes most connected to the learned separating boundary.
  • Margin density is the expected number of samples within a robust classifier’s region of uncertainty, or margin.
  • Classifiers with explicit margins: For SVMs, the margin is defined by parallel boundaries around the separating hyperplane, while soft constraints allow some samples inside it.The linear soft-margin SVM learns a boundary with margin width 2/||w||.
  • Classifiers without explicit margins: For feature-bagged ensembles, high disagreement among models represents uncertainty and contributes samples to the margin density.The ensemble can contain heterogeneous classifier types, making the approach independent of the classification algorithm.
  • Change in Margin Density as an indicator of drift: 19% and 50% error increases for SVM and RS respectively accompanied the boundary-affecting A0-A1 drift, while margin density changed by 0.47.For equal-magnitude shifts, MD ignored movement away from the margin but detected movement toward it; feature tracking produced the same ∆HD of 0.58 for both.
  • Change in Margin Density as an indicator of drift: Tracking the absolute margin-density change detects both increases and decreases, including decreases caused by initially high margin density.The C0-C1 scenario demonstrates why |∆MD| is needed rather than only positive spikes.

4. The Margin Density Drift Detection (MD3) algorithm

MD3 incrementally monitors changes in margin density over an unlabeled stream against a reference distribution. When a significant change is suspected, limited labeling confirms whether concept drift occurred and whether retraining is needed.

  • The algorithm continuously receives unlabeled samples, predicts labels, and computes a margin-inclusion signal for each sample.The signal indicates whether the current sample falls within the classifier’s margin.
  • MD3’s robustness to irrelevant changes reduces the need for frequent confirmation, making labeling primarily necessary for retraining.
  • MD3 starts with an initially trained classifier and a reference distribution containing expected margin-density and performance characteristics.The reference distribution is learned from the initial labeled training data.
  • When a significant drift is suspected, MD3 requests labels for Ntrain samples and uses an accuracy drop to confirm concept drift and trigger retraining.After retraining, a new reference distribution is learned from the labeled samples using K-fold cross-validation.
  • A moving-average formulation updates margin density incrementally using a forgetting factor λ and the current sample’s margin signal.The forgetting factor is computed as λ = (N −1)/N from the chunk-of-influence parameter N.

5. Experimental evaluation

The paper evaluates MD3 experimentally on controlled drift-induced datasets and real-world drifting data to assess its practical drift-detection behavior.

  • The evaluation uses drift-induced datasets for controlled analysis and real-world drifting data to demonstrate practicality.Comparisons include fully labeled accuracy tracking and the HDDDM unlabeled feature-tracking approach.

5.1. Experimental methods and setup

The experiments compare labeled, unlabeled feature-based, and MD3 detectors under a common incremental monitoring setup. MD3 is tested with both an SVM’s explicit margin and a random-subspace ensemble’s uncertainty region.

  • Compared drift detectors: NoChange assumes stationarity, never signals drift, never updates the model, and requests no labels.It serves as the lower baseline.
  • Compared drift detectors: AccTr assumes every predicted sample is labeled and tracks accuracy explicitly as the upper baseline for drift handling.An unlabeled detector is considered effective when its performance is close to AccTr.
  • Compared drift detectors: MD3-SVM computes margin density by tracking samples inside the margin of a linear-kernel SVM with hinge loss.
  • Compared drift detectors: MD3-RS uses 20 C4.5 trees, each trained on 50% of randomly selected features, and treats confidence below 0.5 as margin membership.
  • Compared drift detectors: HDDDM tracks average Hellinger distance between feature distributions and signals change when the distance exceeds a threshold.It represents traditional unlabeled feature-tracking approaches.
  • Experimental setup: All approaches use an incremental moving-average formulation so differences in detection are not attributed to the underlying classification process.The initial 15% of each stream is labeled for training and reference metrics; reference distributions use 5-fold cross-validation for AccTr and MD3.
  • Experimental setup: The metric update uses a method-specific signal: classification error for AccTr, margin inclusion for MD3, and chunk-based histogram processing for HDDDM.

5.2. Experiments on drift induced datasets

Controlled experiments on six drift-induced UCI datasets show that MD3 detects performance-relevant drift while limiting false alarms. Its accuracy tracks the fully labeled baseline closely after retraining.

  • Experimental setup: Six UCI datasets were preprocessed and subjected to controlled concept-drift induction for evaluating detection behavior.The experiments varied both drift location and feature importance, including relevant and irrelevant changes.
  • Experimental setup: The detectability experiments rotated the top 25% of features, producing a true drift that degraded accuracy after the stream midpoint.Bottom-25% feature changes were used separately to test resistance to irrelevant changes.
  • Detectability results: MD3-SVM and MD3-RS detected the induced drifts and achieved final accuracies within an average difference of <1% of the fully labeled AccTr approach.AccTr detected exactly one drift in all six cases and served as the labeled gold standard.
  • False-alarm results: MD3-SVM and MD3-RS resisted irrelevant changes, whereas HDDDM raised more false alarms because it tracks raw feature-distribution changes without classifier information.The two MD3 variants detected the same number of drifts and differed by only 0.25% in average accuracy.
  • Detection dynamics: After the changepoint, MD3 accuracy trajectories remained close to AccTr as retraining restored prediction performance.MD3 detections occurred near the changepoint, although MD3-RS was delayed in two cases because of greater robustness to change.
  • Detection signal: Margin density changed sharply around the accuracy drop, sometimes increasing and sometimes decreasing, motivating an absolute-deviation drift signal.The pattern was presented as evidence that margin density tracks informative changes rather than random stream variation.

5.3. Experiments on real world cybersecurity datasets exhibiting concept drift

On four cybersecurity datasets with real-world concept drift, MD3 achieved accuracy close to the labeled baseline while requiring substantially fewer labels. It also produced fewer false alarms than HDDDM.

  • Experimental setup: Four cybersecurity datasets with unknown drift type and location were evaluated using accuracy, detected drifts, false alarms, and labeling percentage.The datasets are high-dimensional and represent real-world concept-drift settings.
  • Evaluation criteria: A high accuracy, low false-alarm count, and low labeling percentage were the desired evaluation outcomes.Each alarm requests a chunk of samples for labeling, so false alarms directly increase labeling cost.
  • Results: MD3 accuracy remained close to the fully labeled AccTr approach, while its labeling requirement was 88.3% lower.The reported average deviation for MD3-SVM was 1.3%.
  • Results: HDDDM required 8.3% more labeling than MD3 on average because of its higher false-alarm rate.The paper attributes this behavior to responding to distribution changes without correlating them to accuracy degradation.
  • Results: MD3 and AccTr converged to similar accuracy trajectories across the cybersecurity datasets, supporting MD3 as a replacement for fully labeled detection.MD3 raised one false alarm in the spam and spamassassin datasets.
  • Generality: Similar behavior from MD3-SVM and MD3-RS supports the margin-density metric’s classification-algorithm independence.The comparison covered both accuracy progression and detected drifts and false alarms.

5.4. E

Additional experiments found MD3 largely insensitive to the underlying robust detection model and to moderate margin-width choices. A non-robust L1 logistic model was a clear boundary case.

  • Detection model: Five additional detection models were tested across the four cybersecurity datasets to assess MD3’s dependence on the underlying model.The models varied regularization, classifier family, and ensemble construction.
  • Detection model: Varying the underlying model had no significant effect on MD3 detection capabilities, and final accuracies showed no statistically significant difference at p=0.05.The comparison used a Friedman non-parametric test across all four datasets.
  • Detection model: A standalone L1-penalty logistic regression model performed poorly because feature minimization violates MD3’s coupled-features premise.It detected no drifts for phishing and performed significantly worse on spam and spamassassin.
  • Detection model: The L1 logistic model became effective under a random-subspace ensemble, indicating that MD3 can accommodate explicit and non-explicit margins.The paper therefore qualifies its model-independence claim by emphasizing suitable robust classifiers.
  • Margin width: Changing θmargin generally produced similar accuracy trajectories, with θmargin=0.05 failing on the phishing dataset because too few samples entered the margin.The reported suggested range for robustness and effective detection is θmargin=0.25-0.75.

5.5. Experimental results on benchmark concept drift datasets

On the Electricity Market and Covertype benchmark streams, MD3 matched the fully labeled baseline closely while using less labeling than HDDDM. Both datasets benefited from drift handling despite unknown drift characteristics.

  • Experimental setup: The Electricity Market and Covertype streams were used as real-world benchmarks with unknown drift type and location.Both datasets were normalized, converted to numeric features, and evaluated with chunk size N=2500.
  • Results: MD3 accuracy differed from the fully labeled AccTr approach by 1.1% on EM and 0.85% on Covtype.These results were reported despite the datasets’ unknown concept-drift characteristics.
  • Results: MD3 used half the labeling budget on EM and three-quarters on Covtype compared with HDDDM for the same resulting accuracy, on average.The MD3 approaches also signaled fewer drifts than HDDDM.
  • Results: NoChange accuracy was significantly lower than that of the drift-handling techniques, indicating that both benchmark streams benefited from adaptation.The comparison is shown in the benchmark accuracy-over-time results.

6. How the MD3 compares to other margin based drift detection techniques?

MD3 tracks margin density—the number of samples in a classifier’s uncertainty region—rather than average sample uncertainty. Its fixed-margin signal is robust to feature changes that do not affect classification performance and better follows relevant drift for robust classifiers.

  • Signal tracked: MD3 tracks the expected number of samples in a classifier’s uncertain regions, whereas other margin-based techniques track average sample uncertainty over time.The distinction comes from the signal being tracked and from MD3’s use of a fixed margin specified before deployment.
  • Irrelevant-feature drift: Changes in irrelevant features produce no significant classification-error effect, yet Hellinger Distance detects them because it is model agnostic.Margin density and uncertainty tracking remain robust against these irrelevant-feature changes.
  • Relevant-feature drift: Margin density remains robust when relevant features drift, while traditional uncertainty tracking fails to match the robustness of classifiers against changes in only a few features.A robust random subspace ensemble can maintain performance unless a majority of relevant features change simultaneously.
  • Synthetic comparison: Table 11 compares changes in classification error, margin density, uncertainty, and Hellinger Distance as synthetic drift intensity varies.Features 1–5 are irrelevant, and bold entries mark each metric’s first indication of change.
  • Detection timing: The fully labeled technique signals drift after 12 affected features, while MD3 comes closest to tracking actual drift using unlabeled data.The comparison reports high robustness to false alarms for MD3.

7. Conclusion and future work

The paper presents MD3 as an incremental, unlabeled method for detecting concept drift through classifier margin density. Across drift-induced, cybersecurity, and benchmark datasets, it reports high detection and prediction performance with fewer false alarms and less labeling than the compared approaches, while future work targets label-efficient retraining.

  • Conclusion: MD3 detects drift by monitoring the number of samples in a classifier’s uncertainty region and signaling when margin density deviates significantly.The signal requests labeled samples for subsequent verification and classifier retraining.
  • Evaluation scope: MD3 was evaluated on 6 drift-induced datasets, 4 cybersecurity datasets, and 2 benchmark concept-drift datasets.The evaluation covered spam detection, phishing websites, and network intrusion detection within cybersecurity.
  • Conclusion: Compared with HDDDM, MD3 produced fewer false alarms and used 8.7% less labeling on average at the same ∆=+0.66% accuracy.The comparison is reported against a state-of-the-art unlabeled feature-tracking approach.
  • Cybersecurity results: In cybersecurity experiments, MD3 used 88.8% less labeling than supervised drift detection while achieving statistically equivalent classification performance.The reported domains include spam detection, phishing websites, and network intrusion detection.
  • Future work: Future work will investigate label-efficient relearning after drift detection, including active learning for selective confirmation and retraining labels.The stated goal is additional labeling savings during online classification.
Loading 1704.00023v1…