Stochastic Scheduling of Active Support Vector Learning Algorithms ABSTRACT

StochasticSchedulingofActiveSupportVectorLearning

Algorithms

ComputerScienceUniversityofMinnesotaGauravPandeyHimanshuGuptaComputerScienceIITKanpurComputerScienceIITKanpurPabitraMitragaurav@cs.umn.eduABSTRACThimg@cse.iitk.ac.inpmitra@cse.iitk.ac.inActivelearningisagenericapproachtoacceleratetrainingofclassifiersinordertoachieveahigheraccuracywithasmallnumberoftrainingexamples.Inthepast,simpleactivelearningalgorithmslikerandomlearningandquerylearninghavebeenproposedforthedesignofsupportvectormachine(SVM)classifiers.Inrandomlearning,examplesarechosenrandomly,whileinquerylearningexamplesclosertothecurrentseparatinghyperplanearechosenateachlearningstep.However,itisobservedthatabetterschemewouldbetouserandomlearningintheinitialstages(moreex-ploration)andquerylearninginthefinalstages(moreex-ploitation)oflearning.HerewepresenttwonovelactiveSVlearningalgorithmswhichuseadaptivemixturesofran-domandquerylearning.Oneoftheproposedalgorithmsisinspiredbyonlinedecisionproblems,andinvolvesahardchoiceamongthepurestrategiesateachstep.Theotherextendsthistosoftchoicesusingamixtureofinstancesrec-ommendedbytheindividualpurestrategies.Bothstrategieshandletheexploration-exploitationtrade-offinanefficientmanner.Theefficacyofthealgorithmsisdemonstratedbyexperimentsonbenchmarkdatasets.

KeywordsSVM,PoolBasedActiveLearning,Multi-ArmBanditProb-lem,Stochasticscheduling

1.INTRODUCTIONActivelearningisapopularparadigmforreducingthesamplecomplexityofalearningalgorithm[6]wherethelearnerselectsitsowntrainingdata.Here,insteadoflearn-ingfrominstancesselectedrandomly,thelearnercanselectitsowntrainingdata.Thisisdoneiteratively,andtheout-putofalearningstepisusedtoselecttheexamplesofthenextstep.Aparticularsettingofthisframeworkisreferredtoaspoolbasedactivelearning[1],wherethelearnerispre-sentedwithafixedpoolofunlabeledinstancesandoneach

Permissiontomakedigitalorhardcopiesofallorpartofthisworkforpersonalorclassroomuseisgrantedwithoutfeeprovidedthatcopiesarenotmadeordistributedforprofitorcommercialadvantageandthatcopiesbearthisnoticeandthefullcitationonthefirstpage.Tocopyotherwise,torepublish,topostonserversortoredistributetolists,requirespriorspecificpermissionand/orafee.

SAC’05,March13-17,2005,SantaFe,NewMexico,USACopyright2005ACM1-58113-964-0/05/0003...$5.00.

trialitchoosesasetofinstancesfromthepooltobelabeled.Thelearneristhenprovidedthetruelabeloftheinstancesanditinducesanewclassifierbasedonallthelabeledsam-plesseensofar.Severalstrategiesforchoosingthesetofinstancesfromthepoolexistinpractice,e.g.,randomselec-tion,errordriventechniques,uncertaintysampling,versionspacereductionandadaptiveresampling.Poolbasedactivelearningishighlysuitedforapplicationswhereunlabeleddataisabundantbutlabelinginstancesiscostlyandtimeconsuming.Suchascenarioisoftenencounteredintextcat-egorizationandinformationretrieval,wherethelabelingisobtainedbyahumanuser[12].Inthecaseofremotesensingandbiomedicalimageanalysis,labelingisevenmorecostlyasitcanbedoneonlybyexperts.Labellingindrugdis-overyandmoleculescreeningproblemsalsoinvolvecostlyandtimeconsumingchemicalexperiments.

Thesupportvectormachine(SVM)[4,13]hasbeensuc-cessfulasahighperformanceclassifierinseveraldomainsincludingpatternrecognition,dataminingandbioinformat-ics.Ithasstrongtheoreticalfoundationsanddemonstratesgoodgeneralizationcapability.AlimitationoftheSVMde-signalgorithm,particularlyforlargedatasets,istheneedtosolveaquadraticprogramming(QP)probleminvolvingadensen×nmatrix,wherenisthenumberofpointsinthedataset.SincemostQProutineshavecubiccomplexity,SVMdesignrequireshugememoryandcomputationaltimeforlargedataapplications.Reducingthesamplecomplex-ity(n)ofSVMdesignusingpoolbasedactivelearningthusmakesSVMssuitableforlargedataapplications.

