FACULDADE DE ENGENHARIA DA UNIVERSIDADE DO PORTO
Semi-au oma ic classi ica ion: using
ac i e lea ning o e icien class
co e age
Nuno Filipe Fonseca Vasconcelos Escudei o
P og ama Dou o al em Engenha ia In o má ica
Supe iso : P o . Dou o Alípio Má io Jo ge
Second Supe iso : P o . Dou o Rui Ca los Camacho
Oc obe , 2012
Semi-au oma ic classi ica ion: using ac i e lea ning o
e icien class co e age
Nuno Filipe Fonseca Vasconcelos Escudei o
P og ama Dou o al em Engenha ia In o má ica
Oc obe , 2012
Resumo
Alguns p oblemas de classi icação au omá ica, ais como a classi icação de ex o, exigem um
g ande es o ço pa a a e ique ação dos exemplos necessá ios pa a eina um classi icado apesa
da acilidade e baixo cus o en ol idos na ecolha de exemplos não e ique ados. Con a iamen e à
ap endizagem supe isionada, que exige que os exemplos do conjun o de eino sejam odos p e-
iamen e e ique ados, a ap endizagem a i a é um pa adigma em que os exemplos são e ique ados
em unção da sua u ilidade pa a o im em is a. Pa a além da seleção c i e iosa dos exemplos a
e ique a , a ap endizagem a i a é um p ocesso i e a i o que pode se in e ompido quando o alo
ac escen ado dos exemplos ainda não e ique ados ô baixo. De uma o ma ge al, a ap endizagem
a i a eque um es o ço de e ique agem in e io ao da ap endizagem supe isionada.
A maio ia das abo dagens co en es da ap endizagem a i a aplicadas a p oblemas de classi i-
cação assume a exis ência de um conjun o de exemplos p e iamen e e ique ados, cob indo odas
as classes de in e esse. O p ocesso de ap endizagem é inicializado a pa i des e conjun o. O es-
o ço necessá io pa a a e ique ação des es exemplos não é, de uma o ma ge al, con abilizado pa a
e ei os do cálculo do es o ço o al de e ique ação.
No en an o, a iden i icação de exemplos ep esen a i os de odas as classes pode exigi um
es o ço signi ica i o, em pa icula , no que e e e à iden i icação de exemplos ep esen a i os de
classes mino i á ias. Ac esce que, em alguns domínios, ais como a de eção de aude e o di-
agnós ico de doenças a as, po exemplo, es as classes mino i á ias podem se as mais c í icas.
Nes as ci cuns âncias, conduzi e a alia o p ocesso de ap endizagem com base exclusi amen e
em c i é ios de p ecisão, como é comum em p oblemas de classi icação, pode não se su icien e.
De ac o, dependendo do en iesamen o da dis ibuição das classes, um classi icado pode ap esen-
a uma axa de e o baixa mesmo desconhecendo po comple o as classes mino i á ias.
O a amen o adequado des es casos eque uma abo dagem di e en e que assegu e, pa a além
da p ecisão, ambém a capacidade de econhecimen o de odas as classes independen emen e da
sua dis ibuição. En endemos que é possí el desen ol e uma es a égia de ap endizagem a i a
que pe mi a cons ui classi icado es p ecisos, com conhecimen o de odas as classes, com um
es o ço de e ique ação (cus o) in e io ao das abo dagens a uais.
Nes a ese p opomos uma es a égia de ap endizagem a i a que inclui um c i é io de seleção
dos exemplos a e ique a e um c i é io de pa agem que in e ompe o p ocesso de ap endizagem
quando o alo ac escen ado dos exemplos disponí eis pa a e ique a é baixo. Es a es a égia
p omo e a e iciência do p ocesso de ap endizagem, ocando-se nos exemplos mais in o ma i os e
unicamen e enquan o o seu alo ac escen ado o jus i ique.
O c i é io de seleção p opos o, d-Con idence, ag ega a con iança do classi icado com a dis ân-
cia en e os exemplos não e ique ados e as classes conhecidas. É um c i é io que ende a seleciona
exemplos de classes desconhecidas, em que o classi icado enha con iança eduzida, que se lo-
calizam em egiões inexplo adas do espaço de exemplos, a uma g ande dis ância das classes con-
hecidas. O c i é io de pa agem p opos o, hcw, combina dois indicado es do alo ac escen ado do
i

ii
conjun o dos exemplos ainda não e ique ados: o g adien e de classi icação e um indicado da es a-
bilidade da dis ibuição da en opia das p e isões. O g adien e de classi icação o nece in o mação
sob e a di e ença nas p edições en e duas i e ações consecu i as. O indicado de es abilidade da
dis ibuição da en opia das p e isões o nece indicações sob e a igualdade das medianas dessas
dis ibuições en e duas i e ações consecu i as.
Espe a-se que es a es a égia pe mi a iden i ica exemplos de odas as classes, independen-
emen e da sua dis ibuição, sendo capaz de ge a classi icado es p ecisos com um es o ço de
e ique ação in e io ao das abo dagens a uais.
Os esul ados da a aliação e e uada mos am que o d-Con idence supe a ou as abo dagens na
iden i icação de exemplos cob indo odas as classes. Os ganhos são pa icula men e no ó ios em
p esença de dis ibuições en iesadas. Os classi icado es cons uídos com o d-Con idence ap esen-
am ambém ganhos ao ní el da p ecisão na maio ia dos casos. No en an o, em algumas si uações,
a edução do es o ço de e ique ação necessá io pa a cob i odas as classes é ob ida à cus a de uma
p ecisão mais baixa.
O c i é io de pa agem aqui p opos o ap esen a um desempenho supe io às es an es abo -
dagens analisadas. É um c i é io obus o que ge a indicações de pa agem de o ma consis en e
quando a u ilidade dos exemplos não e ique ados ainda disponí eis é baixa.
A es a égia de ap endizagem a i a p opos a nes a ese, como um odo, incluíndo o c i é io
de seleção e o c i é io de pa agem, ge a classi icado es p ecisos, capazes de econhece odas as
classes, a um cus o eduzido em compa ação com ou as abo dagens a uais.
Abs ac
In some classi ica ion asks, such as hose ela ed o he au oma ic building and main enance o
ex esou ces, i is expensi e o ob ain labeled ins ances o ain a classi ie al hough i is common
o ha e massi e amoun s o da a a ailable a low cos . Unlike supe ised lea ning, ha equi es a
ully p e-labeled aining se , ac i e lea ning allows asking an o acle o label only he mos in o -
ma i e ins ances gi en he speci ic pu pose o he lea ning ask and he a ailable da a. Mo eo e ,
ac i e lea ning is an i e a i e p ocess ha may be hal ed when he po en ial u ili y o he unlabeled
ins ances emaining in he wo king se is low. Ac i e lea ning gene ally equi es a lowe labeling
e o o build accu a e classi ie s han supe ised lea ning.
Howe e , common ac i e lea ning app oaches assume he a ailabili y o a p e-labeled se , co -
e ing all he a ge classes, o ini ialize he lea ning p ocess. The labeling e o equi ed o build
his ini ializa ion se is no gene ally conside ed when analyzing he pe o mance o he lea ning
p ocess. When in p esence o imbalanced class dis ibu ions, iden i ying labeled ins ances om
mino i y classes migh be e y demanding, equi ing ex ensi e labeling, i que ies a e andomly
selec ed. Ne e heless, hese mino i y classes a e he mos c i ical o ce ain classi ica ion asks,
such as, de ec ion o iscal aud and a e diseases diagnosis. In such ci cums ances, e alua ing
he pe o mance and building a classi ie based exclusi ely in accu acy migh no be app op ia e
since an accu a e classi ie migh s ill ail o iden i y mino i y classes – he c i ical ones – wi h a
li le impac in accu acy.
A no el app oach o ac i e lea ning is equi ed in o de o comply wi h hese cases. Besides
accu acy, i is also impo an o assu e ha he classi ie being buil is awa e o all a ge classes
i espec i ely o hei dis ibu ion. I is ou belie ha i is possible o de elop an ac i e lea ning
s a egy ha builds accu a e classi ie s being awa e o all he a ge classes a a educed labeling
e o – ha is, a low cos – when compa ed o cu en app oaches.
In his hesis we p opose a s a egy o ac i e lea ning ha comp ises an ac i e lea ning c i e-
ion o selec que ies and a s opping c i e ion o hal he lea ning p ocess when he u ili y o he
emaining unlabeled ins ances is low. D-Con idence, ou que y selec ion app oach, is based on
a que y selec ion c i e ion ha agg ega es he pos e io classi ie con idence and he dis ance be-
ween unlabeled ins ances and known classes. This c i e ion is biased owa ds ins ances belonging
o unknown classes – low con idence – ha a e loca ed in unexplo ed egions in he inpu space
– high dis ance o known classes. The s opping c i e ion in ou s a egy, hcw, is an ensemble o
classi ica ion g adien and s eady en opy mean, wo base indica o s o he u ili y o unlabeled
ins ances. Classi ica ion g adien p o ides e idence on he di e ences o he p edic ed labels
be ween wo consecu i e i e a ions o he lea ning p ocess. S eady en opy mean p o ides in o -
ma ion on he s abili y o he dis ibu ion o he en opy o p edic ions be ween wo consecu i e
i e a ions.
This s a egy is expec ed o iden i y exempla y ins ances om all he a ge classes, inde-
penden ly o hei equency, being able o ain an accu a e classi ie while equi ing a educed
labeling e o when compa ed o common ac i e lea ning app oaches.
iii
i
The main esul s om ou e alua ion show ha d-Con idence ou pe o ms s a e-o - he-a ap-
p oaches in he iden i ica ion o exempla y ins ances om all classes. The imp o emen s a e
mainly e iden in imbalanced da a. The accu acy o he classi ie s buil wi h d-Con idence im-
p o es o e o he app oaches in mos si ua ions. Howe e , in some cases, he imp o ed ep esen-
a i eness is ob ained a he cos o accu acy.
The hcw s opping c i e ion signi ican ly ou pe o ms o he s a e-o - he-a app oaches used o
e alua ion. I is a obus c i e ion, igge ing consis en s op signs when he u ili y o he emaining
unlabeled ins ances is low.
The d-Con idence s a egy as a whole – including bo h que y selec ion and s opping c i e ia –
gene a es accu a e classi ie s, being able o ecognize all a ge classes, wi h a educed cos when
compa ed o s a e-o - he-a app oaches.
Acknowledgemen s
The las bu no he leas . One o he i s hough s ha came in o my mind a ew yea s ago, when
I began my PhD, was how nice i mus be o ha e he esea ch concluded, he hesis w i en and,
inally, jus ha e o w i e he acknowledgmen s. By ha ime, I had no a clue on he amoun o
con ibu ions wi hou which I would ha e ne e eached his poin .
Now, ha I am, inally, eally w i ing he acknowledgmen s, I am expe iencing an in ense
mix u e o eelings. I am h illed o ha ing inished w i ing, I am nos algic because one impo an
pe iod in my li e is coming o an end and I am anxious wai ing o he ju y day. Fo all his, hese
las pages a e as impo an as he es (excep ha I am mo e elaxed since i will no be subjec o
e iew om my supe iso s no will i be subjec o discussion wi h my ju y).
My name is w i en in he on page o his hesis. Tha is a g ea esponsibili y. I am jus he
lucky one ep esen ing he e o s om many people who made his possible.
My deep hanks, my deep ecogni ion o e e a e due:
To Alípio Jo ge, my supe iso , o he oppo uni y, o all he ad ice, pa ience, uncondi ional
suppo and sha ing.
To Rui Camacho, my co-supe iso , o all he e o and a ailabili y o p omp ly answe o
any eques .
To P o esso Eugénio Oli ei a, he Di ec o o he Doc o al P og am in In o ma ics Enginee -
ing, o welcoming me and o being always a ailable o sol e any p oblem.
To he School o Enginee ing o he Poly echnic o Po o, ISEP, o g an ing he unds and he
wo king condi ions equi ed o suppo his hesis.
To he Labo a o y o A i icial In elligence and Decision Suppo , LIAAD-INESC Po o L.A.,
o hos ing me as a esea che and suppo ing his hesis.
To Fe nanda Mou a, and Emb apa, Emp esa B asilei a de Pesquisa Ag opecuá ia, in gene al
o o ganizing and suppo ing my s ay he e, in Oc obe 2008, and o he in i a ion o join he
TIENA esea ch p ojec .
To Sa abjo Anand and Tao Li, om he Wa wick Uni e si y, o suppo ing my s ay he e, in
June 2008, and o all ou deba es and sha ing.
To Robson Mo a, om he Ins i u o de Ciências Ma emá icas e de Compu ação o he Uni-
e si y o São Paulo, o he ui ul coope a ion and o being always a ailable o discuss and o
sha e.
To Zélia P io , om he Academic Se ices o he Facul y o Enginee ing o he Uni e si y o
Po o, o all he p ecious help wi h he bu eauc a ic hu dles.
To Paulo Fe ei a, my colleague, o he p o iden ial help when I was abou o despe a e wi h
L
A
T
EX.
To my wi e, o he cons an encou agemen , o making me belie e when hings look una ain-
able, o eaching me se ing p io i ies, o sus aining e e y hing despi e my absence du ing many
impo an momen s.
xii CONTENTS

Lis o Figu es
6.1 Unce ain y egion (shaded). n ep esen s labeled ins ances om class cnand x
ep esen s unlabeled ins ances. We assume ha he concep o lea n has h ee
dis inc classes, one o which has no ye been iden i ied . . . . . . . . . . . . . . 90
6.2 Fo equally con iden ins ances p e e hose ha a e a om p e iously explo ed
egionsinins ancespace .............................. 91
6.3 E ec o d-Con idence o class +1 wi h an SVM classi ie . We assume we ha e
labeled ins ances nea he poin (0,0)o he bi-dimensional inpu space. The de-
cision bounda y is he diagonal line om (−10,10) o (10,−10)......... 96
6.4 A i icialda ase s .................................. 102
6.5 Class dis ibu ions in ex co po a . . . . . . . . . . . . . . . . . . . . . . . . . 104
6.6 P og ession o ins ance space co e age as new que ies a e added. cs ands o
con idence; dc s ands o d-Con idence . . . . . . . . . . . . . . . . . . . . . . . 106
6.7 Ins ance space co e age on he I is da ase as new que ies a e added . . . . . . . 108
6.8 Known classes and gene aliza ion e o in abula da a (when using SVM as he
baseclassi ie ).................................... 114
6.9 E olu ion o he pe cen age o common selec ed que ies h oughou he lea ning
cycle. Each line ep esen s he pe cen age o common ins ances o a gi en pai
o s a egies (dc-c, dc- , c- ) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120
6.10 Known classes and gene aliza ion e o . . . . . . . . . . . . . . . . . . . . . . 121
6.11 Que ies equi ed o iden i y bunches o dis inc classes in NG da ase . . . . . . . 125
6.12 Que ies equi ed o iden i y bunches o dis inc classes in R52 da ase . . . . . . 125
6.13 A e age gain o d-Con idence o e i s baseline c i e ia o i s hi classes on R52.
Classes a e so ed by inc easing equency . . . . . . . . . . . . . . . . . . . . . 126
6.14 Numbe o classes o a gi en equency i s ound by each c i e ia on R52 . . . . 127
6.15 E olu ion o known classes and e o ( esul s om Mo a e al.) . . . . . . . . . . 134
6.16 Explo a ion-Exploi a ion ade-o . . . . . . . . . . . . . . . . . . . . . . . . . 137
7.1 To al cos sensi i i y o B/A, w. . . known classes . . . . . . . . . . . . . . . . . 162
7.2 Penal ycos space.................................. 164
7.3 Symbols ep esen ing s opping c i e ia . . . . . . . . . . . . . . . . . . . . . . . 164
7.4 Cos sensi i i y oB/A ............................... 165
7.5 Mean numbe o i e a ions, a e he i s s op has been igge ed, equi ed o ig-
ge he s op sign o he hi d and i h ime . . . . . . . . . . . . . . . . . . . . 168
xiii
xi LIST OF FIGURES
Lis o Tables
6.1 A i icial da ase s and hei p ope ies . . . . . . . . . . . . . . . . . . . . . . . 103
6.2 Class dis ibu ion in abula da ase s . . . . . . . . . . . . . . . . . . . . . . . . 103
6.3 Co e age (Co ), mean numbe o que ies o iden i y one ins ance om he un-
known class (LDC) and e o (E ) wi h an SVM classi ie on a i icial da a. Mean
co e age and e o a e compu ed o e all i e a ions in all c oss alida ion olds o
e e y a i icial da ase . s ands o a hes - i s , cs ands o con idence and dc
s ands o d-Con idence............................... 106
6.4 A i icial da ase s so ed by dec easing o de o a hes - i s co e age . . . . . . 110
6.5 Pe cen age o in e -clus e o o al a iance . . . . . . . . . . . . . . . . . . . . 111
6.6 Co ela ion be ween in e -clus e / o al a iance and co e age . . . . . . . . . . . 111
6.7 Mic o-a e aged numbe o known classes and e o . Means ha e been compu ed
o e all i e a ions om all c oss alida ion olds o each combina ion o da ase ,
classi ie and que y selec ion c i e ia . . . . . . . . . . . . . . . . . . . . . . . . 113
6.8 Mean numbe o que ies equi ed o i s hi unknown classes . . . . . . . . . . . 115
6.9 LDC o abula da ase s .............................. 116
6.10 A e age i s -hi o e unde - ep esen ed classes a he Poke da ase . . . . . . . 118
6.11 LDC unde di e en imbalance le els. SVM as base classi ie . Imbalance is he
a io o he equency o he mino i y classes o he es . . . . . . . . . . . . . . 119
6.12 Mic o-a e aged numbe o known classes and e o . Means ha e been compu ed
o e all i e a ions om all c oss alida ion olds o each combina ion o da ase ,
imbalance le el and que y selec ion c i e ia. Bold aced alues a e s a is ically
signi ican a 5% .................................. 120
6.13 Mic o-a e aged numbe o known classes and e o . Means ha e been compu ed
o e all i e a ions om all c oss alida ion olds o each combina ion o da ase ,
classi ie and que y selec ion c i e ia . . . . . . . . . . . . . . . . . . . . . . . . 122
6.14 Fi s -hi o he NG da ase . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
6.15 Fi s -hi o he R52 da ase . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123
6.16 Rela i e con as using Euclidean dis ance . . . . . . . . . . . . . . . . . . . . . 129
6.17 Da ase s used by Mo a e al. o e alua e ac i e lea ning c i e ia . . . . . . . . . . 131
6.18 Mean numbe o know classes h oughou he lea ning p ocess (Mo a e al.) . . . 132
6.19 Mean e o h oughou he lea ning p ocess (Mo a e al.) . . . . . . . . . . . . . 132
7.1 D awback o en opy as a s opping c i e ia . . . . . . . . . . . . . . . . . . . . . 146
7.2 Da ase s used o e alua e s opping c i e ia . . . . . . . . . . . . . . . . . . . . . 149
7.3 Class dis ibu ion skewness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150
7.4 Tuning p ocess o sek ............................... 151
7.5 S opping c i e ia pa ame e s . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151
7.6 Ideal i e a ion o s op que ying . . . . . . . . . . . . . . . . . . . . . . . . . . . 152
x
x i LIST OF TABLES
7.7 Numbe o i e a ions o s op . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153
7.8 Penal y i e a ions w. . . e o . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154
7.9 Numbe o da ase s whe e s opping occu s be o e/a e ideal w. . . e o . . . . . 155
7.10 Penal y i e a ions w. . . known classes . . . . . . . . . . . . . . . . . . . . . . . 155
7.11 Numbe o da ase s whe e s opping occu s be o e/a e ideal w. . . known classes 156
7.12 To al cos w. . . e o when A = B = 1 . . . . . . . . . . . . . . . . . . . . . . . 157
7.13 To al cos w. . . known classes when A = B = 1 . . . . . . . . . . . . . . . . . . 158
7.14 C i e ia ank o penal y cos w. . . e o . . . . . . . . . . . . . . . . . . . . . . . 158
7.15 P- alue o equal means o e o penal y cos w. . . hcw .............. 159
7.16 Pe cen age o ins ances in W ha a e que ied be o e s opping . . . . . . . . . . . 160
7.17 C i e ia ank o penal y cos w. . . known classes . . . . . . . . . . . . . . . . . 160
7.18 P- alue o equal medians o known classes penal y cos w. . . hcw ........ 161
7.19 P- alue o - es o equal means o penal y cos w. . . hcw ............ 162
7.20 S opping c i e ia op pe o me s . . . . . . . . . . . . . . . . . . . . . . . . . . 166
7.21 Ra io be ween a e age nega i e by a e age posi i e di e ences o ideal s op . . . 167
7.22 Que y u ili y as po en ial e o imp o emen . . . . . . . . . . . . . . . . . . . . 169
7.23 Que y u ili y as po en ial known classes imp o emen . . . . . . . . . . . . . . . 169
Lis o Algo i hms
2.1 Gene alALalgo i hm................................ 12
3.1 Unce ain y sampling (adap ed om (Lewis and Gale, 1994)) . . . . . . . . . . . 36
3.2 Rep esen a i e sampling (adap ed om (Xu e al., 2003)) . . . . . . . . . . . . . 42
3.3 P o o ype Based Ac i e Classi ica ion (adap ed om (Ceb on and Be hold, 2009)) 44
6.1 D-Con idencealgo i hm .............................. 92
x ii

