OPTWIN: Drift Identification with Optimal
Sub-Windows
1st Mauro D. L. Tosi

2nd Martin Theobald

Department of Computer Science
University of Luxembourg
Esch-sur-Alzette, Luxembourg
https://orcid.org/0000-0002-0218-2413

Department of Computer Science
University of Luxembourg
Esch-sur-Alzette, Luxembourg
https://orcid.org/0000-0003-4067-7609

Abstract—Online Learning (OL) is a subfield of Machine
Learning (ML) that is increasingly gaining attention in academia
and industry. A long-standing challenge in OL is the presenceof concept drifts, which are commonly defined as unforeseeablechanges in the statistical properties of an incoming data stream
over time. State-of-the-art concept-drift detectors however still
exhibit high false-positive rates in their drift identification, whichthen leads to an undue amount of computational resources spentby the underlying ML algorithm on retraining its model.
In this paper, we propose OPTWIN, our “OPTimal WINdow”
concept drift detector suited for both classification and regression
problems. The novelty of OPTWIN lies in identifying where to
split a sliding window W of error rates produced by an ML model
into two provably optimal sub-windows, such that the split occurs
at the earliest event at which a statistically significant difference
according to either the t- or the f -tests occurred. Specifically,
OPTWIN reaches this result by (1) considering both the mean
and the variance of the error rates, and (2) improves the cost of
detecting this optimal split from O(log |W |) to O(1) per iteration.
We assessed OPTWIN over the MOA framework, using ADWIN,
DDM, EDDM, STEPD, and ECDD as baselines over 12 synthetic
and real-world datasets with both sudden and gradual concept
drifts. In our experiments, OPTWIN surpasses the F1-score of thebaselines in a statistically significant manner while maintaining
a lower detection delay and saving up to 21% of time spent on
retraining the models.
Index Terms—concept drift, drift detection, data streams

I. I NTRODUCTION
Online Learning (OL) is an area of research which gained anincreasing amount of attention in academia and industry overthe past years. OL is a sub-field of Machine Learning (ML) in
which an underlying ML technique aims to constantly update
its model’s parameters from an incoming data stream underlimited time and space constraints. Ideally, OL methods aretrained in real-time and thereby aim to maximize the prediction
accuracy of their models based on bounded windows of data
instances they have previously seen and which they may
see in the near future [1]. Use-cases of OL are varied andinclude online video segmentation [2], spam detection [3],fraud detection [4], and many others [5]–[7].
The presence of concept drifts is one of the numerous
challenges when processing data streams in real-time. Concept
drifts are commonly defined as unforeseeable changes in theThis work is funded by the Luxembourg National Research Fund under the
PRIDE program (PRIDE17/12252781).

statistical properties of the incoming data stream over time[8]. Such a change may have different sources and types, andit may involve different adaptation strategies (cf. Section II).
In practice, concept drift is the key phenomenon that impairs
the performance of pre-trained ML models over data streams.
The most common form of drift detection is the error ratebased one. This type of drift detection uses the difference
between the number or magnitude of historical prediction
errors and new prediction errors to determine if a concept drift
occurred [8]. The most popular error rate-based algorithms
are ADWIN [9], DDM [10], and their variations as [11],[12]. Those and newer drift detectors [13], [14] are known
for being lightweight and identifying concept drifts with an
outstanding true-positive rate. However, those algorithms still
have a high false-positive rate. Additionally, most of themwork with classification problems only, with few being suitedfor regression problems. Therefore, as concluded by Bayram
et al. [15], the development of drift detectors, which return
a low false-positive rate and are suited for both classification
and regression, is an open research problem in this area.
As opposed to previous approaches, which track concept
drifts based on the means of past prediction errors, we argue
that also changes in the standard deviations of those errors
should trigger concept drifts. Take, as a simple example, aregressor that outputs the following errors at window W0 :W0 = ⟨0.3; 0.7; 0.7; 0.3; 0.3; 0.7; 0.5; 0.5⟩
While, at window W1 , it outputs the following errors:
W1 = ⟨0.0; 1.0; 1.0; 0.0; 1.0; 0.0; 0.0; 1.0⟩
Current drift detectors like ADWIN would not consider this asa concept drift, as the error means µW0 , µW1 over both windows are equal to 0.5, whereas we—intuitively—understandthat something changed in the error stream and, therefore, aconcept drift should be flagged.
In this paper, we propose the “OPTimal WINdow” drift
detector (OPTWIN). It is a sliding-window algorithm thatanalyzes the error rates (either binary or real-valued) produced
by an underlying ML algorithm. It calculates the optimal cut ofa sliding window W to divide it into two sub-windows Whist
and Wnew . It then performs the well-known t- (for means)
and f -tests (for standard deviations) to determine whether thetwo sub-windows exhibit a statistically significant differencein either their means or standard deviations, respectively.
OPTWIN has the following two main features: (1) it cancalculate the optimal cut based only on the length of W
in O(1); (2) it uses both the errors’ means and standard
deviations to flag drifts. Furthermore, we provide detailed andrigorous guarantees of OPTWIN’s performance in terms of its
true-positive (TP), false-positive (FP), and false-negative (FN)
rates, as well as in its drift-identification delay.
To assess OPTWIN, we used the popular MOA framework [16] and compared OPTWIN to the most studied driftdetection frameworks in the literature: ADWIN [9], DDM[10], EDDM [11], STEPD [17] and ECDD [18]. Using MOA,
we compared the precision, recall and F1-score, as well as thedelay of all drift detectors over both sudden and gradual drifts.
Furthermore, we also trained a Naive Bayes (NB) classifier on
MOA that adapts itself based on the drift detectors and compared its results on various synthetic datasets (STAGGER [19],RANDOM RBF [20], and AGRAWAL [21]) and real-world
ones (Covertype and Electricity) [22], [23]. Additionally, we
likewise assessed OPTWIN on a Neural Network (NN) usecase. Specifically, we pre-trained a Convolutional NN (CNN)with the CIFAR-10 [24] image dataset and simulated an endto-end OL scenario with concept drifts by using OPTWIN and
ADWIN as drift detectors.
Our results show that OPTWIN reliably identifies bothsudden and gradual drifts in classification and regression
problems. Furthermore, OPTWIN is the drift detector withthe best F1-score when compared to the baselines. This isdue to its higher precision, which indicates a low FP rate.
With respect to the drift-identification delay, there was nodrift detector that was superior to the others in a majorityof the datasets. In terms of runtime, OPTWIN in combination
with the CNN training pipeline is 21% faster than a similar
ADWIN pipeline due to OPTWIN’s lower FP rate, which leads
to a significantly reduced amount of re-training iterations.
Therefore, our experiments indicate that OPTWIN identifies
concept drifts with a similar delay as other drift detectors but
maintains a higher precision and recall in the drift detection,
which reduces the overall runtime of OL pipelines that triggera re-training of their models upon each detected concept drift.

