The number of decision-making processes that rely on machine learning models to operate has been increasing in recent years. Safety of those systems is compromised when models deviate from their expected behavior. One root cause is a shift in the underlying data distribution, known as concept drift. A direct consequence of concept drift is a rapid drop in model's predictive power. Accurate detection of drift is essential as false alarms lead to unnecessary down time and undermine confidence in the drift detection model. This paper introduces Real-Drift Detector (RDD), a drift detector that is not triggered by virtual drift. RDD does not need use class labels during the inference phase to operate. Our detector outperformed the state of the art in an extensive benchmark on a large panel of well-known datasets used in drift detection.
distribution [
However, ML models can be crippled by a wide range distributions. One way to categorize drifts is with its
of problems that raise serious questions regarding their impact on a model’s performance. Virtual drift is used
impact on the safety of systems and their consequence to describe a distribution change that does not impact a
on society. Some models inadvertently induce bias in model while real drift does. Let be a set a variables
their predictions [
ifeld of research in the machine learning community.
Focus was mostly aimed at models dealing with drift as well as drift detectors. Recent advances in detecting drift when true class labels are available led algorithms to achieve almost perfect detection. Other (more realistic) contexts still show room for improvement.
To prevent drift from afecting ML models, several
mechanisms have been proposed. Assuming that recent
data share the same distribution as upcoming data, one
way is to continuously update a pool of models. In [
When detecting a drift, the consensus is that an
increase of the error rate of a model means the presence of
concept drift. Detection methods based on that
hypothesis have been given a lot of attention as this methodology
is able to systematically detect real drift while
consistently ignoring virtual drift. The detection methods
presented in [
Both updating a pool of models and monitoring the error rate perfectly deal with drift. As virtual drift does not impact accuracy, it is systematically ignored. However, in order to work, both approaches need access to the true labels immediately after the inference phase. This is not realistic for real-world scenarios when true class labels are almost never available promptly and are sometimes never known. To address this issue, several ways of dealing with drift in an unsupervised manner have been studied.
To detect drift without class labels availability,
window-based technique have been studied. The authors
of [
To avoid detecting drift over one-dimension sliding
windows, [
To circumvent the unavailability of true labels, the
authors of [
The authors of [
During the inference phase the authors monitor the
error rate of the student model and use [
The idea behind concept drift detection by statistical
tests is that a distribution change will be a strong
indicator of drift [
the distribution of regions made by of a class dependant partitioning while virtual drift does not. We use a decision tree to partition the feature space into regions of homogeneous class labels.
Our intuition is that a data distribution change in a leaf between the training phase and inference phase indicates a drift. It is our assumption that a real drift is likely to change in which region the observations are assigned to. Such misplaced samples are likely to have a diferent distribution than that of the training observations. A distribution change leading to virtual drift is unlikely to be seen locally as it may afect less the way observations are distributed in leaves.
In order to better discriminate real drift from virtual drift, each region is attributed a weight. The weights represent the ability of a given region to correctly assign a label to an observation. A region that only contains a single class of observations will have a large weight. While a region that cannot well separate samples on their label will have a small weight. This is done to reduce the risk of sudden class imbalance to be detected as a distribution change. Our model signals a drift when enough regions flag their distribution as changing. 3.2. Mathematical Background distribution. During the initialisation step, leaves that cannot well separate class labels are removed, all leaves with less than 20% impurity are dropped. During early experimental runs, we found that setting a low minimum impurity percentage yields very few leaves with enough samples to conduct the statistical test. We also found that setting a high value prevents us from confidently assigning a class to a leaf. We set the maximum impurity value at 20% as it ofers a good compromise, although this value could be changed based on the data at hand. In an efort to rank the remaining leaves, we attribute to each leaf a weight which corresponds to a leaf’s purity during training.
Weights somehow capture the separation power of a leaf. If a given observation is classified at a leaf with high weight, we may expect that the probability of this observation to be misclassified is low. On the other hand, a leaf with a lower weight will be more susceptible to assign the wrong label to an observation. Our goal by ranking the leaves based on their predictive power is to help our detector ignore virtual drift.
The detection step is detailed in Algorithm 1. In line 1-5 test set observations are attributed to based on the leaf they are at. In line 6, we go over each leaf that contains test data; in line 7 we initialize the drift features DF variable that tracks the number of drifted features. In line 8, the number of observations at a leaf is checked. In lines 9 through 13, for all leaves containing enough test instances, we proceed to do a Levene test of variance equality on all dimensions between the inference and training set contained in a leaf. We choose here the Levene test as it is adequate when the data distribution may slightly deviate from the normal one. Of course, other tests could be used, based on the knowledge of the underlying data distribution to improve the detector’s performances (when the data distribution is strictly normal, the Barlett’s test should be used; the Brown–Forsythe test may also be an alternative when the data does not follow a normal distribution). We did not make any assumptions on the distribution and independence of variables, it will be the focus of future work.
In lines 14 through 18, leaves are classified as drifting if the ratio of features that fail the homoscedasticity test exceeds the user defined threshold. In line 21, the algorithm flags a drift if the weighted average of leaf’s drift-labels exceeds the user defined threshold.
(ℳ) is fit over the training data. Like most drift detection algorithms, we assume the training data is sampled from one single concept. We do not consider the training data to include past concepts that might ofset the detector.
For both the training ( ) and inference () test sets, we consider the variables to follow a normal distribution.
This hypothesis is required to test for homoscedasticity
in the latter. After discarding all leaves that contain too
few samples or that are not pure, we store, for each leaf,
the training instances that belong to it. Let , be the
training and inference data within leaf of class . For
the test to be significant [
By construction, the leaves of a decision tree don’t hold the same separation power of class labels. The in- 3.3. Hyper-parameter discussion tuition is that leaves containing pure class labels should be less afected by P( | ) concept change as they are generally further away from the decision boundary. On the contrary, impure leaves are more likely to experience a distribution change due to a P() drift or to be subject to misclassifications that may impact the inference
the parameter reduces the risk to make a type I error, which, in our case, indicating drift when there is not. The parameter was set to 0.01.
The parameter is the minimum ratio of features to reject the equal variance hypothesis. A low parameter Algorithm 1 RDD - Inference 1.0 Parameter =
Inputs: 0.8 - ℳ : Trained Decision Tree Model taeR00..46 - : Dictionary of leaves mapping to the training 0.2 instances 0.0 Metric -- ∈: RLeda× vmes :wTeeisgthstest with d features and m samples 10..08 Parameter = TTHPN -Par:aNmuemtebresr: of variables in dataset taeR00..64 -- :: MHyinpiomthuemsinsuremjebcetrioonf oribsskervation in a leaf 00..02 0.1 0.2 0.3 0.4 Va0l.u5e 0.6 0.7 0.8 0.9 - : Minimum ratio of ℋ0 rejection for a leaf to drift - : Minimum ratio of leaves to drift to trigger an Figure 1: Influence of the and parameters on the True alarm. Positive rate, True Negative rate and H score. On the plot, Variables: = 0.3 and on the plot, = 0.3. The graph confirms our - : Dictionary of leafs mapping to the test in- intuition that low values tend to flag virtual drift as real drift stances in those leafs while high values cause the detector not to detect any drift. - : Drift status of leaves - : Number of features that drift within a leaf 1: for ∈ do 2: if ℳ() ∈ then 3: [ℳ()] ← [ℳ()] + 4: end if 5: end for means leaves will be considered as drifting if few features present a shift in variance (i.e. the detector will be sensible).
The parameter is the minimum ratio of drifted leaves to signal a drift has taken place.
In order to set relevant and values for our detector, we conducted a hyper parameter search on three datasets (airlines, poker and weather). We excluded those datasets from the experimental study to prevent bias. In Figure 1 we plot the influence of both and on TP, TN and the H score. The H score is detailed in Section 4.
In this experiment we assess our method’s ability to
detect drift while ignoring virtual drift. We extensively
tested our method against a wide panel of state of the art
detectors on a extensive set of both real and synthetic
datasets. The benchmark used in this section are the
standard ones when testing drift detectors [
drift when true class labels are available after inference, is the test-then-train approach. A model predicts the class on a batch of samples, then, the true class is revealed and the model updates itself. The global prediction accuracy is then used to rank models.
This setup is not suited for models that do not rely on true labels availability. In most datasets used to benchmark drift handling methods, the presence of drift is only assumed or artificially introduced by sorting the observations on an attribute. To the best of our knowledge, the exact occurrence of drift is unknown for all usual datasets. The experimental setup described bellow allows us to know the exact drift occurrence and to evaluate the efect it has on a model’s accuracy.
The goal of the experiment is to assess the performance of detectors on real drift and virtual drift. Two distinct perturbations are used to change the dataset: the Step Drift, where a subset of the features are shufled and the Noise Drift, where Gaussian (1, 1) noise is added to a subset of features (Gaussian noise with mean equal to 1 is used to change the mean of the distribution, not to obfuscate the signal). The idea is now to be able to artificially generate real drift and virtual drift. To create virtual drift, we add one of the two perturbations on the 25% least im- Table 1 portant features as to their predictive power of the class Overview of the dataset used in our experiment. All but one labels. In doing so, we hope to change the distribution RW dataset are binary classification problems. 2 RW datasets of several features will not afect a predictive model’s contain more than 100 features. For the synthetic datasets, performances. To create real drift, we modify the 25% we limit the number of generated observations at 10 000. most informative features by adding one of the two per- Dataset Dimensions Classification turbations. The intuition is that a change of distribution on the most important features is likely to cause a drop Adult (48842, 66) Binary of performance in a predictive model. To find 25% most BCaonvk ((14150231913,,4591)) MulBtii-ncalarsys (7) and least important features, we train a Random Forest Digits08 (1499, 17) Binary Classifier over the training data. We choose this model Digits17 (1557, 17) Binary as it is a robust, widely used model that achieves good Elec (45312, 15) Binary level of performance on the datasets. For each dataset, Musk (6598, 167) Binary we introduce the 2 perturbations on the 2 sets of features Phishing (11055, 47) Binary thus creating 4 distinct drift set. Spam (6213, 500) Binary
In order to have stationary non-drifting data before Wine (6497, 13) Binary adding our generated drifts, we first randomly shufle Hyperplane (10000, 11) Binary the observations. Each dataset is then partitioned into LED (10000, 26) Multi-class (10) three: a train set, a validation set and a drift set. 4 distinct Waveform (10000, 41) Multi-class (3) copies of the drift set are independently modified with the 4 diferent perturbations described above. In order to assess if a drift is virtual or real, we fit a Random Table 2 Forest Classifier on the train set before reporting it’s AdactciuornacayndofdariftRseatn.dAodmdiFnogrensotisCelatossliefaiesrt oinvfeorrmthaettivraeifneiantgu,rveasliaccuracy on the train set, validation set and the 4 diferent (LN) leads to virtual drift on all datasets. Adding step perturbadrift sets. The drop of the model’s accuracy between the tion to the least informative features (LS) also leads to virtual diferent sets is used to classify drift as virtual or real. If drift except for the musk dataset. When those perturbation the diference in accuracies between the validation set are made on the most informative features (MN and MS), it and the training set is lower than that of the validation leads to real drift across all real datasets. We highlight in bold set and the drift set, we consider the drift induced to be perturbations that lead to real drift. real, otherwise, it is considered a virtual drift. Train Val. LN LS MN MS
Table 1 briefly describes the datasets used in the experiment. The datasets dimensions range from 11 on Adult 1. .85 .85 .85 .28 .59 Hyperplane to 500 on Spam. The classification task is Bank 1. .94 .92 .94 .52 .52 binary on 10 datasets and multi-class on 3. This ensures Cov .99 .85 .84 .84 .49 .46 that RDD is tested in a variety of scenarios. DD1078 11.. .919. .919. .919. ..5747 ..8609
In table 2 we report the average accuracies of the Ran- Elec 1. .89 .87 .87 .57 .62 dom Forest Classifier over the training, validation and Musk 1. .98 .94 .97 .51 .56 the four diferent drift set. changing the most important Phis. .99 .97 .96 .96 .69 .47 features generates real drift while changing the least im- Spam 1. .98 .98 .98 .58 .59 portant features creates virtual drift regardless of the per- Wine 1. 1. 1. 1. .63 .44 turbation. There are 3 exceptions, when noise is added to Hyp. 1. .87 .87 .85 .71 .87 the least important features, real drift is produced on the LED 1. 1. 1. 1. .58 .31 Musk dataset. When corrupting the most important fea- Wav. 1. .85 .85 .85 .72 .41 tures, the step perturbation produces virtual drift on the Hyperplane dataset while the noise perturbation yields virtual drift on the Waveform dataset. real drift is detected.
In an efort to aggregate both the True Positives and
FmaelstreicN1edgeafintievdesinin[to20o]n.eSimnecetrwice, wcoenwduilcltmouakreexupseeroimftehnet = 2 * ̂̂︂︂ +* (1)
on a batch mode, we removed the impact of the detection
delay defined as the number of drift samples processed We evaluate RDD with = 0.01, = 0.3, = 0.3
before signaling a drift. The Drift Accuracy (̂︂) is a against:
binary value that assess the correctness of the detection,
it’s equal to 1 when a virtual drift is ignored or when a
• ADWIN [
drift induced by a Step corruption of the least important features. On the 7 detectors evaluated, 3 are able to consistently ignore this type of virtual drift: TSDD, ST and RDD. TSDD comes first with no detections on realworld (RW) datasets and almost none on synthetic data. RDD makes no False Positives (FP) on 7 RW datasets and all synthetic datasets. On 3 real-word datasets the FP is very low (0.1). The Student Teacher detector produces no FP on 8 RW datasets and on 2 synthetic ones, however on 2 RW datasets the FP rate is high as it is around .5. ADWIN along with the statistical test-based KS and MMD fail to ignore virtual drift on all but 1 RW dataset. D3 does slightly better ignoring virtual drift on 3 RW datasets. On synthetic data, relatively few FP are made by those 4 detectors.
Table 4 exhibits detection rate when adding noise to the least important features. On the Musk dataset, this type of perturbation produces real drift and therefore, detections are considered as True Positive (TP). ADWIN along with D3, KS and MMD which where not specifically built to handle virtual drift, systematically wrongfully detect drift across all real and synthetic datasets. RDD flags detects virtual drift on the Digits 08 dataset 4 out of 10 runs. Virtual drift is otherwise ignored by RDD. ST and TSDD fail to ignore the virtual drift on 2 RW datasets. 0.1 In Table 5 we observe real drift induced by a Step drift on the most informative features. The Hyperplane exhibits virtual drift with this corruption and low values should be regarded as TN. ADWIN, D3, KS and MMD, which all exhibit poor performance on virtual drift, now achieve almost perfect detection on RW datasets. However, D3 and ADWIN fail to detect real drift on synthetic data. Our method systematically detects real drift on 4 RW datasets and achieve good levels of detection on 3 others. Drift is detected on 50% of the runs on the phishing dataset. The ST model achieves 4 perfect detections on RW datasets and good level of detection on 3 others. The TSDD detector yields poor performance detecting only 2 drifts out of all RW datasets. On the 2 synthetic datasets with real drift, ADWIN, D3 and RDD fail to detect the drift, while TSDD detects 1. KS, MMD and ST detectors succeed in their detection.
Noise detection on the most important features results are shown in Table 6. ADWIN, D3, KS and MMD achieve perfect detection across both real and synthetic datasets. RDD detection results exceed that of ST and TSDD with 7 perfect detections on RW datasets. TSDD and ST are tied with both 5 accurate detections on RW datasets. Only our detector and TSDD ignore virtual drift on the Waveform dataset. ST and TSDD outperform RDD with one perfect detection on the virtual datasets.
In Table 7, we produce the combined true positive and true negative results by (1). This table showcases the overall performance achieved by each detector on each dataset. Due to the fact that on the Musk, Hyperplane and the Waveform datasets, drift induction either generates more virtual or real drift, the TN score will have a varying impact.
Table 7 allows us to assess the ability of a model to ignore real drift while detecting real drift. RDD yields the best H scores on 7 RW datasets and tying the first place
In this paper we introduced RDD, a drift detector that does not need ground truth labels during the inference phase. We extensively challenged our algorithm against a number of state of the art drift detectors and over a large panel of both real and synthetic datasets. We experimentally proved that our method outperforms current drift detection methods. We showed our detector’s ability to detect real drift and to ignore virtual drift. As false alarms are the main reason why drift detectors are not on 2 synthetic ones. TSDD takes second place with the highest score on 1 RW dataset but coming first or tying ifrst place on all synthetic datasets. ST comes third with the highest H scores on 2 RW datasets and tying first place on 1 synthetic dataset. On RW datasets, we see that ADWIN, D3, KS and MMD have overall low scores due to their misclassification of virtual drift despite having detected all real drifts. On synthetic datasets, their score is better having not made too many misclassification when a step drift was induced on the least informative features. widely used in production. We demonstrated the usability of our detector for real world applications. We tuned the hyper-parameters on 3 datasets not used in the experimental study. We show that they are valid in a wide range of real-world scenarios and that few efort should be made when using the models in production. We also demonstrated the ability of RDD to work in any dimension, having the best detection accuracy on both datasets that had over 100 features.
Future work will consist of further modeling the partition space. Research will also deal on how a drift detector can be initialized in recurrent concept drift scenarios, when no stationary dataset can be used to initialize a detector.