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,FranceObjectifsetcontenudelenseignement1/28Planducours2Objectifsetcontenudelenseignement3S parateurs vastemarge4SVMlin aire(cass parable)5Donn esnons parableslin airementObjectifsetcontenudelenseignement2/28ObjectifLaraisond tredesstatistiques,cestdevousdonnerraison.AbeBurrowsMachines vecteursdesupport(SupportVectorMachinesSVM)etm thodes noyau:Separateurs vastemargeCaslin airements parableCasnon-s parablelin airementAstuce noyauSVMnonlin aireObjectifsetcontenudelenseignement3/28ObjectifSVMetm thodes noyau:SVMpourlar gressionOne-classSVMPrincipedesm thodes noyauxKernelPCA,KernelCCASVM noyauxmultiples(MultipleKernelLearning-MKL)Noyauxpourdesdonn esstructur sApplicationsS parateurs vastemarge3/28Planducours2Objectifsetcontenudelenseignement3S 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:Distanceentreleplusprocheexempledapprentissageetlasurfacedes paration.Basdapprentissage:{(xi,yi),i=1,...,n},xiRd,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 lhyperplan,bestled calageparrapport lorigineLesparam 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/28Planducours2Objectifsetcontenudelenseignement3S 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)e1,i=1,...,nLar solutiondeceprobl mepeutsefairedirectement(m thodesstochastiquedetypeGauss-Seidel,algorithmesdepointint rieur,detypeNewtonoudetypegradientconjugu )Ilesttoutefoismieuxdepasser laformationdualedeceprobl me:Ledualestunprobl mequadratiquedetaillen( galaunombredobservations)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 Lesconditionsn cessairesdoptimum:LbL(w,b, )=0= nXi=1 iyi=0LwL(w,b, )=0= w=nXi=1 iyixiSVMlin aire(cass parable)15/28SVMlin aire(cass parable)Parsubstitutiononobtientleprobl medual: max Pni=1 iPni,j=1 i jyiyjxTixjt.q. ie0,i=1,...,n(admissibilit duale)Pni=1 iyi=0(stationarit )Lesvecteursdesupportsontceuxpourlesquels ie0Ajouterdes chantillons lensembledapprentissagequinesontpasdesvecteurssupportsnaaucuneinfluencesurlasolutionfinalebestobtenu0partirdelarelation|xTsw+b|=1valablepourtouslesvecteursdesupportSVMlin aire(cass parable)16/28SVMlin aire(cass parable)Lafonctionded cisionpermettantdeclasserunenouvelleobservationxestf(x)=nXi=1 iyixTix+bLhyperplansolutionned pendqueduproduitscalaireentrelevecteurdentr eetlesvecteursdesupports.Cetteparticularit estloriginedela2emeinnovationmajeuredesSVM:lepassageparunespacededescriptiongr ce desfonctionsnoyau.Donn esnons parableslin airement16/28Planducours2Objectifsetcontenudelenseignement3S 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)Lid e:mod liserleserreurspotentiellespardesvariablesd cartpositives iassoci esauxobservations(xi,yi),i=1,...n.Siunpoint(xi,yi)v rifielacontraintedemargeyiwTxi+b)e1alorslavariabled cart(quiestunemesureducoutdelerreur)estnulle.Nousavonsdoncdeuxsituations:Pasderreur:yi(wTxi+b)e1=Ҿi=0Erreur:yi(wTxi+b)<1=Ҿi=1yi(wTxi+b)>0Donn esnons parableslin airement19/28SVMlin aire(casnons parable)Onassocie cetted finitionunefonctioncoutappel e coutcharni re : i=max(cid:16)0,1yi(wTxi+b)(cid:17)Unseulpointestmalclass (pointbleu).L cartmesureladistancedupoint lamargenum riquedelhyperplans parateur.Donn esnons parableslin airement20/28SVMlin aire(casnons parable)Probl medoptimisationdanslecasdesdonn esnon-s parable: minw,b(12||w||2Pni=1 it.q.yi(w xi+b)e1 i,i=1,...,n ie0,i=1,...,nSitouteslesvariablesd cart i=0,onretrouveleprobl mes parablelin airementPuisqueilfautminimiserlesdeuxtermessimultan mentonintroduitunevariabled quilibrageC>0quipermetdavoiruneseulefonctionobjectifdansleprobl medoptimisation:minw,b12||w||2+CnXi=1 iDonn esnons parableslin airement21/28SVMlin aire(casnons parable)Probl medoptimisationdanslecasdesdonn esnon-s parable: minw,b12||w||2+CPni=1 it.q.yi(w xi+b)e1 i,i=1,...,n ie0,i=1,...,nCestunevariabledep nalisationdespointsmalclass sfaisantuncompromisentrelalargeurdelamargeetlespointsmalclass s. isappellentaussivariablesressort(anglais:slackvariables)Donn esnons parableslin airement22/28SVMlin aire(casnons parable)Leprobl medualdevient: max Pni=1 i12Pni,j=1 i jyiyjxTixjt.q.Ce ie0,i=1,...,n(admissibilit duale)Pni=1 iyi=0(stationarit )Cjoueler leduneconstanteder gularisation(lar gularisationestdautantplusfortequeCestprochede0!)Ladiff rencepourleprobl medualeentrelecass parableetnons parableestquelesvaleursdes isontmajor esparC.Lespointsmalclass souplac sdanslamargeontun i=Cbestcalcul desortequeyif(xi)=1pourlespointstelsqueC> i>0Lafonctionded cisionpermettantdeclasserunenouvelleobservationxesttoujoursf(x)=nXi=1 iyixTix+bDonn 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