drift because it does not impact the decision boundaries ofthe learner; and (2) Pt (Y |X) ̸= Pt+1 (Y |X), which is known
as an actual drift because it directly impacts the learner’s
accuracy [8], [25], [26]. It is also possible to have both drift
sources simultaneously [8].
Another important characteristic of a concept drift is its
type. Concept drifts can be (1) sudden; (2) incremental;(3) gradual; and (4) reoccurring (see Figure 1) [8], [26].
Sudden drifts occur when the probability distribution changes
completely within a single step. Incremental drifts occur
when the distribution Pt (X, Y ) changes incrementally until its
convergence. Gradual drifts occur when the new distribution
gradually replaces the old one. Reoccurring drifts occur when
distributions can reoccur after some time.

Fig. 1. Concept drift types.

To recover from concept drifts, one may adapt the learneraccording to different strategies. The selection of the appropriate strategy depends not only on the type and source ofthe drifts but also on the use-case and the adopted learner. A
common strategy is to train a new model with the latest data
points whenever a drift is identified. Another strategy is toadjust the current learner instead of training a new one fromscratch. Moreover, it is also possible to have an ensemble oflearners, which is useful for adapting to reoccurring drifts [8].
The most popular procedure to evaluate learning algorithms
that handle concept drifts is the prequential procedure. Prequential is an evaluation scheme in which each data point
is used for testing before training the learning algorithm.
Therefore, it is not necessary to know when a drift occurredto perform the evaluation, which is useful when using realworld datasets that do not have labeled drifts [8]. Regarding
the metrics used to evaluate the drift detector, one may referto the following ones: TPs, FPs and FNs (and hence precision,
recall and F1-score) in the detection rates, as well as the delayof the drift detection [8], [27].

II. BACKGROUND

III. OPTWIN – O PTIMAL W INDOW C ONCEPT D RIFTD ETECTOR

A concept drift may exhibit different characteristics, whose
understanding is essential for a fast and reliable drift detection.
Consider an unbounded data stream that receives features xi ∈X and labels yi ∈ Y in the form of pairs of instances (xi , yi )used for training an underlying ML model. At time t, these
instances follow a certain distribution Pt (X, Y ). A concept
drift is the change of this distribution over time. Formally, a
concept drift occurs at time t + 1 iff Pt (X, Y ) ̸= Pt+1 (X, Y )[8], [25], [26]. The underlying data distribution Pt (X, Y ) may
also be decomposed and expressed as a product of probabilities
Pt (X, Y ) = Pt (X) × Pt (Y |X) via the well-known chain
rule of probability. Thus, a concept drift may come from twosources: (1) Pt (X) ̸= Pt+1 (X), which is known as a virtual

