Ensembles(Bagging,Boosting,andallthat)

Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level, Jude Shavlik 2006,David Page 2007,Ensembles Lecture, Slide,*,Ensembles,(Bagging, Boosting, and all that),Old View,Learn,one,good model,New View,Learn a good,set,of models,Probably best example of interplay between “theory & practice” in Machine Learning,Nave Bayes, k-NN, neural net,d-tree, SVM, etc,Ensembles of Neural Networks,(or any supervised learner),Ensembles often produce accuracy gains of 5-10 percentage points!,Can combine “classifiers” of various types,E.g., decision trees, rule sets, neural networks, etc.,Network,Network,Network,INPUT,Combiner,OUTPUT,Combining Multiple Models,Three ideas,Simple (unweighted) votes,Standard choice,Weighted votes,e.g., weight by tuning-set accuracy,Train a combining function,Prone to,overfitting,?,“Stacked generalization” (,Wolpert,),Some Relevant Early Papers,Hansen & Salamen, PAMI:20, 1990,If (a) the combined predictors have,errors,that are,independent,from one another,And (b) prob any given model correct predicts any given testset example is, 50%, then,Think about flipping,N,coins, each with prob of coming up heads what is the prob,more than half,will come up heads?,Some Relevant Early Papers,Schapire, MLJ:5, 1990 (“Boosting”),If you have an algorithm that gets, 50%,on any distribution of examples, you can create an algorithm that gets, (100% -,), for any, 0,- Impossible by NFL theorem (later) ?,Need an infinite (or very large, at least) source of examples,- Later extensions (eg, AdaBoost) address this weakness,Also see Wolpert, “Stacked Generalization,”,Neural Networks, 1992,Some Methods for Producing “Uncorrelated” Members of an Ensemble,k,times randomly choose (,with,replacement),N,examples from a training set of size,N -,give each training set to a,std,ML algo,“Bagging” by Brieman,(MLJ, 1996),Want,un,stable algorithms,Part of HW3,Reweight examples each cycle (if wrong, increase weight; else decrease weight),“AdaBoosting” by Freund & Schapire,(1995, 1996),Some More Methods for Producing “Uncorrelated” Members of an Ensemble,Directly optimize,accuracy + diversity,Opitz used genetic algos),Melville ,DECORATE,algo),Different number of hidden units in a neural network, different,k,in,k,-NN, tie-breaking scheme, example ordering, etc,Various people,See 2005 and 2006 papers of Caruanas groupfor large-scale empirical study of ensembles,Variance/Diversity Creating Methods (cont.),Train with,different associated,tasks,Caruana (1996),Use different input features, randomly perturb training examples, etc,Cherkauer (UW-CS), Melville & Mooney,X,age,X,gender,X,income,“Multi-Task,Learning”,Other functions,related,to the main task of,X,Variance/Diversity Creating Methods (cont.),Assign each category an,error correcting code, and train on,each bit separately,Dietterich et al. (ICML 1995),Cat1 = 1 1 1 0 1 1 1,Cat2 = 1 1 0 1 1 0 0,Cat3 = 1 0 1 1 0 1 0,Cat4 = 0 1 1 1 0 0 1,Predicting 5 of 7 bits,correctly suffices,Want: Large Hamming distance between rows,Large Hamming distance between columns,Random Forests,(Breiman, MLJ 2001; related to Ho, 1995),A variant of BAGGING,Algorithm,Repeat,k,times,Draw with replacement,N,examples, put in train set,Build d-tree,but,in each recursive call,Choose (w/o replacement),i,features,Choose best of these,i,as the root of this (sub)tree,Do NOT prune,Let,N,= # of examples,F,= # of features,i,= some number 1/2,return,H,1, H,2, , H,i-1, (all previous hypotheses),Reweight,correct,exs:,Note: since ,i,1/2, w,i+1,w,i,Renormalize, so sum,wgts,= 1,i i+1,goto,1,Using the Set of Hypothesis Produced by AdaBoost,Output for example,x,=,where (false) 0, (true) 1,-,ie, count,weighted,votes for hypotheses that predict category,y,for input,x,Dealing with Weighted Examples in an ML Algo,Two approaches,Sample,from this probability distribution and train as normal (,ie, create,prob,dist from,wgts, then sample to create an,unweighted,train set),Alter,learning algorithm so it counts,weighted,examples and not just examples,eg,) from accuracy = # correct / # total,to,weighted,accuracy = ,w,i,of correct / ,w,i,of all,#2 preferred avoids sampling effects,AdaBoosting & ID3,Apply to PRUNED trees* otherwise no trainset error!,(Can avoid,i,= 0,via,m,-ests),ID3s calcs all based on weighted sums, so easy to extend to weighted examples,Boosting & Overfitting,Often get better test-set results, even when (and after),train error is ZERO,Hypothesis,(see papers by Schurmanns or Schapire),Still improving,number/strength,of votes even though getting all train-set exs correct,Wider “margins” between pos and neg exs relates to SVMs,test,train,Error (on,un,weighted examples),cycles,Empirical Studies,(from Freund reprinted in Dietterichs AI Mag paper),Error Rate of,C4.5,Error Rate of,Bagged,(,Boosted,) C4.5,(Each point one data set),Boosting and Bagging helped almost always!,Error Rate of,AdaBoost,Error Rate of,Bagging,On average, boosting slightly better?,Large Empirical Study of Bagging vs. Boosting,Opitz & Maclin (UW CS PhDs),JAIR,Vol 11, pp 169-198, 1999,Bagging almost always better than single D-tree or ANN (artificial neural net),Boosting can be much better than Bagging,However, boosting can sometimes be harmful (too much emphasis on “outliers”?),Thought Experiment,(possible class project),Consider a,learning curve,Plot, averaged across many datasets,error rates of,Best single model,Some ensemble method,We know that for many #examples,ensembles have lower error rates,What happens as,#examples,?,Boosting/Bagging/Etc Wrapup,An easy to use and usually highly effective technique,always,consider it (bagging, at least) when applying ML to practical problems,Does reduce “comprehensibility” of models,see work by Craven & Shavlik though (“rule extraction”),Also an increase in runtime, but cycles usually much cheaper than examples,