# Concept Drift Adaptation with Incremental-Decremental SVM
## 3 Background: The Adaptive Window Model for Drift Detection and the Incremental-Decremental SVM
### Kuhn-Tucker Conditions and Vector Migration in Incremental-Decremental SVMs  
Among the SVM models suitable for adapting to drifting environments, the incremental SVM learning algorithm of Cauwenberghs and Poggio [36] (later extended in [37]) is well equipped for handling non-linearly separable input spaces. By design, it is also able to non-destructively forget samples, adapting its statistical model to the remaining data samples. Retraining from scratch is thus avoided, and the model can learn/unlearn much faster than a traditional SVM. An efficient implementation for individual learning of the CP algorithm was analyzed by [PERSON] [38], along with a similar algorithm for one-class learning. Practical implementation issues of the CP algorithm were discussed in [39, 40]. The algorithm was also adapted for regression [41, 42, 43]. The incremental approach was revisited more recently in [44], where a linear exponential cost-sensitive incremental SVM was defined. In the following, Equations (5)-(14) are taken from [39]. Our AIDSVM method is based on the CP algorithm. Therefore, we briefly review the theoretical framework, with emphasis on the Kuhn-Tucker conditions and exact vector migration relations, which were previously presented in [39] with full details. For a set of samples \(x_{i}\) with associated labels \(y_{i}\in\{-1,+1\}\) (\(i=1,\ldots,N\)), a linear SVM computes the separation hyperplane as a linear combination of the input samples given by the function \(g(x)=w^{T}x+b\), where the predicted label is given by \(\hat{y}_{i}=sign(g(x_{i}))\). The optimal hyperplane is determined by the following optimization problem:  
\[\min_{w}\frac{1}{2}\|w\|^{2}+C\sum_{i=1}^{N}\xi_{i} \tag{5}\] \[\text{subject to}\quad y_{i}(w^{T}x_{i}+b)\geq 1-\xi_{i},\;\xi_{i} \geq 0,\;i=1,\ldots,N \tag{6}\]  
where \(C\) is the regularization constant tuning the constraints strength. We define the penalty function \(h(x_{i})\) for data samples \(x_{i}\) as:  
\[h(x_{i})=y_{i}g(x_{i})-1=y_{i}(w^{T}x_{i}+b)-1 \tag{7}\]  
If \(x_{i}\) is correctly classified, \(h(x_{i})\) would be positive; the variable associated with the constraint, \(\xi_{i}\), is zero in this case. Otherwise, if incorrectly classified, or on the right side of the hyperplane, but at a smaller distance than the minimum margin \(\frac{1}{2}\|w\|\), the value \(h(x_{i})\) becomes negative. If sample \(x_{i}\) is not classified correctly within a sufficient margin distance, \(h(x_{i})<0\) and \(\xi_{i}>0\). However, Equation (5) enforces small \(\xi_{i}\) penalties. The \(C\) regularization parameter tunes the trade-off between margin increase and correct classification. Solving the constraint optimization problem makes use of the Kuhn-Tucker (KT) conditions; two of them are relevant for the incremental-decremental approach:  
\[\lambda_{i}[h(x_{i})+\xi_{i}]=0 i=1,\ldots,N \tag{8}\] \[h(x_{i})+\xi_{i}\geq 0 i=1,\ldots,N \tag{9}\]  
Applying the KT conditions also determines the separation hyperplane to be computed as \(g(x_{i})=\sum_{j=1}^{N}\lambda_{j}y_{j}x_{j}^{T}x_{i}+b\). Condition (8) is the complementary slackness condition. If \(\lambda_{i}=0\), then the vector is not part of the solution at all. If non-zero, then (9) must be true, and \(x_{i}\) will be part of the solution. When \(\xi_{i}=0\) and \(h(x_{i})=0\), sample \(x_{i}\) will be considered a support vector. The penalty \(h(x_{i})\) can be:  
\[h(x_{i})\left\{ \begin{array}{ll}>0,&\lambda_{i}=0\;\text{and}\;\xi_{i}=0\\ =0,&0<\lambda_{i}<C,\\ &h(x_{i})+\xi_{i}=0\;\text{with}\;\xi_{i}=0\\ <0,&\lambda_{i}=C,\\ &h(x_{i})+\xi_{i}=0\;\text{with}\;\xi_{i}>0\end{array} \right.