FAFU機器學習08-2 Ensemble Learning課件

FoundationsofMachineLearning

EnsembleLearning（集成學習）Top10algorithmsindataminingC4.5K-MeansSVMAprioriEM(MaximumLikelihood)PageRankAdaBoostKNNNa?veBayesCARTEnsembleLearningIntroductionCommonlyusedensemblelearningalgorithmsBaggingRandomforestBoostingsklearn.ensemble:EnsembleMethods2023/11/4EnsembleLearningLesson7-3IntroductionSomeonewantstoinvestinacompanyXYZ.Heisnotsureaboutitsperformancethough.So,helooksfor

adviceonwhetherthestockpricewillincreasemorethan6%perannumornot?Hedecidestoapproachvarious

expertshavingdiversedomainexperience:

EmployeeofCompanyXYZ:

right70%times.FinancialAdvisorofCompanyXYZ:

right75%times.StockMarketTrader:

right70%times.Employeeofacompetitor:

right60%times.MarketResearchteaminsamesegment:

right75%times.SocialMediaExpert:

right65%times.2023/11/4EnsembleLearningLesson7-4IntroductionSomeonewantstoinvestinacompanyXYZ.Heisnotsureaboutitsperformancethough.So,helooksfor

adviceonwhetherthestockpricewillincreasemorethan6%perannumornot?Hedecidestoapproachvarious

expertshavingdiversedomainexperience:

Inascenariowhenallthe6experts/teamsverifythat

it’sagooddecision(assumingallthepredictionsareindependentofeachother),wewillgetacombinedaccuracyrateof:1-30%*25%*30%*40%*25%*35%=99.92125%2023/11/4EnsembleLearningLesson7-5DefinitionEnsemblelearningisamachinelearningparadigmwheremultiplelearnersaretrainedtosolvethesameproblem.Also,calledmulti-classifiersystem（多分類器系統(tǒng)）,orcommittee-basedlearning（基于委員會的學習）.Incontrasttoordinarymachinelearningapproacheswhichtrytolearnonehypothesisfromtrainingdata,ensemblemethodstrytoconstructasetofhypothesisandcombinethemtouse2023/11/4EnsembleLearningLesson7-6Definition2023/11/4EnsembleLearningLesson7-7DefinitionIndividuallearners（個體學習器）areanumberoflearnersusedinanensembleBaselearners（基學習器）theindividuallearnersthatareusuallygeneratedfromtrainingdatabyasinglebaselearningalgorithmtoproduceahomogeneousensemble.Componentlearners（組件學習器）theindividuallearnersthatareusuallygeneratedfromtrainingdatabymultiplelearningalgorithmtoproduceaheterogeneousensemble.2023/11/4EnsembleLearningLesson7-8DefinitionWeaklearnersOnlyslightlybetterthanrandomguessErrorRate:

<50%MosttheoreticalanalysesworkweaklearnersStronglearnersRendersclassificationofarbitraryaccuracyErrorRate:

isarbitrarilysmallEnsemblelearningisappealingbecausethatisabletoboostweaklearnerstostronglearnersBycombiningdiverseofweaklearners2023/11/4EnsembleLearningLesson7-9DefinitionEnsemblelearningisappealingbecausethatisabletoboostweaklearnerstostronglearnersBycombiningdiverseofweaklearners2023/11/4EnsembleLearningLesson7-10Ensemblelearningisprimarilyusedtoimprovethe(classification,prediction,functionapproximation,etc.)performanceofamodel,orreducethelikelihoodofanunfortunateselectionofapoorone.Otherapplicationsofensemblelearningincludeassigningaconfidencetothedecisionmadebythemodel,selectingoptimal(ornearoptimal)features,datafusion,incrementallearning,nonstationarylearninganderror-correcting.2023/11/4EnsembleLearningLesson7-11ScenariosforusingensemblelearningModelSelection--Whatisthemostappropriateclassifierforagivenclassificationproblem?whattypeofclassifiershouldbechosenamongmanycompetingmodels,suchas

multilayerperceptron

(MLP),

supportvectormachines

(SVM),

decisiontrees,

naiveBayesclassifier,etc;givenaparticularclassification

algorithm,whichrealizationofthisalgorithmshouldbechosen-forexample,differentinitializationsofMLPscangiverisetodifferentdecisionboundaries,evenifallotherparametersarekeptconstant.

