Introduction to Statistical Learning Theory

1 Introductionto StatisticalLearningTheoryOlivierBousquet 1, St ephaneBoucheron2, andG aborLugosi31 Max-Planck ,D-72076T e deParis-Sud,Laboratoired'InformatiqueB^a timent 490,F-91405 Orsay tostudy, ina sta-tisticalframework, ,mostresultstake statisticallearningtheoryis toprovidea frameworkforstudy-ingtheproblemofinferen ce,thatis ofgainingknowledge,makingpredictions,mak ingdecisionsorconstructingmodelsfroma studiedinastatisticalframework,thatis thereareassumptionsofstatisticalnatureab outtheunderlyingphenomena(intheway thedatais generated).Asa motivationfortheneedofsuch a Theory , :(Vapnik,[1]) Nothingis morepracticalthana good ,a theoryofinferenceshouldbe abletogive a formalde nitionofwordslike Learning ,generalization,over tting,andalsotocharacterizetheperformanc eoflearningalgorithmssothat,ultimately, itmay goals:make thingsmorepreciseandderive understudyhereis theprocessof inductive inferencewhich canroughlybe summarizedasthefollowingsteps:176 Bousquet,Boucheron& a predictionsusingthismodelOfcourse,thisde nitionis verygeneralandcouldbe toactuallyautomatethisprocessandthegoalo fLearningTheoryis considera specialcaseoftheabove processwhich is ,thedataconsistsof instance-label pairs,wherethelabel is either+1or 1.

2 Givenasetof such pairs,a learningalgorithmconstructsa such thatit makesfewmistakeswhenpredictingthelabel ,givensometrainingdata,it is alwayspossibletobuilda functionthat ,inthepresenceofnoise,thismay notbe thebestthingtodoasit wouldleadtoa poorperformanceonunseeninstances(thisis usuallyreferredtoasover tting). between thustolookforregularities(ina sensetobe de nedlater)intheobservedphenomenon( ). , onewouldlook,ina collectionofpossiblemodels,foronewhich tswellthedata,butatthesametimeis assimpleaspossible(seeFigure1).Thisimmed iatelyraisesthequestionofhowtomeasureand quantifysimplicity of a model( 1;+1g-valuedfunction).StatisticalLearnin gTheory177It turnsoutthattherearemany waystodoso, ,peopletendtoprefermodelswhich have a smallnumberof ,thelengthofde-scriptionof a modelina codinglanguagecanbe anindicationof ,thenumberoffreeparametersofa modelisusuallyameasureof itscomplexity.

3 Surprisinglyasit may seem,thereis nouniversalwayofmeasuringsimplicity (oritscounterpartcomplexity)andthechoice ofa spe-ci actuallyinthischoicethatthedesignerofthe learningalgorithmintroducesknowledgeabou tthespeci ofuniversallybestchoicecanactuallybe formalizedinwhatiscalledtheNoFree Lunchtheorem,which inessencesaysthat,if thereisnoassumptiononhow thepast( )is relatedtothefuture( ),predictionis ,if thereis noa priorirestrictiononthepossiblephenomenat hatareexpected,itisimpossibletogeneraliz eandthereis thusnobetteralgorithm(any algorithmwouldbe beatenby anotheroneonsomephenomenon).Hencetheneed tomake assumptions,like thefactthatthephenomenonweobserve canbe explainedby a ,aswe said,simplicity isnotanabsolutenotion,andthisleadstothes tatement thatdatacannotreplaceknowledge,orinpseud o-mathematicalterms:Generalization=Data+ nowmake moreprecisetheassumptionsthataremadeby ,aswe saidbeforewe needtoassumethatthefuture( )observationsarerelatedtothepast( )ones,sothatthephenomenonis thecoreof thetheoryis a probabilisticmodelof thephenomenon(ordatagenerationprocess).