InthecontextofSVM,severalpoolbasedactivelearningalgorithmshavebeenproposed.Theearliestonesselectedthenewsetofinstancesrandomly[9](referedtoasRan-domSVMintherestofthepaper).In[5],aquerylearningstrategyforlargemarginclassifiersispresented,whichit-erativelyrequeststhelabelofthedatapointclosesttothecurrentseparatinghyperplane(referredtoasQuerySVMintheremainderofthepaper).Similarly,[3]chosesthenextbatchoftrainingpointsw.r.t.theanglesmadebytheex-ampleswiththecurrenthyperplane.Astrategybasedonversionspacesplittingispresentedin[12].Thepointswhichsplitthecurrentversionspaceintotwohalveshavingequalvolumesareselectedateachstep,astheyarelikelytobetheactualsupportvectors.Agreedyoptimalstrategyisde-scribedin[11].Herelogisticregressionisusedtocomputetheclassprobabilities,whicharefurtherusedtoestimatetheexpectederrorafteraddinganexample.TheexamplethatminimizesthiserroristhecandidateSV.Thisapproach,thoughoptimal,isnotpracticalbecausetheselectionofeach

38

candidatepointrequiressolvingtwoQPproblemsandcanbeabottleneckforlargedatasets.

Inspiteofthewidevarityoftechniquesused,alimitationthesestrategiesisthattheyareessentiallypurestrategiesinthesensethatthroughoutthetrainingprocesstheyeitherqueryforpointsclosetothecurrentseparatinghyperplaneorselectrandomsamplesconsistingmostlyofinteriorpointsofaclass.Boththesestrategiesrepresentextremecases;theformeroneisfastbutunstable,whilethelatteroneisrobustbutslowlyconverging.Theformerstrategyisusefulinthefinalphaseoflearning,whilethelatteroneismoresuitableintheinitialphase.Anadaptivemixtureoftheabovetwostrategiesisexpectedtoyieldbetterperformance.

Inthispaper,mixedactivelearningstrategies,whicharecombinationsoftwopurestrategies,namely,RandomSVMandQuerySVM,areproposedtoachievefastandrobustconvergence.Here,theactivesupportvectormachinelearn-ingproblemistreatedasastochasticschedulingproblem,morespecificallyasamulti-armedbanditproblem.Thisisthentransformedtoanequivalentonlinedecisionproblemofselectingamixtureofthetwopurestrategies.Twoal-gorithmsforcombining/mixingthepurestrategiesarepro-posed.Thefirstalgorithminvolvesahardchoicebetweenoneofthetwopurestrategiesateachlearningstep.ThisisdonebyadynamicallocationalgorithmcalledFollowthePerturbedLeader[8].Ontheotherhand,thesecondoneper-formsasoftchoicebetweentheindividualpurestrategiestodeterminethecompositionoftheselectedsetofinstances.Experimentalresultsonbenchmarkdatasetsdemonstratetheeffectivenessofthestrategies.

Itmaybenotedthatamulti-armedbanditformulationofactivelearningproblemhasbeenproposedin[10]and[1].However,theretraininginstancesaretreatedasslotsofthegamblingmachine.Aprobabilitydistributionismaintainedoverthetraininginstancestodeterminewhichinstancetoselectnext(i.e.,whichslottoplaynext).However,forlargedatasetsmaintainingsuchadistributionwouldbeinfeasibleintermsofstorage.Hence,inouralgorithmwereformulatethemulti-armedbanditproblemasanonlinedecisionprob-leminvolvingchoiceofoneofthetwoexperts(i.e.,purestrategies).Here,oneneedstoonlystorea(dynamical-location)indexperexperttodeterminewhichexampletochosenextandisthussuitableforlargedatasets.

Theorganizationofthearticleisasfollows.InthenextsectionwedescribeRandomandQuerySVM.Section3reformulatestheactiveSVMlearningproblemasamulti-armedbanditproblem.Wealsomentiontheequivalenton-linedecisionproblem.TwoonlinealgorithmsforactiveSVMlearningarepresentedinSection4.ExperimentalresultsappearinSection5.WeconcludethepaperinSection6.

2.SUPPORTVECTORMACHINES

SVMsareageneralclassoflearningarchitecturesinspiredbystatisticallearningtheorythatperformsstructuralriskminimizationonanestedsetstructureofseparatinghyper-planes[4,13].Giventrainingdata,SVMsobtaintheoptimalseparatinghyperplaneintermsofthegeneralizationerror.

