Sociedad de Es ad´ıs ica e In es igaci´on Ope a i a
Top (2006) Vol. 14, No. 2, pp. 399–424
De i ing Weigh s in Mul iple-C i e ia Decision
Making wi h Suppo Vec o Machines
Emilio Ca izosa
Facul ad de Ma em´a icas, Uni e sidad de Se illa
A da Reina Me cedes s/n, 41012 Se illa (Spain)
E-mail: ec[email p o ec ed]
Abs ac
A key p oblem in Mul iple-C i e ia Decision Making is how o measu e he impo -
ance o he di e en c i e ia when jus a pa ial p e e ence ela ion among ac ions
is gi en. In his no e we add ess he p oblem o cons uc ing a linea sco e unc ion
(and hus how o associa e weigh s o impo ance o he c i e ia) when a bina y
ela ion compa ing ac ions and pa ial in o ma ion ( ela i e impo ance) on he
c i e ia a e gi en. I is shown ha hese asks can be done ia Suppo Vec o Ma-
chines, an inc easingly popula Da a Mining echnique, which educes he sea ch o
he weigh s o he esolu ion o (a se ies o ) nonlinea con ex op imiza ion p oblems
wi h linea cons ain s. An in e ac i e me hod is hen p esen ed and illus a ed by
sol ing a mul iple-objec i e 0-1 knapsack p oblem. Ex ensions o he case in which
da a a e imp ecise (gi en by in e als) o in ansi i i ies in s ic p e e ences exis
a e ou lined.
Key Wo ds: Linea sco e unc ions, suppo ec o machines, mul iple-c i e ia
decision making wi h pa ial in o ma ion, da a mining.
AMS subjec classi ica ion: 90B50, 90C30, 62H30.
1 In oduc ion
Suppose we a e gi en
•an in ege N,
•a ini e di ec ed g aph (A, P),whose se o edges Pis non-emp y and
con ains no loops,
Pa ially suppo ed by g an s MTM2005-09362-103-01 o MEC, Spain, and FQM-329 o
Jun a de Andaluc´ıa, Spain. Pa o his wo k has been w i en while he au ho isi ed
he Depa men o S a is ics and Decision Suppo Sys ems o he Uni e si ¨a Wien.
The au ho hanks he e e ees o hei cons uc i e sugges ions, which ha e helped o
imp o e he quali y o he pape .
Manusc ip ecei ed: Ap il 2004. Final e sion accep ed: No embe 2006.
400 E. Ca izosa
•a unc ion Ψ : A −→ RN,
•a polyhed al cone Ω in RN
+,Ω6={0}, ep esen ed in he o m
Ω = nω∈RN:q⊤
jω≥0, j ∈Jo,
o a ini e se {qj:j∈J} ⊂ RN,
•a no m γin RN,
and conside he op imiza ion p oblem
max
ω∈Ω {0}min
(a,a′)∈P
ω⊤Ψ(a)−ω⊤Ψ(a′)
γ(ω).(1.1)
P oblem (1.1) has a clea in e p e a ion in Mul iple-C i e ia Decision
Making, as ske ched below:
A ep esen s a ini e se o ac ions, whe e we ha e de ined
•a ec o - alued unc ion Ψ : A −→ RN,in such a way ha Ψj(a)
ep esen s he sco e o ac ion aacco ding o he j- h c i e ion, j=
1,2,...,N. All sco es a e assumed o be in a scale ” he highe he
be e ”
•a bina y i e lexi e ela ion P⊂ A×A.No u he assump ions (e.g.
ansi i i y o weak connec edness) a e made on P. Fo ins ance, P
migh be he s ic p e e ences ob ained wi h Elec e I, Roy (1968), o
he s ic p e e ences de ec ed ia a sample o pai wise compa isons
among ac ions.
By abuse o no a ion, we will w i e in wha ollows indi e en ly aPa′
o (a, a′)∈P.
Ou aim is o ex end he bina y ela ion P o a o al p eo de on A ia
a linea unc ion o he sco es gi en by Ψ.In o he wo ds, we seek ω∈Ω
such ha
ω⊤Ψ(a)> ω⊤Ψ(a′)∀a, a′∈ A, aPa′.(1.2)
Any ωsa is ying (1.2) induces a pai o bina y ela ions (Pω, Iω) on A,
aPωa′i ω⊤Ψ(a)> ω⊤Ψ(a′)
aIωa′i ω⊤Ψ(a) = ω⊤Ψ(a′),(1.3)
In e ing weigh s ia SVM 401
o s ic p e e ence and indi e ence.
We ha e ha he s ic p e e ence Pωis compa ible wi h P, in he sense
ha he se Pis included in he se Pω, and hus no in o ma ion con ained
in Pis los i Pis eplaced by Pω.Mo eo e , Pωenjoys p ope ies usually
conside ed o be desi able such as ansi i i y. By cons uc ion, each com-
ponen o ωmeasu es he impo ance o he co esponding c i e ion in Pω,
and hence we can also see ωjas a measu e o impo ance o Ψjin P.
We illus a e he model in he ollowing Example.
Example 1.1. Conside he p oblem wi h 6 ac ions, (A={a1,...,a6}),
N= 4 c i e ia, C1,...,C4,wi h ewa ds sco ed (in o dinal o ca dinal
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
a5A e age 8 1 1
a6Low 4 4 4
Table 1:Decision able o Example 1.1
Conside also he i e lexi e bina y ela ion Pgi en on A ep esen ed
in Figu e 1.
The mechanism used o cons uc such Pis simple: aiPaji c i e ion
C1in aiis s ic ly be e han C1in aj,and, a he same ime, he a e age
o he h ee emaining sco es in aiis s ic ly g ea e han he a e age in
aj.
In o de o accommoda e hese da a o he model conside ed, he c i-
402 E. Ca izosa
a1 a2
a3
a4
a5
a6
(High,4,2,8) (Low,2,2,7)
(High,3,4,3)
(Low,2,5,2)(A e age,8,1,1)
(Low,4,4,4)
Figu e 1:The g aph (A, P)in Example 1.1
e ia mus be measu ed in a ca dinal scale. To do ha , we de ine
Ψ11(a) = 1,i ain C1 akes he alue ”High”
0,else
Ψ12(a) = 1,i ain C1 akes he alue “A e age”
0,else
Ψ13(a) = 1,i ain C1 akes he alue “Low”
0,else
Ψi(a) = sco e o aacco ding o Ciin Table 1, i = 2,...,4,
and we ob ain Table 2.
Unde hese assump ions, we seek a ec o o weigh s ω, o be associa ed
wi h he columns o Table 2, in such a way ha o dinal alues a e eplaced
by a io-scaled alues, and he o al anking ob ained by a e aging he
ac ions ωis compa ible wi h P e aining all he in o ma ion on he c i e ia:
since he c i e ia a e o he o m “ he highe he be e ,” he weigh s should
be non-nega i e; mo eo e , he weigh associa ed wi h Ψ11 should no be
smalle han he weigh associa ed wi h Ψ12,which should no be smalle
han he weigh associa ed wi h Ψ13.
In e ing weigh s ia 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 o Example 1.1. Ca dinal scales
Le ΩPdeno e he se o solu ions o (1.2),
ΩP=nω∈Ω : ω⊤Ψ(a)> ω⊤Ψ(a′)∀(a, a′)∈Po.
In p ac ice, o cou se, ΩPcan be emp y. This is he case, o ins ance,
when he g aph (A, P) con ains cycles. In such cases, no Pωcompa ible
wi h Pexis s. In wha ollows we assume ha ΩP6=∅.How o add ess he
case ΩP=∅will be ou lined in Sec ion 4.
In case ω∈ΩPexis s, i is highly desi able ha such ωmakes maximal
sepa a ion be ween ac ions, i.e., he slack ω⊤Ψ(a)−ω⊤Ψ(a′) should be no
only posi i e bu high in all pai s a, a′∈ A, aPa′.To do ha , we can ake
as c i e ion he maximiza ion o he lowes slack,
min
(a,a′)∈Pnω⊤Ψ(a)−ω⊤Ψ(a′)o.(1.4)
Maximizing o e Ω (o o e ΩP) he lowes slack is, as soon as ΩP6=∅,an
op imiza ion p oblem wi h unbounded solu ion: gi en ω∈ΩP, ϑω ∈ΩP
o any ϑ > 0,and makes he smalles slack g ow wi hou limi by g owing
ϑ.
Hence, we ha e o in oduce a no maliza ion condi ion which enables
us o iden i y ωand ϑω, ϑ > 0.This can be done e.g., by se ing γ(ω) = 1
o a gi en no m, o , equi alen ly, as done in (1.1).
The inclusion o linea cons ain s on ωenables us o conside p oblems
wi h pa ial in o ma ion on he impo ance o be gi en o he di e en
scala unc ions Ψj,e.g., Ca izosa e al. (1995), and Ca izosa and Conde
(2002). Fo ins ance, since, by assump ion, Ψjsco es a c i e ion o ype

404 E. Ca izosa
” he highe , he be e ”, he ωsough should sa is y, oge he wi h (1.2),
a sign cons ain
ωj≥0.(1.5)
Mo eo e , we may ha e in o ma ion abou he ela i e impo ance o
c i e ia. Fo ins ance, om wo c i e ia Ψi,Ψjo ype ” he highe , he
be e ”, we may impose ha he weigh associa ed wi h c i e ion ishould
no exceed Kij imes he weigh associa ed wi h he j- h c i e ion. This
way we gene a e he homogeneous linea cons ain
ωi≤Kijωj,(1.6)
e.g., Ca izosa and Conde (2002), and Ca izosa e al. (1995).
Mo e complex homogeneous linea cons ain s may appea , o ins ance,
in decision p oblems unde isk, wi h Nscena ios, each ωj ep esen ing he
p obabili y o he j- h scena io. Unde such assump ions, since he weigh s
ep esen p obabili ies, hei sum mus equal 1.This is modelled by aking
as γin (1.1) he ℓ1no m. Mo eo e , i we ha e in e al in o ma ion abou
he p obabili y o he i- h scena io, in he o m
Li≤ωi≤Ui,
we can ans o m his condi ion in o
Li
1−Li≤ωi
1−ωi≤Ui
1−Ui
,
o in o he pai o homogeneous linea cons ain s
Li
1−LiPj6=iωj≤ωi
Ui
1−UiPj6=iωj≥ωi.(1.7)
On he o he hand, i wo ac ions, a, a′a e known o be indi e en , one
would ha e (Ψ(a)−Ψ(a′))⊤ω≥0
(Ψ(a′)−Ψ(a))⊤ω≥0(1.8)
As seen abo e, sign cons ain s and, among o he s, hose o ype (1.6),
(1.7) and (1.8), can be modelled by imposing ha ωbelongs o a polyhed al
cone Ω.
In e ing weigh s ia SVM 405
Example 1.2. Wi h he da a o Example 1.1, since he c i e ia in Table
1 a e all o ype ” he highe he be e ”, all weigh s mus be non-nega i e.
Since we ha e passed C1 o a ca dinal scale, see Table 2, we mus impose
also ha ω11 ≥ω12 ≥ω13.
This in o ma ion on he weigh s yields he polyhed al cone
Ω = ω= (ω1, ω2,...,ω6)∈R6
+:
(1,−1,0,0,0,0)⊤ω≥0
(0,1,−1,0,0,0)⊤ω≥0}
(1.9)
Sol ing nume ically (1.1) aking as γ he Euclidean no m, he ollowing
weigh s (measu es o impo ance o he c i e ia) a e ob ained a e no mal-
iza ion o sum 1:
ω= (ω11, ω12, ω13, ω2, ω3, ω4) = (0.333,0.000,0.000,0.333,0.000,0.333).
(1.10)
Hence, only he highes alue o C1, oge he wi h C2and C4a e ele-
an , all being equally impo an .
Wi h his in o ma ion, he unc ion a7−→ ω⊤Ψ(a) is gi en in Table 3,
yielding he o al s ic o de
a1Pωa2Pωa5Pωa6Pωa3Pωa4.
aiω⊤Ψ(a)
a14.334
a23.001
a32.333
a41.333
a53.000
a62.667
Table 3:Values o ω⊤Ψ(·)in Example 1.2
Suppose we also know ha C4should no be weigh ed much s onge
(say, 5 imes) han C3,modelled wi h he cons ain
ω4≤5ω3.(1.11)
406 E. Ca izosa
a1 a2
a3
a4
a5
a6
(High,4,2,8) (Low,2,2,7)
(High,3,4,3)
(Low,2,5,2)(A e age,8,1,1)
(Low,4,4,4)
Figu e 2:The g aph (A, Pω)in Example 1.1
This cons ain mus hen be added o hose gi en in (1.9).
Sol ing nume ically (1.1) aking as γ he Euclidean no m, he ollowing
weigh s (measu es o impo ance o he c i e ia) a e ob ained a e no mal-
iza ion o sum 1:
ω= (ω11, ω12, ω13, ω2, ω3, ω4) = (0.342,0.000,0.000,0.340,0.053,0.265),
yielding he o al s ic o de
a1Pωa5Pωa2Pωa6Pωa3Pωa4.
Hence, he addi ion o he cons ain (1.11) has p oduced sligh changes in
he op imal weigh ec o ω, bu has led o a change in he anking o he
al e na i es (please compa e he posi ion o a3and a5in bo h ankings.
The g aph o Pωis depic ed in Figu e 2. P e e ences al eady p esen in
Pa e plo ed wi h a hick a ow, whe eas hose which did no exis in P
and a e added by Pωa e do ed.
In o de o gain insigh in o P oblem (1.1), and o ex end he me hod-
ology o he case in which ΩPis emp y, we connec his wi h (a a ian o )
In e ing weigh s ia SVM 407
Suppo Vec o Machines. O he app oaches o o dinal eg ession based on
Suppo Vec o Machines can be ound e.g., in F eund e al. (2001), and
He b ich e al. (2000).
The emainde o he pape is o ganized as ollows. In Sec ion 2 we
make a quick in oduc ion o Suppo Vec o Machines, and eph ase ou
p oblem wi hin his amewo k. An in e ac i e me hodology is ou lined in
Sec ion 3, whe e an illus a i e example is also gi en. Possible ex ensions
o his wo k a e gi en in Sec ion 4.
Th oughou his pape , con (X) deno es he con ex hull o a se X, and
cone(X) deno es he conic hull o X, i.e., cone(X) is he se o poin s which
can be exp essed as a linea combina ion wi h non-nega i e coe icien s o
elemen s o X, C ame and Singe (2001).
2 Suppo Vec o Machines
Be o e pa icula izing o ou p oblem, (see Sec ion 2.2), we i s b ie ly
ou line he main ideas unde lying he Disc iminan Analysis me hod known
as Suppo Vec o Machines, SVM. The eade is e e ed o e.g., Bu ges
(1998), Co es and Vapnik (1995), C is ianini and Shawe-Taylo (2000),
Has ie e al. (2001), Suykens e al. (2002), Vapnik (1998), Vapnik (2000),
and he e e ences he ein o u he de ails.
2.1 Gene al esul s
Le Ω be a polyhed al cone in RN.Le Ibe a ini e non-emp y se o
indi iduals, pa i ioned as I=I+∪I−,wi h I+, I−6=∅.Each i∈Ihas
an associa ed ec o xi∈RN.One seeks an a ine unc ion sepa a ing I+
and I−,by s ic ly sepa a ing he se s {xi:i∈I+}and {xi:i∈I−}:
(ω, β)∈Ω×Ris sough such ha
ω⊤xi+β > 0∀i∈I+
ω⊤xi+β < 0∀i∈I−.(2.1)
I such (ω, β) exis s, since, by assump ion, I+, I−6=∅,one has ha ω6= 0,
and hus i de ines a hype plane H(ω, β) = {x∈RN:ω⊤x+β= 0},which
414 E. Ca izosa
Pa icula choices, howe e , lead o mo e s uc u ed p oblems o which
mo e e icien algo i hms can be used. Fo ins ance, i k·k is he Euclidean
dis ance, (2.10) leads o a linea ly-cons ained con ex quad a ic p oblem,
whe eas i k · k is a polyhed al no m (i.e., a no m whose uni ball is a
polyhed on), hen (2.10) can easily be ans o med in o an equi alen linea
p og am.
2.2 Linea sco es and SVM
Once we ha e desc ibed ou Mul iple-C i e ia decision p oblem, and a e
de i ing he canonical o mula ion (2.10) o he SVM, we show how o
in e p e ou p oblem, as desc ibed in Sec ion 1, as a pa icula ins ance
o (2.10). To do his, in wha ollows we cons uc a classi ica ion p oblem
wi h he elemen s gi en in Sec ion 1.
Gi en he di ec ed g aph (A, P),de ine he index se s I+, I−as
I+={(a, a′)∈ A×A :aPa′}
I−={(a′, a)∈ A×A :aPa′}.(2.11)
Each pai (a, a′)∈I+∪I−has associa ed a ec o xaa′∈RN,
xaa′= Ψ(a)−Ψ(a′).(2.12)
ΩP-sepa a ion and Ω-sepa a ion a e ela ed as ollows:
P oposi ion 2.2. One has
ΩP=ω∈Ω : (ω, 0) Ω-sepa a es {xaa′:aPa′},{xa′a:aPa′}
=ω∈Ω : (ω, β) Ω-sepa a es {xaa′:aPa′},{xa′a:aPa′}
o some β∈R
P oo . Gi en ω∈ΩP,one has by de ini ion o ΩP ha
ω⊤(Ψ(a)−Ψ(a′)) >0∀a, a′, aPa′,
which amoun s o saying ha (ω, 0) Ω-sepa a es he se s {xaa′:aPa′},{xa′a:
aPa′}.To inish he p oo , le (ω, β) Ω-sepa a e {xaa′:aPa′},{xa′a:
aPa′},and le us conclude ha ω∈ΩP.By de ini ion, one has ha
ω⊤(Ψ(a)−Ψ(a′)) + β > 0∀a, a′, aPa′
ω⊤(Ψ(a′)−Ψ(a)) + β < 0∀a, a′, aPa′,

In e ing weigh s ia SVM 415
hus
ω⊤Ψ(a)−Ψ(a′)>|β| ≥ 0∀a, a′, aPa′.
Hence, ω∈ΩP.
P oposi ion 2.3. Fo I+, I−, x = (xaa′)aP a′,as de ined in (2.11)-(2.12),
i (ω, β)is an op imal solu ion o (2.10), hen β= 0.
P oo . The cons ain s in (2.10) a e w i en as
ω⊤(Ψ(a)−Ψ(a′)) + β≥1∀a, a′∈ A, aPa′
ω⊤(Ψ(a′)−Ψ(a)) + β≤ −1∀a, a′∈ A, aPa′
ω∈Ω,
o , in condensed o m,
ω⊤(Ψ(a)−Ψ(a′)) ≥1 + |β| ∀a, a′∈ A, aPa′
ω∈Ω.(2.13)
Gi en (ω0, β0), easible o (2.10), wi h β06= 0,one has ha he solu-
ion ( 1
1+|β0|ω0,0) is also easible, wi h objec i e alue 1
1+|β0|kω0k◦<kω0k◦.
Hence, (ω0, β0) canno be op imal.
Hence, we can impose in (2.10) ha β= 0,and hen (2.13) yields a
ini e se o linea cons ain s. This way we ew i e (2.10) as
min kωk◦
s. . ω⊤(Ψ(a)−Ψ(a′)) ≥1∀a, a′∈ A, aPa′
ω∈Ω,
(2.14)
which is equi alen o (1.1), aking as no m γ=k·k◦.
In o he wo ds, inding he linea sco e unc ion in Ω maximizing he
minimum slack (no maliza ion done ia γ) is educed o he p oblem o
inding he hype plane o la ges ma gin, dis ances being measu ed h ough
k·k =γ◦.
Fo mo e s uc u ed p oblems, u he esul s can be ob ained. This is
he case, o ins ance, when he no m has some mono onici y p ope ies.
We ecall ha k·k◦is said o be mono onic in RN
+i
(0 ≤ω≤ω)⇒ kωk◦≤ kωk◦,
416 E. Ca izosa
whe eas k·k◦is said o be s ic ly mono onic in RN
+i
(0 ≤ω≤ω, ω 6=ω)⇒ kωk◦<kωk◦.
Fo mono onic no ms we ha e he ollowing
P oposi ion 2.4. Le u∈RN
+, u 6= 0,such ha
u⊤Ψ(a)−Ψ(a′)≤0∀a, a′∈ A, aPa′
q⊤
ju≤0∀j∈J.
1. I k·k◦is mono onic in RN
+, hen he e exis s ω∗,op imal o (2.14),
such ha min{ω∗
i:ui>0}= 0.
2. I k·k◦is s ic ly mono onic in RN
+, hen any ω∗op imal o (2.14)
sa is ies min{ω∗
i:ui>0}= 0.
P oo . Le k·kbe mono onic in RN
+,and le ω∗be op imal o (2.14). De ine
∆ as
∆ = min ω∗
i
ui
:ui>0.
I ∆ = 0, he esul ollows, so suppose ∆ >0.By cons uc ion o ∆
and he assump ions,
ω∗
i−∆ui≥0∀i= 1,2,...,N
q⊤
j(ω∗−∆u)≥0∀j∈J.
Hence, ω∗−∆u∈Ω.Mo eo e , o any a, a′∈ A, aPa′,one has ha
(ω∗−∆u)⊤Ψ(a)−Ψ(a′)≥ω∗⊤Ψ(a)−Ψ(a′)≥1,
hus ω∗−∆uis easible o (2.14).
Hence,
0≤ω∗−∆u≤ω∗
ω∗−∆u6=ω∗
I k·k◦is mono onic in RN
+,we ha e ha
kω∗−∆uk◦≤ kω∗k◦,
In e ing weigh s ia SVM 417
and hus ω:= ω∗−∆uis also op imal and sa is ies, by cons uc ion,
min{ωi:ui>0}= 0.
I k·k◦is s ic ly mono onic in RN
+,we ha e ha
kω∗−∆uk◦<kω∗k◦,
which is a con adic ion, and hus, in his case, ω∗,as any op imal solu ion,
mus sa is y min{ω∗
i:ui>0}= 0.
As an applica ion o his esul , conside a decision p oblem in which
c i e ion Ckis measu ed in an o dinal scale, wi h nkdi e en anked le els,
L1,...,Lnk, L1being he bes and Lnk he wo s .
Following he s a egy o in oducing dummy a iables, as desc ibed in
Example 1.1, we de ine
Ψk1(a) = 1,i a akes he alue L1in c i e ion Ck
0,else
.
.
..
.
.
Ψknk(a) = 1,i a akes he alue Lnkin c i e ion Ck
0,else
No u he cons ain s a e imposed on he weigh s associa ed wi h Ck, hus
he only cons ain s in ol ing he weigh s ωk,1...,ωk,nkshould be, as in
Example 1.2,
ωk,1≥ωk,2...≥ωk,nk
I k·k◦is mono onic in RN
+, hen he e exis s an op imal ωwi h ωknk= 0.
Mo eo e , i k·k◦is s ic ly mono onic in RN
+, hen we can asse ha any
op imal ωsa is ies ωknk= 0.This is a di ec consequence o P oposi ion
2.4. Indeed, ake as u he ec o wi h 0 in all i s componen s excep ing
hose co esponding o he columns o he o m Ψkj,which a e se o 1.
Such a ec o u ul ills he assump ions o P oposi ion 2.4, and hus he
esul ollows.
3 An in e ac i e me hod
SVM a e known o enjoy excellen gene aliza ion p ope ies bo h in heo y
and in p ac ice, i.e., he ule cons uc ed ia (2.10) ends o be use ul o
418 E. Ca izosa
classi y u u e ins ances in he classi ica ion p oblem, see C is ianini and
Shawe-Taylo (2000), Vapnik (1998), and Vapnik (2000).
In he con ex o Mul iple-C i e ia Decision Making, his p ope y can
be ex emely use ul o designing a me hod o p og essi e a icula ion o
p e e ences, in which, unlike o he classical in e ac i e me hods such as
STEM, Benayoun e al. (1971), o he Tchebyche me hod o S eue and
Choo (1983), he sys em a each s ep asks he decision-make o ind some-
how an ac ion be e han he one p oposed by he sys em, o o inc ease
he amoun o pa ial in o ma ion inco po a ed in he polyhed al cone Ω.
The p ocedu e migh wo k as ollows
S ep 0: Ini ialize:
•Choose a no m k·k in RN.
•Take Ω1,polyhed al cone in RN
+,modelling he ela i e
impo ance o c i e ia.
•Cons uc P1by pai wise compa ison among some elemen s
o A, P1.
•Se k= 1 and go o S ep 1.
S ep k:Find ωk,op imal solu ion o
min kωk◦
s. . ω⊤(Ψ(a)−Ψ(a′)) ≥1∀a, a′∈ A, aPka′
ω∈Ωk,
(3.1)
and ind ak∈ A,op imal o
max Ψ(a)⊤ωk
s. . a∈ A
I (ak, ωk)is conside ed o be sa is ac o y hen
STOP wi h akas op imal solu ion and ωkas ec o o weigh s.
Else, enla ge Pk(e.g., by showing some ap e e ed o ak,
and se ing Pk+1 =Pk∪{(a, ak)}) o educe Ωk(by adding a
homogeneous cons ain , and hus se ing Ωk+1 = Ωk∩ {ω:
q⊤ω≤0}). GoTo S ep k+ 1.
A oy example is gi en below.
In e ing weigh s ia SVM 419
Example 3.1. Conside he 4-objec i e knapsack p oblem
max  ⊤
1x, . . . , ⊤
4x
s. . d⊤x≤30
xi∈ {0,1}, i = 1,2,...,10,
(3.2)
wi h coe icien s jand dgi en in Table 4. Since his is a syn he ic p oblem,
we can assume ha he weigh ec o ω∗o he decision-make is a hand,
and will check he ou pu o he algo i hm agains such ω∗.In ac , he
unknown ω∗will be gi en by
ω∗= (0.1,0.3,0.2,0.4),(3.3)
al hough no in o ma ion on he weigh s (apa om non-nega i i y) will be
p o ided o he sys em. Hence, Ω = RN
+.
I is clea ha he high ca dinali y o he easible se Aad ices agains
he use o any me hodology which s a s wi h a comple e enume a ion o
A. Ins ead, he sys em samples some easible solu ions and de ines s ic
p e e ences among hem, leading o a s ic p e e ence P, om which a
weigh ec o ωand an ac ion aa e ob ained.
17 6 1 9 8 2 7 7 10 4
22 1 −2 3 4 −8 2 6 9 −6
310 2 4 9 1 5 3 6 3 9
4−1 4 −15 4 1 1 −6 7 −7−1
d7 1 6 4 7 3 6 6 10 4
Table 4:Da a o Example 3.1.
We sol e he single-objec i e knapsack p oblems
max ⊤
ix
s. . d⊤x≤30
xj∈ {0,1} ∀j,
and deno e by yi he co esponding op imal solu ions, as gi en in Table 5.
The decision-make is asked o so he ac ions in {y1, y2, y3, y4}, hus
de ining (A, P1).The decision-make (in ac , we, ollowing (3.3)) gi es he
ollowing so ing
y2P1y4P1y1P1y3

420 E. Ca izosa
yi ⊤
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:Op imal solu ions xi o single-objec i e knapsack p oblems.
As cus oma y in SVM, we ha e chosen as k · k he Euclidean no m.
Sol ing he con ex quad a ic p oblem wi h linea cons ain s (3.1) o Ω1=
RN
+and P1,one ob ains
ω1= (0,0.1209,0,0.1319)
x1= (0,1,0,1,1,0,0,1,1,0) = y2
Such solu ion is no conside ed o be sa is ac o y, and P1is en iched, yield-
ing P2.In pa icula , he decision make p o ides some easible ac ion, y5,
y5= (1,1,0,1,0,0,0,1,1,0),
and P2is de ined as
P2=P1∪{(y5, x1)}.
P oblem (3.1) is sol ed o P2,yielding ω2, x2,
ω2= (0,0.1994,0.2101,0.2462)
x2= (1,1,0,1,1,0,0,1,0,1).
The impo ance weigh s ω2ob ained a e no conside ed o be accep -
able: ω2inco po a es he ac ha he leas impo an c i e ion is he i s
one, and he mos impo an is he las one, bu ails o i he ank o he
second and hi d c i e ia, which a e e e sed wi h espec o ω∗.
I we we e conce ned no only wi h inding he mos p e e ed ac ion,
bu also a ull anking on A,we could go on, e.g., by imposing he weigh
cons ain ω2≥ω3.Adding his cons ain o he p oblem, and sol ing
again, we ob ain
ω3= (0,0.2162,0.2162,0.2568)
x3=x2= (1,1,0,1,1,0,0,1,0,1).
In e ing weigh s ia SVM 421
Adding now he cu ω4≥1.5ω3leads o
ω4= (0.0286,0.2571,0.2571,0.3857)
x4=x3=x2= (1,1,0,1,1,0,0,1,0,1).
A his momen , i seems he p ocess is s abilized in he solu ion x2and
we s op, yielding x2as op imal ac ion, and ω4as ec o o impo ance o
weigh s. In ac , x2can be shown o be op imal o he knapsack p oblem
agg ega ing he ou c i e ia wi h weigh s ω∗.
Hence, we ha e quickly ob ained a mos p e e ed ac ion.
4 Concluding ema ks and ex ensions
In his no e we ha e add essed he p oblem o ex ending an i e lexi e bi-
na y ela ion (modelling s ic p e e ences in a Mul iple-Objec i e Decision-
Making p oblem) o a o al p eo de induced by a linea unc ion o he
c i e ia Ψ1,...,ΨN.Posed as a non-pa ame ic classi ica ion p oblem, we
ha e shown ha (ha d-ma gin) SVM can be used o come up wi h a p o-
cedu e o p og essi e elici a ion o p e e ences.
The s a egy p oposed in his no e can also be used o p oblems wi h
unce ain y o agueness in he da a. Indeed, suppose he c i e ia a e no
sco ed in a p ecise way, and, ins ead, each sco e unc ion Ψjdoes no ake
alues in Rbu in he se o compac in e als o R,
Ψj(a) = hΨj(a),Ψj(a)i⊂R, j = 1,2,...,N. (4.1)
We could s ill use (3.1) aking in o accoun ha now, each cons ain
o ype
ω⊤Ψ(a)−Ψ(a′)≥1
has an in e al as le -hand-side. Since he ωis non-nega i e ( ecall ha , by
assump ion, Ω ⊂RN
+), we can a oid in e al- ype cons ain s and e-w i e
(3.1) as
min kωk◦
s. . PN
j=1 ωjΨj(a)−Ψj(a′)≥1∀a, a′∈ A, aPka′
ω∈Ωk.
(4.2)
422 E. Ca izosa
SVM a e used no only o linea ly sepa a e sepa able se s, bu also o
cons uc linea ules which misclassi y ” ew poin s” in he non-sepa able
case, i.e., o he case in which P oblem (2.10), o (4.2) i , as in (4.1), in e -
als a e gi en o Ψj.is un easible. Se e al s a egies ha e been p oposed
o do so. In pa icula , in he so-called so -ma gin app oach, Co es and
Vapnik (1995), (2.10) is eplaced by a p oblem in he o m
min kωk2
2+CPi∈Iηp
i
s.a. yiω⊤xi+β≥1−ηi∀i∈I
η≥0
ω∈Ω,
(4.3)
whe e p≥1 ( ypically p= 1) and Cis a s ic ly posi i e uning pa ame e .
See, e.g., C is ianini and Shawe-Taylo (2000), Suykens and Vandewalle
(1999), Suykens e al. (2002), and Zhu e al. (2003), o ela ed p oposals,
all seen as Goal-P og amming s a egies o sol ing un easible op imiza ion
p oblems, Ca izosa and Fliege (2002).
In ou Mul iple-C i e ia Decision-Making p oblem, i may be he case
ha ΩPis emp y, since, e.g., Pcon ains cycles o s ic p e e ence. Ou
aim o seeking Pωen iching Pis hen eplaced by he less ambi ious aim
o seeking Pωsomehow simila o P. The in e ac i e p ocedu e desc ibed
in Sec ion 3 can be used by eplacing he SVM p oblem (3.1) by
min kωk2
2+CPaPka′ηp
aa′
s. . ω⊤(Ψ(a)−Ψ(a′)) ≥1−ηaa′∀a, a′∈ A, aPka′
ηaa′≥0∀a, a′∈ A, aPka′
ω∈Ωk.
(4.4)
Wi h his, one ob ains a ec o ωwhich hope ully sa is ies mos o he
cons ain s de ining ΩP.I should be obse ed, howe e , ha he solu ion
ob ained his way is no necessa ily a ec o minimizing he numbe o
cons ain s in ΩP,and can only be seen as a heu is ic app oach.
Whe eas he aim o his no e was o show ha SVM can be used in
Mul iple-C i e ia Decision Making, i is also possible o see he p oblem
he o he way ound. Indeed, he p oblem does no ask o he use o he
s anda d SVM; on he con a y, ce ain issues a e ele an he e, bu mos ly
igno ed in he SVM li e a u e. Among o he s,
In e ing weigh s ia SVM 423
1. he choice o he no m k·k.Since we a e using γas a no maliza ion,
he e is no na u al choice o i . This asks o a deep s udy o SVM
o a bi a y no ms, ex ending he esul s o Mangasa ian (2000).
2. he pa ial in o ma ion on he c i e ia has been modelled ia homo-
geneous linea cons ain s. Whe eas SVM p oblems wi h cons ain s
ha e al eady been add essed in he li e a u e, e.g., Fung e al. (2001),
his seems o be mo e he excep ion han he ule. Fu he esul s,
bo h a analy ical and algo i hmic le els, a e needed.
These issues dese e u he s udy and will be he subjec o u u e esea ch.
Re e ences
Benayoun R., Mon gol ie J. de, Te gny J. and La i che O. (1971). Linea P o-
g amming and Mul iple Objec i e Func ions: STEP Me hod (STEM). Ma h-
ema ical P og amming 1, 366–375.
Bu ges C. (1998). A Tu o ial on Suppo Vec o Machines o Pa e n Recogni-
ion”. Da a Mining and Knowledge Disco e y 2, 121–167.
Ca izosa E. and Conde E. (2002). A F ac ional Model o Loca ing Semi-Desi able
Facili ies on Ne wo ks. Eu opean Jou nal o Ope a ional Resea ch 136, 67–80.
Ca izosa E., Conde E., Fe n´andez F.R. and Pue o J. (1995). Mul i-C i e ia
Analysis wi h Pa ial In o ma ion abou he Weigh ing Coe icien s. Eu opean
Jou nal o Ope a ional Resea ch 81, 291–301.
Ca izosa E. and Fliege J. (2002). Gene alized Goal P og amming: Polynomial
me hods and applica ions. Ma hema ical P og amming 93, 281–303.
Co es C. and Vapnik V. (1995). Suppo Vec o Ne wo ks. Machine Lea ning
20, 273–297.
C amme K. and Singe Y. (2001). P anking wi h Ranking. P oceedings o he
Fou een h Annual Con e ence on Neu al In o ma ion P ocessing Sys ems,
641–647.
C is ianini N. and Shawe-Taylo J. (2000). An In oduc ion o Suppo Vec o
Machines. Camb idge Uni e si y P ess.
F eund Y., Iye R., Schapi e R.E. and Singe Y. (1998). An E icien Boos ing Al-
go i hm o Combining P e e ences. P oceedings o he Fi een h In e na ional
Con e ence on Machine Lea ning, Madison, Wisconsin, USA, 170–178.
Fung G., Mangasa ian O.L. and Sha lik J. (2001). Knowledge-Based Suppo