# Concept Drift Adaptation with Incremental-Decremental SVM
## 3 Background: The Adaptive Window Model for Drift Detection and the Incremental-Decremental SVM
### Concept Drift with Adaptive Window  
We use the ADWIN adapting window strategy to cope with concept drift. Details can be found in the original paper [20]. During learning, past data, up to the current sample, are stored in a fixed-size window. For every sample \(x_{i}\) in the window characterized by its class \(y_{i}\), the trained model predicts class \(\hat{y_{i}}\); we compute the sample error \(e_{i}\) which is 0 if \(y_{i}=\hat{y_{i}}\) or 1 if the predicted label is wrong. Given a set of samples, the prediction error \(e_{i}\) is a random variable that follows a Bernoulli distribution. The sum of these errors, for a set of samples, is a random variable following a binomial distribution. If the width of the window is \(n\), where \(x_{i}\) (\(i=1,\ldots,n\)) are the window samples, then the model error rate is the probability \(p_{i}\) of observing 1 in the sequence of \(e_{j}\) errors (\(j=1,\ldots,i\)). Each \(p_{i}\) is drawn from a distribution \(D_{i}\). In the ideal case of no concept drift, all \(D_{i}\) distributions are identical. With concept drift, the distribution changes, as the error rate is expected to increase. The ADWIN strategy successively splits the current window of \(n\) elements into two \"large enough\" sub-windows. If these sub-windows show \"different enough\" averages of their sample error, then the expected values corresponding to the two binomial distributions are different. By incrementing the \(i\) value, the approach constructs all possible cuts of the current window into two adjacent splits (\(W_{0}\), \(W_{1}\)), where \(W_{0}\) has \(n_{0}\) samples \(x_{1},x_{2},\ldots,x_{i}\) and \(W_{1}\) has \(n_{1}\) samples \(x_{i+1},\ldots,x_{n}\). We have \(n=n_{0}+n_{1}\). As cuts are constructed, they are evaluated against the following Hoeffding test:  
\[Pr(|\mu_{0}-\mu_{1}|\geq e_{cut})\leq\frac{\delta}{n} \tag{1}\]  
where \(\mu_{0}\) and \(\mu_{1}\) are the averages for the error values in \(W_{0}\) and \(W_{1}\), and \(\delta\in(0,1)\) is the required global error. The scaling \(\frac{\delta}{n}\) is required by the Bonferroni correction, since we perform multiple hypothesis testing by repeatedly splitting the samples. The statistical test checks whether the observed averages differ by more than a threshold \(\epsilon_{cut}\), which is dependent on the window split size. The null hypothesis \(H_{0}\) assumes that the mean \(\mu\) has remained constant along all the sufficient \"large enough\" cuts performed on the sliding window \(W\). Parameter \(\delta\) tunes the test's confidence; for example, a 95% confidence level is assimilated to \(\delta=0.05\). The statistical test for observing different distributions in \(W_{0}\) and \(W_{1}\) checks whether the observed averages in both sub-windows differ by more than the threshold \(\epsilon_{cut}\). Given a specified confidence parameter \(\delta\), it was shown in [20] that the maximum acceptable difference \(\epsilon_{cut}\) is:\[\epsilon_{cut}=\sqrt{\frac{1}{2m}\cdot\ln\frac{4}{\delta^{\prime}}} \tag{2}\]  
where:  
\[m=\frac{1}{1/n_{0}+1/n_{1}}\ \text{(the harmonic mean of $n_{0}$ and $n_{1}$)},\quad\delta^{\prime}=\frac{\delta}{n} \tag{3}\]  
However, this approach is too conservative. Based on the Hoeffding bound, it overestimates the probability of large deviations for small variance distributions, assuming the variance is \(\sigma^{2}=0.25\), which is the worst-case scenario. A more appropriate test used in [20] also takes the window variance into consideration:  
\[\epsilon_{cut\_adjusted}=\sqrt{\frac{2}{m}\cdot\sigma_{\
u}^{2}\cdot\ln\frac{2} {\delta^{\prime}}}+\frac{2}{3m}\ln\frac{2}{\delta^{\prime}} \tag{4}\]  
In Equation (4), the square root term actually adjusts the \(\epsilon_{cut}\) term relative to the standard deviation, whereas the additional term guards against the cases where the window sizes are too small. An exemplification of these criteria is given in Figure 1. We considered a window of 1000 simulated samples.