4 Withinthismodel,therelationshipbetweenpa standfutureobservationsis thattheybotharesampledindependentlyfromt hesamedistri-bution( ).Theindependenceassumptionmeansthateach informationabouttheunderlyingphenomenon( herea probabilitydistribution).Animmediatecons equenceofthisverygeneralsettingis thatonecancon-structalgorithms( ) thatareconsis-tent, which meansthat,asonegetsmoreandmoredata, canhave , any (consistent)algorithmcanhave anarbitrarilybadbehaviorwhengivena ,thisdiscussionindicatesthatgeneralizati oncanonlycomewhenoneaddsspeci learningalgorithmencodesspeci c178 Bousquet,Boucheron&Lugosiknowledge(ora speci cassumptionabouthow theoptimalclassi erlookslike),andworksbestwhenthisassumpt ionis satis edby theproblemtowhich it ,surveys,andresearch mono-graphshave beenwrittenonpatternclassi andBartlett[2], Breiman,Friedman,Olshen,andStone[3], Devroye, Gy or ,andLugosi[4], DudaandHart[5], Fukunaga[6],KearnsandVazirani[7], Kulkarni,Lugosi,andVenkatesh[8],Lugosi[9 ], McLach-lan[10], Mendelson[11], Natarajan[12], Vapnik[13, 14, 1],andVapnikandChervonenkis[15].

5 2 FormalizationWe consideraninputspaceXandoutputspaceY. Sincewe restrictourselvestobinaryclassi cation,we chooseY=f 1;1g. Formally, we assumethatthepairs(X;Y)2X Yarerandomvariablesdistributedaccordingt oanunknowndistributionP. We observe a (Xi;Yi) sampledaccordingtoPandthegoalis toconstructa functiong:X ! needa criteriontochoosethisfunctiong. Thiscriterionis a low proba-bility oferrorP(g(X)6=Y). We thusde netheriskofgasR(g) =P(g(X)6=Y) = g(X)6=Y :NoticethatPcanbe decomposedasPX P(YjX). We introducetheregressionfunction (x) = [YjX=x] =2 [Y= 1jX=x] 1 andthetargetfunction(orBayesclassi er)t(x) =sgn (x). Thisfunctionachievestheminimumriskoveral lpossiblemeasurablefunctions:R(t) = infgR(g):We willdenotethevalueR(t) byR , ,onehasY=t(X) almostsurely( [Y= 1jX]2f0;1g) andR = 0. Inthegeneralcasewe cande nethenoiselevelass(x) =min( [Y= 1jX=x];1 [Y= 1jX=x]) =(1 (x))=2 (s(X) =0 almostsurelyinthedeterministiccase)andth isgivesR = s(X).

