Rappel de cours sur l'Apprentissage Supervisé

Cédric Herpson

Description

Universite Paris 7 - Denis Diderot Introduction a l’IAerM1 info Annee 2009-2010, 1 semestreRappel de Cours n 2Principes qui sous-tendent l’Apprentissage SuperviseFig. 1 { Idee generaleLe probleme de la categorisation vu sous l’angle de l’apprentissage peut ^etre illustre commesuit :On dispose d’un ensemble d’emails (les individus sur la gure ) que l’on veut trier automati-quement en 2 categories : spam/non-spam. On suppose qu’il existe un moyen (une fonction f )qui permet de dire avec certitude pour chaque email a quelle categorie il appartient. Malheu-reusement, cette fonction f nous est inconnue. On choisi donc de representer les emails par unensemble de descripteurs. Par exemple :{ la frequence d’apparition des lettres (permet notamment de retrouver la langue utilisee){ certains mots cles (sex,viagra,money,$, ...){ la longueur du message{ la source du{ l’objet{ etc...Ce changement de representation a pour but de mettre en evidence certains traits des emails non1explicites dans leur forme originale . L’idee est alors d’arriver a detecter, par l’utilisation d’unefonction h sur ces descripteurs, d’eventuels points communs entre les individus d’une m^emecategorie. Dans le cadre de l’apprentissage supervise, et pour notre exemple, cela veut dire quel’on dispose d’un certain nombre d’emails dont on connait la classe.La fonction h est une hypothese. La t^ache de l’inference inductive est, etant donne cette collec-tion ...

Informations

• Publié par: Fiom
• Nombre de lectures: 47
• Langue: Français

Extrait

Universit´eParis7-DenisDiderotIntroduction`al’IA er M1infoAnne´e2009-2010,1semestre ◦ Rappel de Cours n 2 Principesquisous-tendentl’ApprentissageSupervis´e

Fig.e´neelar–Id´eeg´1

Leprobl`emedelacat´egorisationvusousl’angledel’apprentissagepeuteˆ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.Onsupposequ’ilexisteunmoyen(unefonctionf) quipermetdedireaveccertitudepourchaqueemaila`quellecate´gorieilappartient.Malheu- reusement, cette fonctionf´eprredeleerntsepsliamesnuranousnconestinOhcun.eodcniois ensemble de descripteurs. Par exemple : –lafr´equenced’apparitiondeslettres(permetnotammentderetrouverlalangueutilise´e) –certainsmotscle´s(sex,viagra,money,$,...) – lalongueur du message – lasource du message – l’objet – etc...

Cechangementderepre´sentationapourbutdemettreene´videncecertainstraitsdesemailsnon 1 explicit´esdansleurformeoriginale.L’ide´eestalorsd’arriver`ade´tecter,parl’utilisationd’une fonctionheimnedividusedn’turneelmeˆscsmoumsnlepsiotnev’´tueneupt,drsedseircscrus cat´egorie.Danslecadredel’apprentissagesupervise´,etpournotreexemple,celaveutdireque l’on dispose d’un certain nombre d’emails dont on connait la classe. La fonctionhe´eri’fndncucnieest,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,e’ibnelise´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´epourapprendrehst’e(cmbseenl’el’dparpneitssasge).On´evaluera ensuitelaqualite´decettehypothesesurlerestedesemailsconnus(c’estl’ensembledetest).

1 lechoixdecesdescripteursestdoncunee´tapecle´

1

Oncherchedonc`aminimiserladiffe´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. Quecesoitpourl’apprentissageoupourl’´evaluationdeh, la question de la taille et de la forme desensemblesutilise´ssepose.Onvaalorschercher: –a`de´finirquellequantit´eetquelstypesd’exemplessontne´cessairespourpouvoirqualifierun ensembledetestrepr´esentatif. –a`quantifierlenombred’exemplesne´cessairespourquehsoit dans l’-boule autour def, c’est lecrit`eredeVapnik-Chervonenkis.

Leproble`medusurapprentissage(overfitting):Anfie´tilauqalednoitulvo´el’erditu´ed’ delasolutionhlorsdel’apprentissage,onrepr´esentel’´evolutiondel’erreurdeclassificationpour les ensembles de test (E test ) et d’apprentissage (E app ) sur la figure .

Fig.2 – Ilustration du surapprentissage, taux d’erreur surE app etE test [wikipedia]

La diminution du taux d’erreurE app se traduit bien par une diminution deE test lors de la premie`repartiedel’apprentissage.Cependant,bienqueletauxd’erreurenapprentissageconti- nueded´ecroitretoutaulongdelaphased’apprentissage,l’erreursurl’ensembledetest(inconnu del’algorithmed’apprentissage)sestabilisepuissemet`aaugmenter.Ceph´enom`enes’explique parunsurapprentissagedel’algorithmequige`n`erel’hypoth`ese;h´enndeesenl’-loc”a”elodxu sembled’apprentissagetenepermetplusdege´n´eraliser.End’autretermes,sionluidonne suffisament(trop)detempsrelativement`acescapacite´setaunombred’exemplesconsid´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´terminationdelatailledel’ensemble`aconside´rer. 2 calcul qui sort de cette introduction

2