x iii LIST OF ALGORITHMS
Abb e ia ions and Symbols
A Cos o que ying he o acle o one label
A2Agnos ic Ac i e lea ning
AL Ac i e lea ning
αSigni icance le el o s a is ical es s
B U ili y o one unlabeled ins ance in U, he alue o he imp o emen in he
pe o mance o he classi ie induced by adding a new que y o he aining
se . Oppo uni y cos o no que ying
balee BalancedEE
C Se o a ge classes
c Re e s o con idence in Tables and Figu es
C4.5 Algo i hm o gene a e decision ees
CART Algo i hm o gene a e decision ees
cg Classi ica ion g adien s opping c i e ion
CHAD Algo i hm o gene a e decision ees
CiSe o a ge classes known a i e a ion i,Ci⊆C
ckA speci ic a ge class, an elemen o C
ClassDis (xj,ck)Agg ega ion unc ion. Compu es dk
j, he dis ance be ween unlabeled ins ance
xjand all labeled ins ances belonging o class ck
con i(uj,ck)Pos e io con idence on class ckgi en uj
c a Va iance model s opping c i e ion
d-Con idence Re e s o bo h he ac i e lea ning c i e ion and he ac i e lea ning s a egy
p oposed in his hesis
dc Re e s o d-Con idence in Tables and Figu es
dcon i(xj,ck)Ma ginal pos e io d-Con idence o class ckgi en xj
dCon i(xj)D-Con idence o ins ance xja i e a ion i
dk
jDis ance be ween one unlabeled ins ance xjand all labeled ins ances belonging
o class ck
E O acle, domain expe p o iding labels on eques
e Re e s o e o in Tables and Figu es
ECOC E o Co ec ing Ou pu Code
EM Expec a ion Maximiza ion
Re e s o a hes - i s in Tables and Figu es
hkNumbe o que ies equi ed o iden i y he i s ins ance belonging o class ck;
i s -hi o ck
h Hypo hesis gene a ed by he lea ning algo i hm, a classi ie lea ned o C
HCAC Hie a chical Con idence-based Ac i e Clus e ing
hck Hyb id Classi ica ion g adien Kolmogo o -smi no s opping c i e ion
xix
xx ABBREVIATIONS AND SYMBOLS
hcw Hyb id Classi ica ion g adien Wilcoxon s opping c i e ion
HKLD His o y Kullback-Leible Di e gence
hs Hie a chical Sampling
HUS His o y Unce ain y Sampling
i Lea ning p ocess i e a ion index
IBL Ins ance Based Lea ning
ID3 Algo i hm o gene a e decision ees
IE In o ma ion Ex ac ion
IR In o ma ion Re ie al
ISC In insic S opping C i e ion
K Numbe o a ge classes, #C
kc Numbe o known classes; numbe o classes ha ha e ep esen a i e ins ances
in he labeled se , L
k Ke nel Fa hes Fi s
KNN K-Nea es -Neighbo s
KQBC Ke nel Que y By Commi ee
LLabeled se , se o labeled ins ances
L1Labeled se a i e a ion 1, se o p e-labeled ins ances used o ini ialize he
lea ning p ocess
LDC Label Disclosu e Complexi y
ldc Re e s o LDC in Tables and Figu es
Lk
iSe o labeled ins ances known a i e a ion i ha belong o class ck
maxc Max-con idence s opping c i e ion
MI Exploi a ion mode
mine Min-e o s opping c i e ion
MMC Maximal loss educ ion wi h Maximal Con idence
MR Explo a ion mode
NNumbe o ins ances in he wo king se , #W
N1Numbe o p e-labeled ins ances used o ini ialize he lea ning p ocess
NER Named En i y Recogni ion
NG Newsg oup da ase
nkNumbe o ins ances in he aining se ha belong o class ck
NNET Neu al Ne wo k
o u O e all unce ain y s opping c i e ion
PBAC P o o ype Based Ac i e Classi ica ion
POS Pa -O -Speech
QBC Que y By Commi ee
qiQue y selec ed a i e a ion i
R52 Reu e s-21578 da ase
RBF Radial Basis Func ion
RPART Decision ee base classi ie
sek S eady En opy Kolmogo o -smi no s opping c i e ion
sew S eady En opy Wilcoxon s opping c i e ion
simple Que y selec ion c i e ion ha selec s he que y lying in he SVM ma gin closes
o he di iding hype plane
SVM Suppo Vec o Machine
TF×IDF Te m F equency In e se Documen F equency weigh ing
UUnlabeled se , se o unlabeled ins ances
UCI UCI machine lea ning eposi o y
ABBREVIATIONS AND SYMBOLS xxi
V() Va iance
WWo king se , se o all ins ances a ailable o lea n
xjIns ance in W
yjT ue label o ins ance xj
ˆyjP edic ed label o ins ance xj
6In oduc ion
a necessa y s opping condi ion bu no a su icien one. The ensemble o he wo is expec ed o be
su icien .
Ou hypo heses we e in es iga ed h ough an empi ical esea ch me hodology.
1.4 Main esul s
The main esul s om ou expe imen al e alua ion show ha d-Con idence exhibi s a signi ican
po en ial o he ea ly co e age o inpu space. D-Con idence e ie es exempla y ins ances om all
he a ge classes a a lowe cos han i s baseline c i e ia and o he s a e-o - he-a AL app oaches.
This imp o emen , in gene al, has no nega i e impac on accu acy. In ac , in many cases, he e is
an imp o emen in accu acy. In some o he cases, he imp o emen in class co e age is made a
he cos o accu acy.
D-Con idence is cha ac e ized by a dynamic shi be ween explo a ion and exploi a ion ha
a ises om i s na u e and does no equi e any uning, ha is, no o e head cos . The comp o-
mise be ween explo a ion and exploi a ion is balanced by he geome ical p ope ies o he inpu
space i sel . This cha ac e is ic o d-Con idence gea s a as e co e age o he inpu space while
simul aneously gene a ing accu a e models.
Conce ning he s opping c i e ia, ou e alua ion indica es ha he hyb id c i e ia p oposed in
his hesis ou pe o m he o he s opping c i e ia unde e alua ion. The e is a clea dominance o
hyb id c i e ia, no ably hcw, ega ding bo h cos and p edic i e abili y.
1.5 Thesis s uc u e
The emaining o his hesis is o ganized in se en chap e s. Chap e s 2 and 3 e e o he s a e-
o - he-a o he AL ield. In Chap e 2 we e iew his ield o machine lea ning analyzing i s
e olu ion om i s incep ion in he 80s. Then, in Chap e 3 we desc ibe in mo e de ail wo aspec s
o AL ha a e undamen al o ou wo k – que y selec ion s a egies and s opping c i e ia.
Chap e 4 e iews he main echniques in ex classi ica ion. We e e o he p e-p ocessing
phase, e iewing he p elimina y aspec s equi ed o he au oma ic p ocessing o ex documen s.
These include ex p epa a ion and models o ex ep esen a ion. Nex , we e iew common ex
classi ica ion se ings, ex classi ie s and pe o mance indica o s.

1.5 Thesis s uc u e 7
Chap e 5 elabo a es a o mal desc ip ion o he p oblem s udied in his hesis, p o iding a
gene al se ing o p omo e discussion and u he de elopmen s.
Chap e s 6 and 7 a e co e o his hesis. They desc ibe in de ail ou main con ibu ions and he
e alua ion o d-Con idence and he s opping c i e ia. The eade is assumed o be amilia wi h
he o mal desc ip ion o d-Con idence p o ided in Chap e 5.
In Chap e 8 we e iew he main con ibu ions and desc ibe oppo uni ies o u he esea ch
a ising om ou wo k.
8In oduc ion
Chap e 2
Ac i e Lea ning Re ospec i e
Machine lea ning (Mi chell, 1997) is a scien i ic ield o a i icial in elligence. I co e s he e-
sea ch and de elopmen o models and compu e algo i hms based on pa e ns ex ac ed om
empi ical da a. In his hesis we add ess one o he majo a eas o machine lea ning: classi ica ion
p oblems.
In a classi ica ion p oblem, labels – he classes – a e assigned o ins ances. Class labels come
om a p ede ined se , p e iously es ablished by he use . The assignmen o classes o a gi en
ins ance is done by a classi ie , based on a classi ica ion model. The classi ie is in e ed by a
lea ning algo i hm om he empi ical da a. The models1a e cons uc ed om a subse o he
ins ance space – he aining se . Classi ica ion models a e hypo heses o he a ge concep ha
a e consis en wi h he obse ed aining ins ances – as pe cei ed by he lea ne gi en e idence on
he a ge concep . In he con ex o his hesis we assume ha ins ances a e desc ibed by a se o
ea u es.
2.1 Machine lea ning se ings
The e a e se e al machine lea ning se ings sui ed o classi ica ion each wi h i s own p os and
cons gi en he speci ic p oblem a hand.
1Ins ance based lea ning (IBL) is a speci ic lea ning se ing ha does no equi e he induc ion o a model. IBL jus
s o es he aining se ha , in classi ica ion p oblems, is somehow used o assign labels o ins ances.
9
10 Ac i e Lea ning Re ospec i e
Supe ised lea ning This is a se ing whe e he lea ne gene a es hypo heses mapping he inpu
ea u es – he se o ea u es desc ibing ins ances – o a p e-es ablished se o classes (Cunning-
ham P, 2008). Supe ised lea ning algo i hms equi e a se o p e-classi ied (p e-labeled) ins ances
om which he lea ne gene a es he hypo heses. The need o ha e a ully labeled aining se is a
majo d awback o such a se ing, especially when he cos o labeling is high.
Unsupe ised lea ning This se ing does no equi e any p e-labeling; lea ning is achie ed ex-
clusi ely om he inpu ea u es (Ghah amani, 2004). Unsupe ised algo i hms seek o ealize
wha is he unde lying s uc u e go e ning he inpu ea u es’ space. Unsupe ised lea ning gen-
e a es models elying on he mos salien pa e ns ound in he inpu ea u e space which may no
p ope ly map he a ge concep . Unsupe ised classi ica ion algo i hms (Ka akos e al., 2005;
Sona e al., 2006; Sigogne and Cons an , 2009) a e commonly based on clus e ing echniques
which, in he speci ic ield o ex ca ego iza ion, assume he clus e ing hypo hesis ( an Rijsbe -
gen, 1979) – documen s ha ing simila con en a e also ele an o he same opic. Unsupe ised
lea ning does no equi e any labeling bu use s ha e no chance o ailo clus e s o hei spe-
ci ic needs and he e is no gua an ee ha he induced clus e s will be aligned wi h he classes o
lea n. This lack o guidance owa ds use needs du ing he aining phase is a majo d awback o
unsupe ised algo i hms om he poin o iew o he wo k p esen ed in his hesis.
Semi-supe ised lea ning The lea ning se ings abo e ely exclusi ely on a ully labeled da ase
– in he case o supe ised lea ning – o on a comple ely unlabeled one – unsupe ised lea ning.
Combining bo h labeled and unlabeled da a o ake ad an age o his combina ion, and o le e age
he in o ma ion con ained in unlabeled da a, is he goal o semi-supe ised lea ning (Nigam e al.,
2000; Chapelle e al., 2006; Zhu, 2008; Zhu and Goldbe g, 2009). Semi-supe ised algo i hms
usually ely on a small se o labeled da a and a la ge se o unlabeled da a. A simple heu is ic
app oach o semi-supe ised lea ning consis s in a wo s ep lea ning p ocess. In he i s s ep a
classi ie is ained based on he labeled da a only. This classi ie is hen used o classi y unlabeled
da a. The ins ances whe e he cu en classi ie is mos con iden abou a e added o he labeled
se assuming he p edic ed labels a e co ec .
2.2 Ac i e lea ning 11
Ac i e lea ning In supe ised lea ning he aining se can be ob ained by some me hod, such
as andom sampling, wi hou any a bi a ion by he lea ning algo i hm, in which case we e e o
passi e lea ning, o by some speci ic sampling c i e ion unde con ol o he lea ning algo i hm,
biased acco ding o some desi able p ope ies o he aining se , in which case we e e o ac i e
lea ning. Ac i e lea ning (Angluin, 1988; Cohn e al., 1994; Roy and McCallum, 2001; Muslea
e al., 2006) is a pa icula o m o supe ised lea ning whe e ins ances o label a e selec ed by
he lea ne h ough some c i e ia aimed a educing he labeling complexi y (Hanneke, 2007).
Labeling complexi y is de ined as he numbe o label eques s ha a e necessa y and su icien o
lea n he a ge concep .
2.2 Ac i e lea ning
Se e al classi ica ion asks – o ins ance hose in ol ing uns uc u ed da a, such as, speech ecog-
ni ion, ex and Web pages (Se les, 2009) ca ego iza ion, images and music e ie al and il e ing
– equi e e icien classi ica ion algo i hms due o he high labeling cos , on one side, and he as
amoun o a ailable, bu unlabeled, da a, on he o he . E iciency in such ci cums ances e e s o a
ade-o solu ion be ween high accu acy and comp ehensi eness, on one hand, and low labeling
e o , on he o he . Ac i e lea ning (AL) is an app op ia e lea ning se ing o his scena io gi en
he chance o de elop lea ning s a egies aiming a a desi able ade-o .
In AL, he lea ne is allowed o ask an o acle ( ypically a human) o label ins ances – hese
eques s a e called que ies. The mos in o ma i e que ies, gi en he goals o he classi ica ion ask,
a e selec ed by he lea ning algo i hm unlike passi e lea ning whe e aining ins ances a e selec ed
a andom. AL can be pe o med in se e al dis inc se ings which will be co e ed in Chap e 3.
The co e idea in AL is o es ima e he alue o labeling unlabeled ins ances. The gene al lea ning
p ocess in Algo i hm 2.1 is he basis o AL classi ica ion.
Re e ing o Algo i hm 2.1, Wis he wo king se , a ep esen a i e sample o ins ances om
he p oblem space. Liis a subse o W. Membe s o Lia e he ins ances in Wwhose labels a e
known a i e a ion i. A i e a ion i,Uiis he (se ) di e ence be ween Wand Li,Ui=W Li, i.e.,
he se o unlabeled ins ances in he wo king se ; hi ep esen s he classi ie lea ned a i e a ion i;
qiis he que y selec ed by he ac i e lea ne a i e a ion i. A speci ic ins ance is ep esen ed by

12 Ac i e Lea ning Re ospec i e
Algo i hm 2.1 Gene al AL algo i hm
1: Inpu : W, se o unlabeled ins ances xj; q() que y u ili y unc ion
2: Ou pu : hi, lea ned classi ie
3:
4: Ini ialize L1,U1 om W
5: i=1
6: while s opping c i e ia does no hold do
7: hi=lea n(Li), gene a e classi ie hiusing cu en labeled se Li
8: Use hi o classi y ins ances in he cu en unlabeled se Ui
9: qi=a gmax
xj
q(xj),xj∈Ui, selec qi=xj∈Uimaximizing que y u ili y
10: Ask he o acle o he label o xj,yj
11: Li+1=Li∪<xj,yj>
12: Ui+1=Ui xj
13: i++
14: end while
15: e u n hi
<xj,yj>whe e xjis he se o desc ip i e ea u es and yjis i s ue class (label).
All AL app oaches analyze unlabeled ins ances and selec he mos use ul ones once labeled.
The gene al idea o AL is o es ima e he alue o labeling unlabeled ins ances, i.e., he alue o
que ies. Que y selec ion may be based ei he on a gene a i e s a egy (Angluin, 1988) o on a
disc imina i e s a egy (Li e al., 2010).
In a gene a i e s a egy – he que y cons uc ion pa adigm – que ies a e a i icially syn he-
sized (Angluin, 1988; Baum, 1991). Gene a i e s a egies a e sui able o he case whe e a i i-
cially syn hesized ins ances make sense o he o acle p o iding labels. This assump ion makes
gene a i e AL s a egies unsui ed o he gene ali y o uns uc u ed da a domains as is he case o
ex co po a.
Disc imina i e s a egies – he que y il e ing pa adigm – selec que ies om a gi en dis i-
bu ion. These s a egies a e sui able when he dis ibu ion o he a ailable da a migh be di e en
om he a ge dis ibu ion and also when a i icially syn hesized ins ances a e no meaning ul o
he o acle as is usual in ex ca ego iza ion elying on he bag-o -wo ds model (Ha is, 1954). Two
app oaches a e common unde he que y il e ing pa adigm: pool based ac i e lea ning (Lewis
and Gale, 1994; McCallum and Nigam, 1998) – whe e que ies a e selec ed om a s a ic pool o
da a – and s eam based ac i e lea ning (Zhu e al., 2007, 2010c; Chu e al., 2011) – p ocessing
da a s eams and deciding online whe he o no o que y each new incoming ins ance.
Applying AL echniques o classi ica ion in ol es a se o speci ic challenges ha add o he
2.3 A e ospec i e iew 13
common issues a ising in gene al classi ica ion p oblems. In gene al, au oma ic classi ica ion in-
ol es a numbe o dis inc asks, including he de ini ion o he main goal o he lea ning p ocess,
se ing he e alua ion p ocedu e, ga he ing aining and es se s, de ining he da a ep esen a ion
model, selec ing and uning he mos adequa e lea ne . Speci ic AL challenges include: e ie ing
an ini ial se o labeled ins ances, es ablishing he que y selec ion c i e ia, es ablishing he s op-
ping c i e ia, ag eeing on a comp omise be ween explo a ion – inding ep esen a i e samples in
he da ase ha a e use ul o label, ocusing on comple eness – and exploi a ion – sha pening he
classi ica ion bounda ies, ocusing on accu acy. Decisions on hese issues a e di ec ed by he goals
o he classi ica ion p oblem a hand. These aspec s o AL a e add essed in he ollowing sec ions.
2.3 A e ospec i e iew
Resea ch in AL became popula in ecen yea s. The massi e quan i y o digi al in o ma ion ha
has become widely a ailable du ing he las yea s igge ed i s popula i y. Ne e heless, he AL
pa adigm, applied o machine lea ning, has been in use o o e 30 yea s.
In 1984, Valian desc ibes machine lea ning – he p ocess o “knowledge acquisi ion in he
absence o explici p og amming” – as consis ing o (i) an in o ma ion ga he ing mechanism and
(ii) a p ocess o explo e he concep space ha can be lea ned in a easonable (polynomial) num-
be o s eps (Valian , 1984). Pe o mance and lea nabili y a e conce ns al eady pe cei ed om
his ema k on “ easonable” complexi y. I is wo hwhile no ing he co e ole assumed by he
in o ma ion ga he ing mechanism in machine lea ning, om i s incep ion. AL con ibu es o he
easibili y o he lea ning p ocess by educing he ex en o he inpu needed o lea n. In his wo k
om Valian , he lea ning pa adigm is ex ended o include que ies, in he cu en sense o he e m
in AL – he lea ne supplies a se o ea u e’s alues and asks o an ou pu ha is p o ided by an
o acle.
In he ollowing we will desc ibe he mos ele an landma ks o AL in he machine lea ning
ield.
14 Ac i e Lea ning Re ospec i e
2.3.1 Incep ion, 1980’s
The e m ac i e lea ning has been o iginally coined in he educa ional ield in 1991, as a co olla y
o he b oad discussion a ound ins uc ional pa adigms ha occu ed du ing he 80’s, e e ing
o he ins uc ional ac i i ies in ol ing s uden s in doing hings and hinking abou wha hey a e
doing (Bonwell and Eison, 1991). In he educa ional ield, AL has always been associa ed o
seeking new in o ma ion, o ganizing i in meaning ul ways and u he exploi ing i (Allen D.,
2005), he e y same conce ns o he machine lea ning ield.
Lea ning om que ies, 1981 A ew yea s ea lie , du ing he 80’s, he pa adigm had al eady
been applied o machine lea ning, al hough no explici ly agged as AL. In 1988, Dana An-
gluin (Angluin, 1988) p oposes a o mal amewo k o o ganize and s udy se e al ypes o que ies
and hei alue o machine lea ning asks. Six dis inc ypes o que ies we e es ablished: membe -
ship, equi alence, subse , supe se , disjoin ness, and exhaus i eness que ies. The answe o each
one o hese que ies, excep o he membe ship ype which e u ns a single Boolean (T ue/False),
is composed by a Boolean esul and a coun e example in case o a nega i e answe .
Be o e ha , a ew lea ning sys ems based on que ies had been p oposed. Fo ins ance, in 1981,
Shapi o (Shapi o, 1981) and, in 1986, Sammu e al. (Sammu and Bane ji, 1986) bo h p opose
gene a i e app oaches o lea n new concep s om p e ious knowledge. Howe e , Dana Angluin
did he i s o mal desc ip ion o he AL pa adigm in he machine lea ning ield.
Fa hes - i s , 1985 One o he baseline c i e ia in ou wo k, a hes - i s was in oduced in
1985 (Hochbaum and Shmoys, 1985) o ind an e icien sub-op imal solu ion o he k-cen e
p oblem2. In his app oach, an ini ial ins ance is selec ed a andom. F om he e on, we selec
he ins ance ha is a he apa om he p e iously e ched ins ances un il we ha e kins ances.
These kins ances – collec i ely known as he a hes - i s a e sal o he da a – a e se as clus e
cen e s. The emaining ins ances a e hen assigned o he closes cen e . The dis ance be ween
2The k-cen e p oblem is de ined as ollows (Miheliˇ
c and Robiˇ
c, 2005): Le G = (V, E) be a comple e undi ec ed
g aph wi h edge cos s sa is ying he iangle inequali y, and k be a posi i e in ege no g ea e han |V|. Fo any se
S⊆Vand e ex ∈V, de ine d( , S) o be he leng h o a sho es edge om o any e ex in S. The p oblem is o
ind such a se S⊆V, whe e |S|≤k, which minimizes max ∈Vd( ,S)
2.3 A e ospec i e iew 15
an ins ance and a se is he minimum dis ance be ween he ins ance a hand and each o he in-
s ances belonging o he se . Fa hes - i s a e sal may p o ide a se o seeds o build hie a chical
clus e ing wi h ce ain pe o mance gua an ees (Dasgup a and Long, 2005).
Lea nabili y, 1988 In 1998, Pi e al. ocus on lea nabili y issues, s a ing ha some concep s a e
no lea nable jus by ins ances when we ha e no p io knowledge on he base dis ibu ion (Pi and
Valian , 1988). This same p oblem is discussed by Eisenbe g and Ri es (Eisenbe g, 1991), ha se
a bound on he deg ee o which membe ship que ies (Angluin, 1988) may imp o e gene aliza ion
when he unde lying dis ibu ion is unknown. 1988 was also he yea o he seminal pape om
Dana Angluin (Angluin, 1988) se ing o he i s ime a o mal amewo k o AL in he ield o
machine lea ning.
In 1990, Kinzel e al. (Kinzel and Ruján, 1990) show e idence on he abili y o simple pe -
cep on lea ne s3 o s ongly enhance gene aliza ion by allowing he ne wo k i sel o selec he
aining examples.
In 1991, Baum (Baum, 1991) p oposes a hyb id algo i hm ha lea ns a bina y classi ie om
p e-labeled ins ances and a i icially syn hesized que ies. Two g oundwo k ins ances – one posi-
i e and one nega i e example – a e andomly selec ed om he p e-labeled se o s a wi h. Then,
a que y is gene a ed hal way be ween hose wo. This gene a ed ins ance is labeled by he o acle
and eplaces he p e ious g oundwo k ins ance wi h he same label. The p ocess i e a es educ-
ing he dis ance be ween he selec ed ins ances and he sepa a ing hype plane in each and e e y
i e a ion.
2.3.2 Rudimen s, ea ly 1990’s
Selec ing que ies based on he dis ance o labeled ins ances, a hes - i s , o on he pos e io s
gene a ed by he cu en classi ie , unce ain y sampling, a e, oge he wi h Que y By Commi ee,
among he main g oundwo k app oaches o AL. In he ea ly 90’s, AL is explici ly assumed as a
esea ch a ea in he machine lea ning ield.
3A pe cep on is a simple ype o neu al ne wo k, de eloped in la e 50’s and ea ly 60’s mainly by F ank Rosenbla ,
ha deploys a linea bina y classi ie .
22 Ac i e Lea ning Re ospec i e
on a single base classi ie , as is common, Ba am e al. (Ba am e al., 2004) p opose an app oach
ha elies on an ensemble o base classi ie s. The AL p ocess is go e ned by an algo i hm ha
combines hese base lea ne s by e alua ing hei indi idual pe o mance and dynamically swi ch-
ing o he bes pe o me a each i e a ion.
Ba ch mode e isi ed, ba ch di e si y, 2003 Ba ch mode AL is a lea ning app oach ha is
adequa e when he aining cos is high. Ano he mo i a ion o add mo e han one que y o he
aining se a each i e a ion is o a oid annoying he use wi h many consecu i e i e a ions o
a single que y ha migh ha e a negligible imp o emen in he in e ed classi ica ion model, no
eally obse able by he use (Chen e al., 2010). In ba ch mode, ins ead o e aining a each single
que y – he adi ional AL se ing, e aining is done a e ha ing que ied a ba ch o ins ances. This
app oach poses a new p oblem. The issue is ha di e si y wi hin he ba ch o ins ances o que y
is equi ed o a oid que ying edundan ins ances. This desi able di e si y is no assu ed by jus
selec ing he op mmos in o ma i e ins ances as seen by he cu en lea ne (Schohn and Cohn,
2000; Wa mu h e al., 2002). Speci ic ca e is needed o assu e ha all ba ch membe s add alue
on op o he es .
In 2003, B inke (B inke , 2003) p oposes a new ba ch mode app oach o AL ha inco po a es
a di e si y measu e while selec ing ba ch membe s. This app oach selec s he que ies lying close
o he decision bounda y ha ha e he la ges angles o p e iously selec ed candida es. B inke ’s
app oach ou pe o ms p e ious AL app oaches using SVM base classi ie s.
Hoi e al. (Hoi e al., 2006) sugges a ba ch mode app oach elying on he Fishe in o ma-
ion ma ix (Papa hanasiou, 1993) o educe edundancy among selec ed ins ances. Li e al. (Li
and Se hi, 2006) compu e di e si y wi hin selec ed ins ances om hei condi ional e o . Hoi e
al. (Hoi e al., 2009) p opose semi-supe ised SVM ba ch mode, a new ba ch mode app oach wi h
wo objec i es in mind: o inc ease he numbe o aining ins ances and o assu e hei di e si y
o imp o e SVM pe o mance. Semi-supe ised SVM ba ch mode i s lea ns a ke nel unc ion
om labeled and unlabeled da a. Then, his unc ion is used o iden i y he mos in o ma i e and
di e se ins ances o que y.
Ra e ca ego y de ec ion, 2004 Pelleg (Dan Pelleg, 2004) desc ibes a no el AL scena io ha
add esses a e y simila p oblem o ou own. Pelleg explo es AL wi h he pu pose o iden i ying

