Fast Online Training of Ramp Loss Support Vector Machines

A fast online algorithm OnlineSVM^R for training Ramp-Loss Support Vector Machines (SVM^Rs) is proposed. It finds the optimal SVM^R for 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 OnlineASVM^R, is a greedy approach that approximately optimizes the SVM^R objective function and is suitable for online active learning. The proposed algorithms were comprehensively evaluated on 9 large benchmark data sets. The results demonstrate that OnlineSVM^R (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 OnlineASVM^R (1) achieves consistently better accuracy than QueryAll and competitive accuracy to Greedy approach; (2) outperforms the active learning version of IDSVM.