Strongly agree or strongly disagree? Rating features in support vector machines

Strongly Agree or Strongly Disagree?: Rating Features in Support Vector Machines Emilio Carrizosa Universidad de Sevilla (Spain) [email protected] Amaya Nogales-Gómez Universidad de Sevilla (Spain) [email protected] Dolores Romero Morales University of Oxford (United Kingdom) [email protected] October 15, 2013 Abstract In linear classiers, such as the Support Vector Machines (SVM), a score is associated with each feature and objects are assigned to classes based on the linear combination of the scores and the values of the features. Inspired by discrete psychometric scales, which measure the extent to which a factor is in agreement with a statement, we propose the Discrete Level Support Vector Machines (DILSVM) where the feature scores can only take on a discrete number of values, dened by the so-called feature rating levels. The DILSVM classier benets from interpretability as it can be seen as a collection of Likert scales, one for each feature, where we rate the level of agreement with the positive class. To build the DILSVM classier, we propose a Mixed Integer Linear Programming approach, as well as a collection of strategies to reduce the building times. Our computational experience shows that the 3-point and the 5-point DILSVM classiers have comparable accuracy to the SVM with a substantial gain in interpretability and sparsity, thanks to the appropriate choice of the feature rating levels. Keywords: Support Vector Machines, Mixed Integer Linear Programming, Likert scale, interpretability, feature rating level. 1 Introduction Supervised Classication , (Apte 2003, Hand et al. 2001, Wu et al. 2007), based on large datasets, plays an important role in many industries, with notable examples being credit 1 scoring (Baesens et al. 2003), fraud detection (Cecchini et al. 2010), customer targeting (Archak et al. 2011, Cui et al. 2006), and surveillance (Fang et al. 2013). In Supervised Classication, we are given a set of objects Ω partitioned into classes and the aim is to build a procedure for classifying new objects. In its simplest form, each object i∈Ω has associated a pair (xi, yi) , where the feature vector xi takes values on a set X⊆Rd and yi∈ {−1,+1} is the class membership of object i . There are several desirable managerial properties in Supervised Classication methods. Incorporating domain knowledge at the time of building the classier is a very appealing property (Cecchini et al. 2010). One may also like to keep the costs of learning the classier low, where these costs arise from retrieving the features (Carrizosa et al. 2008, Turney 1995), obtaining feature information from the classier (Saar-Tsechansky et al. 2009), or refreshing the classier to include new data (Fang et al. 2013). Another desirable property is the comprehensibility/interpretability of the classier. Since conciseness of the classier is closely related with its interpretability, much eort has been devoted to increasing its sparsity, i.e., to reducing the number of active features in the classier (Guyon et al. 2002), discretizing the features to detect active ranges of the features (Liu et al. 2002, Romero Morales and Wang 2009) or relevant thresholds for the features (Carrizosa et al. 2010). When trading o between accuracy and interpretability, another popular approach has been to extract easytounderstand structures from powerful yet blackbox type classiers, such as ifthen rules, decision trees and decision tables (Baesens et al. 2003, Bertsimas et al. 2011, Martens et al. 2007, Martens and Provost 2013, Orsenigo and Vercellis 2003, 2004). Yet another way of achieving interpretability is by building discrete linear classiers (Chevaleyre et al. 2013, Golea and Marchand 1993). Classier interpretability is a major challenge in datasets that contain a huge number of features, where most of these are irrelevant. To address this issue, models have been proposed aimed at increasing the sparsity of the classier, as is done with the Lasso, see Li et al. (2006) and Roth (2004). In Supervised Classication, linear classiers are based on score functions. For instance, the CHADS 2 score (Gage et al. 2001, Letham et al. 2012) is widely used in medicine to predict the risk of stroke in patients with atrial brillation based on ve dierent symptoms of the patient, whereas the extended CHA 2 DS 2 VAS c score (Lip et al. 2010) includes three additional risk factors. A score is associated with each feature, and objects are assigned to classes based on the linear combination of the scores and the values of the features. The role each feature plays in the classier is related to the magnitude of the corresponding score, while the sign gives information on how the feature points towards a given class. A state-of-the-art method in Supervised Classication using a score function is the Support Vector Machines (SVM), Cristianini and Shawe-Taylor (2000), Vapnik (1995, 1998). The SVM aims at separating both classes by means of a hyperplane, ω>x+b= 0 , found by solving the following Quadratic Programming problem with linear constraints: min ω, b, ξ 1 2 d X j=1 ω2 j+C n n X i=1 ξi 2 s.t. (SVM) yi(ω>xi+b)≥1−ξi∀i= 1, . . . , n ω∈Rd b∈R ξi≥0∀i= 1, . . . , n, where n is the size of the sample used to build the classier, C is a nonnegative tradeo parameter, (ξi) is the vector of deviation variables, the input feature vector xi takes values on Rd and Pn i=1 ξi is the so-called hinge loss function. See Carrizosa and Romero Morales (2013) for a recent review on Mathematical Optimization and the SVM, and Bertsimas et al. (2008), Brooks (2011), Cecchini et al. (2010), Chaovalitwongse et al. (2008), Guyon et al. (2002), Martens et al. (2007), Romero Morales and Wang (2010) for successful applications of the SVM. The classier obtained by solving the SVM, like any linear classier, provides valuable information on the role of each feature in the classier. Indeed, the set of features can be partitioned into three clusters, namely those with positive ωj , those with negative ωj , and the ones with ωj equal to zero. We can say that features in the rst group have a positive contribution in the classier, and thus such features point towards class +1 , the positive class; similarly, features in the second group have a negative contribution, and thus such features point towards class −1 , the negative class; and those features with ωj= 0 have no contribution in the classier and are therefore irrelevant. However, the construction of the SVM classier is aimed at margin maximization (a surrogate of classication accuracy), and interpretability issues are fully disregarded in the formulation. Inspired by discrete psychometric scales, which measure the extent to which a factor is in agreement with a statement, (Keeney and Gregory 2005), and by linear classiers in which the weights are allowed to take values on a discrete set, (Chevaleyre et al. 2013, Golea and Marchand 1993), we propose the Discrete Level Support Vector Machines (DILSVM) where the feature scores can only take on a discrete number of levels, dened by the so-called feature rating levels. The DILSVM classier benets from interpretability, as it can be seen as a collection of Likert scales, one for each feature, where we rate the level of agreement with the positive class. We formulate the DILSVM as a Mixed Integer Linear Programming (MILP) problem. The parameters of our model, namely, the tradeo parameter C and the rating levels, may heavily inuence the performance, i.e., the accuracy and the sparsity, of the DILSVM and, therefore, have to be carefully chosen. Thus, building the DILSVM classier involves solving a series of MILP problems, which, if solved to optimality, may make the overall computational cost high for large datasets. For this reason we propose three strategies to alleviate the computational burden, with dierent tradeos between performance and reduction in computational cost. Such strategies use the guidance of related but simpler optimization models, and reduce the computational cost associated with each parameter vector and/or the number of parameter vectors to be inspected. In our computational experience, we compare the DILSVM against the SVM classier using ten real-life datasets. We show that the 3-point and 5-point DILSVM classiers, built using the MILP approach, have comparable accuracy to the SVM, with a substan- 3 tial gain in sparsity. Moreover, by the very nature of our procedure (only a few levels, to be interpreted as intensities, are allowed), interpretability is denitely improved allowing us to visualize the classication process via Likert scales. The tests illustrating the performance of the reduction strategies reveal a clear competitiveness in terms of sparsity, while the accuracy depends on the magnitude of the reduction, being close to the SVM accuracies. In our computational experience, we also compare the DILSVM against the 3-point DILSVM classier with xed parameters using ten real-life datasets. The 3-point DILSVM with xed parameters is inspired by the model in (Chevaleyre et al. 2013). The results illustrate the relevance of tuning parameters to ensure accuracy and sparsity are not compromised. Likert scale representations allow non-experts to easily understand the classier, and there are fewer relevant features because of the improvement on sparsity. This contributes to the literature on SVM, but more generally, on Data Mining, because it signicantly improves interpretability of learning methods and their visualization, without comprising accuracy. These advantages are obtained by extending existing SVM models, adding parameters right in the place they are needed to improve sparsity and thus interpretability. The remainder of this paper is organized as follows. In Section 2 we introduce the DILSVM classier. In Section 3 we discuss procedures for building the DILSVM classier. In Section 4 we report our computational results using real-life datasets. We end the paper in Section 5 with some conclusions and directions for future research. 2 The DILSVM classier The Discrete Level Support Vector Machines (DILSVM) is a variant of the SVM classier where for each feature j , the score ωj can only take on a discrete number of values. Let A ⊂ R be a nite set that includes the value 0 , which models the marginal impact of the feature on the classier. We can formulate the DILSVM as the following Discrete Quadratic Programming problem: min ω, b, ξ 1 2 d X j=1 ω2 j+C n n X i=1 ξi (1) s.t. yi(ω>xi+b)≥1−ξi∀i= 1, . . . , n (2) ωj∈ A ∀j= 1, . . . , d (3) b∈R (4) ξi≥0∀i= 1, . . . , n. (5) See Burer and Letchford (2012) for a recent review of algorithmic tools for Mixed Integer Nonlinear Programming. For adequate choices of A , this model gains in interpretability and visualization. For instance, let us consider A={−a, 0, a}, a > 0 . In the DILSVM classier, some of the ωj will be equal to a or −a , while the rest will be equal to zero. Features for which 4 ωj=a will have a positive impact on the classier and therefore will point towards the positive class, those for which ωj=−a will point towards the negative class, while the rest have no impact. We can view this in an alternative way: for a given rating level a , the DILSVM detects those features which strongly agree with the positive class, those which strongly disagree (and therefore strongly agree with the negative class), and those which are irrelevant to the classier. This DILSVM classier can be represented as a collection of 3-point Likert scales, one for each feature, measuring the extent to which the feature is in agreement with the positive class. When looking for more granularity of the scale, we can increase the size of A . For A={−a1,−a2,0, a2, a1}, a1> a2>0 , the DILSVM classier can be seen as a collection of 5-point Likert scales where features j with ωj=a1 are seen to strongly agree with the positive class, those with ωj=a2 agree (but not so strongly), while ωj=−a1(−a2) strongly disagree ( disagree ). As an illustration, let us consider the well-known German credit dataset, german , which is one of the datasets used in our computational tests in Section 4, with 63 features in total. This is a credit scoring dataset, with good customers dening the positive class, and has been used in the context of Supervised Classication and interpretability, such as in Baesens et al. (2003) where rule extraction techniques are studied. Table 5 displays the DILSVM classier with A={−1,0,1} and C/n = 106 as a collection of 3-point Likert scales. Let us focus on three of the features, namely `having no debtor', `having a co-applicant' and `having a guarantor'. The only relevant feature is `having a guarantor', strongly contributing to being a good customer, while for the other two features the score is equal to zero. This is a pattern that can be extended to the overall classier, where more than half of the features are irrelevant (41 out 63). The remaining features are roughly equally split between the left and right side of the scale. Thus, in addition to the gain in interpretability, this DILSVM classier gains in sparsity too. The 5-point Likert scale representation of the DILSVM classier with A={−1,−1/2,0,1/2,1} and C/n = 106 is given in Table 6. The feature `having a guarantor' still strongly contributes to being a good customer, but `having a co-applicant' now contributes negatively (but not strongly), while `having no debtor' is still irrelevant. Similarly to the 3-point Likert scale classier, the split between the left and right side of the scale is balanced, but the number of irrelevant features is about a third (27 out of 63). Apart from the gain in interpretability and sparsity, once the DILSVM classier has been obtained, its evaluation (i.e., classifying new objects) is as inexpensive as for the SVM. However, these advantages come with an increased computational burden, related to the choice of the set A , to build the classier. We analyze this issue in the next section. 3 Constructing the DILSVM classier Inspired by Likert scales, we assume that the set A is symmetric and dened as A= {−a1,...,−aK,0, aK, . . . , a1} , where a1> . . . > aK>0 are the so-called rating levels telling us about the extent to which each feature is in agreement with the positive class. We denote this model by DILSVM (K) . Our model involves K+1 parameters, namely the K rating levels as well as the tradeo parameter C . In the following, we formulate the DILSVM (K) , when the K+1 parameters 5 are xed, as an MILP problem. As we will illustrate in Section 4, tuning eciently the parameters is a necessary and challenging problem, Carrizosa et al. (2014). In order to alleviate this computational burden, a collection of strategies is proposed. 3.1 An MILP formulation In this section we formulate (1)(5) with A={−a1,...,−aK,0, aK, . . . , a1} as an MILP problem. For each feature j and each rating level ak , let αjk be equal to either −1,1 or 0 , indicating whether ωj is equal to −ak , ak or none of these two. For each feature j , at most one αjk variable can be dierent from zero. We can now rewrite ωj= K X k=1 akαjk d X j=1 ω2 j= d X j=1 K X k=1 a2 kα2 jk = d X j=1 K X k=1 a2 k|αjk|, where the latter follows from the fact that αjkαjk0= 0 for k6=k0 . It is straightforward to see that by making these substitutions in (1)(5) and adding the constraints relating to αjk , the DILSVM (K) can be formulated as: min α,b,ξ 1 2 d X j=1 K X k=1 a2 k|αjk|+C n n X i=1 ξi s.t. yi d X j=1 K X k=1 akαjkxij +b!≥1−ξi∀i= 1, . . . , n K X k=1 |αjk| ≤ 1∀j= 1, . . . , d αjk ∈ {−1,0,1} ∀j= 1, . . . , d, ∀k= 1, . . . , K b∈R ξi≥0∀i= 1, . . . , n. Using the usual trick to transform an absolute value into linear constraints, i.e., αjk = α+ jk −α− jk , and |αjk|=α+ jk +α− jk , with α+ jk, α− jk ∈ {0,1} , we can reformulate the DILSVM (K) as an MILP problem: min α+,α−,b,ξ 1 2 d X j=1 K X k=1 a2 k(α+ jk +α− jk) + C n n X i=1 ξi (6) 6 s.t. (DILSVM (K) ) yi d X j=1 K X k=1 ak(α+ jk −α− jk)xij +b!≥1−ξi∀i= 1, . . . , n (7) K X k=1 (α+ jk +α− jk)≤1∀j= 1, . . . , d (8) α+ jk, α− jk ∈ {0,1} ∀j= 1, . . . , d, ∀k= 1, . . . , K (9) b∈R (10) ξi≥0∀i= 1, . . . , n. (11) This MILP formulation has n+d constraints, 2dK binary decision variables, n nonnegative and 1 free, while the SVM formulation has a quadratic objective function but all the decision variables are continuous. In terms of the choice of the number of rating levels, the DILSVM (K) may lead to a higher classication accuracy than the DILSVM (K0) , with K > K0 , but it is computationally more expensive as the number of zeroone decision variables increases and the gains in interpretability and sparsity are less dramatic. Similar observations can be made when comparing the SVM and the DILSVM (K) , since at the end of the spectrum is the SVM, which can be seen as DILSVM (∞) . In the tradeo between accuracy and interpretability, we recommend the K= 1 and K= 2 versions of the model, namely the DILSVM (1) and the DILSVM (2) . 3.2 Reduction Strategies We have formulated the DILSVM (K) as an MILP problem. Solving this MILP formulation to optimality is an NP -Hard task even if we only consider one single rating level, namely K= 1 and a1= 1 , and C=∞ , as shown in Chevaleyre et al. (2013). In addition, the performance of the DILSVM (K) classier may be strongly inuenced by the choice of the tradeo parameter C as well as the K rating levels. Thus, building the DILSVM classier involves solving a series of MILPs, which, if solved to optimality, may make the overall computational cost high for large datasets. In this section we present three dierent strategies to alleviate the computational burden of building the DILSVM (K) classier. The proposed strategies use the guidance of related but simpler optimization models, and reduce the computational cost associated with each parameter vector and/or the number of parameter vectors to be inspected. The rst strategy is based on rounding the SVM classier using each vector of rating levels. The second strategy proposes, for each parameter vector, the randomized rounding, Raghavan and Tompson (1987), of the Linear Programming (LP) relaxation of the DILSVM (K) . The third strategy aims at speeding up the process for the DILSVM (K) based on information readily available for the DILSVM (K0) , K0< K . Clearly, these strategies are of diverse nature and, as the computational experience will illustrate, oer dierent tradeos between performance and reduction in computational cost. The rst and second strategies will be presented for general K , while, and for the sake of clarity, the third strategy will be described for K= 2 , though the process gracefully 7 Step 1. For each C , (i) Solve the SV M and obtain the (partial) optimal solution (ω, b) . (ii) For each (a1, . . . , aK) , For j= 1, . . . , d For k= 1, . . . , K , set β+ jk =β− jk = 0 For k= 1, . . . , K If ak≤ωj< ak−1 then β+ jk = 1 ElseIf −ak−1< ωj≤ −ak then β− jk = 1 end end Return the classifier K X k=1 ak(β+ k−β− k)>x+b . Step 2. Choose the optimal parameter vector using K X k=1 ak(β+ k−β− k)>x+b . Figure 1: Pseudocode for Strategy 1, the SVM rounding strategy. extends to arbitrary K . Apart from a grid of parameter vectors, we assume that we are given a selection criterion, Carrizosa and Romero Morales (2013), to choose the optimal classier among those generated for each vector of the grid. This is usually the accuracy on an independent sample dierent from the one used to build the classier, see Section 4.1 for more details. The rst strategy, the SVM rounding ( RSVM ), is based on rounding the feature scores of the SVM classier using the rating levels. For each value of C , the SVM classier is obtained, and the rounding procedure is performed using each vector of rating levels. The pseudocode of this reduction strategy is given in Figure 1, where a0=∞ . While this strategy examines all the parameter vectors in the grid, it is appealing since it is cheaper to train an SVM than a DILSVM. In addition, for a given value of C , once the SVM classier has been obtained, the rounding procedure takes O(dK) time for each vector of rating levels. The second strategy is based on the randomized rounding of the LP relaxation of the DILSVM (K) . We call this the randomized rounding ( RR ) strategy. For each parameter vector (C, a1, . . . , aK) , the RR strategy solves the LP relaxation of the DILSVM (K) , where constraints (9) are relaxed to α+ jk, α− jk ∈[0,1] . Let (α+, α−) be the (partial) optimal solution obtained. Without loss of optimality, α+ jk ·α− jk = 0 . Thus, for a given feature j , α+ jk ( α− jk ) can be seen as the desirability of setting the score of feature j to value ak ( −ak ). Noting that the assignment constraints (8) are satised, a randomized rounding procedure can be applied to derive the DILSVM classier. In order to ensure feasibility with respect 8 Step 1. For each (C, a1, . . . , aK) , (i) Solve the LP relaxation of DILSVM (K) and obtain the (partial) optimal solution (α+, α−) . (ii) For j= 1, . . . , d For k= 1, . . . , K , set β+ jk =β− jk = 0 Set K={1, . . . , K} while (K 6=∅) Let ¯ k such that max{α+ j¯ k, α− j¯ k} ≥ max{α+ jk, α− jk},∀k∈ K Set β+ j¯ k=rand(α+ j¯ k) β− j¯ k=rand(α− j¯ k) If β+ j¯ k=β− j¯ k= 0 , set K=K \ {¯ k} Else K=∅ end end (iii) Return the classifier K X k=1 ak(β+ k−β− k)>x+b . Step 2. Choose the optimal parameter vector using K X k=1 ak(β+ k−β− k)>x+b . Figure 2: Pseudocode for Strategy 2, the randomized rounding strategy. to the assignment constraints, the rounding needs to take place in a predetermined order of the rating levels, such that once a rating level and a sign has been assigned to a feature, we move to the next feature. In the current version of the RR strategy, the rating levels are arranged in decreasing order of max{α+ jk, α− jk} . The pseudocode of this reduction strategy can be found in Figure 2, where rand(p) is a subroutine of random numbers generation, returning the value 1 with probability p and 0 otherwise. In the third strategy, the xing strategy, we use the output of the DILSVM (1) classier to alleviate the burden of building the DILSVM (2) classier. In this case, the reduction is twofold. First, the size of the parameter space is narrowed down. Second, some of the decision variables in the MILP formulation (6)(11) are xed in advanced, and therefore eliminated. The pseudocode for this reduction strategy can be found in Figure 3. Using the grid corresponding to parameters C and a1 , we rst build the DILSVM (1) classier yielding optimal parameters values C(1) and a(1) 1 . We then build the DILSVM (2) classier using the MILP formulation (6)(11) for K= 2 , with C=C(1) , a1=a(1) 1 and the values of a2 in the grid. In addition, we reduce the number of zeroone decision variables in the MILP formulation. In the current version of the xing strategy, feature j will have a 9 the building time of the RSVM and the SVM is roughly equal to 1 for each dataset. For the RR strategy, when comparing with the SVM, the median ratio is equal to 10.32 for K= 1 and 34.41 for K= 2 . Finally, the xing strategy is designed to reduce the building time when K= 2 using the DILSVM (1) classier, and the median ratios are very similar to the ones reported for the MILP approach with K= 1 , namely 211.60 against the SVM. In conclusion, we have presented three strategies of very diverse nature that are able to reduce the building time of the DILSVM classier. When compared to the SVM, the RR and the xing strategies are competitive in terms of mean accuracy, but less so is the RSVM , while the dominance of the three strategies in terms of sparsity is overwhelming. 5 Conclusions In this paper we propose the DILSVM (K) classier, an SVM-type classier in which there are K possible levels of agreement of each feature with the positive class. We recommend small values of K , such as K= 1 and K= 2 . In this case, our classier enjoys two properties. First, it can be visualized as a collection of Likert scales, and therefore, since K is small, the DILSVM (K) classier gains in interpretability. Second, once the classier has been built, the evaluation of the DILSVM (K) (i.e., classifying new objects) is at least as inexpensive as for the SVM: classifying new objects amounts to evaluating a linear function. In addition, as shown by our computational experience, many coecients are set to zero in both the DILSVM (1) and the DILSVM (2) , while the SVM is fully dense. The gain in visualization and sparsity achieved by the DILSVM is made without paying any price in accuracy. As our computational experience shows, the DILSVM is competitive against the SVM in terms of accuracy. Our classier is much harder to obtain than the SVM, since an MILP problem is to be solved for each parameter vector, and we have illustrated that parameter tuning is crucial if we do not want to compromise accuracy. In terms of the number of parameters, there are now one ( K= 1 ) or two ( K= 2 ) more parameters than in the standard SVM to tune. In order to alleviate the computational burden, we propose three reduction strategies. Our computational tests show that we are able to preserve an accuracy comparable to the SVM and signicantly better sparsities. This means that, at the expense of an increase in o-line computational cost, the DILSVM is able to extract easy-to-interpret information from datasets without sacricing classication accuracy. We conclude with three promising extensions of our approach. First, knowledge domain can also be incorporated into the model. Given a family of features, constraints of the type at least one feature of this family should be selected or no more than one feature of this family should be chosen simply lead to new linear constraints in the MILP formulation. Second, accuracy and interpretability are usually contradicting objectives. In this paper we x the number of rating levels, and aim at optimizing accuracy. It is natural to consider the problem of simultaneous optimization of both accuracy and interpretability, see for instance Hooker and Williams (2012), Müssel et al. (2012). This biobjective model deserves further analysis and testing. Third, our approach can also be extended to other linear classiers, such as the classical Linear Discriminant Analysis (Fisher 1936) and the Logistic Regression (Hastie et al. 2001), where building the new 16 classier yields Nonlinear Integer Programming problems (Burer and Letchford 2012). Solving these nonlinear problems eciently remains an important future challenge. Acknowledgments This work has been partially supported by projects MTM2012-36163, Ministerio de Economía y Competitividad, Spain, and FQM-329 of Junta de Andalucía, Spain, both with EU ERD Funds. References Apte, C. 2003. The big (data) dig. OR/MS Today 30 (1) 2429. Archak, N., A. Ghose, P.G. Ipeirotis. 2011. Deriving the pricing power of product features by mining consumer reviews. Management Science 57 (8) 14851509. Baesens, B., R. Setiono, C. Mues, J. Vanthienen. 2003. Using neural network rule extraction and decision tables for credit-risk evaluation. Management Science 49 (3) 312329. Bertsimas, D., M.V. Bjarnadóttir, M.A. Kane, J.Ch. Kryder, R. Pandey, S. Vempala, G. Wang. 2008. Algorithmic prediction of health-care costs. Operations Research 56 (6) 13821392. Bertsimas, D., A. Chang, C. Rudin. 2011. ORC: Ordered rules for classication. A discrete optimization approach to associative classication. Tech. Rep. OR 386-11, Massachusetts Institute of Technology. Blake, C.L., C.J. Merz. 1998. UCI Repository of Machine Learning Databases. http://www.ics.uci.edu/ ∼ mlearn/MLRepository.html. University of California, Irvine, Department of Information and Computer Sciences. Brooks, J.P. 2011. Support vector machines with the ramp loss and the hard margin loss. Operations Research 59 (2) 467479. Burer, S., A.N. Letchford. 2012. Non-convex mixed-integer nonlinear programming: A survey. Surveys in Operations Research and Management Science 17 (2) 97106. Carrizosa, E., B. Martín-Barragán, D. Romero Morales. 2008. Multi-group support vector machines with measurement costs: A biobjective approach. Discrete Applied Mathematics 156 950966. Carrizosa, E., B. Martín-Barragán, D. Romero Morales. 2010. Binarized support vector machines. INFORMS Journal on Computing 22 (1) 154167. Carrizosa, E., B. Martín-Barragán, D. Romero Morales. 2014. A nested heuristic for parameter tuning in support vector machines. Computers and Operations Research 43 (0) 328334. Carrizosa, E., D. Romero Morales. 2013. Supervised classication and mathematical optimization. Computers and Operations Research 40 150165. Cecchini, M., H. Aytug, G.J. Koehler, P. Pathak. 2010. Detecting management fraud in public companies. Management Science 56 (7) 11461160. Chang, C.C., C.J. Lin. 2011. LIBSVM: a library for support vector machines. ACM Transactions on Intelligent Systems and Technology 2 127. Chaovalitwongse, W. A., Y.-J. Fan, R. C. Sachdeo. 2008. Novel optimization models for abnormal brain activity classication. Operations Research 56 (6) 14501460. 17 Chevaleyre, Y., F. Koriche, J.-D. Zucker. 2013. Rounding methods for discrete linear classi- cation. S. Dasgupta, D. McAllester, eds., Proceedings of the 30th International Conference on Machine Learning (ICML-13) , vol. 28. JMLR Workshop and Conference Proceedings, 651659. CPLEX, ILOG. 2012. www.ilog.com/products/cplex. Cristianini, N., J. Shawe-Taylor. 2000. An Introduction to Support Vector Machines and Other Kernel-based Learning Methods . Cambridge University Press. Cui, G., M.L. Wong, H.-K. Lui. 2006. Machine learning for direct marketing response models: Bayesian networks with evolutionary programming. Management Science 52 (4) 597612. Fang, X., O.R. Liu Sheng, P. Goes. 2013. When is the right time to refresh knowledge discovered from data? Operations Research 61 (1) 3244. Fisher, R.A. 1936. The use of multiple measurements in taxonomy problems. Annals of Eugenics 7 179188. Gage, B. F., A. D. Waterman, W. Shannon, M. Boechler, M.W. Rich, M.J. Radford. 2001. Validation of clinical classication schemes for predicting stroke: Results from the national registry of atrial brillation. Journal of the American Medical Association 285 (22) 2864 2870. Golea, M., M. Marchand. 1993. On learning perceptrons with binary weights. Neural Computation 5 (5) 767782. Guyon, I., J. Weston, S. Barnhill, V. Vapnik. 2002. Gene selection for cancer classication using support vector machines. Machine Learning 46 389422. Hand, H., H. Mannila, P. Smyth. 2001. Principles of Data Mining . MIT Press. Hastie, T., R. Tibshirani, J. Friedman. 2001. The Elements of Statistical Learning . Springer, New York. Hooker, J.N., H.P. Williams. 2012. Combining equity and utilitarianism in a mathematical programming model. Management Science 58 (9) 16821693. Keeney, R.L., R.S. Gregory. 2005. Selecting attributes to measure the achievement of objectives. Operations Research 53 (1) 111. Letham, B., C. Rudin, T.H. McCormick, D. Madigan. 2012. Building interpretable classiers with rules using bayesian analysis. Tech. Rep. tr609, University of Washington. Li, F., Y. Yang, E. Xing. 2006. From Lasso regression to feature vector machine. Y. Weiss, B. Schölkopf, J. Platt, eds., Advances in Neural Information Processing Systems , vol. 18. MIT Press, Cambridge, MA, 779786. Lip, G.Y.H., R. Nieuwlaat, R. Pisters, D.A. Lane, H.J.G.M. Crijns. 2010. Rening clinical risk stratication for predicting stroke and thromboembolism in atrial brillation using a novel risk factor-based approach: The Euro heart survey on atrial brillation. CHEST Journal 137 (2) 263272. Liu, H., F. Hussain, C. Tan, M. Dash. 2002. Discretization: An enabling technique. Data Mining and Knowledge Discovery 6 (4) 393423. Martens, D., B. Baesens, T.V. Gestel, J. Vanthienen. 2007. Comprehensible credit scoring models using rule extraction from support vector machines. European Journal of Operational Research 183 (3) 14661476. Martens, D., F. Provost. 2013. Explaining data-driven document classications. Technical report. Forthcoming in MIS Quarterly . 18 Müssel, C., L. Lausser, M. Maucher, H.A. Kestler. 2012. Multi-objective parameter selection for classiers. Journal of Statistical Software 46 (5). Orsenigo, C., C. Vercellis. 2003. Multivariate classication trees based on minimum features discrete support vector machines. IMA Journal of Management Mathematics 14 (3) 221 234. Orsenigo, C., C. Vercellis. 2004. Discrete support vector decision trees via tabu search. Computational Statistics and Data Analysis 47 (2) 311322. Raghavan, P., C. D. Tompson. 1987. Randomized rounding: A technique for provably good algorithms and algorithmic proofs. Combinatorica 7 (4) 365374. Romero Morales, D., J. Wang. 2009. A parallel discretization algorithm for cancellation rate forecasting in revenue management. Working Paper, Saïd Business School, University of Oxford, UK. Romero Morales, D., J. Wang. 2010. Forecasting cancellation rates for services booking revenue management using data mining. European Journal of Operational Research 202 (2) 554562. Roth, V. 2004. The generalized lasso. IEEE Transactions on Neural Networks 15 (1) 1628. Saar-Tsechansky, M., P. Melville, F. Provost. 2009. Active feature-value acquisition. Management Science 55 (4) 664684. Turney, P.D. 1995. Cost-sensitive classication: Empirical evaluation of a hybrid genetic decision tree induction algorithm. Journal of Articial Intelligence Research 2 369409. Vapnik, V. 1995. The Nature of Statistical Learning Theory . Springer-Verlag. Vapnik, V. 1998. Statistical Learning Theory . Wiley. Vlachos, P., M. Meyer. 1989. StatLib. http://lib.stat.cmu.edu. Wu, X., V. Kumar, J. Ross Quinlan, J. Ghosh, Q. Yang, H. Motoda, G.J. McLachlan, A. Ng, B. Liu, P.S. Yu, Z.-H. Zhou, M. Steinbach, D.J. Hand, D. Steinberg. 2007. Top 10 algorithms in data mining. Knowledge and Information Systems 14 137. 19 Table 2: Validation performance in % with C/n ∈ {10−6,...,106} : the SVM. Name SV M Accuracy Sparsity mean std med mean std med adult 84.89 0.28 84.98 0.00 0.00 0.00 mushroom 99.98 0.04 100.00 0.00 0.00 0.00 german 72.96 2.37 72.60 4.12 1.05 3.97 ijcnn1 91.37 0.36 91.33 0.00 0.00 0.00 careval 95.05 0.86 94.91 0.00 0.00 0.00 gamma 79.32 0.57 79.47 0.00 0.00 0.00 abalone 79.52 1.14 79.73 0.00 0.00 0.00 shuttle 98.17 0.08 98.15 0.00 0.00 0.00 cod-rna 93.86 0.12 93.89 0.00 0.00 0.00 calhous 83.59 0.29 83.59 0.00 0.00 0.00 Table 3: Validation performance in % with C/n ∈ {10−6,...,106} : the MILP approach and the reduction strategies for the DILSVM (1) . Name MILP MILP RSV M RR C=∞, a1= 1 a1∈ {20,...,210}a1∈ {20,...,210}a1∈ {20,...,210} Accuracy Sparsity Accuracy Sparsity Accuracy Sparsity Accuracy Sparsity mean std med mean std med mean std med mean std med mean std med mean std med mean std med mean std med adult 82.93 0.48 82.91 55.93 9.65 55.69 90.43 0.64 90.69 79.27 8.80 74.80 75.81 0.28 75.90 100.00 0.00 100.00 82.33 0.36 82.19 97.36 0.93 97.56 mushroom 99.98 0.04 100.00 49.08 3.32 50.42 100.00 0.00 100.00 91.60 0.00 91.60 52.01 1.05 51.87 100.00 0.00 100.00 99.47 0.23 99.47 97.56 2.27 98.32 german 72.52 2.14 72.40 51.43 7.31 50.00 75.32 5.70 73.20 70.95 12.17 69.84 69.24 3.00 69.20 98.89 2.84 100.00 69.28 2.72 68.80 93.02 6.49 94.05 ijcnn1 90.18 0.36 90.03 81.82 22.27 100.00 90.17 0.36 90.03 100.00 0.00 100.00 90.18 0.36 90.03 98.18 3.64 100.00 90.17 0.37 90.04 96.59 4.22 100.00 careval 86.92 2.47 86.81 30.00 15.21 33.30 96.21 1.98 96.84 59.52 5.73 61.90 82.03 5.32 84.48 62.86 15.18 61.90 87.61 1.62 87.78 81.19 7.18 80.95 gamma 70.37 0.60 70.47 31.00 5.39 30.00 79.09 0.64 79.22 50.00 10.95 45.00 77.95 0.71 77.79 80.00 0.00 80.00 78.31 0.49 78.26 73.00 4.00 75.00 abalone 74.28 0.81 73.95 15.00 5.00 15.00 78.28 0.99 78.17 70.00 8.94 70.00 77.19 1.85 77.85 72.00 6.00 70.00 76.91 1.32 77.30 75.50 5.22 75.00 shuttle 80.83 1.26 80.63 15.55 7.37 16.66 97.32 0.11 97.33 63.33 5.09 66.67 84.30 5.09 82.76 75.56 9.69 77.78 93.75 1.77 92.81 68.33 7.88 66.67 cod-rna 66.56 0.38 66.58 87.50 0.00 87.50 78.17 0.28 78.20 87.50 0.00 87.50 71.05 3.09 71.35 88.75 3.75 87.50 76.13 1.51 75.70 93.75 0.00 93.75 calhous 63.57 2.47 63.48 0.00 0.00 0.00 81.98 0.50 81.78 31.25 8.39 37.50 78.60 2.00 79.06 50.00 0.00 50.00 78.17 1.17 78.16 65.00 5.73 68.75 Table 4: Validation performance in % with C/n ∈ {10−6,...,106} : the MILP approach and the reduction strategies for the DILSVM (2) . Name MILP RSV M RR xing a1∈ {20,...,210}, a2∈ {a1/2, a1/22}a1∈ {20,...,210}, a2∈ {a1/2, a1/22}a1∈ {20,...,210}, a2∈ {a1/2, a1/22}C(1), a(1) 1, a2∈ {a(1) 1/2, a(1) 1/22} Accuracy Sparsity Accuracy Sparsity Accuracy Sparsity Accuracy Sparsity mean std med mean std med mean std med mean std med mean std med mean std med mean std med mean std med adult 90.56 0.46 90.75 77.40 11.64 78.45 77.88 2.41 77.22 90.33 7.01 90.25 89.04 1.99 89.14 93.33 8.39 95.93 89.08 1.63 88.66 67.07 19.10 73.98 mushroom 100.00 0.00 100.00 91.60 0.00 91.60 99.41 0.14 99.42 95.80 0.00 95.80 100.00 0.00 100.00 100.00 0.00 100.00 100.00 0.00 100.00 91.60 0.00 91.60 german 75.96 5.32 74.00 55.87 22.06 55.56 70.92 3.38 71.00 57.78 20.21 47.62 73.00 4.51 72.20 54.76 20.59 46.03 71.60 2.26 71.60 35.56 10.56 36.51 ijcnn1 90.18 0.36 90.03 95.46 13.63 100.00 90.46 0.45 90.51 65.91 7.67 70.46 90.25 0.33 90.14 70.45 4.66 72.73 90.17 0.36 90.03 100.00 0.00 100.00 careval 98.71 0.44 98.77 35.72 2.39 35.72 89.81 3.22 89.97 43.34 6.88 42.86 98.76 0.43 98.90 53.81 30.57 38.10 96.84 0.81 97.25 51.90 12.68 61.90 gamma 79.31 0.65 79.11 50.00 16.73 40.00 78.28 0.39 78.18 52.00 12.49 50.00 79.19 0.84 79.34 57.00 14.87 60.00 79.36 0.64 79.49 32.00 7.48 30.00 abalone 79.05 1.07 78.77 55.00 9.22 50.00 78.28 0.76 78.03 57.00 14.87 65.00 77.64 1.36 77.62 65.00 19.62 65.00 78.43 1.05 78.44 61.00 13.75 50.00 shuttle 97.59 0.27 97.51 45.55 13.57 44.44 92.16 3.77 92.16 43.33 20.76 33.33 96.30 0.83 96.29 43.33 27.87 33.33 97.32 0.09 97.34 47.78 15.76 50.00 cod-rna 90.64 0.88 90.57 42.50 11.46 50.00 73.94 5.88 74.03 82.50 8.29 81.25 80.10 4.60 82.46 62.50 12.50 62.50 81.32 2.18 80.25 46.25 11.25 50.00 calhous 83.03 0.24 83.09 17.50 6.12 12.50 80.14 0.84 80.23 25.00 19.36 12.50 80.47 0.64 80.50 17.50 6.12 12.50 82.25 0.44 82.12 20.00 6.12 25.00 20 Table 5: 3-point Likert scale for german dataset with the DILSVM. The following features contribute to being a good customer: Strongly Agree Neutral Strongly Disagree Status of existing checking account . . . < 0 DM × 0≤. . . < 200 DM × ...≥200 DM × No checking account × Credit duration × Credit history no credits taken/all credits paid back duly × all credits at this bank paid back duly × existing credits paid back duly till now × delay in paying o in the past × critical account/other credits existing (not at this bank) × Purpose new car × used car × furniture/equipment × radio/television × domestic appliances × repairs × education × vacation × retraining × business × others × Credit amount × Saving accounts . . . < 100 DM × 100 ≤. . . < 500 × 500 ≤. . . < 1000 × ...≥1000 × unknown/no saving accounts × Duration of present employment unemployed × . . . < 1 year × 1≤. . . < 4 years × 4≤. . . < 7 years × ...≥7 years × Installment rate in % of disposable income × Personal status and sex male (divorced/separated) × female (divorced/separated/married) × male (single) × male (married/widowed) × female (single) × Other debtors/guarantors none × co-applicant × guarantor × Duration of present residence × Property real estate × building society savings agreement/life insurance × car/others × unknown/no property × Age × Other installment plans bank × stores × none × Housing rent × own × for free × Number of existing credits at this bank × Job unemployed/unskilled (non-resident) × unskilled (resident) × skilled employee/ocial × management/self-employed/highly qualied employee ocer × Number of people being liable to provide maintenance for × Telephone None × Yes × Foreign worker Yes × No × 21 Table 6: 5-point Likert scale for german dataset with the DILSVM. The following features contribute to being a good customer: Strongly Agree Agree Neutral Disagree Strongly Disagree Status of existing checking account . . . < 0 DM × 0≤. . . < 200 DM × ...≥200 DM × No checking account × Credit duration × Credit history no credits taken/all credits paid back duly × all credits at this bank paid back duly × existing credits paid back duly till now × delay in paying o in the past × critical account/other credits existing (not at this bank) × Purpose new car × used car × furniture/equipment × radio/television × domestic appliances × repairs × education × vacation × retraining × business × others × Credit amount × Saving accounts . . . < 100 DM × 100 ≤. . . < 500 × 500 ≤. . . < 1000 × ...≥1000 × unknown/no saving accounts × Duration of present employment unemployed × . . . < 1 year × 1≤. . . < 4 years × 4≤. . . < 7 years × ...≥7 years × Installment rate in % of disposable income × Personal status and sex male (divorced/separated) × female (divorced/separated/married) × male (single) × male (married/widowed) × female (single) × Other debtors/guarantors none × co-applicant × guarantor × Duration of present residence × Property real estate × building society savings agreement/life insurance × car/others × unknown/no property × Age × Other installment plans bank × stores × none × Housing rent × own × for free × Number of existing credits at this bank × Job unemployed/unskilled (non-resident) × unskilled (resident) × skilled employee/ocial × management/self-employed/highly qualied employee ocer × Number of people being liable to provide maintenance for × Telephone None × Yes × Foreign worker Yes × No × 22