L_p Regular Izat Ion In Support Vector Machine For Features Selection

Feature selection plays an important role in machine learning. Feature s-election is to eliminate the redundant or irrelevant features, which results in a simplified but more information feature subset. The advantages of feature selec-tion include:preventing overfitting and improving the generalization performance, improving data interpretability and visualization, reducing the computation cost, reducing data measurement and storage requirements.We study feature selection strategies for support vector machine. Recently, the so called LP-SVM (0<p<1) has received much attention because it can encourage better sparsity than the widely used L1-SVM. However, the LP-SVM is a nonconvex, nonsmooth and non-Lipschitz optimization problem. Developing numerical methods for this problem is a challenging task. Our major contributions are outlined here.1. We reformulate the LP-SVM into an optimization model with linear ob-jective function and smooth constraints (LOSC-SVM), so that it can be solved by efficient numerical methods for smooth constrained optimization. We establish the equivalence between LOSC-SVM and LP-SVM, and show some good properties of LOSC-SVM. This efficient reformulation would open a new path to develop nu-merical methods for Lp-SVM. Numerical experiments on artificial datasets show that the LOSC-SVM (0<p<1) can improve the performance both in feature selection and classification by choosing a suitable parameter p. The results on real datasets show that the LOSC-SVM is better than L1-SVM both in feature selection and classification performance, and more robust than another LP-SVM algorithm which called SLA-SVM.2. Recent numerical researches have shown that the L1/2regularization prob-lem can be regarded as a representative in the Lp (0<p<1) regularization prob-lems. Therefore, we pay more efforts to the numerical methods for L1/2-SVM. We develop an interior point algorithm to solve the L1/2-SVM based on its equiva-lent smooth constraint optimization model. Then we establish the convergence of the proposed algorithm. Numerical results support the reformulation of L1/2-SVM and the proposed method. The solutions of L1/2-SVM are much sparser than L1-SVM under the comparable classification accuracy. Furthermore, the classification results of L1/2-SVM are more accuracy than Lo-SVM (FSV).3. We introduce a penalty successive linear programming algorithm (PSLP) to solve the L1/2-SVM. The PSLP can be applied to as large a problem as the LP code can handle, and is especially efficient on highly constrained problems. Under mild conditions, we establish the convergence of the PSLP algorithm. We explore the application of L1/2-SVM to gene selection for cancer classification. The characters of gene expression data are high dimensionality, huge redundancy and noise and highly imbalanced. Numerical results on three well-known gene expres-sion data sets support the effectiveness of the proposed method compared to other commonly-used regularization SVMs.4. To our knowledge, there is still no formal proof or comprehensive mathe-matical understanding on how Lp regularization can bring feature selection. We analyze theoretically the feature selection ability of the LP-SVM. We first discuss the possibilities of feature selection for specified data. The results show that fea-ture selection depends not only on the parameter p but also on the data itself. Then we provide a formula for computing the probabilities which measure the fea-ture selection ability. Based on this formula, we compute the probabilities for some popular p. Computations show that, small p really helps to enhance the feature selection ability of Lp-SVMs.