Research On The Models And Algorithms For Support Vector Machines

Support Vector Machine(SVM),based on the statistical learning theory, has become a new method for machine learning. For the sake of its advantages such as global optimization, excellent generalization ability, and sparsity solution, SVM can solve many practical application problems such as small samples, nonlinear learning, over fitting, curse of dimensionality and local minima, which makes SVM paid more and more attention. And SVM has been widely used in classification, regression estimation, function approximation, etc. In this thesis, a new semi-supervised SVM is presented, and several new and improved training methods for some other SVM models are proposed. The main achievements of the thesis are as follows.Firstly, based on the ideas of LIAM and the U-support vector machine, this paper proposes a new semi-supervised proximal support vector machine(NPLIAM), which only requires solving the inverse of an n+1by n+1matrix to obtain the final classification hyperplane just as the PLIAM and is faster and more efficient than other mathematical programming-based methods. The most essential is that this method overcomes the two fundamental drawbacks of the general LIAM semi-supervised support vector classifiers:1) they included the whole information provided by both the positively and negatively labeled instances through the unlabeled instances that are in its neighborhood in the linear constraints, which greatly added the number of constraints and made the optimization solver more complex;2) they can only utilize the unlabeled points that are in the neighborhood of a labeled point, which may influence the accuracy of classification.Secondly, on the basis of the analysis of a new standard problem for SVM and the primal-based SQP-like algorithm proposed by Roger and Gaetano, an improved training algorithm for the standard SVM are presented. We compare the new modified method with the original, and the effectiveness of our method is validated with numerical experiments. A discovery is that the modified SQP-like algorithm may directly seek out the local optimal point and terminate when the iteration point close to the solution. However, the original method may do an additional search step. Furthermore, we offer another selection strategy for the parameter θ in the original algorithm, which has better reliability and stability, especially when the points are not separable(i.e. h<0).Thirdly, we reformulate the optimization problem in the K-SVCR method for multi-class classification as an box constrained variational inequality problem(BVI) with a positive semi-definite matrix, which, actually speaking, is a box constrained variational inequality problem with P0-function(P0BVI). At the same time, because the BVI can be reformulated as the solution of a nonsmooth system of equations, based on Ma’s regularized smoothing Newton method for nonlinear complementarity problem with P0-function (P0-NCP)[40], we introduce a single smoothness parameter μ and regularization parameter ε, which are viewed as independent variables in our algorithm, and propose a new regularized smoothing Newton method for the generally P0BVI, which could be directly used to deal with the K-SVCR method mentioned above. This algorithm seems to be simpler and more easily implemented compared to many previous methods, which relies on the two independent variables. The proposed algorithm is proved to be convergent globally. Furthermore, under CD-regularity, we prove that the proposed algorithm has a superlinear (quadratic) convergence rate without requiring strict complementarity conditions. Fortunately, this method could be directly used to deal with the K-SVCR method mentioned above, which relies on its own features.Finally, we make some experiments on public benchmarks for the above NPLIAM and the new training methods, which indicates our new semi-supervised SVM model and training algorithms are effective and efficient.