6 Ourgoalis thustoidentifythisfunctiont, butsincePis unknownwe cannotdirectlymeasuretheriskandwe alsocannotknow canonlymeasuretheagreement ofa calledtheempirical risk:Rn(g) =1nnXi=1 g(Xi)6=Yi:It is commontousethisquantity asa thatthegoalis clearlyspeci ed,we reviewthecommonstrategiesto(ap-proximate ly)achieve denotebygnthefunctionreturnedby (g) butonlyapproximateit byRn(g), it wouldbe unreasonabletolookforthefunctionminimizi ngRn(g) ,whentheinputspaceis in nite,onecanalwaysconstructafunctiongnwhi ch perfectlypredictsthelabelsof thetrainingdata( (Xi) =Yi, andRn(gn) = 0),butbehaves ontheotherpoints astheoppositeof thetargetfunctiont, (X) = YsothatR(gn) =14. Soonewouldhave is thusnecessarytoprevent thisover waystodothis(which canbe combined).The rstoneis torestricttheclassoffunctionsinwhich theminimizationis performed,andthesecondis tomodifythecriteriontobe minimized( penalty for`complicated'functions).

7 Oneofthemoststraight-forward,yetit is usuallye cient. Theideais tochooseamodelGofpossiblefunctionsandtom inimizetheempiricalriskinthatmodel:gn= argming2 GRn(g):Ofcourse,thiswillworkbestwhenthet argetfunctionbelongstoG. However,it is raretobe abletomake such anassumption,soonemay want toenlargethemodelasmuch aspossible,whilepreventingover nitese-quencefGd:d=1;2;:::gofmodelsofinc reasingsizeandtominimizetheempiricalrisk ineach modelwithanaddedpenalty forthesizeofthemodel:gn= argming2Gd;d2 Rn(g) + pen(d;n):Thepenalty pen(d;n) givespreferencetomodelswhereestimationer roris ,usuallyeasiertoimplement approach consistsinchoosinga largemodelG(possiblydensein thecontinuousfunctionsforexample)andtode neonGaregularizer, typicallya normkgk. Thenonehastominimizetheregularizedempiri calrisk:gn= argming2 GRn(g) + kgk2:4 Strictlyspeakingthisis onlypossibleif theprobability distributionsatis essomemildconditions( ).

8 Otherwise,it may notbe possibletoachieveR(gn) = 1 buteveninthiscase,providedthesupportofPc ontainsin nitelymanypoints,a ,Boucheron&LugosiComparedtoSRM,thereis herea freeparameter , calledtheregularizationparameterwhich allowstochoosetheright trade-o between is usuallya hardproblemandmostoften, (andsuccessful)methodscanbe thought ,insomesense,be `normalized', correspondstosomeprobability probability distribution de nedonG(usuallycalleda prior),onecanuseasa regularizer log (g)5. Reciprocally, froma regularizerof theformkgk2,if thereexistsa measure onGsuch thatRe kgk2d (g)<1forsome >0,thenonecanconstructa ,ifGis thesetofhyperplanesin dgoingthroughtheorigin,Gcanbe identi edwith dand,taking astheLebesguemeasure,it is possibletogofromtheEuclideannormregulari zertoa sphericalGaussianmeasureon dasa of normalizedregularizer,orprior,canbe usedtoconstructanotherprobability distribution onG(usuallycalledposterior),as (g) =e Rn(g)Z( ) (g);where 0 is a freeparameterandZ( ) is a this canbe we take thefunctionmaximizingit,we recoverregularizationasargmaxg2G (g) = argming2G Rn(g) log (g);wheretheregularizeris 1log (g) , canbe ,beforecom-putingthepredictedlabel foraninputx, onesamplesa functiongaccordingto andoutputsg(x).

9 Thisprocedureis usuallycalledGibbsclassi inwhich thedistribution constructedabove canbe usedis bytakingtheexpectedpredictionofthefuncti onsinG:gn(x) = sgn( (g(x))):5 Thisis newhenGis ,onehastoconsiderthedensity associatedto . We nitedimensionalHilbertspacescanalsobe donebutit correspondencebetweenthenormofareproduci ngkernelHilbertspaceanda Gaussianprocesspriorwhosecovariancefunct ionis Rn(g) log (g) isequivalent tominimizingRn(g) 1log (g).StatisticalLearningTheory181 Thisis thispoint we have toinsistagainonthefactthatthechoiceof theclassGandoftheassociatedregularizeror prior,hastocomefroma prioriknowledgeaboutthetaskathand,andthe reis have presentedtheframeworkofthetheoryandthety pe ofalgorithmsthatit studies,we now introducethekindof resultsthatit have ina , a learningalgorithmtakes asinputthedata(X1;Y1);:::;(Xn;Yn) andproducesa functiongnwhich want toestimatetheriskofgn.

10 However,R(gn) is a randomvariable(sinceit dependsonthedata)andit cannotbe computedfromthedata(sinceit alsodependsontheunknownP). EstimatesofR(gn) thususuallytake modelG, itispossible,by introducingthebestfunctiong inG, withR(g ) = infg2GR(g), towriteR(gn) R = [R(g ) R ] + [R(gn) R(g )]:The rsttermontheright handsideis usuallycalledtheapproximationerror,andme asureshow wellcanfunctionsinGapproach thetarget(itwouldbe zeroift2 G).Thesecondterm,calledestimationerroris a randomquantity (itdependsonthedata)andmeasureshow usuallyhardsinceit , inStatisticalLearningTheoryit is preferabletoavoidmakingspeci cassumptionsaboutthetarget(such asitsbelongingtosomemodel),buttheassumpt ionsareratheronthevalueofR , is alsoknownthatforany (consistent)algorithm,therateofconvergen cetozerooftheapproximationerror8canbe arbitrarilyslowif onedoesnotmakeassumptionsabouttheregular ity ofthetarget,whiletherateofconvergenceoft heestimationerrorcanbe computedwithoutany such thefollowing:R(gn) =Rn(gn) + [R(gn) Rn(gn)]:Inthiscase,oneestimatestheriskby itsempiricalcounterpart,andsomequan-tity which approximates(orupperbounds)R(gn) Rn(gn).