Introduction to Machine Learning Lecture 11

1 Introduction to Machine LearningLecture 11 Mehryar MohriCourant Institute and Google Mohri - Introduction to Machine Learning2 BoostingpageMehryar Mohri - Introduction to Machine Learning3 Main idea: use weak learner to create strong method: combine base classifiers returned by weak simple relatively accurate base classifiers often not , how should base classifiers be combined?Boosting IdeaspageMehryar Mohri - Introduction to Machine LearningAdaBoost4 AdaBoost(S=((x1,y1),..,(xm,ym)))1fori 1tomdo2D1(i) 1m3fort 1toTdo4ht base classifier inHwith small error t=PrDt[ht(xi) =yi]5 t 12log1 t t6Zt 2[ t(1 t)]12 normalization factor7fori 1tomdo8Dt+1(i) Dt(i)exp( tyiht(xi))Zt9f Tt=1 tht10returnh=sgn(f)H { 1,+1}X.

2 (Freund and Schapire, 1997)pageMehryar Mohri - Introduction to Machine LearningNotesDistributions over training sample: originally uniform. at each round, the weight of a misclassified example is increased. observation: , sinceWeight assigned to base classifier : directy depends on the accuracy of at round .5Dt ththttDt+1(i)=Dt(i)e tyiht(xi)Zt=Dt 1(i)e t 1yiht 1(xi)e tyiht(xi)Zt 1Zt=1me yiPts=1 shs(xi) ts= +1(i)=e yift(xi)mQts=1 ZspageMehryar Mohri - Introduction to Machine Learning6 Illustrationt = 1t = 2pageMehryar Mohri - Introduction to Machine Learning7t = Mohri - Introduction to Machine Learning8= 1+ 3+ 2pageMehryar Mohri - Introduction to Machine Learning9 Bound on Empirical ErrorTheorem: The empirical error of the classifier output by AdaBoost verifies: If further for all , , then does not need to be known in advance: adaptive [1,T] (12 t) R(h) exp( 2 2T).

3 R(h) exp 2T t=1 12 t 2 . (Freund and Schapire, 1997)pageMehryar Mohri - Introduction to Machine Learning10 Proof: Since, as we saw, , Now, since is a normalization factor, R(h)=1mm i=11yif(xi) 0 1mm i=1exp( yif(xi)) 1mm i=1 mT t=1Zt DT+1(i)=T t= i=1Dt(i)e tyiht(xi)= i:yiht(xi) 0Dt(i)e t+ i:yiht(xi)<0Dt(i)e t=(1 t)e t+ te t=(1 t) t1 t+ t 1 t t=2 t(1 t).Dt+1(i)=e yift(xi)mQts=1 ZspageMehryar Mohri - Introduction to Machine Learning Thus, Notes: minimizer of . since , at each round, AdaBoost assigns the same probability mass to correctly classified and misclassified instances.

4 For base classifiers , can be similarly chosen to minimize .11 t (1 t)e + te (1 t)e t= te t tx [ 1,+1]ZtT t=1Zt=T t=12 t(1 t)=T t=1 1 4 12 t 2 T t=1exp 2 12 t 2 =exp 2T t=1 12 t 2 .pageMehryar Mohri - Introduction to Machine Learning12 Objective Function: convex and Coordinate DescentF( )=m i=1e yif(xi)=m i=1e yiPTt=1 tht(xi).e x0 1loss=pageMehryar Mohri - Introduction to Machine Learning13 Direction: unit vector with Since ,etThus, direction corresponding to base classifier with smallest error. et=argmintdF( t 1+ et)d = ( t 1+ et)=m i=1e yiPt 1s=1 shs(xi)e yi ht(xi)dF( t 1+ et)d =0= m i=1yiht(xi)exp yit 1 s=1 shs(xi) = m i=1yiht(xi)Dt(i) mt 1 s=1Zs = [(1 t) t] mt 1 s=1Zs =[2 t 1] mt 1 s=1Zs.

