Nonparallel Support Vector Machines for Pattern Classification
Lokesh Sharma sharma.123lokesh@gmail.com Anand Mishra anand.lnmiit@gmail.com Vaibhav Kumar Soni vbhvsoni22@gmail.com Sudhanshu Bansal sudhanshu.bansal@lnmiit.ac.in Prasant Rathore prasant.rathore@lnmiit.ac.in The LNM Institute of Information Technology, Jaipur (INDIA)

Abstract—We introduce a nonparallel classifier knows as nonparllel support vector machine(NPSVM) for the purpose of binary classification. Proposed NPSVM is totally different from the existing non parallel classifier, such as the generalized eigenvalue proximal support vector machine (GEPSVM) and the twin support vector machine (TWSVM). NPSVM has several incomparable advantages:1) Two primal problems are constructed implementing the structural risk minimization principle; 2) The dual problems of these two primal problems have the same advantages as that of the standard SVMs, so that the kernel trick can be applied directly; 3)The dual problems have the same elegant formulation with that of standard SVMs and can certainly be solved efficiently by sequential minimization optimization algorithm, while existing GEPSVM or TWSVMs are not suitable for large scale problems; 4) It has the inherent sparseness as standard SVMs; 5) Existing TWSVMs are only the special cases of the NPSVM when the parameters of which are appropriately chosen. Experimental results on lots of datasets show the effectiveness of our method in both sparseness and classification accuracy, and therefore, confirm the above conclusion further. NPSVM is a new starting point of nonparallel classifiers.

support hyperplanes, have been proposed. In the twin support vector machine (TWSVM), it seeks two nonparallel proximal hyper planes such that each hyper plane is closer to one of the two classes and is at least one distance from the other. This strategy results that TWSVM solves two smaller QPPs, whereas SVC solves one larger QPP, which increases the TWSVM training speed by approximately fourfold compared to that of SVC. Some of the drawbacks which are still in TWSVMs:•

•

Index Terms - Classification, nonparallel support vector machines (NPSVM), sparseness, structural risk minimization Principle. I. I NTRODUCTION Support vector machines are computationally powerful tools for pattern classification and regression and have already been successfully applied in a wide variety of fields SVM is so successful because of three essential elements : the principle of maximum margin, dual theory, and kernel trick. The standard support vector classification (SVC), maximizing the margin between two parallel hyperplanes leads to solving a convex quadratic programming problem (QPP), dual theory makes introducing the kernel function possible, then the kernel trick is applied to solve nonlinear cases. In recently , some nonparallel hyper plane classifiers, which are different with standard SVC searching for two parallel

•

•

TWSVM lost the sparness by using two loss function by each class : a quadratic loss function and a soft margin loss function For the nonlinear case, TWSVMs consider the kernel generated surfaces instead of hyperplanes and construct extra two different primal problems, which means that they have to solve two problems for linear case and two other problems for nonlinear case separately. Unlike the standard SVMs in which only one dual problem is solved for both cases with different kernels. Although TWSVMs only solve two smaller QPPs, they have to compute the inverse of matrices, it is in practice intractable or even impossible for a large data set by the classical methods, whereas in the standard SVMs, large scale problems can be solved efficiently by the well known sequential minimization optimization (SMO) algorithm. Only the empirical risk is considered in the primal problems of TWSVMs, and it is well known that one significant advantage of SVMs is the implementation of the structural risk minimization (SRM) principle.

In this paper, we propose a novel nonparallel SVM, termed NPSVM for binary classification NPSVM has the following advantages•

The semi-sparseness is promoted to the whole sparseness. Where semi-sparseness is when a quadratic loss function

•

•

•

•

