Sequential bootstrapped support vector machines - a SVM accelerator

Support vector machine has obtained much success in machine learning. But it requires to solve a quadratic optimization (QP) problem so that its training time increases dramatically with the increase of training set. Hence, standard SVM with batch learning has difficulty in handling large scale problems. In this paper, we introduce a SVM accelerator, called sequential bootstrapped SVM (SeqSVM), to speed up the training of SVM. At the beginning, the SeqSVM trains a SVM classifier on a small part of all training samples and then keeps on selecting the so-called convex hull samples from the given large training set to retrain this SVM until all convex hull samples are selected. The key principle in our method is to help the SVM pick the convex hull sample that is wrongly classified by the current SVM and furthest from the current SVM solution. The convex hull sample, which disagrees most with the SVM solution, will lie on the convex hull of each class distribution and all support vectors lie on the convex hull in the case of linearly separable classes. Two difficulties have to be overcome. The first is that the SeqSVM´s iterations will take too many if there are too many support vectors. The second is that when the class distributions are not separable, it is not easy to pick convex hull samples. In this paper, we show how these two difficulties are overcome. Experimental results on both artificial database and benchmark databases demonstrated the effectiveness of proposed algorithm to reduce the learning time of SVM on the whole training set.