An accelerator for online SVM based on the fixed-size KKT window

Support vector machine (SVM), as a general and useful supervised learning tool, is facing with some challenges such as low learning efficiency, poor generalization performance, noise sensitivity, etc. when it is applied to online learning tasks. To overcome these limitations, an accelerator model based on window technology and the KKT conditions for online SVM learning is proposed in this paper. The proposed model is not an independent online algorithm but may be regarded as an accelerator for other online SVM learning algorithms, and it constructs working set of SVM by a fixed-size window with the samples which violate the KKT conditions. The relationship between Lagrangain multipliers in dual problem of SVM and KKT conditions are analyzed in the case of online learning. On this basis, a fixed-size KKT window can be constructed according to whether the samples violate KKT conditions or not. Then, it takes the samples that violate the KKT conditions as the training window, which not only makes the training samples with the same size each time, but also ensures that all samples are useful for the hyperplane updating (it means that the classifier can be updated more smoothly). Two typical and specific online SVM algorithms are used as baseline, and the corresponding speeding online SVM learning algorithms with "X+accelerator" models are proposed to testing the performance of the proposed accelerator. Comprehensive experiments clearly show that the proposed model can accelerate the online learning process effectively and has good robustness and generalization performance.