OPTWIN is the new concept-drift detector which we propose in this paper. It is an error rate-based drift detector, which
tracks the error rates produced by an OL learner in a sliding
window W . Its name stands for “OPTimal WINdow” due toits calculation of the optimal split of the sliding window. We
consider this split “optimal” because it is detected for the firstelement in W at which a statistically significant difference
between either the means or the variances of the error rates(based on the common t- and the f -tests) among two subwindows of W occurs. Specifically, W keeps growing until
either a concept drift is detected or a maximum user-definedsize wmax is reached. Based on the sliding-window size |W |and a pre-defined confidence level δ, OPTWIN calculates theoptimal point to divide W into “historical” (Whist ) and “new”(Wnew ) data points.

Algorithm 1 OPTWIN
Input parameters:• δ – confidence level• ρ – robustness• wmax – max window size

A. Setup & Parameters
Without loss of generality, we consider a typical OL scenario, in which OPTWIN receives as input a sequence ofreal numbers x1 , x2 , ..., xi , ... from a possibly unbounded datastream X. Thus, the algorithm is assumed to access only one
element xi at time i from the stream, and it buffers previously
seen elements in a sliding window W ⊂ X of consecutive
events. Moreover, OPTWIN requires as parameters (1) δ, theconfidence level for the concept-drift detection; (2) wmax , themaximum size of the sliding window W ; and (3) ρ, a parameter
we refer to as robustness, which we define as the minimum
ratio by which µWnew has to vary in relation to σWhist in orderfor OPTWIN to consider this variation as a concept drift. The
intuition behind ρ is to enable users to specify the expectedmagnitude of concept drifts relative to the data’s standard
deviation instead of its raw value, simplifying its definition andreducing dependency on problem types and data magnitude.
B. Assumptions• There is no concept drift within the first wmin data
instances from X (which is needed to initialize OPTWIN).
• A concept drift occurs when the means or the standard
deviations within two sub-windows of W are statisticallydifferent.
• Within any two sub-windows of W , the values producedby the test statistic of the unequal-variance t-test [28](henceforth called “t value”) follow a t-distribution.
• Within any two sub-windows of W , the values producedby the test statistic of the f -test [29] (henceforth called“f value”) follow an f -distribution.
Our first assumption mitigates the negative impact of outliers when only a few data points are available. The second
assumption points out when we expect OPTWIN to identify
concept drifts. The third and the fourth assumptions are
generally required to guarantee the validity of the t- and f tests, respectively, but do not impose limitations on the values
ingested from the data stream in practice.
C. Algorithm
As seen in Algorithm 1, OPTWIN first needs to be initialized by creating an empty sliding window W . Analogously toother drift detectors, it collects wmin many first elements fromthe stream (usually within 30 to 50) to guarantee that it has aminimum amount of data to output statistically relevant drift
detections. It also defines a small constant η = 1e−5 , which
avoids a division by 0 when added to the standard deviations
during the calculation of the f -test.
Second, the A DD E LEMENT procedure is called once toprocess each data element received from the data stream. The
procedure starts by inserting the most recent data element xi
into W and by checking whether W has already reached theminimum amount of elements to detect a possible concept
drift. If so, it checks if W increased above wmax and removes

Global variables:
W = ⟨ ⟩ – sliding window
wmin = 30 – min window size
η = 1e−5 – avoids division by 0

1: procedure A DD E LEMENT(xi )2:W ← W ∪ xi
3:
if |W | < wmin then4:
return False
5:else if |W | ≥ max lenght then6:
W ← W − W017:
ν ← O PTIMAL C UT(|W |, ρ, δ 4 )8:νsplit ← ⌊ν |W |⌋9:
Whist ← W0:νsplit
10:
Wnew ← Wνsplit :|W |−1
11:
12:
13:
14:
15:
16:

if
then

(σWnew +η)2
(σW
+η)2

cf. Equation (1)// f-test> f ppf (δ , ν|W | − 1, (1 − ν)|W | − 1)
1
4

hist

reset()
return True// t-test
1
else if t value(Whist , Wnew ) > t ppf (δ 4 , df ) thenreset()
return True

the oldest element from W if necessary. Up to this point,
OPTWIN performs standard queuing operations to maintain its
sliding window bounded between wmin and wmax elements.
Then, OPTWIN calculates ν, which is the optimal splitting
point of W into Whist and Wnew , by solving Equation 1 forthe highest value of ν in terms of δ ′ , ρ and |W |:s′ρ = t ppf (δ ,df )f ppf (δ ′ , ν |W |−1, (1−ν) |W |−1)
1
+
ν|W |
(1−ν) |W |(1)