2.1SVMDesignUsingActiveLearning

Asdiscussedintheprevioussection,activelearningisamethodofincrementallearningwhichenablesalearn-ingalgorithmtoapproachthemaximumachievableclas-sificationaccuracyverycloselywithrelativelysmallernum-

beroftrainingexamplesascomparedtothebatchlearningmethod.ActivelearningisequallyapplicabletoSupportVectorMachines(SVMs)andvariousapproacheshavebeensuggestedforusingitinSVMtrainingandclassification.WepresentheretwoofthemostcommonactivelearningstrategiesforSVMs,namelyrandomandquerySVM.Theydifferinthewayexamplesarequeriedfromthedataset.RandomSVM:Thisisauniversalandperhapsthesim-plestactivelearningstrategyforanylearningalgorithm.Itassumesthattheprobabilityofanyexamplebeingchosenatanystageofthetrainingprocessisindependentofthatoftheothers,i.e.allexamplesaregivenauniformprobabilityofbeingchosenfortraining.Thetrainingprogresseswiththechoiceofkrandomexamplesateachstage.

QuerySVM:Randomactivelearning,asdiscussed,isanunguidedstrategyandhenceitisexpectedthatitwillnotperformverywellonmanyproblems.Analternativeandmoreintuitiveapproachistoimprovetheconfidenceindimensionsaboutwhichwealreadyhaveinformation.Thiscanbeachievedbycontinuallynarrowingtheexistingmar-gin.Thus,ateachstageofthetrainingprocess,ktrainingexamplesclosesttothecurrentdividinghyperplanearese-lectedandaddedtotheintermediatetrainingset[5].

3.MULTI-ARMEDBANDIT,ACTIVELEARN-INGANDSTOCHASTICSCHEDULING

TheMulti-armedbandit(MAB)problemisawellstudiedprobleminstochasticschedulinganddynamicallocation.InMAB[7],agambler,vistingacasino,mustchoosewhichofKmachinestoplay.Ateachtimestep,hepullsthearmofoneofthemachinesandreceivesarewardorpayoff(possiblyzeroornegative).Thegambler’spurposeistomaximizehistotalrewardoverasequenceoftrials.Sinceeacharmisassumedtohaveadifferentdistributionofrewards,thegoalistofindthearmwiththebestexpectedreturnasearlyaspossible,andthentokeepgamblingusingthatarm.

Theproblemisaclassicalexampleofthetrade-offbe-tweenexplorationandexploitation.Ontheonehand,ifthegamblerplaysexclusivelyononemachinethathethinksisbest(exploitation),hemayfailtodiscoverthatoneoftheotherarmsactuallyhasahigheraveragereturn.Ontheotherhand,ifhespendstoomuchtimetryingoutallthemachinesandgatheringstatistics(exploration),hemayfailtoplaythebestarmoftenenoughtogetahightotalreturn.Intheearlyyears,thebanditproblemwasstudiedwiththeaidofstatisticalassumptionsontheprocessgeneratingtherewardsforeacharm.However,itislikelythatthecostassociatedwitheacharmisdeterminedateachtimestepbyanadversaryratherthanbysomebenignstochasticprocess.Wecanonlyassumethattherewardsarechosenfromaboundedrange.Here,thereisnosinglemachinewhichgivesthehighestpayoffatallthetimesteps.Henceonshouldfindasequenceofmachineswhichgivesthehighesttotalreward.Theperformanceofanyplayerismeasuredintermsof‘regret’,i.e.,theexpecteddifferencebetweenthetotalrewardscoredbytheplayerandthetotalrewardscoredbythebestsequenceofarms.

3.1ActiveLearningasanMABProblem

Inactivelearning,thelearnerhasthefreedomtochoosetheexamplestobeusedforlearning.Inotherwords,thetraininginstancesareequivalenttotheslotsofagambling

39

machinethatthelearnerchoosesfrom.Usingthesequeriedexamplesthelearnerupdatesitselfandqueriesanewsetofexamples.Thusthelearnerhastomakeasequenceofchoicesofexamplestoquery,withoutknowledgeofthefu-ture.Therewardateachstephereisthegaininclassifica-tionaccuracyachievedbythelearnerbylearningfromthesetofexamplesqueried.Thelearnershouldtrytomaximizethisrewardoveralltimestepssuchthatthefinalaccuracyismaximum.Thisisdonebymaintainingbilitydistribution{pt1,...,pt

aselectionproba-l},wheretisthelearningstep,listhetotalnumberoftraininginstances,andchoosingthesetofinstanceshavinghighprobabilitiesforthe(t+1)thstep.Inboosting[10],thisdistributionismaintainedbyrepetitivemultiplicativeupdatesonaninitialsetofuniformprobabilities.

