Locate potential Support Vectors for faster Sequential Minimal Optimization
Hansheng Lei, Qian Long · 2011
Sequential Minimal Optimization (SMO) is one of the state-of-the-art solutions for Support Vector Machines (SVM) training. SMO sequentially picks a pair of training samples for joint optimization, which minimizes the usage of memory. However, to find such two samples, SMO uses one outer loop through the entire training set looking for a sample which violates the KKT conditions, and one inner loop to look for a sample which heuristically maximizes the increase of the SVM objective function. While there is limited room for improvement in the inner loop, the outer loop can be reduced significantly if we can locate a small subset of training samples which potentially contains the Support Vectors (SVs).We present a Fisher Discriminant Analysis(FDA) based approach to locate potential SVs in a small core subset, which enables the SVM training to be focused effectively on a promising small region instead of the entire SV-sparse training set. Nevertheless, the training points outside the subset can not be blindly ignored. The method iteratively trains the classifier on the core subset and tune it using the remainder subset. Experimental results show that the approach significantly speeds up SMO training by reducing kernel evaluations, which dominates the training time. It converges much faster to optimal solution with much fewer iterations than standard SMO.