Apprentissage des réseaux de neurones et modèles graphiques

Apprentissage,réseauxdeneuronesetmodèlesgraphiques(RCP209)MachinesàvecteursdesupportSupportVectorMachines(SVM)MarinFERECATU&MichelCrucianu([email protected])http://cedric.cnam.fr/vertigo/Cours/ml2/DépartementInformatiqueConservatoireNationaldesArts&Métiers,Paris,FranceObjectifsetcontenudel’enseignement1/28Planducours2Objectifsetcontenudel’enseignement3Séparateursàvastemarge4SVMlinéaire(casséparable)5DonnéesnonséparableslinéairementObjectifsetcontenudel’enseignement2/28Objectif“Laraisond’êtredesstatistiques,c’estdevousdonnerraison.”—AbeBurrowsMachinesàvecteursdesupport(SupportVectorMachinesSVM)etméthodesànoyau:SeparateursàvastemargeCaslinéairementséparableCasnon-séparablelinéairementAstuceànoyauSVMnonlinéaireObjectifsetcontenudel’enseignement3/28ObjectifSVMetméthodesànoyau:SVMpourlarégressionOne-classSVMPrincipedesméthodesànoyauxKernelPCA,KernelCCASVMànoyauxmultiples(MultipleKernelLearning-MKL)NoyauxpourdesdonnéesstructurésApplicationsSéparateursàvastemarge3/28Planducours2Objectifsetcontenudel’enseignement3Séparateursàvastemarge4SVMlinéaire(casséparable)5DonnéesnonséparableslinéairementSéparateursàvastemarge4/28Problèmesdeclassification:Linéaire(haut)vs.non-linéaire(bas).Séparateursàvastemarge5/28SéparationlinéaireSéparateurslinéaires.Séparateursàvastemarge6/28SéparationlinéaireetmargeMargedesséparateurslinéaires.Séparateursàvastemarge7/28SéparationlinéaireetmargeMargedesséparateurslinéaires.Séparateursàvastemarge8/28SéparationlinéaireetmargeMargedesséparateurslinéaires.Séparateursàvastemarge9/28SéparationlinéaireetmargeMarge:Distanceentreleplusprocheexempled’apprentissageetlasurfacedeséparation.Basd’apprentissage:{(xi,yi),i=1,...,n},xi∈Rd,yi∈{−1,1}Fonctiondedécision:f(x)=wTx+b=0f(x)=0:hyperplan(surface)deséparationf(x)>0:classe1(yi=1)f(x)<0:classe2(yi=−1)Séparateursàvastemarge10/28SéparationlinéaireetmargeFonctiondedécision:f(x)=wTx+b=0Paramètres:westlanormaleàl’hyperplan,bestledécalageparrapportàl’origineLesparamètreswetbnesontpasuniques.kwetkbdonnentlamêmesurfacedeséparation:kwTx+kb=k(wTx+b)=0Séparateursàvastemarge11/28SéparationlinéaireetmargeQuellefonctiondedécisionchoisir:f(x)=wTx+b=0Solution:cellequimaximiselamarge.Séparateursàvastemarge12/28SéparationlinéaireetmargeSixsestunsupportvecteur,etH={x|wTx+b=0}alorslamargeest:marge=2d(x,H)=2|wTxs+b|||w||Onimposelaconditiondenormalisation|wTxs+b=1|pourlesvecteursdesupportxs:marge=2||w||SVMlinéaire(casséparable)12/28Planducours2Objectifsetcontenudel’enseignement3Séparateursàvastemarge4SVMlinéaire(casséparable)5DonnéesnonséparableslinéairementSVMlinéaire(casséparable)13/28SVMlinéaire(casséparable)Optimisationdelamarge:optimisationsouscontraintes(problèmeprimal)minw,b12||w||2t.q.yi(w·xi+b)≥1,i=1,...,nLarésolutiondeceproblèmepeutsefairedirectement(méthodesstochastiquedetypeGauss-Seidel,algorithmesdepointintérieur,detypeNewtonoudetypegradientconjugué)Ilesttoutefoismieuxdepasseràlaformationdualedeceproblème:Ledualestunproblèmequadratiquedetaillen(égalaunombred’observations)Pourcetypedeproblèmes(optimisationquadratique)ilexistedesalgorithmesbienétudiésettrèsperformantsLaformulationdualefaitapparaîtrelamatricedeGramXXTcequipermetdegérerlecasnonlinéaireàtraversdesnoyaux.SVMlinéaire(casséparable)14/28SVMlinéaire(casséparable)OnintroduitlesmultiplicateursαdeLagrange:L(w,b,α)=12||w||2+nXi=1αi[yi(wTx+b−1)]Lesconditionsnécessairesd’optimum:∂L∂bL(w∗,b∗,α∗)=0=⇒nXi=1α∗iyi=0∂L∂wL(w∗,b∗,α∗)=0=⇒w∗=nXi=1α∗iyixiSVMlinéaire(casséparable)15/28SVMlinéaire(casséparable)Parsubstitutiononobtientleproblèmedual:maxαPni=1αi−Pni,j=1αiαjyiyjxTixjt.q.αi≥0,i=1,...,n(admissibilitéduale)Pni=1αiyi=0(stationarité)Lesvecteursdesupportsontceuxpourlesquelsαi≥0Ajouterdeséchantillonsàl’ensembled’apprentissagequinesontpasdesvecteurssupportsn’aaucuneinfluencesurlasolutionfinaleb∗estobtenu0partirdelarelation|xTsw∗+b∗|=1valablepourtouslesvecteursdesupportSVMlinéaire(casséparable)16/28SVMlinéaire(casséparable)Lafonctiondedécisionpermettantdeclasserunenouvelleobservationxestf∗(x)=nXi=1α∗iyixTix+b∗L’hyperplansolutionnedépendqueduproduitscalaireentrelevecteurd’entréeetlesvecteursdesupports.Cetteparticularitéestl’originedela2emeinnovationmajeuredesSVM:lepassageparunespacededescriptiongrâceàdesfonctionsnoyau.Donnéesnonséparableslinéairement16/28Planducours2Objectifsetcontenudel’enseignement3Séparateursàvastemarge4SVMlinéaire(casséparable)5DonnéesnonséparableslinéairementDonnéesnonséparableslinéairement17/28SVMlinéaire(casnonséparable)Danslecasoulesdonnéesnesontpasséparableslinéairementonutiliseunetechniqueditedemargesouple,quitolèrelesmauvaisclassements:RajouterdesvariablesderelâchementdescontraintesξiPénalisercesrelâchementsdanslafonctionobjectif.Donnéesnonséparableslinéairement18/28SVMlinéaire(casnonséparable)L’idée:modéliserleserreurspotentiellespardesvariablesd’écartpositivesξiassociéesauxobservations(xi,yi),i=1,...n.Siunpoint(xi,yi)vérifielacontraintedemargeyiwTxi+b)≥1alorslavariabled’écart(quiestunemesureducoutdel’erreur)estnulle.Nousavonsdoncdeuxsituations:Pasd’erreur:yi(wTxi+b)≥1=⇒ξi=0Erreur:yi(wTxi+b)<1=⇒ξi=1−yi(wTxi+b)>0Donnéesnonséparableslinéairement19/28SVMlinéaire(casnonséparable)Onassocieàcettedéfinitionunefonctioncoutappelée«coutcharnière»:ξi=max(cid:16)0,1−yi(wTxi+b)(cid:17)Unseulpointestmalclassé(pointbleu).L’écartmesureladistancedupointàlamargenumériquedel’hyperplanséparateur.Donnéesnonséparableslinéairement20/28SVMlinéaire(casnonséparable)Problèmed’optimisationdanslecasdesdonnéesnon-séparable:minw,b(12||w||2Pni=1ξit.q.yi(w·xi+b)≥1−ξi,i=1,...,nξi≥0,i=1,...,nSitouteslesvariablesd’écartξi=0,onretrouveleproblèmeséparablelinéairementPuisqueilfautminimiserlesdeuxtermessimultanémentonintroduitunevariabled’équilibrageC>0quipermetd’avoiruneseulefonctionobjectifdansleproblèmed’optimisation:minw,b12||w||2+CnXi=1ξiDonnéesnonséparableslinéairement21/28SVMlinéaire(casnonséparable)Problèmed’optimisationdanslecasdesdonnéesnon-séparable:minw,b12||w||2+CPni=1ξit.q.yi(w·xi+b)≥1−ξi,i=1,...,nξi≥0,i=1,...,nCestunevariabledepénalisationdespointsmalclassésfaisantuncompromisentrelalargeurdelamargeetlespointsmalclassés.ξis’appellentaussivariablesressort(anglais:slackvariables)Donnéesnonséparableslinéairement22/28SVMlinéaire(casnonséparable)Leproblèmedualdevient:maxαPni=1αi−12Pni,j=1αiαjyiyjxTixjt.q.C≥αi≥0,i=1,...,n(admissibilitéduale)Pni=1αiyi=0(stationarité)Cjouelerôled’uneconstantederégularisation(larégularisationestd’autantplusfortequeCestprochede0!)LadifférencepourleproblèmedualeentrelecasséparableetnonséparableestquelesvaleursdesαisontmajoréesparC.Lespointsmalclassésouplacésdanslamargeontunαi=Cbestcalculédesortequeyif(xi)=1pourlespointstelsqueC>αi>0Lafonctiondedécisionpermettantdeclasserunenouvelleobservationxesttoujoursf∗(x)=nXi=1α∗iyixTix+b∗Donnéesnonséparableslinéairement23/28SVMlinéaire(casnonséparable)Implémentationssoftware:Torch,LibSVM,LibLinear,Scikit-LearnToch,http://torch.ch/LibSVM,https://www.csie.ntu.edu.tw/~cjlin/libsvm/LibLinear,https://www.csie.ntu.edu.tw/~cjlin/liblinear/Scikit-Learn,http://scikit-learn.org/PratiquementtouslesgrandsenvironnementdemodélisationmathématiquepossèdentimplémentationsperformantespourlesSVMetméthodesànoyaux(R,Matlab,Mathematica,Scipy,Torch,Scikit-learn,etc.)Donnéesnonséparableslinéairement24/28SVMlinéaire(casnonséparable)Séparationlinéaire(vecteursdesupportengras):Donnéesnonséparableslinéairement25/28SVMlinéaire(casnonséparable)Séparationlinéaire(vecteursdesupportengras):Donnéesnonséparableslinéairement26/28SVMlinéaire(casnonséparable)Laversionànoyaux(séancesuivante)permetdeséparermieuxlesclasses:Donnéesnonséparableslinéairement27/28SVMlinéaire(casnonséparable)Oumêmedesclassespluscompliquées:Donnéesnonséparableslinéairement28/28RéférencesLivres,articles,web:Steinwart,Christmann,SupportVectorMachines,Springer2008Scholkopf,Smola,LearningwithKernels,TheMITPress,2001Hastie,Tibshirani,Friedman,Theelementsofstatisticallearning:Datamining,inference,andprediction,NewYork,SpringerVerlag,2006—,Machinesàvecteurssupports(WikiStat),http://wikistat.fr