Compu e s & Indus ial Enginee ing 172 (2022) 108611
A ailable online 30 Augus 2022
0360-8352/© 2022 The Au ho (s). Published by Else ie L d. This is an open access a icle unde he CC BY-NC-ND license (h p://c ea i ecommons.o g/licenses/by-
nc-nd/4.0/).
Con en s lis s a ailable a ScienceDi ec
Compu e s & Indus ial Enginee ing
jou nal homepage: www.else ie .com/loca e/caie
A ma hema ical p og amming app oach o SVM-based classi ica ion wi h
label noise✩
Víc o Blancoa,b,∗, Albe o Japónc,d, Jus o Pue o c,d
aIns i u e o Ma hema ics (IMAG), Uni e sidad de G anada, Spain
bDp . Quan i a i e Me hods o Economics & Business, Uni e sidad de G anada, Spain
cIns i u e o Ma hema ics (IMUS), Uni e sidad de Se illa, Spain
dDp . S a s & OR, Uni e sidad de Se illa, Spain
ARTICLE INFO
Keywo ds:
Supe ised classi ica ion
SVM
Mixed in ege non linea p og amming
Label noise
ABSTRACT
In his pape we p opose no el me hodologies o op imally cons uc Suppo Vec o Machine-based classi ie s
ha ake in o accoun ha label noise occu in he aining sample. We p opose di e en al e na i es based
on sol ing Mixed In ege Linea and Non Linea models by inco po a ing decisions on elabeling some o he
obse a ions in he aining da ase . The i s me hod inco po a es elabeling di ec ly in he SVM model while
a second amily o me hods combines clus e ing wi h classi ica ion a he same ime, gi ing ise o a model
ha applies simul aneously simila i y measu es and SVM. Ex ensi e compu a ional expe imen s a e epo ed
based on a ba e y o s anda d da ase s aken om UCI Machine Lea ning eposi o y, showing he e ec i eness
o he p oposed app oaches.
1. In oduc ion
The p ima y goal o supe ised classi ica ion is o ind pa e ns
om a aining sample o labeled da a in o de o p edic he labels
o ou -o -sample da a, in case he possible numbe o labels is ini e.
Among he mos ele an applica ions o classi ica ion me hods a e
hose ela ed wi h secu i y, as in spam il e ing o in usion de ec ion.
The main di e ence o hese applica ions wi h espec o o he uses o
classi ica ion app oaches is ha malicious ad e sa ies can adap i ely
manipula e hei da a o mislead he ou come o an au oma ic analysis.
Fo ins ance, spamme s o en modi y hei emails by ob usca ing wo ds
which ypically appea in known spam o by adding wo ds which a e
likely o appea in legi ima e emails. Also, as s a ed in Wee asinghe,
E ani, Alpcan, and Leckie (2019), when machine lea ning algo i hms
u ilized in sa e y–c i ical en i onmen s a e comp omised by ad e -
sa ies, i could e en esul in loss o human li es. No e ha , doub ing
on he eliabili y o he labels on he a ge a iable is usual when
ha ing suspicions abou he possibili y o an in en ional lip among
hese labels. Howe e , i is no by a he only case in which one
mus hink abou his possibili y. Nowadays, i is commonly said ha
✩The au ho s o his esea ch acknowledge inancial suppo by he Spanish Minis e io de Ciencia y Tecnologia, Agencia Es a al de In es igacion and Fondos
Eu opeos de Desa ollo Regional (FEDER) ia p ojec PID2020114594GB-C21. The au ho s also acknowledge pa ial suppo om p ojec s FEDER-US-1256951,
Jun a de Andalucía P18-FR-1422, CEI-3-FQM331, Ne mee Da a: Ayudas Fundación BBVA a equipos de in es igación cien í ica 2019. The i s au ho was
also suppo ed by p ojec s P18-FR-2369 (Jun a de Andalucía) and IMAG-Ma ia de Maez u g an CEX2020-001105-M /AEI /10.13039/501100011033. (Spanish
Minis e io de Ciencia y Tecnologia).
∗Co esponding au ho .
E-mail add esses: [email p o ec ed] (V. Blanco), [email p o ec ed] (A. Japón), [email p o ec ed] (J. Pue o).
da a scien is s spend a la ge pe cen age o hei ime dealing wi h
collec ing and p ep ocessing da a, meanwhile he emainde is used o
model and ex ac in o ma ion om da abases. Mis akes con e ed in o
w ong label assignmen s a e e y likely o happen. Fo ins ance, da a
can be w ongly iden i ied a he e y beginning o he da a collec ion
phase, o code e o s can occu when p ep ocessing a da abase, leading
o a da ase wi h label noise. Then, one has o, no only de i e a
classi ica ion ule om a aining sample, able o adequa ely classi y
ou -o -sample da a, bu also o ake in o accoun ha some o he labels
migh be inco ec .
The goal o his pape is o analyze he powe o using ma hema ical
p og amming ools o he label noise de ec ion when cons uc ing a
Suppo Vec o Machine (SVM) classi ie . As poin ed ou in Ganapa hi-
aju and Picone (2000), among all he a ailable op imiza ion-based
classi ie s, SVMs pa icula ly su e he e ec o noisy labels because
hei eliance on suppo ec o s and he ea u e in e dependence as-
sump ion. This is he eason o analyze only his baseline model he e.
Al hough i would ha e been possible o ex end he analysis o o he
me hodologies ( o ins ance, o classi ica ion ees), i would equi e
h ps://doi.o g/10.1016/j.cie.2022.108611
Recei ed 7 Sep embe 2021; Recei ed in e ised o m 10 May 2022; Accep ed 23 Augus 2022
Compu e s & Indus ial Enginee ing 172 (2022) 108611
2
V. Blanco e al.
o include ex a ma hema ical p og amming o mula ions as well as
u he conside a ions on he p oposed models which would loose he
ocus o ou con ibu ion and would dec ease he eadabili y o he
pape . Needless o say, ha a simila app oach can be ollowed wi h
o he baseline me hods bu his is beyond he scope o his pape .
The in e es ed eade is e e ed o Blanco, Japón, and Pue o (2020b)
o u he de ails o his me hodology applied o he cons uc ion o
classi ica ion ees.
Rela ed wo ks
Analyzing he ulne abili ies o classi ie s and hei obus ness
agains a acks, o be e unde s and how hei secu i y may be im-
p o ed, has ecen ly ecei ed g owing in e es om he scien i ic
communi y. Bi and Zhang p opose in Bi and Zhang (2005) obus
al e na i es when he ea u es o he aining sample obse a ions a e
co up ed. On he o he hand, Biggio e al. p o ide in Biggio, Nelson,
and Lasko (2011) an algo i hmic app oach o handle ad e sa ial
modi ica ions o he labels, in case he labels a e independen ly lipped
wi h he same p obabili y, by co ec ing he ke nel ma ix. Acco ding
o Nalepa and Kawulok (2018), h ee main g oups o app oaches
o dealing wi h noisy da ase s ha e been al eady p oposed in he
li e a u e: (1) Design o algo i hms which il e noisy and/o misla-
beled ec o s om he inpu da a (as in Ekamba am e al.,2016;
Ghoggali & Melgani,2009;Han & Chang,2013); (2) Cons uc ion o
obus classi ie s agains noisy labeling (see Duan and Wu (2018) and
Na a ajan, Dhillon, Ra ikuma , and Tewa i (2017)); and (3) Use o
noise models in pa allel wi h he ob en ion o he classi ie , which
a e inally coupled o a highe -quali y classi ica ion (see Be simas,
Dunn, Pawlowski, and Zhuo (2019), Ganapa hi aju and Picone (2000),
Wee asinghe e al. (2019), Xiao e al. (2015) and Xu, C amme , and
Schuu mans (2006)). Fu he de ails on he di e en app oaches o deal
wi h da ase s con aining mislabeled obse a ions can be ound in he
ecen su ey in F énay and Ve leysen (2013).
Mos ecen me hodologies o deal wi h noisy da ase s a e sequen-
ial. Thus, loosing he op imal pe o mance ob ained by one sho
me hods based on ma hema ical p og amming app oaches. Fo in-
s ance, in he ecen me hod p esen ed in No hcu , Jiang, and Chuang
(2021), based in he so-called Suppo Vec o Machine wi h Con i-
den Lea ning (SVM-CL) app oach, he au ho s p opose a p obabilis ic
me hod in h ee sequen ial phases: (1) es ima e he ansi ion ma ix o
class-condi ional label noise, (2) il e ou noisy examples, and (3) ain
he da ase once noisy da a a e emo ed ia Co-Teaching. Analogously,
in de F ança and Coelho (2015) i is p oposed a no el me hod in which
i s he aining sample is biclus e ed (see e.g., Cheng & Chu ch,2000)
ying o cap u e co ela ion be ween ea u es and obse a ions, nex
he aining sample is modi ied acco ding o he biclus e s, and hen
he classi ica ion is pe o med on he modi ied da ase . Fu he mo e,
he e a e some globally op imal me hods ha ha e been p oposed in he
li e a u e. In pa icula , in Be simas e al. (2019), he au ho s p esen
di e en obus adap a ions o classical classi ica ion me hods o deal
wi h unce ain y in labels and/o ea u es in he aining sample.
In con as o hose me hods ha ha e been al eady p oposed o
deal wi h classi ica ion and noisy labels, ou app oach simul aneously
cons uc a SVM-based classi ie and e-labels obse a ions, leading
o an op imal me hod. In addi ion, his app oach allows one o ge
sepa a ing hype planes ha would ha e been impossible o ob ain
h oughou s anda d SVM and ha epo be e esul s o many
di e en p oblems.
Al hough he me hod p oposed in Be simas e al. (2019) also
op imally cons uc s he classi ie unde he p esence o noisy labels,
i is hough o be obus agains he wo se possible si ua ion. On
he con a y, ou me hod builds he classi ie always on he con e-
nience o inding good classi ie s and no o be p o ec ed agains he
wo s possible lip o labels which esul s in be e classi ie s in mos
scena ios.
Mo ing away om he main ocus o ou pape , one can also ind in
he li e a u e di e en echniques o handle da a wi h noisy labels, as
o ins ance, deep-lea ning classi ica ion models (see e.g., Chen, Liao,
Chen, and Zhang (2019), Liu, Niles-Weed, Raza ian and Fe nandez-
G anda (2020), Tanaka, Ikami, Yamasaki, and Aizawa (2018) and Yu
e al. (2019)) o Classi ica ion T ees (Blanco e al.,2020b).
Ou con ibu ion
In his pape , we p opose a no el ma hema ical p og amming based
me hodology o cons uc an op imal classi ica ion ule by means o
an ad hoc adap a ion o a Suppo Vec o Machine (SVM) classi ie
ha inco po a es he de ec ion and co ec ion o label noise in he
da ase . Suppo Vec o Machine (SVM) is a widely-used me hodology
in supe ised bina y classi ica ion, i s ly p oposed in Co es and Vap-
nik (1995). Gi en a numbe o obse a ions wi h hei co esponding
labels, he SVM echnique consis s, in i s simples o m, o inding
an hype plane in he ea u e space so ha each class belongs o a
di e en hal -space maximizing he sepa a ion be ween classes (in a
aining sample) and minimizing some measu e o he misclassi ying
e o s. This p oblem can be cas wi hin he class o con ex op imiza ion
and i s dual has e y good p ope ies ha allow one o ex end he
me hodology o cons uc also nonlinea classi ie s. Mos o he SVM
li e a u e concen a es on bina y classi ica ion whe e se e al ex en-
sions a e a ailable. One can use di e en measu es o he sepa a ion
be ween classes (Blanco, Pue o and Rod íguez-Chía,2020;Ikeda &
Mu a a,2005a,2005b), agg ega ion s a egies (Maldonado, Me igó,
& Mi anda,2018), selec impo an ea u es (Labbé, Ma ínez-Me ino,
& Rod íguez-Chía,2018), apply egula iza ion s a egies (López, Mal-
donado, & Ca asco,2018;Peng, Xu, Kong, & Chen,2016), use win
(non pa allel) sepa a o s (Peng & Chen,2018), ex ensions o mul iclass
classi ica ion (Blanco, Japón, & Pue o,2020a;Liu, Ma ín-Ba agán, &
P ie o,2021), one-class classi ica ion (Kang, Kim, & Cho,2019;Shin,
Eom, & Kim,2005) and con ol cha s pa e n ecogni ion (Ünlü,2021),
inco po a ion o ma gin dis ibu ions (Liu, Chu, Gong and Peng,2020),
o ex ensions o he hype plane loca ion p oblem o o he supe ised
lea ning p oblems (Blanco, Japón, Ponce, & Pue o,2021;Blanco,
Pue o, & Salme ón,2018), e c.
One o he main easons o he success o SVM ools in classi i-
ca ion, may be ha one can p ojec he o iginal da a on o a highe
dimensional space whe e he sepa a ion o he classes can be mo e
adequa ely pe o med, and s ill wi h he same compu a ional e o
ha was equi ed in he o iginal p oblem. This p ope y is he so-
called ke nel ick, and e y likely his is one o he easons ha has
mo i a ed he success ul use o his ool in a wide ange o applica ions
(see e.g., Bahlmann, Haasdonk, and Bu kha d (2002), Kašćelan, Kašće-
lan, and No o ić Bu ić (2016), Majid, Ali, Iqbal, and Kausa (2014),
Okwuashi and Ndehedehe (2020) and Radhimeenakshi (2016), among
many o he s).
The cons uc ion o SVM-based classi ie s ha simul aneously ela-
bel obse a ions has many ad an ages when dealing wi h label noise
da ase s, bu also when wo king on p oblems in which alse posi i es
and alse nega i es ha e di e en misclassi ying cos s. Also, in p ob-
lems wi h unbalanced classes (as o ins ance in da ase s on aud
wi h c edi ca d ansac ions in which a ound a 99.9% o he obse a-
ions a e no audulen ansac ions Fede al T ade Commission,2017;
Maldonado, B a o, López, & Pé ez,2017 o in he numbe o claims
in non-li e insu ances Bouche , Denui , & Guillen,2009). In Fig. 1
we illus a e his si ua ion. One can obse e in he le pic u e he
p ojec ion on he plane o a se o obse a ions labeled by audulen
( ed) and non audulen (g een) ansac ions. Linea sepa a o s seems
o be impossible o cons uc o his ins ance, bu also non linea
classi ie s will esul in o e i ing. Howe e , as shown in he igh
pic u e, i one allows a ew o he labels o be changed, one can ob ain
be e classi ie s. No e ha in his case, alse posi i es a e mo e cos ly
han alse nega i es (since asking o a li le mo e o in o ma ion ia
Compu e s & Indus ial Enginee ing 172 (2022) 108611
3
V. Blanco e al.
Fig. 1. O iginal da a (le ) and op imal hype plane sepa a ing e-labeled classes wi h ou me hod ( igh ).
ex message on he phone no mally sol es his ue nega i e cases). I
is also impo an o ema k ha his sepa a ing hype plane could no
ha e been ob ained h ough s anda d SVM since all he suppo ec o s
belong o he same class (g een poin s).
In his pape we p opose wo di e en app oaches. We p esen a
model in which e-labeling obse a ions depends on he e o s o he
SVM-based me hod i sel sea ching o a comp omise be ween he gain
ob ained in misclassi ica ion e o and ma gin and he penal y paid
o each change o labels. On he o he hand, we will also in oduce
wo models in which e-labeled obse a ions will come om simila i y
measu es on he da a. Ou me hod is dis ibu ion- ee so ha i does no
assume any dis ibu ion on he da ase and he de ec ion o mislabeled
obse a ions and he cons uc ion o he classi ie is op imal based on
sol ing an add-hoc ma hema ical p og am.
To assess he alidi y o hese me hods we ha e pe o med a ba e y
o compu a ional expe imen s on 7 di e en eal da ase s. Fo hese
da ase s we ha e epea ed he expe imen s o 5 di e en scena ios, by
andomly lipping a 0%, 20%, 30%, 40% o 50% o he labels in he
o iginal da a. When compa ing ou me hod wi h espec o classical
SVM, and wi h SVM-CL om No hcu e al. (2021), we can see ha
ou s ge s be e esul s on noisy label da ase s.
Summa izing, he main con ibu ions o his wo k a e he ollowing:
•We p o ide di e en ma hema ical p og amming models o con-
s uc classi ica ion ules om a aining sample by deciding,
simul aneously, hose obse a ions wi h label noise.
•The ma hema ical p og amming o mula ions a e based on adap -
ing adequa ely di e en Suppo Vec o Machine models o in-
eg a e hem he possibili y o elabeling obse a ions wi h wo
di e en amilies o app oaches: One based on elabeling by
means o minimizing misclassi ica ion e o s and o he based on
di e en unsupe ised lea ning ools.
•The p oposed app oaches do no assume any dis ibu ion on he
da ase and he de ec ion o mislabeled obse a ions and he con-
s uc ion o he classi ie is op imal based on sol ing an add-hoc
op imiza ion p og am.
•The esul s o es ing ou algo i hms on di e en eal-wo ld
da ase s indica e ha ou p oposals a e mo e obus unde a acks
han he classical SVM classi ie bu also han he ecen SVM-
CL (No hcu e al.,2021) app oach which is speci ically aylo ed
o his end.
The es o he pape is o ganized as ollows. In Sec ion 2we se up
and desc ibe he elemen s o he p oblem o be conside ed. A e wa d,
in Sec ion 3we in oduce he di e en o mula ions o ou models, o
end up in Sec ion 4p esen ing ou compu a ional expe imen s. Finally,
we inish his a icle in Sec ion 5wi h some conclusions and an ou line
o ou u u e wo k.
2. P elimina ies
In his sec ion we in oduce he p oblem unde s udy and se he
no a ion used h ough his pape .
Gi en a aining sample {(𝑥1, 𝑦1),…,(𝑥𝑛, 𝑦𝑛)}⊆R𝑝×{+1,−1}, he
goal o linea SVM (see e.g., Co es and Vapnik (1995) and Mangasa ian
(1999)) is o ob ain a hype plane sepa a ing he da a (𝑥∈R𝑝)in o hei
wo di e en classes (𝑦∈{+1,−1}). Among all possible hype planes
ha can ob ain such a sepa a ion be ween he classes, SVM looks
o he one wi h maximum ma gin (maximum dis ance om classes
o he sepa a ing hype plane) while minimizing he misclassi ica ion
e o s. Le us deno e by a hype plane in R𝑝in he o m =
{𝑧∈R𝑝∶𝜔𝑡𝑧+𝜔0= 0} o some 𝜔∈R𝑝and 𝜔0∈R( he ec o 𝑣𝑡
is he esul o he anspose ope a o applied o he ec o 𝑣∈R𝑝).
This hype plane will induce a subdi ision o he da a space R𝑝in o
h ee egions: he +1 (posi i e) hal -space +={𝑧∶𝜔𝑡𝑧+𝜔0>1},
he −1 (nega i e) hal -space −={𝑧∶𝜔𝑡𝑧+𝜔0<−1}and he
s ip ={𝑧∶ −1 ≤𝜔𝑡𝑧+𝜔0≤1}. In he SVM model, posi i e-class
obse a ions (𝑦= +1) will be o ced o lie on he posi i e hal -space,
and he same cons ain will be imposed o he nega i e-class (𝑦= −1)
obse a ions on he nega i e hal -space. When hese cons ain s a e
iola ed o an obse a ion, a penaliza ion e o is accoun ed o in
he op imiza ion p oblem. The sepa a ion (ma gin) be ween classes
is compu ed as he wid h o he s ip . As men ioned be o e, he
SVM sepa a ing hype plane will be ob ained om an equilib ium o
maximizing he sepa a ion be ween classes and minimizing hese pe-
naliza ion e o s. Deno ing by 𝑒𝑖∈R+ he misclassi ica ion e o o
obse a ion 𝑖, and by 𝐶 he cons an o penaliza ion o hese e o s, he
SVM can be o mula ed as he ollowing Non Linea P oblem (NLP):
min 1
2‖𝜔‖2
2+𝐶
𝑛
∑
𝑖=1
𝑒𝑖
s. . 𝑦𝑖(𝜔𝑡𝑥𝑖+𝜔0)≥1 − 𝑒𝑖,∀𝑖= 1,…, 𝑛
𝜔∈R𝑝, 𝜔0∈R,
𝑒𝑖∈R+,∀𝑖= 1,…, 𝑛.
In Fig. 2 we can see a se o poin s belonging o wo di e en ,
blue and g een, classes (le pic u e) and i s SVM op imal solu ion o
a gi en pa ame e 𝐶( igh pic u e). The black line is he sepa a ing
hype plane while he o he wo pa allel lines a e delimi ing he s ip, ,
be ween classes. The poin s ha lie on hese pa allel lines, he bounda y
o he s ip, a e he so called suppo ec o s, and hey e i y ha
|𝜔𝑡𝑥𝑖+𝜔0|= 1. Finally, we ep esen in ed colo he magni ude o
he e o s induced by ma gin iola ions.
I we u he analyze he abo e da ase , we can see ha he e a e
ou blue obse a ions a he e y igh o he da ase , and wo g een
obse a ions on he le ha ha e a s ong impac when building he
Compu e s & Indus ial Enginee ing 172 (2022) 108611
4
V. Blanco e al.
Fig. 2. O iginal se o poin s (le ) and op imal SVM solu ion on hese poin s ( igh ).
Fig. 3. No op imal solu ion on he SVM p oblem.
classi ie . These obse a ions do no allow one o cons uc a SVM
sepa a o o he da ase as he one we can see in Fig. 3, since ha would
lead o e y big misclassi ica ion e o s wi h a e y iny ma gin.
Mo eo e , he e a e ano he wo g een obse a ions, besides he
wo on he le , ha a e close o he blue cloud o poin s han o he
g een one. Hence, i we could conside ha hese ou g een poin s
and he ou blue ones on he igh we e w ongly labeled (because o
hei closeness o he es o poin s), we migh conside a sepa a ing
hype plane wi h a slope like he one p esen ed on he le o Fig. 4
as a be e classi ie . Howe e , his sepa a ing hype plane would be
impossible o ob ain wi h he SVM model since all he suppo ec o s
belong o he same class and o a oid huge misclassi ica ion e o s he
model would o bid such a slope.
Mo i a ed by he abo e kind o con igu a ions, we ha e s udied
di e en models in which a sepa a ing hype plane is ob ained no only
based on he o iginal labels bu also on he possibili y o elabeling
some o he o iginal obse a ions o he aining sample a a gi en
penal y cos . We say ha an obse a ion is elabeled i one o he
ollowing assump ions occu s:
𝑦𝑖= ±1 bu ou model conside s ha 𝑦𝑖= ∓1.
We will use he no a ion 𝑦𝑖 o ep esen he class ha he model
is conside ing o obse a ion 𝑖. Hence, an obse a ion is said o be
elabeled i 𝑦𝑖≠𝑦𝑖.
Following he example shown in Figs. 2 and 3, we can see on he
igh o Fig. 4 he solu ion o ou model, wi h a sepa a ing hype plane
wi h he desi ed slope. Conside ing he o iginal classes (blue and
g een), pu ple poin s ep esen he poin s ha he model conside s o
be blue (despi e o hei ac ual label), and o ange poin s ep esen he
poin s ha he model conside s o be g een. This sepa a ing hype plane
is op imal in ou p oblem, he model conside s ha suppo poin s be-
long o di e en classes (e en hough ha is no ue ega ding o he
o iginal alues) and no misclassi ica ion e o s appea in he solu ion
(which is also no ue o he o iginal labels). The unde lying idea in
hese models is ha based on he geome y o he p oblem, elabeling
some obse a ions can lead o mo e obus /accu a e classi ie s. These
classi ie s can be e y use ul when dealing wi h da ase s wi h ou lie s,
and also in da ase s in which some noise is known o be added o he
da a labels.
3. Ma hema ical p og amming models
In his sec ion we p esen he h ee ma hema ical op imiza ion
models ha we p opose o sol e he p oblem consis ing in building
a hype plane o bina y classi ica ion, and, simul aneously, elabeling
po en ial noisy obse a ions. In he i s model, elabeling labels on
he o iginal obse a ions will be based on he e o s wi h espec o
he sepa a ing hype plane. On he o he hand, besides conside ing he
e o s wi h espec o he sepa a ing hype plane, he o he wo models
will also ake in o accoun in o ma ion om da a based on he geom-
e y o he poin s h ough he k-means and he k-medians me hods.
Ne e heless, despi e he ac ha some obse a ions a e elabeled in
ou models, in o de o make p edic ions, we will main ain he s a e o
p edic ions on ou o sample da a which es ablishes ha obse a ions
ha lie on he posi i e hal -space o he sepa a ing hype plane will
be p edic ed as posi i e class obse a ions, meanwhile obse a ions
ha lie on he nega i e hal -space will be p edic ed as nega i e class
obse a ions.
Compu e s & Indus ial Enginee ing 172 (2022) 108611
5
V. Blanco e al.
Fig. 4. Op imal solu ion a e e-labeling.
3.1. Model 1: Re-label SVM
The i s model ha we p opose elies on a e y basic idea, obse a-
ions will be elabeled based on he e o wi h espec o he sepa a ing
hype plane, i.e., a penal y o each elabeling will be conside ed and
he model will de e mine whe he he cos compensa es he global
misclassi ica ion e o . Le 𝑦𝑖be he inal label o he obse a ion
𝑖(a e elabeling), o all 𝑖= 1,…, 𝑛. Hence, using he no a ion
in oduced be o e, he model can be syn he ically summa ized in he
ollowing way:
min 1
2‖𝜔‖2
2+𝐶1
𝑛
∑
𝑖=1
𝑒𝑖+ elabelingCos ( 𝑦)
s. . 𝑦𝑖(𝜔𝑡𝑥𝑖+𝜔0)≥1 − 𝑒𝑖,∀𝑖= 1,…, 𝑛
𝜔∈R𝑝, 𝜔0∈R,
𝑒𝑖∈R+,∀𝑖= 1,…, 𝑛,
𝑦𝑖∈ {−1,1},∀𝑖= 1,…, 𝑛.
The model abo e is a SVM model in which obse a ions can be ela-
beled, and hus, ins ead o conside ing 𝑦𝑖on he sepa abili y cons ain ,
he elabeled obse a ions 𝑦𝑖a e used. In wha ollows we desc ibe
how o inco po a e he elabeling o he cons ain s and he objec i e
unc ion. Obse e ha i no cos is assumed o elabeling, he model
will elabel mos o he obse a ions o ob ain a null misclassi ica ion
e o , esul ing in senseless classi ie s. Thus, we model his cos wi h
a penal y, so ha he model will y o main ain he o iginal labels on
da a and i will only elabel obse a ions when a s ong gain on he
ma gin o a s ong minimiza ion on he e o s is p oduced.
No e ha classical linea SVM-based me hodologies measu e he
misclassi ica ion e o o a gi en aining obse a ion (𝑥𝑖, 𝑦𝑖)by means
o he dis ance om 𝑥𝑖 o he co ec hal space (+o −) wi h espec
o i s label 𝑦𝑖. In con as , in his new model, since he obse a ion
may be con enien ly e-labeled, he misclassi ica ion e o , al hough
measu ed also as he dis ance om 𝑥𝑖 o one o he hal spaces +
o −, he e e ence hal space is de e mined by he ac ual label (𝑦𝑖)
p o ided by he model ins ead ha by he o iginal one. A he end,
misclassi ica ion e o s a e measu ed exac ly in he same way in bo h
models, bu in Re-label SVM he o iginals labels may be modi ied,
paying a penal y cos o elabeling, implying mo e lexibili y when
i ing he SVM-based sepa a ing hype planes.
In o de o de i e a sui able ma hema ical p og amming o mula-
ion o he p oblem, we conside he ollowing se o bina y a iables
o model elabeling:
𝜉𝑖={1, 𝑖𝑓 𝑦𝑖= −𝑦𝑖,
0,o he wise. o 𝑖= 1,…, 𝑛.
Wi h hese a iables, elabelingCos ( 𝑦) = 𝐶2∑𝑛
𝑖=1 𝜉𝑖, whe e 𝐶2is he
uni a y cos o elabeling. Also, o cons uc he classi ie , we conside
he ollowing auxilia y se o con inuous a iables:
𝛽𝑖𝑗 ={𝜔𝑗,i obse a ion 𝑖is elabeled,
0,o he wise.∈R o 𝑖= 1,…, 𝑛, o 𝑗= 0,…, 𝑝,
and by 𝛽𝑖= (𝛽𝑖1,…, 𝛽𝑖𝑝) ∈ R𝑝.
Obse e ha , wi h he abo e no a ion,
𝑦𝑖(𝜔𝑡𝑥𝑖+𝜔0) = 𝑦𝑖(𝜔𝑡𝑥𝑖+𝜔0)−2𝑦𝑖(𝛽𝑡
𝑖𝑥𝑖+𝛽𝑖0).
Based on he discussion abo e, ou p oblem can be o mula ed as
ollows:
min 1
2‖𝜔‖2
2+𝐶1
𝑛
∑
𝑖=1
𝑒𝑖+𝐶2
𝑛
∑
𝑖=1
𝜉𝑖(RE-SVM)
s. . 𝑦𝑖(𝜔𝑡𝑥𝑖+𝜔0)−2𝑦𝑖(𝛽𝑡
𝑖𝑥𝑖+𝛽𝑖0)≥1 − 𝑒𝑖,∀𝑖= 1,…, 𝑛, (1)
𝛽𝑖𝑗 =𝜉𝑖𝜔𝑗,∀𝑖= 1,…, 𝑛, 𝑗 = 0,…, 𝑝, (2)
𝜔∈R𝑝, 𝜔0∈R,(3)
𝛽𝑖∈R𝑝, 𝛽𝑖0∈R,∀𝑖= 1,…, 𝑛, (4)
𝑒𝑖∈R+, 𝜉𝑖∈{0,1},∀𝑖= 1,…, 𝑛. (5)
In he o mula ion abo e, cons ain s (1) and (2) allow one o model
he elabeled obse a ions whe eas (3) decla es ha he coe icien s o
he hype plane a e con inuous a iables. Cons ain (4) de ines a se o
a iables ha will be equal o he coe icien s o he hype plane when
an obse a ion is elabeled, and ze o o he wise. Wi h hese new coe i-
cien s, i an obse a ion is no elabeled, cons ain s (1) coincide wi h
hose o he classical SVM, ha oge he wi h he objec i e unc ion
and (5) allow one modeling he misclassi ica ion e o s as hinge losses,
i.e. 𝑒𝑖= max{0,1 − 𝑦𝑖(𝜔𝑡𝑥𝑖+𝜔0)} o all 𝑖= 1,…, 𝑛.
No e ha (RE-SVM) is a Mixed In ege Nonlinea P oblem due o i s
objec i e unc ion, because e en hough cons ain s (2) a e w i en in
a nonlinea way, hey can be linea ized as ollows:
𝜔𝑗−𝑀(1 − 𝜉𝑖)≤𝛽𝑖𝑗 ≤𝜔𝑗+𝑀(1 − 𝜉𝑖),∀𝑖= 1,…, 𝑛, 𝑗 = 0,…, 𝑝,
−𝑀𝜉𝑖≤𝛽𝑖𝑗 ≤𝑀𝜉𝑖,∀𝑖= 1,…, 𝑛, 𝑗 = 0,…, 𝑝,
o 𝑀 ≫ 0a big enough cons an . Obse e ha one can always
assume ha he coe icien s o he hype plane a e no malized and ha
‖(𝜔, 𝜔0)‖∞≤1, and hen, he alue o 𝑀can be ixed o one.
Wi h he abo e conside a ions, (RE-SVM) can be e o mula ed as
a Quad a ic Mixed In ege P og amming p oblem wi h linea con-
s ain s (MIQP), which can be sol ed by he a ailable o - he-shel
sol e s (Gu obi, CPLEX, XPRESS, ...), which use a non-linea b anch
and bound app oach (Gup a & Ra ind an,1985) whose con inuous
subp oblems a e e icien ly sol ed using in e io -poin algo i hms.
Rema k 3.1. In he same manne ha we o mula e he p oblem abo e
using a hinge-loss poin o iew o he misclassi ica ion e o s, i can
be easily adap ed o o he loss unc ions as he amp loss (Huang, Shi,
& Suykens,2014). This la e case esul s in he ollowing ma hema ical
p og amming model:
min 1
2‖𝜔‖2
2+𝐶(𝑛
∑
𝑖=1
𝑒𝑖+ 2
𝑛
∑
𝑖=1
𝜉𝑖)(RL-SVM)
s. . 𝑦𝑖(𝜔𝑡𝑥𝑖+𝜔0)≥1 − 𝑒𝑖−𝑀𝜉𝑖,∀𝑖= 1,…, 𝑛

Compu e s & Indus ial Enginee ing 172 (2022) 108611
6
V. Blanco e al.
0≤𝑒𝑖≤2,∀𝑖= 1,…, 𝑛
𝜉𝑖∈ {0,1},∀𝑖= 1,…, 𝑛
𝜔∈R𝑝, 𝜔0∈R.
He e, he obse a ions ha lie ou side he ma gin in he w ong side
o he sepa a ing hype plane a e equally penalized in he objec i e
unc ion ega dless o he misclassi ica ion dis ance.
3.2. Clus e -SVM models
The second amily o models ha we p opose o de ec ing label
noise in he da a a e based on using simila i y measu es on he ob-
se a ions. These models will be called Clus e -SVM me hods since hey
pe o m, simul aneously, wo asks: clus e ing and classi ica ion by
SVM. On he one hand, he clus e phase o hese me hods will induce
elabeling based on he e ogenei y o he in o ma ion, whe eas he SVM
phase compu es he classi ie a e elabeling. We p esen he e wo
di e en al e na i es o clus e ing da a in o wo g oups and i s linkage
o a classi ica ion sys em: he 2-median and he 2-mean p oblems.
The goal o hese me hods is o ind wo clus e s o a gi en se
o obse a ions, conside ing ha an obse a ion will belong o exac ly
one clus e . These clus e s a e buil by inding wo e e ence poin s
(cen oids o medians) ep esen ing each o he wo g oups de e mined
by he obse a ions close o hem, in a way ha he o e all sum o
dis ances om poin s o hei espec i e e e ence poin s is minimum.
We dis inguish wo models unde hese se ings by using wo di e en
dis ance measu es: he 𝓁1and he 𝓁2no ms.
Le us deno e by 𝐾+∈R𝑝and 𝐾−∈R𝑝 he wo (unknown) e e ence
poin s, and 𝑑𝑖= min{‖𝑥𝑖−𝐾+‖,‖𝑥𝑖−𝐾−‖}, he dis ance om he
obse a ion 𝑖 o i s closes e e ence poin s, o 𝑖= 1,…, 𝑛 (he e ‖⋅‖
will ep esen ei he he 𝓁1o he 𝓁2-no m). The ep esen a ion o such
a closes dis ance o he e e ence poin s will be inco po a ed o he
ma hema ical p og amming model using he ollowing se o bina y
a iables:
𝜃𝑖={1,i obse a ion 𝑖is assigned o clus e +,
0,i obse a ion 𝑖is assigned o clus e −, o 𝑖= 1,…, 𝑛.
These clus e s ep esen simila obse a ions and will help he SVM
me hodology, oge he wi h he elabeling, o ind mo e accu a e clas-
si ie s.
Combining he ideas p esen ed on RE-SVM wi h he clus e ing based
me hods, we can de i e a new amily o models, ha assign obse -
a ions o wo g oups based on he clus e s ob ained by minimizing
he o e all sum o he no m-based dis ances om he da a poin s o
hei co esponding e e ence poin s. Mo eo e , i also ies o sepa a e
as much as possible hese wo clus e s by means o a hype plane.
Each one o he clus e s is assigned o one o he di e en ia ed classes
in ou classi ica ion p oblem. Finally, his hype plane will induce a
subdi ision o he da a space in a way ha he decision ule o he
classi ica ion p oblem o ou -o -sample da a is he same ha is used
in s anda d SVM. We p esen below he MIP o mula ion o his
p oblem. Le 𝑀1, 𝑀2, 𝑀3≫0be big enough posi i e cons an s and
‖⋅‖ ep esen ing ei he he 𝓁1o he 𝓁2-no m.
min 1
2‖𝜔‖+𝐶1
𝑛
∑
𝑖=1
𝑒𝑖+𝐶2
𝑛
∑
𝑖=1
𝜉𝑖+𝐶3
𝑛
∑
𝑖=1
𝑑𝑖(Clus e -SVM)
s. . 𝑦𝑖(𝜔𝑡𝑥𝑖+𝜔0)≥−𝑀1𝜉𝑖,∀𝑖= 1,…, 𝑛, (6)
𝑑𝑖≥‖𝑥𝑖−𝐾+‖−𝑀2(1 − 𝜃𝑖),∀𝑖= 1,…, 𝑛, (7)
𝑑𝑖≥‖𝑥𝑖−𝐾−‖−𝑀2𝜃𝑖,∀𝑖= 1,…, 𝑛, (8)
𝜔𝑡𝑥𝑖+𝜔0≥1 − 𝑒𝑖−𝑀3(1 − 𝜃𝑖),∀𝑖= 1,…, 𝑛, (9)
𝜔𝑡𝑥𝑖+𝜔0≤−1 + 𝑒𝑖+𝑀3𝜃𝑖,∀𝑖= 1,…, 𝑛, (10)
𝜃𝑖, 𝜉𝑖∈ {0,1},∀𝑖= 1,…, 𝑛, (11)
𝑒𝑖, 𝑑𝑖∈R+,∀𝑖= 1,…, 𝑛, (12)
𝐾+, 𝐾−∈R𝑝,(13)
𝜔∈R𝑝, 𝜔0∈R.(14)
No e ha he cons an s 𝑀1, 𝑀2, 𝑀3in he o mula ion abo e mus be
chosen such ha 𝑀1>max𝑖=1,…,𝑛 {𝑦𝑖(∑𝑗=1,…,𝑑 𝑥𝑖𝑗 + 1)}(conside ing
w.l.o.g. ha he coe icien s a e aken so ha ‖(𝜔, 𝜔0)‖∞≤1), 𝑀2>
max{‖𝑥𝑖−𝑥𝑗‖∶𝑖, 𝑗 = 1,…, 𝑛}and 𝑀3>∑𝑗=1,…,𝑑 𝑥𝑖𝑗 +2+max{‖𝑥𝑖−𝑥𝑗‖2∶
𝑖, 𝑗 = 1,…, 𝑛}. Tigh ened alues o his cons an s could be calcu-
la ed using simila ideas han hose elabo a ed in Baldome o-Na anjo,
Ma ínez-Me ino, and Rod íguez-Chía (2020).
The objec i e unc ion o (Clus e -SVM) agg ega es he ollowing
ou elemen s o be simul aneously op imized:
- The ma gin (measu ed wi h he 𝓁1o 𝓁2no m) has o be maxi-
mized.
- The e o s o classi ica ion wi h espec o he sepa a ing hype -
plane ha e o be minimized.
- Relabeled obse a ions ha e o be penalized.
- Dis ances om obse a ions o hei e e ence poin s ha e o be
minimized.
The agg ega ion o hese ou e ms leads o de ine a hype plane wi h
a good ma gin, sepa a ing wo homogeneous clus e s wi h espec o
dis ances and classes. Cons ain (6) en o ces he posi i e ( esp. neg-
a i e) class obse a ions o be loca ed on he posi i e ( esp. nega i e)
hal -space o he sepa a ing hype plane when no elabeling is applied.
Each elabeled obse a ion is penalized by 𝐶2uni s, no allowing a
la ge numbe o elabeling unless i compensa es la ge misclassi ica ion
e o s o unless hey lead o a ma gin gain. This me hodology allows us
o keep he same decision ule o ou -o -sample da a as he one used in
s anda d SVM. Cons ain s (7) and (8) pe mi o de e mine he closes
cen oid o each obse a ion, whe eas cons ain s (9) and (10) en o ce
he misclassi ica ion e o s o be compu ed wi h espec o he clus e ,
i.e. he classi ica ion is pe o med wi h espec o he classes 𝜃𝑖 ha
ha e been c ea ed based on he simila i y o he obse a ions.
The abo e model esul s in wo di e en p oblems depending on he
no m-based dis ances applied.
2Median SVM Model This model esul s om (Clus e -SVM) using
he no m 𝓁1. I will be e e ed o as he 2-Median SVM model.
The p oblem u ns ou o be a mixed in ege linea p oblem and
can be sol ed using any o he o - he-shel MIP sol e s.
2Mean SVM Model This is he e sion o model (Clus e -SVM) using
he 𝓁2. Since we a e using a nonlinea no m, he 2-Means SVM
esul s in a Mixed In ege Nonlinea P og amming p oblem,
ha can be e o mula ed as a Mixed In ege Second O de
Cone Op imiza ion (MISOCO) p oblem. As o he MIP he e
a e nowadays a ailable o - he-shel comme cial op imiza ion
sol e s implemen ing ou ines o i s e icien solu ion.
Rema k 3.2 (2-𝓁𝜏Clus e SVM Model).One could also conside di e -
en 𝓁𝜏-no ms (𝜏≥1) o bo h he ma gin measu e and he clus e s
simila i y measu es. In his case, he p oblem becomes also a MINLP
p oblem, bu based on he esul s p o ided by Blanco, Ben Ali, and
Pue o (2014), i can also be e icien ly e o mula ed as a MISOCO
p oblem. These ype o p oblems can be sol ed by he a ailable o -
he-shel sol e s (Gu obi, CPLEX, XPRESS, ...), which use a b anch
and bound app oach (Gup a & Ra ind an,1985) whe e con inuous
p oblems in he nodes (Second O de Cone op imiza ion) a e e icien ly
sol ed using in e io -poin algo i hms.
4. Expe imen s
In his sec ion we epo he esul s o ou compu a ional ex-
pe ience. We ha e s udied se en eal da ase s om UCI Machine
Compu e s & Indus ial Enginee ing 172 (2022) 108611
7
V. Blanco e al.
Lea ning Reposi o y (see Biggio e al.,2011), all o hem a e bina y
classi ica ion p oblems ha come om di e en opics. The da ase s
used a e: S a log-Aus alian C edi App o al (Aus alian), B eas Cance
(B eas Cance ), S a log-Hea (Hea ), Pa kinson Da ase wi h epli-
ca ed acous ic ea u es (Pa kinson), QSAR biodeg ada ion (QSARbiodeg),
Ve eb al Column (Ve eb al) and Wholesale Cus ome s (Wholesale).
The dimensions (𝑛: numbe o obse a ions, 𝑝: numbe o ea u es) o
hese da ase s is epo ed in Table 1.
Fo each o hese da ase s we ha e pe o med i e di e en expe i-
men s. The goal in hese expe imen s is o make p edic ions as accu a e
as possible on ou o sample da a. The i s expe imen consis s on mak-
ing p edic ions by aining he models wi h he o iginal da a. On he
o he hand, in o de o ep esen a acks in he aining da a, we ha e
conside ed ou di e en scena ios in which a andom amoun o labels,
wi hin he se {20%,30%,40%,50%}, ha e been lipped o aining da a,
i.e., ou scena ios in which we ha e added some label-noise on aining
da a.
We ha e pe o med a 5- old c oss alida ion scheme. Thus, da a
ha e been spli in o 5 ain- es andom pa i ions. In each o hese olds
we ha e ained ou models and we ha e used he o he ou olds o
es ing. Mo eo e , we ha e epea ed his 5- old c oss alida ion 5 imes
o each da ase , in o de o a oid bene icial s a ing pa i ions, and
we epo he a e age esul s ob ained. Fo all he ins ances we ha e
ained ou h ee models and we ha e compa ed hem wi h s anda d
SVM and SVM-CL (No hcu e al.,2021). We ha e conside ed s anda d
SVM as benchma k since, despi e he good esul s p o ided by SVM-
CL o some expe imen s, s anda d SVM p o ided a be e pe o mance
on a e age among all he expe imen s (see Table 1 and Fig. 5). The
measu e used o e alua e he pe o mance o he models ha e been he
accu acy, in pe cen age, on ou o sample da a:
𝐴𝐶𝐶 =#Well Classi ied Tes Obse a ions
#Tes Obse a ions ⋅100
The pa ame e s ha appea in he di e en me hods ha we compa e
a e alida ed as usual, ha is, o each o he ins ances we pe o m a
g id sea ch on he cos pa ame e s and he bes esul ob ained in he
alida ion sample among hese pa ame e s is he one epo ed. Mo e
speci ically, he g ids used in he expe imen s a e he ollowing:
SVM: 𝐶∈{10𝑖∶𝑖= −5,…,5}.
RE-SVM: 𝐶1, 𝐶2∈{10𝑖∶𝑖= −5,…,5}.
2-medians-SVM: 𝐶1, 𝐶2∈{10𝑖∶𝑖= −5,…,5},𝐶3∈{10𝑖∶𝑖=
−3,…,0}.
2-means-SVM: 𝐶1, 𝐶2∈{10𝑖∶𝑖= −5,…,5},𝐶3∈{10𝑖∶𝑖= −3,
…,0}.
SVM-CL: De aul uning pa ame e s (see No hcu e al.,2021).
Obse e ha some app oaches equi ed mo e hype pa ame e s o cali-
b a e han o he s. Al hough i implies a clea compu a ional disad an-
age in he aining phase, i does no imply a bene i o one me hod
o e o he s in e ms o quali y o he ob ained classi ie since aining
and es a e e enly pe o med wi h all he models (one old o aining
and he emainde o alida ing).
The ma hema ical p og amming models we e coded in Py hon 3.6,
and sol ed using Gu obi 7.5.2 on a PC In el Co e i7-7700 p ocesso a
2.81 GHz and 16 GB o RAM. Due o he complexi y o he 2-means-
SVM, we ha e helped he sol e uploading an ini ial easible solu ion
ha was ob ained in he 2-medians-SVM p oblem. We ha e no sol ed
o op imali y all he ins ances, especially hose wi h he 2-means-SVM
in which he p oblem becomes nonlinea , and hence we ha e es ab-
lished a ime limi o 30 s o all he expe imen s. This aining ime
has su iced o ob ain a he good classi ie s. Indeed, as one can obse e
om he esul s ob ained, his ime limi is adequa e o cons uc obus
classi ie s unde noisy labels. No e ha no gua an ying he op imali y
o he solu ions o ou models does no necessa ily imply ha he
classi ie s a e no adequa e.
Table 1
Accu acy esul s o ou compu a ional expe imen s.
Da ase Me hod Pe cen age o lipped labels
0% 20% 30% 40% 50%
SVM-CL 84.55 82.10 71.12 58.93 49.68
Aus alian SVM 86.11 85.43 79.23 68.13 59.47
(690,14) RE-SVM 86.42 85.68 83.37 76.97 66.13
2-medians-SVM 86.08 85.84 84.67 78.95 69.54
2-means-SVM 85.97 85.74 82.65 77.14 67.70
SVM-CL 95.73 91.87 87.37 78.49 58.36
B eas Cance SVM 96.49 93.47 89.96 85.94 68.16
(683,9) RE-SVM 96.88 96.20 94.97 90.36 77.00
2-medians-SVM 96.63 95.31 94.46 91.10 87.31
2-means-SVM 96.96 95.93 95.39 93.11 90.01
SVM-CL 78.70 71.03 60.09 56.01 49.66
Hea SVM 82.23 76.86 69.68 63.79 56.90
(270,13) RE-SVM 82.84 78.38 73.16 68.86 61.25
2-medians-SVM 82.01 78.75 77.29 75.38 71.99
2-means-SVM 82.06 78.81 77.40 75.97 72.90
SVM-CL 78.18 65.56 59.47 55.58 49.29
Pa kinson SVM 81.66 74.74 70.17 62.28 57.82
(240,40) RE-SVM 82.43 77.64 73.22 67.29 62.97
2-medians-SVM 80.32 78.62 78.12 77.51 76.28
2-means-SVM 80.47 79.22 78.78 78.20 77.03
SVM-CL 81.62 78.86 74.07 56.78 46.78
QSARbiodeg SVM 82.12 78.07 74.09 63.38 48.97
(1055,40) RE-SVM 84.53 79.61 75.00 66.42 54.58
2-medians-SVM 84.08 78.79 74.32 67.87 67.02
2-means-SVM 83.61 78.55 74.42 67.86 66.81
SVM-CL 80.94 72.79 68.54 60.53 50.69
Ve eb al SVM 84.51 75.43 71.34 66.78 57.47
(310,6) RE-SVM 85.10 79.61 74.83 72.33 67.92
2-medians-SVM 85.31 82.62 80.80 78.30 76.31
2-means-SVM 86.28 84.32 81.77 79.91 76.76
SVM-CL 88.98 85.40 78.03 57.19 45.42
Wholesale SVM 90.08 85.30 79.74 72.23 57.73
(440,7) RE-SVM 90.39 88.77 85.97 80.12 69.07
2-medians-SVM 90.58 89.54 87.79 82.78 73.54
2-means-SVM 91.23 89.56 87.39 85.88 82.92
In Table 1 we epo he a e age accu acy esul s ob ained in all he
expe imen s o he di e en models and he di e en le els o label-
noise. In such a able we ha e used he yellow-g een colo o indica e
he esul s in which we a e a 3% − 5% be e han he benchma k, he
g een colo o indica e whe he we a e a 5% − 10% be e han he
benchma k, and he cyan colo o highligh he esul s in which we
a e a leas a 10% abo e he benchma k. Also, we show in Fig. 5 he
accu acy boxplo s o he 625 ins ances pe da ase (5 pa i ions ×5
scena ios ×5 olds ×5 models).
Rega ding o he esul s, se e al conclusions can be poin ed ou :
•Ou h ee models pe o m consis en ly be e han classical SVM
when he aining da ase is co up ed. Besides, he s onge he
pe cen age o lipped labels, he bigge he di e ence be ween ou
models’ esul s and SVM’s esul s. In Fig. 5 one can check how
SVM model has lowe ails and wide boxes han RE-SVM.
•2-medians-SVM and 2-means-SVM pe o m be e han RE-SVM
o hea y a acks (40%−50% o lipped obse a ions). In con as ,
he clus e -based models equi e mo e ime o be ained han
RE-SVM, bo h because he p oblems a e ha de o sol e (apa
om elabeling, he dis ances o he cen oids and he assign-
men s obse a ions- o-cen oids a e modeled) and he numbe o
pa ame e s ha mus be uned. In Fig. 5 one can easily check ha
RE-SVM has wide boxes han 2-medians-SVM and 2-means-SVM,
which a e explained by he beha io o hese models agains he
a acks.
•Ou models ha e a be e pe o mance han he es o app oaches
e en o he o iginal da ase s in which no labels a e lipped. This
Compu e s & Indus ial Enginee ing 172 (2022) 108611
8
V. Blanco e al.
Fig. 5. Accu acy Boxplo s o he ob ained accu acies.
is due o he lexibili y o e ed by me hodologies, because some
o he obse a ions a e allowed o be elabeled looking o a
be e classi ie . The o iginal da ase s may con ain ou lie s ha
con amina e he sample and so hey de e io a e he classi ie . This
si ua ion is au oma ically de ec ed and ixed by ou me hods, by
adequa ely elabeling obse a ions.
•Ou me hods ou pe o m SVM-CL, which is a specialized me hod,
designed o de ec noisy labels. The a ionale unde hese esul s
is ha SVM-CL seems o w ongly iden i y he igh dis ibu ions
o he da a. These mis akes p opaga e o he cons uc ion o he
classi ie since i is buil on some incomple e da a. This ac also
esul s in wo se accu acies han s anda d SVM ha wo ks wi h
he en i e da ase wi hou paying a en ion o he exis ence o
ou lie s.
O e all, as one may expec and i is con i med in ou compu a ional
expe imen s, i is be e o cons uc he classi ie wi hou iden i ying
inco ec ly he noise labels (as SVM does) han using inadequa e lips
o build he classi ie (as SVM-CL seems o do in he es ed da ase s).
Ob iously, he esul s in he pape also show ha i is a he ad an a-
geous he co ec iden i ica ion o he w ong labels since i imp o es
signi ican ly he classi ica ion a es.
5. Conclusions
This pape p esen s a me hodology o cons uc a classi ica ion ule
ha a he same ime inco po a es he de ec ion o label noise in he
da ase s. Ou me hodology combines he powe o SVM and he ea u es
o clus e ing analysis o simul aneously iden i y w ong labels o build
a sepa a ing hype plane maximizing he ma gin, minimizing he mis-
classi ica ion e o s and penalizing elabeling. The a ionale is simple:
obse a ions iden i ied as w ongly labeled will be elabeled only i he
gain in ma gin o he dec ease in misclassi ica ion e o compensa e he
lipping. In spi e o i s heo e ical simplici y we show he excep ional
pe o mance o ou me hodology in a numbe o da abases aken om
he UCI eposi o y.
These models a e implemen ed using ma hema ical p og amming
o mula ions wi h some in ege a iables (MIP). In all cases, hey gi e
ise o models ha a e simple and ha enjoy he quali y o being
sol able by nowadays o - he-shel comme cial sol e s (Gu obi, CPLEX,
XPRESS...)
Ou indings a e no only o heo e ical in e es . I s p ac ical pe -
o mance when applied o da abases is ema kable. In all es ed cases,
ou me hods a e supe io o he conside ed benchma k ha in ou
case is s anda d SVM. Thus, hey a e di ec ly applicable o da ase s
in which lipped labels a e suspec ed, esul ing in obus classi ie s o
noisy labels.
Fu he esea ch on he opic includes he ex ension o ou models
o deal wi h mul iclass ins ances by modi ying he elabel - a iables o
iden i y he new (non-bina y) labels. The s a egy should be ca e ully
chosen using a mul iclass SVM-based app oach (as One e sus One, One
e sus All o any o he uni ied ools). This ex ension is no i ial and
equi es a deepe analysis.
O he lines o esea ch ha would ex end ou me hods a e he ap-
plica ion o al e na i e clus e ing s a egies, as hose based on o de ed
median objec i e unc ions o he win SVM me hodology. Also, he use
o ke nel ools in ou app oaches, in o de o be able o cons uc non
linea classi ie s has o be in es iga ed.
CRediT au ho ship con ibu ion s a emen
Víc o Blanco: Concep ualiza ion, Da a cu a ion, Fo mal analy-
sis, Funding acquisi ion, In es iga ion, Me hodology, P ojec admin-
is a ion, Resou ces, So wa e, Supe ision, Valida ion, Visualiza ion,
Roles/W i ing – o iginal d a , W i ing – e iew & edi ing. Albe o
Japón: Concep ualiza ion, Da a cu a ion, Fo mal analysis, Funding
acquisi ion, In es iga ion, Me hodology, P ojec adminis a ion, Re-
sou ces, So wa e, Supe ision, Valida ion, Visualiza ion, Roles/W i ing
– o iginal d a , W i ing – e iew & edi ing. Jus o Pue o: Concep-
ualiza ion, Da a cu a ion, Fo mal analysis, Funding acquisi ion, In-
es iga ion, Me hodology, P ojec adminis a ion, Resou ces, So wa e,
Supe ision, Valida ion, Visualiza ion, Roles/W i ing – o iginal d a ,
W i ing – e iew & edi ing.
Re e ences
Bahlmann, C., Haasdonk, B., & Bu kha d , H. (2002). On-line handw i ing ecogni ion
wi h suppo ec o machines a ke nel app oach. In IWFHR’02,P oceedings o he
eigh h in e na ional wo kshop on on ie s in handw i ing ecogni ion (pp. 49–54).
Baldome o-Na anjo, M., Ma ínez-Me ino, L. I., & Rod íguez-Chía, A. M. (2020). Tigh -
ening big Ms in in ege p og amming o mula ions o suppo ec o machines
wi h amp loss. Eu opean Jou nal o Ope a ional Resea ch,286(1), 84–100.
Be simas, D., Dunn, J., Pawlowski, C., & Zhuo, Y. D. (2019). Robus classi ica ion.
INFORMS Jou nal on Op imiza ion,1(1), 2–34.
Compu e s & Indus ial Enginee ing 172 (2022) 108611
9
V. Blanco e al.
Bi, J., & Zhang, T. (2005). Suppo ec o classi ica ion wi h inpu da a unce ain y.
In Ad ances in neu al in o ma ion p ocessing sys ems (pp. 161–168).
Biggio, B., Nelson, B., & Lasko , P. (2011). Suppo ec o machines unde ad e sa ial
label noise. In Asian con e ence on machine lea ning (pp. 97–112).
Blanco, V., Ben Ali, S., & Pue o, J. (2014). Re isi ing se e al p oblems and algo i hms
in con inuous loca ion wi h 𝑙𝑝no ms. Compu a ional Op imiza ion and Applica ions,
58(3), 563–595.
Blanco, V., Japón, A., Ponce, D., & Pue o, J. (2021). Compu e s & Ope a ions Resea ch,
128, A icle 105124.
Blanco, V., Japón, A., & Pue o, J. (2020a). Op imal a angemen s o hype planes o
mul iclass classi ica ion. Ad ances in Da a Analysis and Classi ica ion,14, 175–199.
Blanco, V., Japón, A., & Pue o, J. (2020b). Robus op imal classi ica ion ees unde
noisy labels. Ad ances in Da a Analysis and Classi ica ion,16, 155–179.
Blanco, V., Pue o, J., & Rod íguez-Chía, A. M. (2020). On 𝓁𝑝-suppo ec o machines
and mul idimensional ke nels. Jou nal o Machine Lea ning Resea ch,21.
Blanco, V., Pue o, J., & Salme ón, R. (2018). Loca ing hype planes o i ing se o
poin s: A gene al amewo k. Compu e s & Ope a ions Resea ch,95, 172–193.
Bouche , J.-P., Denui , M., & Guillen, M. (2009). Numbe o acciden s o numbe o
claims? An app oach wi h ze o-in la ed Poisson models o panel da a. The Jou nal
o Risk and Insu ance,76(4), 821–846.
Chen, P., Liao, B. B., Chen, G., & Zhang, S. (2019). Unde s anding and u ilizing deep
neu al ne wo ks ained wi h noisy labels. In In e na ional con e ence on machine
lea ning (pp. 1062–1070). PMLR.
Cheng, Y., & Chu ch, G. M. (2000). Biclus e ing o exp ession da a. In P oceedings o
he 8 h in . con . on in elligen sys ems o molecula biology (pp. 93–103).
Co es, C., & Vapnik, V. (1995). Suppo - ec o ne wo ks. Machine Lea ning,20(3),
273–297.
de F ança, F. O., & Coelho, A. L. (2015). A biclus e ing app oach o classi ica ion wi h
mislabeled da a. Expe Sys ems wi h Applica ions,42(12), 5065–5075.
Duan, Y., & Wu, O. (2018). Lea ning wi h auxilia y less-noisy labels. IEEE T ansac ions
on Neu al Ne wo ks and Lea ning Sys ems,28(7), 1716–1721.
Ekamba am, R., Fe ila ye , S., Sh e e, M., K ame , K., Hall, L. O., Goldgo , D. B., e
al. (2016). Ac i e cleaning o label noise. Pa e n Recogni ion,51, 463–480.
Fede al T ade Commission (2017). Consume sen inel ne wo k da a book o
Janua y-Decembe 2016.
F énay, B., & Ve leysen, M. (2013). Classi ica ion in he p esence o label noise: a
su ey. IEEE T ansac ions on Neu al Ne wo ks and Lea ning Sys ems,25(5), 845–869.
Ganapa hi aju, A., & Picone, J. (2000). Suppo ec o machines o au oma ic da a
cleanup. In Six h in e na ional con e ence on spoken language p ocessing.
Ghoggali, N., & Melgani, F. (2009). Au oma ic g ound- u h alida ion wi h gene ic
algo i hms o mul ispec al image classi ica ion. IEEE T ansac ions on Geoscience
and Remo e Sensing,47(7), 2172–2181.
Gup a, O. K., & Ra ind an, A. (1985). B anch and bound expe imen s in con ex
nonlinea in ege p og amming. Managemen Science,31(12), 1533–1546.
Han, X., & Chang, X. (2013). An in elligen noise educ ion me hod o chao ic signals
based on gene ic algo i hms and li ing wa ele ans o ms. In o ma ion Sciences,
218, 103–118.
Huang, X. L., Shi, L., & Suykens, J. A. K. (2014). Ramp loss linea p og amming suppo
ec o machine. Jou nal o Machine Lea ning Resea ch,15, 2185–2211.
Ikeda, K., & Mu a a, N. (2005a). E ec s o no ms on lea ning p ope ies o suppo
ec o machines. In ICASSP (5) (pp. 241–244).
Ikeda, K., & Mu a a, N. (2005b). Geome ical p ope ies o nu suppo ec o machines
wi h di e en no ms. Neu al Compu a ion,17(11), 2508–2529.
Kang, S., Kim, D., & Cho, S. (2019). App oxima e aining o one-class suppo ec o
machines using expec ed ma gin. Compu e s & Indus ial Enginee ing,130, 772–778.
Kašćelan, V., Kašćelan, L., & No o ić Bu ić, M. (2016). A nonpa ame ic da a mining
app oach o isk p edic ion in ca insu ance: a case s udy om he mon eneg in
ma ke . Economic Resea ch-Ekonomska Is aži anja,29(1), 545–558.
Labbé, M., Ma ínez-Me ino, L. I., & Rod íguez-Chía, A. M. (2018). Mixed in ege
linea p og amming o ea u e selec ion in suppo ec o machine. Disc e e Applied
Ma hema ics,h p://dx.doi.o g/10.1016/j.dam.2018.10.025.
Liu, L., Chu, M., Gong, R., & Peng, Y. (2020). Nonpa allel suppo ec o machine wi h
la ge ma gin dis ibu ion o pa e n classi ica ion. Pa e n Recogni ion,106, A icle
107374.
Liu, L., Ma ín-Ba agán, B., & P ie o, F. J. (2021). A p ojec ion mul i-objec i e SVM
me hod o mul i-class classi ica ion. Compu e s & Indus ial Enginee ing,158, A icle
107425.
Liu, S., Niles-Weed, J., Raza ian, N., & Fe nandez-G anda, C. (2020). Ea ly-lea ning
egula iza ion p e en s memo iza ion o noisy labels. a Xi p ep in a Xi :2007.
00151.
López, J., Maldonado, S., & Ca asco, M. (2018). Double egula iza ion me hods o
obus ea u e selec ion and SVM classi ica ion ia DC p og amming. In o ma ion
Sciences,429, 377–389.
Majid, A., Ali, S., Iqbal, M., & Kausa , N. (2014). P edic ion o human b eas and colon
cance s om imbalanced da a using nea es neighbo and suppo ec o machines.
Compu e Me hods and P og ams in Biomedicine,113(3), 792–808.
Maldonado, S., B a o, C., López, J., & Pé ez, J. (2017). In eg a ed amewo k o p o i -
based ea u e selec ion and SVM classi ica ion in c edi sco ing. Decision Suppo
Sys ems,104, 113–121.
Maldonado, S., Me igó, J., & Mi anda, J. (2018). Rede ining suppo ec o machines
wi h he o de ed weigh ed a e age. Knowledge-Based Sys ems,148, 41–46.
Mangasa ian, O. L. (1999). A bi a y-no m sepa a ing plane. Ope a ions Resea ch Le e s,
24(1–2), 15–23.
Nalepa, J., & Kawulok, M. (2018). Selec ing aining se s o suppo ec o machines:
a e iew. A i icial In elligence Re iew, 1–44.
Na a ajan, N., Dhillon, I. S., Ra ikuma , P., & Tewa i, A. (2017). Cos -sensi i e lea ning
wi h noisy labels. Jou nal o Machine Lea ning Resea ch,18(1), 5666–5698.
No hcu , C. G., Jiang, L., & Chuang, I. L. (2021). Con iden lea ning: Es ima ing
unce ain y in da ase labels. Jou nal o A i icial In elligence,70, 1373–1411.
Okwuashi, O., & Ndehedehe, C. E. (2020). Deep suppo ec o machine o
hype spec al image classi ica ion. Pa e n Recogni ion, A icle 107298.
Peng, X., & Chen, D. (2018). PTSVRs: Reg ession models ia p ojec ion win suppo
ec o machine. In o ma ion Sciences,435, 1–14.
Peng, X., Xu, D., Kong, L., & Chen, D. (2016). L1-no m loss based win suppo ec o
machine o da a ecogni ion. In o ma ion Sciences,340–341, 86–103.
Radhimeenakshi, S. (2016). Classi ica ion and p edic ion o hea disease isk using
da a mining echniques o suppo ec o machine and a i icial neu al ne wo k.
In In e na ional con e ence o compu ing o sus ainable global de elopmen (INDIACom)
(pp. 3107–3111). IEEE.
Shin, H. J., Eom, D. H., & Kim, S. S. (2005). One-class suppo ec o machines—an
applica ion in machine aul de ec ion and classi ica ion. Compu e s & Indus ial
Enginee ing,48(2), 395–408.
Tanaka, D., Ikami, D., Yamasaki, T., & Aizawa, K. (2018). Join op imiza ion amewo k
o lea ning wi h noisy labels. In P oceedings o he IEEE con e ence on compu e ision
and pa e n ecogni ion (pp. 5552–5560).
Ünlü, R. (2021). Cos -o ien ed LSTM me hods o possible expansion o con ol cha ing
signals. Compu e s & Indus ial Enginee ing,154, A icle 107163.
Wee asinghe, S., E ani, S. M., Alpcan, T., & Leckie, C. (2019). Suppo ec o machines
esilien agains aining da a in eg i y a acks. Pa e n Recogni ion,96, 1–14.
Xiao, H., Biggio, B., Nelson, B., Xiao, H., Ecke , C., & Roli, F. (2015). Suppo ec o
machines unde ad e sa ial label con amina ion. Neu ocompu ing,160, 53–62.
Xu, L., C amme , K., & Schuu mans, D. (2006). Robus suppo ec o machine aining
ia con ex ou lie abla ion. In AAAI, Vol. 6 (pp. 536–542).
Yu, X., Han, B., Yao, J., Niu, G., Tsang, I., & Sugiyama, M. (2019). How does dis-
ag eemen help gene aliza ion agains label co up ion? In In e na ional con e ence
on machine lea ning (pp. 7164–7173). PMLR.