2.3 A e ospec i e iew 23
a e ca ego ies – expe imen s a e epo ed wi h a e ca ego ies ha ing as ew as 0.002% ins ances
in he da a pool – in a se ing whe e no labeled ins ances om hese classes a e p esen in he
ini ial aining se . Ou wo k is somehow mo e gene al han his one. We ocus on ga he ing
exempla y ins ances o all he classes o lea n – i espec i e o hei equency – in he absence
o any p e-labeled ins ances, a low labeling cos . The au ho s p opose an in e lea ing s a egy
based on a mix u e model o i he da a and elying on he deg ee o owne ship o each mix u e
componen s w. . . unlabeled ins ances. In each i e a ion, a ba ch o 50 ins ances is selec ed based
on ou selec ion c i e ia, one o which is he p oposed in e lea ing s a egy. No ca e o a oid
edundancy in he ba ch composi ion is sugges ed.
Hie a chical sampling, p oposed by Dasgup a e al. (Dasgup a and Hsu, 2008) in 2008, was
also applied o he de ec ion o a e ca ego ies. The au ho s epo signi ican gains in he numbe
o que ies ha a e equi ed o disco e a leas one ins ance om each class. This la e wo k
is also in line wi h ou own e o s o de ising a me hod capable o swi ly iden i y ins ances
om unknown classes. P elimina y esul s ha e been published by us also in 2008 in a wo kshop
pape (Escudei o and Jo ge, 2008).
Class p obabili y es ima es, 2004 The mos common use o AL is p obably in classi ica ion
p oblems, aiming a maximizing accu acy. In many si ua ions, howe e – o ins ance, when in
p esence o unequal misclassi ica ion cos s – compu ing class p obabili y es ima es is mo e use ul
han aiming a high accu acy. Class p obabili y es ima es a e used o e alua e he expec ed u ili y
o a se o al e na i es, assuming pa icula ele ance in decision making. A ew wo ks on he
applica ion o AL o class p obabili y es ima es show empi ical e idence on he imp o emen s
assu ed by ac i e selec ion o que ies. BOOTSTRAP-LV (Saa -Tsechansky and P o os , 2004)
equi es less labeled ins ances o p oduce accu a e class p obabili y es ima es when compa ed
o he adi ional unce ain y sampling s a egy (Lewis and Gale, 1994). Mel ille e al. (Mel ille
e al., 2005) imp o e o e he p e ious wo k by using he Jensen-Shannon di e gence as a measu e
o he u ili y o new que ies.
24 Ac i e Lea ning Re ospec i e
2.3.4 Explo ing new di ec ions, ea ly 2000’s
Applica ion o AL in s eam-based se ings and he scalabili y o QBC a e among he new di ec-
ions add essed by AL esea ch in he ea ly 2000’s. Theo e ical essays, ying o p o ide a sound
heo e ical g ound o AL, we e also a conce n.
Clus e ing app oaches, 2004 Clus e ing has also been conside ed o p o ide an ini ial s uc u e
o da a o o sugges aluable que ies.
In 2004, Basu e al. (Basu e al., 2004) used AL based on a hes - i s o p o ide labeled da a
in a semi-supe ised clus e ing se ing (Basu e al., 2002). They ac i ely acqui e a se o mus -
link and canno -link cons ain s o imp o e he clus e ing p ocess. Empi ical esul s o e UCI
da a (F ank and Asuncion, 2010) and ex co po a, show ha he p oposed AL s a egy imp o es
o e andom pai wise que ies.
In 2004, Nguyen e al. (Nguyen and Smeulde s, 2004) inco po a e clus e ing in o AL by lea n-
ing a classi ica ion model om he se o he clus e ep esen a i es, and hen p opaga e he clas-
si ica ion decision o he o he ins ances ia a local noise model. The p oposed model allows o
selec he mos ep esen a i e ins ances as well as o a oid epea edly labeling ins ances in he
same clus e .
Adami e al. (Adami e al., 2005) me ge clus e ing and o acle labeling o boo s ap a p ede-
ined hie a chy o classes. Al hough he o iginal clus e s p o ide some s uc u e o he inpu , his
app oach s ill demands o a high alida ion e o , especially when hese clus e s a e no aligned
wi h class labels.
Huang e al. (Huang e al., 2008) explo e he Wikipedia5as a backg ound knowledge base
o c ea e a concep -based ep esen a ion o a ex documen enabling he au oma ic g ouping o
documen s wi h simila hemes. The seman ic ela edness be ween Wikipedia concep s is used o
ind cons ain s o supe ised clus e ing using AL.
In 2008, Dasgup a e al. (Dasgup a and Hsu, 2008) p opose hie a chical sampling, a clus e -
based me hod ha consis en ly imp o es label complexi y o e supe ised lea ning by de ec ing
and exploi ing clus e s ha a e loosely aligned wi h class labels. Thei me hod s a s wi h a hie -
a chical clus e ing o he unlabeled pool. Then, andom samples om each node o a pa i ion o
5h p://en.wikipedia.o g, accessed on Oc obe 2012
2.3 A e ospec i e iew 25
he da a, gi en by a p uning o he ee, a e que ied. Thei labels a e used o compu e he pu i y
o each node in he pa i ion. Nodes wi h low le els o pu i y a e eplaced by hei child nodes.
This p ocess can be hal ed whene e equi ed, o ins ance when a gi en pu i y le el is achie ed
a each node. A each i e a ion, he sampling s a egy a o s less pu e nodes.
Hu e al. (Hu e al., 2009), mo i a ed by simila conce ns, p opose an AL schema, based
on g aph- heo e ic clus e ing algo i hms. Thei app oach aims o supp ess he lack o abili y o
common AL app oaches o que y ins ances ha belong o new classes, ha ha e no ye appea ed
in he aining se . This mo i a ion is common o ou own.
The AL se ing in gene al is conside ed o be an app op ia e se ing o lea ning om imbal-
anced da a (Kapoo e al., 2010a).
Xu e al. (Xu e al., 2003) p oposed ep esen a i e sampling in 2003. Rep esen a i e sampling
is an AL me hod ha applies k-means clus e ing o he unlabeled ins ances lying wi hin he SVM
ma gin and selec he clus e cen oids o labeling. Thei p oposal signi ican ly ou pe o ms SVM
AL - selec ing he unlabeled ins ance ha is close o he sepa a ing hype plane (Tong and Kolle ,
2002) – and andom sampling a he ini ial s ages o he lea ning p ocess. Howe e , a e a numbe
o i e a ions, in some cases, SVM AL ou pe o ms ep esen a i e sampling. Acco ding o he
au ho s, his poo pe o mance is p obably due o he poo clus e ing s uc u e o he unlabeled
ins ances wi hin he SVM ma gin when he ma gin is ge ing exhaus ed.
Donmez e al. (Donmez e al., 2007) no iced ha unce ain y based app oaches end o dis-
ag ee wi h densi y based app oaches when selec ing que ies o AL. Due o hei na u e, unce -
ain y based app oaches pe o m well when in p esence o a la ge labeled se and poo ly when
in p esence o ew labeled ins ances. The opposi e beha io is obse able in densi y based ap-
p oaches. Donmez e al. (Donmez e al., 2007) p opose a me hod, in 2007, ha mixes densi y and
unce ain y componen s o ake ad an age o hei bes pe o mance a each pa icula si ua ion.
Thei me hod dynamically upda es he selec ion s a egy pa ame e s based on he es ima ed u u e
esidual e o educ ion.
Scalable QBC, 2005 Gilad-Bach ach e al. (Gilad-bach ach e al., 2005) in oduce Ke nel Que y
By Commi ee, (KQBC), a no el QBC algo i hm ha is able o lea n la ge scale p oblems by using
26 Ac i e Lea ning Re ospec i e
AL. KQBC p ojec s he inpu ea u e space in o a low dimensional space o educe he cos o
que y selec ion. The au ho s epo ed imp o ed pe o mance o e adi ional QBC.
Ins ance dele ion, il e ing ou i ele an ins ances, 2005 The o me wo k o Lewis e al. on
unce ain y sampling (Lewis and Gale, 1994) was ex ended by Becke e al. (Becke and Osbo ne,
2005) in 2005. In his la e wo k, a wo-s age me hod is p oposed. In he i s s age he ins ances
ha canno be eliably selec ed using unce ain y sampling a e il e ed ou . A he second s age,
unce ain y sampling is applied o he emaining eliable ins ances o selec que ies. Empi ical
esul s suppo be e pe o mance o his me hod when compa ed o pu e unce ain y sampling.
A simila mo i a ion – il e ing ou i ele an ins ances ha will mos p obably gene a e was ed
que ies – is p esen in Mazzoni e al. (Mazzoni e al., 2006). They p opose ele ance bias ha
combines he que y selec ion c i e ia in use wi h he ou pu o a ele ance classi ie , ained in
pa allel, o a o ins ances ha a e likely o be bo h ele an and in o ma i e. Que ies a e anked by
he p oduc o he ou pu o he ac i e lea ne , no malized o [0,1], by he p obabili y o ele ance,
he ou pu o he ele ance classi ie . Th ee que y selec ion c i e ia ha e been e alua ed – simple
ma gin (Tong and Kolle , 2002), MaxMin ma gin (Tong and Kolle , 2002) and a ba ch mode
s a egy assu ing di e si y among he selec ed ins ances (B inke , 2003) – and compa ed o andom
que y selec ion. The au ho s de ine p obabilis ic AL, a a ian o he base que y selec ion c i e ia
ha so s unlabeled ins ances by he que y selec ion c i e ia and hen selec s a andom sample
among he op 10% ins ead o selec ing he op- anked que y. The a ionale o his p ocedu e
is based on he heu is ic na u e o he que y selec ion c i e ia in use ha does no assu e op imal
que y selec ion. Besides, he di e ences in he alue o he selec ion c i e ia among he op- anked
que ies migh be non-signi ican . Fo hese easons, he op- anked que y migh no be he op imal
one and a andom sample o he mos p obable candida es migh be aluable. Despi e he ac ha
he e is no jus i ica ion o he h eshold ha he au ho s use – 10% o he op- anked ins ances –
and ha his h eshold is independen o he da a and, pa icula ly, o he a iance o he u ili y o
hose 10% op- anked ins ances, imp o emen s in pe o mance a e obse ed when compa ed o
s ic base c i e ia.
S eam-based ac i e lea ning, 2005 We mus go back a ew yea s o e iew one o he o me
app oaches o s eam-based AL. In 1997, Helmbold e al. (Helmbold and Panizza, 1997) discussed
2.3 A e ospec i e iew 27
he ade-o be ween he cos o eques ing a que y and he cos o e o s in a s eam-based se ing
– e e ed by label e icien lea ning. Fu he app oaches o s eam-based, o online, AL include
ecen esea ch e o s like he wo k om Bianchi e al. in 2005 and 2006 (Cesa-bianchi e al.,
2005; Cesa-Bianchi e al., 2006) and mo e ecen wo k om Dasgup a e al. in 2009 (Dasgup a
e al., 2009) and Chu e al. in 2011 (Chu e al., 2011).
The dynamic na u e o da a s eams – inc easing da a olumes and e ol ing decision concep s
– poses new challenges o s eam-based AL. Be ween 2007 and 2010, Zhu e al. (Zhu e al., 2007,
2010c) in oduce a minimum- a iance p inciple o guide ins ance labeling om da a s eams based
on an ensemble o classi ie s. A weigh upda ing ule is de i ed o ensu e a p ope adjus men o
d i ing concep s in he da a s eam.
Theo e ical essays, 2005 In 2005, Dasgup a (Dasgup a, 2005) de ined heo e ical bounds show-
ing ha AL has exponen ially smalle label complexi y han supe ised lea ning unde some pa -
icula and es ic i e cons ain s. Kää iäinen ex ended his wo k by elaxing some o hose con-
s ain s (Kää iäinen, 2006). An impo an conclusion o his la e wo k is ha he gains o AL a e
much mo e e iden in he ini ial phase o he lea ning p ocess, a e which hese gains deg ade and
he speed o lea ning d ops o ha o passi e lea ning.
In 2006, Balcan e al. p opose Agnos ic Ac i e lea ning (Balcan e al., 2006), A2.A2achie es
an exponen ial imp o emen o e he usual label complexi y o supe ised lea ning in he p esence
o a bi a y o ms o noise. This model is u he s udied by Hanneke (Hanneke, 2007), in 2007,
who se s gene al bounds on label complexi y.
In 2007, Cas o e al (Cas o and Nowak, 2007) show heo e ically ha , in a classi ica ion ask,
AL ou pe o ms passi e lea ning achie ing a as e a e o classi ica ion e o decay i espec i e
o he beha io o he pos e io p obabili y in he icini y o he decision bounda y and o he
complexi y o he Bayes decision bounda y.
2.3.5 Mode n ac i e lea ning, la e 2000’s o ea ly 2010’s
Relaxing he base assump ions o AL se s he g ound o p oac i e lea ning, a gene aliza ion o
he o me . AL can be pa icula ly bene icial o applica ions depending on uns uc u ed, high-
dimensional da a, like ex and ideo. The comp omise be ween explo a ion and exploi a ion is

28 Ac i e Lea ning Re ospec i e
also being add essed.
Va iable labeling cos s, 2005 Cullo a e al. (Culo a and McCallum, 2005) in oduce a iable
labeling cos s applied o in o ma ion ex ac ion (IE) (Cowie and Lehne , 1996). They p opose a
new AL pa adigm which educes no only he numbe o ins ances o label bu also he di icul y in
labeling each one o hem. The p oposed s a egy p o ides a way o quan i y he numbe o ac ions
a use mus pe o m o label each aining example, dis inguishing be ween bounda y anno a ions
– bounda y o segmen a ion in IE is he ask pe o med o de ine he limi s o an en i y in a
sequence o ex – and classi ica ion anno a ions – classi ying in IE is he ask pe o med o assign
a class o an en i y in a p e-segmen ed ex . Bounda y anno a ions a e usually mo e demanding
han classi ica ion anno a ions.
SVM base classi ie s, 2006 Mos o he AL me hods elying on SVM as base classi ie s que y
o ins ances based on hei dis ance o he cu en sepa a ing hype plane. Mi a e al. (Mi a
e al., 2004) ex ended his common app oach by in oducing o SVM an adap i e con idence ac o
es ima ed om local in o ma ion using k-nea es -neighbo p inciples. Thei me hod, mo i a ed
by he s a is ical que y model o lea ning (Kea ns, 1998), selec s a ba ch o que ies acco ding o a
dis ibu ion ha is de e mined by he cu en sepa a ing hype plane and by his adap i e con idence
ac o , enabling mo e obus and e icien lea ning capabili ies.
Cesa-Bianchi e al. (Cesa-Bianchi e al., 2006) in oduced, in 2006, a label e icien me hod
o selec i e sampling o linea classi ie s ha eques s o he label o a gi en ins ance wi h a
p obabili y ha is a unc ion o i s dis ance o he di iding hype plane. This p obabili y is highe
when he dis ance o he hype plane is lowe . When his dis ance is 0, he cu en model has a
con idence o 0 on he ins ance label, and he p obabili y o asking a que y is 1.
Sculley (Sculley, 2007) p oposes logis ic ma gin sampling, a simila heu is ic o he p e ious
wo k om Cesa-Bianchi e al. (Cesa-Bianchi e al., 2006) bu ha models he sampling p obabili y
using a logis ic eg ession o he dis ance o he di iding hype plane. Bo h hese heu is ics a e
compa ed o he so-called ixed ma gin sampling, p oposed by he au ho s, ha simply eques s a
label o an ins ance when i s dis ance o he di iding hype plane is below a gi en p ese h eshold.
2.3 A e ospec i e iew 29
Mul i-label classi ica ion, 2006 AL is mos equen ly used in single-label classi ica ion asks.
Unce ain y sampling, o ins ance, ocuses on measu ing he con idence o he mos p obable
class. Expec ed e o educ ion s a egies a e based on an e o es ima e o one single class.
QBC selec he ins ances whe e he cu en commi ee has he bigges disag eemen w. . . he op
class. The e a e some p e ious app oaches o AL o mul i-label classi ica ion (B inke , 2006),
equen ly applied o image e ie al (Li e al., 2004; Qi e al., 2009). Howe e hese app oaches
a e no adequa e o ex classi ica ion, as epo ed by Yang e al. (Yang e al., 2009) in 2009,
ei he o exhibi ing poo pe o mance when applied o ex co po a o o equi ing eading and
labeling he same documen se e al imes, which migh be easonable o images bu e y cos ly
o ex documen s. Yang e al. (Yang e al., 2009) p opose an AL app oach o deal wi h mul i-label
ex classi ica ion. The AL componen selec s que ies based on he Maximum loss educ ion wi h
Maximal Con idence (MMC) c i e ia as de ined by he au ho s.
Esuli e al. (Esuli and Sebas iani, 2009) p opose se e al AL s a egies o mul i-label classi ica-
ion asks, e alua ing hem on ex co po a, each one combining he ou pu s e u ned by indi idual
bina y classi ie s as a esul o classi ying a gi en unlabeled documen .
Bo h o hese app oaches o mul i-label ex classi ica ion (Yang e al., 2009; Esuli and Sebas-
iani, 2009) a e based on a se o bina y classi ie s, one o each class o lea n.
Explo a ion e sus exploi a ion, 2006 Kai Yu e al. (Yu e al., 2006) p opose ansduc i e
expe imen al design, an AL app oach applied o eg ession (Has ie e al., 2003). Thei wo k
is ocused on expe imen al design, and deno es conce ns ela ed o he explo a o y aspec s o
AL (Th un, 1998). T ansduc i e expe imen al design sea ches o que ies ha a e simul aneously
ha d o p edic – add essing exploi a ion – and ep esen a i e o he unexplo ed da a – add essing
explo a ion.
In 2009 Ceb on e al. (Ceb on and Be hold, 2009), in oduce P o o ype Based Ac i e Clas-
si ica ion (PBAC), an AL algo i hm o classi ica ion ha e alua es he po en ial o each ins ance
based on a combina ion o i s ep esen a i eness and he unce ain y o he classi ie . Thei mo i-
a ion – he da ase s need o be explo ed i s o gene a e a coa se model and hen he model can be
adap ed o u he ine- une he classi ica ion accu acy – is aligned wi h ou own and a ises om
he need o classi y la ge da ase s wi hou any a-p io i in o ma ion on he a ge classes. PBAC
30 Ac i e Lea ning Re ospec i e
akes in o accoun he densi y o he ea u e space and he unce ain y o he classi ie combined
o o m one single c i e ion o he selec ion o que ies. The ansi ion be ween explo a ion and
exploi a ion occu s as he lea ning p ocess e ol es. This ansi ion is achie ed a each i e a ion
by dec easing he in luence in he selec ion c i e ion o he explo a ion e m whils exploi a ion
in luence inc eases.
This conce n, an explici sense o explo a ion e sus exploi a ion, is also p esen in he wo k
o Osugi e al. (Osugi e al., 2005) ha apply a Ke nel-Fa hes -Fi s algo i hm o explo a ion in
AL wi h SVM. The decision o go o an explo a ion s ep is made a each i e a ion based on he
change ha is induced by he newly added labeled ins ance on he hypo hesis space.
Ou p oposal dynamically shi s be ween explo a ion and exploi a ion modes wi hou equi ing
any uning hus, a oiding o e head cos s. This au oma ic shi ing is guided by bo h he geome ic
p ope ies o he wo king se and he knowledge on he a ge concep embedded in he cu en
hypo hesis.
T ans e lea ning, 2008 AL and ans e lea ning (Ca uana, 1997; Dai e al., 2007) a e dis inc
s a egies o ob ain labeled ins ances o lea ning. AL asks domain expe s o label pa icula ly
in o ma i e que ies while ans e lea ning in ends o le e age he knowledge om a gi en domain
o lea n in a di e en one. Shi e al. (Shi e al., 2008) wo k on he applica ion o AL o he ans e
o knowledge ac oss domains. The au ho s p opose a amewo k o ac i ely ans e knowledge
om one domain in o de o help labeling he ins ances in he a ge domain. They ex end he
s anda d p ocedu e by including an unce ain y based AL componen ha que ies an o acle when
he ou -o -domain example is classi ied wi h low con idence.
Videos may come om many di e en sou ces o domains. Fo ins ance, we may ind a ideo
showing an ai plane – le ’s say, he seman ic concep o lea n – ha comes om a mo ie o om a
news channel. Each o hese sou ces has i s dis inc i e class dis ibu ion so, ans e o knowledge
ac oss di e en sou ces becomes ele an . AL can be used o educe he labeling e o equi ed o
build a classi ie o a new sou ce by eusing a classi ie p e iously ained o he same seman ic
concep bu unde a di e en sou ce o domain.
Li e al. (Li e al., 2010) p oposed an hyb id app oach o selec que ies in a c oss-domain
ideo seman ic concep classi ica ion ask. Thei app oach selec s a ba ch o que ies o ixed
2.3 A e ospec i e iew 31
leng h. Que ies a e selec ed by an ensemble o a disc imina i e que y s a egy, SVM AL, and a
gene a i e que y s a egy ha selec s he sample ha is mos unlikely o ha e been gene a ed by
he sou ce domain dis ibu ion. The pe cen age o que ies in he ba ch ha come om each o
hese s a egies is de ined by a pa ame e o he model. This pa ame e is ini ialized a 50% and is
dynamically upda ed acco ding o he numbe o posi i e ins ances ha ha e been selec ed by he
s a egy in he p e ious i e a ion. The s a egy ha selec s mo e posi i e ins ances will be assigned
a bigge sha e in he ba ch o que ies.
P oac i e lea ning, 2008 Recen wo k on AL is ocused on elaxing some o he base assump-
ions unde lying his lea ning pa adigm, such as, he exis ence o a single omniscien o acle who is
assumed o be in allible (ne e w ong), inde a igable (always answe s), indi idual (only one o a-
cle) and insensi i e o cos s (always ee o always cha ges he same). P oac i e lea ning (Donmez
and Ca bonell, 2008) is a gene aliza ion o AL designed o elax hese un ealis ic assump ions.
Recen app oaches and applica ions o ac i e lea ning, 2008 Robson Mo a e al. (Mo a
e al., 2009) p opose a no el app oach o suppo AL in classi ica ion asks. They explo e he use
o complex ne wo k p ope ies (Newman, 2003; Luciano e al., 2007) – mainly e ex cen ali y
measu es such as closeness and be weenness – o imp o e he pe o mance o AL algo i hms. The
au ho s discussed and e alua ed how hese measu es can be explo ed o guide que y selec ion.
Xiao ei He (He, 2010) showed imp o emen s in op imal expe imen al design when applying
AL. He p oposed a no el AL algo i hm based on he in insic geome y o he inpu space, g asped
om he g aph s uc u e in e ed om he da a, o apply in image e ie al. Empi ical esul s show
imp o emen s o e SVM AL and Laplacian egula ized leas squa es (Belkin e al., 2006).
Despi e he la ge olume o esea ch on AL i s me hods a e being slowly adop ed in p ac ical
applica ions (A enbe g and P o os , 2011). Tex classi ica ion and mo ie il e ing a e among he
ields ha may di ec ly bene i om AL o a g ea ex en . In gene al, any ield cha ac e ized by
uns uc u ed abundan da a will possess he ea u es equi ed o bene i om AL: high labeling
cos and da a a ailabili y. Me a-lea ning applied o p edic he pe o mance o lea ning algo i hms
is a ield ha may also bene i om AL. Labeling ins ances in his ield may be expensi e since i
38 Ac i e Lea ning App oaches
by a commi ee wi h an e en numbe o membe s, 2m, each one assigning a label. Que ies a e
selec ed by he p inciple o maximal disag eemen among commi ee membe s. In a bina y clas-
si ie , disag eemen maximiza ion is achie ed when hal o he commi ee classi ies he inpu as
posi i e while he o he hal classi ies i as nega i e. In such ci cums ances, each que y bisec s he
e sion space when m→∞, maximizing in o ma ion gain (Shannon, 1948). Mon e Ca lo simula-
ions using a wo-membe commi ee con i m he imp o ed pe o mance o Que y By Commi ee
(QBC) o e andom sampling as p esc ibed by he heo e ical s udy. The in o ma ion gain o a
QBC que y ends asymp o ically o a ini e non-ze o alue leading o an exponen ially dec easing
gene aliza ion e o as he numbe o que ies inc eases. When using andom sampling his in o -
ma ion gain ends o 0 and gene aliza ion e o dec eases as an in e se powe law in he numbe o
que ies hus, pe o ming poo e han QBC. The au ho s e e ha , in a il e ing app oach, whe e
que ies a e selec ed om he a ailable da ase , he lea ne may ha e o e alua e many ins ances
be o e inding one whe e he commi ee disag ees. This d awback does no s and in he que y-
cons uc ion se ing whe e one can gene a e speci ic a i icial ins ances o p omo e disag eemen
in he commi ee. QBC is no mally used in s eam-based lea ning whe e a que y is made o each
incoming ins ance gene a ing commi ee disag eemen . The esul s om his seminal pape on
QBC (Seung e al., 1992) a e gene alized and u he discussed by F eund e al. (F eund e al.,
1997).
Lu e al. (Lu e al., 2010) sus ain ha speci ic da ase s demand o speci ic ensembles o base
classi ie s. The “one-size- i s-all” app oach, unde lying he o iginal QBC app oach, can be im-
p o ed by dynamically adap ing he ensemble o base classi ie s o he da ase a hand. The au-
ho s p opose adap i e in o ma i e sampling, ex ending he base QBC echnique o accommoda e
hei claim. Adap i e in o ma i e sampling is ini ialized wi h a balanced ensemble composed by
an equal numbe o classi ie s om wo dis inc ypes – hei wo k elies on neu al ne wo ks and
decision ees. Then, a each i e a ion, he pe cen age o commi ee membe s om each ype
is upda ed based on he classi ie s’ pe o mance in he p e ious i e a ion in a way o a o bes
pe o me s.
The pe o mance o a gi en classi ie in he commi ee is e alua ed by wo dis inc i ness
unc ions depending on he numbe o classes o lea n. In bina y classi ica ion asks, commi ee
membe s, hi, a e e alua ed by he i ness unc ion, , in Equa ion 3.3, whe e pkis he numbe o

