Source-linked AI summary
Reactive Soft Prototype Computing for Concept Drift Streams
Christoph Raab, Moritz Heusinger, Frank-Michael Schleif
TL;DR
Concept drift in streaming data can make prior models unusable, while adaptation must balance stability with learning new concepts. The paper proposes RRSLVQ, combining KS-based drift detection with prototype adaptation, and reports stable, quick adjustment during drift, although its detection still requires improvement.
Problem
Concept drift can reduce prior models’ prediction performance, while stable adaptation remains difficult because models must preserve prior knowledge and learn new concepts.
Method
RRSLVQ combines the Kolmogorov-Smirnov test for concept drift detection with a prototype adaptation strategy built on RSLVQ.
Results
The proposed method improves on original RSLVQ and shows remarkable stability over time in streams with high drift rates.
Takeaways & Limitations
RRSLVQ offers an interpretable stream model with bounded memory and time complexity, while achieving prediction performance comparable to OzaBaggingAdwin and Hoeffding Adaptive Tree.
Takeaways & Limitations
Concept drift detection remains imperfect: dimension-wise testing and false positives require further investigation, despite Kswin outperforming standard detectors.
Abstract
from arXiv · showhide
The amount of real-time communication between agents in an information system has increased rapidly since the beginning of the decade. This is because the use of these systems, e. g. social media, has become commonplace in today's society. This requires analytical algorithms to learn and predict this stream of information in real-time. The nature of these systems is non-static and can be explained, among other things, by the fast pace of trends. This creates an environment in which algorithms must recognize changes and adapt. Recent work shows vital research in the field, but mainly lack stable performance during model adaptation. In this work, a concept drift detection strategy followed by a prototype-based adaptation strategy is proposed. Validated through experimental results on a variety of typical non-static data, our solution provides stable and quick adjustments in times of change.
1. Introduction
Streaming systems must process rapidly arriving, non-static data while adapting to concept drift without sacrificing model stability. The paper proposes RRSLVQ, combining KS-based drift detection with prototype adaptation to learn new concepts quickly while maintaining stability.
- Streaming data can exceed systems’ memory and processing capacity, motivating online algorithms that avoid storing large portions of data.
- Concept drift changes underlying class distributions, causing prior models’ prediction performance to drop and making drift detection and handling essential.
- The stability-plasticity dilemma balances incorporating new knowledge against preserving prior knowledge during distribution changes.
- RRSLVQ combines RSLVQ, prototype adaptation, and the Kolmogorov-Smirnov test to detect drift and adapt prototypes.
- Experiments on benchmark streams report stable performance during drift and quick learning of new concepts, including frequent reoccurring drift.
2. Related Work
Prior work detects concept drift through distribution or classifier-performance monitoring and adapts models using active strategies such as prototype modification. Prototype-based methods provide interpretable classification but commonly assume that all classes are present.
- Drift detection: Drift detectors monitor either stream distributions or classifier performance, with Adwin using adaptive subwindows to identify distribution changes.Adwin assumes that a detected performance change indicates concept drift.
- Drift detection: Related approaches compare recent and historical data with statistical tests such as the KS-Test, but some require application-specific critical-value tables.One method maintains two windows using a randomized search tree, while another simplifies the KS-Test.
- Drift detection: A supervised detector using snapshots of the last and recently surveyed concepts cannot detect drift independently of conditional class probabilities.Its detection is therefore tied to the relationship between features and class labels.
- Adaptation: Concept-drift handling is divided into passive continual updating and active adaptation, with LVQ commonly used for prototype adaptation or insertion.Passive methods update without a specific drift-detection strategy, whereas active methods change the model when drift is detected.
- Adaptation: LVQ represents class regions with geometric prototypes that are attracted or repelled by samples during error minimization, providing interpretable classification.The original LVQ was heuristic-based, while later developments include GLVQ.
- Adaptation: Prototype-insertion methods select means, error-minimizing samples, or near-mean samples as new prototypes, but share the assumption that all classes exist in a given stream.The near-mean method selects the sample closest in Euclidean distance to the mean of misclassified examples.
3. Preliminaries
Stream classifiers predict and learn sequentially in potentially infinite, non-stationary data streams, where concept drift changes the underlying distributions. The proposed detection perspective monitors p(X), assuming that real drift includes a change in the prior distribution, and evaluates frequent recurring drift because it occurs in practical settings.
- Stream classification: A supervised stream is a potentially infinite sequence of feature-label tuples arriving one at a time, requiring prediction and learning at every step.The classifier predicts an unseen label before incorporating the new tuple into the model.
- Concept drift: Stream classifiers must operate in non-stationary environments because concept drift changes the data-generating process over time.Concept drift is defined as a change in joint distributions of samples and corresponding labels between time points.
- Concept drift: Drift types describe transitions between dominating concepts, with the data mean and its temporal transition illustrated across sub-figures.The figure’s vertical axis represents the overall data mean.
- Detection principle: Detectors should identify changes as soon as possible by monitoring data distributions rather than classifier-performance values.This design goal is stated in connection with the drift-detection equation.
- Detection principle: The detector assumes that every real concept drift includes a change in the prior distribution p(X), corresponding to virtual drift.This assumption also underlies most statistical tests because they observe the prior rather than the conditional class probability.
- Evaluation scope: Frequent recurring drift is included because real-world systems such as robotics and autonomous driving may face repeated changes from lighting or weather.The paper notes that prior evaluations usually use streams with few drifts per setting.
4. Reactive Robust Soft Learning Vector Quantization
RRSLVQ combines KS-based drift detection with prototype adaptation to respond to changing stream distributions. Its sliding-window detector and two-step adaptation are designed to retain stability while learning new concepts, including when drift signals are false positives.
- 4. Reactive Robust Soft Learning Vector Quantization: RRSLVQ combines a KS-Test-based concept drift detector with a prototype adaptation strategy for streaming classification.The detector is called Kswin, and the adaptation extends RSLVQ.
- 4.1. Concept Drift Detection: The detector stores n recent samples, compares r newest samples with r uniformly sampled non-recent samples, and applies distribution-difference tests across dimensions.The KS-Test is applied to all dimensions because it is restricted to one-dimensional distributions.
- 4.1. Concept Drift Detection: Uniform sampling can miss recurring drifts when sampled points repeatedly represent the same changing concept.The paper chooses uniform sampling because it has no parameters and is fair for unknown distributions, while acknowledging that it approximates the full sliding window.
- 4.1. Concept Drift Detection: Small window sizes and corrected significance levels make Kswin more insensitive to small distribution differences, reducing false-positive signals without eliminating them.The required KS distance increases when the confidence level α decreases and decreases when the window size r increases.
- 4.3. Prototype Adaptation Strategy: When drift is detected, all existing prototypes are replaced by m mean-initialized prototypes and then optimized while retaining the class assignments.RSLVQ performs online prototype-based classification, with momentum-based updates controlled by a decay factor γ.
- 4.4. Stability during Concept Drift: Adaptation on window R achieves lower error when distributions differ sufficiently, so false-positive detections do not harm classification in the described setting.The resulting adapted model g(R) can have lower loss than the previous model h1(x) after sufficiently large window differences.
5. Experiments
The experiments evaluate drift detectors and stream classifiers on standard and frequently reoccurring drift streams. RRSLVQ improves over RSLVQ with stable performance during drift, constant memory and time behavior, and prediction performance comparable to several competing classifiers.
- Study design: The study uses six synthetic generators, six real-world datasets, and additional streams with frequent gradual or abrupt reoccurring drift.Streams contain 100,000 time steps with batches of ten, totaling one million samples per stream.
- Concept drift detectors: Kswin detects far more concept drifts than the other detectors, with roughly 5% detection accuracy versus roughly 0.001% for the remaining methods, but also produces the most false positives.The authors identify its false-positive rate as a target for future work.
- Concept drift detectors: Kswin achieves the best mean prediction performance among the tested detectors, although it is best on only four of 16 individual streams.Missed detections prevent classifiers from switching to new concepts, especially on MIXED streams.
- Stream classifiers: RRSLVQ provides stable performance and rapid adaptation during drift, outperforming other tested RSLVQ variants because both Kswin and prototype adaptation contribute to stability.The approach is evaluated against Hoeffding Adaptive Tree, OzaBaggingAdwin, Adaptive Random Forest, SamKNN, and baseline RSLVQ.
- Resource use and interpretation: RRSLVQ maintains stable memory consumption and linear time complexity during drift, while requiring less total time than ARF and OZA and supporting an interpretable prototype model.The paper concludes that stream processing remains feasible on limited technical devices.
- Stream classifiers: 81% mean accuracy on synthetic drift streams gives RRSLVQ a 12% increase over baseline RSLVQ, while SamKNN reaches 86%.RRSLVQ is approximately equal to OZA at 81% and improves real-world mean accuracy over RSLVQ by about 8%.
6. Conclusion
RRSLVQ is presented as a stable and interpretable approach for adapting to concept drift, with performance comparable to established stream classifiers. The authors identify drift detection and prototype adaptation as areas for further improvement.
- RRSLVQ provides stable performance during drift and a high adaptation rate compared with other methods.
- Kswin detects occurring stream changes and supports the concept-drift handling process with useful timing indicators.
- RRSLVQ has a straightforward, interpretable model with bounded memory and time complexity suited to embedded systems.
- Its prediction performance is comparable with OzaBaggingAdwin and Hoeffding Adaptive Tree.
- Future work should improve dimension-wise testing, examine false positives, and combine Kswin with other classifiers.
Appendix A. Dataset Description
The appendix separates the evaluated data streams into synthetic and real-world streams.
- The dataset description is divided into synthetic data streams and real-world streams.
Appendix A.1. Synthetic Stream Generators
The synthetic evaluation uses generators representing abrupt, incremental, and other changing stream concepts. These generators vary feature distributions, decision functions, or concept assignments over time.
- Synthetic streams can be potentially infinite, with drift implemented by changing the generating function.
- SEA: SEA generates binary streams with abrupt concept drift and four blocks governed by different classification functions.
- MIXED: MIXED is a binary stream with two Boolean and two numeric attributes, where labels depend on satisfying two of three conditions.
- MIXED: After each concept drift in MIXED, the classification is reversed.
- RTG and RBF: RTG assigns classes through randomly generated trees, while RBF generates instances around weighted centroids with class labels.
- HYPER: HYPER simulates incremental drift by varying the orientation and position of a hyperplane over time.
Appendix A.2. Real-world Streams
The real-world stream collection covers credit, electricity, poker, forest-cover, airline-delay, and moving-squares tasks. These datasets represent varied prediction settings, including temporal, virtual, and predefined moving concepts.
- Real-world streams are finite, and their concept drift is unknown from a statistical standpoint.
- GMSC: GMSC is a credit-scoring dataset for deciding whether loans should be allowed, containing 150,000 borrowers with ten attributes.
- Electricity: Electricity records 45,312 market observations, labeling whether prices move up or down relative to a 24-hour moving average.
- Poker-Hand: Poker-Hand contains 1,000,000 instances and introduces virtual drift by sorting randomly generated hands by rank and suit.
- Forest Cover Type: Forest Cover Type assigns cartographic variables to forest cover classes across 30-square-meter cells.
- Airlines: Airlines predicts whether a planned flight is delayed using airport, airline, and time-related features.
- SQRE: Moving Squares consists of four moving square distributions representing different classes, with a predefined 120-example horizon before old instances may overlap current ones.