2023/11/4EnsembleLearningLesson7-12ScenariosforusingensemblelearningToomuchortoolittledataWhentheamountoftrainingdataistoolargetomakeasingleclassifiertrainingdifficult,thedatacanbestrategicallypartitionedintosmallersubsets.Eachpartitioncanthenbeusedtotrainaseparateclassifierwhichcanthenbecombinedusinganappropriatecombinationrule.Whenthereistoolittledata,thenbootstrapping

canbeusedtotraindifferentclassifiersusingdifferentbootstrapsamples

ofthedata,whereeachbootstrapsampleisarandomsampleofthedatadrawnwithreplacementandtreatedasifitwasindependentlydrawnfromtheunderlyingdistribution.2023/11/4EnsembleLearningLesson7-13ScenariosforusingensemblelearningDivideandConquerCertainproblemsarejusttoodifficultforagivenclassifiertosolve.2023/11/4EnsembleLearningLesson7-14ScenariosforusingensemblelearningDataFusionInmanyapplicationsthatcallforautomateddecisionmaking,itisnotunusualtoreceivedataobtainedfromdifferentsourcesthatmayprovidecomplementaryinformation.Asuitablecombinationofsuchinformationisknownas

dataorinformationfusion,

andcanleadtoimprovedaccuracyoftheclassificationdecisioncomparedtoadecisionbasedonanyoftheindividualdatasourcesalone.Theseheterogeneousfeaturescannotbeusedalltogethertotrainasingleclassifier(andeveniftheycould-byconvertingallfeaturesintoavectorofscalarvalues-suchatrainingisunlikelytobesuccessful).Insuchcases,anensembleofclassifierscanbeused,whereaseparateclassifieristrainedoneachofthefeaturesetsindependently.Thedecisionsmadebyeachclassifiercanthenbecombinedbyanyofthecombinationrulesdescribedbelow.2023/11/4EnsembleLearningLesson7-15ScenariosforusingensemblelearningConfidenceEstimationTheverystructureofanensemblebasedsystemnaturallyallowsassigningaconfidencetothedecisionmadebysuchasystem.Ifavastmajorityoftheclassifiersagreewiththeirdecisions,suchanoutcomecanbeinterpretedastheensemblehavinghighconfidenceinitsdecision.If,however,halftheclassifiersmakeonedecisionandtheotherhalfmakeadifferentdecision,thiscanbeinterpretedastheensemblehavinglowconfidenceinitsdecision.2023/11/4EnsembleLearningLesson7-16WhyensemblessuperiortosinglesSuppose,theerrorofbaselearnersAnensemblewithvotingcanbepresentedasTheerroroftheensembleis2023/11/4EnsembleLearningLesson7-17MethodsforconstructingensemblesSubsamplingthetrainingexamplesMultiplehypothesesaregeneratedbytrainingindividualclassifiersondifferentdatasetsobtainedbyresamplingacommontrainingset.ManipulatingtheinputfeatureMultiplehypothesesaregeneratedbytrainingindividualclassifiersondifferentrepresentations,ordifferentsubsetsofacommonfeaturevectorManipulatingtheoutputtargetsTheoutputtargetsforCclassesareencodedwithanL-bitcodeword,andanindividualclassifierisbuilttopredicteachoneofthebitsinthecodewordModifyingthelearningparametersoftheclassifierAnumberofclassifiersarebuiltwithdifferentlearningalgorithms,suchasnumberofneighborsinaKNNrule,initialweightsinanMPL.2023/11/4EnsembleLearningLesson7-18EnsemblecombinationrulesAlgebraiccombiners(代數(shù)結(jié)合)Algebraiccombinersare

non-trainablecombiners,wherecontinuousvaluedoutputsofclassifiersarecombinedthroughanalgebraicexpression.2023/11/4EnsembleLearningLesson7-19EnsemblecombinationrulesAlgebraiccombinersVotingbasedmethodsVotingbasedmethodsoperateonlabelsonlyMajority(plurality)votingWeightedmajorityvoting2023/11/4EnsembleLearningLesson7-20EnsemblecombinationrulesAlgebraiccombinersVotingbasedmethodsOthercombinationrules

Bordacount

behaviorknowledgespace

(Huang1993)"decisiontemplates"(Kuncheva2001)

Dempster-Schaferrule