where ρ is the aforementioned, user-defined robustness parameter. During this calculation, OPTWIN uses t ppf and f ppf ,which are the Probability Point Functions (PPF) of the t- andthe f -distributions, respectively. To calculate t ppf , we apply1
a confidence of δ ′ = δ 4 , which considers the application of
the two tests to calculate ν in Equation 1 and the two tests on
Lines 11 and 14 in Algorithm 1.
Finally, OPTWIN performs the t- and f -tests (in any order)
to compare both sub-windows and determine if their means
and standard deviations, respectively, belong to the same
distribution. If not, a concept drift is flagged and the algorithm
is reset. Otherwise, the A DD E LEMENT method is called forthe next element from the data stream in an iterative manner.
The usage of the t- and f -tests to identify significant
changes in the means and standard deviations among series ofdata values is well-established. However, OPTWIN’s novelty
comes from the combination of both tests to calculate ν,and thereby identify where to optimally divide this series ofvalues to perform both tests. In short, by solving Equation
1 in terms of ν, we determine the minimum size of Wnew
(the optimal splitting point of W ) that statistically guarantees
the identification of any concept drift with a robustness of atleast ρ when using the t- and f -tests, thereby achieving lowerdrift-detection delays than other approaches. To calculate ν,other than the confidence level δ, the only values that shallbe inputted by the user are wmax and ρ. Regarding ρ, whenselecting a small value, one may expect to identify smaller
drifts in exchange of a higher drift-detection delay. On theother hand, with higher values of ρ, one can expect a smaller
detection delay in exchange of missing smaller drifts. In
practice, ρ shall be set based on the magnitude and frequencyof drifts expected. However, determining the correct ρ toeach use case should not be a difficult task, since different
ρ’s tend to produce similar results (as seen in Section IV).
Regarding wmax , with a higher value, one may expect smaller
drift-detection delays in exchange for more memory usage. In
practice, when using ρ = 0.1, we did not observe a significant
variation in |Wnew | even when increasing wmax to more than
25,000 elements.
One important point to note is that we can only calculateν as the optimal splitting point if |W | ≥ wproof , with wproof
representing the minimum size of W in which there exists a
ν that solves Equation 1. Otherwise, we set ν to the middleof W until it grows to the minimum size needed to solve
Equation 1. Thus, if it exists, it is defined as the highest rootof Equation 1. Otherwise, it is set to ν = 0.5.
Below, we present Theorem 3.1, our main theoretical result.
It gives guarantees in terms of OPTWIN’s false positive (FP)and false negative (FN) bounds for identifying concept drifts.
Theorem’s 3.1 proof is available in the extended version ofthis paper [30].
Theorem 3.1:
2
• False Positive Bound. At every step, if µW and σW
remain constant within W , OPTWIN will flag a concept
drift at this step with a confidence of at most 1-δ.
• False Negative Bound (for mean drift with large enough
W ). For any partitioning of W into two sub-windows
Whist Wnew , with |W | ≥ wproof and Wnew containing
the most recent elements, if µhist − µnew > ρ σhist , then,with confidence δ, OPTWIN flags a concept drift in at
most |W | − νsplit steps.
• False Negative Bound (for mean drift with small W ). For
any partitioning of W into two sub-windows Whist Wnew ,with wmin ≤ |W | < wproof and Wnew containing themost recent elements, if µhist − µnew > ρtemp σhist , then,with confidence δ, OPTWIN flags a concept drift in at|
most |W
2 steps.
• False Negative Bound (for standard-deviation drift with
any W ). For any partitioning of W into two sub-windows
Whist Wnew , with |W | ≥ wmin and Wnew containing theσ2most recent elements, if σnew
> f ppf (δ ′ , ν |W | − 1, (1 −2histν) |W | − 1), then, with confidence δ, OPTWIN flags aconcept drift in at most νsplit steps.
D. Implementation & Analysis
We implemented OPTWIN via a combination of Java andPython scripts as extensions of the MOA [16] (Java) and theRiver [31] (Python) libraries (both available on Github1 ). We
pre-calculated the values of ν, t ppf , and f ppf based on a
fixed confidence value of δ = 0.99 and for wmax = 25,000,
thus 30 ≤ |W | ≤ 25,000. All pre-calculated variables werestored in lists indexed by the window sizes |W | from which
they were calculated. This is possible because those variables,
as seen in Equation 1, do not depend on the actual error
distribution. Thus, it is not necessary to calculate them in realtime. On the other hand, we need to store the sliding window
W plus the other three lists of floating point values of size up
to wmax in memory, which takes a maximum of wmax ∗ 4 ∗ 4bytes. Thus, for wmax = 25,000, OPTWIN would require onlyaround 390 KB of memory.
Furthermore, the full calculation of the means and standard
deviations from Whist and Wnew can be avoided. Insteadof calculating them from scratch, one only needs to updatethem incrementally. Moreover, as W is bounded by wmax ,we can use a circular array to make insertions at the endof the array, deletions from the beginning of the array, andthen look up each value in O(1) time per iteration. Therefore,
the A DD E LEMENT procedure has an overall computational
complexity of O(1) per element ingested from the data stream(assuming a constant cost for the numerical operations involved in resolving Equation 1 to ν). Our analytical approachthus provides great potential runtime gains over the iterative
search procedure applied, e.g., by ADWIN, which requires
O(log |W |) computations per iteration.
By default, OPTWIN’s Algorithm 1 tracks concept driftsthat either increase or decrease the means and standard deviations of the variables tracked. However, in an OL scenario, we
usually want to update the learner only when the number of
errors increases. Therefore, in our implementation, we checkif also µnew ≥ µhist along with the statistical tests on Lines
11 and 14 of Algorithm 1. In doing so, we consider that adrift occurred only if µnew is higher than µhist (i.e., when thelearner actually decreased in performance).
IV. E XPERIMENTS & R ESULTS
In this section, we report our detailed experiments to assess
OPTWIN. We compared OPTWIN to the most commonly usedbaselines for concept-drift detection: ADWIN, DDM, EDDM,STEPD, and ECDD. We additionally investigated more recent
techniques [12]–[14] but found them transitively compared tothe classical techniques mentioned above. That is because they
address specific frailties of the classical drift detectors likerecurrent drifts and decreased sensitivity when concepts are
long, often without statistical improvements over them.
We performed most of the experiments using the common
MOA [16] framework which is a Java-based data stream
simulator. In addition, we performed experiments on Python
to assess OPTWIN on a Neural Network (NN) use case, which
would not be possible via MOA.
1 https://github.com/maurodlt/optwin