3.2ActiveLearning&StochasticScheduling

Analternatewayofformulatingtheaboveschedulingproblemistoconsiderasetofexpertswhichadvisesthelearneronwhichsetofexamplestochoosenext.Theex-pertsmayrepresentsomepurechoicestrategiesthemselves.Thelearnerusesacombinationormixtureoftheexpertstoselectthenextsetofexamples.Inouralgorithmswehaveconsideredasetoftwoexperts,namely,theRandomSVMandQuerySVM.ThesearediscussedinSection2.Thefor-merexpertrepresentshighexplorationinlearningwhilethelaterrepresentshighexploitation.Thesetofexamplestobequeriedbythelearnerconsistsofexamplesrecommendedbyeitherorbothoftheexperts.OnemaynotethatintheformulationofactivelearningasaMABproblemthede-cisionconsistsofchoosingthesequenceofexamplestobequeriedforlearning.However,selectingaparticularmix-tureofexpertsalsoleadstoqueryingaparticularsetofexamplesandactivelearningintheMABsettingcanalsobeconsideredasasequenceofdecisionswhichchoosecer-tainmixtureofindividualexperts.Infact,thereexistsacorrespondencebetweenthetwodecisionprocessesinactivelearning,namely,theselectionofasetofexamplesandtheselectionofamixtureofexperts.However,inthelatterpro-cess,oneneedstomaintainaprobabilitydistributionoverthesetofexpertsratherthanthesetofexamples,andthusrequiresconsiderablylessstorageforlargedatasets.

4.

PROPOSEDALGORITHMSFORACTIVESUPPORTVECTORLEARNING

Inthissectionwepresenttwoalgorithmsforonlineschedul-ingofamixtureofexperts.Theexpertsherearethepurestrategiesforactivelearning,namelyRandomSVMandQuerySVM.TheyaredescribedinSection2.

Thefirstmixturestrategyisahardstrategywhichchoosesasingleexpertineachstep,althoughthechoiceofexpertsmayvaryoverdifferentsteps,whilethesecondoneisasoftstrategywhichchoosesacompositionofexamplesrecom-mendedbyboththeexperts.Theratioofexamplesrec-ommendedbyeachexpertvariesadaptivelyoverthesteps.Thefirststrategyusesanefficientonlinedecisionalgorithmcalled‘followtheperturbedleader’(FPL)[8]andthesec-ondusesclassificationerrorsinamannersimilartoboosting[10].Thealgorithmsaredescribedinthenexttwosections.

4.1HardChoice:FollowthePerturbedLeader

Thecorrespondencebetweentheproblemofactivelearn-ingforsupportvectormachinesandonlinedecisionprob-

Data:UnlabeledandLabeled

examples

Tunlabeled,Tlabeled

Result:FinalclassifierCfinal

Q←ChooseRandom(Tunlabeled,k);Label(Q);

C←SVMTrain(Q);

cost0,random←GetError(Tlabeled,C);cost0,query←0;t←1;

whileterminationconditionisnotmetdo

Q←Q∪ChooseNearest(Tunlabeled,k,C);Label(Q)/*Onlynewlyaddedexamplesarelabeled*/;

C←SVMTrain(Q);costt,query←

costt−1,query+GetError(Tlabeled,C);endelse

itateachstepwhereitisselected.Fortheotherstrategies,thecostincurredforthisstepiszero.Usingthisnotion,FPLiscapturedinbriefinthefollowingsteps:FPL(α):Oneachperiodt,

1.Choosept,d,theperturbationvector,atrandomac-cordingtothedensitydµ(x)∝e−α|x|1,foreachstrategyd.

2.UseM(s1:t−1+pt)=argmind∈D[s1:t−1,d+pt,d],wheres1:t−1,disthetotalcostincurredbystrategydtillperiodt−1.

TheFPLalgorithmhasbeenshowntobeoptimalwithina(1+󰀧)bound.Experimentsonthehardchoicestrategyalsoshowitssuperiorperformancecomparedtotherandomandquerylearningstrategies.ItisseenthatinitiallyrandomSVMistheleaderandisfollowedbytheabovealgorithm,whileaftersometimethealgorithmswitchesovertoquerySVMandfollowsitforsubsequentsteps.Someoscillationsbetweenthesetwooccurintheintermittentphases.

