Apprentissage, Réseaux de Neurones et Modèles Graphiques (RCP209) - Méthodes d’Agrégation

Apprentissage,réseauxdeneuronesetmodèlesgraphiques(RCP209)Méthodesd’agrégationMarinFERECATU([email protected])http://cedric.cnam.fr/vertigo/Cours/ml2/DépartementInformatiqueConservatoireNationaldesArts&Métiers,Paris,FranceObjectifsetcontenudel’enseignement1/22Planducours2Objectifsetcontenudel’enseignement3Estimateursdevarianceélevée4Bagging5Forêtsaléatoires6BoostingObjectifsetcontenudel’enseignement2/22Objectif“Laraisond’êtredesstatistiques,c’estdevousdonnerraison.”—AbeBurrowsMéthodesd’agrégations:BaggingForetsAléatoiresBoostingEstimateursdevarianceélevée2/22Planducours2Objectifsetcontenudel’enseignement3Estimateursdevarianceélevée4Bagging5Forêtsaléatoires6BoostingEstimateursdevarianceélevée3/22AvantagesetdéfautsdesarbresdedécisionAvantages:Modèle”whitebox”:lerésultatestfacileàconceptualiseretàvisualiserIlsnécessitentpeudepréparationdedonnées(e.g.normalisation,etc.)Lecoutd’utilisationdesarbresestlogarithmiqueCapablesd’utiliserdesdonnéescatégoriellesetcontinuesCapablesdegérerdesproblèmesmulti-classeBoncomportementparrapportauxoutliersGèrentbienlesdonnéesmanquantesEstimateursdevarianceélevée4/22AvantagesetdéfautsdesarbresdedécisionProblèmes:Parfoislesarbresgénérésnesontpaséquilibrés(cequiimpliquequeletempsdeparcoursn’estpluslogarithmique).Ilestdoncrecommandéd’équilibrerlabasededonnéeavantlaconstruction,pouréviterqu’ilyauneclassedominante(entermedenombred’exemplesd’apprentissage)Sur-apprentissage:parfoislesarbresgénéréssonttropcomplexesetgénéralisentmal(solution:élagage,lecontrôledelaprofondeurdel’arbreetdelatailledesfeuilles)Ilssontinstables:deschangementslégèresdanslesdonnéesproduisentdesarbrestrèsdifférents.Changementsdesnœudsprochesdelaracineaffectentbeaucoupl’arbrerésultant.Cesontdesestimateursdevarianceélevée.Estimateursdevarianceélevée5/22EstimateursdevarianceélevéeEstimateursdevarianceélevée:RéductiondevarianceMoyennedesestimateurs,calculéssurdesdonnéeslégèrementdifférentesBaggingetRandomForests:utiliserlehasardpouraméliorerlesperformancesdesalgorithmesdebase(arbresdedécisionCART).AlgorithmesproposésparBreiman,etbeaucoupétudiésrécemment:L.Breiman.Baggingpredictors,MachineLearning,24(2),1996.L.Breiman.Randomforests,MachineLearning,45,2001.Bagging5/22Planducours2Objectifsetcontenudel’enseignement3Estimateursdevarianceélevée4Bagging5Forêtsaléatoires6BoostingBagging6/22BaggingBased’apprentissage:Attributs:A1,...,Ap,classe:CDonnéesd’apprentissage:(xi,yi),xi∈Rp,yi∈R,i=1,...,Nyipeuventêtredesvaleurscontinuesoudiscrètes(étiquettesdesclasses)xi=(a(i)1,...,a(i)p)OnconsidèreG(x)unmodèledeprédictionapprissurunéchantillondedonnéesz={(xi,yi)}ni=1(e.g.arbrededécisionCART)Bagging7/22BaggingBagging(Breiman,1996):Ontireauhasarddanslabased’apprentissageBéchantillonsavecremisezi,i=1,...,B(chaqueéchantillonayantnpoints)—appeléséchantillons”bootstrap”PourchaqueéchantillonioncalculelemodèleGi(x)Régression:agrégationparlamoyenneG(x)=1BPBi=1Gi(x)Classification:agrégationparvoteG(x)=Votemajoritaire(G1(x),...,GB(x))Bagging8/22BaggingC’estl’estimateurmoyennequiaidearéduirelavariance:X1,X2,...,Xnvariablesaléatoiresi.i.d.demoyenneµetvarianceσ21n(X1+X2+···+Xn)estdevarianceσ2/nCritèreperformanceetcalculdeB:l’erreurOOB(OutOfBag).Pourchaquexkélémentdelabased’apprentissageonagrègeleserreurssurlesGitelquexi/∈zi(aulieudefaireundécoupageclassiquetest/validationdelabased’apprentissage)OnchoisiBoul’erreursestabiliseetnedescendplus.Bagging9/22BaggingDéfautdubagging:LesestimateursGinesontpasenréalitéindépendants.Gisontcalculéssurdeséchantillonsquiserecouvrentfortement(tirageavecremise),etdoncilssontcorrélés.X1,X2,...,XBvariablesaléatoiresi.d.(maispasindépendantes)demoyenneµ,varianceσ2etcorrélationρ=Corr(Xi,Xj),∀i6=j.AlorsY=1B(X1+X2+···+XB)estdevariance:Var(Y)=ρσ2+1−ρBσ2QuandBestgrandle2emetermeestnégligeablemaisle1ernon.L’idéedesforetsaléatoiresestdebaisserlacorrélationentrelesGial’aided’uneétapesupplémentairederandomisation.Forêtsaléatoires9/22Planducours2Objectifsetcontenudel’enseignement3Estimateursdevarianceélevée4Bagging5Forêtsaléatoires6BoostingForêtsaléatoires10/22ForêtsaléatoiresForêtsaléatoires:AméliorationdubaggingpourlesarbresdedécisionCARTObjectif:rendrelesarbresutilisésplusindépendants(moinscorrélés)BonsrésultatssurtoutengrandedimensionTrèssimpleàmettreenœuvrePeudeparamètresForêtsaléatoires11/22ForêtsaléatoiresForêtsaléatoires(Breiman,2001):Ontireauhasarddanslabased’apprentissageBéchantillonsavecremisezi,i=1,...,B(chaqueéchantillonayantnpoints)Pourchaqueéchantillonionontireauhasardqattributsparmilespexistantsetonconstruitl’arbreCARTGi(x)surcesattributs.Régression:agrégationparlamoyenneG(x)=1BPBi=1Gi(x)Classification:agrégationparvoteG(x)=Votemajoritaire(G1(x),...,GB(x))Lesarbressontmoinscorréléscar:IlssontapprissurunensembledifférentdesattributsIlssontconstruitssurdeséchantillonsdifférentsEngénéral:p=√pForêtsaléatoires12/22ForêtsaléatoiresForêtsaléatoires(Breiman,2001):Onselimiteengénéralàdesarbrespastrèsprofonds(pourleBaggingilfautdesarbresprofondspourlimiterleurcorrélation:maislesarbrestrèsprofondssouffrentdesur-apprentissage)Chaquearbreestpetitdoncmoinsperformant,maisl’agrégationcompensepourcemanquement(chaqueattributseretrouvetypiquementdansplusieursarbres)CommepourleBaggingonutilisel’erreurOOBpourprévenirlesur-apprentissageForêtsaléatoires13/22ForêtsaléatoiresParamètres(valeurspardéfaut):Classification:q=√p,taillenœudminimale1;Régression:q=p/3,taillenœudminimale5.Enpratiquelesvaleurs”idéales”dépendentbeaucoupdelabase(etilfautlestrouverparcross-validation.)Forêtsaléatoires14/22ForêtsaléatoiresOOBvserreurdetestsurlabase”Spambase”.Forêtsaléatoires15/22ForêtsaléatoiresL’importancedesattributs:Gini:Lechangementdansl’impureté(ougaind’information)danschaquenoeudcumulésurtouslesarbresdelaforet.ErreurOOB:tousleséchantillonsOOBsontévaluéparl’arbreetl’erreurmesuré.Ensuiteonpermutealéatoirementlesvaleurssurchaqueattributjetonmesureletauxd’erreurànouveau.Lavaleurfinaleestladégradationmoyenne(changementdutauxd’erreurs)surtouslesarbres.Forêtsaléatoires16/22ForêtsaléatoiresL’importancedesattributs:Gini(gauche)vsOOBerror(droite).Boosting16/22Planducours2Objectifsetcontenudel’enseignement3Estimateursdevarianceélevée4Bagging5Forêtsaléatoires6BoostingBoosting17/22BoostingBoosting:Combinelessortiesdeplusieursclassifieursfaibles(weaklearners)pourobtenirunrésultatplusfort.Classifieurfaible:uncomportementdebasemeilleurquel’aléatoire(tauxd’erreurssous0.5pouruneclassificationbinaire)Donnéesd’apprentissage:(x1,y1),...,(xn,yn)UnefamilleGdeclassifieursfaiblesBoosting18/22BoostingBoosting19/22BoostingBoosting20/22BoostingBoosting:Étape2(a):gm(x)estleclassifieurquiminimisel’erreurpondérésurlabased’apprentissageargmingm∈GPni=1wi1yi6=gm(xi)L’erreuremdoitêtreinférieureà0.5,sinonαmdevientnégativeL’algorithmeminimisel’espérancedelafonctionperte”naturelle”l(y,g(x))=1yi6=g(xi)Boosting21/22BoostingBoosting22/22RéférencesLivresetarticles:L.Breiman.Baggingpredictors,MachineLearning,24(2),1996.L.Breiman.Randomforests,MachineLearning,45,2001.Hastie,Tibshirani,Friedman,Theelementsofstatisticallearning:Datamining,inference,andprediction,NewYork,SpringerVerlag,2006LaurentRouvière,Introductionauxméthodesd’agrégation:boosting,baggingetforêtsaléatoires,polycopiécours,(https://perso.univ-rennes2.fr/laurent.rouviere)