Two-group classification via a biobjective margin maximization model

Two-group classification via a biobjective margin maximization model q Emilio Carrizosa * , Belen Martin-Barragan Departamento de Estadı ´stica e Investigacio ´n Operativa, Universidad de Sevilla, Avda. Reina Mercedes, s/n, 41012 Sevilla, Spain Received 15 October 2004; accepted 15 June 2005 Available online 18 November 2005 Abstract In this paper we propose a biobjective model for two-group classification via margin maximization, in which the margins in both classes are simultaneously maximized. The set of Pareto-optimal solutions is described, yielding a set of parallel hyperplanes, one of which is just the solution of the classical SVM approach. In order to take into account different misclassification costs or a priori probabilities, the ROC curve can be used to select one out of such hyperplanes by expressing the adequate tradeoff for sensitivity and specificity. Our result gives a theoretical motivation for using the ROC approach in case misclassification costs in the two groups are not necessarily equal. Ó2005 Elsevier B.V. All rights reserved. Keywords: Multiple objective programming; Support vector machines; Biobjective; ROC curve; Classification; Data mining 1. Introduction In the last decade, support vector machine (SVM), e.g., [1–5], has shown to be a powerful tool for the two-group classification problem. This method attempts to build a hyperplane with maximal margin that linearly separates the two groups, in the sense that it correctly classifies the whole set Iof objects in the database, and the distance to the closest point is maximized. When linear separation is not possible, perturbations in the model are allowed. Moreover, the use of SVM is theoretically justified by the dependence on the margin of certain bounds on the probability of misclassifying a forthcoming object, e.g., [6–8]. 0377-2217/$ - see front matter Ó2005 Elsevier B.V. All rights reserved. doi:10.1016/j.ejor.2005.06.059 q This research was partially supported by projects BFM2002-11282-E and BFM2002-04525-C02-02 of Ministerio de Ciencia y Tecnologı ´a (Spain) and FQM-329 of Plan Andaluz de Investigacio ´n (Andalucı ´a, Spain). * Corresponding author. E-mail addresses: [email protected] (E. Carrizosa), [email protected] (B. Martin-Barragan). European Journal of Operational Research 173 (2006) 746–761 www.elsevier.com/locate/ejor However, crude SVM cannot take into account different misclassification costs or known a priori probabilities. In this work, we formulate a new model in which margins between each class and the hyperplane are dealt independently. We study the simultaneous maximization of both margins, i.e., the distance to the closest point in each group. This yields a biobjective problem, whose Pareto-optimal solutions are sought. In other words, we seek the set of hyperplanes such that there is not any other hyperplane having greater margin for both classes, thus we expect their performance cannot be improved simultaneously with respect to both classes. Our main result states that the set of all Pareto-optimal solutions is described as a set of parallel hyperplanes, which can be easily computed. The paper is organized as follows: In Section 2, the problem is formally introduced, and notation is set. As in classical SVM approaches, we deal separately with the linearly separable case (Section 3) and the case in which the two classes are not linearly separable (Section 4). Some illustrative examples, as well as a visual procedure for choosing bbased on the receiver operating characteristic (ROC) curves are given in Section 5, ending with some concluding remarks. 2. The problem We have a set of objects X, each object uhaving two components u=(x u ,y u ). The first component x u is called the predictor vector and takes values in Rp, whose components x l ,l=1,2,...,p, are called predictor variables. The other component y u , takes values in the set of classes C¼f1;1gand is called the classmembership of object u. Object uis said to belong to class y u . In general, class-membership of objects in Xis known only for a subset I, called the training sample: both predictor vector and class-membership are known for u2I, whereas only x u is known for u2XnI. Denote by I c ={u2I:y u =c}, the set of objects of class c, for every c2C. We assume throughout this paper that each class is represented in the training sample, i.e., I c 5;,8c2C. Our framework to classify objects is as follows. We are seeking a score function of the form: fðxÞ¼X p k¼1 xkxkþb¼x>xþb;ð1Þ where x=(x 1 ,x 2 ,...,x p )50. Such a function defines a hyperplane in the predictor space Rp, given by fx2Rp:x>xþb¼0g. We identify with (x,b) such a hyperplane. An object u2Xwill be allocated to class 1iff(x u ) < 0, i.e., if x u belongs to the halfspace fx2Rp:x>xþb<0g. Analogously, uwill be allocated to class 1 if f(x u ) > 0, i.e., if x u belongs to the halfspace fx2Rp:x>xþb>0g. In case of ties, i.e., when x u belongs to the hyperplane, objects can be allocated randomly or by a prefixed order. Our problem is to find a hyperplane (x,b) correctly classifying all (or at least, most) objects u2I, and enjoying good generalization properties, in the sense that one can expect the good behavior obtained in Ito be generalized to X. In this paper, as done in classical SVM [2–4,6,7], we address first the case in which a hyperplane correctly classifying all objects in the training sample exists, and consider later the case in which such hyperplane does not exist. Let us give a formal definition of linear separability. Definition 1. A hyperplane (x,b), is said to separate linearly Iif yuðx>xuþbÞ>0;8u2I.ð2Þ Moreover, Iis said to be linearly separable if there exists a hyperplane (x,b) linearly separating I. E. Carrizosa, B. Martin-Barragan / European Journal of Operational Research 173 (2006) 746–761 747 3. The linearly separable case In this section, we address the case in which Iis linearly separable, i.e., (2) is satisfied by some (x,b). Although this condition may be rather restrictive, it is usually fulfilled in practice by mapping the data into a vector space of higher dimension, in such a way that the predictor vectors become linearly separable. See, e.g., [4,5]. The theoretical basis of SVM was developed by Vapnik et al. [3,6,7], where they gave bounds on the generalization ability of a linear classifier in terms of the margin, as defined, e.g., in [4]. Definition 2. Given the hyperplane (x,b), the margin of an object u, is defined as the Euclidean distance between x u and the hyperplane (x,b), with positive sign if uis correctly classified, and negative sign otherwise, i.e., quðx;bÞ¼yuðx>xuþbÞ kxk;ð3Þ where kÆkstands for the Euclidean norm. The margin of a class c2Cin the training sample Iis the minimum margin over all objects u2I c , qcðx;bÞ¼min u2Ic quðx;bÞ;ð4Þ and the margin of the training sample I, is the minimum over all the objects uin I qIðx;bÞ¼min u2Iquðx;bÞ.ð5Þ Under the assumption that Iis linearly separable, we can construct the so-called hard margin hyperplane [3,6,7], which is the hyperplane which linearly separates Iand has maximal margin q I . This is usually obtained by solving the problem min kxk2 s.t. yuðx>xuþbÞP1;8u2I; x2Rp;b2R. ð6Þ It is shown in [6,7] that (6) always has just one optimal solution. This approach does not take into account different misclassification costs or known a priori probabilities. We propose a novel approach, in which instead of maximizing the margin on I, we simultaneously maximize the margin on both classes as defined in (4). This yields the following biobjective optimization problem with open feasible region: max fq1ðx;bÞ;q1ðx;bÞg s.t. yuðx>xuþbÞ>0;8u2I; x2Rp;b2R;x6¼ 0. ð7Þ We seek the set of Pareto-optimal solutions to (7), i.e., the set of feasible solutions ð x; bÞsuch that no (x,b) exists such that q1ðx;bÞPq1ð x; bÞ; q1ðx;bÞPq1ð x; bÞ;ð8Þ 748 E. Carrizosa, B. Martin-Barragan / European Journal of Operational Research 173 (2006) 746–761 with at least one inequality strict. Note that, for u2I, quðlx;lbÞ¼quðx;bÞ;8l>0;8x2Rp;x6¼ 0;8b2R.ð9Þ Hence, for all l>0,x2Rp,x50, b2R, one has that q1ðlx;lbÞ¼q1ðx;bÞ; q1ðlx;lbÞ¼q1ðx;bÞ.ð10Þ Hence, if (x,b) is a Pareto-optimal solution to (7), then, for any l>0,(lx,lb) is also feasible for (7), and, by (10), it is also a Pareto-optimal solution to (7). Our final aim is to construct classifiers with adequate tradeoff of misclassification costs in the two groups in X. In other words, we ideally would solve the biobjective problem max fq1ðx;bÞ;q1ðx;bÞg s.t. yuðx>xuþbÞ>0;8u2X; x2Rp;b2R;x6¼ 0, ð11Þ by describing the set of Pareto-optimal solutions. Since the class y u of u2Xis known only for the objects u2I, we consider (7) as a surrogate of (11), and thus the set of Pareto-optimal solutions of (7) is seen as an approximation to the set of Pareto-optimal solutions of (11). First let us recall that ð x; bÞis a weakly efficient solution of Problem (7) if no feasible (x,b) exists that is strictly better than ð x; bÞfor both objectives, i.e., q1ðx;bÞ>q1ð x; bÞ; q1ðx;bÞ>q1ð x; bÞ.ð12Þ We refer the reader to, e.g., [9] for further details on these concepts of vector optimization. Since all feasible solutions (x,b) satisfy that q 1 (x,b) > 0 and q 1 (x,b) > 0 one can generate all weakly efficient solutions by solving max–min type scalarizations [9]. For the sake of completeness we state the following technical result: Lemma 3. The set of weakly efficient solutions of Problem (7)is obtained as the set of optimal solutions of max min fq1ðx;bÞ;hq1ðx;bÞg s.t. yuðx>xuþbÞ>0;8u2I; x2Rp;b2R;x6¼ 0; ð13Þ when h2(0, +1), in the sense that (1) any optimal solution of Problem (13)is weakly efficient for Problem (7), (2) for every weakly efficient solution (x h ,b h ) of Problem (7)there exists h2(0, +1), such that (x h ,b h )is optimal for Problem (13). For h2(0,+1), define Ah¼2h hþ1; yu h¼1ifu2I1; hif u2I1; ( E. Carrizosa, B. Martin-Barragan / European Journal of Operational Research 173 (2006) 746–761 749 and consider the convex quadratic problem min kxk2 s.t. yu hðx>xuþbÞPAh;8u2I; x2Rp;b2R. ðPhÞ Observe that Problem (6) is a particular case, since it corresponds to the case h=1. Lemma 4. One has: (1) For each h2(0, +1), Problem (P h )has a unique optimal solution (x h ,b h ), satisfying x h 50. (2) Given ðx;bÞ2RpR, the following statements are equivalent: (a) There exists h2(0, +1) such that (x,b) is optimal for Problem (P h ). (b)x=x 1 and jbb 1 j<1, where (x 1 ,b 1 ) is the optimal solution for Problem (P h )for h=1. Proof. For hgiven, since the function x#kxk 2 is strictly convex, there exists a unique x h such that any optimal solution (x,b) for Problem (P h )has x=x h . We show now that the set of optimal solutions of Problem (P h )is a singleton. For Problem (P h ), KKT conditions at (x h ,b), which are necessary and sufficient for optimality, are given by ku hP0;8u2I; 2xhX u2I khuyu hxu¼0; X u2I ku hyu h¼0; ku h½yu hðx> hxuþbÞAh¼0;8u2I. ð14Þ First of all, note that k h 50. Indeed, if ku h¼0 for all u2I, one would have x h = 0, which simultaneously implies, since (x h ,b) is feasible, that bPA h > 0 and b6Ah h<0. This is a contradiction, and hence k h 50. Hence, for any (x h ,b), optimal for (P h )there exists u2Isuch that yu hx> hxuþb  Ah¼0;ð15Þ i.e., b¼Ah yu h x> hxu.ð16Þ This means that the set of optimal solutions of Problem (P h )is finite. On the other hand, by convexity, for any two different optimal solutions of Problem (P h ), all the solutions in the segment between them are optimal. This contradicts the finiteness of the set of optimal solutions of Problem (P h ), yielding the conclusion that such a set has an unique solution, (x h ,b h ), with b h of the form (16) for some u2I. In order to prove the second part of the Lemma we show that for h2(0, +1) the unique optimal solution (x h ,b h ) of Problem (P h )is given by xh¼x1; bh¼b1þh1 hþ1. 750 E. Carrizosa, B. Martin-Barragan / European Journal of Operational Research 173 (2006) 746–761 To show this, let k 1 be the multipliers in (14) for h= 1 and define the multipliers k h as ku h¼ku 1;8u2I1; ku h¼1 hku 1;8u2I1. It is easy to see that (x h ,b h ,k h ) satisfies (14). Indeed, X u2I ku hyu hxu¼X u2I1 ku 1xuX u2I1 1 hku 1hxu¼X u2I ku 1yu 1xu¼2x1; and X u2I ku hyu h¼X u2I1 ku 1X u2I1 1 hku 1h¼X u2I ku 1yu 1¼0. Since, ku his equal to zero iff ku 1¼0, and in such a case, they trivially satisfy the last set of equations of (14), we just have to prove that for all u2Iwith ku 1>0, it holds yu hx> 1xuþbh  Ah¼0. ð17Þ Let u2I 1 such that ku 16¼ 0. By (14), one has x> 1xuþb1¼1. After substituting it into (17), it yields yu hx> 1xuþbh  Ah¼x> 1xuþb1þh1 hþ12h hþ1¼11¼0. ð18Þ Analogously, let u2I 1 such that ku 16¼ 0. Then, x> 1xuþb1¼1, and by substituting it into (17) it yields yu hðx> 1xuþbhÞAh¼hx > 1xuþb1þh1 hþ1  2h hþ1¼0. ð19Þ Hence, we conclude that (x 1 ,b h ) with bh¼b1þh1 hþ1, is the unique optimal solution of Problem (P h ).It means that the set of all optimal solutions of Problem (P h )for all h2(0, +1), is given by fðx1;bhÞ:h2ð0;þ1Þg ¼ ðx1;bÞ:b¼b1þh1 hþ1for some h2ð0;þ1Þ  ¼fðx1;bÞ:jbb1j<1g. Theorem 5. The set W of weakly efficient solutions of the biobjective Problem (7)is given by W¼fðlx1;lbÞ:jbb1j<1;l>0g; where (x 1 ,b 1 ) is the optimal solution of Problem (P 1 ). Proof. Let ð x; bÞ2RpR.ByLemma 3,ð x; bÞis weakly efficient for Problem (7) if and only if there exists h2(0,+1) such that ð x; bÞis an optimal solution of Problem (13). This is equivalent to ð x; bÞbeing optimal for min kxk min minu2I1yuðx>xuþbÞ;hminu2I1yuðx>xuþbÞ  s.t. yuðx>xuþbÞ>0;8u2I; x2Rp;b2R;x6¼ 0. ð20Þ E. Carrizosa, B. Martin-Barragan / European Journal of Operational Research 173 (2006) 746–761 751 Observe that (x,b) is optimal for (20) if and only if (lx,lb) is optimal for (20) for any l> 0. Hence, by normalizing the denominator in the objective of (20) we have that ð x; bÞis optimal for (20) if and only if there exist h2(0, +1) and l> 0 such that ðl x;l bÞis optimal for the following problem: min kxk s.t. min min u2I1 ðx>xuþbÞ;hmin u2I1 ðx>xubÞ  ¼Ah; x2Rp;b2R;x6¼ 0; ð21Þ where Ah¼2h hþ1. Such a problem is equivalent to the following one min kxk2 s.t. min min u2I1 ðx>xuþbÞ;min u2I1 hðx>xubÞ  PAh; x2Rp;b2R; ð22Þ which can be rephrased as min kxk2 s.t. yu 1ðx>xuþbÞPAh;8u2I1; hyu 1ðx>xuþbÞPAh;8u2I1; x2Rp;b2R;x6¼ 0. ð23Þ Since yu 1¼yu h;8u2I1 hyu 1¼yu h;8u2I1. Problem (23) is actually Problem (P h ). Hence, ð x; bÞis weakly efficient iff there exists l> 0 such that ðl x;l bÞsolves (P h )for some h2(0,+1). By Lemma 4, this is equivalent to ð x; bÞhaving the form (lx 1 ,lb) with jbb 1 j<1. h Corollary 6. The set of Pareto-optimal solutions of the biobjective Problem (7)is given by W, W¼fðlx1;lbÞ:jbb1j<1;l>0g. Proof. Any Pareto-optimal solution is, by definition, weakly efficient. Let us show the converse. Let ð x; bÞ be weakly efficient. By Lemma 4 and Theorem 5, there exist h2(0, +1) and l> 0 such that ðl x;l bÞsolves (P h ). Suppose ð x; bÞis not Pareto-optimal. Then ðl x;l bÞwould not be Pareto-optimal either. Hence there would exist (x0,b0) such that q1ðx0;b0ÞPq1ðl x;l bÞ¼q1ð x; bÞ; q1ðx0;b0ÞPq1ðl x;l bÞ¼q1ð x; bÞ; ð24Þ with at least one of those inequality strict. 752 E. Carrizosa, B. Martin-Barragan / European Journal of Operational Research 173 (2006) 746–761 Without loss of generality we can suppose that kx0k¼kl xk. Then (24) is equivalent to min u2I1 yuðx0>xuþb0ÞPmin u2I1 yuðl x>xuþl bÞPAh; min u2I1 yuðx0>xuþb0ÞPmin u2I1 yuðl x>xuþl bÞPAh.ð25Þ Hence, (x0,b0) would be feasible for Problem (P h ). Since its objective value at (x0,b0)iskx0k2¼kl xk2,we would have that (x0,b0) is also optimal for Problem (P h ).ByLemma 4,(P h )has a unique optimal solution. Thus x0¼l x, contradicting that at least one of the inequalities in (24) is strict. h 4. The nonseparable case When the set Iis not linearly separable, no hyperplane exists classifying correctly all data points, and thus problem (6) is infeasible. One can try to find a hyperplane minimizing the number of misclassified points. However, this problem is known to be NP-hard, and very difficult to solve in practice [10]. For these cases, the margin maximization approach can be extended to the so-called soft margin approach, e.g., [3–5], which consists of allowing some objects in Ito be misclassified, by perturbing (6) in order to make it feasible. In particular, one can replace (6) by its soft counterpart min kxk2þCX u2I ðnuÞ2; s.t. yuðx>xuþbÞþnuP1;8u2I; x2Rp;b2R;n2RjIj; ð26Þ where Cis a constant which is usually chosen by crossvalidation techniques, see, e.g., [11–13] and is used in order to tradeoff the perturbations n u and the classification scores x > x u +b. More generally, we can follow [14], where a more general approach is proposed, in which the perturbations are weighed by different parameters C 1 and C 1 , yielding the problem min kxk2þC1X u2I1 ðnuÞ2þC1X u2I1 ðnuÞ2; s.t. yuðx>xuþbÞþnuP1;8u2I; x2Rp;b2R;n2RjIj. ð27Þ The parameters C 1 and C 1 allow the incorporation of different a priori probabilities or misclassification costs in an approximate way [5]. The class chaving smaller a priori probability (or classification cost) should have the large C c value. For instance in [5] Cc¼1 nc, where n c denotes the number of objects in I c , for c2{1,1} is suggested. With this, a priori probabilities, as well as different misclassification costs for each class, can be taken into account to weight the perturbations, but not the margin itself, which is the main aim of this paper. As a generalization of Definition 2, now, the margin of an object u2I, is defined as quðx;b;nÞ¼yuðx>xuþbÞþnu kðx;nÞk;ð28Þ where kÆk * stands for the weighted Euclidean norm given by kðx;nÞk¼ffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi kxk2þC1X u2I1 ðnuÞ2þC1X u2I1 ðnuÞ2 s. E. Carrizosa, B. Martin-Barragan / European Journal of Operational Research 173 (2006) 746–761 753 The margin of a class c2{+1, 1} in a training sample I, and the margin of a training sample are defined as in Definition 2 for the linearly separable case. We will study now the Pareto-optimal solutions for the problem of simultaneous maximization of the margin in both classes, under the constraint that all the objects in the training sample are correctly classified in the feature space max fq1ðx;b;nÞ;q1ðx;b;nÞg s.t. yuðx>xuþbÞþnu>0;8u2I; x2Rp;b2R;n2RjIj. ð29Þ This is a nonlinear nonconvex biobjective problem whose feasible region is not closed. Analogously to the hard-margin approach one obtains the following result: Theorem 7. The set of Pareto solutions of the biobjective Problem (29)is given by W * W¼fðlx1;lb;ln1Þ:jbb1j<1;l>0g for (x 1 ,b 1 ,n 1 ) optimal solution of Problem (27). Proof. Since all feasible solutions (x,b,n) satisfy that q 1 (x,b,n) > 0 and q 1 (x,b,n) > 0 one can generate, as in Lemma 3, all weakly efficient solutions by solving max–min type scalarizations [9] of the form max min fq1ðx;b;nÞ;hq1ðx;b;nÞg s.t. yuðx>xuþbÞþnu>0;8u2I; x2Rp;b2R;n2RjIj; ð30Þ for hvarying in (0, +1). For hgiven, this problem is homogeneous. Hence, as we did in the linearly separable case, (x,b,n) is an optimal solution of (30) iff there exists l> 0 such that (lx,lb,ln) is optimal for the following problem: min kxk2þC1X u2I1 ðnuÞ2þC1X u2I1 ðnuÞ2 s.t. ðx>xuþbÞþnuPAh;8u2I1; ðhÞðx>xuþbÞþhnuPAh;8u2I1; x2Rp;b2R;n2RjIj; ð31Þ where Ah¼2h hþ1. Problem (31) is convex quadratic with linear constraints and KKT conditions are necessary and sufficient. Such conditions at the unique optimal solution (x h ,b h ,n h ) can be expressed as ku hP0;8u2I; 2xhX u2I1 ku hxuþX u2I1 hku hxu¼0; 2C1nu hku h¼0;8u2I1; 2C1nu hhku h¼0;8u2I1; X u2I ku hyu h¼0; ku hðx> hxuþbhÞþnu hAh  ¼0;8u2I1; ku hðhÞðx> hxuþbhÞþhnu hAh  ¼0;8u2I1. ð32Þ 754 E. Carrizosa, B. Martin-Barragan / European Journal of Operational Research 173 (2006) 746–761 [8] V. Vapnik, An overview of statistical learning theory, IEEE Transactions on Neural Networks 10 (1999) 988–999. [9] M. Ehrgott, M. Wiecek, in: Multiobjective Programming, Springer Science, New York, 2000, pp. 667–722 (Chapter 17). [10] L. Devroye, L. Gyo ¨rfi, G. Lugosi, Probabilistic Theory of Pattern Recognition, Springer, New York, 1996. [11] B. Efron, R. Tibshirani, Improvements on cross-validation: The .632+ bootstrap method, Journal of the American Statistical Association 92 (438) (1997) 548–560. [12] G. Wahba, Y. Lin, H. Zhang, Generalized approximate cross validation for support vector machines, in: Advances in Large Margin Classifiers, MIT Press, Cambridge, MA, 2000, pp. 297–311. [13] S. Weiss, C. Kulikowski, Computer Systems That Learn, Morgan Kaufmann, Los Altos, CA, 1999. [14] K. Veropoulos, N. Cristianini, C. Campbell, Controlling the sensitivity of support vector machines, in: Proceeding of SVM workshop at IJCAI99, 1999. [15] M. Kupinski, M. Anastasio, Multiobjective genetic optimization of diagnostic classifiers with implications for generating receiver operating characteristic curves, IEEE Transactions On Medical Imaging 18 (8) (1999) 675–685. [16] C. Blake, C. Merz, UCI Repository of Machine Learning Databases, Downloadable from website http://www.ics.uci.edu/ ~mlearn/MLRepository.html, University of California, Irvine, Dept. of Information and Computer Sciences, 1998. [17] A. Schwaighofer, SVM toolbox for Matlab, Downloadable from website http://www.cis.tugraz.at/igi/aschwaig/software.html, 2002. [18] C. Chang, C. Lin, LIBSVM: A library for support vector machines, Downloadable from website http://www.csie.ntu.edu.tw/ ~cjlin/libsvm, 2001. E. Carrizosa, B. Martin-Barragan / European Journal of Operational Research 173 (2006) 746–761 761