3.3 Expec ed u ili y gain 39
ue posi i es iden i ied o class ckand nkis he o al equency o class kin he aining se .
(hi) = p0
n0× p1
n1(3.3)
Fo mul i-class classi ica ion asks he i ness unc ion is de ined as he numbe o misclassi-
ied ins ances in he aining se . Expe imen al esul s show ha adap i e in o ma i e sampling
consis en ly ou pe o ms homogeneous ensembles.
3.3 Expec ed u ili y gain
The AL app oaches ha we ha e conside ed unde his ca ego y selec que ies based on an es ima e
o he u ili y o unlabeled ins ances. The u ili y measu e depends on he conc e e ask bu expec ed
e o and e o a iance a e usual.
Cohn e al. (Cohn e al., 1996) desc ibe an op imal solu ion o pool-based AL ha selec s
he ins ance ha , once labeled and added o he aining se , p oduces he minimum expec ed
e o . The expec ed e o o he lea ne is decomposed in o h ee e ms: noise in he class dis-
ibu ion (independen om he lea ne ), he lea ne ’s bias and he lea ne ’s a iance ( e lec ing
he sensi i i y o he lea ne o he aining se ). Di ec es ima ion o bo h bias and a iance, is
no possible o induc i e lea ning since i equi es knowing he ac ual class dis ibu ion which
is no a ailable. Howe e , a iance es ima ion is compu ed wi hou e e ence o he unde lying
p obabili y dis ibu ion. Mo eo e , when in p esence o low a iance, accu a e classi ica ion is
achie able ega dless o bias (F iedman, 1997). Cohn e al. assume app oxima ely unbiased lea n-
e s, i.e., lea ne s whose a e age p edic ion o a gi en ins ance is equal o i s ue class. Unde
such ci cums ances e o is educed o he a iance e m hus, minimizing he lea ne ’s a iance is
equi alen o minimizing e o . This app oach, howe e , equi es high compu a ional e o .
Schohn e al. (Schohn and Cohn, 2000) wo ked on AL, wi h SVM base classi ie s, de ining a
que y selec ion heu is ic ha es ima es he expec ed change in e o when adding a gi en ins ance
o he aining se . Thei esul s a e, in some cases, be e han i all a ailable da a is used o ain.
One op imal app oach, in a bina y classi ica ion ask, es ima es he expec ed e o , Ej, a e adding
a new ins ance, xj, o he aining se as he mean o he expec ed e o when he new que y being
40 Ac i e Lea ning App oaches
added belongs ei he o class 1, E(xj,1), o o class −1, E(xj,−1)(Equa ion 3.4).
Ej=P(yj=1|xj)·E(xj,1)+P(yj=−1|xj)·E(xj,−1)(3.4)
E(xj,ck)migh be compu ed by Mon e Ca lo simula ion (Cohn e al., 1996) o , as sugges ed by
he au ho s, using a simple non-p obabilis ic app oach ha de ines E(xj,ck)as he olume spanned
by he SVM ma gin and hen compu es Ej=maxE(xj,1),E(xj,−1). In such case, Ejse s a lowe
bound o he dec ease in unce ain y ha is achie able when adding xj o he aining se .
Howe e , bo h hese g eedy app oaches a e un easible in p ac ice since compu ing E(xj,ck)
equi es building a la ge numbe o classi ie s o each i e a ion – wice he numbe o unlabeled
ins ances o a bina y classi ica ion ask. The same d awback – high compu a ional cos – is
expe ienced by Roy e al. (Roy and McCallum, 2001) whose app oach equi es e aining he
classi ie se e al imes a each i e a ion, one o each class o lea n.
To o e come his p ac ical d awback, he au ho s claim ha que ies can be selec ed wi hou
he need o es ima e he expec ed change in e o , hus a oiding ex ensi e e aining. Selec ing
he nex que y such ha he expec ed gene aliza ion e o is minimized can be accomplished by
na owing he exis ing ma gin as much as possible, ha is, by que ying he unlabeled ins ance
ha is close o he di iding hype plane. The compu a ional cos o his heu is ic is incompa ably
lowe han he one equi ed by he op imal algo i hms desc ibed abo e. The esul s epo ed by
he au ho s a e also a o able o hei p oposal. High accu acy is achie ed e y quickly, in some
cases equi ing ou imes ewe labeled ins ances han compe ing me hods.
Chapelle (Chapelle, 2005) p oposes an app oach ha di ec ly compu es an es ima e o he ex-
pec ed gene aliza ion e o , pe o ming he op imal AL s a egy desc ibed abo e (Equa ion 3.4) in
a easible way. This app oach elies on a simple classi ie , he Pa zen window classi ie (De oye
e al., 1996), ha gi es di ec es ima es o he pos e io p obabili ies a oiding a cos ly e aining
p ocess a each i e a ion.
Lindenbaum e al. (Lindenbaum e al., 2004) apply AL o ins ance based lea ning explo ing
nea es -neighbo classi ie s1. They p opose wo accu acy based u ili y unc ions ha a e maxi-
1The nea es -neighbo classi ie s o es all p e iously labeled ins ances ha a e hen used o classi y unlabeled in-
s ances acco ding o he label o i s nea es labeled neighbo . Va ia ions o his scheme include k-nea es -neighbo
classi ie s (Duda and Ha , 1973) ha assign classes o unlabeled ins ances by majo i y o e o he k-nea es labeled
neighbo s (Co e and Ha , 1967).
3.4 Densi y based 41
mized a e labeling and adding he new que y o he aining se : an absolu e-accu acy u ili y
unc ion, ha es ima es he absolu e expec ed accu acy o he u u e hypo hesis ega dless o he
cu en one and a gain-based u ili y unc ion ha es ima es he accu acy gain o he u u e hypo h-
esis ela i e o he cu en one.
Using andom ield models (Wong and Hajek, 1985), Wong and Hajek es ima e he p obabili y
o he possible labels o an unlabeled ins ance, xj, and hen compu e i s expec ed u ili y om hose.
Be a di e al. (Be a di e al., 2012) p opose inspec ion gain, an app oach o ex classi ica ion
ha anks au oma ically labeled documen s by he expec ed imp o emen in he classi ica ion
e ec i eness ha is achie able by e aining a e e iewing he au oma ically labeled documen s.
The anking unc ion used o so au oma ically labeled documen s ac s as a que y selec ion c i e ia
based on u ili y.
3.4 Densi y based
Unde his ca ego y we ha e conside ed AL app oaches ha a e based ei he on he dis ance be-
ween ins ances o on he densi y o he da a in inpu space o on clus e ing. Dis ance based ap-
p oaches a e common in AL. The equen use o SVM as he base classi ie may ha e con ibu ed
o his since unce ain y in SVM classi ie s is ela ed o dis ance o he di iding hype plane. The
simples dis ance based app oach, a hes - i s (Hochbaum and Shmoys, 1985), selec s he nex
que y as he unlabeled ins ance ha is a he apa om all labeled ins ances. This app oach,
a o ing explo a ion o e exploi a ion, elies exclusi ely on dis ance measu es in he inpu space
ha a e independen om he base lea ne .
SVM AL (Tong and Kolle , 2002) selec s he ins ance lying wi hin he SVM ma gin closes
o he di iding hype plane. This app oach assumes a clea ocus on exploi a ion. F om he poin
o iew o he explo a ion-exploi a ion ade-o hese wo opposing s a egies, a hes - i s and
SVM AL, bo h based on dis ance, ake ex eme posi ions.
Rep esen a i e sampling (Xu e al., 2003), also a SVM based app oach, goes a li le u he
beyond SVM AL and ies o cap u e he s uc u e unde lying he unlabeled ins ances wi hin he
SVM ma gin. Rep esen a i e sampling selec s a ba ch o mque ies in each i e a ion ollowing
42 Ac i e Lea ning App oaches
Algo i hm 3.2 un il some s opping c i e ia is sa is ied. This ba ch is composed by he medoids2o
he clus e s o med by he unlabeled ins ances lying inside he SVM ma gin.
Algo i hm 3.2 Rep esen a i e sampling (adap ed om (Xu e al., 2003))
1: while no s opping c i e ia do
2: T ain a linea SVM based on he labeled ins ances
3: Clus e he unlabeled ins ances lying in he ma gin o he newly ained SVM in o mg oups
using k-means clus e ing and inne p oduc as a simila i y measu e
4: Iden i y he mmedoids o he mclus e s
5: Ask he o acle o he labels o hese mins ances
6: end while
7: Re u n he cu en SVM classi ie
The clus e ing s ep (s ep 3 in Algo i hm 3.2) is expec ed o p ese e he densi y dis ibu ion by
allowing o que y he mos impo an unce ain ins ances. Ba ch di e si y is achie ed by selec ing
he medoid o each clus e as he ba ch membe s.
Wang e al. (Wang e al., 2009) selec a p elimina y ba ch o ins ances ha lie in he SVM
ma gin and hen en o ce di e si y by selec ing hose ins ances om his p elimina y ba ch ha
explici ly maximize he dis ance be ween each o he in he o iginal inpu ea u e space. To assu e
di e si y, Chen e al. (Chen e al., 2010) use dis ance di e si y and se densi y in he SVM ea u e
space o e alua e he he e ogenei y o he selec ed ba ch.
Clus e ing has also been explo ed o p o ide an ini ial s uc u e o da a o o sugges aluable
que ies (McCallum and Nigam, 1998; Nguyen and Smeulde s, 2004; Hu e al., 2009; Zhu e al.,
2010a).
Adami e al. (Adami e al., 2005) me ge clus e ing and o acle labeling o boo s ap a p ede-
ined hie a chy o classes. Al hough he o iginal clus e s p o ide some s uc u e o he inpu , his
app oach s ill demands o a high alida ion e o , especially when hese clus e s a e no aligned
wi h class labels.
This conce n on misalignmen is also p esen in (Dasgup a and Hsu, 2008). Dasgup a e
al. p opose a clus e -based me hod ha consis en ly imp o es label complexi y – he numbe
o que ies ha is su icien o lea n a concep – o e supe ised lea ning. Thei me hod de ec s and
exploi s clus e s ha a e loosely aligned wi h class labels.
2A medoid is a ep esen a i e objec o a gi en se . I is he ins ance whose a e age dissimila i y o all he ins ances
in he se is minimal. Medoids a e simila in concep o cen oids, bu hey a e always eal ins ances o he da ase . The
medoid is he da ase ins ance ha is closes o he cen oid.
3.5 Hyb id app oaches 43
Jiang e al. (Jiang and Ip, 2007) p opose a no el dynamic dis ance-based app oach o AL
wi h SVM, named dynamic dis ance-based ac i e lea ning. The au ho s claim ha hei app oach
ou pe o ms he s anda d SVM AL app oach (Tong and Kolle , 2002). The dynamic dis ance-
based s a egy is implemen ed in wo s eps. In he i s s ep, he nea es ins ance o he cu en
decision bounda y is que ied – he s anda d SVM AL app oach. Then, i s neighbo s a e so ed
by inc easing dis ance o he cu en decision bounda y. The second s ep in ol es he o acle ha
mus label he ins ances in his anked lis , in sequence, om op o bo om – he closes ins ances
o he decision bounda y a e que ied i s – un il eaching an ins ance whose label is opposi e o
he p e ious. The las posi i e ins ance is added o he aining se .
3.5 Hyb id app oaches
Hyb id app oaches combine se e al dis inc s a egies in an a emp o ake ad an age o he ben-
e i s om each one. Pu e s a egies end o a o ei he explo a ion o exploi a ion compe ences.
While exploi a ion conce ns seem o ha e been domina ing AL esea ch, explo a ion seems o
ha e been gaining ele ance. The issue is ha explo a ion and exploi a ion a e co ela ed. Ac ing
on one has in luence on he o he , usually equi ing a comp omise solu ion. Focusing on ins ances
nea he decision bounda y, a o ing exploi a ion, p e en s explo ing egions in he ea u e space
ha migh con ain ins ances being misclassi ied by he cu en hypo hesis (Ba am e al., 2004). On
he o he hand, ocusing on explo a ion, i.e., selec ing que ies om egions in he ea u e space
away om he decision bounda y, educes he chances o sha pen cu en decision bounda ies.
Se e al hyb id app oaches, like P o o ype Based Ac i e Classi ica ion (PBAC) (Ceb on and
Be hold, 2009), y o combine explo a ion and exploi a ion capabili ies in a unique s a egy in
sea ch o a good comp omise solu ion.
PBAC, mo i a ed by he need o classi y la ge da ase s wi hou any a-p io i in o ma ion, se-
lec s que ies based on he unce ain y dis ibu ion, a no el c i e ion p oposed by he au ho s.
Unce ain y dis ibu ion es ima es he u ili y o an ins ance om an agg ega ion o i s ep esen a-
i eness po en ial, which is e alua ed om densi y es ima es on he unlabeled da a, and classi ie
unce ain y, based on labeled da a. PBAC (Algo i hm 3.3) s a s by explo ing a da ase o gene -
a e a coa se model; hen, his p elimina y model is exploi ed o une classi ica ion accu acy. The

44 Ac i e Lea ning App oaches
ansi ion om explo a ion o exploi a ion occu s as he lea ning p ocess e ol es by dec easing a
each i e a ion he in luence o he explo a ion e m while inc easing he in luence o he exploi a-
ion e m.
Algo i hm 3.3 P o o ype Based Ac i e Classi ica ion (adap ed om (Ceb on and Be hold, 2009))
1: Se h eshold T
2: GlobalPo en ial =0
3: o all xj∈Udo
4: Compu e he po en ial P(xj)
5: GlobalPo en ial =GlobalPo en ial +P(xj)
6: end o
7: while GlobalPo en ial >Tdo
8: o all xj∈Udo
9: Compu e he classi ie unce ain y C(xj)
10: Compu e he unce ain y dis ibu ion D(xj)acco ding o Equa ion 3.5
11: end o
12: Selec qi he ins ance xjwi h he highes po en ial
13: Ob ain a class label yi o qi
14: C ea e a new p o o ype wi h alues qiand class label yi
15: Classi y he da ase s wi h he cu en se o p o o ypes
16: Reduce he po en ials
17: end while
The unce ain y dis ibu ion, D, o an unlabeled ins ance, xj, combines i s po en ial, P(xj),
compu ed on he unlabeled da a, and he classi ica ion unce ain y, C(xj), compu ed on he labeled
da a (Equa ion 3.5). In Equa ion 3.5, ε∈[0,1]con ols he in luence o he exploi a ion e m.
D(xj) = (1−ε)P(xj)+εC(xj)(3.5)
The po en ial o xj,P(xj), is compu ed om he dis ance be ween xjand i s closes neighbo s.
Ins ances ha ha e mo e neighbo s in hei close icini y ha e a highe po en ial. Ha ing he
po en ials compu ed, he ins ance wi h highe po en ial, x∗
j, is selec ed and he po en ials o x∗
jand
hei close neighbo s a e educed o a oid ha ing hese ins ances selec ed in he nex i e a ion. This
po en ials’ educ ion s ep also educes he o e all in luence o explo a ion as he lea ning p ocess
i e a es. The educ ion o po en ials is also used o de ine a s opping c i e ion. The lea ning
p ocess s ops when he o al sum o all po en ials d ops unde a p ede ined h eshold, T.
The classi ie unce ain y o a gi en ins ance xj,P(xj), is compu ed as he en opy o i s
membe ship p obabili ies o all classes. These class p obabili ies a e compu ed om a weigh ed
3.5 Hyb id app oaches 45
k-nea es -neighbo classi ie based only on he labeled ins ances, called p o o ypes. The class
label o a gi en unlabeled ins ance, xj, is assumed o be he class label o he p o o ype wi h he
la ges p o o ype weigh , i.e., he closes p o o ype o xj.
An explici conce n o explo a ion e sus exploi a ion, is also discussed by Osugi e al. (Osugi
e al., 2005). They p opose an AL s a egy ha decides a each i e a ion whe he o explo e o
exploi . This decision is based on a bina y andom a iable, a “coin lip” as he au ho s pu i ,
assigning a p obabili y p o explo e (and 1−p o exploi ).
I he decision is o explo e, he Ke nel Fa hes Fi s (Ba am e al., 2004) algo i hm is applied
o selec he nex que y – selec he unlabeled ins ance ha is u he away om all labeled in-
s ances in he ea u e space induced by he ke nel unc ion used by he classi ie . O he wise he
nex que y is selec ed wi h Simple (Tong and Kolle , 2002) – selec he unlabeled ins ance ha is
closes o he cu en decision bounda y. This new que y is labeled and added o he aining se .
To de e mine how success ul an explo a ion s ep was, he au ho s compu e d(hi−1,hi)∈[−1,+1],
he change induced om he p e ious hypo hesis, hi−1, o he cu en , hi. I d(hi−1,hi)is posi i e,
implying signi ican change om hi−1 o hi, he p e ious explo a ion s ep is assumed o be suc-
cess ul and he p obabili y pis kep high encou aging u he explo a ion. I d(hi−1,hi)is nega i e,
pis educed.
The explo a ion p obabili y pis upda ed om i e a ion i−1 o i e a ion iusing Equa ion 3.6.
pi=max(min(pλed(hi−1,hi),1−ε),ε)(3.6)
whe e εis a pa ame e ha bounds he alue o p(so he e is always a chance o explo ing and
exploi ing) and λis he lea ning a e o upda ing p. The unc ion d(hi−1,hi), used o measu e he
change induced by he que y jus added o he aining se , is a linea ans o ma ion (Equa ion 3.7)
o he cosine, s(h,h0), be ween he ec o s o he eal- alued labels, hand h0, p edic ed by bo h
hypo hesis hiand hi−1 o he wo king se (including he p edic ions o labeled and unlabeled
ins ances).
d(hi−1,hi) = 3−4s(h,h0)(3.7)
46 Ac i e Lea ning App oaches
3.6 Ini ializa ion and s opping c i e ia
AL classi ica ion is an i e a i e app oach ha e ol es a base classi ie un il a ce ain pe o mance
le el which is assumed o be adequa e gi en he ask a hand. Du ing he lea ning p ocess he
same s a egy is execu ed in e e y s ep o a loop. This loop is p eceded by an ini ializa ion s ep –
p o iding an ini ial labeled se equi ed o lea n he i s ins ance o he classi ie – and hal ed when
a gi en s opping c i e ion is me . A simple way o pe o m he ini ializa ion s ep is by andom
sampling while a simple s opping ule is he exhaus ion o he unlabeled se . Some esea ch has
been done o imp o e hese nai e app oaches. We a e pa icula ly conce ned wi h he s opping
c i e ia enabling us o hal he lea ning p ocess when in p esence o a good “enough” classi ie ,
hus a oiding o ask o labels ha add li le o no alue.
3.6.1 Ini ializa ion
Ini ializing he labeled se in some p ope way migh educe he numbe o was ed que ies – que ies
ha p oduce useless labels – and imp o e he pe o mance o he classi ie s lea ned a he ini ial
s age o he lea ning p ocess. Selec ing a p ope labeled se aims a ea ly g asping he dis ibu ion
o he da a o classi y, hus c ea ing condi ions o selec aluable que ies in he ollowing i e a ions.
This, howe e , is a ask o be pe o med in he absence o any p io e idence on he concep o
lea n. Se e al app oaches, based on chance alone o exploi ing somehow he a ailable wo king
se , a e a ailable in he li e a u e.
Some s aigh app oaches o he ini ializa ion o he labeled se a e common, such as using a
se o ins ances p e iously labeled by some mean (Sun and Ha doon, 2010) o andom sampling.
Ini ializing he labeled se by andomly selec ing aining ins ances om e e y class o lea n is
p obably he mos common app oach (Tong and Kolle , 2002; Zhang and Chen, 2002; Wa mu h
e al., 2003; Xu e al., 2004; Schü ze e al., 2006).
Howe e , andom sampling migh be e y demanding mainly when in p esence o a se e ely
imbalanced da ase . This is one o he main conce ns in (Dima and Hebe , 2005) who de ine an
ini ializa ion algo i hm, based on he densi y o he inpu space, ha disca ds edundan ins ances
– hose lying in egions o he ea u e space ha a e densely popula ed – while keeping ins ances
3.6 Ini ializa ion and s opping c i e ia 47
om spa se egions a ailable o que ying. Thei assump ion is ha ins ances om densely pop-
ula ed egions a e ep esen a i es o he same class wi h high p obabili y and epea ed que ies on
hese egions will miss unde - ep esen ed classes while inc easing he numbe o was ed que ies.
This assump ion leads o a beha io which anks explo a ion highe han exploi a ion.
An opposi e easoning – assuming ha a e o bo de line cases ha do no occu e y o en
a e no in e es ing o classi ica ion and, he e o e, disca ding hem om he ini ial labeled se
– mo i a es he wo k desc ibed in (Ceb on e al., 2007), whe e he seed que ies a e selec ed on
he basis o he so called po en ial o each unlabeled ins ance. This po en ial, as de ined by he
au ho s, is a measu e o he densi y o he inpu space in a gi en p ede ined neighbo hood o he
ins ance being e alua ed. Any ins ance ha lies wi hin his neighbo hood has a la ge in luence
on he po en ial o he ins ance a hand. Seed que ies a e he ins ances wi h he highes po en ial
sco e, ha is, hose ha lie in densely popula ed egions. This easoning boos s exploi a ion o e
explo a ion.
Clus e ing is also a common app oach o he ini ializa ion phase ha ies o explo e he in-
insic s uc u e o he wo king se . K-means clus e ing is used o selec ini ial aining ins ances
in (Kang e al., 2004). The au ho s p opose a me hod ha di ides he unlabeled ins ances in o
clus e s and hen selec s he clus e s’s medoids which a e assumed o be he mos ep esen a i e
ins ances om each clus e . The cen oid i sel may be di icul o label because i will be mos
likely a syn he ic ins ance mainly when wo king wi h high dimensional inpu spaces as is he
case wi h ex co po a. Ne e heless, he clus e syn he ic cen oids hemsel es may also be used
as aining ins ances a no ex a labeling cos since hey will be assigned he same label ha he
o acle has assigned o he ep esen a i e ins ance. In such a case, he cen oids a e named model
examples. Expe imen s pe o med on a ious ex da ase s ha e shown ha he ac i e lea ne s a -
ing om he ini ial aining se selec ed by his me hod eaches highe accu acy as e han when
ini ialized by andom sampling. The inclusion o he model examples in he aining se u he
imp o es lea ning pe o mance.
Nguyen e a . (Nguyen and Smeulde s, 2004) use a simpli ied e sion o he K-medoid algo-
i hm (Kau man and Rousseeuw, 1990) ha inds K ep esen a i es o he da ase o ini ialize he
labeled se . These ep esen a i e ins ances a e hose minimizing he sum o he dis ances om
he da a samples o he nea es ep esen a i e. To o e come he high compu a ional cos o he
54 Ac i e Lea ning App oaches
ions on que ies is al eady la ge han a p ede ined accu acy h eshold (no benchma k is p o ided).
Max-con idence and min-e o a e sugges ed, espec i ely, as he uppe bound and he lowe bound
o s opping condi ions. These c i e ia a e based on he p emises ha i a classi ie induced om
he cu en aining da a has s ong classi ica ion con idence on an unlabeled ins ance, hen we can
conside i as edundan .
I should be no iced ha min-e o is adequa e o ba ch mode AL. In a di e en se ing, whe e
only one que y is selec ed pe i e a ion, he accu acy pe o mance is ei he 1, i he classi ie
p edic s he co ec label, o 0, o he wise. In such se ings, max-con idence and min-e o migh
be used ensemble. Once bo h condi ions a e me , he cu en classi ie is assumed o ha e enough
con idence on he labels o all he emaining unlabeled da a and he lea ning p ocess e mina es.
This o me wo k by Zhu e al. is ex ended o in oduce he minimum expec ed e o s a egy ha
in ol es es ima ing he classi ica ion e o on u u e unlabeled ins ances.
O e all-unce ain y is simila o max-con idence, bu , ins ead o aking only he mos in o -
ma i e ins ances in o conside a ion, i is compu ed o e all unlabeled ins ances.
Classi ica ion-change assumes ha he mos in o ma i e ins ance is he one which causes he
classi ie o change i s p edic ed label. Thus, he lea ning p ocess is e mina ed once no p edic ed
label changes du ing wo consecu i e i e a ions.
Recen ly, in 2010, Zhu e al. (Zhu e al., 2010b) p opose he selec ed accu acy me hod along
wi h combina ions o all he abo e s a egies o es ima e he equi ed h esholds. The selec ed
accu acy me hod is designed o apply in ba ch mode AL. In such a se ing he lea ning algo i hm
has access, in each i e a ion, o he ue labels o all he ba ch membe s. The unlabeled ins ances
composing he ba ch a e supposed o be he mos in o ma i e gi en he cu en hypo hesis and he
unlabeled da a pool. The lea ning p ocess is e mina ed when he accu acy o he cu en classi ie
on hese ba ch ins ances is abo e a gi en h eshold.
Missed clus e s Schu ze e al. (Schü ze e al., 2006) claim ha he e is no ob ious p ocedu e
o decide con enien ly when o s op que ying due o he so called missed clus e s – unexplo ed
egions in he inpu space con aining posi i e ins ances. Missing clus e s can only be ound by
chance, demanding o andom sampling. As a consequence o his easoning he au ho s claim
ha ins ead o ying o se s opping c i e ia depending on he a ailable da a ano he al e na i e is