Detector
ADWIN
DDM
EDDM
STEPD
ECDD
OPTWINρ=0.1
OPTWINρ=0.5
OPTWINρ=1.0

Avg. Delay
132.19569.371127.56
196.97131.84156.13120.98414.29Avg. FP
4.39
0.73
8.22
34.93
67.22
0.17
0.19
0.32

Avg. F1
67%
86%
49%
30%
37%
95%
95%
89%

TABLE IAVERAGE STATISTICS OF DRIFT IDENTIFICATION ON THE FOLLOWINGSYNTHETIC SETTINGS : GRADUAL BINARY DRIFT, GRADUAL NON - BINARYDRIFT, SUDDEN BINARY DRIFT, SUDDEN NON - BINARY DRIFT, SUDDENSTAGGER , SUDDEN RANDOM RBF, AND SUDDEN AGRAWL .

A. MOA Experiments
We compared 3 configurations of OPTWIN with the default
configurations of our baselines. All OPTWIN configurations
had δ = 0.99, wmax = 25,000, and pre-computed values forν, t ppf , and f ppf (as described on Section III-D). The
difference among the OPTWIN configurations is only on ρ,
which we varied between 0.1, 0.5, and 1.0 to better understandhow our robustness parameter affects OPTWIN in practice.
We performed two types of experiments on MOA. The
first one uses the “Concept Drift” interface, in which MOA
creates a stream of data points (either binary or non-binary)and produces a concept drift that can be sudden or gradual.
We later refer to those experiments according to their data
input and their drift type. The second type of experimentuses the “Classification” interface. It generates data streams
based on both synthetic datasets (STAGGER, RANDOM RBF,
and AGRAWL) [19]–[21] and real-world ones (Electricity and
Covertype) [22], [23]. The idea of these experiments is to train
a classifier that is reset every time a concept drift is detected bya drift detector. We chose MOA’s built-in Naive Bayes (NB)
classifier for its simplicity, which facilitates the analysis of thedrift-detection results. For the synthetic datasets, we generate
data streams with 100,000 data points with drifts occurring
every 20,000 data points (either sudden or gradual). For the
real-world data sets, the drifts are already present and have an
unknown location on the stream.
Table I presents the average results comparison among drift
detectors on the above-mentioned configurations. We repeatedeach experiment 30 times and compared their average TP, FP
and FN rates to compute their micro-average precision, recall,and F1-score, along with their average drift-detection delay(in terms of the number of streamed elements between theoccurrence of a known concept drift and its identification by
the detector). Note that we did not include in Table I the“Classification” experiments on real-world datasets nor theones with gradual concept drifts. For the real-world datasets, it
is not possible to calculate the above-mentioned metrics without knowing the drifts’ locations. For the gradual drifts, weobserved a divergence between the starting and ending pointsof those drifts in the MOA documentation and in practice.
Therefore, we did not include those in our comparison.
Based on the results in Table I, we can observe a higher F1-

Fig. 2. Gradual binary drift detection with average TP and FP rates comparedto drift-detection delays.