68 66 64Classification Accuracy 62 60 58 56 54 52 0 100 200 300 400 500 600Number of Labeled Examples 100Hard SwitchingSoft SwitchingQuery SVMRandom SVM 700 800 900 95VariousobservationsshowthatrandomSVMperformsbetterclassificationinitially,whilequerySVMdoesbetterinthelaterpart.Sinceinitiallythetrainingisdoneonaverysmallsizedsample,theinitialhyperplanefoundwillbeveryfarfromtheoptimalhyperplane.UsingquerySVMtochooseatrainingpointthatisclosesttothishyperplanewillresultonlyinasmalldrifttowardstheoptimalhyper-plane.Choosingarandomtrainingpointseemstobeabet-terideaasitmaylieclosetotheoptimalhyperplane,anditsinclusioninthetrainingsetwillimplysignificantprogresstowardstheoptimalhyperplane.Inthelaterstages,thecur-renthyperplaneisclosetotheoptimalhyperplane.Thus,choosingthedatapointclosesttothecurrenthyperplanewillbebetterasitensuresthatthepointchosenisclosetotheoptimalhyperplaneaswell.Thisanalysissuggeststhatanoptimalstrategyofchoosingdatapointsateachstagewouldbetoselectsomepointsrandomlyandsomeotherpointsclosetothecurrenthyperplane,i.e.,asoftmixtureofthetwopurestrategiesrandomSVMandquerySVM.Theratioofthepointsrecommendedbytheseindividualpurestrategiesvariesadaptivelyoverthelearningsteps.

Thestrategyatanystepconsistsoftwosubsteps:(i)se-lectingpointsrandomly,obtaininganupdatedSVM,andcalculatingitserroronthelabeleddataset(denotethisas󰀧random)and,(ii)selectingdatapointsclosesttothecurrentseparatinghyperplane,obtaininganupdatedSVM,andde-terminingitserroronlabeleddataset(denotethisas󰀧query).Afinaldecisionofthenumberofpointstobeselectedran-domlyandthatofthosetobeselectedonthebasisoftheirdistancefromthecurrentseparatinghyperplaneismadeus-ing󰀧randomand󰀧query.AnoutlineofthisstrategyisgiveninAlgorithm2.Forλqueryandλrandom,aformsimilartoAdaBoost[10]hasbeenchosen.

Classification Accuracy4.2SoftChoice 90 85 80 75 70Hard SwitchingSoft SwitchingQuery SVMRandom SVM 65 0 20 40 60 80 100 120 140Number of Labeled Examples 60 160 180 200 58Classification Accuracy 56 54 52 50Hard SwitchingSoft SwitchingQuery SVMRandom SVM 48 0 50 100 150 200 250 300Number of Labeled Examples 60 350 400 450 58 56Classification Accuracy 54 52 50 485.EXPERIMENTALRESULTS 46Performanceoftheproposedactivelearningstrategieshasbeenstudiedforfourbenchmarkdatasets,namelytheiono-sphere,contraceptiveuse,Australiancreditapprovalandthecreditscreeningdatasets.AlldatasetsarefromtheUCIMachineLearningRepository[2],andtheirdetailsaregiveninTable1.Missingvalueswerereplacedbyrandomvalueswithintherangeofthecorrespondingattributeto

44 0 50 100 150 200 250 300Number of Labeled ExamplesHard SwitchingSoft SwitchingQuery SVMRandom SVM 350 400 450Figure1:Convergencecurvesofdifferentactivelearningalgorithmsondifferentdatasets.Fromtoptobottom1.Contraceptiveusedataset2.Iono-spheredataset3.Australiancreditapprovaldataset4.Creditscreeningdataset

41

Data:Unlabeled&Labeledexamples

Tunlabeled,Tlabeled

Result:FinalclassifierCfinal

Qsoft←ChooseRandom(Tunlabeled,k)/*Initializethetrainingsetwithkrandomexamples*/;Label(Qsoft);

Csoft←SVMTrain(Qsoft);Cquery←Csoft;Crandom←Csoft;

whileterminatingconditionisnotmetdo

Table1:CharacteristicsofdatasetsDataSet#Attributes

351

Contraceptiveuse10

690

Creditscreening15suchasbioinformatics,wherelabellingdatamaybecostly

bothintermsofmoneyandtime.

