# Concept Drift Adaptation with Incremental-Decremental SVM
## 4 Adaptive-Window Incremental-Decremental SVM (AIDSVM)
The estimated class \(\hat{y}_{i}\) is compared against the true class label \(y_{i}\). For every pair of window splits \(W_{0}\) and \(W_{1}\), we compute the mean of the sample error \(e_{i}=\{y_{i}\) different from \(\hat{y}_{i}\}\), and then the difference of those means. This difference is compared to the dynamic threshold \(\epsilon_{cut\_adjusted}\) given by Equation (4). In the ideal case, the difference is close to zero (for a window without concept drift). Once the difference becomes greater than the computed threshold, all samples from the first split \(W_{0}\) are unlearned by the decremental SVM procedure, and training is resumed. The algorithm does not apply the statistical test if the current shifting window has fewer samples than \(min\_window\_size\); this is taken as a measure of precaution. Conversely, the upper size of the shifting window is also limited. In addition, the SVM does not remove a vector that is the only remaining representative of its class. Let us analyze the computational complexity of this algorithm. We consider \(N\) to be the width of the shifting window. The AdaptiveShiftingWindow procedure (Algorithm 1) calls the Learn/Unlearn procedures. Both procedures follow the following steps:

1. Perform an O(1) test to check if the associated \(\lambda_{c}\) is within the allowed limits, \(0\leq\lambda_{c}\leq C\), while testing whether the penalty \(h_{c}\) has either reached zero (due to \(x_{c}\) migrating to support set) or a positive or negative value (due to migration to the rest/error sets);
2. Computation of \(Q\) is in \(O(N^{3})\);
3. Computation of \(\hat{y}_{s}\), given by Equation (11), is based on matrix inversion, so it is in \(O(nSV^{3})\), where \(nSV\leq N\) is the number of support vectors;
4. Computation of \(\gamma_{s}\) is in \(O(nSV^{2})\) as given by Equation (12);
5. Procedure _compute_limits_for_support_and_rest_vectors()_ is in \(O(N^{2})\), computation of the maximum/minimum for \(\Delta\lambda\) values associated to support vectors is in \(O(nSV)\), and for the rest vectors we have to compute the penalties \(h\), which is \(O(N^{2})\);
6. Procedure _reassign_vectors_in_sets()_ has linear time. The inner loop of the Learn/Unlearn procedures is in \(O(N^{3})\). This is dominant over the construction of the window splits, which is in \(O(N^{2})\). The Unlearn procedure is called within the for loop, and theoretically we could have \(O(N^{4})\). However, in practice, we

Figure 2: ADWIN framework. observed that discarding the entire \(W_{0}\) is sufficient to reinitialize the model, and any further drops do not occur. We can conclude that, for most cases, execution time is in \(O(N^{3})\). ## 5 Experiments

We experimentally compared the performance of AIDSVM to the ones of FHDDM, FHDDMS, DDM, EDDM and ADWIN, which were introduced in Sections 2 and 3.1. For these drift detectors, two algorithms were employed, namely Naive Bayes (NB) and Hoeffding Trees (HT) [28]. We used the implementations provided by the Tornado framework (sources can be found on-line [45]). We also compared the performance of AIDSVM against the classic SVM ([[https://scikit-learn.org/stable/modules/generated/sklearn.svm.SVC.html](https://scikit-learn.org/stable/modules/generated/sklearn.svm.SVC.html)]([https://scikit-learn.org/stable/modules/generated/sklearn.svm.SVC.html](https://scikit-learn.org/stable/modules/generated/sklearn.svm.SVC.html)), accessed on 2 October 2021) (C-SVM). This is actually a SVM trained on a fixed size window. When a sample arrives, the earliest one is discarded to make room for the new one, and the SVM is retrained from scratch based on the updated window. ### SINE1 Dataset

Following [28,30,46], we used the SINE1 synthetic dataset ([[https://github.com/alipsgh](https://github.com/alipsgh)]([https://github.com/alipsgh](https://github.com/alipsgh)), accessed on 2 October 2021), with two classes, 100,000 samples, and abrupt concept drift [31]. Additionally, 10% noise was added to the data.