Study Of Parallel Algorithms For Large-Scale Support Vector Machine Problems

As a new learning method based on statistic learning theories, Support Vector Machine(SVM) has perfect theoretical basis and outstanding learning ability, widely applied into engineering fields. However, the arrival of Information Era brings large-scale training set to SVM, triggering deficiencies of low training speed, massive memory usage and inefficient execution. Thus, we focused on the research of parallel SVM algorithms, to speed up training process and fulfill the real-time requirements at a low RAM and storage cost.Reviewing the background and models of classic SVMs, this thesis proposed a parallel algorithm based on penalty method, solving SVM through unconstrained smooth optimization. Our algorithm adopted a special penalty function to decompose SVM problem into smaller subproblems, which would be resolved by Parallel Variable Distribution algorithms, guaranteeing good convergence rate. Moreover, the theory proved the equivalence of general mixed-integer constrained problems to mixed-integer and continuous unconstrained ones, making the proposed parallel algorithm available for mixed-integer planning, integer programming and constrained problems.To accelerate SVM training, we also put forward an improved extended saddle-point theory, based on which another new parallel solver is constructed. In the new parallel algorithm, penalty parameters do not have to tend to infinity, and training on the whole data set would bring few errors, improving the prediction accuracy and increasing training efficiency. What is more, both the theory and algorithm can be applied to generic convex planning according to their outstanding generalization.