3.6 Ini ializa ion and s opping c i e ia 55
o de ine a le el o accep able pe o mance and s op he lea ning p ocess when his le el has been
eached – hey sugges using F1=80%.
56 Ac i e Lea ning App oaches
Chap e 4
Tex Classi ica ion
Classi ica ion asks, in gene al, aim a assigning one o mo e classes, om a p ede ined se , o a
gi en ins ance om he a ge domain. Tex classi ica ion, also known as ex ca ego iza ion, e e s
o he classi ica ion ask pe o med o e ex co po a. In ex classi ica ion, classes, a.k.a. labels,
a e assigned o ex documen s.
Ea ly ex classi ica ion app oaches, in use be ween he 60’s and la e 80’s, we e pe o med by
domain expe s deploying a se o ules o assign classes o documen s in a speci ic domain. This
expe sys em’s app oach has wo majo d awbacks: i is es ic ed o a speci ic a ge domain and
equi es a signi ican e o and ime om he domain expe s. These app oaches a e no scalable
o he a ie y and olume o ex ual in o ma ion ha became a ailable since he las decade o
he 20 h cen u y wi h he widesp ead use o he Web and o he In e ne se ices. This misma ch
be ween he chances o e ed by he amoun o ex ual da a widely a ailable and he cos o ex
classi ica ion mo i a ed he sea ch o au oma ic ex classi ica ion solu ions. Resea ch e o s
ocused on ex classi ica ion in he a ea o machine lea ning a ose na u ally in he ea ly 90’s.
Nowadays, many o he ex classi ica ion sys ems ely, o some ex en , on au oma ic classi ie s
coming om he machine lea ning ield. S a e-o - he-a ex classi ica ion sys ems exhibi accep -
able pe o mance a a lowe cos han ha equi ed by non-au oma ic sys ems elying exclusi ely
on he knowledge o domain expe s. Ne e heless, ex classi ica ion has ce ain cha ac e is ics
ha make i a di icul ask o machine lea ning. Tex co po a, collec ions o ex documen s,
a e cha ac e ized by high-dimensional inpu spaces – equen ly anging o e 104dimensions –
ha ing many i ele an ea u es and con aining high le els o noise. As a consequence, a la ge
57
58 Tex Classi ica ion
numbe o labeled ins ances is usually equi ed o ain. Howe e , building classi ica ion ules
by hand is ce ainly mo e demanding – conce ning human e o and he equi ed skills – han
assigning labels o a se o ex documen s o be used o ain a classi ie (Hayes, 1992).
Tex classi ica ion in ol es a se o asks, including: (a) he p ope p epa a ion o ex doc-
umen s, which a e by na u e uns uc u ed da a objec s, in o de o ex ac he ele an ea u es
ha a e equi ed by he classi ica ion p ocess; (b) he p ope ep esen a ion o ex documen s in a
o ma ha is adequa e o he classi ica ion p ocess; (c) lea ning he a ge classes; (d) applying
he lea ned model o classi y new documen s and (e) e alua e he pe o mance o he classi ica ion
p ocess.
The p e-p ocessing asks, e e ed abo e as asks (a) and (b), a e discussed in Sec ion 4.1,
while asks (c) o (e) a e discussed in Sec ions 4.2, 4.3, 4.4 and 4.5.
4.1 P e-p ocessing
We conside a p e-p ocessing s age comp ising he asks ha a e equi ed o ob ain a sui able
documen ep esen a ion, alid o he subsequen au oma ic lea ning phase. This s age includes
ex p epa a ion and ex ep esen a ion.
4.1.1 Tex p epa a ion
The ex p epa a ion phase akes a ex documen as inpu and e u ns a se o ea u es desc ibing
i . This phase includes se e al s eps ha a emp o elimina e non-in o ma i e ea u es and migh
in ol e some o all o he ollowing (based on (Baeza-Ya es and Ribei o-Ne o, 1999) and (Weiss
e al., 2004)):
• okeniza ion – b eaking he ex documen in o okens, commonly wo ds; includes all so s
o lexical analysis s eps, such as: elimina ing punc ua ion, numbe s, accen s and ex a spac-
ing, con e ing o lowe o uppe case;
•s op-wo d emo al – emo ing i ele an e ms; equi es a lis o s op-wo ds (wo ds o elim-
ina e);
•s emming o lemma iza ion – educing wo ds o hei seman ic oo ; he Po e algo i hm (Po e ,
1980) is p obably he mos well known s emming algo i hm; speci ic algo i hms, such as he
4.1 P e-p ocessing 59
one p oposed by O engo e al. (O engo and Huyck, 2001) o he Po uguese language, a e
equi ed o each language;
• ea u e selec ion – de ining index e ms, he ea u es ha will be used o documen model-
ing. The ull p ocess o selec ing ea u es and compu ing hei weigh s is known as indexing.
The applica ion o hese p e-p ocessing asks mus be ca e ully done because he p edic i e
powe o wo ds is highly dependen on he opic o in e es (Chak aba i e al., 1998a). Ano he
essen ial aspec o conside is he language in which he documen is w i en, which de e mines,
a leas , he lis o s op-wo ds and he s emming algo i hm o use.
S op-wo ds emo al is con o e sial. Remo ing wo ds om a ex , e en hose ha in a linguis-
ic sense ha e low seman ic alue, always educes he in o ma ion con ained in he ex documen .
S op-wo d emo al educes he dimensionali y o he ea u e space a a cos o loosing some in o -
ma ion. A comp omise solu ion mus be se so ha his in o ma ion loss does no ge coun e p o-
duc i e. Wha is le ou om “ o be o no o be” a e s op-wo d emo al? Recall ha his ph ase
is comple ely made up o wo ds ha a e equen ly ecognized as s op-wo ds. To a oid his loss,
some sys ems, like Ci eSee (Law ence e al., 1999), o ins ance, do no emo e any wo ds om
he documen s o be indexed. Web documen s, o ma ed in HTML o o he ma kup language,
s ill equi e spli ing ma kup ags om con en which is pe o med ea ly in he okeniza ion s ep,
be o e lexical analysis.
The wo ds ha appea in documen s o en ha e many mo phological a ian s. Thus, pai s o
e ms such as “s uden ” and “s uden s”, will no be ecognized as equi alen wi hou some o m
o p ocessing. Reducing mo phological a ian s o wo ds wi h he same seman ics o a common
oo , o s em, is called s emming. A s em, by de ini ion, is he po ion o he wo d ha is le
a e he emo al o i s a ixes (p e ixes and su ixes). Mos equen ly, se e al mo phological
a ian s o wo ds ha e he same seman ics and so hey can be in e p e ed as he same o ex
ca ego iza ion pu poses. This way, no only he numbe o ea u es ge s educed bu also he op-
ics desc ibed in he ex ge mo e no iceable o he lea ning algo i hms since seman ically simila
wo ds a e con la ed o a single ep esen a i e o m. Fo au oma ic p ocessing pu poses, i does
no usually ma e whe he he s ems gene a ed a e genuine wo ds o no ( o example: "compu a-
ion" migh be s emmed o "compu " ins ead o "compu e") p o ided ha di e en wo ds wi h he
same base meaning a e con la ed o he same s em and ha wo ds wi h dis inc meanings a e kep

60 Tex Classi ica ion
sepa a e. In lec ional s emming, in linguis ic e minology called mo phological analysis, may be
seen as a ligh s emming p ocess limi ed o egula ize g amma ical a ian s such as singula /plu al,
gen e and pas /p esen . The e a e a numbe o s emming algo i hms (known by s emme s o lem-
ma ize s) a ailable and widely used, such as, he Po e algo i hm (Po e , 1980), he K o e z
algo i hm (K o e z, 1993) and he Lo ins algo i hm (Lo ins) – he i s s emme wi h widesp ead
dissemina ion, published in 1968.
In ex classi ica ion he numbe o ea u es is ypically much la ge han he numbe o ain-
ing ins ances and, i ca e is no aken, undesi able o e i ing may a ise. Fea u e selec ion is de-
si able no only o a oid o e i ing bu also o educe ea u e space dimension and, consequen ly,
s o age and p ocessing cos . Fea u e selec ion (Yang and Pede sen, 1997) o ea u e educ ion
echniques may be heu is ic – go e ned by linguis ic p inciples o speci ic ules om he uni e se
o discou se – o s a is ical. The p ocedu e o ea u e selec ion usually comp ises he ollowing
s eps (Chak aba i, 2003):
1. compu e, o each ea u e, a measu e ha allows o disc imina e a ge classes;
2. lis ea u es in dec easing o de o ha measu e and
3. keep he subse o he ea u es wi h he highes disc imina i e powe .
The high ea u e space dimensionali y, common in ex co po a, can be educed wi h ech-
niques ha migh be ca ego ized ei he as ea u e selec ion o e-pa ame e iza ion echniques (Aas
and Eik il, 1999). Fea u e selec ion a emp s o emo e non-in o ma i e wo ds om documen s
in o de o imp o e ca ego iza ion e ec i eness and educe compu a ional complexi y while e-
pa ame e iza ion is he p ocess o cons uc ing new ea u es, as combina ions o ans o ma ions
o he o iginal ones. Fea u e selec ion app oaches a e usually u he classi ied as w appe o il e
echniques depending on whe he hey explo e he lea ning algo i hm o selec he mos app o-
p ia e ea u es o no . Among common ea u e selec ion echniques we may include (Yang and
Pede sen, 1997):
•documen equency h eshold (Xu e al., 2008) elies on he in e se documen equency,
i.e. he numbe o documen s whe e he ea u e is p esen , and elimina es ea u es whose
in e se documen equency alls o some p e-de ined h eshold; he applica ion o his
4.1 P e-p ocessing 61
echnique is simple, inexpensi e and has been p o iding good esul s, al hough i equi es
some ca e in he speci ica ion o he h eshold alue;
•in o ma ion gain (Zheng e al., 2004) so s ea u es by dec easing o de o hei in o ma ion
gain; he mos in o ma i e ea u es a e e ained while he leas in o ma i e a e emo ed
om he ea u e se ;
•mu ual in o ma ion (Dumais e al., 1998; No o iˇ
co á e al., 2004; Peng e al., 2005) mea-
su es he associa ion be ween ea u es and classes based on a wo way con ingency able;
ea u es wi h he highes mu ual in o ma ion a e selec ed;
•chi-squa e (Gala o i e al., 2000; Zheng e al., 2004) uses he same con ingency able as
mu ual in o ma ion bu pe o ms a chi-squa e s a is ical es o in e independence be ween
ea u es and a ge classes; he majo ad an age o his me hod, compa ed o mu ual in-
o ma ion, is ha , since he es s a is ic is no malized, i allows o compa isons among
ea u es o he same class;
• e m s eng h (Wilbu and Si o kin, 1992; Liu e al., 2003) is signi ican ly di e en om he
abo e; his me hod compu es each e m s eng h independen ly om he documen class.
I assumes ha documen s sha ing many common wo ds a e simila and, u he , ha he
common wo ds a e in o ma i e. This me hod es ima es e m impo ance based on he con-
di ional p obabili y o a e m appea ing in a ce ain documen gi en ha i appea s in ano he
simila documen ;
•The Ma ko blanke c i e ion (Kolle and Sahami, 1996; Ali e is e al., 2010) educes he
ea u e se by inc emen ally excluding he leas ele an ea u es un il he educed subse is
sa is ac o y;
•La en seman ic indexing (Dee wes e e al., 1990), LSI, is a e-pa ame e iza ion echnique,
which uses he singula alue decomposi ion o he documen × e m ma ix o educe he
dimension o ea u e space;
62 Tex Classi ica ion
•Pa -O -Speech (POS) agging assigns g amma ical ca ego ies – such as e bs, nouns and
adjec i es – o e ms in a ex depending on hei de ini ion and con ex . Using POS ag-
ging in o ma ion o ea u e selec ion in ex is a ele an app oach o iden i y he mos
meaning ul e ms (Masuyama and Nakagawa, 2004; Gonçal es e al., 2006);
•Named En i ies (NE) may also p o ide e y ele an indexing e ms o ex in speci ic do-
mains. NE a e ecognized as one o he mos impo an indexing elemen s in biomedical
ex (Saha e al., 2009). NE Recogni ion (NER) aims o loca e and classi y e ms in o se-
man ic ca ego ies, such as p o ein o gene, in he biomedical domain, o company o place
in he business domain.;
•Synonyms eplacing is ano he echnique a ailable o educe he dimension o he ea u es
space in ex (Bolshako and Gelbukh, 2004). Synonyms may be eplaced by a unique e m.
Synonyms may be ob ained om lexical da abases, like Wo dNe 1, o simple synonyms
dic iona ies.
A di e en app oach aimed a educing he ime and compu a ional e o equi ed o ain a
classi ie is sub-sampling which uses only a educed sample o he a ailable da a o ain. Tex
bundling (Shih e al., 2003) is a sub-sampling echnique ha educes he numbe o aining in-
s ances by a e aging oge he small g oups o ins ances, such ha impo an s a is ical in o ma ion
is e ained. Tex bundling o ganizes ex s belonging o he same class in o homogeneous g oups.
Each o hese g oups is a e aged o gene a e a single bundled ex ha will eplace all he g oup in
he aining se . This app oach equi es a p e-labeled se ha migh be used o o ganize he co pus
in homogeneous g oups co esponding o he a ge classes.
4.1.2 Tex ep esen a ion
Once he ex p epa a ion s age desc ibed abo e is concluded, each documen is educed o i s
ep esen a i e ea u es. Then, a he nex s ep, ex ep esen a ion, his se o ea u es is encoded
in o a speci ic o ma ep esen ing he documen in an adequa e manne o au oma ic p ocessing.
1h p://wo dne .p ince on.edu/
4.1 P e-p ocessing 63
Classic ex models, iew a documen as a bag-o -wo ds, desc ibing ex documen s by he
e ms – wo ds o ph ases – appea ing in i . In hese models, each e m in a documen – known by
index e m – has a weigh associa ed o i .
The ec o space model (Sal on e al., 1997), p obably he mos commonly used model o
ex ep esen a ion, assigns eal non-nega i e weigh s o index e ms. In his model, documen s
a e ep esen ed by ec o s in a mul i-dimensional Euclidean space. Each dimension in his space
co esponds o an index e m, a ele an e m ha is con ained in he documen collec ion and also
pa o he ocabula y in use. In he ec o model, index e m weigh s a e usually ob ained as a
unc ion o wo ac o s:
• he e m equency ac o , T F, a measu e o in a-clus e simila i y; compu ed as he numbe
o imes ha he e m occu s in he documen , no malized in a way as o make i independen
o documen leng h and
• he in e se documen equency ac o , IDF, a measu e o in e -clus e dissimila i y; weigh s
each e m acco ding o i s disc imina i e powe in he en i e collec ion.
The deg ee o simila i y o documen s is e alua ed as he co ela ion be ween he ec o s ep-
esen ing he documen s. This is usually quan i ied by he cosine o he angle be ween he wo
ec o s.
Some p oposals, dis inc om he adi ional ec o space model, y o explo e sequences o
cha ac e s o wo ds, known as n-g ams (Ca na and T enkle, 1994; Lodhi e al., 2002; Zhang and
Zhu, 2007; Rahmoun and Elbe ichi, 2007).
S uc u ed models (Baeza-Ya es and Na a o, 1996), combining in o ma ion on ex con en
wi h in o ma ion on he documen s uc u e, a e also a ailable al hough no as popula as bag-o -
wo ds models. A he end o he 80’s and h oughou he 90’s, a ious s uc u ed ex e ie al
models ha e been p oposed (Chak aba i, 2003), such as non-o e lapping lis model, p oximal
nodes model (Na a o and Baeza-Ya es, 1995), simple conco dance lis models (Dao e al., 1997),
pa h p e ixing and PAT exp essions (Salminen and Tompa, 1994). These models, ha explo e
he s uc u al cha ac e is ics o he documen s, a e mo e di ec ed o in o ma ion e ie al (Baeza-
Ya es and Ribei o-Ne o, 1999), whe e he goal is o ank documen s by hei ele ance o a gi en
70 Tex Classi ica ion
2004; Zhang and Zhou, 2005).
In hie a chical classi ica ion i is also common o b eak down he o iginal p oblem in o a se
o la p oblems o simplici y easons. These app oaches, howe e , do no ake in o accoun he
in o ma ion con ained in he hie a chical s uc u e o he concep o lea n (Kolle and Sahami,
1997; Ki i chenko e al., 2006). Top-down, o le el-based, app oaches, ake in o accoun he
hie a chical na u e o he a ge concep a a local le el (Sun and Lim, 2001). These app oaches
build la classi ie s o lea n classi ica ion models ha can p edic he classes a each le el o
he hie a chy. These la classi ie s a e hen applied sequen ially a all le els in he hie a chy
ha a e deemed ele an o a gi en ins ance by he p e ious le el classi ie . The p ocess s ops
when a ce ain le el classi ie does no ind any ele an class o he ins ance a hand a i s own
le el o when he p ocess eaches a lea node. Global app oaches o hie a chical classi ica ion,
known by big-bang (Sun and Lim, 2001; Ki i chenko e al., 2006), build a single classi ie able
o disc imina ing all he classes in he hie a chy aking in o conside a ion he exis ing hie a chical
ela ionships.
4.3 Lea ning se ings
The applica ion o machine lea ning echniques o classi ica ion p oblems gene ally equi es wo
dis inc s ages: (1) he lea ning s age – when he classi ie is lea ned, ha is he algo i hm builds
a model o he concep o be lea ned based on aining and es da a – and (2) he p oduc ion
s age – when he p e iously lea ned model is applied o unseen ins ances in o de o classi y
hem. The lea ning s age demands o a sample o he a ge popula ion ha is o be pa i ioned in
a aining se and a es se . The need o label ins ances in his sample, acco ding o he speci ic
a ge concep , is p obably one o he mos expensi e asks expe ienced du ing all he classi ica ion
p ocess. The e o e, i becomes a co e aspec o ake in o conside a ion.
I espec i ely o he lea ning se ing in use, some a ge classes may no be lea nable o se e al
easons (Schü ze e al., 2006), such as, ha ing ew ins ances a ailable in he co pus o using a ex
model ha is no exp essi e enough o he pu pose o he classi ica ion ask – he bag-o -wo ds
model, o ins ance, does no ake in o conside a ion he ela i e o de o wo ds which migh be o
c ucial impo ance.

