OPTWIN: Drift identification with optimal sub-windows
Mauro Dalle Lucca Tosi Martin Theobald
Online Learning (OL) is a field of research that is increasingly gaining
attention both in academia and industry. One of the main challenges of OL is
the inherent presence of concept drifts, which are commonly defined as
unforeseeable changes in the statistical properties of an incoming data stream
over time. The detection of concept drifts typically involves analyzing the
error rates produced by an underlying OL algorithm in order to identify if a
concept drift occurred or not, such that the OL algorithm can adapt
accordingly. Current concept-drift detectors perform very well, i.e., with low
false negative rates, but they still tend to exhibit high false positive rates
in the concept-drift detection. This may impact the performance of the learner
and result in an undue amount of computational resources spent on retraining a
model that actually still performs within its expected range. In this paper, we
propose OPTWIN, our "OPTimal WINdow" concept drift detector. OPTWIN uses a
sliding window of events over an incoming data stream to track the errors of an
OL algorithm. The novelty of OPTWIN is to consider both the means and the
variances of the error rates produced by a learner in order to split the
sliding window 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. We assessed OPTWIN over
the MOA framework, using ADWIN, DDM, EDDM, STEPD and ECDD as baselines over 7
synthetic and real-world datasets, and in the presence of both sudden and
gradual concept drifts. In our experiments, we show that OPTWIN surpasses the
F1-score of the baselines in a statistically significant manner while
maintaining a lower detection delay and saving up to 21% of time spent on
retraining the models.