making the proximal hyperplane close enough to the class itself, and a soft-margin loss function making the hyperplane as far as possible from the other class,which results that almost all the points in this class and some points in the other class contribute to each final decision function. The regularization term is added naturally due to the introduction of -insensitive loss function, and two primal problems are constructed implementing the SRM principle. The dual problems of these two primal problems have the same advantages as that of the standard SVMs, i.e., only the inner products appear so that the kernel trick can be applied directly. The dual problems have the same formulation with that of standard SVMs and can certainly be solved efficiently by SMO, we do not need to compute the inverses of the large matrices as TWSVMs usually do. The initial TWSVM or improved TBSVM are the special cases of our models. Our NPSVM degenerates to the initial TWSVM or TBSVM when the parameters of which are appropriately chosen, therefore, our models are certainly superior to them theoretically. II. BACKGROUND

term w and the empirical risk term at the same time. B. TWSVM

2

l i=1

ξi are minimized

Consider the binary classification problem with the training set T = {(x1 , +1), ..., (xp , +1), (xp+1 , −1), ...(xp+q , −1)} (4) where xi n , i = 1, ..., p + q. For the linear classification problem, TWSVM seeks two nonparallel hyperplanes (w+ · x) + b+ = 0 and (w− · x) + b− = 0 by solving two smaller QPPs min 1 2 p p+q

(5)

w+ ,b+ ,ξ−

((w+ · xi ) + b+ ) + d1 i=1 j=p+1

2

ξj

(6)

s.t. (w+ ·xj )+ b+ ≤ -1+ξj ,j=p+1,. . .,p+q ξj ≥ 0 j=p+1,. . .,p+q and min 1 2 ((w− · xi ) + b− ) + d2 ξj 2 i=p+1 j=1 p+q p

w− ,b− ,ξ+

(7)

In this section, we briefly introduce the C-SVC and two variations of TWSVM. A. C-SVC Consider the binary classification peoblem with the training set T = {(x1 , y1 ), ...., (xl , yl )} (1)

s.t. (w− · xj )+ b− ≥ 1-ξj j=1,. . .,p ξj ≥ 0,j=1,. . .,p where di , i = 1, 2 are the penalty parameters. For nonlinear classification problem, two kernel-generated surfaces instead of hyperplanes are considered and two other primal problems are constructed. C. TBSVM An improved ∗1 TWSVM, termed ∗2 TBSVM, is proposed in , whereas the structural risk is claimed to be minimized by adding a regularization term with the idea of maximizing some margin. For the linear classification problem, they solve the following two primal problems: min 1 ( w 2
2

where xi Rn , yi Y = {1,-1},i=1,....,l standard C-SVC formulates the problem as a convex QPP standard C-SVC formulates the problem as a convex QPP w,b,ξ min

1 2

w

2

+C

l i=1 ξi

s.t. yi ((w.xi ) + b) ≥ 1 − ξi ξi ≥ 0 i=1,....,l

(2)

w+ ,b+ ,ξ−

+b2 )+ +

c1 2

p

p+q

((w+ ·xi )+b+ )2 +c2 i=1 j=p+1

ξj (8)

where ξ = (ξ1 ,...,ξl ) , and C> 0 is a penalty parameter. For this primal problem, C-SVC solves its Lagrangian dual problem. minα 1 2 l l l

s.t. (w+ ·xi )+ b+ ≤ -1 +ξj , j=p+1,. . .,p+q, ξj ≥ 0 , j=p+1,. . .,p+q ——————————————————————————– TWSVM-Twin support vector machines (TWSVM) is based on the idea of proximal SVM based on generalized eigenvalues (GEPSVM), which determines two nonparallel planes by solving two related SVM-type problems, so that its computing cost in the training phase is 1/4 of standard SVM.
∗1 ∗2

αi αj yi yj K(xi , xj ) − i=1 j=1 i=1 l

αi

(3)

s.t. j=1 yi αi =0 0≤αi ≤ C,i = 1,..., l where K(x,x’) is the kernel function which is also a convex QPP and then constructs the decision function.The SRM principal is implemented in C-SVC: the confidential interval

TBSVM-Twin Bounded Support Vector Machine it is improved version of TWSVM.