4.3 Lea ning se ings 71
When bo h aining and es se s a e ully labeled, we a e in p esence o a supe ised lea ning
se ing. On he o he ex eme, i none o he aining ins ances is labeled, we a e in p esence
o unsupe ised lea ning. When he aining da a is pa ially labeled, we a e in p esence o a
semi-supe ised lea ning se ing. Benne e al. (Benne and Demi iz, 1998) u he classi y semi-
supe ised lea ning p oblems as ei he semi-supe ised clus e ing, when he numbe o labeled
ins ances is small when compa ed o he dimension o he aining se , o ansduc ion p oblems,
when he numbe o labeled ins ances is la ge when compa ed o he aining se dimension. The
ansduc ion p oblem e e s o he es ima ion o he alue o a classi ica ion unc ion a a gi en
ins ance, which opposes o he s anda d induc i e lea ning p oblem o es ima ing he classi ica ion
unc ion o all possible ins ances and hen using he ixed unc ion o deduce i s alue a a gi en
ins ance.
The supe ised se ing equi es he ull da ase , om whe e he aining and es samples a e
ob ained, o be labeled o , a leas , ha he e is a la ge numbe o labeled ins ances om each class.
This is one majo d awback in his se ing, conce ning ex classi ica ion, because o he high cos
o labeling ex documen s. The p ocess o manually assigning labels o ex documen s is bo h
ime consuming, inaccu a e and subjec o incon ollable ac o s a ising om human na u e (Mac-
skassy e al., 1998) – wo use s wi h he same skills may classi y he same page di e en ly o he
same use may classi y he same page di e en ly a di e en momen s o ime. In opposi ion o
his passi e lea ning p ocess, ac i e lea ning (Chap e s 2 and 3) gi es he lea ne he abili y o
selec which ins ances should be included in he aining se . Ac i e lea ning (AL) educes he
amoun o labeling ha needs o be done h ough selec i e sampling o unlabeled da a. In AL
he lea ne examines a collec ion o unlabeled ins ances and selec s he mos in o ma i e ones,
equi ing an anno a o o label he selec ed ins ances, and i e a i ely e- ains on he augmen ed
se o labeled aining examples.
In he unsupe ised se ing he e is no p io knowledge on labels, nei he on he labels o
each documen no e en on he labels hemsel es. Clus e ing algo i hms o ganize documen s in
homogeneous g oups, based on hei simila i y, o ming pa i ions o he da ase ha minimize
in a-g oup a iance and maximize in e -g oup a iance.
Semi-supe ised lea ning echniques a e pa icula ly in e es ing when he p ocess o labeling
aining da a is expensi e and ime consuming, as is he case o labeling ex documen s. In his
72 Tex Classi ica ion
se ing, classi ie s a e w apped by some me hod in o de o ake ad an age o unlabeled documen s.
Se e al app oaches ha e been p oposed o sol e he semi-supe ised lea ning p oblem:
•Boo s apping (Jones e al., 1999) is a simple i e a i e me hod. A each i e a ion, labeled
ins ances a e used o lea n a classi ie . This classi ie is applied o label unlabeled ins ances;
hose whe e he e is enough e idence in a o o a ce ain label agains he o he s a e added
o he labeled se . The algo i hm p oceeds i e a i ely un il con e gence.
•Usage o Expec a ion-Maximiza ion (Nigam e al., 2000) (EM) o es ima e maximum a pos-
e io pa ame e s o a gene a i e ex classi ica ion model.
•Co- aining (Blum and Mi chell, 1998) is a supe ised lea ning me hod, pa icula ly use ul
when i is equi ed o combine sou ces o e idence o igina ed o m e y dis inc spaces –
pa icula ly i hey ha e a he di e en dimensions and scales, which may bias he agg ega-
ion o measu es om hese dis inc sou ces. Wi h co- aining dis inc classi ie s keep dis-
junc i e, independen ea u e se s and hei es ima es a e ne e di ec ly consolida ed; ins ead
his me hod uses he es ima es o one classi ie o ain o he s. The applica ion o co- ain-
ing equi es he exis ence o dis inc and independen se s o ea u es. Blum e al (Blum and
Mi chell, 1998) apply co- aining o Web documen classi ica ion, a ield whe e he ea u es
a e na u ally sepa able in o disjoin se s, such as ex in he page i sel and wo ds appea ing
in he in-links o he page, and wo classi ie s, one o each ea u e se , can be buil .
•E o Co ec ing Ou pu Code (Die e ich and Baki i, 1995) (ECOC) is a me hod ha con-
e s a K-mul i-class p oblem in a se o L bina y p oblems (Wi en and F ank, 2000). Any
bina y classi ie can hen be used o lea n hese L p oblems. ECOC assigns o each class a
unique bina y s ing, he code wo d, whe e each bi is p edic ed by one o he bina y classi-
ie s. The p edic ed class is he one whose code wo d is closes o he code wo d p oduced
by he se o he L bina y classi ie s. The dis ance be ween code wo ds is compu ed by he
Hamming dis ance, which is calcula ed as he numbe o di e en bi s in bo h code wo ds.
Ghani (Ghani, 2001) desc ibes a me hod o semi-supe ised lea ning ha uses he ECOC
me hod bundled wi h co- aining echniques in o de o lea n he bina y classi ie s.
4.4 Tex classi ie s 73
•T ansduc ion (Gamme man e al., 1998) is na u ally ela ed o ins ance based lea ning. In
ansduc ion we a e in e es ed in he classi ica ion o a pa icula ins ance a he han in a
gene al ule o classi ying any u u e ins ance.
•Coaching (Tibshi ani and Hin on, 1998) is a echnique ha applies when we a e in he
p esence o wo dis inc se s o p edic i e a iables bu only one o hese will be a ailable
on he u u e examples o classi y. Coaching echniques use one o he se s o p edic i e
a iables o coach he o he se how o imp o e p edic ion in he absence o he o me .
4.4 Tex classi ie s
Many classi ica ion p oblems a e bina y in na u e: a gi en example ei he belongs o some speci-
ied concep o i does no . In ex ca ego iza ion we a e usually in e es ed in se s o classes wi h
mo e han jus wo dis inc classes: he classi ica ion p oblem is equen ly a mul i-class p oblem.
One common app oach o mul i-class p oblems, alid o some classi ie s, is o use a se
o bina y classi ie s, each one esponsible o de e mining he ele ance o he documen as o
one speci ic class. The ele ance sco es o each one o he indi idual bina y classi ie s a e hen
combined in o de o p o ide he inal answe .
Se e al ypes o classi ie s used in machine lea ning in abula , s uc u ed da a, a e also applied
o uns uc u ed high-dimensional p oblems like ex classi ica ion.
4.4.1 Rochio
Rochio’s algo i hm (Joachims, 1997) is a classic me hod o documen ca ego iza ion in In o ma-
ion Re ie al2(Manning e al., 2008). In his me hod he aining examples a e used o build a
p o o ype ec o o each class. The p o o ype ec o o each class is compu ed as he a e age
ec o o e all he aining documen ec o s ha belong o he class. A new documen is classi ied
acco ding o he dis ance measu ed be ween he documen ec o and he class p o o ype ec o s.
2The pu pose o In o ma ion Re ie al is no o assign classes o documen s bu o ank documen s acco ding o
hei simila i y o a gi en que y documen – usually a use que y speci ied h ough a se o keywo ds.
74 Tex Classi ica ion
4.4.2 K-Nea es -Neighbo s
K-Nea es -Neighbo s (KNN) is an ins ance based classi ie which has been demons a ing good
pe o mance in pa e n ecogni ion and ex ca ego iza ion p oblems (Yang and Chu e, 1994; Yang
and Pede sen, 1997). This me hod classi ies a documen based on he cha ac e is ics o i s closes
kneighbo documen s in he inpu space.
In applica ions o ex ca ego iza ion, documen s a e usually ep esen ed in he adi ional ec-
o space model and he cosine be ween documen ec o s is also equen ly used as he simila i y
measu e. Classes migh be assigned by some o ing scheme – he majo i y class in he kneighbo s
is assigned, o ins ance – o , he classes ha ha e a ele ance sco e abo e a gi en h eshold a e
assigned o he documen (Yang e al., 2002).
KNN is a local me hod based on ins ances ha does no equi e any aining s age. Howe e ,
i demands o a ully p e-labeled se o ins ances.
4.4.3 Nai e Bayes
Nai e Bayes me hods (Kib iya e al., 2005; Kim e al., 2006; Jiang e al., 2011) use he join
p obabili y o e ms, i, and ca ego ies, cj, o es ima e ca ego y p obabili ies gi en a documen ,
P(cj| 1, 2,..., n). Dependencies be ween e ms a e igno ed, i.e., Nai e Bayes assumes ha he
condi ional p obabili y o a e m gi en a ca ego y is independen o he condi ional p obabili y o
any o he e ms gi en he ca ego y – he nai e assump ion.
When assuming e m independence, he condi ional p obabili y o documen d, gi en class cj
can be ob ained by Equa ion 4.9:
P(d|cj) = ∏
i
P( i|cj)(4.9)
Gi en a documen , he algo i hm compu es he pos e io p obabili ies o each one o he classes
and assigns o he documen he mos p obable one, cNB (Equa ion 4.10). Ma ginal, a p io i, class
p obabili ies, P(cj), may be es ima ed om he class dis ibu ion in he aining se .
cNB =a gmax
cj∈C
P(cj)∏
i
P( i|cj)(4.10)
4.4 Tex classi ie s 75
Compu ing class pos e io s equi es o es ima e he condi ional p obabili ies P( i|cj), which
may be ob ained by Equa ion 4.11:
P( i|cj) = ni+1
n+| ocabula y|(4.11)
In Equa ion 4.11, nis he o al numbe o e ms in all aining documen s belonging o ca ego y
cj,niis he equency o e m iand | ocabula y|is he o al numbe o dis inc e ms in he aining
co pus – he lexicon ca dinali y (Fang e al., 2001).
The cons an 1, added o he nume a o , and | ocabula y|, added o he denomina o , a e bo h
necessa y o a oid he 0/0 inde e mina e ha would a ise o he e ms, i, no appea ing in he
aining documen s belonging o class cj, hus o cing P(d|cj) = 0 in such cases.
Special ca e is equi ed when applying Nai e Bayes o high-dimensional da a, as is he case
o ex co po a. In ac , when dealing wi h e y la ge se s o a ibu es, p oblems ela ing o he
limi s o p ecision in compu e s may a ise. By na u e o p obabili y, P(x|y)<=1. I is also
ue ha lim
n→∞∏iP( i|cj) = 0. In p ac ice, i may happen ha ng ows la ge enough o he alue
o ∏iP( i|cj) o exceed below he limi s o double p ecision loa ing poin numbe s in mode n
compu e s. Compu ing he loga i hm o he condi ional p obabili ies as ollows, add esses his
p oblem (Equa ion 4.12).
a gmax
cj∈C"−log(P(cj)∏
i
P( i|cj)#=a gmax
cj∈C"−log(P(cj))−∑
i
log(P( i|cj))#(4.12)
4.4.4 Decision ees
Decision ees a e decision s uc u es buil o e a oo node con aining all he aining ins ances (Wi -
en and F ank, 2000; Lewis and Ringue e, 1994). The se o ins ances in any speci ic node is pa -
i ioned in o i s descendan nodes. This spli is made wi h he objec i e o minimizing he di e si y
o ca ego ies p esen a each node and i is ca ied ou un il no u he easonable imp o emen
is possible. A a gi en node, he spli is made as o assu e ha he sum o he di e si ies a he
child nodes is (much) less han he di e si y a he p esen node wi hou spli ing. The goal is o
maximize di e si y(node)−∑di e si y(childnodes).
Ca e mus be aken o a oid o e i ing which is usually done by p uning he decision ee.

76 Tex Classi ica ion
The e a e wo common p uning app oaches: pos o backwa d p uning and p e o o wa d p un-
ing (Wi en and F ank, 2000). In he pos-p uning app oach he ee is expanded as much as possible
a an ini ial s age and hen i is p uned back by emo ing hose nodes ha do no signi ican ly im-
p o e he homogenei y, hence he p edic i e powe , o he ee. P e-p uning app oaches e alua e
when o s op de eloping sub- ees du ing he ee cons uc ion p ocess.
The nodes a he bo om o he ee a e called he lea nodes. Any aining example belongs
o a ce ain lea node. Each lea node is hen assigned o a class and he e o a e o he lea is
he p obabili y o examples in ha lea node being misclassi ied. The global ee e o a e is a
weigh ed sum o all he lea nodes e o a es.
A key issue in decision ees is o decide which ea u es allow o he bes spli a each node,
he one ha gene a es he mos homogeneous pa i ion, and he de ini ion o he di e si y measu e
o use. One o he mos common di e si y measu es is en opy. The en opy o a gi en node, L, is
gi en by Equa ion 4.13.
−
K
∑
j=1
P(cj|L)log(P(cj|L)) (4.13)
Whe e P(cj|L)is he p obabili y o a aining example belonging o class cjgi en ha i
is loca ed in node L, which can be es ima ed by he ela i e equency o class cjin node L
(Equa ion 4.14):
P(cj|L) = Nj(L)
N(L)(4.14)
Nj(L)is he numbe o ins ances o class cjin node Land N(L)is he o al numbe o ins ances
in node L. Se e al algo i hms a e a ailable o g ow decision ees – CART, ID3, CHAID and C4.5
a e common app oaches (Aas and Eik il, 1999). The CART algo i hm (B eiman e al., 1984)
builds a bina y decision ee by spli ing he aining examples a a gi en node. The spli ing ule
is a linea combina ion o ea u es. The main ask is o decide, a each node, which combina ion
o ea u es pe o ms he bes pa i ion and wha is he spli alue. ID3 (Quinlan, 1986) spli s
nodes based on he unused a ibu e exhibi ing minimum en opy – i.e., maximum in o ma ion
gain. The C4.5 (Quinlan, 1993) algo i hm builds decision ees ha ha e wo child en pe node,
when spli ing on nume ic ea u es, bu migh ha e mo e hen wo child en pe node when he
spli ing ule is based on a ca ego ical a ibu e. In such cases, i is no limi ed o bina y ees ( wo
child en pe node) as is CART. CHAID (Kass, 1980) is also a popula algo i hm bu i is limi ed
4.4 Tex classi ie s 77
o ca ego ical ea u es; hus, i he domain unde s udy has nume ic a ibu es hen hey mus be
p e iously disc e ized.
4.4.5 Suppo Vec o Machines
Suppo Vec o Machines (SVM) (Joachims, 1998) a e based on he in ui ion ha a hype plane
ha is close o se e al aining examples will ha e a bigge chance o making e oneous decisions
han one which is as a as possible om all aining examples. The SVM algo i hm is a bina y
classi ie ha de ines a maximum ma gin hype plane be ween he con ex hulls o med by he
aining examples o each class. The maximum ma gin hype plane is he one ha is as a away
as possible om bo h con ex hulls – i is o hogonal o he sho es line connec ing he hulls,
in e sec ing i hal way. This hype plane may be de ined as a unc ion o he aining examples
ha a e closes o i , he suppo ec o s.
SVMs, like all disc imina i e classi ie s, a e non-pa ame ic. They do no assume any unde -
lying da a dis ibu ion besides he i ial assump ion ha aining and es ing ins ances all come
om he same popula ion, hus assuming iden ical dis ibu ions.
SVM implemen a ions equi e some pa ame e uning depending on he ype o ke nels in
use. Linea ke nels equi e no pa ame e s. Radial Basis Func ion (RBF) ke nels equi e se ing γ,
he wid h o he RBF ke nel, and he cos pa ame e , C, ha a ec s he ade-o be ween model
complexi y and aining e o , ha is, he accep able p opo ion o nonsepa able ins ances. I C
is oo la ge, a o ing model complexi y, we ha e a high penal y o nonsepa able ins ances which
may lead o s o e many suppo ec o s and o e i – C=1 is a small alue o C while C=1000
is high.
4.4.6 Explo ing o he ea u es besides con en ex
Hype ex (Web) documen s migh ha e some addi ional a ibu es besides con en ex . When
compa ed o plain ex his ype o documen s allows o a iche ep esen a ion ha migh be
explo ed in (hype ) ex classi ica ion. Yang e al (Yang e al., 2002) de ine i e ypes o egula i ies
ha migh be p esen in hype ex collec ions:
•no egula i y – he only place ha has ele an in o ma ion abou he class o he documen
is he documen i sel ,
78 Tex Classi ica ion
•encyclopaedia egula i y – documen s wi h a gi en class only link o documen s wi h he
same class,
•co- e e encing egula i y – some, o all, o he neighbo ing documen s belong o he same
class bu his class is dis inc om he documen class,
•p e-classi ied egula i y – he egula i y is p esen a he s uc u al le el whe e a single page
(hub) poin s o se e al pages which belong o he same class and
•me ada a egula i y – me ada a is a ailable om ex e nal sou ces and can be explo ed as
addi ional sou ces o e idence gene a ing new ea u es.
The au ho s hen de ine he ypes o ea u es ha should be used in o de o imp o e he classi-
ica ion ask o documen s belonging o each o hese egula i ies. Howe e , he e is no sugges ion
as o how o p e iously de e mine he ype o egula i y ha is p esen in a gi en documen collec-
ion. Acco ding o hei expe imen s di e en classi ie designs should be conside ed, depending
on which o he abo e egula i ies holds. Wi h no egula i y we would no expec any bene i om
using hype links and he sugges ion is o use la ex classi ie s, exclusi ely based on he ex o
he documen i sel . Encyclopaedia egula i y sugges s augmen ing he ex o each documen wi h
he ex o i s neighbo s, hus inc easing he numbe o wo ds ela ed o he opic ha a e p esen
in he documen ep esen a ion. In he case o co e e en ial egula i y, he ex o he documen
should also be augmen ed wi h he ex om i s neighbo s bu hese impo ed wo ds should be
ea ed as i hey came om a di e en ocabula y, o ins ance p e ixing hem wi h a speci ic ag.
I he collec ion has a p e-classi ied egula i y hen he e is no need o look a he documen ex ,
i su ices o look a he pages ha link o i and de e mine hei class. When ex e nal sou ces o
in o ma ion a e a ailable ha can be used as me ada a, me ada a egula i y, we can collec hem –
possibly elying on in o ma ion ex ac ion echniques.
Chak aba i e al (Chak aba i e al., 1998b) also es se e al ea u e se s, simila o he ones
sugges ed by (Yang e al., 2002): local ex , local ex conca ena ed wi h all neighbo s ex , local
ex plus neighbo s ex p e ixed wi h disc imina i e ags. They conclude ha nai e use o e ms
in he link neighbo hood o a documen can e en deg ade pe o mance. Yang e al (Yang e al.,
2002) ha e eached he same conclusion, which seems consensual. Al hough he use o ex ended
se s o ea u es a ailable in hype ex collec ions – including ex om hype link ancho s, he ull
4.5 Pe o mance measu es 79
ex om neighbo documen s, HTML ags, ca ego y dis ibu ion o e a linked neighbo hood,
me ada a a ailable om ex e nal sou ces – migh p o ide ich in o ma ion o he classi ica ion
ask, i is no gua an eed ha he use o such ea u es will imp o e pe o mance, which in gene al
is dependen o he speci ic documen collec ion.
A olksonomy3, a.k.a. social classi ica ion o collabo a i e agging is a dis ibu ed unsupe -
ised classi ica ion sys em c ea ed and main ained by a g oup o indi idual use s. Folksonomies
may su e om common p oblems ela ed o ag ambigui y, synonymous ags o mul ilingual-
ism (Robu e al., 2009; We zke e al., 2010; T a ne e al., 2011). Ne e heless, an empi ical
analysis o he complex dynamics o agging sys ems (Halpin e al., 2007) shows ha cohe en
ca ego iza ion schemes can eme ge om unsupe ised agging by g oups o use s.
4.5 Pe o mance measu es
Pe o mance e alua ion is one o he mos impo an issues in machine lea ning, in gene al. In
classi ica ion asks, his e alua ion can be based on se e al measu es. Common measu es in ex
classi ica ion a e ecall, p ecision, F-measu e – which agg ega es ecall and p ecision in a single
measu e – and accu acy o e o – wo complemen a y measu es o he e iciency o he lea ne .
Recall is de ined as he a io be ween he numbe o documen s co ec ly classi ied and he
o al numbe o documen s in he ca ego y. P ecision is de ined as he a io be ween he numbe
o documen s co ec ly classi ied and he o al numbe o documen s classi ied in he ca ego y.
Usually a classi ie exhibi s a ade-o be ween p ecision and ecall. These measu es a e
nega i ely co ela ed: imp o emen in ecall is made a he cos o p ecision and ice- e sa. I
is equen o ha e ex classi ie s ope a ing a he b eak-e en poin – he ope a ing poin whe e
ecall and p ecision ha e he same alue. The F-measu e combines ecall and p ecision in a unique
indica o (Equa ion 4.15):
Fβ=β2+1×p ecision × ecall
β2×p ecision + ecall (4.15)
whe e βis a pa ame e allowing di e en weigh ing o p ecision and ecall – p ecision and ecall
a e equally weigh ed when β=1. A he b eak-e en poin , ecall, p ecision and F1all ha e he
3h p:// ande wal.ne / olksonomy.h ml
86 P oblem S a emen
h oughou he lea ning p ocess. None o he classes o lea n a e p e iously speci ied wi h he
excep ion o wha can be in e ed om W.
We a e assuming an i e a i e lea ning p ocess wi h que ies being asked a each i e a ion.
When a que y is asked we assume ha he ue label yjo one unlabeled ins ance xjis al-
ways p o ided. A each i e a ion, i, du ing he lea ning p ocess, Liand Ui o m a se pa i-
ion o W.Liis he subse o ins ances in Wwhose ue label is known a i e a ion i,Li=
<xj,yj>:xj∈W∧yj=E(xj)∈C.Uiis he subse o ins ances inWwhose label is no known
a i e a ion i.
A domain expe , E, knowing he a ge concep and being awa e o each o he classes in C, is
always a ailable. A each i e a ion, i, his expe may be que ied o he label o a single unlabeled
ins ance xj∈Ui– ba ch mode AL was no conside ed – a a ce ain cos , A. When que ied o
a label, he expe always p o ides i s ue label, ∀j,E(xj) = yj,yj∈C– he expe Eis always
a ailable and always ce ain.
We assume he a ailabili y o a base classi ica ion algo i hm ha gene a es hypo heses – a.k.a.
classi ie s, h, om a se o labeled ins ances. The classi ie , hi, gene a ed a each i e a ion, i, om
Li, p edic s labels, ˆyj, o he ins ances xj∈Ui.
The u ili y o an ins ance a i e a ion i,B, is he alue o he imp o emen in he pe o mance
o h ha a que y may induce i included in Li+1.
5.4.2 Lea ning p ocess
In gene al, AL is an i e a i e p ocess. Each i e a ion has h ee phases: lea n, p edic and que y.
This lea ning p ocess is ini ialized om a se o p e-labeled ins ances, L1. This se mus con ain a
leas wo labeled ins ances om Wha ing dis inc labels. This imposi ion s ems om he ac ha
we need a leas a posi i e and a nega i e example o boo up a classi ie . Besides his imposi ion,
he e a e no o he cons ains o he building p ocess o L1. A co e conce n, howe e , mus be aken
in o conside a ion. Since we a e ocusing on cos educ ion and he cos o L1is N1A, assuming
N1is he numbe o p e-labeled ins ances in L1, hen N1should be small, ideally N1=2 as we
use. The ins ances in L1a e andomly selec ed om W. Thei labels a e eques ed o he domain
expe , E.

5.4 Fo mal p oblem se ing 87
Once his ini ializa ion se , L1, is buil we en e he i e a i e lea ning p ocess. A each i e a ion,
i, he labeled se Liis used o build a classi ie , hi, ha p edic s labels o all ins ances in Ui. Then,
he AL c i e ia in applied o selec a que y, qi om Ui. We a e assuming ha one single que y is
selec ed a each i e a ion. Ba ch mode AL was no conside ed.
The label o he selec ed que y is eques ed o he expe , E. The que y is hen added o he
labeled se , Liand emo ed om he unlabeled se , Ui. The labeled se o he nex i e a ion,
Li+1, is he union o he p e ious labeled se and he que y selec ed a he cu en i e a ion Li+1=
Li∪{<qi,E(qi)>}. The unlabeled se o he nex i e a ion, Ui+1is he se di e ence be ween
he p e ious unlabeled se and he que y selec ed a he cu en i e a ion Ui+1=Ui {qi}.Liand
Uialways o m a pa i ion o W. This p ocess i e a es un il a gi en s opping c i e ion is me .
The e i ica ion o he hypo heses unde in es iga ion depends on:
1. he ea ly iden i ica ion o ins ances whose labels ully co e C, i.e., he e should be a small
isuch ha ∀ck∈C,∃xj∈Li:E(xj) = ck:
2. simul aneously, a low e o a e should be obse ed a he p edic ions made by he lea ned
hypo hesis, i.e., he a io o he numbe o co ec p edic ions made by hion Uiby he
ca dinali y o Uishould be low when compa ed o cu en app oaches;
3. he iden i ica ion o e ec i e s opping c i e ia p e en ing cos ly useless que ies.
5.4.3 E alua ion o solu ions
The e alua ion o he solu ions o ou p oblem should be based on e o , an essen ial pe o mance
dimension in classi ica ion, and on he numbe o a ge classes ha a e known, i.e., ha ha e
ep esen a i e ins ances in L. Ha ing ep esen a i es om all classes in Cis a co e conce n in he
esea ch p oblem being in es iga ed.
A each i e a ion, i, he e o a e is e alua ed on he se o unlabeled ins ances, Ui– gene al-
iza ion e o . The numbe o known classes is e alua ed on he se o labeled ins ances, Li. Besides
he numbe o known classes in i sel , i is also impo an o eco d he i s ime ha a gi en class
is iden i ied, i.e., he i s i e a ion ou pu ing a que y being labeled wi h a gi en class, ck. We will
e e o his indica o as i s -hi . F om a b oade pe spec i e i is also impo an o e alua e he
minimum numbe o que ies ha a e equi ed o iden i y ep esen a i e ins ances o all he a ge
88 P oblem S a emen
classes. we de ine label disclosu e complexi y o his pu pose. All hese pe o menca indica o s
a e de ines in Sec ion 6.3.1.
Chap e 6
D-Con idence
Gi en a a ge concep wi h an a bi a y numbe o classes oge he wi h a sample o unlabeled
ins ances om he a ge space – he wo king se , W– ou pu pose is o build an accu a e classi ie
co e ing all a ge classes while posing as ew que ies as possible. A que y consis s o eques ing
he o acle, E, o p o ide he ue label, yj, o a speci ic ins ance, xj∈U.Uis he se o ins ances
in Wwhose label is no known. Que ying E o a label has a cos , A– he que ying cos – assumed
o be cons an h oughou he lea ning p ocess. The wo king se is assumed o be ep esen a i e o
he class space – he ep esen a i eness assump ion (Liu and Mo oda, 2001).
Ac i e lea ne s commonly sea ch o que ies in he neighbo hood o he decision bounda y
(Figu e 6.1a), whe e class unce ain y is highe . Howe e , he unce ain y egion, as pe cei ed
gi en cu en e idence, migh be unaligned wi h he eal a ge concep . The (pe cei ed) unce -
ain y egion is de ined (Cohn e al., 1994) as he a ea ha is no de e mined by a ailable in o -
ma ion, ha is, he se o ins ances in he wo king se such ha he e a e wo hypo heses ha a e
consis en wi h all aining ins ances ye disag ee on he classi ica ion o hose.
Limi ing ins ance selec ion o he pe cei ed unce ain y egion seems adequa e when he ain-
ing se is a ep esen a i e sample o he a ge concep in which case he pe cei ed unce ain y
egion is p obably consis en wi h he a ge concep . Class ep esen a i eness in he aining se is
assumed by he majo i y o ac i e lea ning (AL) app oaches. In such a scena io, selec ing que ies
om he unce ain y egion is e ec i e in educing e sion space.
Bu , wha i he eal unce ain y egion is no co ec ly o ully pe cei ed by he cu en hy-
po hesis? Unde such an assump ion, a o ing exploi a ion a he han explo a ion wi hholds he
89
90 D-Con idence
chances o achie e an ea ly comple e co e age o he a ge concep .
(a) Pe cei ed unce ain y egion (b) Real unce ain y egion
Figu e 6.1: Unce ain y egion (shaded). n ep esen s labeled ins ances om class cnand x ep e-
sen s unlabeled ins ances. We assume ha he concep o lea n has h ee dis inc classes, one o
which has no ye been iden i ied
6.1 The in ui ion
The ini ial s age o he lea ning p ocess, when s ill sea ching o exempla y ins ances co e ing
all a ge classes, is c i ical ega ding he labeling cos . While s ill missing labeled ins ances o
some a ge classes, he unce ain y egion pe cei ed by he ac i e lea ne (Figu e 6.1a) migh be
educed o a po ion o he eal unce ain y egion (Figu e 6.1b) o migh be se e ely biased. Being
limi ed o his pa ial e a ic iew o he concep , he lea ne may be misled and is mo e likely o
was e que ies, hus inc easing labeling cos a no bene i . The amoun o he unce ain y egion
ha he lea ne misses is ela ed o he numbe o a ge classes ha ha e no ye been iden i ied.
Ou in ui ion (Figu e 6.2) is ha que y selec ion should be based no only on classi ie con i-
dence bu also on dis ance o p e iously labeled ins ances. In he p esence o wo ins ances wi h
equally low con idence – say, Xaand Xbin Figu e 6.2 – we p e e o selec he one ha is a he
apa om wha we al eady know, i.e., om p e iously labeled ins ances – e e ing o Figu e 6.2
we would p e e o que y Xa han Xb.
6.2 The d-Con idence c i e ion 91
Figu e 6.2: Fo equally con iden ins ances p e e hose ha a e a om p e iously explo ed
egions in ins ance space
We expec ha an AL app oach ha exhibi s a high explo a o y po en ial a he ini ial phase o
he lea ning p ocess – while s ill sea ching o exempla y ins ances o some o he a ge classes
– and hen smoo hly shi s o a highe exploi a ion po en ial migh educe he amoun o was ed
que ies, hus educing he labeling cos . We sea ch o a que y selec ion c i e ion ha a o s
explo a ion – ends o selec s que ies om unexplo ed egions in ins ance space – a an ini ial
phase and hen, as he inpu space is becoming explo ed, u ns o a o exploi a ion.
6.2 The d-Con idence c i e ion
Many AL app oaches ely on classi ie con idence o selec que ies (Angluin, 1988) and assume
ha he p e-labeled se co e s all he labels o lea n. The pe o mance o hese app oaches is
ocused on accu acy, a o ing exploi a ion o e explo a ion. Ou scena io is somehow di e en :
we do no assume ha we ha e p e-labeled ins ances om all classes and, besides accu acy, we
a e mainly conce ned wi h he as iden i ica ion o ep esen a i e ins ances om all classes.
To achie e ou goals we p opose a new selec ion c i e ion, d-Con idence (Escudei o and Jo ge,
2012), which deals well wi h unde - ep esen ed classes. Ins ead o elying exclusi ely on classi ie
con idence we p opose o selec que ies based on he a io be ween classi ie con idence and he
dis ance o known classes. D-Con idence, weighs he con idence o he classi ie wi h he in e se
o he dis ance be ween he ins ance a hand and p e iously known classes.

