The Study On Smo Algorithm For Training Support Vector Machines

This dissertation studies the training of support vector machines(SVM) with emphases on the sequential minimal optimization,and makes some improvements to the SVM algorithm. In order to demonstrate the effectiveness of the improvements , the improved algorithm is applied to linear SVMs and Gaussian SVMs.The dissertation is arranged in four chapters. The first chapter introduces the studying background , the development of decomposition algorithm and some modifications on the original SMO algorithm in this paper.In the second chapter some definitions and conditions are presented to formulate the SVM training problem, which is described as a large-scale convex quadratic programming problem. The primal optimization problem and its dual problem are first given for the case when all training data can be linearly separated. When the training data are separated by a nonlinear hypersurface, we transform the data to an higher dimensional space such that the data will be linear separable. Finally, the optimization model is modified by introducing relaxation variables such that it can be applied to the case when the training data are allowed to be separated incorrectly.In the third chapter, SMO algorithm is studied in detail, including its theoretical basis, the deducing process of the algorithm(analytically solving sub-optimization problem and how to update other variables after a successful optimization step)and the strategy of choosing two variables for every step.In the fourth chapter, the shortcomings of the original SMO algorithm are pointed out: the computation for SMO is dominated by kernel evalations and the first optimizing variable is chosen so randomly that it influences the convergence of the whole algorithm. Then the modified SMO is brought forward. It utilizes sparse input to accelerate kernel evaluations, chooses the variable which makes the objectivefunction of dual problem increase most as the first optimizing variable, reduces the range of the second optimizing variable to those violating KKT conditions. At last, the author compiles the original and modified algorithms in Matlab . We test two middle-scale data sets in benchmark problems: the front 500 samples in adult-la database and the whole 958 samples in tic-tac-toe database. The result shows that not only for linear SVMs, but also for non-linear SVMs, the CPU time and iterations ofmodified algorithm are much less than original SMO algorithm.