Multi-group support vector machines with measurement costs a biobjective approach

Multi-group Support Vector Machines with measurement costs: a biobjective approach ∗ Emilio Carrizosa. Facultad de Matem´aticas. Universidad de Sevilla (Spain). [email protected] Belen Martin-Barragan. Facultad de Matem´aticas. Universidad de Sevilla (Spain). [email protected] Dolores Romero Morales. Sa¨ıd Business School. University of Oxford (United Kingdom). [email protected].ac.uk July 28, 2005 Abstract Support Vector Machine has shown to have good performance in many practical classification settings. In this paper we propose, for multi-group classification, a biobjective optimization model in which we consider not only the generalization ability (modelled through the margin maximization), but also costs associated with the features. This cost is not limited to an economical payment, but can also refer to risk, computational effort, space requirements, etc. We introduce a biobjective mixed integer problem, for which Pareto optimal solutions are obtained. Those Pareto optimal solutions correspond to different classification rules, among which the user would choose the one yielding the most appropriate compromise between the cost and the expected misclassification rate. Keywords: Multi-group Classification, Pareto Optimality, Biobjective Mixed Integer Programming, Feature Cost, Support Vector Machines. ∗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 Investigaci´on (Andaluc´ıa, Spain). 1 1 Introduction In the last years operations researchers have made significant contributions to problems related with Data Mining (e.g. [2, 5, 8, 9, 23, 28]), such as Supervised Classification. Roughly speaking, supervised classification consists of building a rule to predict the classmembership of new objects from the same population than those in a given database. Support Vector Machine (SVM), e.g. [11, 13, 20], has shown to be a powerful tool for Supervised Classification. When only two groups exist, this method attempts to build a hyperplane with maximal margin that separates the two groups. Margin can be seen as a value that is zero when there are misclassified objects and otherwise it measures the confidence in the prediction, [1]. It has been shown (e.g. [11, 32, 33]) that this method enjoys good generalization properties, in the sense that one can expect the good behavior obtained in the available data to be generalized to the population which data come from, since the probability of misclassifying a forthcoming individual can be bounded by a function which is decreasing in the margin. Generalization ability, addressed via margin maximization, will be our first goal. However, in real-word classification problems it is very convenient to obtain classification rules that, not only achieve good classification behavior, but are also cheap or quick. A typical example is medical diagnosis, where some tests are much more expensive or take much longer than others. If the classification rule does not use variables based on the most expensive tests, classifying new patients will be much cheaper or quicker, perhaps without deteriorating significantly the quality of classification. Together with misclassification costs, which are related with the generalization ability of the rule, other costs, linked to the variables or attributes, can be defined. In the simplest model we associate equal costs to each feature; keeping the total cost below a given level amounts to stating an upper bound on the number of features to be used. Turney [31] proposed other types of nontrivial cost, for instance the test cost, also called measurement cost, where each test (attribute, measurement, feature) has an associated cost, such as economical payment, computational effort or some kind of complexity. The aim of minimizing such costs has been mentioned before in the literature as a desirable consequence of feature selection, see e.g. [18], but hardly directly addressed. In this paper, we address classification problems in which both misclassification rate and measurement costs are relevant. To do this, we formulate a biobjective program of simultaneous minimization of misclassification rate, via the maximization of the margin (the natural measure in SVM), and measurement costs. Pareto-optimal solutions, i.e. classifiers that cannot be improved at the same time in both objectives, are sought. The set of Pareto-optimal solutions of the biobjective program gives us a finite set of classification rules, in such a way that any rule which is not Pareto-optimal should be discarded, since it is beaten in terms of margin and cost by another rule. Choosing one out of the set of Pareto-optimal rules is done by choosing an appropriate compromise between the two criteria involved. We have structured the paper as follows. In Section 2 the problem is formally in2 troduced. In Section 3 we model the first goal: the measurement cost. Maximizing the margin, as a surrogate of minimizing the misclassification rate, will be our second goal. Formal definitions of margin are given in Section 4, by generalizing the concept of margin for two groups. A Biobjective Mixed Integer Program formulation is given in Section 5, where a method to find the Pareto-optimal classifiers, the Two-Phase Method [34], is proposed. In Section 6, such biobjective formulations are modified to allow some points in the training sample to be misclassified. Doing this we avoid the problem called overfitting. Finally, some numerical results are presented in Section 7. 2 The problem We have a finite set of classes C={1,2, . . . , C},and a set of objects Ω,each object u having two components (xu, cu).The first component xuis called the predictor vector and takes values in a set X. The set Xis usually assumed to be a subset of IRp,and then, the components xl, l = 1,2, . . . , p, of the predictor vector xare called predictor variables. The other component cu,with values in the set of classes C,is called the class-membership of object u. Object uis said to belong to class cu. In general, class-membership of objects in Ω is known only for a subset I, called the training sample: both predictor vector and class-membership are known for u∈I, whereas only xuis known for u∈Ω\I. For any c∈ C,denote by Icthe set of objects in Ibelonging to class c:Ic= {u∈I:cu=c}.We assume that each class is represented in the training sample, i.e., Ic6=∅ ∀c∈ C. We use a classification model in which a score function,f= (fc)c∈C with fc:X−→ IR, enables us to classify (allocate) any z∈Xas member of one of the classes as follows zis allocated to the class cif fc(z)> fj(z),∀j6=c, (1) i.e. zis allocated to the class c∗whose score function is highest: c∗= arg max c∈C fc(z).(2) Notice that in case of ties, the object will be unclassified by this rule, and can be later allocated randomly or by a prefixed order to some class in arg maxc∈C fc(z).Following a worst-case approach, we will consider those objects as misclassified throughout the paper. Score functions fcare assumed to have the form fc(x) = N X k=1 αc kφk(x) + βc,(3) where αc∈IRN, βc∈IR, and G={φ1, φ2, . . . , φN}is a finite set of real-valued functions on X. Hence, each fcbelongs to a vector space F,generated by G.For instance, linear 3 classifiers correspond to scores generated by G={x1, x2, . . . , xp},(4) whereas quadratic classifiers, [15, 16], are obtained by setting G={x1, x2, . . . , xp}[{xixj: 1 ≤i≤j≤p}(5) i.e., the set of monomials of degree up to 2. This framework also includes voting classifiers, such as boosting, e.g. [14, 17], in which C={1,2}and a set of primitive classifiers φk:X→ {0,1} φk(x) = 1 iff xis allocated to class 1 via the k-th classifier, (6) are combined linearly into a single score function of the form (3). For a very promising strategy for generating such primitive classifiers see e.g. [7]. Denote the coefficients of the score function by A= (α1, . . . , αC) and b= (β1, . . . , βC). The problem of choosing fis reduced to the choice of its coefficients (A, b). Definition 1 f= (fc)c∈C with fc:X−→ IR, is said to separate {Ic:c∈ C} if fcu(xu)> fj(xu)∀j6=cu,∀u∈I. (7) Moreover, {Ic:c∈ C} is said to be separable by the space Fif there exists f= (fc)c∈C, with fc∈ F,separating {Ic:c∈ C}. Now we compare the definition of separability given in Definition 1 with those existing in the literature, [1, 19, 20, 32]. For the two-group case, C={1,2},our definition is equivalent to the classical definition of separability stating that the convex hulls of {φ(xu) : u∈I1}and {φ(xu) : u∈I2}are contained in open halfspaces with a common hyperplane as boundary. Property 2 Let C={1,2}.{Ic:c∈ {1,2}} is separable iff there exists (ω, γ)∈(IRN\ {0})×IR such that ω>φ(xu) + γ > 0∀u∈I1 ω>φ(xu) + γ < 0∀u∈I2.(8) Proof. Take ω=α1−α2, γ =β1−β2and conversely, given (ω, γ),satisfying (8), setting α1=ω, β1=γ, α2= 0 and β2= 0,we have a score function that correctly classifies {Ic:c∈ {1,2}} .2 For the multi-group case, |C| >2,we have that, together with the concept of separability given in Definition 1, a natural alternative exists: we will say that {Ic:c∈ C} is one-against-rest separable (OAR-separable) iff for all c1∈ C,{Ic1,Sc∈C\{c1}Ic}is separable. 4 Property 3 One has OAR-separability ⇒separability Proof. Let {Ic:c∈ C} be OAR-separable. It means that, for each class c1,we have two score functions: fc1associated with Ic1,and fc1,associated with the objects in the remaining classes Sc∈C\{c1}Ic.Since (fc1, fc1) separates {Ic1,Sc∈C\{c1}Ic},then fc1(xu)> fc1(xu)∀u∈Ic1 f0 c1(xu)> fc1(xu)∀u∈Sc∈C\{c1}Ic(9) Set gc=fc−fc,for each c∈ C.Then gc(xu)>0 iff u∈Ic.The function g= (g1, g2, . . . , gC) trivially separates {Ic:c∈ C} .Hence, OAR-separability implies separability. 2 Notice that the converse implication does not hold: for instance, in Figure 1 we have three classes 1,2,3 with elements denoted respectively by crosses (points (4,−3),(1,0) and (4,3)), stars (points (−1,−1) and (3,−4)) and circles (points (−1,1) and (3,4)), which, as one can see in Figure 1, are not OAR-separable, but they are separable by the following score function, f1(x1, x2) = x1 f2(x1, x2) = −x2 f3(x1, x2) = x2. The definition of separability, as given in Definition 1, depends on the generator G. Under weak assumptions, there exists a generator, G,rich enough to enable separability of {Ic:c∈ C} . Property 4 If Xis a subset of IRpand xu6=xv,∀u, v ∈Iwith cu6=cv,then there exists a finite generator Gsuch that {Ic:c∈ C} is separable in the space Fgenerated by G. Proof. For each c∈ C,consider the function fc(x) = −Y u∈Ic d(x, xu)2 where d(·,·) stands for the Euclidean distance. This function is zero for all xuwith u∈Ic and strictly negative otherwise. Then, for u∈Ic,and c06=c, fc(xu)−fc0(xu) = −fc0(xu)>0, thus, such set of functions separates {Ic:c∈ C}. Moreover, each fcis a polynomial in the variables x1, x2, . . . , xp,then it can be written as fc(x) = X h=(h1,...,hp)∈{0,1,...,2|Ic|}p αc h p Y k=1 (xk)hk,(10) 5 -4 -2 02468 -6 -4 -2 0 2 4 6 Figure 1: separable, but not OAR-separable belonging to the space Fgenerated by Gthe set of monomials of degree up to 2|I|.2 Suppose that Fis rich enough to enable separability, which ensures the existence of separating functions f. However, uniqueness never holds. Indeed, it is easy to see that given (ˆα, ˆ β)∈IRN+1 the classification rules obtained by (A, b) and ( ˜ A,˜ b) with ˜αc=λαc+ˆα and ˜ βc=λβc+ˆ βfor all c∈ C,are equivalent for all λ > 0,in the sense that both allocate objects to the same classes. Moreover, there are also more than one score function that separates {Ic:c∈ C} and they are not equivalent. For instance, given a score function separating {Ic:c∈ C} ,let εbe any number satisfying: 0< ε < min u∈Imin j6=cu{fcu(xu)−fj(xu)}. The function fε= (f1+ε, f2, . . . , fC) also separates {Ic:c∈ C} .We need a criterion for choosing one of them. Following Vapnik’s publications in generalization ability, e.g. [32], we will use the margin maximization criterion, as will be explained in Section 4. 6 3 Measurement costs Finding classifiers separating conveniently the groups is a plausible criterion when obtaining the predictor vector xuis costless. When this is not the case, we should also take into account the cost associated with the evaluation of the classification rule. In many practical applications, as medical diagnosis, the predictor variables of the data may be some diagnosis test (such as blood test, ...) that have associated a cost, either money, or risk/damage incurred to the patient. If the classifier built does not depend on some of these variables, we could avoid their measurement (and the corresponding cost) in the diagnosis of new patients. In this situation, we should seek a classifier that enjoys good generalization properties, and at the same time, has low cost. Obtaining cheaper or quicker classification rules have been mentioned as one of the desirable consequences of feature selection, where the aim is to reduce the number of variables or features used by the classification rule. However costs associated with such variables or features have seldom been considered. Several authors have addressed measurement cost issues related with classification. For instance, [24, 25, 30] consider classification trees whose branching rule takes such costs into account. See [31] for a comparison of such methods and [3, 31] and the references therein for other proposals. In most cases, the unique goal is to minimize some surrogate of the expected misclassification cost, and, since the algorithm takes somehow into account measurement costs, it is hoped that the measurement cost of individuals with the rule obtained this way is not too high. In this paper, however, we explicitly consider the minimization of measurement costs as one criterion, whose trade-off with margin optimization is to be determined by the user. Costs are modelled as follows: Denote by Πkthe cost associated with evaluating the feature φk∈ G at a given x. For instance, if we are following a linear approach, as given by (4), Πlrepresents the cost of measuring the predictor variable lin a new object. Given the parameter A= (α1, . . . , αC),define S(A) = {k| ∃c∈ C :αc k6= 0,1≤k≤N}. In other words, S(A) represents the set of features we have to use in order to classify new objects. In principle, these are the features we have to pay for, so a score function with coefficients (A, b) will have associated a measurement cost equal to π(A, b) = X k∈S(A) Πk.(11) Pure linearity, as assumed in (11), may be unrealistic in some practical situations. For instance, it may be the case that, once we have incurred a cost for obtaining some feature φk,some other features may be given for free or at reduced cost. This may happen, for example, in a medical context when the measurement of a variable requires a blood 7 extraction, and some other variables can be measured using the same blood test. Another context where one encounters this, is the case in which some features are functions of other features: In model (5), feature φ(x) = xixjis obtained for free if both features φ(x) = xi and φ(x) = xjhave been previously inspected. In Table 1 one can see the costs of a simple example with two classes C= 2,and G={φ1, . . . , φ5}with different costs. features φ1φ2φ3φ4φ5 costs 2 5 3 0 2 Table 1: Example of feature cost. The score function given by f1=φ1+ 4φ5and f2= 3φ1+ 2 incurs a cost of 2 + 2 = 4. Suppose that precedence constraints, in the form of a partial order ≺between the features, is given. This means that if hk, the use of the feature φkrequires also the payment for feature φh.Moreover, in computing the total cost, the cost for every feature has to be summed at most once. In order to formalize this, define an auxiliary variable zk∈ {0,1}for each k= 1, . . . , N, representing zk=1 if payment of Πkis needed 0 otherwise (12) in other words: zk=1 if h∈S(A) for some hwith kh 0 otherwise (13) Thus, cost associated with a score function with coefficients (A, b) will be π(A, b) = N X k=1 zkΠk.(14) Particular cases already suggested in the literature can be easily accommodated into our framework. For instance, in [26] variables are grouped in a way that, if one variable from a group is requested, then all the others in the same group are available for zero additional cost. To model this case in our setting, define the cost of one variable from each group to be equal to the cost of the group it belongs to, and set the remaining variables to have zero cost. Moreover, choose a partial order ≺for which h≺jiff variables hand jare in the same group and hhas nonzero cost. Moreover, this modelling technique allows us to use, but it is not limited to, polynomial kernels. Indeed, suppose a kernel k(x, y) = Φ(x)>Φ(y) for some Φ : X→F. If Φ holds •Fis a finite dimensional feature space,F⊂IRN, 8 •for any component φk, k = 1,2, . . . , N of Φ = (φ1, φ2, . . . , φN),the information about what original variables are needed to calculate φkis available, then, the cost associated to a score function can be modelled using the methodology explained in this section. We will show in Sections 5 and 6, that this modelling technique allows formulations as Biobjective Mixed Integer Programs. For these models there exist suitable techniques for finding their Pareto-optimal solutions. Biobjective problems for more general problems, such as e.g. measurement cost minimization using kernels which are not of polynomial type, [36], can also be formulated. However, they yield combinatorial problems which are much harder to solve in practice. Minimizing (14) will be one of our goals. However, our main goal is finding classifiers with good generalization properties. This, the second objective in our model, will be discussed in detail in the following section. 4 Margin optimization Throughout this section, unless explicitly stated, we assume that Fis rich enough to enable separability: Assumption 1 {Ic:c∈ C} is separable by F. We may observe that we can always consider Fas in Property 4, and therefore Assumption 1 will be hold. However we expect in practice to attain separability with smaller generators. Since by Assumption 1 objects in Iwill be correctly classified, the substantial matter is the classification of objects u∈Ω\I. Hence, we are interested in obtaining classifiers with good generalization properties, via margin maximization,[11, 32, 33]). The concepts of functional and geometrical margin, introduced in Cristianini and Shawe-Taylor [13] for the case of two groups, are extended below to the multi-group case. Definition 5 The functional margin of an object uwith respect to the score function f, with coefficients (A, b),is the quantity ˆ θu(A, b) = min j6=cu{fcu(xu)−fj(xu)}(15) The functional margin of a score function f, with coefficients (A, b)with respect to a training sample Iis equal to ˆ θI(A, b) = min u∈I ˆ θu.(16) We immediately obtain 9 In order to both avoid overfitting and deal with the non-separability of I, the typical SVM approach, called soft-margin maximization [13], is based on allowing some objects in Ito be misclassified. This is done by adding to the model some slack variables ξ∈IRn +, where nis the cardinal of the training sample. Using this idea, the biobjective Problem (28) is replaced by the following problem: max y min PN k=1 Πkzk s.t. :PN k=1 φk(xu)αi k−αj k+βi−βj−y+ξu≥0,∀i6=j;i, j ∈ C, u ∈Ii kAk+γPu∈Iξu≤N −N zk≤Pk:hkPC c=1 αc k≤N zh∀h= 1,2, . . . , N αc kunrestricted ∀k= 1,2, . . . , N;c∈ C yunrestricted βc≥0∀c∈ C zk∈ {0,1} ∀k= 1,2, . . . , N ξu≥0∀u∈I, (32) for some user-defined value γ, which trades off the perturbations ξuand the margin. In the same way as for the hard-margin approach, when k·kis a polyhedral norm, this problem can be formulated as a Biobjective Mixed Integer Problem. For instance, if k·kis a scaled L1-norm, then Problem (32) can be formulated as follows: max y min PN k=1 Πkzk s.t. :PN k=1 φk(xu)αi +k−αi −k−αj +k+αj −k+βi−βj−y+ξu≥0, ∀i6=j;i, j ∈ C, u ∈Ii PC c=1 PN k=1 αc +k+αc −k+γPu∈Iξu≤N Pk:hkPC c=1 αc +k+αc −k≤N zh∀h= 1,2, . . . , N yunrestricted αc +k≥0∀k= 1,2, . . . , N;c∈ C αc −k≥0∀k= 1,2, . . . , N;c∈ C βc≥0∀c∈ C zk∈ {0,1} ∀k= 1,2, . . . , N ξu≥0∀u∈I (33) The Two-Phase Method proposed in Section 5 to find the Pareto-optimal classifiers can also be used for solving (33). Note that in this case, the solution with minimal (zero) cost is not the trivial solution (A, b) = (0,0),but any optimal solution (33) with Aset equal to the null matrix. The following steps of the method remain analogous to the hard-margin approach, and will not be repeated here. 16 7 Numerical results In order to explore both, costs and quality, of the Pareto score functions obtained, we have performed a series of numerical tests on four standard databases, publicly available from the UCI Machine Learning Repository [6], namely, the BUPA Liver-disorders Database, called here bupa; the Pima Indians Diabetes Database, called here pima; the New Diagnostic Database, contained in the Wisconsin Breast Cancer Databases, called here wdbc, and the Credit Screening Databases, called here credit. For each database, the name of the file (as called in the database), the total number of objects |Ω|, the number of groups Cand the number of variables (all quantitative) p are given in Table 2. Database filename |Ω|C p bupa bupa.data 345 2 6 pima pima-indians-diabetes.data 768 2 8 wdbc wdbc.data 569 2 30 credit crx.data∗768 2 8 Table 2: Parameters of the databases. ∗only the numerical variables were used. For the sake of simplicity, the features are chosen as the original variables in the database x1, x2, . . . , xpand their products, yielding monomials of degree up to g. However, other feature spaces, as those proposed by [7], might give better classification rates. Two types of costs are considered for the original variables. For the four databases, costs are independently chosen, randomly in the interval (0,1).Moreover, for the databases bupa and pima there exists a file, donated by Turney [31] and publicly available in the UCI repository [6], which contains an example for possible costs for the measurement of the variables. The cost information comes from the Ontario Health Insurance Program’s fee schedule. For these databases we have also considered such given costs. The remaining features have zero cost. The partial order is given as follows: feature φ=xkprecedes all features of the form φ(x) = xkq(x) for some monomial q(x) of degree up to g−1. Data were standardized by subtracting its mean and dividing by its standard deviation. Then, from each database, a random sample with two thirds of the objects is drawn and used as training sample I. The supported Pareto-optimal solutions of Problem (32) were computed by the first phase of the Two-Phase Method [34], described in Section 5. The non-supported Pareto-optimal solutions can also be computed using formulation (31). The trade-off parameter γis chosen to be equal to the number of objects in I. The results are plotted in Figures 2-9. In the right side of such figures, measurement costs of the Pareto-optimal rules (except for zero-cost solutions) are plotted against the margin. Since only Pareto-optimal solutions are considered, we see that, the higher the cost, the higher the margin. 17 'Bupa', g=1. Random Costs. 50 55 60 65 70 75 80 85 90 95 100 0 0.5 1 1.5 2 2.5 3 cost correctly classified Testing 'Bupa', g=1. Random Costs. 0.000145 0.000146 0.000147 0.000148 0.000149 0.00015 0.000151 0.000152 0.000153 0.000154 0.000155 0 0.5 1 1.5 2 2.5 3 cost margin Figure 2: Database ‘bupa’, g= 1,random costs. This is the plot the final user will obtain in real-world applications, and chose, with this information, one classification rule. However, margin maximization is only a surrogate for the minimization of the misclassification rate, which will remain unknown. In the right side of Figures 2-9 we have plotted, for the Pareto-optimal classifiers obtained, costs against the percentage of correctly classified objects in the testing sample. Figures show clearly that high correct classification rates correspond to high costs. Moreover, the trade-off between measurement costs and margin translates into a similar trade-off between measurement costs and percentage of correctly classified objects. method ‘bupa’ ‘pima’ ‘wdbc’ ‘credit’ 1-Nearest Neighbor 60.87 64.84 94.74 72.07 2-Nearest Neighbor 57.39 69.14 94.21 70.72 3-Nearest Neighbor 60.00 72.27 95.26 73.87 4-Nearest Neighbor 60.87 72.27 95.26 72.52 5-Nearest Neighbor 62.61 71.48 95.79 72.07 Classification Tree 67.83 70.31 90.53 72.97 SVM with linear kernel 72.17 74.22 95.79 77.48 SVM with polynomial kernel, grade =2 66.96 38.28 94.21 65.32 SVM with polynomial kernel, grade =3 59.13 66.41 93.68 69.37 SVM with polynomial kernel, grade =4 58.26 62.89 89.47 59.01 SVM with polynomial kernel, grade =5 57.39 67.19 91.58 75.23 SVM with radial basis function kernel 68.70 64.84 63.16 77.48 Table 3: Behavior of other methods. 18 'Bupa', g=1. Turney Costs. 50 55 60 65 70 75 80 85 90 95 100 0 200 400 600 800 1000 1200 cost correctly classified Testing 'Bupa', g=1. Turney Costs. 0.000142 0.000144 0.000146 0.000148 0.00015 0.000152 0.000154 0.000156 0 200 400 600 800 1000 1200 cost margin Figure 3: Database ‘bupa’, g= 1,Turney’s costs. For comparative purposes, in Table 3, the percentage of correctly classified objects is shown for different classification methods, such as classification trees [10], k−nearest neighbor classifier [12] and the classical SVM approach as implemented in SVMlight [21]. It can be observed that the classification behavior of the Pareto-optimal classifiers are among the best ones, even for low classification costs. The method proposed in this paper, can thus be seen as a procedure that generates a series of classification rules with different costs, and expected good classification behavior supported by the theoretical generalization properties of the margin maximizer (e.g. Vapnik [33]). Choosing one classification rule among them can be done by the user after plotting the measurement costs against margins, as illustrated in the examples. References [1] E.L. Allwein, R.E. Schapire, and Y. Singer. Reducing multiclass to binary: A unifying approach for margin classifiers. Journal of Machine Learning Research, 1:369–409, 2000. [2] C. Apte. The big (data) dig. OR/MS Today, February 2003. [3] V. Bayer Zubek. Learning Cost-Sensitive Diagnostic Policies from Data. PhD thesis, Oregon State University, July 2003. http://eecs.oregonstate.edu/library/?call=200313. [4] K. Bennet. Combining support vector and mathematical programming methods for induction. In Advances in Kernel Methods - Support Vector Learning, 1999. 19 'Pima', g=1. Random Costs. 50 55 60 65 70 75 80 85 90 95 100 0 0.5 1 1.5 2 2.5 3 3.5 4 cost correctly classified Testing 'Pima', g=1. Random Costs. 0.000054 0.000055 0.000056 0.000057 0.000058 0.000059 0.00006 0.000061 0.000062 0.000063 0.000064 0 0.5 1 1.5 2 2.5 3 3.5 4 cost margin Figure 4: Database ‘pima’, g= 1,random costs. [5] K.P. Bennet and O.L. Mangasarian. Robust linear programming discrimination of two linearly inseparable sets. Optimization Methods and Software, 1:23–24, 1992. [6] C.L. Blake and C.J. Merz. UCI Repository of Machine Learning Databases. http://www.ics.uci.edu/∼mlearn/MLRepository.html, 1998. University of California, Irvine, Dept. of Information and Computer Sciences. [7] E. Boros, P. L. Hammer, T. Ibaraki, and A. Kogan. A logical analysis of numerical data. Mathematical Programming, 79:163–190, 1997. [8] P. Bradley, O. Mangasarian, and D. Musicant. Optimization methods in massive datasets. In J. Abello, P.M. Pardalos, and M.G.C. Resende, editors, Handbook of Massive Datasets, pages 439–472. Kluwer Academic Pub., 2002. [9] P.S. Bradley, U.M. Fayyad, and O.L. Mangasarian. Mathematical programming for data mining: formulations and challenges. INFORMS Journal on Computing, 11(3):217–238, 1999. [10] L. Breiman, J.H. Friedmann, R.A. Olshen, and C.J. Stone. Classification and Regresion Trees. Wadsworth, Belmont, CA, 1984. [11] C. Cortes and V. Vapnik. Support-vector network. Machine Learning, 1:113–141, 1995. [12] T.M. Cover and P.E. Hart. Nearest neighbor pattern classification. IEEE Transactions on Information Theroy, 13:21–27, 1967. [13] N. Cristianini and J. Shawe-Taylor. An introduction to support vector machines. Cambridge University Press, 2000. 20 'Pima', g=1. Turney Costs. 50 55 60 65 70 75 80 85 90 95 100 0 1020304050 cost correctly classified Testing 'Pima', g=1. Turney Costs. 0.0000614 0.0000616 0.0000618 0.000062 0.0000622 0.0000624 0.0000626 0.0000628 0.000063 0 1020304050 cost margin Figure 5: Database ‘pima’, g= 1,Turney’s costs. [14] A. Demiriz, K. P. Bennett, and J. Shawe-Taylor. Linear programming boosting via column generation. Machine Learning, 46(1):225–254, 2002. [15] A.P. Duarte Silva and A. Stam. Second order mathematical programming formulations for discriminant analysis. European Journal of Operational Research, 72:4–22, 1994. [16] J.E. Falk and V.E. Karlov. Robust separation of finite sets via quadratics. Computers and Operations Research, 28:537–561, 2001. [17] Y. Freund and R.E. Schapire. A decision-theoretic generalization of on-line learning and an application to boosting. Journal of Computer and System Sciences, 55(1):119– 139, 1997. [18] I. Guyon and A. Elisseff. An introduction to variable and feature selecion. Journal of Machine Learning Research, 3(1157-1182), 2003. [19] T. Hastie and R. Tibshirani. Classification by pairwise coupling. The Annals of Statistics, 26(2):451–471, 1998. [20] R. Herbrich. Learning Theory Classifiers. Theory and Algorithms. MIT Press, 2002. [21] T. Joachims. Learning to Classify Text Using Support Vector Machines. Kluwer, 2002. [22] O.L. Mangasarian. Linear and nonlinear separation of patterns by linear programming. Operations Research, 13:444–452, 1965. 21 'Credit', g=1. Random Costs. 50 55 60 65 70 75 80 85 90 95 100 0 0.5 1 1.5 2 2.5 cost correctly classified Testing 'Credit', g=1. Random Costs. 0 0.00001 0.00002 0.00003 0.00004 0.00005 0.00006 0.00007 0 0.5 1 1.5 2 2.5 cost margin Figure 6: Database ‘credit’, g= 1,random costs. [23] O.L. Mangasarian. Mathematical programming in data mining. Data Mining and Knowledge Discovery, 42(1):183–201, 1997. [24] S.W. Norton. Generating better decision trees. In Proceedings of the Eleventh International Joint Conference on Artificial Intelligence, IJCAI-89, pages 800–805, Detroit, Michigan, 1989. [25] M. N´u˜nez. The use of background knowledge in decision tree induction. Machine Learning, 6:231–250, 1991. [26] P. Pacl´ık, R.P.W. Duin, G.M.P. van Kempen, and R. Kohlus. On feature selection with measurement cost and grouped features. Lecture Notes in Computer Science, 2396(461-469), 2002. [27] J.P. Pedroso and N. Murata. Support vector machines with different norms: motivation, formulations and results. Pattern recognition letters, 22:1263–1272, 2001. [28] A.M. Rubinov, A.M. Bagirovand, N.V. Soukhoroukova, and J. Yearwood. Unsupervised and supervised data classification via nonsmooth and global optimization. TOP, 11(1):1–93, 2003. [29] A. Smola, T.T. Friess, and B. Sch¨olkopf. Semiparametric support vector and linear programming machines. In Advances in Neural Information Processing Systems 10, pages 585–591, 1999. [30] M. Tan. Cost-sensitive learning of classification knowledge and its applications in robotics. Machine Learning, 13:7–33, 1993. 22 'Credit', g=2. Random Costs. 50 55 60 65 70 75 80 85 90 95 100 0 0.5 1 1.5 2 2.5 cost correctly classified Testing 'Credit', g=2. Random Costs. 0 0.00005 0.0001 0.00015 0.0002 0.00025 0.0003 0.00035 0 0.5 1 1.5 2 2.5 cost margin Figure 7: Database ‘credit’, g= 2,random costs. [31] P.D. Turney. Cost-sensitive classification: Empirical evaluation of a hybrid genetic decision tree induction algorithm. Journal of Artificial Intelligence Research, 2:369– 409, 1995. [32] V. Vapnik. The nature of statistical learning theory. Springer-Verlag, 1995. [33] V. Vapnik. Statistical learning theory. Wiley, 1998. [34] M. Vis´ee, J. Teghem, M. Pirlot, and E.L. Ulungu. Two-phases method and branch and bound procedures to solve the bi-objective knapsack problem. Journal of Global Optimization, 12:139–155, 1998. [35] J. Weston, A. Gammerman, M.O. Stitson, V. Vapnik, V. Vovk, and C. Watkins. Support vector density estimation. In Advances in Kernel Methods - Support Vector Learning, 1999. [36] J. Weston, S. Mukherjee, O. Chapelle, M. Pontil, T. Poggio, and V. Vapnik. Feature selection for SVMs. In Advances in Neural Information Processing Systems 13, 2001. 23 'Wdbc', g=1. Random Costs. 50 55 60 65 70 75 80 85 90 95 100 0 2 4 6 8 10 12 14 cost correctly classified Testing 'Wdbc', g=1. Random Costs. 0.55 0.57 0.59 0.61 0.63 0.65 0.67 0.69 0.71 0.73 02468101214 cost margin Figure 8: Database ‘wdbc’, g= 1,random costs. 'Wdbc', g=2. Random Costs. 50 55 60 65 70 75 80 85 90 95 100 0 2 4 6 8 10 12 14 cost correctly classified Testing 'Wdbc', g=2. Random Costs. 0 5 10 15 20 25 30 35 40 02468101214 cost margin Figure 9: Database ‘wdbc’, g= 2,random costs. 24