A Study On The Fast Training Methods Of Support Vector Machines Based On Coordinate Descent

Support vector machines(SVMs)play an important role in machine learning.Coordinate descent is one of the important methods for solving SVMs.At each iteration of coordinate descent,only one variable is chosen and updated while all the other variables remain fixed.Thus,coordinate descent can obtain a very fast convergence rate.Traditional S VM solver SMO based on coordinate descent are not scalable in the current big data era.In addition,the asynchronous greedy coordinate descent(AsyGCD)algorithm is the state of the art solver,but AsyGCD is limited to binary classification.Ordinal regression is one of the most important tasks of supervised learning.Support vector ordinal regression(SVOR)is an important method to tackle ordinal regression problems.Due to the complexity in the formulation of SVOR,large-scale training for SVOR is still vacant.In order to address these problems,in this paper,we focus on the following research on the fast training method of SVMs based on the coordinate descent:(1)For the traditional SVM solver SMO,we propose a generalized framework of accelerat-ing SMO through SSGD.The shrinking and caching techniques are commonly used to accelerate SMO,however,most of the computational time is wasted on the first half of iterations during the process of SMO with shrinking.In order to improve the efficiency of SMO,in this paper,we consider the fact that the stochastic sub-gradient descent(SSGD)method is extremely fast for building a good solution and propose a generalized framework of accelerating SMO through SSGD for a variety of SVMs of binary classification,regression,ordinal regression and so on.Then we provide a deep insight into why SSGD can accelerate SMO.Experiment results on a variety of datasets and learning applications finally confirm that our method can effectively speed up SMO.(2)Based on the activity set technique,we propose an asynchronous accelerated greedy coordinate descent algorithm.AsyGCD is a state of the art solver based on the asynchronous greedy coordinate descent,but it is not scalable enough and is limited to binary classification.In order to address the above problems,in this paper,we propose an asynchronous accelerated greedy coordinate descent algorithm(AsyAGCD)for SVMs with the active set strategy.Then we extend AsyAGCD to deal with the regression problem e-SVR.Moreover,we provide the comparison of computational complexity of AsyGCD and our AsyAGCD.Finally,the experi-ment results on a variety of datasets confirm that our AsyAGCD is much faster than the existing SVM solvers.(3)For the ordinal regression problem,we propose a new SVOR formulation and provide the corresponding asynchronous greedy coordinate descent algorithm for SVOR.Compared to standard support vector machines,the formulations of SVOR are more complicated because of multiple inequality or equality constraints.In order to address the above problems,in this pa-per,we propose a new SVOR formulation without inequality and equality constraints.Then,based on the new SVOR formulation,we propose an asynchronous greedy coordinate descent(AsySVOR)algorithm for SVOR.Experimental results on several datasets demonstrate that our proposed AsySVOR algorithm run much faster than the existing SVOR solvers while ensuring the accuracy,especially in the large data set.