Research On Models And Algorithms Of Semi-supervised Support Vector Machine

Support vector machine is an effective method of machine learning for classification problems with less samples. It is based on the structural risk minimization in statistical theory. Due to its global optimal solutions and the strong ability of generalization, support vector machine has been applied in many areas such as compressed sensing, sparse optimization, pattern recognition, feature selection, image processing and medical diagnosis. Semi-supervised support vector machine is a learning technique for classification using both labeled and unlabeled samples. Since obtaining plenty of labeled samples is often time-consuming and labor-consuming in the real-world applications, researchers have paid a large amount of attention on combining unlabeled samples with labeled ones.However, the optimization problem related to semi-supervised support vector machine is a non-convex problem, which is NP-hard in general. Besides, it is often time-consuming for choosing suitable kernel functions for nonlinear classification. Thus, the research on semi-supervised support vector machine is of great significance both in theory and applications.This thesis aims to proposing new models and design efficient algorithms for semisupervised classification. The proposed methods are further tested on some artificial and public benchmark data sets.We propose two conic relaxation models for semi-supervised support vector machine with quadratic Hinge loss function, respectively. Semi-supervised support vector machine induces to a mixed-integer programming problem. First, we propose a new semi-definite relaxation and estimate its possibly maximal ratio of the optimal value approximately. Then we propose a well-known conic programming problem called completely positive programming problem that is equivalent to the original problem. Since this problem is NP-hard, a doubly non-negative relaxation is proposed for approximated solutions. Furthermore, we prove that the doubly non-negative relaxation is tighter than the semi-definite relaxation. Finally, we use both the optimization package CVX and alternating direction methods to solve two relaxation problems. Numerical results show that two proposed relaxations generate proper classifiers. Besides, the semi-definite relaxation outperforms doubly non-negative relaxation in classification accuracy.Motivated by the efficiency and effectiveness of constructing separating surfaces directly, we propose a kernel-free semi-supervised quadratic surface support vector machine model for binary classification. This model is formulated as a mixed integer pro-gramming problem, which is equivalent to a non-convex optimization problem with absolute-value constraints. Using the relaxation techniques, we derive a semi-definite programming problem which is polynomial-time solvable. The optimization package CVX is further used to solve this problem. Preliminary computational results show that the proposed method outperforms some existing well-known methods for semisupervised support vector machine with a radial basis kernel function in terms of classification accuracy. When compared with supervised support vector machine, we find that unlabeled samples are useful for improving classification performance. However, this method is often memory overflowed when dealing with large-scaled problems.To deal with the issues of memory overflowing, we propose a proximal quadratic surface support vector machine model for semi-supervised binary classification without using kernel functions. This model is inspired by the fast speed of proximal support vector machine and the kernel-free classification. It can be reformulated as a mixedinteger programming problem which is NP-hard in general. Semi-definite relaxation is then adopted and some linear matrix inequalities are added for deriving a tighter lower bound. Then a primal alternating direction method designed by using the structure of the relaxation model is developed for fast computation. Preliminary results indicate that the proposed method is computational efficient and outperforms the kernel-free semisupervised quadratic surface support vector machine in terms of the accuracy of classification. Furthermore, the results also indicate that both labeled and unlabeled samples are useful for improving classification performance.