92 D-Con idence
D-Con idence is expec ed o a o a as e co e age o ins ance space, exhibi ing a endency
o explo e unknown egions. As a consequence, i p o ides be e explo a o y beha io han con i-
dence alone. This d i owa ds unexplo ed egions and unknown classes is achie ed by selec ing
he ins ance wi h he lowes d-Con idence as he nex que y. Low d-Con idence combines low
con idence – p obably indica ing ins ances om unknown classes – wi h high dis ance o known
classes – poin ing o unseen egions in ins ance space. This e ec p oduces signi ican di e ences
in he beha io o he lea ning p ocess. Ac i e lea ne s ocused on he unce ain y egion, ask
que ies ha a e expec ed o na ow i down. The issue is ha he po ion o he unce ain y egion
ha is pe cei ed a a gi en momen is de e mined by he labels known a ha momen . Focusing
ou sea ch o que ies exclusi ely in his egion, while we a e s ill looking o exempla y ins ances
o some a ge classes ha a e no ye known, is no e ec i e gi en ou goals. Unknown classes
ha dly come by unless hey a e ep esen ed in he cu en unce ain y egion.
Algo i hm 6.1 p esen s d-Con idence, ou AL p oposal specially ailo ed o achie e a as class
ep esen a i e co e age.
Algo i hm 6.1 D-Con idence algo i hm
1: gi en W
2: compu e dis ance be ween ins ances in W
3: i=1
4: ini ialize L1
5: while no s opping c i e ia do
6: Ui=W−Li
7: Ci=dis inc class labels in Li
8: lea n hi om Li
9: apply hi o Uigene a ing con i(xj,ck),∀xj∈Ui,Ck∈Ci
10: o (xj∈Ui)do
11: o (ck∈Ci)do
12: dk
j=ClassDis (xj,ck)
13: dcon i(xj,ck) = con i(xj,ck)
dk
j
14: end o
15: dCon i(xj) = maxck(dcon i(xj,ck))
16: end o
17: qi=a gmin
xj
(dCon i(xj))
18: Li+1=Li∪<qi,E(qi)>
19: i++
20: end while
Wis he wo king se , a ep esen a i e sample o ins ances om he p oblem space. Liis a
6.2 The d-Con idence c i e ion 93
subse o W. Membe s o Lia e he ins ances in Wwhose labels a e known a i e a ion i.Ciis
he se o he class labels ha ha e ep esen a i e ins ances in Li.U, a subse o W, is he se o
he unlabeled ins ances p esen in he wo king se . A i e a ion i,Uiis he (se ) di e ence be ween
Wand Li;hi ep esen s he classi ie lea ned a i e a ion i;qiis he que y selec ed a i e a ion i;
con i(uj,ck)is he pos e io con idence on class ckgi en ins ance uj, a i e a ion i.
The co e o ou p oposal is he compu a ion o he d-Con idence alue o unlabeled ins ances.
Tha is accomplished a he ou e o cycle in Algo i hm 6.1, a s eps 10 o 16, as explained nex .
6.2.1 Compu ing d-Con idence
D-Con idence is ob ained as he a io be ween con idence and dis ance be ween unlabeled in-
s ances and known classes (Equa ion 6.1). We may iew d-Con idence as he con idence pe uni
dis ance.
dCon (xj) = max
k con (xj,ck)
dk
j!(6.1)
Fo a gi en unlabeled ins ance, xj∈Ui, he classi ie gene a es he pos e io con idence w. . .
known classes (s ep 9 in Algo i hm 6.1). The dis ance be ween one unlabeled ins ance xjand all
labeled ins ances belonging o class ck∈Ci,dk
j, is compu ed by ClassDis () a s ep 12. A ou
cu en implemen a ion his dis ance indica o , dk
j, is he median o he dis ances be ween ins ance
xjand all labeled ins ances in Libelonging o class ck. We expec he median o so en he e ec
o ou lie s. The Euclidean me ic was p e iously used, a s ep 2, o compu e he dis ance be ween
all pai s o ins ances in W. We compu e dcon i(xj,ck), he ma ginal d-Con idence o each known
class ck∈Cigi en xj, by di iding class con idence by he agg ega ed dis ance o ha class (s ep
13).
The maximum d-Con idence on indi idual classes ck∈Ci o a gi en ins ance xj∈Uiis inally
compu ed (s ep 15) as he d-Con idence o he ins ance a i e a ion i,dCon i(xj).
I we now look a he i e a i e lea ning p ocess as a whole, we see ha a he ini ial phase he e
a e ew labeled ins ances – he ins ance space is ba ely explo ed – and he median o he dis ances
o know classes is high o many unlabeled ins ances and low o o he s. This high a iabili y will
ha e a big in luence in d-Con idence and will led i o selec que ies ha lie a apa om known
classes, hus exhibi ing a high explo a o y po en ial. When he ins ance space ge s mo e and mo e
94 D-Con idence
explo ed, he median o he dis ances o known classes is expec ed o become mo e homogeneous
among unlabeled ins ances and he con idence ac o o d-Con idence exe s i s in luence ising
he exploi a ion po en ial o d-Con idence.
D-Con idence is expec ed o dynamically shi be ween explo a ion and exploi a ion as he
lea ning p ocess i e a es. This dynamic shi ing is guided by he bond be ween he a iance o he
pos e io s gene a ed by hiand he a iance o he dis ance be ween membe s o Uiand Li.
Being based on he dis ance be ween wha is known and wha has no been explo ed ye ,
d-Con idence is also a obus app oach ha applies independen ly o he speci ic geome ic p op-
e ies o he ins ance space. D-Con idence au oma ically adap s o he inpu space s uc u e –
ha ing bo h Uand Lin o conside a ion – wi hou equi ing any p elimina y uning e o . This
cha ac e is ic o d-Con idence is expec ed o educe any se e e bias om he o iginal da a dis i-
bu ion ha may occu in AL app oaches ha a e exclusi ely based on con idence (Wang and Hua,
2011) and do no ake in o conside a ion he s uc u al p ope ies o he inpu space.
Also, his app oach does no incu in he o e head cos ha is imposed by he ew AL ap-
p oaches ha a e conce ned wi h he explo a ion e sus exploi a ion comp omise. Fo ins ance,
(Osugi e al., 2005; Ceb on and Be hold, 2009) a e wo o hese app oaches, bo h equi ing o
une wo pa ame e s guiding he ansi ion be ween explo a ion and exploi a ion.
SVM classi ie s – by de aul , we use SVM as he base classi ie – can be uns able wi h a small
aining se (Dagli, 2005). This is p obably due o he ac ha SVM con idence is e y high o
any ins ances lying a om he decision ma gin. The decision hype plane migh change signi i-
can ly om one i e a ion o he nex when he aining se is small and e en mo e when we do no
ha e an ini ial p e-labeled se co e ing all classes. As a consequence he se o ins ances whe e
he classi ie is highly con iden may also change om i e a ion o i e a ion a he easily. D-Con i-
dence me ges wo complemen a y aspec s o he wo king da ase : dis ance, which is measu ed in
he inpu ea u es space, and con idence, which is compu ed in he base classi ie ea u es space.
Adding he con ibu ion o he dis ance measu ed in he inpu space is expec ed o imp o e he
obus ness o d-Con idence and con ibu e o imp o e he s abili y o he lea ning p ocess when
using SVM base classi ie s.
6.2 The d-Con idence c i e ion 95
6.2.2 Baseline c i e ia
D-Con idence agg ega es wo baseline AL c i e ia, con idence and dis ance (based on a hes -
i s ). The con idence gene a ed a each i e a ion by he cu en e sion o he base classi ie ,
con i(xj,ck), is he pos e io p obabili y o class ckgi en xj. The agg ega ed dis ance o known
classes, dk
j, is compu ed by ClassDis (xj,ck)based on he indi idual dis ances be ween each pai
o ins ances (Equa ion 6.2). Indi idual pai dis ances migh be compu ed by any dis ance unc ion
– a he cu en implemen a ion we a e using he Euclidean dis ance. ClassDis (xj,ck)is any
agg ega ion unc ion compu ed on he indi idual pai dis ances be ween one unlabeled ins ance
xj∈Uiand e e y labeled ins ance om class ck∈Ci– a he cu en implemen a ion we a e using
he median.
ClassDis i(xj,ck) = dk
j=mediandis xj,Lk
i (6.2)
Lk
iis he se o labeled ins ances known a i e a ion i ha belong o class ck, ha is, Lk
i=
<xj,yj>∈Li:yj=ck.
6.2.3 E ec o d-Con idence on SVM
The ou pu o SVM classi ie s is he signed dis ance o he decision bounda y measu ed in e ms
o hal ma gin wid h – an ins ance loca ed on he decision bounda y ou pu s 0 while an ins ance
which is collinea wi h suppo ec o s o class +1 gene a es an ou pu 1 and an ins ance which
is collinea wi h suppo ec o s o class −1 gene a es an ou pu −1. An ins ance wi h a dis ance
o he decision bounda y ha is n imes he dis ance be ween he bounda y and a suppo ec o
ou pu s n. This dis ance, d, is ans o med in o p∈[0,1], a measu e o he pos e io con idence o
he lea ne on class +1.
I , as is commonly he case, his ans o ma ion is based on logis ic eg ession (Equa ion 6.3),
he SVM classi ie will be e y con iden on any ins ance loca ed a om he decision bounda y
(Figu e 6.3a), educing he chances o selec que ies ha a e a om he cu en unce ain y
egion.
p= (d) = 1
1+e−d(6.3)
102 D-Con idence
(a) ds0000 (b) ds0001 (c) ds0010 (d) ds0011
(e) ds0100 ( ) ds0101 (g) ds0110 (h) ds0111
(i) ds1000 (j) ds1001 (k) ds1010 (l) ds1011
(m) ds1100 (n) ds1101 (o) ds1110 (p) ds1111
Figu e 6.4: A i icial da ase s

6.3 Expe imen al se up 103
Table 6.1: A i icial da ase s and hei p ope ies
Da ase p ope ies Da ase
Alignmen Dis ibu ion Topology Sepa abili y
non-collinea
balanced
polymo phic sepa able ds0000
o e lapping ds0001
isomo phic sepa able ds0010
o e lapping ds0011
imbalanced
polymo phic sepa able ds0100
o e lapping ds0101
isomo phic sepa able ds0110
o e lapping ds0111
collinea
balanced
polymo phic sepa able ds1000
o e lapping ds1001
isomo phic sepa able ds1010
o e lapping ds1011
imbalanced
polymo phic sepa able ds1100
o e lapping ds1101
isomo phic sepa able ds1110
o e lapping ds1111
•Cle eland hea disease (imbalanced class dis ibu ion),
•a andom sample om Vowels (highe numbe o dis inc classes han he o he s),
•a sample om Sa log (highe numbe o a ibu es han he o he s) and
•a sample om Poke (highly imbalanced class dis ibu ion).
These da ase s we e selec ed o hei p ope ies, mainly due o hei dis inc class dis ibu ions
(Table 6.2).
Table 6.2: Class dis ibu ion in abula da ase s
Da ase #ins ances # ea u es 1 2 3 4 5 6 7 8 9 10 11
I is 150 4 50 50 50
Cle eland 298 13 161 53 36 35 13
Vowels 330 10 30 30 30 30 30 30 30 30 30 30 30
Sa log 500 36 125 118 96 67 48 46
Poke 500 10 270 170 34 12 4 3 3 2 1 1
The Poke da ase wi h a highly imbalanced class dis ibu ion causes some excep ions. The
wo classes wi h equency 1 om he Poke da ase a e ne e selec ed as ini ial classes. Two ou
o he 10 olds used o c oss alida ion do no include all he 10 classes in he Poke da ase .
104 D-Con idence
Fo his eason, he maximum numbe o classes ound when using his da ase is below he o al
numbe o classes in he da ase , since his igu e is es ima ed as a mean o e all alida ion olds.
A his second e alua ion phase we ha e in es iga ed he pe o mance o d-Con idence when
using, besides SVM, neu al ne wo ks (NNET) and decision ees (RPART) as base classi ie s.
Da ase s used in he hi d phase Fo he hi d phase we ha e selec ed wo high-dimensional
uns uc u ed da ase s. Two samples om adi ional ex co po a we e used:
•a s a i ied sample om he 20 Newsg oups co pus (NG), con aining 500 documen s de-
sc ibed by 10333 e ms and
•a s a i ied sample om he R52 se o he Reu e s-21578 collec ion (R52), con aining 1000
documen s desc ibed by 6019 e ms.
The NG da ase has documen s om 20 dis inc classes while he R52 da ase has documen s om
52 dis inc classes. Tex documen s a e modeled wi h TF×IDF weigh ing. These da ase s ha e
been selec ed o hei dis inc class dis ibu ions. The class dis ibu ion in NG is ai ly balanced
(Figu e 6.5a) wi h a maximum equency o 35 and a minimum equency o 20 while he R52
da ase p esen s an highly imbalanced class dis ibu ion (Figu e 6.5b). The mos equen class in
R52 has a equency o 435 while he leas equen has only wo ins ances in he da ase . This
da ase has 42 classes, ou o 52, wi h a equency below 10 om which 31 ha e a equency below
i e.
(a) NG co pus (b) R52 co pus
Figu e 6.5: Class dis ibu ions in ex co po a
We a e elying on SVM as ou base classi ie by de aul . Al hough he pe o mance o ex
classi ie s depends hea ily on he documen collec ion a hand (Yang and Pede sen, 1997), some
6.4 E alua ion 105
classi ie s, pa icula ly SVM and K-Nea es -Neighbo s seem o ou pe o m o he s in he majo i y
o he domains (Joachims, 1998). A ew p ope ies o ex documen s – high dimensional ea u e
spaces, many i ele an ea u es, documen ec o s’ spa si y and he ac ha mos ex ca ego-
iza ion p oblems a e linea ly sepa able – jus i y he dominance o SVM in ex ca ego iza ion
asks (Joachims, 1998).
6.4 E alua ion
The e alua ion o d-Con idence desc ibed in his chap e in es iga es i s abili y as a que y selec ion
c i e ion in compa ison o i s baseline and o he s a e-o - he-a c i e ia. In pa icula , we in es-
iga e he abili y o d-Con idence o educe he labeling e o needed o co e all a ge classes
wi hou comp omising accu acy. The esul s ob ained in he h ee phases o ou e alua ion plan
a e discussed in Sec ions 6.4.1 o 6.4.3. The esul s om he wo k o ou colleagues Mo a e
al. (Mo a e al., 2012) a e discussed in Sec ion 6.4.4.
6.4.1 Ins ance space co e age
This phase aims o assess he abili y o d-Con idence o achie e a as co e age o inpu space and
as e ie al o ep esen a i e ins ances om all a ge classes. Fas , in his sense, means wi h ew
que ies which is equi alen o low cos . We also wan o e alua e he accu acy o he classi ica ion
models gene a ed by d-Con idence. A e we ading accu acy o co e age? Ano he aim o hese
expe imen s is o in es iga e how he geome ic s uc u e o he da ase impac s he pe o mance
o d-Con idence.
In his phase we ha e used SVM wi h RBF ke nels as he base classi ie . We ha e eco ded,
a e e y i e a ion, he newly added que y, he numbe o dis inc labels known o he classi ie
and gene aliza ion e o o all selec ion c i e ia unde e alua ion – a hes - i s , con idence and
d-Con idence. F om hese, we ha e compu ed, on each da ase , mean co e age, mean numbe
o que ies equi ed o iden i y he hidden class – which in his case is equi alen o LDC since
#C=3 and #C1=2 – and mean gene aliza ion e o in each i e a ion o e all c oss alida ion
olds (Table 6.3).
106 D-Con idence
Table 6.3: Co e age (Co ), mean numbe o que ies o iden i y one ins ance om he unknown
class (LDC) and e o (E ) wi h an SVM classi ie on a i icial da a. Mean co e age and e o a e
compu ed o e all i e a ions in all c oss alida ion olds o e e y a i icial da ase . s ands o
a hes - i s , cs ands o con idence and dc s ands o d-Con idence
Da ase Co ( ) Co (c) Co (dc) LDC ( ) LDC (c) LDC (dc) E ( ) E (c) E (dc)
ds0000 0.745 0.967 0.979 46 20 60.209 0.038 0.023
ds0001 0.756 0.922 0.937 42 19 22 0.281 0.192 0.174
ds0010 0.716 0.920 0.908 71 19 20.104 0.032 0.014
ds0011 0.684 0.893 0.886 24 27 30.198 0.137 0.104
ds0100 0.838 0.897 0.945 180 9 10 0.185 0.032 0.046
ds0101 0.721 0.914 0.933 66 35 13 0.221 0.112 0.106
ds0110 0.725 0.877 0.894 147 28 20.149 0.052 0.019
ds0111 0.675 0.875 0.870 149 34 11 0.219 0.111 0.086
ds1000 0.767 0.908 0.974 89 29 30.352 0.077 0.088
ds1001 0.743 0.953 0.976 74 11 70.411 0.240 0.255
ds1010 0.771 0.893 0.958 180 24 20.238 0.039 0.016
ds1011 0.704 0.911 0.933 92 25 60.282 0.174 0.144
ds1100 0.769 0.883 0.819 104 55 13 0.222 0.183 0.198
ds1101 0.767 0.852 0.835 89 22 11 0.276 0.188 0.178
ds1110 0.766 0.862 0.877 18 29 20.153 0.052 0.028
ds1111 0.667 0.803 0.827 7 32 30.220 0.128 0.120
I is 0.720 0.918 0.949 84 18 30.304 0.134 0.082
Ins ance space co e age is he pe cen age o ins ances in W ha lie on a gi en neighbo hood
o any labeled ins ance. We assume ha , a any i e a ion i, hose ins ances yielding a dis ance
o any labeled ins ance in Lilowe han 1
10 o he maximum dis ance be ween ins ances in Wa e
co e ed. The p og ess o ins ance space co e age is depic ed in Figu e 6.6 whe e we can see he
pe cen age o co e ed ins ances a e que ying ou , 16 and 64 ins ances.
Figu e 6.6: P og ession o ins ance space co e age as new que ies a e added. cs ands o con i-
dence; dc s ands o d-Con idence
On e e y da ase we ha e compu ed mean co e age and mean e o o e all i e a ions and
o e he 10 olds o a hes - i s , con idence and o d-Con idence. This p ocess gene a ed h ee
6.4 E alua ion 107
pai ed samples wi h he obse ed ins ance space co e age plus h ee pai ed samples wi h obse ed
e o . Wi h hese samples we ha e es ed he signi icance o he di e ences o he means using
pai ed - es s.
The numbe o que ies equi ed o iden i y one ins ance om he unseen class is es ima ed as
he a e age o e he 10 olds o a hes - i s , con idence and d-Con idence. These means ha e
also been es ed o equal means wi h pai ed - es s. S a is ically di e en means, a a signi icance
le el o 5%, a e bold aced in Table 6.3.
D-Con idence consis en ly imp o es ins ance space co e age o e bo h con idence and a -
hes - i s . This beha io is obse ed i espec i ely o da ase p ope ies. The e is a clea domi-
nance o bo h d-Con idence and con idence when compa ed o a hes - i s .
D-Con idence ou pe o ms con idence on six ou o eigh collinea da ase s – collinea da ase s
ha e he i s nume ical digi on hei name se o 1,ds1??? (see Sec ion 6.3.2). This same igu e is
obse ed on balanced da ase s (ds?0??), on polymo phic (ds??0?) and also on sepa able (ds???0)
da ase s. On all he o he g oups o da ase s – non-collinea (ds0???), imbalanced (ds?1??), iso-
mo phic (ds??1?) and o e lapping (ds???1) – d-Con idence ou pe o ms con idence on i e ou
o eigh da ase s.
The esul s on polymo phic da ase s a e pa icula ly in e es ing since hese con ain classes
ha ing dis inc clus e s in di e en egions o ins ance space. Al hough he co e age e iciency
o d-Con idence is no as clea as in isomo phic da ase s, d-Con idence s ill ou pe o ms bo h
con idence and a hes - i s .
F om Figu e 6.6 we obse e ha con idence gene ally achie es a be e co e age han d-Con-
idence a e he ini ial ou que ies – which happens in 10 ou o 16 da ase s. A e hese ew
ini ial que ies his end e e ses and d-Con idence imp o es o e con idence. A e 16 que ies
d-Con idence ou pe o ms con idence in 14 ou o 16 da ase s.
Label disclosu e complexi y When analyzing LDC – which, in his case is equi alen o he
numbe o que ies equi ed o i s hi an ins ance o he hi d class – we obse e a clea dominance
o d-Con idence agains con idence and a hes - i s . D-Con idence ou pe o ms con idence and
a hes - i s in 14 ou o 16 da ase s. Con idence p esen a lowe LDC a ds0001 and ds0100. The
o e all mean LDC on hese a i icial da ase s is 7 o d-Con idence, 26 o con idence and 86 o

