La lecture en ligne est gratuite
Télécharger
Universit´eParis7-DenisDiderotIntroduction`alIA er M1infoAnne´e2009-2010,1semestre Rappel de Cours n 2 Principesquisous-tendentlApprentissageSupervis´e
Fig.e´neelarId´eeg´1
Leprobl`emedelacat´egorisationvusouslangledelapprentissagepeuteˆtreillustr´ecomme suit : On dispose d’un ensemble d’emails (les individus sur la figure ) que l’on veut trier automati-quementen2cate´gories:spam/non-spam.Onsupposequilexisteunmoyen(unefonctionf) quipermetdedireaveccertitudepourchaqueemaila`quellecate´gorieilappartient.Malheu-reusement, cette fonctionf´eprredeleerntsepsliamesnuranousnconestinOhcun.eodcniois ensemble de descripteurs. Par exemple : lafr´equencedapparitiondeslettres(permetnotammentderetrouverlalangueutilise´e) certainsmotscle´s(sex,viagra,money,$,...) – lalongueur du message – lasource du message – l’objet – etc...
Cechangementderepre´sentationapourbutdemettreene´videncecertainstraitsdesemailsnon 1 explicit´esdansleurformeoriginale.Lide´eestalorsdarriver`ade´tecter,parlutilisationdune fonctionheimnedividusednturneelmeˆscsmoumsnlepsiotnev´tueneupt,drsedseircscrus cat´egorie.Danslecadredelapprentissagesupervise´,etpournotreexemple,celaveutdireque l’on dispose d’un certain nombre d’emails dont on connait la classe. La fonctionhe´erifndncucnieest,tiventdo´etattece´nn-celloceutseyhenhtopse`eat.Lchˆaeled tion d’exemples defopyhe`htenimenurd´deeretoncs,nusehqui approximefe`emedL.peorlb l’induction est de trouver une fonctionheuqidertsa`c,eibnelise´erag´enquihleabtiodrteˆpace depr´edirecorrectementlaclasse`alaquelleappartientunindividu(unemail)nonencorevu. L´evaluationdesperfomancesdehslteourtselitisuselpmexeseparcsiteecesnenaptnedqeeuno´s que nous connaissons durant la phase d’apprentissage. Une partie des emails dont nous connais-sonslaclasseserautilise´epourapprendrehste(cmbseenleldparpneitssasge).On´evaluera ensuitelaqualite´decettehypothesesurlerestedesemailsconnus(cestlensembledetest).
1 lechoixdecesdescripteursestdoncunee´tapecle´
1
Oncherchedonc`aminimiserladie´renceentrehetf:P(hMf)etonsouhaitedeplusquelaprobabilit´equehsoit proche defsttiose`rtrofe,quellesquesoietn lesdonn´ees:P(P(hMf))1γ
Apprentissage PAC :On a alors l’intuition que toute hypothesehvraiment mauvaise a une forteprobabilite´desetromperapr`esunpetitnombredetestssurdesindividusdontonconnais laclasse.Parcons´equent,onvaconside´rerquetoutehypothe`sequidonnedebonsre´sultatssur un ensemble d’exemplesuffisamentoleredni´valtiredeeuanchsdceetˆgardnpalleenete´U. hypoth`eseseraconside´re´ecommeProbablement Approximativement Correcte. Quecesoitpourlapprentissageoupourl´evaluationdeh, la question de la taille et de la forme desensemblesutilise´ssepose.Onvaalorschercher: a`de´nirquellequantit´eetquelstypesdexemplessontne´cessairespourpouvoirqualierun ensembledetestrepr´esentatif. a`quantierlenombredexemplesne´cessairespourquehsoit dans l’-boule autour def, c’est lecrit`eredeVapnik-Chervonenkis.
Leproble`medusurapprentissage(overtting):Ane´tilauqalednoitulvo´elerditu´eddelasolutionhlorsdelapprentissage,onrepr´esentel´evolutiondelerreurdeclassicationpour les ensembles de test (Etest) et d’apprentissage (Eapp) sur la figure .
Fig.2 – Ilustration du surapprentissage, taux d’erreur surEappetEtest[wikipedia]
La diminution du taux d’erreurEappse traduit bien par une diminution deEtestlors de la premie`repartiedelapprentissage.Cependant,bienqueletauxderreurenapprentissageconti-nueded´ecroitretoutaulongdelaphasedapprentissage,lerreursurlensembledetest(inconnu delalgorithmedapprentissage)sestabilisepuissemet`aaugmenter.Ceph´enom`enesexplique parunsurapprentissagedelalgorithmequige`n`erelhypoth`ese;h´enndeesenl-locaelodxu sembledapprentissagetenepermetplusdege´n´eraliser.Endautretermes,sionluidonne susament(trop)detempsrelativement`acescapacite´setaunombredexemplesconsid´er´es, l’algorithme d’apprentissage apprend ”par coeur” les exemples de l’ensemble d’apprentissage et devientincapabledeg´ene´raliser. 2 LecalculdeladimensiondeVapnik-Chervonenkisdoitdoncprendreencomptececrit`erepour lade´terminationdelatailledelensemble`aconside´rer. 2 calcul qui sort de cette introduction
2