A Fast Optimization Algorithm For Support Vector Machines

Since the nineties of the last century, the support vector machine (SVM) based on the structural risk minimization principle has been successfully applied in a variety of practical problems, such as particle recognition, text classification, bioinformatics and finance prediction, etc.. The optimal classification hyperplane of SVM is obtained by solved the dual quadratic programming problem(QPP), which makes the solution is global. But the speed of solving large-scale QPP is slow also influence application of SVM to large-scale problems. Popular SVM optimization algorithms include decomposition algorithm, geometric algorithm and sequence minimization algorithm, etc..This paper introduces a novel DCD algorithm, namely the clipping dual coordinate descent (clipDCD) algorithm. Different to the DCD algorithm, this clipDCD algorithm only has one layer of iteration, in which each iteration selects a multiplier variable by the maximum possible descent criterion and updates it. Compared with the DCD algorithm, the proposed algorithm not only has a simple iterative scheme, but also is easy to implement. Note that when the size of training data is large, the clipDCD algorithm in each iteration needs to spend more time on the selection of the multiplier variable. This paper further discusses a probabilistic acceleration clipDCD algorithm. Based on the probability theory, the selection range of multiplier variable is restricted on a random subset with a size for min(|A|, [log(0.025)/log(0.975)]) in A, where A is the alternative index set.To validate the effectiveness of the clipDCD and accelerated clipDCD algorithms, this paper respectively runs the twin support vector machine (TWSVM), twin Parametric-margin support vector machine (TPMSVM) and projection twin support vector machine (PTSVM) on different data sets by using theDCD, clipDCD and accelerated clipDCD algorithms. Experimental results show that the proposed clipDCD and accelerated clipDCD algorithms not only obtain the same classification accuracy, but also significantly reduce the training time and kernel evaluations compared with the DCD algorithm.