Sparse Laplacian Support Vector Machine For Semi-supervised Learning

Support Vector Machine(SVM)is a general supervised machine learning method based statistical learning theory.SVM minimizes the structural risk,and has the advantages of high fitting accuracy,few parameters,high generalization performance and global solution.As an effective supervised learning method for small-sample and nonlinear tasks,SVM has attracted substantial attention in machine learning.In the real world,unlabeled data is easy to obtain,which results that the number of unlabeled data is usually quite large.It is often expensive and time-consuming to tag unlabeled data.Thus,how to effectively use a small number of labeled samples and a large number of unlabeled samples is an issue to be considered in semi-supervised learning.Laplacian Support Vector Machine(LapSVM)introduces the Laplacian regularization into SVM and fully uses the unlabeled data,which successfully extends SVM from supervised learning to semi-supervised learning.Real-world data often contains various noise,such as redundant features or/and samples,which would have a negative effect when constructing models.In order to eliminate noise or redundancy in the data,it is necessary to generate a sparse decision model to implement data reduction.In order to solve the issue that LapSVM does not have a sparse decision model,we propose variants of LapSVM and apply them to semi-supervised learning tasks such as classification,dimensionality reduction and denoising.The contributions of this thesis are summarized as follows.(1)Based on LapSVM,we introduce the L1-norm regularization and present a kind of linear sparse LapSVM,or L1-norm LapSVM.Unlike LapSVM,the L1-norm LapSVM solves the optimization problem in the original space.In addition,the hinge loss function and the L1-norm regularization in the objective function simultaneously ensure the sparsity of solution.Since the Ll-norm LapSVM can achieve feature selection and classification at the same time,this method can be regarded as a classifier or as a feature selection method.Experimental results show that the L1-norm LapSVM has better performance than other comparative linear methods.(2)In order to process nonlinearly separable data,the kernel L1-norm Support Vector Machine(kernel L1-norm LapSVM)is proposed based on the L1-norm LapSVM by introducing the kernel trick.The objective function of the kernel L1-norm LapSVM also contains the hinge loss and the L1-norm regularization,the sparsity of the model can be guaranteed.The kernel L1-norm LapSVM can realize both sample reduction and classification.Experimental results show that the kernel L1-norm LapSVM has better classification performance than other compared methods.(3)A semi-supervised manifold preserving graph reduction(SMPGR)algorithm is proposed to preprocess data.When the number of unlabeled samples is relatively large,the kernel L1-norm LapSVM has a high computational complexity.To solve this issue,we propose SMPGR and its kernel version to screen data and improve the quality of data.After preprocessing,the sample size can be reduced and the original structural information of data can be maintained.Combining preprocessing methods with the kernel L1-norm LapSVM further implements data reduction.Experimental results verify that our data reduction methods are effective in semi-supervised learning.