(Kittler1998).Foradetailedoverviewoftheseandothercombinationrules,see(L.I.Kuncheva,CombiningPatternClassifiers,MethodsandAlgorithms.NewYork,NY:WileyInterscience,2005.).2023/11/4EnsembleLearningLesson7-21EnsembleLearningIntroductionCommonlyusedensemblelearningalgorithmsBaggingRandomforestBoostingsklearn.ensemble:EnsembleMethods2023/11/4EnsembleLearningLesson7-22CommonlyusedensemblelearningalgorithmsBagging(

bootstrap(自展法)aggregating)isoneoftheearliest,mostintuitiveandperhapsthesimplestensemblebasedalgorithmsBaggingcreatesanensemblebytrainingindividualclassifiersonbootstrapsamplesofthetrainset.Buildaclassifieroneachbootstrapsample2023/11/4EnsembleLearningLesson7-232023/11/4EnsembleLearningLesson7-242023/11/4EnsembleLearningLesson7-25H1H2H3H4SamplingN’exampleswithreplacementSet1Set2Set3Set4(usuallyN=N’)Ntrainingexamples2023/11/4EnsembleLearningLesson7-26y1H1H2H3H4y2y3y4Average/votingTestingdataxThisapproachwouldbehelpfulwhenyourmodeliscomplex,easytooverfit.e.g.decisiontreeTheperturbationinthetrainingsetduetothebootstrapresamplingcausesdifferenthypothesestobebuilt,particularlyiftheclassifierisunstableAclassifierissaidtobeunstableifasmallchangeinthetrainingdata(e.g.orderofpresentationofexample)canbeleadtoaradicallydifferenthypothesis.E.g.decisiontrees,neuralnetwork,logisticsregressionBaggingreducesvarianceIfasingleclassifierisunstable,thatis,ithashighvariance2023/11/4EnsembleLearningLesson7-27BaggingreducesvarianceIfasingleclassifierisunstable,thatis,ithashighvarianceBaggingworkswellforunstablelearningalgorithms.Baggingcanslightlydegradetheperformanceofstablelearningalgorithms.Baggingalmostalwayshelpswithregression,butevenwithunstablelearners,itcanhurtinclassification.2023/11/4EnsembleLearningLesson7-28RandomforestRandomForestsareanimprovement

overbaggeddecisiontrees.AproblemwithdecisiontreeslikeCARTisthattheyaregreedy.Theychoosewhichvariabletosplitonusingagreedyalgorithmthatminimizeserror.Assuch,evenwithBagging,thedecisiontreescanhavealotofstructuralsimilaritiesandinturnhavehighcorrelationintheirpredictions.Combiningpredictionsfrommultiplemodelsinensemblesworksbetterifthepredictionsfromthesub-modelsareuncorrelatedoratbestweaklycorrelated.2023/11/4EnsembleLearningLesson7-29RandomforestRandomForestsareanimprovement

overbaggeddecisiontrees.Randomforestchangesthealgorithmforthewaythatthesub-treesarelearnedsothattheresultingpredictionsfromallofthesubtreeshavelesscorrelation.Therandomforestalgorithmchangesthisproceduresothatthelearningalgorithmislimitedtoarandomsampleoffeaturesofwhichtosearch.2023/11/4EnsembleLearningLesson7-30RandomforestRandomForestsareanimprovement

overbaggeddecisiontrees.Motivation:reduceerrorcorrelationbetweenclassifiersMainidea:buildalargernumberofun-pruneddecisiontreesKey:usingarandomselectionoffeaturestosplitonateachnode（使用隨機選擇的特征子集來選擇最佳分割特征）2023/11/4EnsembleLearningLesson7-31RandomforestHowRandomforestworksEachtreeisgrownonabootstrapsampleofthetrainingsetofNexamples.AnumbermisspecifiedmuchsmallerthanthetotalnumberofvariablesM(e.g.m=sqrt(M)).Ateachnode,mvariablesareselectedatrandomoutoftheM.Thesplitusedisthebestsplitonthesemvariables.Finalclassificationisdonebymajorityvoteacrosstrees.2023/11/4EnsembleLearningLesson7-32gcForestDeepForest:TowardsAnAlternativetoDeepNeuralNetworksgcForest采用了cascade的結(jié)構(gòu)，每層接受特征信息，經(jīng)過處理后傳給下一層。每一層都是一個決策樹深林的總體，也就是由多個隨機深林組成。隨機深林的類型越多越好。論文中給定的有兩種類型的隨機深林，藍色表示randomforests，黑色表示complete-randomtreeforests。2023/11/4EnsembleLearningLesson7-33gcForestDeepForest:TowardsAnAlternativetoDeepNeuralNetworksIncontrasttodeepneuralnetworkswhichrequiregreateffortinhyper-parametertuning,gcForestismucheasiertotrain;evenwhenitisappliedtodifferentdataacrossdifferentdomainsinourexperiments,excellentperformancecanbeachievedbyalmostsamesettingsofhyper-parameters.ThetrainingprocessofgcForestisefficient,anduserscancontroltrainingcostaccordingtocomputationalresourceavailable.TheefficiencymaybefurtherenhancedbecausegcForestisnaturallyapttoparallelimplementation.Furthermore,incontrasttodeepneuralnetworkswhichrequirelargescaletrainingdata,gcForestcanworkwellevenwhenthereareonlysmall-scaletrainingdata.。2023/11/4EnsembleLearningLesson7-34PerformanceofgcForestImageCategorizationFaceRecognitionMusicClassificationHandMovementRecognition…2023/11/4EnsembleLearningLesson7-35gcForest