Theseapproachesareexpectedtogivebetterresultsgen-erallysincethemostappropriatebasestrategy(randomorquerySVM)ischosen(orweightedheavilyinthecaseofsoftswitching)inthemostappropriatestageoflearning.ThiscorrespondstochoosingrandomSVMintheearlystagesandquerySVMinthelaterones,asjustifiedearlier.Inordertoillustratethisgeneralefficacy,resultshavebeenshownondatasetswithvariedcharacteristics.

6.CONCLUSIONSANDDISCUSSION

Wehaveproposedtwoalgorithmsforfastandrobustactivesupportvectorlearning.Thealgorithmsaremoti-vatedbyonlinedecisionproblemsandefficientlyhandletheexploration-exploitationtrade-offinactivelearning.

Thesuperiorityofthealgorithmshasbeendemonstratedempiricallyonbenchmarkdatasets.However,alargebodyoftheoreticalresultsononlinedecisionproblemsisavailable.Theoreticalboundsontheaccuraciesoftheproposedactivelearningalgorithmswillbereportedinasubsequentarticle.

λrandom←|ln

󰀁󰀗query

;

󰀂

|;

1−󰀗random

Qsoft←Qsoft∪

ChooseNearest(Tunlabeled,kλ,Csoft)/*Marktheseselectedpointsasold*/;Qsoft←

Qsoft∪ChooseRandom(Tunlabeled,k(1−λ))/*Marktheseselectedpointsasold*/;Csoft←SVMTrain(Qsoft);Qquery←SV(Csoft);Qrandom←SV(Csoft);end

returnCsoft;

Algorithm2:SoftactivelearningstrategyforSVMs

λquery+λrandom

7.REFERENCES

[1]Y.Baram,R.El-Yaniv,andK.Luz.Onlinechoiceof

activelearningalgorithms.JMLR,5:255–291,2004.[2]C.L.BlakeandC.J.Merz.UCIrepositoryofmachine

learningdatabases,1998.

[3]K.Brinker.Incorporatingdiversityinactivelearning

withsupportvectormachines.InICML,2003.

[4]C.J.C.Burges.Atutorialonsupportvectormachines

forpatternrecognition.DataMiningandKnowledgeDiscovery,2:1–47,1998.

[5]C.Campbell,N.Cristianini,andA.Smola.Query

learningwithlargemarginclassifiers.InICML,2000.[6]D.Cohn,LAtlas,andR.Ladner.Improving

generalizationwithactivelearning.MachineLearning,15:201–221,1994.

[7]J.C.Gittins.Multi-armedBanditAllocationIndices.

JohnWiley,1989.

[8]A.KalaiandS.Vempala.Efficientalgorithmsforthe

onlinedecisionproblem.InCOLT,2003.

[9]N.A.Sayeed,H.Liu,andK.K.Sung.Asudyof

supportvectorsonmodelindependentexampleselection.InSIGKDD,1999.

[10]R.Schapire,Y.Freund,P.Bartlett,andW.S.Lee.

Boostingthemargin:Anewexplanationfortheeffectivenessofvotingmethods.AnnalsofStatistics,26:1651–1686,1998.

[11]G.SchohnandD.Cohn.Lessismore:Activelearning

withsupportvectormachines.InICML,2000.

[12]S.TongandD.Koller.Supportvectormachineactive

learningwithapplicationtotextclassification.JMLR,2:45–66,2001.

[13]V.Vapnik.StatisticalLearningTheory.Wiley,1998.

preventanybias.Thesedatasetshaveabalancedmixofcontinuous,few-valuenominalandmany-valuenominalat-tributes,andthusareappropriatefortheexperiments.Theconvergencecurvesofalltheactivelearningstrate-giesconsidered,namelyrandomSVM,querySVM,activelearningusingfollowtheperturbedleaderandsoftchoicealgorithm,ontheabovementioneddatasetsareshowninFigure1.Theresultspresentedareforabatchsizeof10(i.e.,10instancesarechosenactivelyateachstep).Theaveragevalueoftheclassificationaccuraciesovertwentyex-ecutionsareplottedinFigure4.2.

Fromtheplots,itcanbeseenthattheproposedalgo-rithmsachievethemaximumpossibleaccuracywithinacloselimitwithmuchfewerexamsascomparedtoqueryandrandomSVM.Thisisclearlyobservedinthecaseofsoftswitchinginplots2and3,andinthecaseofhardswitchinginplots1and4.Thischaracteristicispreciselythegoalofactivelearningandprovesexpeciallyusefulinapplications

42