Robust and Sparse Linear Programming Twin Support Vector Machines

In this paper, we propose a new linear programming formulation of exact 1-norm twin support vector machine (TWSVM) for classification whose solution is obtained by solving a pair of dual exterior penalty problems as unconstrained minimization problems using Newton–Armijo algorithm. The idea of our f...

Full description

Saved in:
Bibliographic Details
Published in:Cognitive computation 2015-02, Vol.7 (1), p.137-149
Main Author: Tanveer, M.
Format: Article
Language:English
Subjects:
Algorithms
Artificial Intelligence
Biomedical and Life Sciences
Biomedicine
Classification
Computation by Abstract Devices
Computational Biology/Bioinformatics
Iterative methods
Linear equations
Linear programming
Neurosciences
Optimization
Pattern recognition
Quadratic programming
Regularization
Robustness (mathematics)
Support vector machines
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In this paper, we propose a new linear programming formulation of exact 1-norm twin support vector machine (TWSVM) for classification whose solution is obtained by solving a pair of dual exterior penalty problems as unconstrained minimization problems using Newton–Armijo algorithm. The idea of our formulation is to reformulate TWSVM as a strongly convex problem by incorporated regularization techniques and then derive an exact 1-norm linear programming formulation for TWSVM to improve robustness and sparsity. The solution of two modified unconstrained minimization problems reduces to solving just two systems of linear equations as opposed to solving two quadratic programming problems in TWSVM and TBSVM, which leads to extremely simple and fast algorithm. One significant advantage of our proposed method is the implementation of structural risk minimization principle. However, only empirical risk is considered in the primal problems of TWSVM due to its complex structure and thus may incur overfitting and suboptimal in some cases. Our approach has the advantage that a pair of matrix equation of order equals to the number of input examples is solved at each iteration of the algorithm. The algorithm converges from any starting point that can be easily implemented in MATLAB without using any optimization packages. Computational comparisons of our proposed method against original TWSVM, GEPSVM and SVM have been made on both synthetic and benchmark datasets. Experimental results show that our method is better or comparable in both computation time and classification accuracy.
ISSN:1866-9956
1866-9964
DOI:10.1007/s12559-014-9278-8