第 1 页
Algorithmes Antoine Cornuéjols - Laurent Miclet ApprentissageAvec la participation d’Yves Kodratoff artificiel Concepts et algorithmes Préface de Tom Mitchell
资料内容
第 2 页
Apprentissage artificiel Antoine Cornuéjols est Les programmes d’intelligence artificielle sont aujourd’hui maître de conférences à capables de reconnaître des commandes vocales, d’analyser l’Institut d’informatique automatiquement des photos satellites, d’assister des experts d’entreprise et chercheur au pour prendre des décisions dans des environnements complexes LRI de Paris XI à Orsay. Il et évolutifs (analyse de marchés financiers, diagnostics médi- enseigne l’apprentissage artificiel dans plusieurs caux…), de fouiller d’immenses bases de données hétérogènes, grandes écoles et en DEA. Ses telles les innombrables pages du Web… recherches portent notamment sur l’utilisation Pour réaliser ces tâches, ils sont dotés de modules d’apprentis- de l’apprentissage pour sage leur permettant d’adapter leur comportement à des situa- l’analyse de données en tions jamais rencontrées, ou d’extraire des lois à partir de bases médecine, en génomique et de données d’exemples. en vision artificielle. Laurent Miclet est Ce livre présente les concepts qui sous-tendent l’apprentissage professeur à l’ENSSAT de artificiel, les algorithmes qui en découlent et certaines de leurs Lannion. Il est responsable applications. Son objectif est de décrire un ensemble d’algo- du projet CORDIAL de l’INRIA rithmes utiles en tentant d’établir un cadre théorique unique et enseigne l’apprentissage pour l’ensemble des techniques regroupées sous ce terme artificiel et la « d’apprentissage artificiel ». reconnaissance des formes dans plusieurs grandes À qui s’adresse ce livre ? écoles et en DEA. Ses • Aux décideurs et aux ingénieurs qui souhaitent comprendre recherches portent en l’apprentissage automatique et en acquérir des connaissances particulier sur l’apprentissage pour le solides ; dialogue homme-machine et • Aux étudiants de niveau maîtrise, DEA ou école d’ingénieurs les technologies vocales. qui souhaitent un ouvrage de référence en intelligence Yves Kodratoff est directeur artificielle et en reconnaissance des formes. de recherches au CNRS et dirige au LRI l’équipe Sommaire Inférence et Apprentissage. I. Les fondements de l’apprentissage • Première approche théorique de Il s’intéresse à toutes les l’induction • Environnement méthodologique •II. Apprentissage par exploration• techniques de raisonnement inductif, et en particulier à Induction et relation d’ordre • Programmation logique inductive • Inférence grammaticale • leur application au data Apprentissage par évolution • III. Apprentissage par optimisation • Surfaces mining. séparatrices linéaires • Réseaux connexionistes • Réseaux bayésiens • Modèles de Markov Cet ouvrage est publié cachés •IV. Apprentissage par approximation et interpolation• Classification avec le concours de l’École non supervisée • Apprentissage par renforcement •Annexes et bibliographie. Nationale Supérieure des Sciences Appliquées et de Technologie (Lannion). Collection Technique et Scientifique des Télécommunications publiée sous l'égide de France Telecom Recherche et Développement
第 3 页
Apprentissage artificiel Concepts et algorithmes Ce document est la propriété exclusive de nona nina (ninasbalka@gmail.com) - 27 Octobre 2009 à 09:30
第 4 页
DANS LA MÊME COLLECTION G. DREYFUS et al. – Réseaux de neurones. Méthodologie et applications. N°11019, 2002, 380 pages. Y. COLLETTE, P. SIARRY. – Optimisation multiobjectif. N°11168, 2002, 328 pages. C. GUÉRET, C. PRINS, M. SEVAUX. – Programmation linéaire. 65 problèmes d’optimisation modélisés et résolus avec Visual XPress. N°9202, 2e édition, mars 2003, 365 pages + CD-Rom. CHEZ LE MÊME ÉDITEUR R. LEFÉBURE, G. VENTURI. – Data mining. Gestion de la relation client –Personnalisation de sites Web. N°9176, 2001, 392 pages, avec CD-ROM. M. BAZSALICZA, P. NAÏM. – Data mining pour le Web. Profiling – filtrage collaboratif – Personnalisation client. N°9203, 2001, 280 pages. M. JAMBU. – Méthodes de base de l’analyse des données. N°5256, 1999, 440 pages. M. GONDRAN, M. MINOUX. – Graphes et algorithmes. N°1571, 1995, 622 pages. BOURDA. – Introduction à l’informatique théorique. Ce document est la propriété exclusive de nona nina (ninasbalka@gmail.com) - 27 Octobre 2009 à 09:30N°1642, 1994, 236 pages.
第 5 页
Apprentissage artificiel Concepts et algorithmes Antoine Cornuéjols • Laurent Miclet Avec la participation d’Yves Kodratoff Deuxième tirage 2003 Ce document est la propriété exclusive de nona nina (ninasbalka@gmail.com) - 27 Octobre 2009 à 09:30
第 6 页
ÉDITIONS EYROLLES 61, Bld Saint-Germain 75240 Paris cedex 05 www.editions-eyrolles.com Ce document est la propriété exclusive de nona nina (ninasbalka@gmail.com) - 27 Octobre 2009 à 09:30 Le code de la propriété intellectuelle du 1er juillet 1992 interdit en effet expressément la photocopie à usage collectif sans autorisation des ayants droit. Or, cette pratique s’est généralisée notamment dans les établissements d’enseignement, provoquant une baisse brutale des achats de livres, au point que la possibilité même pour les auteurs de créer des œuvres nouvelles et de les faire éditer correctement est aujourd’hui menacée. En application de la loi du 11 mars 1957, il est interdit de reproduire intégralement ou partiellement le présent ouvrage, sur quelque support que ce soit, sans autorisation de l’Éditeur ou du Centre Français d’Exploitation du Droit de Copie, 20, rue des Grands-Augustins, 75006 Paris. © Groupe Eyrolles, 2002, ISBN : 2-212-11020-0 © France Telecom Recherche et Développement, 2002, ISBN : 2-212-11162-2
第 7 页
i Preface Lapprentissapables de s'amgeeliorerartificielautomatiquemens'interesset aaul'ecriturel du temps,de programmessoit sur la based'ordinateurde leur propreca- experience, soit a partir de donnees anterieures fournies par d'autres programmes. Dans le domaine scienti que relativement jeune de l'informatique, l'apprentissage ar- ti ciel joue un r^ole de plus en plus essentiel. Au debut de son existence, dans les annees 1950, l'informatique se resumait principalement a programmer des machines en leur speci ant ligne apres ligne la sequence d'instructions que l'ordinateur aurait a suivre. Autour des annees 1990, les logiciels etaient devenus si complexes qu'une alternative s'imposait naturellement: developper des techniques pour que les programmes puissent s'entra^ner a partir d'exemples. Le resultat est qu'il existe aujourd'hui de nombreux domaines d'application de l'informatique dans lesquels les methodes de l'apprentissage arti ciel sont employees pour entra^ner les logiciels. Mieux, le code resultant depasse de beaucoup en performance les realisations les plus abouties de programma- tion manuelle (( ligne apres ligne )). C'est ainsi que tous les meilleurs logiciels commercialises de reconnaissance de la parole sont fondes sur l'entra^nement de leurs programmes a la recon- naissance des di erents sons et mots. La plupart d'entre eux permettent m^eme a l'utilisateur d'accoutumer le systeme aux caracteristiques de sa voix. D'autres exemples existent dans des domaines tels que la vision par ordinateur, le traitement automatique du texte et la robotique. La discipline de l'apprentissage arti ciel peut donc deja revendiquer des succes dans un grand nombre de domaines d'application. Des logiciels de fouille de donnees sont utilises a grande echelle pour decouvrir quelle prescription est la plus ecace pour quel patient, a partir de l'analyse de chiers medicaux anterieurs. La palette des applications va de la prediction de la demande en energie, etant connu l'historique des consommations anterieures, a l'apprentissage de la reconnaissance de transactions frauduleuses par carte de credit, par examen des transac- tions passees averees frauduleuses. Au moment ou nous passons des cinquante premieres annees de l'informatique au les cinquante prochaines, il semble certain que le r^ole de l'apprentissage arti ciel ne cessera de cro^tre au centre de cette science. Pourquoi cette progression? La reponse fondamentale est que nous possedons desormais la comprehension de plusieurs principes calculatoires qui guident tout processus d'apprentis- sage, qu'il soit implemente sur une machine ou sur un humain. La discipline de l'apprentissage arti ciel possede desormais de riches fondements theoriques : on commence a savoir repondre a des questions comme : (( Combien au mimimum d'exemples d'entra^nement faut-il fournir a un programme d'apprentissage pour ^etre certain qu'il apprenne avec une ecacite donnee? )) et (( Quelles methodes d'apprentissage sont les plus ecaces pour tel ou tel type de probleme? )) Ce document est la propriété exclusive de nona nina (ninasbalka@gmail.com) - 27 Octobre 2009 à 09:30 Ces fondements proviennent de la theorie statistique de l'estimation, de la theorie de l'identi - cation et de la commande optimale, de travaux pionniers sur la complexite de l'apprentissage de grammaires ou plus recents sur l'inference bayesienne algorithmique. Cet ouvrage fournit au lecteur francophone l'introduction la plus complete a ce jour a l'ap- prentissage arti ciel. Il traite de la theorie et des applications de cette discipline sous un grand nombre d'aspects, en couvrant des sujets comme l'apprentissage bayesien, l'inference gramma- ticale ou l'apprentissage par renforcement. C'est avec plaisir que je recommande au lecteur de decouvrir ce livre, et a travers lui les idees et les methodes de l'apprentissage arti ciel. Tom M. Mitchell Pittsburgh, Pennsylvania, USA Le 29 Mai 2002
第 8 页
Ce document est la propriété exclusive de nona nina (ninasbalka@gmail.com) - 27 Octobre 2009 à 09:30
第 9 页
iii The idea of a learning machine may appear paradoxical to some readers. A. M. Turing, 1950. a Isabelle, Claire, Aurelie, Sebastien, Fanny et a Maura, Fabien, Marion Remerciements Ce livre est publie avec l'aide de l'ENSSAT. Nous remercions son directeur, Joel Crestel, d'avoir associe cet etablissement a la publication de cet ouvrage. Nous devons des remerciements particuliers aux personnes qui nous ont autorises a reprendre leurs ecrits, edites ou non, ainsi qu'a toutes celles qui nous ont fait bene cier de leur expertise Ce document est la propriété exclusive de nona nina (ninasbalka@gmail.com) - 27 Octobre 2009 à 09:30pour nous aider dans la redaction de cet ouvrage. Notre gratitude va aussi aux lecteurs critiques des versions preliminaires, ce qui inclut notablement une certaine proportion de nos etudiants. Il nous tient a cur de remercier tout specialement : Abdel Belad, Sami Bengio, Christophe Bernard, Marc Bernard, Olivier Boe ard, Michel Cartier, Christophe Choisy, Francois Coste, Francois Denis, Pierre Dupont, Daniel Fredouille, Colin de la Higuera, Yves Kodrato , Israel- Cesar Lerman, Stan Matwin, Engelbert Mephu Nguifo, Tom Mitchell, Jacques Nicolas, Celine Rouveirol, Michele Sebag, Dominique Snyers, Franck Thollard, Fabien Torre, Stephane Vanden- mersch et Jean-Daniel Zucker. L'adresse Web : www.editions-eyrolles.com contient les gures de cet ouvrage, les trans- parents des cours des auteurs et les errata.
第 10 页
Ce document est la propriété exclusive de nona nina (ninasbalka@gmail.com) - 27 Octobre 2009 à 09:30
第 11 页
Avant-propos Ceartilivreciel.prSonesenamte bitionles theories,est d'uneles algorithmespart d'uni eretlelescadreapplicationsmethodologique,de l'apprenet d'autretissage part de decrire un ensemble d'algorithmes utiles, de maniere coherente avec ce cadre, en n de faire conna^tre ses applications existantes et potentielles. A quoi sert l'apprentissage arti ciel? La plupart des programmes d'intelligence arti cielle possedent aujourd'hui un module d'apprentissage et tous les programmes de reconnaissance des formes sont fondes sur des algorithmes d'apprentissage. Et que font ces programmes? Ils sont capables de reconna^tre la parole humaine et de l'interpreter. Ils realisent une analyse automatique de photos satellites pour detecter certaines ressources sur la Terre. Ils assistent les experts pour prendre des decisions dans des environnements complexes et evolutifs, par exemple le marche nancier ou le diagnostic medical. Ils fouillent d'immenses bases de donnees heterogenes comme les millions de pages Web accessibles a tous. Ils analysent les donnees clientele des entreprises pour les aider a mieux cibler leurs campagnes de publicite. Ils participent aussi a des tournois: le 11 mai 1997, le tenant du titre de champion du monde du jeu d'echecs, Gary Kasparov, a ete battu en match par un programme. On sait donc programmer les ordinateurs pour leur faire executer des t^aches considerees comme intelligentes, de multiples facons et de maniere de plus en plus ecace. Cet ouvrage s'interesse a un aspect particulier de cette intelligence arti cielle: la faculte d'apprentissage. L'apprentissage arti ciel est une discipline dont les outils et les champs d'applications sont assez disparates. Cependant, les connaissances de base necessaires a sa comprehension sont essen- tiellement une culture generaliste que l'on trouve par exemple dans les ouvrages de mathematiques pour l'informatique: notions d'algebre lineaire, de probabilites, de combinatoire, d'analyse elemen- taire, d'algorithmique, de theorie des langages, de logique. Dans la mesure du possible, ces notions de base sont brievement rappellees selon la necessite des chapitres de ce livre. A qui s'adresse cet ouvrage? Ce document est la propriété exclusive de nona nina (ninasbalka@gmail.com) - 27 Octobre 2009 à 09:30 On peut tirer pro t de cet ouvrage en autodidacte, comme le fera par exemple un ingenieur qui cherche a conna^tre ce qui se cache derriere les mots ou a acquerir une initiation a des techniques qu'il ignore encore. On pourra aussi s'en servir comme d'un appui pour completer un enseignement: ce sera le cas pour un etudiant au niveau ma^trise, DEA ou ecole d'ingenieurs, ou comme d'un ouvrage de reference pour faire un cours sur le domaine.
第 12 页
vi Quelques applications de l'apprentissage arti ciel Voyons maintenant comment rendre un programme plus ecace en le dotant d'une possi- bilite d'apprentissage. Reprenons pour cela les applications de l'intelligence arti cielle et de la reconnaissance des formes citees ci-dessus. Un programme de reconnaissance de la parole augmente ses performances au fur et a mesure de son utilisation par la m^eme personne: c'est une experience qu'il est aujourd'hui facile de faire en pratique si on achete un logiciel personnel de dictee vocale. Un programme de detection des ressources terrestres apprend a reconna^tre une zone de pollution au milieu de la mer, a partir d'une base de donnees d'exemples d'images de zones connues comme propres ou comme polluees: cette base de donnees lui sert d'experience pour determiner sa decision sur une zone inconnue. Un programme de diagnostic sur un ensemble d'informations evolutives prises sur un patient doit avoir ete pourvu de connaissances, a partir de diagnostics de praticiens et d'experts sur des situations types. Mais il doit aussi avoir ete dote d'un module de generalisation, de facon a reagir correctement a des situations auxquelles il n'a jamais ete confronte exactement. Les moteurs de recherche sur le Web pourraient ^etre munis d'un module d'adaptation au style de navigation de l'usager: c'est une faculte souhaitable pour augmenter l'ergonomie de leur utilisation. Les programmes ne sont pas encore reellement agrementes de cette propriete, mais il est clair que c'est une condition necessaire pour franchir certains obstacles de communication si evidents actuellement. L'exploitation des chiers client d'une entreprise est souvent faite par un expert ou un programme expert qui utilise des regles explicites pour cibler un segment de clientele sus- ceptible d'^etre interesse par un nouveau produit. Mais ces regles peuvent ^etre acquises automatiquement, par un apprentissage dont le but est de fournir de nouvelles connais- sances expertes, a la fois ecaces et intelligibles pour l'expert. Un programme de jeu d'echecs possede en general une tres bonne ecacite a priori ; mais il est naturel d'essayer de le doter d'un module ou il puisse analyser ses defaites et ses victoires, pour ameliorer ses performances moyennes dans ses parties futures. Ce module d'apprentissage existe dans un certain nombre de programmes de jeux. Quelques de nitions de base Ce document est la propriété exclusive de nona nina (ninasbalka@gmail.com) - 27 Octobre 2009 à 09:30Apprentissage (sous entendu : arti ciel, automatique) (Machine Learning) Cette notion englobe toute methode permettant de construire un modele de la realite a partir de donnees, soit en ameliorant un modele partiel ou moins general, soit en creant completement le modele. Il existe deux tendances principales en apprentissage, celle is- sue de l'intelligence arti cielle et quali ee de symbolique, et celle issue des statistiques et quali ee de numerique. Fouille de donnees (Data Mining) ou Extraction de connaissances a partir des donnees (Knowledge Discovery in Data) La fouille de donnees prend en charge le processus complet d'extraction de connaissances: stockage dans une base de donnees, selection des donnees a etudier, si necessaire : nettoyage des donnees, puis utilisation des apprentissages numeriques et symboliques a n de proposer des modeles a l'utilisateur, en n validation des modeles proposes. Si ces modeles sont invalides par l'utilisateur, le processus complet est repete.
第 13 页
Avant-propos vii Precision vs. Generalisation Le grand dilemme de l'apprentissage. La precision est de nie par un ecart entre une valeur mesuree ou predite et une valeur reelle. Apprendre avec trop de precision conduit a un (( sur-apprentissage )), comme l'apprentissage par cur, pour lequel des details insigni- ants (ou dus^ au bruit) sont appris. Apprendre avec trop peu de precision conduit a une (( sur-generalisation )) telle que le modele s'applique m^eme quand l'utilisateur ne le desire pas. Les deux types d'apprentissage, numerique et symbolique, ont de ni des mesures de generalisation et c'est a l'utilisateur de xer le seuil de generalisation qu'il juge optimal. Intelligibilite (devrait ^etre Comprehensibility mais tend a devenir Understandability) Depuis quelques annees, principalement sous la poussee des industriels, les chercheurs se sont mis a essayer de contr^oler aussi l'intelligibilite du modele obtenu par la fouille de donnees. Jusqu'a present les methodes de mesure de l'intelligibilite se reduisent a veri er que les resultats sont exprimes dans le langage de l'utilisateur et que la taille des modeles n'est pas excessive. Des methodes speci ques de visualisation sont aussi utilisees. Classi cation, classement et regression. La classi cation, telle qu'elle est de nie en analyse de donnees, consiste a regrouper des ensembles d'exemples non supervises en classes. Ces classes sont souvent organisees en une structure (clustering). Si cette structure est un arbre, alors on parle de taxonomie ou de taxinomie (taxonomy). Sous l'in uence du mot anglais classi cation, on a tendance a confondre classi cation et classement. Ce dernier mot designe le processus de reconnais- sance en intension (par leur proprietes) de classes decrites en extension (par les valeurs de leurs descripteurs). Lorsque les valeurs a predire sont des classes en petit nombre, on parle de classi cation. Il s'agit par exemple de prevoir l'appartenance d'un oiseau observe a la classe (( canard )) ou (( oie )). La regression traite des cas ou les valeurs a predire sont numeriques, par exemple: nombre d'exemplaires de cet ouvrage qui seront vendus = 3900. Deux champs industriels de l'apprentissage arti ciel : la reconnaissance des formes et la fouille de donnees En quarante ans et plus d'existence, l'apprentissage arti ciel a fourni un grand nombre d'outils aux industriels et aux entrepreneurs. Nous les regroupons selon deux grands axes : la reconnaissance des formes et la fouille de donnees ou pour ^etre plus precis, l'extraction de connaissances des donnees. Le second domaine est le moins bien connu des deux bien qu'il soit porteur de reelles possi- Ce document est la propriété exclusive de nona nina (ninasbalka@gmail.com) - 27 Octobre 2009 à 09:30bilites economiques. Quant au premier, rappellons seulement que les methodes de l'apprentissage arti ciel sont a la base de la reconnaissance des images (ecriture manuscrite, signatures, detection de ressources par satellite, pilotage automatique, etc.), de la reconnaissance de la parole, du traitement avance des signaux bio-medicaux, etc. Pour mesurer l'extraordinaire vitalite des applications et des potentialites de la reconnaissance des formes, il sut par exemple de suivre la parution incessante des livres dans ce domaine. Pour ne citer que lui, l'editeur World Scienti c a une cinquantaine de titres a son catalogue sous la rubrique (( Applications de la reconnaissance des formes )) et les renouvelle a raison de pres d'une dizaine par an. Revenons maintenant a la fouille de donnees. Les problemes pratiques que peut resoudre en ce domaine l'apprentissage arti ciel se posent constamment dans la vie industrielle: comment distinguer un bon client d'un mauvais, comment reconna^tre un mauvais procede de fabrication et l'ameliorer, voila deux exemples frappants parmi d'autres. On constate pourtant que l'ancrage
第 14 页
viii de ce type d'application dans la vie industrielle ne date que des annees 1990, avec la naissance d'un discipline nouvelle, creee sous le nom de (( fouille de donnees )) (data mining ) ou ECD: (( extraction de connaissances a partir des donnees )) (knowledge discovery in databases, KDD). Nous presentons rapidement le domaine avant d'en donner l'etat de l'art industriel dans le dernier paragraphe de cet avant-propos. L'ECD est nee de la constatation que les trois approches qui permettaient de construire des modeles, a savoir les statistiques exploratoires, l'analyse des donnees et l'apprentissage symbo- lique automatique (ASA), sou raient de deux defauts communs: exiger des donnees presentees sous une forme tres rigide et faire peu de cas de l'intelligibilite des resultats. De plus, chacune presentait un defaut particulier g^enant leur emploi: les statistiques exploratoires et l'analyse des donnees s'adressaient a des donnees essentiellement numeriques et l'ASA se limitait aux donnees symboliques ou discretisees en intervalles de valeurs. Depuis, ces domaines ont evolue et les critiques a leur adresser ont change, mais tel etait l'etat de l'art dans les annees 1990. L'ECD est donc nee d'un quadruple e ort : permettre aux utilisateurs de fournir des donnees dans l'etat ou elles sont : ceci a donne naissance aux techniques de nettoyage des donnees (ce point sera developpe au chapitre 3) ; utiliser les donnees enregistrees sous forme de bases de donnees (en general relationnelles): ceci a provoque un large courant de recherche au sein de la communaute des BD interessee par la creation de modeles; fournir aux utilisateurs des outils capables de travailler sur des donnees mixtes, numeriques et symboliques ; construire des outils produisant une connaissance intelligible aux utilisateurs. C'est ainsi que l'ECD a pu trouver la large reconnaissance industrielle dont elle jouit actuelle- ment. Elle a commence a resoudre les deux problemes industriels principaux de l'analyse des donnees, ceux qui couten^ t le plus cher : le fait que le client est souvent imprecis dans la de nition du probleme qu'il se pose et le fait que les donnees dont il dispose sont souvent de qualite dis- cutable. L'etude des applications industrielles de l'ECD montre qu'il existe une assez forte demande en outils de creation de modeles, autrement dit en apprentissage arti ciel. Ceci se traduit par le fait qu'environ cent cinquante compagnies se sont specialisees dans ce domaine. Certaines de ces compagnies existent depuis plusieurs annees et d'autres se sont vendues fort cher. L'ensemble revele bien un secteur en progression raisonnable sur plusieurs annees. Notre estimation est que le marche de l'ECD est occupe par 60 % d'outils d'apprentissage statistique et 40 % d'outils d'apprentissage symboliques. Ces dernieres techniques etant moins Ce document est la propriété exclusive de nona nina (ninasbalka@gmail.com) - 27 Octobre 2009 à 09:30enseignees que les premieres dans les universites, on constate un hiatus entre l'enseignement et l'industrie. En tous cas, le present livre cherche a aller dans le sens d'un meilleur enseignement des methodes de l'apprentissage arti ciel, symbolique comme statistique. Les caracteristiques de l'apprentissage arti ciel Certaines des facultes que l'on peut lier naturellement a l'apprentissage ont ete citees dans les exemples ci-dessus: entra^nement, reconnaissance, generalisation, adaptation, amelioration, intelligibilite. Rappellons la de nition classique de l'apprentissage en sciences cognitives: (( capacite a ameliorer les performances au fur et a mesure de l'exercice d'une activite )). Cette de nition s'applique en particulier au comportement d'un joueur d'echecs au l des parties, ou l'assimi- lation de l'experience et la puissance de raisonnement se combinent dans sa progression. Elle
第 15 页
Avant-propos ix est aussi pertinente pour des t^aches perceptives: on s'habitue a un accent, a une ecriture. On accumule des bonnes et des mauvaises experiences. A partir d'elles, on sait, consciemment ou non, en abstraire ou faire evoluer des regles pour mieux e ectuer la t^ache. Nous avons mentionne une autre facette de l'apprentissage, souvent entrem^elee a la precedente : la faculte a generaliser rationnellement. Si une experience accumulee sur un certain nombre d'exemples a permis de tirer des regles de comportement, ces regles doivent s'appliquer aussi a des situations non encore rencontrees. Prenons quelqu'un qui apprend a conduire sur une berline de petite puissance. Des qu'il a merite le permis, la loi l'autorise a conduire une camionnette utilitaire ou une voiture de sport. C'est que les regles qu'il a apprises et les re exes qu'il a acquis s'appliquent aussi (plus ou moins directement) a ces vehicules. Qu'en est-il des machines? Des les debuts de l'intelligence arti cielle, c'est-a-dire en verite des l'apparition des ordinateurs, les chercheurs et les ingenieurs se sont poses le probleme de l'apprentissage1. L'apprentissage arti ciel dans sa situation actuelle est donc le produit d'une histoire de cinquante ans de recherches et de realisations. Comme on l'a vu, un grand nombre de t^aches d'intelligence arti cielle et de reconnaissance des formes s'appuient ou sont fondees sur des modules d'apprentissage. On verra dans cet ouvrage comment des programmes peuvent mettre en uvre un appren- tissage par amelioration du comportement, en general gr^ace a des techniques d'optimisation. On verra aussi qu'il est possible d'ecrire des programmes qui realisent un apprentissage par generalisation : quand on leur donne susamment d'exemples et le type du concept a apprendre, ils choisissent un concept qui n'est pas seulement valide sur les exemples qu'ils ont vus, mais qui sera egalement valable pour d'autres. C'est ainsi qu'un programme de reconnaissance de la parole ne peut pas (( entendre )) tous les sons avant d'elaborer une regle de decision. Il est ecrit pour extraire une methode de classi cation de ceux qu'on lui a presentes et traiter ensuite du mieux possible tous les sons qu'il aura a decoder. En realite, d'un point de vue informatique, la problematique n'est pas fondamentalement di erente dans les deux cas. Il s'agit dans le premier de faire evoluer des regles de comportement au l des exemples et dans le second d'extraire des regles a partir d'un ensemble d'exemples donne a priori. De m^eme que dans l'apprentissage naturel, un panachage de ces deux modes de fonctionnement est facile a concevoir dans l'apprentissage arti ciel. Il y a une autre facette de l'apprentissage que l'intelligence arti cielle explore. Quand un expert extrait des connaissances d'un ensemble de donnees, il apprend une certaine facon de les resumer. Mais le resultat de cet apprentissage ne sera operatoire que si la connaissance extraite est intelligible, transmissible de l'expert aux utilisateurs, interpretable (( en clair )). Il en est de Ce document est la propriété exclusive de nona nina (ninasbalka@gmail.com) - 27 Octobre 2009 à 09:30 m^eme pour un agent arti ciel: certaines t^aches d'apprentissage ne se mesurent pas seulement par leur qualite de prediction, mais aussi par la maniere dont les resultats sont expliques. Cet aspect est relie operationnellement a l'intelligence arti cielle symbolique, aux systemes experts en particulier: mieux vaut souvent un petit nombre de regles comprehensibles qu'un fouillis de regles sophistiquees, m^eme avec une performance objective superieure. Avant de decrire plus en detail les motivations et l'organisation de cet ouvrage, precisons a travers trois exemples comment s'organise l'apprentissage dans des situations concretes. Cela nous permettra de donner une typologie des methodes et de presenter le plan de cet ouvrage. 1. A. Turing, dans son article Computing Machine and Intelligence, de la revue Mind en Octobre 1950 (Vol LIX, No 236) avait intitule un paragraphe Learning Machines. On peut consulter un fac-simile du manuscrit sur le site http://data.archives.ecs.soton.ac.uk/turing/ et le texte a : http://www.abelard.org/turpap/turpap.htm
第 16 页
x Trois exemples d'apprentissage Un exemple ornithologique Imaginons un etang sur lequel nagent des oies et des cygnes (nous admettons qu'il n'y a pas d'autres oiseaux dans cette region). Le brouillard est tombe, quand arrivent deux avimateurs dont l'un est expert et l'autre debutant. Ils n'apercoivent en arrivant qu'une partie des animaux, de maniere peu distincte. Pour l'expert, l'identi cation est cependant facile (il n'est pas expert pour rien). Quant au debutant, il doit se contenter de mesurer ce qui lui para^t caracteristique : le niveau de gris du plumage et la taille de la b^ete. Pour representer le probleme, il va donc prendre ces deux mesures sur chaque animal qu'il voit et faire un graphique: il se place ainsi dans un certain espace de representation ( gure 0.1, a gauche). Sombre . . Sombre o . .. o o . . . o o o Clair . . Clair o o c . . . . o . . . c o c c . . . c c c . .. c c c o c c Blanc Blanc Taille de l’oiseau Taille de l’oiseau Fig. 0.1 { Le premier graphique de l'avimateur debutant represente les oiseaux observes places dans son espace de representation. Le second graphique represente les m^emes oiseaux, mais il est etiquete par l'expert. La lettre O signi e que l'oiseau est une oie, C qu'il est un cygne. Maintenant, comment lancer une phase d'apprentissage? Il faut que le debutant se place en situation d'apprenant vis-a-vis de l'expert, en lui demandant quelle est la decision correcte pour chaque oiseau. Une fois que l'expert a agi comme un professeur en donnant toutes les reponses, notre apprenant possede un graphique enrichi ( gure 0.1, a droite) qui va lui permettre de demarrer l'apprentissage proprement dit. Le probleme d'apprentissage est maintenant bien pose. Il peut s'enoncer ainsi: comment trouver une regle qui decide, dans l'espace de representation choisi, avec le moins d'erreurs Ce document est la propriété exclusive de nona nina (ninasbalka@gmail.com) - 27 Octobre 2009 à 09:30possibles, quel oiseau est une oie et quel oiseau est un cygne? La regle trouvee doit posseder de bonnes proprietes de generalisation, c'est-a-dire fonctionner au mieux non seulement sur ces exemples expertises, mais par la suite sur des oiseaux non encore observes. Que sera une telle regle? L'apprenant peut imaginer de tracer dans le plan de representation une ligne (courbe ou droite) qui separe les cygnes des oies. A partir des exemples connus, il aura alors induit une loi generale : pour tout oiseau observe qui se place (( sous )) cette ligne, il sera decide qu'il s'agit d'un cygne, d'une oie sinon. Mais on peut tracer une in nite de telles lignes. C'est ici que l'apprenant doit preciser le type des connaissances a acquerir, le type du concept a apprendre, en l'espece quelle est la forme generale de la ligne. Si l'apprenant impose que la ligne soit droite, le but de l'apprentissage sera de trouver la meilleure ligne droite, en optimisant d'un critere dont il est ma^tre. On remarque d'ailleurs qu'aucune droite ne separe parfaitement les exemples, mais c'est le prix a payer pour un concept aussi simple. Sur la gure 0.2 est montree la regle de decision que notre debutant en ornithologie
第 17 页
Avant-propos xi peut raisonnablement produire. S'il n'impose pas de restriction aussi stricte sur la forme de la ligne, il pourra obtenir une decision comme celle de la gure 0.3. Sombre Sombre o o o o o o o o o o o o c o o c Clair o Clair o o o c o c c c o c c c c c c c c c c c c c c o o c c c c Blanc Blanc Taille de l’oiseau Taille de l’oiseau Fig. 0.2 { Une regle de decision simple et une regle de decision complexe pour separer les oies des cygnes. Quand le brouillard se leve, d'autres oiseaux deviennent visibles. L'apprenant peut alors veri er la qualite de la regle qu'il a apprise, toujours avec l'aide de son professeur. Dans l'exemple donne sur la gure 0.3, il est facile de constater que la droite qu'il a choisie mene a une erreur environ une fois sur cinq2. Pas trop mal, pour un debutant ! Il est assez facile de transposer cet Sombre o o o oo o o oo o c Clair o c o o o c c o ooo c c c c c c c cc c c o cc c Blanc Taille de l’oiseau Fig. 0.3 { Le test de la regle simple sur d'autres oiseaux. Ce document est la propriété exclusive de nona nina (ninasbalka@gmail.com) - 27 Octobre 2009 à 09:30exemple a l'ecriture d'un programme d'apprentissage. Remarquons bien qu'un tel programme n'apprend pas tout court mais apprend quelque chose, en l'occurence une regle de decision sous la forme d'une equation de droite dans le plan. Cet exemple est caracteristique de ce que font les programmes de reconnaissance des formes. Ce type d'apprentissage par generalisation est d'une immense importance methodologique et pratique. Un exemple linguistique Maintenant, un autre exemple. Supposons que nous disposions d'un ensemble de phrases d'une certaine langue. Est-il possible d'ecrire un programme pour en apprendre automatiquement la grammaire? Pour une langue naturelle, le probleme est certainement complexe, ne serait-ce que parce qu'un tres grand nombre d'exemples est necessaire. Mais on peut essayer de le resoudre 2. La ligne courbe donnerait une erreur encore plus grande, nous reviendrons sur ce phenomene au chapitres 2 et 3 .
第 18 页
xii dans le cas d'un langage arti ciel comme ceux qui servent a interroger les bases de donnees ou pour un sous-ensemble bien delimite de langage naturel. Le langage des echanges entre un client et un employe d'agence de voyage en est un exemple. Dans de tels cas, il est e ectivement possible d'apprendre une grammaire. Il faut cependant imposer au programme des restrictions sur le type de la syntaxe que l'on cherche. L'espace de representation est ici l'ensemble de toutes les sequences de mots possibles, dont on ne conna^t que certaines, linguistiquement correctes. Mais comment de nir la grammaire a apprendre? On verra au chapitre 7 que si on oblige cette grammaire a ^etre un automate ni, on peut demontrer que tous les automates nis qui sont compatibles avec les exemples forment un ensemble limite et structure par une relation d'ordre. Le programme d'apprentissage a alors pour t^ache de chercher le meilleur automate dans cet ensemble structure, encore une fois au sens d'un critere a lui preciser. Remarquons encore que le programme n'apprend pas tout court, mais apprend quelque chose : en l'espece, une grammaire representee par un automate ni. Un exemple d'extraction de connaissances Une compagnie d'assurances cherche a lancer un nouveau produit, destine a couvrir le risque de vol d'objets de valeur a domocile. Elle veut faire une campagne de publicite ciblee aupres d'une partie de ses clients. Cette compagnie ne dispose que de peu de produits du m^eme type et par consequent sa base de donnees ne comporte qu'une petite proportion d'enregistrements ou un client est deja associe a une assurance contre le vol a domicile. De plus, comme ces clients possedent deja un produit analogue, ce n'est pas vers eux qu'il faut principalement cibler la campagne. Mais comment savoir si un client qui n'a pas encore d'assurance de ce type sera interesse par le nouveau produit? Une solution est de chercher un pro l commun aux clients qui se sont deja montres interesses par un produit de ce type pour viser parmi tous les clients ceux qui ont un pro l analogue. Que sera un tel pro l? Dans la base de donnees, chaque client est decrit par un certain nombre de champs, que l'on peut supposer binaires. Par exemples: (( ^age inferieur a trente ans )), (( possede une maison )), (( a un ou plusieurs enfants )), (( vit dans une zone a risque de vol )), etc. Certains champs peuvent ^etre non remplis: les clients qui ont seulement une assurance automobile n'ont pas ete interroges a la constitution de leur dossier sur l'existence d'un systeme d'alarme dans leur appartement. Ce document est la propriété exclusive de nona nina (ninasbalka@gmail.com) - 27 Octobre 2009 à 09:30 Une facon de constituer un pro l consiste a decouvrir des associations dans les donnees, c'est- a-dire des implications logiques approximatives. Disons par exemple que la plupart des clients qui possedent deja une assurance contre le vol d'objets de valeur a domicile sont plut^ot ^ages et n'ont en general qu'une voiture, mais haut de gamme. Il semble raisonnable de demarcher parmi tous les clients ceux qui repondent au m^eme pro l. L'hypothese est donc que posseder une seule voiture (mais de luxe) et ^etre d'^age mur^ est un pro l qui implique sans doute la possession a domicile d'objets de valeur. Ce type d'apprentissage releve de l'extraction de connaissances et de l'apprentissage non supervise. Ce dernier terme veut dire que le programme d'apprentissage se debrouille sans professeur: l'expertise est presente dans les donnees, mais de maniere implicite, c'est au pro- gramme de la decouvrir et de l'utiliser. La combinatoire sous-jacente a ce type d'apprentissage est evidemment tres importante.
第 19 页
Avant-propos xiii Organisation et plan de l'ouvrage L'organisation de cet ouvrage va se decrire maintenant a partir de quelques remarques sur les exemples precedents. Nous disons que, pour le premier, l'espace de recherche est peu structure. Pourquoi cela? Parce qu'on ne peut pas dire si telle droite est meilleure que telle autre sans les tester toutes les deux explicitement sur les donnees. Il s'agit de ce qu'on appelle en general un probleme d'optimisation. En revanche, dans le second exemple, nous avons parle d'une relation d'ordre entre deux solutions, intimement liee a leur qualite relative. Dans ce cas, une exploration partielle de l'ensemble des solutions est possible; elle sera guidee a la fois par sa structure algebrique et par les donnees, exemples et contre-exemples, alors que seules les donnees pouvaient conduire le programme dans le premier cas. Pour le troisieme exemple, il n'y a m^eme pas de guidage dans l'espace de recherche par des exemples et des contre-exemples. Ces remarques sont cruciales pour la conception des algorithmes. C'est la raison pour la- quelle nous avons choisi d'organiser le present ouvrage selon le critere suivant: nous traitons les methodes d'apprentissage en commencant par celles pour lesquelles l'espace de representation des concepts a apprendre est fortement structure, puis de celles pour lesquelles cette hypothese doit ^etre a aiblie et en n de celles pour lesquelles l'information a priori sur la nature des concepts a apprendre est tres faible ou nulle. Partie 1 : Les fondements de l'apprentissage Une partie de fondements methodologiques est d'abord necessaire. Nous y faisons une presen- tation generale de la problematique de l'apprentissage et nous donnons les de nitions de base (Chapitre 1 : De l'apprentissage naturel a l'apprentissage arti ciel). Le chapitre suivant propose une introduction aux theories de l'apprentissage par generalisation (Chapitre 2 : Le probleme de l'induction et les grands principes inductifs : une premiere approche). Un approfondissement de ce theme sera fait au chapitre 17. Le chapitre suivant traite de la representation des donnees et des connaissances et des types d'algorithmes qui sont mis en jeu par la suite (Chapitre 3 : L'environnement methodologique de l'apprentissage). Partie 2 : Apprentissage par exploration Nous analysons dans la deuxieme partie les methodes d'apprentissage quand les represen- tations des concepts forment des ensembles fortement structures. Nous l'avons appelee l'ap- prentissage par exploration. On y trouve d'abord une methode tres generale (Chapitre 4 : Induction et relation d'ordre : l'espace des versions), puis un chapitre sur l'apprentis- Ce document est la propriété exclusive de nona nina (ninasbalka@gmail.com) - 27 Octobre 2009 à 09:30sage dans la logique des predicats (Chapitre 5 : La programmation logique inductive). Le chapitre suivant complete ce point de vue en montrant comment modi er des concepts dans des espaces structures (Chapitre 6 : La reformulation et le transfert des connaissances). Le chapitre suivant (Chapitre 7 : L'inference grammaticale) traite de l'apprentissage des automates et des grammaires. En n les methodes d'apprentissage par evolution simulee, fondees sur l'exploration par algorithmes genetiques, sont exposees (Chapitre 8 : L'apprentissage par evolution simulee). Partie 3 : Apprentissage par optimisation et interpolation Dans la troisieme partie, les connaissances sur la structure des espaces sont plus faibles. Il s'agit de l'apprentissage par optimisation. On y trouve le probleme de l'apprentissage de droites, mentionne ci-dessus, et leur generalisation a des hyperplans (Chapitre 9 : L'apprentissage de surfaces separatrices lineaires). Une extension desormais classique mene aux reseaux
第 20 页
xiv connexionnistes multicouche (Chapitre 10 : L'apprentissage de reseaux connexionnistes). Nous considerons dans la m^eme famille l'apprentissage des arbres de decision et les techniques de combinaison de classi cateurs dont l'optimisation est cependant de nature assez di erente (Chapitre 11 : L'apprentissage par combinaison de decisions). Le fonctionnement et l'apprentissage des reseaux de probabilites conditionnelles est ensuite aborde (Chapitre 12 : L'apprentissage de reseaux bayesiens). Le chapitre suivant traite comme le chapitre 7 de l'apprentissage de certaines machines a produire des sequences, mais sous un aspect probabiliste (Chapitre 13 : L'apprentissage de modeles de Markov caches). Partie 4 : Apprentissage par approximation La derniere partie, intitulee l'apprentissage par approximation, traite des methodes les moins informees, celles ou l'espace des concepts cherches possede le moins de proprietes. Nous decrivons d'abord les techniques d'apprentissage de regles de classi cation par des methodes statistiques qui cherchent a approcher la regle de decision bayesienne. Ce chapitre inclut aussi certains aspects de l'apprentissage par analogie, en particulier la methodes des plus proches voisins (Chapitre 14 : L'approximation de la regle de decision bayesienne). Dans le chapitre suivant, on s'interesse aux donnees non etiquetees par un expert: il s'agit de les organiser et d'y decouvrir des regularites et des associations (Chapitre 15 : La classi ca- tion non supervisee et la decouverte automatique). Le chapitre suivant s'interesse aussi a un apprentissage numerique de type (( punition )) ou (( recompense )), typiquement applicable a l'apprentissage de son comportement par un robot (Chapitre 16 : L'apprentissage par renforcement). Partie 5 : Approfondissements et annexes techniques Ce livre se termine par des approfondissements et par la presentation de certains points tech- niques qui sont enonces sans demonstration dans les chapitres precedents, souvent a plusieurs occasions. Nous revenons d'abord sur les theories de l'apprentissage par generalisation (Cha- pitre 17 : Les grands principes inductifs : approfondissements). Parmi les annexes, celles qui traitent de l'algorithme estimation-maximisation et de l'optimisation par gra- dient sont sans doute les plus referencees dans les chapitres precedents. Le livre se conclut par une bibliographie decoupee en deux parties: la premiere donne des references generales recommandees pour leur qualite et leur accessibilite, essentiellement des livres. La seconde liste donne les references des autres livres, des articles et des rapports cites dans le texte. Ce document est la propriété exclusive de nona nina (ninasbalka@gmail.com) - 27 Octobre 2009 à 09:30 Guide de lecture Apres plus de quarante ans de recherches et de realisations en apprentissage arti ciel, il est dicile pour un non initie de savoir comment aborder ce domaine et comment s'y orienter. Nos collaborations avec des utilisateurs des techniques d'apprentissage et avec des chercheurs d'autres disciplines, comme notre activite d'enseignement et d'encadrement avec nos etudiants, nous ont amplement montre l'inter^et d'un ouvrage d'introduction coherent, articule autour de grandes lignes directrices. Il existe deja des livres d'enseignement et de recherche sur pratiquement chaque sujet aborde dans les chapitres de ce livre et nous ne manquons pas d'y faire reference. Mais si la somme des connaissances qui s'y trouvent est au total bien superieure a celle contenue dans notre livre, leur lecture conduit a des contradictions dans les notations, a des approfondissements theoriques
显示前 20 页。下载资料查看完整内容。
评论 (0)
暂无评论。快来抢沙发吧！