Deriving Weights in Multiple-Criteria Decision Making with Support Vector Machines

Sociedad de Estad´ıstica e Investigaci´on Operativa Top (2006) Vol. 14, No. 2, pp. 399–424 Deriving Weights in Multiple-Criteria Decision Making with Support Vector Machines Emilio Carrizosa Facultad de Matem´aticas, Universidad de Sevilla Avda Reina Mercedes s/n, 41012 Sevilla (Spain) E-mail: ec[email protected] Abstract A key problem in Multiple-Criteria Decision Making is how to measure the importance of the different criteria when just a partial preference relation among actions is given. In this note we address the problem of constructing a linear score function (and thus how to associate weights of importance to the criteria) when a binary relation comparing actions and partial information (relative importance) on the criteria are given. It is shown that these tasks can be done via Support Vector Machines, an increasingly popular Data Mining technique, which reduces the search of the weights to the resolution of (a series of) nonlinear convex optimization problems with linear constraints. An interactive method is then presented and illustrated by solving a multiple-objective 0-1 knapsack problem. Extensions to the case in which data are imprecise (given by intervals) or intransitivities in strict preferences exist are outlined. Key Words: Linear score functions, support vector machines, multiple-criteria decision making with partial information, data mining. AMS subject classification: 90B50, 90C30, 62H30. 1 Introduction Suppose we are given •an integer N, •a finite directed graph (A, P),whose set of edges Pis non-empty and contains no loops, Partially supported by grants MTM2005-09362-103-01 of MEC, Spain, and FQM-329 of Junta de Andaluc´ıa, Spain. Part of this work has been written while the author visited the Department of Statistics and Decision Support Systems of the Universit¨at Wien. The author thanks the referees for their constructive suggestions, which have helped to improve the quality of the paper. Manuscript received: April 2004. Final version accepted: November 2006. 400 E. Carrizosa •a function Ψ : A −→ RN, •a polyhedral cone Ω in RN +,Ω6={0},represented in the form Ω = nω∈RN:q⊤ jω≥0, j ∈Jo, for a finite set {qj:j∈J} ⊂ RN, •a norm γin RN, and consider the optimization problem max ω∈Ω\{0}min (a,a′)∈P ω⊤Ψ(a)−ω⊤Ψ(a′) γ(ω).(1.1) Problem (1.1) has a clear interpretation in Multiple-Criteria Decision Making, as sketched below: Arepresents a finite set of actions, where we have defined •a vector-valued function Ψ : A −→ RN,in such a way that Ψj(a) represents the score of action aaccording to the j-th criterion, j= 1,2,...,N. All scores are assumed to be in a scale ”the higher the better” •a binary irreflexive relation P⊂ A×A.No further assumptions (e.g. transitivity or weak connectedness) are made on P. For instance, P might be the strict preferences obtained with Electre I, Roy (1968), or the strict preferences detected via a sample of pairwise comparisons among actions. By abuse of notation, we will write in what follows indifferently aPa′ or (a, a′)∈P. Our aim is to extend the binary relation Pto a total preorder on Avia a linear function of the scores given by Ψ.In other words, we seek ω∈Ω such that ω⊤Ψ(a)> ω⊤Ψ(a′)∀a, a′∈ A, aPa′.(1.2) Any ωsatisfying (1.2) induces a pair of binary relations (Pω, Iω) on A, aPωa′iff ω⊤Ψ(a)> ω⊤Ψ(a′) aIωa′iff ω⊤Ψ(a) = ω⊤Ψ(a′),(1.3) Inferring weights via SVM 401 of strict preference and indifference. We have that the strict preference Pωis compatible with P, in the sense that the set Pis included in the set Pω, and thus no information contained in Pis lost if Pis replaced by Pω.Moreover, Pωenjoys properties usually considered to be desirable such as transitivity. By construction, each component of ωmeasures the importance of the corresponding criterion in Pω, and hence we can also see ωjas a measure of importance of Ψjin P. We illustrate the model in the following Example. Example 1.1. Consider the problem with 6 actions, (A={a1,...,a6}), N= 4 criteria, C1,...,C4,with rewards scored (in ordinal or cardinal scales) in Table 1. C1C2C3C4 (max) (max) (max) (max) a1High 4 2 8 a2Low 2 2 7 a3High 3 4 3 a4Low 2 5 2 a5Average 8 1 1 a6Low 4 4 4 Table 1:Decision table for Example 1.1 Consider also the irreflexive binary relation Pgiven on Arepresented in Figure 1. The mechanism used to construct such Pis simple: aiPajiff criterion C1in aiis strictly better than C1in aj,and, at the same time, the average of the three remaining scores in aiis strictly greater than the average in aj. In order to accommodate these data to the model considered, the cri- 402 E. Carrizosa a1 a2 a3 a4 a5 a6 (High,4,2,8) (Low,2,2,7) (High,3,4,3) (Low,2,5,2)(Average,8,1,1) (Low,4,4,4) Figure 1:The graph (A, P)in Example 1.1 teria must be measured in a cardinal scale. To do that, we define Ψ11(a) = 1,if ain C1takes the value ”High” 0,else Ψ12(a) = 1,if ain C1takes the value “Average” 0,else Ψ13(a) = 1,if ain C1takes the value “Low” 0,else Ψi(a) = score of aaccording to Ciin Table 1, i = 2,...,4, and we obtain Table 2. Under these assumptions, we seek a vector of weights ω, to be associated with the columns of Table 2, in such a way that ordinal values are replaced by ratio-scaled values, and the total ranking obtained by averaging the actions ωis compatible with Pretaining all the information on the criteria: since the criteria are of the form “the higher the better,” the weights should be non-negative; moreover, the weight associated with Ψ11 should not be smaller than the weight associated with Ψ12,which should not be smaller than the weight associated with Ψ13. Inferring weights via SVM 403 Ψ11 Ψ12 Ψ13 Ψ2Ψ3Ψ4 a11 0 0 4 2 8 a20 0 1 2 2 7 a31 0 0 3 4 3 a40 0 1 2 5 2 a50 1 0 8 1 1 a60 0 1 4 4 4 Table 2:Decision Table for Example 1.1. Cardinal scales Let ΩPdenote the set of solutions to (1.2), ΩP=nω∈Ω : ω⊤Ψ(a)> ω⊤Ψ(a′)∀(a, a′)∈Po. In practice, of course, ΩPcan be empty. This is the case, for instance, when the graph (A, P) contains cycles. In such cases, no Pωcompatible with Pexists. In what follows we assume that ΩP6=∅.How to address the case ΩP=∅will be outlined in Section 4. In case ω∈ΩPexists, it is highly desirable that such ωmakes maximal separation between actions, i.e., the slack ω⊤Ψ(a)−ω⊤Ψ(a′) should be not only positive but high in all pairs a, a′∈ A, aPa′.To do that, we can take as criterion the maximization of the lowest slack, min (a,a′)∈Pnω⊤Ψ(a)−ω⊤Ψ(a′)o.(1.4) Maximizing over Ω (or over ΩP) the lowest slack is, as soon as ΩP6=∅,an optimization problem with unbounded solution: given ω∈ΩP, ϑω ∈ΩP for any ϑ > 0,and makes the smallest slack grow without limit by growing ϑ. Hence, we have to introduce a normalization condition which enables us to identify ωand ϑω, ϑ > 0.This can be done e.g., by setting γ(ω) = 1 for a given norm, or, equivalently, as done in (1.1). The inclusion of linear constraints on ωenables us to consider problems with partial information on the importance to be given to the different scalar functions Ψj,e.g., Carrizosa et al. (1995), and Carrizosa and Conde (2002). For instance, since, by assumption, Ψjscores a criterion of type 404 E. Carrizosa ”the higher, the better”, the ωsought should satisfy, together with (1.2), a sign constraint ωj≥0.(1.5) Moreover, we may have information about the relative importance of criteria. For instance, from two criteria Ψi,Ψjof type ”the higher, the better”, we may impose that the weight associated with criterion ishould not exceed Kij times the weight associated with the j-th criterion. This way we generate the homogeneous linear constraint ωi≤Kijωj,(1.6) e.g., Carrizosa and Conde (2002), and Carrizosa et al. (1995). More complex homogeneous linear constraints may appear, for instance, in decision problems under risk, with Nscenarios, each ωjrepresenting the probability of the j-th scenario. Under such assumptions, since the weights represent probabilities, their sum must equal 1.This is modelled by taking as γin (1.1) the ℓ1norm. Moreover, if we have interval information about the probability of the i-th scenario, in the form Li≤ωi≤Ui, we can transform this condition into Li 1−Li≤ωi 1−ωi≤Ui 1−Ui , or into the pair of homogeneous linear constraints Li 1−LiPj6=iωj≤ωi Ui 1−UiPj6=iωj≥ωi.(1.7) On the other hand, if two actions, a, a′are known to be indifferent, one would have (Ψ(a)−Ψ(a′))⊤ω≥0 (Ψ(a′)−Ψ(a))⊤ω≥0(1.8) As seen above, sign constraints and, among others, those of type (1.6), (1.7) and (1.8), can be modelled by imposing that ωbelongs to a polyhedral cone Ω. Inferring weights via SVM 405 Example 1.2. With the data of Example 1.1, since the criteria in Table 1 are all of type ”the higher the better”, all weights must be non-negative. Since we have passed C1to a cardinal scale, see Table 2, we must impose also that ω11 ≥ω12 ≥ω13. This information on the weights yields the polyhedral cone Ω = ω= (ω1, ω2,...,ω6)∈R6 +: (1,−1,0,0,0,0)⊤ω≥0 (0,1,−1,0,0,0)⊤ω≥0} (1.9) Solving numerically (1.1) taking as γthe Euclidean norm, the following weights (measures of importance of the criteria) are obtained after normalization to sum 1: ω= (ω11, ω12, ω13, ω2, ω3, ω4) = (0.333,0.000,0.000,0.333,0.000,0.333). (1.10) Hence, only the highest value of C1,together with C2and C4are relevant, all being equally important. With this information, the function a7−→ ω⊤Ψ(a) is given in Table 3, yielding the total strict order a1Pωa2Pωa5Pωa6Pωa3Pωa4. aiω⊤Ψ(a) a14.334 a23.001 a32.333 a41.333 a53.000 a62.667 Table 3:Values of ω⊤Ψ(·)in Example 1.2 Suppose we also know that C4should not be weighted much stronger (say, 5 times) than C3,modelled with the constraint ω4≤5ω3.(1.11) 406 E. Carrizosa a1 a2 a3 a4 a5 a6 (High,4,2,8) (Low,2,2,7) (High,3,4,3) (Low,2,5,2)(Average,8,1,1) (Low,4,4,4) Figure 2:The graph (A, Pω)in Example 1.1 This constraint must then be added to those given in (1.9). Solving numerically (1.1) taking as γthe Euclidean norm, the following weights (measures of importance of the criteria) are obtained after normalization to sum 1: ω= (ω11, ω12, ω13, ω2, ω3, ω4) = (0.342,0.000,0.000,0.340,0.053,0.265), yielding the total strict order a1Pωa5Pωa2Pωa6Pωa3Pωa4. Hence, the addition of the constraint (1.11) has produced slight changes in the optimal weight vector ω, but has led to a change in the ranking of the alternatives (please compare the position of a3and a5in both rankings. The graph of Pωis depicted in Figure 2. Preferences already present in Pare plotted with a thick arrow, whereas those which did not exist in P and are added by Pωare dotted. In order to gain insight into Problem (1.1), and to extend the methodology to the case in which ΩPis empty, we connect this with (a variant of) Inferring weights via SVM 407 Support Vector Machines. Other approaches to ordinal regression based on Support Vector Machines can be found e.g., in Freund et al. (2001), and Herbrich et al. (2000). The remainder of the paper is organized as follows. In Section 2 we make a quick introduction to Support Vector Machines, and rephrase our problem within this framework. An interactive methodology is outlined in Section 3, where an illustrative example is also given. Possible extensions of this work are given in Section 4. Throughout this paper, conv(X) denotes the convex hull of a set X, and cone(X) denotes the conic hull of X, i.e., cone(X) is the set of points which can be expressed as a linear combination with non-negative coefficients of elements of X, Cramer and Singer (2001). 2 Support Vector Machines Before particularizing to our problem, (see Section 2.2), we first briefly outline the main ideas underlying the Discriminant Analysis method known as Support Vector Machines, SVM. The reader is referred to e.g., Burges (1998), Cortes and Vapnik (1995), Cristianini and Shawe-Taylor (2000), Hastie et al. (2001), Suykens et al. (2002), Vapnik (1998), Vapnik (2000), and the references therein for further details. 2.1 General results Let Ω be a polyhedral cone in RN.Let Ibe a finite non-empty set of individuals, partitioned as I=I+∪I−,with I+, I−6=∅.Each i∈Ihas an associated vector xi∈RN.One seeks an affine function separating I+ and I−,by strictly separating the sets {xi:i∈I+}and {xi:i∈I−}: (ω, β)∈Ω×Ris sought such that ω⊤xi+β > 0∀i∈I+ ω⊤xi+β < 0∀i∈I−.(2.1) If such (ω, β) exists, since, by assumption, I+, I−6=∅,one has that ω6= 0, and thus it defines a hyperplane H(ω, β) = {x∈RN:ω⊤x+β= 0},which 414 E. Carrizosa Particular choices, however, lead to more structured problems for which more efficient algorithms can be used. For instance, if k·k is the Euclidean distance, (2.10) leads to a linearly-constrained convex quadratic problem, whereas if k · k is a polyhedral norm (i.e., a norm whose unit ball is a polyhedron), then (2.10) can easily be transformed into an equivalent linear program. 2.2 Linear scores and SVM Once we have described our Multiple-Criteria decision problem, and after deriving the canonical formulation (2.10) for the SVM, we show how to interpret our problem, as described in Section 1, as a particular instance of (2.10). To do this, in what follows we construct a classification problem with the elements given in Section 1. Given the directed graph (A, P),define the index sets I+, I−as I+={(a, a′)∈ A×A :aPa′} I−={(a′, a)∈ A×A :aPa′}.(2.11) Each pair (a, a′)∈I+∪I−has associated a vector xaa′∈RN, xaa′= Ψ(a)−Ψ(a′).(2.12) ΩP-separation and Ω-separation are related as follows: Proposition 2.2. One has ΩP=ω∈Ω : (ω, 0) Ω-separates {xaa′:aPa′},{xa′a:aPa′} =ω∈Ω : (ω, β) Ω-separates {xaa′:aPa′},{xa′a:aPa′} for some β∈R Proof. Given ω∈ΩP,one has by definition of ΩPthat ω⊤(Ψ(a)−Ψ(a′)) >0∀a, a′, aPa′, which amounts to saying that (ω, 0) Ω-separates the sets {xaa′:aPa′},{xa′a: aPa′}.To finish the proof, let (ω, β) Ω-separate {xaa′:aPa′},{xa′a: aPa′},and let us conclude that ω∈ΩP.By definition, one has that ω⊤(Ψ(a)−Ψ(a′)) + β > 0∀a, a′, aPa′ ω⊤(Ψ(a′)−Ψ(a)) + β < 0∀a, a′, aPa′, Inferring weights via SVM 415 thus ω⊤Ψ(a)−Ψ(a′)>|β| ≥ 0∀a, a′, aPa′. Hence, ω∈ΩP. Proposition 2.3. For I+, I−, x = (xaa′)aP a′,as defined in (2.11)-(2.12), if (ω, β)is an optimal solution to (2.10), then β= 0. Proof. The constraints in (2.10) are written as ω⊤(Ψ(a)−Ψ(a′)) + β≥1∀a, a′∈ A, aPa′ ω⊤(Ψ(a′)−Ψ(a)) + β≤ −1∀a, a′∈ A, aPa′ ω∈Ω, or, in condensed form, ω⊤(Ψ(a)−Ψ(a′)) ≥1 + |β| ∀a, a′∈ A, aPa′ ω∈Ω.(2.13) Given (ω0, β0),feasible for (2.10), with β06= 0,one has that the solution ( 1 1+|β0|ω0,0) is also feasible, with objective value 1 1+|β0|kω0k◦<kω0k◦. Hence, (ω0, β0) cannot be optimal. Hence, we can impose in (2.10) that β= 0,and then (2.13) yields a finite set of linear constraints. This way we rewrite (2.10) as min kωk◦ s.t. ω⊤(Ψ(a)−Ψ(a′)) ≥1∀a, a′∈ A, aPa′ ω∈Ω, (2.14) which is equivalent to (1.1), taking as norm γ=k·k◦. In other words, finding the linear score function in Ω maximizing the minimum slack (normalization done via γ) is reduced to the problem of finding the hyperplane of largest margin, distances being measured through k·k =γ◦. For more structured problems, further results can be obtained. This is the case, for instance, when the norm has some monotonicity properties. We recall that k·k◦is said to be monotonic in RN +if (0 ≤ω≤ω)⇒ kωk◦≤ kωk◦, 416 E. Carrizosa whereas k·k◦is said to be strictly monotonic in RN +if (0 ≤ω≤ω, ω 6=ω)⇒ kωk◦<kωk◦. For monotonic norms we have the following Proposition 2.4. Let u∈RN +, u 6= 0,such that u⊤Ψ(a)−Ψ(a′)≤0∀a, a′∈ A, aPa′ q⊤ ju≤0∀j∈J. 1. If k·k◦is monotonic in RN +,then there exists ω∗,optimal for (2.14), such that min{ω∗ i:ui>0}= 0. 2. If k·k◦is strictly monotonic in RN +,then any ω∗optimal for (2.14) satisfies min{ω∗ i:ui>0}= 0. Proof. Let k·kbe monotonic in RN +,and let ω∗be optimal for (2.14). Define ∆ as ∆ = min ω∗ i ui :ui>0. If ∆ = 0,the result follows, so suppose ∆ >0.By construction of ∆ and the assumptions, ω∗ i−∆ui≥0∀i= 1,2,...,N q⊤ j(ω∗−∆u)≥0∀j∈J. Hence, ω∗−∆u∈Ω.Moreover, for any a, a′∈ A, aPa′,one has that (ω∗−∆u)⊤Ψ(a)−Ψ(a′)≥ω∗⊤Ψ(a)−Ψ(a′)≥1, thus ω∗−∆uis feasible for (2.14). Hence, 0≤ω∗−∆u≤ω∗ ω∗−∆u6=ω∗ If k·k◦is monotonic in RN +,we have that kω∗−∆uk◦≤ kω∗k◦, Inferring weights via SVM 417 and thus ω:= ω∗−∆uis also optimal and satisfies, by construction, min{ωi:ui>0}= 0. If k·k◦is strictly monotonic in RN +,we have that kω∗−∆uk◦<kω∗k◦, which is a contradiction, and thus, in this case, ω∗,as any optimal solution, must satisfy min{ω∗ i:ui>0}= 0. As an application of this result, consider a decision problem in which criterion Ckis measured in an ordinal scale, with nkdifferent ranked levels, L1,...,Lnk, L1being the best and Lnkthe worst. Following the strategy of introducing dummy variables, as described in Example 1.1, we define Ψk1(a) = 1,if atakes the value L1in criterion Ck 0,else . . .. . . Ψknk(a) = 1,if atakes the value Lnkin criterion Ck 0,else No further constraints are imposed on the weights associated with Ck,thus the only constraints involving the weights ωk,1...,ωk,nkshould be, as in Example 1.2, ωk,1≥ωk,2...≥ωk,nk If k·k◦is monotonic in RN +,then there exists an optimal ωwith ωknk= 0. Moreover, if k·k◦is strictly monotonic in RN +,then we can assert that any optimal ωsatisfies ωknk= 0.This is a direct consequence of Proposition 2.4. Indeed, take as uthe vector with 0 in all its components excepting those corresponding to the columns of the form Ψkj,which are set to 1. Such a vector ufulfills the assumptions of Proposition 2.4, and thus the result follows. 3 An interactive method SVM are known to enjoy excellent generalization properties both in theory and in practice, i.e., the rule constructed via (2.10) tends to be useful to 418 E. Carrizosa classify future instances in the classification problem, see Cristianini and Shawe-Taylor (2000), Vapnik (1998), and Vapnik (2000). In the context of Multiple-Criteria Decision Making, this property can be extremely useful for designing a method of progressive articulation of preferences, in which, unlike other classical interactive methods such as STEM, Benayoun et al. (1971), or the Tchebycheff method of Steuer and Choo (1983), the system at each step asks the decision-maker to find somehow an action better than the one proposed by the system, or to increase the amount of partial information incorporated in the polyhedral cone Ω. The procedure might work as follows Step 0: Initialize: •Choose a norm k·k in RN. •Take Ω1,polyhedral cone in RN +,modelling the relative importance of criteria. •Construct P1by pairwise comparison among some elements of A, P1. •Set k= 1 and go to Step 1. Step k:Find ωk,optimal solution to min kωk◦ s.t. ω⊤(Ψ(a)−Ψ(a′)) ≥1∀a, a′∈ A, aPka′ ω∈Ωk, (3.1) and find ak∈ A,optimal to max Ψ(a)⊤ωk s.t. a∈ A If (ak, ωk)is considered to be satisfactory then STOP with akas optimal solution and ωkas vector of weights. Else, enlarge Pk(e.g., by showing some apreferred to ak, and setting Pk+1 =Pk∪{(a, ak)}) or reduce Ωk(by adding a homogeneous constraint , and thus setting Ωk+1 = Ωk∩ {ω: q⊤ω≤0}). GoTo Step k+ 1. A toy example is given below. Inferring weights via SVM 419 Example 3.1. Consider the 4-objective knapsack problem max r⊤ 1x, . . . , r⊤ 4x s.t. d⊤x≤30 xi∈ {0,1}, i = 1,2,...,10, (3.2) with coefficients rjand dgiven in Table 4. Since this is a synthetic problem, we can assume that the weight vector ω∗of the decision-maker is at hand, and will check the output of the algorithm against such ω∗.In fact, the unknown ω∗will be given by ω∗= (0.1,0.3,0.2,0.4),(3.3) although no information on the weights (apart from non-negativity) will be provided to the system. Hence, Ω = RN +. It is clear that the high cardinality of the feasible set Aadvices against the use of any methodology which starts with a complete enumeration of A. Instead, the system samples some feasible solutions and defines strict preferences among them, leading to a strict preference P, from which a weight vector ωand an action aare obtained. r17 6 1 9 8 2 7 7 10 4 r22 1 −2 3 4 −8 2 6 9 −6 r310 2 4 9 1 5 3 6 3 9 r4−1 4 −15 4 1 1 −6 7 −7−1 d7 1 6 4 7 3 6 6 10 4 Table 4:Data for Example 3.1. We solve the single-objective knapsack problems max r⊤ ix s.t. d⊤x≤30 xj∈ {0,1} ∀j, and denote by yithe corresponding optimal solutions, as given in Table 5. The decision-maker is asked to sort the actions in {y1, y2, y3, y4},thus defining (A, P1).The decision-maker (in fact, we, following (3.3)) gives the following sorting y2P1y4P1y1P1y3 420 E. Carrizosa yir⊤ iyi y10 1 0 1 0 1 1 1 1 0 41 y20 1 0 1 1 0 0 1 1 0 23 y31 0 1 1 0 1 0 1 0 1 43 y40 1 0 1 1 1 0 1 0 0 17 Table 5:Optimal solutions xifor single-objective knapsack problems. As customary in SVM, we have chosen as k · k the Euclidean norm. Solving the convex quadratic problem with linear constraints (3.1) for Ω1= RN +and P1,one obtains ω1= (0,0.1209,0,0.1319) x1= (0,1,0,1,1,0,0,1,1,0) = y2 Such solution is not considered to be satisfactory, and P1is enriched, yielding P2.In particular, the decision maker provides some feasible action, y5, y5= (1,1,0,1,0,0,0,1,1,0), and P2is defined as P2=P1∪{(y5, x1)}. Problem (3.1) is solved for P2,yielding ω2, x2, ω2= (0,0.1994,0.2101,0.2462) x2= (1,1,0,1,1,0,0,1,0,1). The importance weights ω2obtained are not considered to be acceptable: ω2incorporates the fact that the least important criterion is the first one, and the most important is the last one, but fails to fit the rank of the second and third criteria, which are reversed with respect to ω∗. If we were concerned not only with finding the most preferred action, but also a full ranking on A,we could go on, e.g., by imposing the weight constraint ω2≥ω3.Adding this constraint to the problem, and solving again, we obtain ω3= (0,0.2162,0.2162,0.2568) x3=x2= (1,1,0,1,1,0,0,1,0,1). Inferring weights via SVM 421 Adding now the cut ω4≥1.5ω3leads to ω4= (0.0286,0.2571,0.2571,0.3857) x4=x3=x2= (1,1,0,1,1,0,0,1,0,1). At this moment, it seems the process is stabilized in the solution x2and we stop, yielding x2as optimal action, and ω4as vector of importance of weights. In fact, x2can be shown to be optimal for the knapsack problem aggregating the four criteria with weights ω∗. Hence, we have quickly obtained a most preferred action. 4 Concluding remarks and extensions In this note we have addressed the problem of extending an irreflexive binary relation (modelling strict preferences in a Multiple-Objective DecisionMaking problem) to a total preorder induced by a linear function of the criteria Ψ1,...,ΨN.Posed as a non-parametric classification problem, we have shown that (hard-margin) SVM can be used to come up with a procedure of progressive elicitation of preferences. The strategy proposed in this note can also be used for problems with uncertainty or vagueness in the data. Indeed, suppose the criteria are not scored in a precise way, and, instead, each score function Ψjdoes not take values in Rbut in the set of compact intervals of R, Ψj(a) = hΨj(a),Ψj(a)i⊂R, j = 1,2,...,N. (4.1) We could still use (3.1) taking into account that now, each constraint of type ω⊤Ψ(a)−Ψ(a′)≥1 has an interval as left-hand-side. Since the ωis non-negative (recall that, by assumption, Ω ⊂RN +), we can avoid interval-type constraints and re-write (3.1) as min kωk◦ s.t. PN j=1 ωjΨj(a)−Ψj(a′)≥1∀a, a′∈ A, aPka′ ω∈Ωk. (4.2) 422 E. Carrizosa SVM are used not only to linearly separate separable sets, but also to construct linear rules which misclassify ”few points” in the non-separable case, i.e., for the case in which Problem (2.10), or (4.2) if, as in (4.1), intervals are given for Ψj.is unfeasible. Several strategies have been proposed to do so. In particular, in the so-called soft-margin approach, Cortes and Vapnik (1995), (2.10) is replaced by a problem in the form min kωk2 2+CPi∈Iηp i s.a. yiω⊤xi+β≥1−ηi∀i∈I η≥0 ω∈Ω, (4.3) where p≥1 (typically p= 1) and Cis a strictly positive tuning parameter. See, e.g., Cristianini and Shawe-Taylor (2000), Suykens and Vandewalle (1999), Suykens et al. (2002), and Zhu et al. (2003), for related proposals, all seen as Goal-Programming strategies for solving unfeasible optimization problems, Carrizosa and Fliege (2002). In our Multiple-Criteria Decision-Making problem, it may be the case that ΩPis empty, since, e.g., Pcontains cycles of strict preference. Our aim of seeking Pωenriching Pis then replaced by the less ambitious aim of seeking Pωsomehow similar to P. The interactive procedure described in Section 3 can be used by replacing the SVM problem (3.1) by min kωk2 2+CPaPka′ηp aa′ s.t. ω⊤(Ψ(a)−Ψ(a′)) ≥1−ηaa′∀a, a′∈ A, aPka′ ηaa′≥0∀a, a′∈ A, aPka′ ω∈Ωk. (4.4) With this, one obtains a vector ωwhich hopefully satisfies most of the constraints defining ΩP.It should be observed, however, that the solution obtained this way is not necessarily a vector minimizing the number of constraints in ΩP,and can only be seen as a heuristic approach. Whereas the aim of this note was to show that SVM can be used in Multiple-Criteria Decision Making, it is also possible to see the problem the other way round. Indeed, the problem does not ask for the use of the standard SVM; on the contrary, certain issues are relevant here, but mostly ignored in the SVM literature. Among others, Inferring weights via SVM 423 1. the choice of the norm k·k.Since we are using γas a normalization, there is no natural choice for it. This asks for a deep study of SVM for arbitrary norms, extending the results of Mangasarian (2000). 2. the partial information on the criteria has been modelled via homogeneous linear constraints. Whereas SVM problems with constraints have already been addressed in the literature, e.g., Fung et al. (2001), this seems to be more the exception than the rule. Further results, both at analytical and algorithmic levels, are needed. These issues deserve further study and will be the subject of future research. References Benayoun R., Montgolfier J. de, Tergny J. and Laritchev O. (1971). Linear Programming and Multiple Objective Functions: STEP Method (STEM). Mathematical Programming 1, 366–375. Burges C. (1998). A Tutorial on Support Vector Machines for Pattern Recognition”. Data Mining and Knowledge Discovery 2, 121–167. Carrizosa E. and Conde E. (2002). A Fractional Model for Locating Semi-Desirable Facilities on Networks. European Journal of Operational Research 136, 67–80. Carrizosa E., Conde E., Fern´andez F.R. and Puerto J. (1995). Multi-Criteria Analysis with Partial Information about the Weighting Coefficients. European Journal of Operational Research 81, 291–301. Carrizosa E. and Fliege J. (2002). Generalized Goal Programming: Polynomial methods and applications. Mathematical Programming 93, 281–303. Cortes C. and Vapnik V. (1995). Support Vector Networks. Machine Learning 20, 273–297. Crammer K. and Singer Y. (2001). Pranking with Ranking. Proceedings of the Fourteenth Annual Conference on Neural Information Processing Systems, 641–647. Cristianini N. and Shawe-Taylor J. (2000). An Introduction to Support Vector Machines. Cambridge University Press. Freund Y., Iyer R., Schapire R.E. and Singer Y. (1998). An Efficient Boosting Algorithm for Combining Preferences. Proceedings of the Fifteenth International Conference on Machine Learning, Madison, Wisconsin, USA, 170–178. Fung G., Mangasarian O.L. and Shavlik J. (2001). Knowledge-Based Support