Officialimplementationforthepaper'Deepforest:Towardsanalternativetodeepneuralnetworks'Pythonimplementationofdeepforestmethod:gcForest2023/11/4EnsembleLearningLesson7-36BoostingBoosting

isa

machinelearningensemble

meta-algorithm

forprimarilyreducing

bias,andalsovariancein

supervisedlearning,andafamilyofmachinelearningalgorithmswhichconvertweaklearnerstostrongones.Boosting

alsocreatesanensembleofclassifiersbyresamplingthedata,whicharethencombinedbymajorityvotinginboosting,resamplingisstrategicallygearedtoprovidethemostinformativetrainingdata（最具信息的訓練數(shù)據(jù)，即前面分類器預(yù)測錯誤的訓練數(shù)據(jù)）foreachconsecutiveclassifier2023/11/4EnsembleLearningLesson7-37Boosting[Schapire,1989]2023/11/4EnsembleLearningLesson7-38AdaBoostAdaBoost

(AdaptiveBoosting)extendsboostingtomulti-classandregressionproblems.

usingre-weightinsteadofresampling,andadaptivelyweigheachdataexample.Dataexampleswhicharewronglyclassifiedgethighweight(thealgorithmwillfocusonthem)Eachboostingroundlearnsanew(simple)classifierontheweigheddataset.Theseclassifiersareweighedtocombinethemintoasinglepowerfulclassifier.2023/11/4EnsembleLearningLesson7-392023/11/4EnsembleLearningLesson7-40EnsembleLearningIntroductionCommonlyusedensemblelearningalgorithmsBaggingRandomforestBoostingsklearn.ensemble:EnsembleMethods2023/11/4EnsembleLearningLesson7-41sklearn.ensemble:EnsembleMethodsThe

sklearn.ensemble

moduleincludesensemble-basedmethodsforclassification,regressionandanomalydetection.2023/11/4EnsembleLearningLesson7-42ensemble.AdaBoostClassifier([…])AnAdaBoostclassifier.ensemble.AdaBoostRegressor([base_estimator,

…])AnAdaBoostregressor.ensemble.BaggingClassifier([base_estimator,

…])ABaggingclassifier.ensemble.BaggingRegressor([base_estimator,

…])ABaggingregressor.ensemble.RandomForestClassifier([…])Arandomforestclassifier.ensemble.RandomForestRegressor([…])Arandomforestregressor.ensemble.RandomTreesEmbedding([…])Anensembleoftotallyrandomtrees.ensemble.VotingClassifier(estimators[,

…])SoftVoting/MajorityRuleclassifierforunfittedestimators.sklearn.ensemble:EnsembleMethodsclass

sklearn.ensemble.BaggingClassifier(base_estimator=None,

n_estimators=10,

max_samples=1.0,

max_features=1.0,

bootstrap=True,

bootstrap_features=False,

oob_score=False,

warm_start=False,

n_jobs=None,

random_state=None,

verbose=0)Thisalgorithmencompassesseveralworksfromtheliterature.Whenrandomsubsetsofthedatasetaredrawnasrandomsubsetsofthesamples,thenthisalgorithmisknownasPasting

[1].Ifsamplesaredrawnwithreplacement,thenthemethodisknownasBagging

[2].Whenrandomsubsetsofthedatasetaredrawnasrandomsubsetsofthefeatures,thenthemethodisknownasRandomSubspaces

[3].Finally,whenbaseestimatorsarebuiltonsubsetsofbothsamplesandfeatures,thenthemethodisknownasRandomPatches

[4].2023/11/4EnsembleLearningLesson7-43sklearn.ensemble:EnsembleMethodsclass

sklearn.ensemble.RandomForestClassifier(n_estimators=’warn’,

criterion=’gini’,

max_depth=None,

min_samples_split=2,

min_samples_leaf=1,

min_weight_fraction_leaf=0.0,

max_features=’auto’,

max_