La lecture en ligne est gratuite
Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres
Télécharger Lire

Rappel de cours sur l'Apprentissage Supervisé

De
2 pages
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 ...
Voir plus Voir moins
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
Un pour Un
Permettre à tous d'accéder à la lecture
Pour chaque accès à la bibliothèque, YouScribe donne un accès à une personne dans le besoin