5 PageMehryar Mohri - Introduction to Machine Learning14 Step size: obtained viaThus, step size matches base classifier weight of AdaBoost. dF( t 1+ et)d =0 m i=1yiht(xi)exp yit 1 s=1 shs(xi) e yiht(xi) =0 m i=1yiht(xi)Dt(i) mt 1 s=1Zs e yiht(xi) =0 m i=1yiht(xi)Dt(i)e yiht(xi) =0 [(1 t)e te ]=0 =12log1 t Mohri - Introduction to Machine LearningAlternative Loss Functions15x (1 x)21x 1square lossx e xboosting lossx log2(1 +e x)logistic lossx max(1 x,0)hinge lossx 1x<0zero-one losspageMehryar Mohri - Introduction to Machine Learning16 Base learners: decision trees, quite often just decision stumps (trees of depth one).Boosting stumps: data in.

6 Associate a stump to each component. pre-sort each component: . at each round, find best component and threshold. total complexity: . stumps not weak learners: think XOR example!Standard Use in PracticeRNN=2(height(x),weight(x))O(Nmlo gm)O((mlogm)N+mNT)pageMehryar Mohri - Introduction to Machine LearningOverfitting?We could expect that AdaBoost would overfit for large values of , and that is in fact observed in some cases, but in various others it is not!Several empirical observations (not all): AdaBoost does not seem to overfit, furthermore: 17T10100100005101520error# distributionmarginFigure2 [69].

7 Left:thetrainingandtesterrorcurves(lower anduppercurves,respectively) :Thecumulativedistributionofmarginsofthe trainingexamplesafter5,100and1000iterati ons,indicatedbyshort-dashed,long-dashed( mostlyhidden)andsolidcurves, ,asbefore, , , , (inaquantifiablesense)sinceitconcentrate sontheexampleswiththesmallestmargins(whe therpositiveornegative).Boosting seffectonthemarginscanbeseenempirically, forinstance, letter ,evenafterthetrainingerrorreacheszero, ,quantitatively, [9],forinstance,7training errortest decision trees (Schapire et al., 1998).pageMehryar Mohri - Introduction to Machine LearningL1 Margin DefinitionsDefinition: the margin of a point with label is (the algebraic distance of to the hyperplane ):Definition: the margin of the classifier for a sample is the minimum margin of the points in that sample:18S=(x1.)

8 ,xm)xy x=0x=[h1(x),..,hT(x)] (x)=yf(x) mt=T t=y Tt=1 tht(x) 1=y x 1. =mini [1,m]yi xi Mohri - Introduction to Machine Learning19 Note: SVM margin: Boosting margin: Distances: distance to hyperplane : =mini [1,m]yi H(xi) 1, =mini [1,m]yiw (xi) w (x)= h1(x)..hT(x) . qw x+b=0|w x+b| w p,with1p+1q= Mohri - Introduction to Machine LearningConvex Hull of Hypothesis SetDefinition: Let be a set of functions mapping from to . The convex hull of is defined by ensemble methods are often based on such convex combinations of (H)={p k=1 khk:p 1, k 0,p k=1 k 1,hk H}.pageMehryar Mohri - Introduction to Machine LearningMargin Bound - Ensemble Methods Theorem: Let be a set of real-valued functions.

9 Fix . For any , with probability at least , the following holds for all :21 >0 >01 Hh conv(H)(Koltchinskii and Panchenko, 2002)R(h) R (h)+2 Rm H + log1 2m,where is a measure of the complexity of .Rm H HpageMehryar Mohri - Introduction to Machine LearningNotesFor AdaBoost, the bound applies to the functionsNote that does not appear in the f(x) 1= Tt=1 tht(x) 1 conv(H).TpageMehryar Mohri - Introduction to Machine Learning23No: AdaBoost may converge to a margin that is significantly below the maximum margin (Rudin et al., 2004) ( , 1/3 instead of 3/8)!Lower bound: AdaBoost can achieve asymptotically a margin that is at least if data separable and some conditions on the base learners (R tsch and Warmuth, 2002).

10 Several boosting-type margin-maximization algorithms: but, performance in practice not clear or not , Does AdaBoost Maximize the Margin? max2pageMehryar Mohri - Introduction to Machine Learning24 OutliersAdaBoost assigns larger weights to harder : Detecting mislabeled examples. Dealing with noisy data: regularization based on the average weight assigned to a point (soft margin idea for boosting) (Meir and R tsch, 2003).pageMehryar Mohri - Introduction to Machine Learning25 Advantages of AdaBoostSimple: straightforward : complexity for stumps: when and are not too large, the algorithm is quite guarantees: but still many questions.