score for OPTWIN when compared to the baselines. We assert
this due to OPTWIN’s low FP rate which produces a highprecision and F1-score, respectively. We further compared theF1-scores of all configurations of OPTWIN with the two drift
detectors that can be used for regression problems (ADWIN
and STEPD), which showed OPTWIN to be superior basedon a one-tailed Wilcoxon signed-rank test with α = 0.05 in astatistically significant manner.
Regarding the drift-detection delay, OPTWIN with ρ = 0.5
is the drift detector with the smallest delay, taking on average
121 iterations to detect a concept drift. Observe that, thehigher the FP rate of a drift detector, the higher are also
its chances of identifying a drift earlier. Therefore, whenanalyzing ECDD’s average drift delay of 131 iterations, wehave to consider that it had an average of 67 FPs per run, in
contrast to an average of less than 0.4 for any of the OPTWIN
configurations. Furthermore, considering that DDM, EDDM,
and ECDD depend on binary data, they were not included in
the experiments using “non-binary” datasets.
We can better visualize the difference between the drift
detectors in Figure 2, which represents one of the 30 runsof the “gradual binary drift” configuration (we selected therun with results closest to the average ones). In Figure 2, we
can see the high FP rate of the EDDM, STEPD and ECDD
detectors when compared to OPTWIN, DDM and ADWIN.

B. Classification Experiments
In the “Classification” experiments (still using MOA as
platform), we can analyze the average accuracy achieved by
the NB classifier when varying the drift detectors (cf. Table
II). The idea is that the better a drift detector’s performance,
the better the classifier can adapt to the concept drifts, thus
generating a higher prediction accuracy. However, the fast
and accurate detection of the drifts did not always traverse
to a better accuracy for the classifier. We can observe this bycomparing Tables I and II, in which experiments using drift
detectors that produced a low F1-score in Table I achieved agood accuracy in Table II. Moreover, the drift detectors withthe best accuracy on real-world data sets were the ones that
detected more drifts, which is why ECDD achieved such good
accuracy (being the detector with the higher amount of FPs).
For example, ECDD detected 426 drifts on the Electricity
dataset—over twice the amount of other algorithms.
Drift Detector
None
ADWIN
DDM
EDDM
STEPD
ECDD
OPTWINρ=0.1
OPTWINρ=0.5
OPTWINρ=1.0

Synthetic
60.98
79.67
77.72
77.06
79.59
78.28
79.65
79.48
79.25

Real-world
66.94
81.25
84.60
85.45
86.01
88.46
81.64
84.46
84.64

of 20 epochs). At every iteration, the model classified the 32
images and outputted the loss of the batch. We inputted thisloss into the drift-detection algorithm. If a drift was detected,
the next 9,372 batches of images (the equivalent of 3 epochs)
were used for fine-tuning the model (thus adapting it to theconcept drift). Therefore, the goal was for the drift detector to
identify the 4 concept drifts that we simulated, triggering thefine-tuning of the model for a total of 12 epochs.
In Figure 3, we compare OPTWIN and ADWIN under
the setting described above. First, we note that ADWIN’shigh FP rates made it re-train the model for much longer
than OPTWIN. In comparison, ADWIN identified 15 concept
drifts (with 11 FPs), thus triggering model fine-tuning for
61,562 iterations which took in total 945 seconds. In contrast,
OPTWIN identified just 5 drifts (with 1 FP), thus triggering
the model fine-tuning for 23,430 iterations which took 781
seconds. We note that OPTWIN’s running time per iteration
is superior to ADWIN, 1e−5 against 6e−6 seconds. However,OPTWIN still ends up speeding up the OL pipeline wheneverre-training is triggered by the concept-drift detection (21%faster in this use-case). This is because the training of alearner is usually computationally more expensive than thedrift detection. Thus, with fewer FPs, the total training time
can be reduced substantially.

TABLE IIAVERAGE ACCURACY OF NB ON SYNTHETIC ’ S SUDDEN AND GRADUAL(STAGGER, R ANDOM RBF, AND AGRAWL) AND REAL - WORLD(E LECTRICITY AND C OVERTYPE ) DATASETS .