108 D-Con idence
a hes - i s – a clea ad an age o d-Con idence. This is a co e esul add essing ou pu poses.
The low LDC obse ed in hese a i icial da ase s is a e y p omising indica o o he compe ence
o d-Con idence o achie e low-cos disclosu e o all a ge classes.
E o Somehow su p isingly, we obse e ha d-Con idence also imp o es on e o . D-Con-
idence ou pe o ms bo h con idence and a hes - i s in 11 ou o 16 da ase s while con idence
achie es he be e pe o mance in ou ou o 16. In o he wo ds, imp o ed class co e age is no
done a he cos o inc easing e o .
Clus e mo phism seems o ha e impac on e o . F om all he isomo phic da ase s, d-Con-
idence has a signi ican lowe mean e o han ha o con idence and a hes - i s on se en ou
o eigh da ase s. Howe e , on polymo phic da ase s, d-Con idence has simila esul s o hose o
con idence – d-Con idence ou pe o ms con idence on h ee ou o eigh da ase s, while he in e se
occu s on ou da ase s.
Pe o mance e alua ion on I is Such esul s on simula ed da a ha e been checked on a eal
da ase (Figu e 6.7). We ha e applied his same expe imen al plan o he I is da ase (F ank and
Asuncion, 2010). The esul s we ha e achie ed on I is con i m he esul s on a i icial da a. In-
s ance space co e age is mo e e icien when using d-Con idence and his is no achie ed a he
cos o inc easing e o which, in ac , also imp o es.
Figu e 6.7: Ins ance space co e age on he I is da ase as new que ies a e added
6.4 E alua ion 109
On he I is da ase we ha e also eco ded he numbe o que ies equi ed o ge a ull co e age
o ins ance space. Ins ance space is assumed o be ully co e ed when all ins ances in he wo king
se lie close han a ce ain p ede ined dis ance om a leas one labeled ins ance. This p ede ined
dis ance has been se o 1
10 – he ini ial se ing – and hen o 1
8,1
6and 1
4o he maximum dis ance
be ween ins ances. I is expec ed ha he numbe o que ies equi ed o achie e a ull co e age
dec eases as he adius o he assumed co e ed neighbo hood inc eases. This should be mo e
e iden when newly added que ies belong o emo e egions in ins ance space hus ha ing educed
neighbo hood in e sec ions wi h p e iously co e ed ins ances. Ou pu pose is o e alua e whe he
d-Con idence is in ac explo ing unseen egions in ins ance space mo e e icien ly han con idence
– i s di ec compe i o .
We ha e obse ed ha he numbe o que ies equi ed o ge a 100% co e age o ins ance
space wi h con idence dec eases om 84 o 35 – a educ ion o 58% in he labeling e o –
when he neighbo hood adius goes om 1
10 o 1
4. On his same scena io, d-Con idence labeling
e o o ge a ull co e age is educed om 51 o 8 que ies – a educ ion o 84%. These esul s
con i m ha d-Con idence selec s que ies om emo e egions in ins ance space mo e e icien ly
han con idence.
The pe o mance o d-Con idence on I is suppo s he o eseen imp o emen s o e i s baseline
c i e ia. The I is LDC o a hes - i s is 84, o con idence i is 18 and o d-Con idence, h ee.
The mean e o is 30.4% o a hes - i s , 13.4% when using con idence and 8.2% when using
d-Con idence.
Impac o inpu space geome y The di e ence be ween a hes - i s ’s pe o mance and he
o he c i e ia is e y signi ican . We ha e ques ioned whe he a hes - i s unde -pe o mance is
ela ed o some bias in oduced by ou a i icial da ase s and/o he indica o we a e using o assess
ins ance space co e age. Ou hypo hesis is ha i is ela ed o bo h he opology o he da ase –
mainly wi h he ela ion be ween dense and spa se egions in ins ance space – and he indica o in
use o measu e co e age.
Being guided by dis ance only, a hes - i s migh be di ec ed o dis an egions ha a e spa se.
This beha io does no con ibu e o ins ance space co e age he way we ha e de ined i – numbe
o ins ances lying in some neighbo hood o all labeled ins ances in Li.
110 D-Con idence
Table 6.4: A i icial da ase s so ed by dec easing o de o a hes - i s co e age
Da ase Co ( )
ds0100 0.838
ds1010 0.771
ds1100 0.769
ds1000 0.767
ds1101 0.767
ds1110 0.766
ds0001 0.756
ds0000 0.745
ds1001 0.743
ds0110 0.725
ds0101 0.721
ds0010 0.716
ds1011 0.704
ds0011 0.684
ds0111 0.675
ds1111 0.667
So ing he a i icial da ase s by dec easing o de o a hes - i s mean co e age (see Table 6.4)
p o ides some e idence on his ques ion.
We may obse e ha in he op eigh da ase s he e a e six sepa able da ase s. Ou sepa able
da ase s ha e dense clus e s dis an om each o he (see Figu e 6.4). This is an adequa e opology
o a hes - i s ha guides he lea ning p ocess o selec que ies om dis an egions ha a e
simul aneously dense hus, con ibu ing o imp o ed co e age in ou sense. In non-sepa able
da ase s he e is no clea dis ance be ween clus e s and he dis ibu ion o ins ances in inpu space
is mo e homogeneous. When being di ec ed o selec que ies in bo de line egions, ha a e also
less dense, a hes - i s misses he chance o imp o e co e age as much as he o he c i e ia.
Impac o clus e a iance Analyzing clus e a iance (Table 6.5) p o ides u he e idence on
his hypo hesis. In e -clus e and in a-clus e a iance we e compu ed o he numbe o clus e s
a i icially gene a ed in each da ase .
The co ela ion be ween he pe cen age o o al a iance ha is explained by in e -clus e a i-
ance and ins ance space co e age o a hes - i s (Table 6.6) is mo e han 10% highe han ha
o con idence and d-Con idence. The e is also a high co ela ion be ween d-Con idence and con-
idence co e age a es.
6.4 E alua ion 111
Table 6.5: Pe cen age o in e -clus e o o al a iance
Da ase Numbe o clus e s In e -clus e /To al a iance
ds0000 6 0.886
ds0001 5 0.785
ds0010 3 0.875
ds0011 3 0.670
ds0100 5 0.974
ds0101 5 0.874
ds0110 3 0.837
ds0111 3 0.664
ds1000 6 0.958
ds1001 6 0.947
ds1010 3 0.924
ds1011 3 0.765
ds1100 5 0.897
ds1101 5 0.827
ds1110 3 0.666
ds1111 3 0.651
Appa en ly con idence in oduces a bias ha leads he lea ning p ocess o selec que ies om
mo e dense a eas in ins ance space – a o ing exploi a ion. Fa hes - i s di ec s he lea ning p o-
cess o que y ins ances in unexplo ed egions i espec i ely o how dense hey a e – a o ing
explo a ion. Despi e he high co ela ion be ween he co e age a es o d-Con idence and con-
idence, d-Con idence ou pe o ms con idence p obably o i s abili y o ake ad an age o he
me i s o bo h i s baseline c i e ia.
Main ou comes The esul s om hese expe imen s p o ide e idence ha d-Con idence ou pe -
o ms he adi ional con idence app oach as well as a hes - i s ega ding ins ance space co e -
age, iden i ica ion o unknown classes and e o . D-Con idence imp o es ins ance space co e age
and educes he numbe o que ies equi ed o iden i y ins ances om unknown classes wi hou
Table 6.6: Co ela ion be ween in e -clus e / o al a iance and co e age
Co ela ion In e /To al Co e Co e c
Co e 0.689 1
Co e c 0.562 0.231 1
Co e dc 0.580 0.316 0.806
118 D-Con idence
a ela i e equency o 0.2% and six o he classes ha e a ela i e equency below 1% – allows
e alua ing he ea ly iden i ica ion o unde - ep esen ed classes. The a e age i s -hi compu ed
om Table 6.8 o e unde - ep esen ed classes – classes 5 o 10 – shows a weak pe o mance o
con idence in inding a e classes (Table 6.10).
Table 6.10: A e age i s -hi o e unde - ep esen ed classes a he Poke da ase
Classi ie c dc
SVM 80 182 76
NNET 80 141 72
RPART 80 162 89
D-Con idence ou pe o ms bo h i s baseline c i e ia w. . . he ea ly iden i ica ion o ins ances
om unde - ep esen ed classes when using SVM and NNET as base classi ie s. Fa hes - i s
howe e , imp o es o e he o he when using RPART.
LDC p o ides u he e idence suppo ing he imp o ed pe o mance o d-Con idence o e
i s baseline c i e ia. In ac , d-Con idence has he lowes LDC on all combina ions o da ase and
classi ie ha we e e alua ed on abula da a excep on he Vowels da ase when using RPART as
a base classi ie (Table 6.9). The a e age gain on d-Con idence LDC o all pai s da ase /classi ie
when compa ed o con idence on abula da a is o 542%, meaning ha con idence equi es o e
six imes mo e que ies han d-Con idence o iden i y all a ge classes. This igu e, howe e , is
highly biased by he ou lie obse ed on I is/NNET. Ne e heless, i we emo e his ou lie om
ou da a we s ill ha e a gain o 101% in LDC, meaning ha , on a e age, con idence equi es wice
as many que ies as d-Con idence o achie e a ull co e age o he classes o lea n on all abula
da ase s.
Pe o mance unde di e en le els o class imbalance Wi h he pu pose o u he in es iga -
ing he abili y o d-Con idence when in p esence o imbalanced da a, we ha e e alua ed he AL
s a egies being s udied unde di e en le els o class imbalance. We ha e pe o med his e alu-
a ion on he da ase s wi h uni o m class dis ibu ion – I is and Vowels – using SVM as he base
classi ie . The o iginal aining da ase s we e manipula ed o assu e imbalanced class dis ibu ions.
F om each o hose da ase s we ha e ex ac ed ou samples wi h biased class dis ibu ions. A
I is, he numbe o ins ances om one o he classes – which will become he mino i y class – was

6.4 E alua ion 119
educed in hose samples o 1, 3, 5 and 9, co esponding o a pe cen age o 2%, 6%, 11% and 19%
ela i e o he equency o each o he wo emaining classes which kep hei o iginal equency.
A Vowels, he numbe o ins ances om ou o i s 11 classes – which will become he mino i y
classes – was educed in hose samples o 1, 2, 3 and 6, co esponding o a pe cen age o 3%,
7%, 10% and 21% ela i e o he equency o each o he emaining classes whose equency was
kep unchanged. Then we ha e epea ed he same expe imen s as be o e bu now on hese biased
aining se s. The empi ical esul s a e p esen ed in Table 6.11.
The LDC compu ed om hese expe imen s (Table 6.11) con i ms he abili y o d-Con idence
o e ie e a e ins ances in compa ison o i s baseline c i e ia.
Table 6.11: LDC unde di e en imbalance le els. SVM as base classi ie . Imbalance is he a io
o he equency o he mino i y classes o he es
Da ase Imbalance .ldc c.ldc dc.ldc Bes
I is 19% 84 61 3 dc
I is 11% 87 61 3 dc
I is 6% 87 61 4 dc
I is 2% 88 88 5 dc
Vowels 21% 99 26 23 dc
Vowels 10% 84 39 35 dc
Vowels 7% 98 69 55 dc
Vowels 3% 102 58 74 c
On a e age, d-Con idence p esen s lowe LDC han i s baseline c i e ia on all se ings excep
a Vowels wi h 3% imbalance. We may obse e a simila scena io, wi h a signi ican dominance by
d-Con idence, when analyzing he numbe o known classes and e o (Table 6.12). D-Con idence
ou pe o ms i s baseline c i e ia wi h s a is ical signi icance a all se ings excep a he Vowels
da ase wi h 21% imbalance.
Common que ies selec ion Compa ing he ins ances ha a e selec ed by each AL s a egy adds
ele an in o ma ion o ou discussion. A e all s a egies selec ing he same ins ances a he same
s ages o he lea ning cycle? We ha e in es iga ed his ques ion by measu ing he pe cen age o
common que ies being selec ed by each c i e ia as he lea ning p ocess i e a es a I is (Figu e 6.9a)
and Vowels (Figu e 6.9b). Each cu e in hese cha s ep esen s he a e age, compu ed o e all
c oss alida ion olds a each i e a ion, o he pe cen age o common ins ances obse ed in he
labeled se s used o ain he classi ie unde he e e ed s a egies – d-Con idence (dc), con idence
120 D-Con idence
Table 6.12: Mic o-a e aged numbe o known classes and e o . Means ha e been compu ed o e
all i e a ions om all c oss alida ion olds o each combina ion o da ase , imbalance le el and
que y selec ion c i e ia. Bold aced alues a e s a is ically signi ican a 5%
Da ase Imbalance .kc c.kc dc.kc .e c.e dc.e
I is 2% 2.56 2.48 2.96 0.72 0.79 0.67
I is 6% 2.60 2.58 2.98 0.63 0.59 0.40
I is 11% 2.61 2.59 2.98 0.58 0.49 0.26
I is 19% 2.64 2.62 2.98 0.52 0.41 0.15
Vowels 3% 8.11 8.87 8.98 0.94 0.92 0.92
Vowels 7% 8.40 9.36 9.55 0.92 0.92 0.91
Vowels 10% 8.65 9.77 10.12 0.91 0.89 0.89
Vowels 21% 8.83 10.27 10.28 0.81 0.77 0.76
(c) o a hes - i s ( ). Ins ances in L1– which, gi en a da ase , a e he same o all AL c i e ia
– we e no conside ed when compu ing hese in e sec ions. Only he ins ances ha we e in ac
selec ed by each c i e ia om he i s i e a ion on we e accoun ed o .
(a) I is (imbalance 19%) (b) Vowels (imbalance 21%)
Figu e 6.9: E olu ion o he pe cen age o common selec ed que ies h oughou he lea ning cycle.
Each line ep esen s he pe cen age o common ins ances o a gi en pai o s a egies (dc-c, dc- ,
c- )
I is clea om Figu e 6.9a ha d-Con idence and con idence que y many common ins ances
du ing he ini ial s age o he lea ning p ocess a he I is da ase . In ac , a e he i s 29 que ies,
he labeled se s o bo h hese s a egies, L29, ha e nea ly 60% in e sec ion. This le el o o e lap-
ping hen s abilizes o s a inc easing la e as a consequence o he exhaus ion o he unlabeled
se which necessa ily inc eases he in e cep ion be ween he labeled se s o all s a egies.
6.4 E alua ion 121
The opposi e beha io is obse ed when compa ing a hes - i s wi h ei he con idence o d-
Con idence. Despi e he ac ha d-Con idence and a hes - i s sha e many common ins ances a
he e y i s i e a ions (60%), his o e lap d ops as ge ing close o 20% a e 11 que ies.
A he Vowels da ase , he o e lap be ween he labeled se s being buil by all AL s a egies
inc eases a a cons an a e h oughou he majo i y o he lea ning p ocess. Only a he e y be-
ginning, du ing he ini ial 35 i e a ions, a dis inc beha io is obse ed wi h d-Con idence and
a hes - i s que ying mo e common ins ances han he o he . As obse ed also a he I is da ase ,
con idence and a hes - i s a e he s a egies sha ing ewe que ies. This beha io is expec ed
since d-Con idence is a combina ion o bo h con idence and a hes - i s while hese a e indepen-
den om each o he .
Wi h he excep ion o he ini ial s age o he lea ning p ocess o I is w. . . dc-c, he pe cen age
o common que ies sha ed by d-Con idence and i s baseline c i e ia is small. This is an indica ion
ha d-Con idence is p omo ing a new lea ning pa h.
6.4.3 Tex
The e olu ion o he e o a e and he numbe o known classes o e ex co po a is shown in
Figu es 6.10a and 6.10b wi h cu es o each selec ion s a egy unde e alua ion.
(a) NG co pus (b) R52 co pus
Figu e 6.10: Known classes and gene aliza ion e o
Simila ly o wha we ha e done a phase wo, he e olu ion o e o and mean numbe o
known classes h oughou all he lea ning cycle has been also summed up o summa ize o e all
122 D-Con idence
pe o mance on ex co po a (Table 6.13).
Table 6.13: Mic o-a e aged numbe o known classes and e o . Means ha e been compu ed o e
all i e a ions om all c oss alida ion olds o each combina ion o da ase , classi ie and que y
selec ion c i e ia
Da ase Classi ie .kc c.kc dc.kc .e c.e dc.e
NG SVM 19.2 18.6 19.1 0.631 0.629 0.612
R52 SVM 34.4 35.5 39.7 0.531 0.383 0.447
Besides he o al numbe o que ies equi ed o e ie e labels om all classes and gene aliza-
ion e o , we ha e also obse ed i s -hi (Tables 6.14 and 6.15). When compu ing i s -hi o a
gi en class we ha e excluded he expe imen s whe e he ini ial labeled se , L1, con ains ins ances
om ha class.
Table 6.14: Fi s -hi o he NG da ase
Class F eq - h c- h dc- h
1 29 29.8 36.9 35.7
2 22 45.4 46.6 45.7
3 21 87.9 63.7 85.4
4 34 7.5 29.4 7.4
5 35 22.2 23.6 25.2
6 24 17.6 41.2 17.1
7 21 11.4 59.6 12.6
8 24 12.6 32.9 13.1
9 25 12.5 45.4 11.4
10 22 45.5 41.1 48.9
11 22 3.8 47.2 3.9
12 24 3.7 31.8 4.8
13 28 30.0 31.3 34.0
14 28 6.1 25.8 5.4
15 22 5.4 27.4 6.2
16 28 2.4 14.9 2.6
17 23 25.3 23.8 31.0
18 26 8.6 38.3 8.6
19 22 22.7 23.6 24.7
20 20 8.6 29.7 7.7
a e age 20.45 35.71 21.57
The lea ning p ocess o he R52 da ase was hal ed a e 600 i e a ions, be o e explo ing he
ull unlabeled pool – he wo king se had 1000 ins ances, 900 o which we e used o aining
in each old. All he class labels o lea n we e iden i ied a e 600 i e a ions o all he selec ion
6.4 E alua ion 123
Table 6.15: Fi s -hi o he R52 da ase
Class F eq - h c- h dc- h
1 239 1.0 24.0 1.0
2 5 78.5 115.6 64.7
3 3 230.3 118.6 178.7
4 2 98.7 167.4 107.8
5 6 239.0 173.7 110.6
6 11 7.5 80.0 10.0
7 4 15.9 123.6 19.1
8 3 130.0 173.3 102.9
9 7 240.2 128.8 136.0
10 2 153.2 118.0 99.5
11 40 14.6 12.4 20.0
12 2 209.9 158.5 166.4
13 435 2.5 25.2 4.0
14 2 219.0 152.2 150.4
15 3 192.8 214.1 123.9
16 7 113.7 91.9 107.8
17 9 33.1 92.7 46.3
18 5 24.9 96.7 16.8
19 2 93.1 140.0 104.7
20 3 411.8 206.7 184.9
21 2 273.2 143.6 154.5
22 2 588.6 188.9 202.8
23 30 76.0 28.9 63.4
24 4 341.9 171.7 171.1
25 4 253.9 196.2 224.0
26 2 459.6 313.1 256.4
27 5 282.8 130.0 150.7
28 2 294.7 216.3 144.5
29 2 422.5 175.5 198.7
30 3 68.5 213.3 85.2
31 2 111.7 206.0 126.7
32 2 248.3 233.7 167.0
33 30 53.0 39.7 49.7
34 15 67.6 44.6 99.0
35 4 187.8 271.6 219.6
36 2 58.2 153.2 84.1
37 3 45.7 137.6 44.8
38 3 66.6 159.3 52.1
39 2 101.2 226.0 106.9
40 2 90.4 144.3 75.5
41 5 67.6 68.7 62.9
42 3 206.6 159.1 144.8
43 4 43.4 153.4 36.7
44 14 72.7 103.8 76.6
45 3 86.5 179.7 123.9
46 12 3.2 68.6 6.6
47 2 45.9 148.5 51.1
48 3 101.9 160.8 76.1
49 35 39.4 36.4 72.9
50 3 219.0 175.6 108.7
51 3 482.2 146.1 183.5
52 2 302.7 258.8 196.5
a e age 159.10 143.58 107.16

124 D-Con idence
c i e ia, excep o a hes - i s . The mean numbe o known classes a e 600 i e a ions equals 52
o con idence and d-Con idence, meaning hese c i e ia ha e achie ed ull co e age o he class
labels o lea n in all he c oss alida ion olds. Fo a hes - i s he a e age numbe o known
classes, 50.3, is below 52 which means ha a hes - i s was no able o iden i y all class labels
in all c oss alida ion olds a e 600 i e a ions. Fa hes - i s missed, in se e al olds, six classes
wi h equency o wo, wo classes wi h equency o h ee and one class wi h a equency o ou .
In such cases we ha e assigned he mos a o able i s -hi alue o he uniden i ied classes –
a alue om 601 on. Fo ins ance, in a gi en old whe e a hes - i s misses wo classes hei
i s -hi alues a e assumed o be 601 and 602 – he e y i s que ies a e hal ing he lea ning
p ocess a 600 i e a ions. Fi s -hi means we e compu ed on his assump ion – he mos a o able
assump ion o a hes - i s .
Finding unde - ep esen ed classes The e is no clea dominance, nei he om d-Con idence
no om a hes - i s , when inding unknown classes in he NG da ase (Figu e 6.10a). Howe e ,
bo h hese c i e ia ou pe o m con idence a his da ase . The di e ence be ween mean i s -hi o
d-Con idence and a hes - i s in Table 6.14 – 20.45 o a hes - i s and 21.57 o d-Con idence
– is no s a is ically signi ican (α=5%).
In R52, a hes - i s s a s by iden i ying unknown classes a li le as e han d-Con idence
(Figu e 6.10a). Howe e , a e he ini ial lea ning s age, d-Con idence ou pe o ms and domina es
a hes - i s . This beha io had al eady been obse ed, wi h abula da ase s, in he p e ious
expe imen al phase. When iden i ying unknown classes, a hes - i s leads, up o he 45 h que y,
on a e age, aking a maximum ad an age o wo classes a e 37 que ies. A e 45 que ies, wi h
13.2 classes iden i ied on a e age, d-Con idence clea ly domina es a hes - i s .
I is in e es ing o no ice ha a hes - i s bea s d-Con idence on he majo i y classes (Ta-
ble 6.15) bu , once all majo i y classes ha e been ound and only mino i y classes a e le unex-
posed, d-Con idence e eals i s abili y o ind a e ins ances. The mean equency o he classes
ha a e i s ound in R52 by d-Con idence is 3.2, while i is 12.5 o con idence and 33.8 o
a hes - i s .
This aspec migh be u he in es iga ed om a coa se poin o iew by analyzing how as
each AL c i e ion e ie es exempla y ins ances om a ba ch o classes ins ead o analyzing single
6.4 E alua ion 125
classes one a a ime. To analyze his pa icula aspec we p o ide a benchma k based on andom
que y selec ion – a e aged o e 10 andom samples.
We ha e eco ded he numbe o que ies equi ed o iden i y bunches o dis inc classes in
mul iples o 10 o R52 and mul iples o 4 in NG. These bunches a e cons i u ed by classes so ed
by inc easing o de o hei i s -hi . Figu es 6.11 and 6.12 gi e an o e iew o he numbe o
que ies ha a e equi ed in each se ing o i s hi a gi en numbe o dis inc classes.
Figu e 6.11: Que ies equi ed o iden i y bunches o dis inc classes in NG da ase
Figu e 6.12: Que ies equi ed o iden i y bunches o dis inc classes in R52 da ase
In he case o he R52 da ase , d-Con idence always inds new classes as e , ha is wi h ewe
que ies, han con idence. The i s bunch o 10 dis inc classes – he i s classes being iden i ied
126 D-Con idence
a e gene ally majo i y classes – is ound as as wi h andom sampling and a hes - i s as wi h
d-Con idence bu , om he e on, when a e classes come by, d-Con idence akes he lead.
The ou come is qui e di e en in he NG da ase . In his da ase d-Con idence s ill ou pe -
o ms con idence bu i is bea en by andom selec ion o ins ances a e iden i ying 13.3 classes
on a e age – a e 22 que ies on a e age. The abili y o e ie e exempla y ins ances om un-
known classes o d-Con idence is compa able o ha o a hes - i s on NG. When in p esence o
balanced da ase s, as NG, d-Con idence iden i ies new classes as e han andom selec ion a he
ini ial phase o he lea ning p ocess bu selec ing ins ances by chance is be e o iden i y ins ances
in he la es s age o he lea ning p ocess when ew classes emain unde ec ed.
Figu es 6.13 p o ide addi ional e idence on he abili y o d-Con idence o ind a e ins ances.
(a) D-Con idence s a hes - i s (b) D-Con idence s con idence
Figu e 6.13: A e age gain o d-Con idence o e i s baseline c i e ia o i s hi classes on R52.
Classes a e so ed by inc easing equency
These cha s ep esen he di e ence in d-Con idence i s -hi compa ed o hei baseline c i-
e ia. Nega i e di e ences mean ha d-Con idence pe o med be e , i.e., ound ep esen a i e
ins ances o he class wi h ewe que ies han i s baseline c i e ia. In hese cha s, classes a e
so ed by inc easing equency, in i s place, and hen by dec easing gain. This so ing scheme
is esponsible o he pa e ns ha a e obse ed in bo h cha s o Figu e 6.13. Fo ins ance, all
he mino i y classes ha a e ep esen ed in he ho izon al axis o Figu es 6.13a and 6.13b by he
coo dina es 1 o 17 ha e a equency o wo. Fo his g oup, he gain is so ed by inc easing o de
hus gene a ing he pa e n ha we may obse e in bo h cha s o each g oup o classes wi h he
same equency.
The dashed end lines, ep esen ed in bo h cha s (Figu es 6.13), wi h a posi i e slope clea ly
6.4 E alua ion 127
show ha he gain in d-Con idence i s -hi , when compa ed o i s baseline c i e ia, dec eases when
he class equency inc eases. D-Con idence assu es a signi ican educ ion in he mean numbe
o que ies ha a e equi ed o i s hi classes in R52. This educ ion is mo e impo an in mino i y
classes, i.e., in he i s classes appea ing in he ho izon al axis.
Ano he pe spec i e o hese esul s may cla i y ou poin o iew. Figu e 6.14a p esen s he
numbe o classes ha we e i s ound by each c i e ia o each di e en class equency in he
ho izon al axis. Figu e 6.14b ep esen s he accumula ed numbe o i s ound classes.
As de ailed below, bo h hese cha s show e idence on he imp o ed abili y o d-Con idence
o ind exempla y ins ances o unde - ep esen ed classes.
(a) Fi s ound classes (b) Accumula ed i s ound
Figu e 6.14: Numbe o classes o a gi en equency i s ound by each c i e ia on R52
When compa ing d-Con idence agains a hes - i s we can obse e ha om he 17 classes in
R52 ha ha e a equency o wo, d-Con idence inds 11 be o e a hes - i s . F om he 12 classes
wi h a equency o h ee, d-Con idence inds 10 be o e a hes - i s . F om he 13 classes wi h
equency be ween ou and nine, d-Con idence inds 10 wi h ewe que ies han a hes - i s .
F om he emaining 10 classes, wi h a equency be ween 11 and 435, d-Con idence inds only
wo be o e a hes - i s .
A simila compa ison agains con idence shows simila esul s. F om he 17 classes in R52
ha ha e a equency o wo, d-Con idence inds 13 be o e con idence. F om he 12 classes
wi h a equency o h ee, d-Con idence inds 10 be o e con idence. F om he 13 classes wi h
equency be ween ou and nine, d-Con idence inds 10 wi h ewe que ies han con idence. F om
he emaining 10 classes, wi h a equency be ween 11 and 435, d-Con idence inds i e be o e
con idence.