A SimpleAlgorithm for Learning StableMachines

We presentan algorithm for learningstablemachines whichis motivatedby recentresultsin statisticallearningtheory. The algorithm is similar to Breiman’ s baggingdespitesomeimportant differencesin thatit computesanensemblecombinationof machines trainedon small randomsub-samplesof an initial trainingset.A remarkablepropertyis thatit is oftenpossibleto justusetheempirical errorof thesecombinationsof machines for modelselection.We reportexperimentsusingsupport vectormachinesandneuralnetworks validatingthetheory.  Machine Learning, StatisticalLearning Theory, Bagging. 1 Intr oduction and Notation An importanttheoreticalapproach to analyzingthe performanceof learningmachinesis through studying their stability [7, 11, 3]. Various notionsof stability have beenproposedin the past[7, 11, 3], andhave beenusedto studyhow combining machinescaninfluence thegeneralizationperformance . Therehasalsobeena lot of experimentalwork showing thatcombininglearningmachines,for exampleusingBoostingor Baggingmethods [4, 13], very often leads to improvedgeneralizationperformance, andanumberof theoretical explanationshave beenproposed [13, 4, 10]. Bagging[4] is a particularensemblearchitectureconsistingof a votingcombinationof anumberof learningmachines. Eachmachine is obtainedby trainingthesameunderlinelearningalgorithm,e.g.a decisiontree,on a datasetdrawn randomly with replacementfrom an initial training set.The sizeof this sub-sampled datasetis equal to thesizeof theoriginal trainingset,but repetitionsof pointsoccur. Although theredoesnot exist a well-acceptedtheory of Bagging, therearesometheoreticalandexperimentalindicationsthatBagging worksbetterwhentheindividual machineis “unstable”[4]. Instability in thiscasemeansthatthemachinechangesa lot with changesof thetrainingset. In thispaperwepresentasimplealgorithmfor learningstablemachineswhich is basedon recentresultsin statisticallearningtheory . Thealgorithmis similar to Breiman’ s Baggingdespitesomeimportantdifferences:(i) we let eachmachineuseonly asmallpart(i.e. 5-20%)of theoriginal trainingdataformedby randomsamplingwith replacement, (ii) weconsiderthecasewhereclassificationis doneafter thresholdingthecombinationof therealvaluedoutputsof eachof themachines. Thealgorithmis namedSubaggingandis summarized in Figure1. BostonUniversity Boston,USA, E-mail:savina@math.bu.edu Biowulf Technologies, New-York, NY, USA, E-mail: andre@barnhi lltechnologies.com INSEAD, Fontainebleau, France E-mail: theodoros.evgeniou@insead.f r Dept. of Information Engineering,  A setof i.i.d. data ! " $#&%' (%*)+) -, A learningalgorithm .0/1 2 " $#&%' (%*)* 3 4 5 6 ( 7'8:9 denotesthesolutionof . trainedon ; ) For <= >%+ @?(?A?A B C Sub-sample D points from E Let GF H<I the obtained set. C Train . on to compute 7 8KJ'LNM O Output: P Q PM , 7 8 J LNM O Figure 1. Subagging algorithm. In a Relatedwork  we analyzedthe characteristicsof this algorithm. In particular, we developed probabilistic bounds on the distancebetweenthe empirical and the expectederror that, unlike in the standardanalysisof Bagging[4], arenot asymptotic. These bounds formally suggesthatSubaggingcanincreasethestability of the learningmachineswhen thesearenot stableanddecreaseotherwise.Theseresultsare reviewed in Section2. In Section3 we presentexperimentsvalidatingthis theoryusingsupport vectormachinesandneuralnetworksasthebasemachine.Theresultsindicate that Subaggingcansignificantly increasethe stability of thesemachineswhereasthe testerror is close(andsometimesbetter)to that of thesamemachinestrainedon thefull trainingset. Anotherimportantpracticalconsequenceof our theoreticalresults is that, sinceSubaggingimproves the stability, it can be easierto controlthegeneralizationerror. In Section4 we presentexperiments suggestingthat the empirical error can indeedbe a good estimate of the predictive performanceof Subagging. This is a remarkable propertywhich shows the advantageof our ensemblemethodover standardlearningalgorithmsbasedon empiricalrisk minimization. 2 Theory Let R S T S U V W $#&%+ @%*)+) -, be the training set.A learningalgorithm is a function .X/G Y Z $#&%' (%*)* 3 4 5 6 which, given a trainingset , returnsa realvaluedclassifier7 8 9[/ 3]\ ^ . Classificationof a new input is doneby taking thesign of 7*8:9+ : . For simplicity we consideronly deterministicandsymmetric algorithmsalthoughthe theory can be extendedto general algorithmsby addinga randomizingpreprocessingstep.We denote by thetrainingsetobtainedby removing point _ from ` , thatis theset ` 'a1 $ I) . Weusethefollowing notionof stability from : Definition: Wesaythatalearningalgorithmis b1 -stablewith respect to a trainingsetsof size c if thefollowing holds: dfe 4 $%+ (?@?A?A c()$ d d = g 1 / h 7 8 9' K K#i7 8kj 9 K Ah$lSb Roughlyspeakingtheoutputof a learningmachineonanew (test) point shouldnot change morethan b+ whenwe train themachine with any trainingsetof sizec andwhenwetrainthemachinewith the sametrainingsetbut onetrainingpoint (any point) removed.Bounds on stability for many algorithmswereprovedin . It is possibleto relatethe stability of a learningalgorithmto his generalizationerror, m L npo q(OIr s #t 17*8:9+ : vu , wheretheexpectationis taken w.r.t the unknown probability distribution generatingthe data and s is theHeavysidefunction, s wx y z% , if w|{~} , andzerootherwise(for a discussion, see[7, 11, 3]). In orderto statethe results we also definefor any given constant  the empirical error   emp on function 7 to be:   emp 7 4 	 Q -, 1    H is 0 for W#t , 1 for W{} , and  % for #tl l~} (a soft margin function).The following theoremfrom  expressestherelationbetweengeneralizationandstability. Theorem 1 For any given  , with probability %[# the generalization misclassificationerror of an algorithm that is b stable is boundedby:   emp 7'8:9A   b_    %  c  cb1   %A N %  We now discussa similar generalizationbound for an ensemble of machineswhereeachmachineusesonly D pointsdrawn randomly with theuniform distribution from thetrainingdata.To studysucha system,let us introducesomemorenotationsthat incorporatesthe “random sub-sampling”effect. Let  F 8:9 Tm 8 J r 7 8 J*u be the expectedcombinationof machinestrainedon sub-samplesof size D . Theexpectationis takenwith respectto thetrainingdata F of size D drawn uniformly from . Thenext theoremis from [8]. Theorem 2 For any given  , with probability %[# the generalization misclassificationerror of the expectedcombination  F 8 9 of machineseach usinga sub-sampleof size D of the training setand each havinga stability bpF is boundedby:   emp  F 8:9  D c bF    %  c   D*bfF   %( N %  Proof (Sketch): Theproof consistsof bounding thestability of the Subaggingprocedure.To this end, it is sufficient to show that the stability of  F 8 9 is upperbounded by  FI J andapply Theorem2.1 afterwards. This theoremholdsfor ensemblecombinations thataretheoretically definedfrom theexpectation m8KJ r 7'8KJu . It doesnot apply to a finite combinationof machines computedby Subagging, P Q PM , 7 8KJ'LNMHO . Yet, when B is large ; emp  F 8 9 E! emp P"Q PM , 7 8 J L M O and when B increasesthestabilityof thecombined learningsystemtends to thestabilityof theexpectation m 8 J r 7 8 J(u whichdoesnot improve after B haspasseda certainvalue.This valuemaycorrespond to the convergenceof thefinite sum P Q PMH, 7 8KJLNM O to its expectationw.r.t. F See[8] for aformaldiscussion. Thus,thecontrolof thetesterror by the empiricalerror is mainly dueto the sub-samplingeffect and not to thenumber of machinesusedin thecombination. Thatmeans that increasingB shouldn’t improvethiscontrol asmuch asreducing thevalueof D , a factwhich we experimentallyverifiedSeeSection 3. A consequenceof Theorem2 is that,sincethestability of  F 8:9 is smallerthan F  J , if thisstability is betterthanthestabilityof a single machine(which equalsb$ ¡ , theaverageof functions 7 8 J LNM O providesa betterbound.However, in theothercase,theboundis worse andSubagging shouldbeavoided.Wehave thefollowing corollary: Corollary 2.1 If a learningmachinesis b stableand  9  J  F , then combiningtheselearningmachinesvia Subagging doesnot provide a betterboundon the differencebetweenthe testand empirical error. Conversely, if (9  J { F , thencombiningtheselearningmachines leadsto a betterboundon thedifferencebetweenthetestandempir-