C. Regression Experiments on Neural Networks
To further explore OPTWIN’s behavior in a regression scenario, we compared it with ADWIN for identifying drifts fromthe loss of a CNN. We chose ADWIN as our baseline because
it was the drift detector with the best F1-score and smallest
drift-identification delay among the ones that do not requirebinary inputs (thus excluding DDM, EDDM, and ECDD). To
simplify the reader’s understanding of the generation of theconcept drift, instead of training a regression problem on a
CNN, we here focused on image classification by swapping
the labels of the images. Thus, we provoked 4 concept drifts by
swapping the labels of two classes of images every 20% of thesimulated data stream. For example, after 62,480 iterations, weswapped the labels between images from “cats” to “horses”.
Nevertheless, as the drift detectors track the loss of the CNN,
the type of the problem should not affect the experiment.
We pre-trained an image classification model [32] using
the CIFAR-10 [24] data set during 100 epochs, achieving an
average of 89% training accuracy over 3 different runs. Then,we simulated an OL scenario with concept drifts. Our data
stream was formed by batches of 32 images from the CIFAR10 dataset; with a total of 312,400 data points (equivalent to
100 epochs). We simulated our 4 concept drifts by swapping
the labels of two classes every 62,480 iterations (the equivalentFig. 3. Sudden drift detection over the loss of a CNN.

V. C ONCLUSION
In this paper, we presented OPTWIN, a novel concept-drift
detector that uses a sliding window of errors to identify concept drifts in both classification and regression problems witha low FP rate. OPTWIN’s novelty relies on the assumptionthat changes also in the variances of the elements ingested
from a data stream can be an indication of concept drift. This
assumption lets it optimally divide its sliding window in O(1)time by applying the t- and f -tests to determine whether aconcept drift occurred. To assess OPTWIN, we compared itwith 5 popular drift detectors in 11 different experiments.
As a result, OPTWIN achieved higher F1-scores in most of
our experiments. In fact, OPTWIN had the best F1-score(with statistical significance) while maintaining a similar driftdetection delay compared to the drift detectors suited for bothclassification and regression problems. Moreover, OPTWIN
could speed up the overall OL pipeline of a CNN by 21%(compared to ADWIN) due to its low FP rate. To conclude,
we conjecture that OPTWIN’s characteristics can enable evenhigher speed-ups in scenarios where the drift identification
triggers the re-training of complex models.

R EFERENCES[1] S. C. Hoi, D. Sahoo, J. Lu, and P. Zhao, “Online learning: A comprehensive survey,” Neurocomputing, vol. 459, pp. 249–289, 2021.
[2] R. Koner, T. Hannan, S. Shit, S. Sharifzadeh, M. Schubert, T. Seidl, andV. Tresp, “InstanceFormer: An Online Video Instance Segmentation
Framework,” Proceedings of the AAAI Conference on Artificial
Intelligence, vol. 37, no. 1, pp. 1188–1195, Jun. 2023. [Online].
Available: https://ojs.aaai.org/index.php/AAAI/article/view/25201[3] F. Fdez-Riverola, E. L. Iglesias, F. Dı́az, J. R. Méndez, and J. M.
Corchado, “Applying lazy learning algorithms to tackle concept driftin spam filtering,” Expert Systems with Applications, vol. 33, no. 1, pp.
36–48, 2007.
[4] T. Paladini, M. Bernasconi de Luca, M. Carminati, M. Polino, F. Trovò,and S. Zanero, “Advancing Fraud Detection Systems Through Online
Learning,” in Joint European Conference on Machine Learning andKnowledge Discovery in Databases. Springer, 2023, pp. 275–292.
[5] K. Wang, L. Xu, A. Taneja, and M. Tambe, “Optimistic Whittle
Index Policy: Online Learning for Restless Bandits,” Proceedings of
the AAAI Conference on Artificial Intelligence, vol. 37, no. 8, pp.
10 131–10 139, Jun. 2023. [Online]. Available: https://ojs.aaai.org/index.
php/AAAI/article/view/26207[6] G. Li, P. Wang, Q. Luo, Y. Liu, and W. Ke, “Online Noisy Continual
Relation Learning,” Proceedings of the AAAI Conference on Artificial
Intelligence, vol. 37, no. 11, pp. 13 059–13 066, Jun. 2023. [Online].
Available: https://ojs.aaai.org/index.php/AAAI/article/view/26534[7] D. Mandal, G. Radanovic, J. Gan, A. Singla, and R. Majumdar,“Online Reinforcement Learning with Uncertain Episode Lengths,”
Proceedings of the AAAI Conference on Artificial Intelligence,
vol. 37, no. 7, pp. 9064–9071, Jun. 2023. [Online]. Available:
https://ojs.aaai.org/index.php/AAAI/article/view/26088[8] J. Lu, A. Liu, F. Dong, F. Gu, J. Gama, and G. Zhang, “Learning underconcept drift: A review,” IEEE Transactions on Knowledge and Data
Engineering, vol. 31, no. 12, pp. 2346–2363, 2018.
[9] A. Bifet and R. Gavalda, “Learning from time-changing data withadaptive windowing,” in Proceedings of the 2007 SIAM international
conference on data mining. SIAM, 2007, pp. 443–448.
[10] J. Gama, P. Medas, G. Castillo, and P. Rodrigues, “Learning with drift
detection,” in Brazilian symposium on artificial intelligence. Springer,
2004, pp. 286–295.
[11] M. Baena-Garcıa, J. del Campo-Ávila, R. Fidalgo, A. Bifet, R. Gavalda,
and R. Morales-Bueno, “Early drift detection method,” in Fourth international workshop on knowledge discovery from data streams, vol. 6,
2006, pp. 77–86.
[12] R. S. Barros, D. R. Cabral, P. M. Gonçalves Jr, and S. G. Santos,“RDDM: Reactive drift detection method,” Expert Systems with Applications, vol. 90, pp. 344–355, 2017.
[13] O. Wu, Y. S. Koh, G. Dobbie, and T. Lacombe, “Nacre: Proactive
recurrent concept drift detection in data streams,” in 2021 International
Joint Conference on Neural Networks (IJCNN). IEEE, 2021, pp. 1–8.
[14] J. I. G. Hidalgo, L. M. P. Mariño, and R. S. M. de Barros, “Cosine
similarity drift detector,” in Artificial Neural Networks and Machine
Learning–ICANN 2019: Text and Time Series: 28th International Conference on Artificial Neural Networks, Munich, Germany, September 17–
19, 2019, Proceedings, Part IV. Springer, 2019, pp. 669–685.
[15] F. Bayram, B. S. Ahmed, and A. Kassler, “From concept drift tomodel degradation: An overview on performance-aware drift detectors,”
Knowledge-Based Systems, p. 108632, 2022.
[16] A. Bifet, G. Holmes, R. Kirkby, and B. Pfahringer, “MOA: Massive
Online Analysis,” J. Mach. Learn. Res., vol. 11, pp. 1601–1604, 2010.
[Online]. Available: https://dl.acm.org/doi/10.5555/1756006.1859903[17] K. Nishida and K. Yamauchi, “Detecting concept drift using statistical
testing,” in International conference on discovery science. Springer,
2007, pp. 264–269.
[18] G. J. Ross, N. M. Adams, D. K. Tasoulis, and D. J. Hand, “Exponentiallyweighted moving average charts for detecting concept drift,” Patternrecognition letters, vol. 33, no. 2, pp. 191–198, 2012.
[19] J. C. Schlimmer and R. H. Granger, “Incremental learning from noisy
data,” Machine learning, vol. 1, no. 3, pp. 317–354, 1986.
[20] A. Bifet, G. Holmes, B. Pfahringer, R. Kirkby, and R. Gavalda, “Newensemble methods for evolving data streams,” in Proceedings of the
15th ACM SIGKDD international conference on Knowledge discovery
and data mining, 2009, pp. 139–148.

[21] R. Agrawal, T. Imielinski, and A. Swami, “Database mining: A performance perspective,” IEEE transactions on knowledge and data engineering, vol. 5, no. 6, pp. 914–925, 1993.
[22] J. A. Blackard and D. J. Dean, “Comparative accuracies of artificial neural networks and discriminant analysis in predicting forest cover types
from cartographic variables,” Computers and electronics in agriculture,
vol. 24, no. 3, pp. 131–151, 1999.
[23] M. Harries, “Splice-2 comparative evaluation: electricity pricing (Technical Report UNSW-CSE-TR-9905),” Artificial Intelligence Group,
School of Computer Science and Engineering, The University of New
South Wales, Sydney, vol. 2052, 1999.
[24] A. Krizhevsky, G. Hinton et al., “Learning multiple layers of featuresfrom tiny images,” University of Toronto, Tech. Rep., 2009.
[25] N. Lu, J. Lu, G. Zhang, and R. L. De Mantaras, “A concept drift-tolerantcase-base editing technique,” Artificial Intelligence, vol. 230, pp. 108–
133, 2016.
[26] J. Gama, I. Žliobaitė, A. Bifet, M. Pechenizkiy, and A. Bouchachia, “Asurvey on concept drift adaptation,” ACM computing surveys (CSUR),vol. 46, no. 4, pp. 1–37, 2014.
[27] T. Dasu, S. Krishnan, S. Venkatasubramanian, and K. Yi, “Aninformation-theoretic approach to detecting changes in multidimensional data streams,” in In Proc. Symp. on the Interface of
Statistics, Computing Science, and Applications. Citeseer, 2006, pp.
1–24.
[28] G. D. Ruxton, “The unequal variance t-test is an underused alternative
to Student’s t-test and the Mann–Whitney U test,” Behavioral Ecology,
vol. 17, no. 4, pp. 688–690, 2006.
[29] M. Mahbobi and T. K. Tiemann, Introductory business statistics withinteractive spreadsheets-1st Canadian edition.
Campus Manitoba,
2016.
[30] M. D. L. Tosi and M. Theobald, “OPTWIN: Drift identification with
optimal sub-windows,” arXiv preprint arXiv:2305.11942, 2023.
[31] J. Montiel, M. Halford, S. M. Mastelini, G. Bolmier, R. Sourty,
R. Vaysse, A. Zouitine, H. M. Gomes, J. Read, T. Abdessalem et al.,
“River: machine learning for streaming data in python,” The Journal of
Machine Learning Research, vol. 22, no. 1, pp. 4945–4952, 2021.
[32] TensorFlow, “Convolutional Neural Network (CNN); Tensorflow Core,”
Dec 2022. [Online]. Available: https://www.tensorflow.org/tutorials/
images/cnn