Fast Online Training of Ramp Loss Support Vector Machines
Zhuang Wang, Slobodan Vučetić · 2009
A fast online algorithm OnlineSVMRfor training Ramp-Loss Support Vector Machines (SVMRs) is proposed. It finds the optimal SVMRfor t + 1 training examples using SVMR built on t previous examples. The algorithm retains the Karush-Kuhn-Tucker conditions on all previously observed examples. This is achieved by an SMO-style incremental learning and decremental unlearning under the Concave-Convex Procedure framework. Further speedup of training time could be achieved by dropping the requirement of optimality. A variant, called OnlineASVMR, is a greedy approach that approximately optimizes the SVMRobjective function and is suitable for online active learning. The proposed algorithms were comprehensively evaluated on 9 large benchmark data sets. The results demonstrate that OnlineSVMR(1) has the similar computational cost as its offline counterpart; (2) outperforms IDSVM, its competing online algorithm that uses hinge-loss, in terms of accuracy, model sparsity and training time. The experiments on online active learning show that for a fixed number of label queries OnlineASVMR(1) achieves consistently better accuracy than QueryAll and competitive accuracy to Greedy approach; (2) outperforms the active learning version of IDSVM.