Ce d

ocum

ent e

st la

pro

pri

t e

xclu

sive

de O

livie

r BER

NHAR

D (ol

ivier.

simple

life@

gmail

.com)

- 12 m

ai 20

14

14:22

Antoine Cornujols estprofesseur AgroParisTech.Il enseigne lapprentissageartificiel dans plusieursgrandes coles et en Master.Ses recherches portentnotamment surlapprentissage en ligne,lapprentissage partir de flux de donnesainsi que sur desapplications enbioinformatique et sciencesdu vivant.

Laurent Miclet estprofesseur lENSSAT(www.enssat.fr) de Lannion,universit de Rennes-I, et responsable du projetCORDIAL de lIRISA(www.irisa.fr). Il enseigne lapprentissageartificiel et lareconnaissance des formesdans plusieurs grandescoles et en Master. Ses recherches portent enparticulier surlapprentissage pour ledialogue homme-machine etles technologies vocales.

Les programmes dintelligence artificielle sont aujourdhuicapables de reconnatre des commandes vocales, danalyserautomatiquement des photos satellites, dassister des expertspour prendre des dcisions dans des environnements complexeset volutifs (analyse de marchs financiers, diagnostics mdi-caux), de fouiller dimmenses bases de donnes htrognes,telles les innombrables pages du Web

Pour raliser ces tches, ils sont dots de modules dapprentissageleur permettant dadapter leur comportement des situationsjamais rencontres, ou dextraire des lois partir de bases dedonnes dexemples.

Ce livre prsente les concepts qui sous-tendent lapprentissageartificiel, les algorithmes qui en dcoulent et certaines de leursapplications. Son objectif est de dcrire un ensemble dalgo-rithmes utiles en tentant dtablir un cadre thorique pour len-semble des techniques regroupes sous ce terme dapprentis-sage artificiel .

qui sadresse ce livre ? Ce livre sadresse tant aux dcideurs et aux ingnieurs quisouhaitent mettre au point des applications quaux tudiantsde niveau Master 1 et 2 et en cole dingnieurs, qui souhaitentun ouvrage de rfrence sur ce domaine cl de lintelligenceartificielle.

SommaireI. Les fondements de lapprentissage Premire approche de linduction Environnement mthodologique II. Apprentissage par exploration Induction etrelation dordre Programmation logique inductive Transfert de connaissance Infrencegrammaticale Apprentissage par volution III. Apprentissage par optimisation Modles linaires Rseaux connexionnistes Rseaux baysiens HMM (modles de Markovcachs) Infrence darbres IV. Apprentissage par approximation etinterpolation Mthodes noyaux Apprentissage baysien Apprentissage parrenforcement V. Au-del de lapprentissage supervis Combinaisons dexperts Classification non supervise et fouille de donnes. Apprentissage semi-supervis Nouvelles tches et nouvelles questions Annexes et bibliographie.

Apprentissageartificiel

Code

dite

ur : G

1247

1 IS

BN : 9

78-2

-212

-124

71-2

A. C

ornu

jol

sL.

Mic

let

Appr

entis

sage

art

ifici

el

55E

Concepts et algorithmes

Apprentissageartificiel

Alg

orit

hmes

Antoine Cornujols - Laurent Miclet

Prface de Jean-Paul Haton

2 edition

2 edition

2 edition

2e dition

cornu2010 27/04/10 16:55 Page 1

Ce d

ocum

ent e

st la

pro

pri

t e

xclu

sive

de O

livie

r BER

NHAR

D (ol

ivier.

simple

life@

gmail

.com)

- 12 m

ai 20

14

14:22

Antoine Cornujols estprofesseur AgroParisTech.Il enseigne lapprentissageartificiel dans plusieursgrandes coles et en Master.Ses recherches portentnotamment surlapprentissage en ligne,lapprentissage partir de flux de donnesainsi que sur desapplications enbioinformatique et sciencesdu vivant.

Laurent Miclet estprofesseur lENSSAT(www.enssat.fr) de Lannion,universit de Rennes-I, et responsable du projetCORDIAL de lIRISA(www.irisa.fr). Il enseigne lapprentissageartificiel et lareconnaissance des formesdans plusieurs grandescoles et en Master. Ses recherches portent enparticulier surlapprentissage pour ledialogue homme-machine etles technologies vocales.

Les programmes dintelligence artificielle sont aujourdhuicapables de reconnatre des commandes vocales, danalyserautomatiquement des photos satellites, dassister des expertspour prendre des dcisions dans des environnements complexeset volutifs (analyse de marchs financiers, diagnostics mdi-caux), de fouiller dimmenses bases de donnes htrognes,telles les innombrables pages du Web

Pour raliser ces tches, ils sont dots de modules dapprentissageleur permettant dadapter leur comportement des situationsjamais rencontres, ou dextraire des lois partir de bases dedonnes dexemples.

Ce livre prsente les concepts qui sous-tendent lapprentissageartificiel, les algorithmes qui en dcoulent et certaines de leursapplications. Son objectif est de dcrire un ensemble dalgo-rithmes utiles en tentant dtablir un cadre thorique pour len-semble des techniques regroupes sous ce terme dapprentis-sage artificiel .

qui sadresse ce livre ? Ce livre sadresse tant aux dcideurs et aux ingnieurs quisouhaitent mettre au point des applications quaux tudiantsde niveau Master 1 et 2 et en cole dingnieurs, qui souhaitentun ouvrage de rfrence sur ce domaine cl de lintelligenceartificielle.

SommaireI. Les fondements de lapprentissage Premire approche de linduction Environnement mthodologique II. Apprentissage par exploration Induction etrelation dordre Programmation logique inductive Transfert de connaissance Infrencegrammaticale Apprentissage par volution III. Apprentissage par optimisation Modles linaires Rseaux connexionnistes Rseaux baysiens HMM (modles de Markovcachs) Infrence darbres IV. Apprentissage par approximation etinterpolation Mthodes noyaux Apprentissage baysien Apprentissage parrenforcement V. Au-del de lapprentissage supervis Combinaisons dexperts Classification non supervise et fouille de donnes. Apprentissage semi-supervis Nouvelles tches et nouvelles questions Annexes et bibliographie.

Apprentissageartificiel

Code

dite

ur : G

1247

1 IS

BN : 9

78-2

-212

-124

71-2

A. C

ornu

jol

sL.

Mic

let

Appr

entis

sage

art

ifici

el

Concepts et algorithmes

Apprentissageartificiel

Alg

orit

hmes

Antoine Cornujols - Laurent Miclet

Prface de Jean-Paul Haton

2 edition

2 edition

2 edition

2e dition

cornu2010 27/04/10 16:55 Page 1

Ce d

ocum

ent e

st la

pro

pri

t e

xclu

sive

de O

livie

r BER

NHAR

D (ol

ivier.

simple

life@

gmail

.com)

- 12 m

ai 20

14

14:22

Apprentissageartificiel

cornuejolstitre 26/04/10 17:23 Page 1

Ce d

ocum

ent e

st la

pro

pri

t e

xclu

sive

de O

livie

r BER

NHAR

D (ol

ivier.

simple

life@

gmail

.com)

- 12 m

ai 20

14

14:22

CHEZ LE MME DITEUR

Dans la mme collection

G. Dreyfus et al. Apprentissage statistique et rseaux de neurones. Mthodologie et applications. N12229, 3e dition 2008, 464 pages avec CD-Rom.

P. Nam, P.-H. WuillemiN, P. leray, O. POurret, a. Becker. Rseaux baysiens. N11972, 3e dition, 2007, 424 pages (collection Algorithmes).

G. fleury, P. lacOmme et a. taNGuy. Simulation vnements discrets. Modles dterministes et stochastiques Exemples dapplications implments en Delphi et en C++. N11924, 2006, 444 pages avec CD-Rom.

J. ricHalet et al. La commande prdictive. Mise en oeuvre et applications industrielles. N11553, 2004, 256 pages.

P. lacOmme, c. PriNs, m. sevaux Algorithmes de graphes. N11385, 2003, 368 pages, avec CD-Rom.

J. DrO, a. PtrOWski, P. siarry, e. taillarD Mtaheuristiques pour loptimisation difficile. Recuit simul, recherche tabou, algorithmes volutionnaires et algorithmes gntiques, colonies de fourmis N11368, 2003, 368 pages.

y. cOllette, P. siarry Optimisation multiobjectif. N11168, 2002, 316 pages.

C. Guret, c. PriNs, m. sevaux. Programmation linaire. 65 problmes doptimisation modliss et rsolus avec Visual XPress. N9202, 2000, 365 pages, avec CD-ROM.

Autres ouvrages

i. HurBaiN, avec la contribution dE. Dreyfus. Mmento Unix/Linux N11954, 2006, 14 pages.

c. Jacquet. Mmento LaTeX N12244, 2007, 14 pages.

r. rimel. Mmento MySQL. N12720, 2e dition 2010, 14 pages.r. m. stallmaN et al. Richard Stallman et la rvolution du logiciel libre. Une biographie autorise. N12609, 2010, 344 pages.

s. BOrDaGe, D. tHveNON, l. DuPaquier, f. BrOusse. Conduite de projet Web. N12665, 5e dition, 2010, 432 pages.

S. JaBer. Programmation GWT 2. Dvelopper des applications Ajax avec le Google Web Toolkit. N12569, 2010, 484 pages

Ce d

ocum

ent e

st la

pro

pri

t e

xclu

sive

de O

livie

r BER

NHAR

D (ol

ivier.

simple

life@

gmail

.com)

- 12 m

ai 20

14

14:22

Antoine Cornujols - Laurent Miclet

Apprentissageartificiel

cornuejolstitre 26/04/10 17:23 Page 2

2 e dition

Ce d

ocum

ent e

st la

pro

pri

t e

xclu

sive

de O

livie

r BER

NHAR

D (ol

ivier.

simple

life@

gmail

.com)

- 12 m

ai 20

14

14:22

DITIONS EYROLLES61, bd Saint-Germain75240 Paris Cedex 05

www.editions-eyrolles.com

Le code de la proprit intellectuelle du 1er juillet 1992 interdit en effet expressment la photocopie usage collectif sans autorisation des ayants droit. Or, cette pratique sest gnralise notamment dans les tablissements denseignement, provoquant une baisse brutale des achats de livres, au point que la possibilit mme pour les auteurs de crer des uvres nouvelles et de les faire diter correctement est aujourdhui menace.En application de la loi du 11 mars 1957, il est interdit de reproduire intgralement ou

partiellement le prsent ouvrage, sur quelque support que ce soit, sans autorisation de lditeur ou du Centre Franais dExploitation du Droit de Copie, 20, rue des Grands-Augustins, 75006 Paris. Groupe Eyrolles, 2002, 2010, ISBN : 978-2-212-12471-2

Remerciements Eric Bernauer pour la relecture de cet ouvrage.

Ce d

ocum

ent e

st la

pro

pri

t e

xclu

sive

de O

livie

r BER

NHAR

D (ol

ivier.

simple

life@

gmail

.com)

- 12 m

ai 20

14

14:22

i

Prface la deuxime dition

Apprendre.

Apprendre par lexemple, par lenvironnement, par la lecture, par le professeur, par cur. . .

Lapprentissage est multiforme et cest une caractristique de lintelligence. On comprend laremarque, trs opportunment mise en exergue par les auteurs, dAlan Turing, un des pionniers delintelligence artificielle. Prtendre doter une machine de cette facult propre ltre humain, ou tout le moins lanimal suprieur, pouvait paratre une gageure lpoque o cette remarque at nonce. Ce nest plus le cas aujourdhui et le vaste champ de lapprentissage par une machineest un domaine de recherche en pleine expansion et dans lequel il y a encore beaucoup faire !

Lapprentissage occupe une place privilgie au sein de lintelligence artificielle, et plus gnra-lement de linformatique. Cette place ne cessera de crotre. Les succs des programmes incluantun certain niveau dapprentissage automatique ou semi-automatique sont dj nombreux. Il suffitde songer la reconnaissance de la parole, la vision par ordinateur, le rejet de pourriels, la dtec-tion de transactions frauduleuses, le diagnostic, les jeux, la prdiction et la prvision, la fouillede donnes, etc. Les progrs spectaculaires enregistrs sont ds pour une bonne part aux effortsdes chercheurs qui sont parvenus une meilleure comprhension des processus dapprentissage,quils soient implants sur une machine ou quils existent dans le cortex dun animal.

Le moment est donc opportun de faire le point sur les connaissances acquises et les appli-cations. La dcision de proposer une profonde rvision de la premire dition de louvrage deA. Cornujols et L. Miclet arrive ainsi point nomm. Ces deux auteurs, aux comptences com-plmentaires, sont particulirement bien indiqus pour couvrir le vaste champ pluridisciplinairede lapprentissage. La premire dition, de trs grande qualit, a connu un succs considrable etjustifi, auprs dun public vari : tudiants, enseignants-chercheurs, ingnieurs. Elle est devenueun ouvrage de rfrence pour la communaut francophone proposant la somme la plus compltedides, de concepts, dalgorithmes et dapplications sur le sujet.

Le mme fil directeur original a t conserv pour cette seconde dition. Laccroissement desconnaissances se traduit directement dans le nombre de pages et lon ne peut que se fliciter quilexiste encore en France des diteurs acceptant de faire paratre un ouvrage scientifique originalde plus de 800 pages. . .

Je ne doute pas du succs de cette dition dont je recommande chaudement la lecture toutepersonne dsirant faire le point sur lapprentissage, un des plus grands dfis lanc la rechercheen intelligence artificielle.

Jean-Paul HatonNancy, 28 mars 2010

Ce d

ocum

ent e

st la

pro

pri

t e

xclu

sive

de O

livie

r BER

NHAR

D (ol

ivier.

simple

life@

gmail

.com)

- 12 m

ai 20

14

14:22

Ce d

ocum

ent e

st la

pro

pri

t e

xclu

sive

de O

livie

r BER

NHAR

D (ol

ivier.

simple

life@

gmail

.com)

- 12 m

ai 20

14

14:22

iii

The idea of a learning machine may appear paradoxical to some readers.A. M. Turing, 1950.

Isabelle, Claire, Aurlie, Sbastien, Fannyet Maura, Fabien, Marion

Prsentation de la deuxime dition

La premire dition de cet ouvrage, parue en septembre 2002, a reu un trs bon accueil, mon-trant lintrt dun livre couvrant largement les aspects de lapprentissage artificiel. Par ailleursson organisation raisonne autour de trois grandes parties : lapprentissage par exploration, paroptimisation, et par approximation et interpolation, luniformit des notations et un fil directeurtenu de bout en bout ont visiblement sduit ct de loffre des ouvrages existant en langueanglaise.

Au fil des annes, nous avons reu de nombreux courriels tmoignant la fois de la varit dupublic intress : tudiants, enseignant-chercheurs du domaine, spcialistes de domaines connexes,et grand public, et de ltendue gographique des publics touchs : la zone francophone bien sr,y compris le Canada et les pays du Maghreb, mais aussi des pays dEurope centrale.

Plus rapidement quattendu, les presque 2000 exemplaires de la premire dition ont t pui-ss. La question sest alors pose du choix entre une simple r-impression ou bien une mise jourconduisant une deuxime dition. Lexprience de la premire dition aurait du nous rendreprudents, mais la mmoire humaine tant volatile et tant donne la vitalit du domaine delapprentissage artificiel, il nous a paru pertinent de choisir la deuxime voie. Petit petit cepen-dant, nous avons ralis que non seulement les techniques et les rsultats avaient progress, maisque, plus largement, de nouvelles questions et de nouvelles approches taient apparues depuis2002. Il devenait difficile de se contenter de simplement adapter la premire dition, de nou-veaux chapitres taient ncessaires. Par ailleurs, une r-organisation de certaines parties taitgalement souhaitable pour tenir compte de nouvelles perspectives ou de laccent port des ap-proches classiques mais remises au got du jour, comme les mthodes linaires. Dun ravalementde faade, nous sommes insensiblement passs un chantier comprenant une r-organisation desespaces et des cloisons et llaboration dextensions significatives. Comme pour tout chantier,les dlais prvus ont t largement dpasss, puis dpasss encore, et certains moments, notrediteur pourtant conciliant, et nos familles pourtant trs comprhensives, ont pu croire que lafiction de Dino Buzzati, Le dsert des tartares , se ralisait. Ce nest donc finalement quen2010 quapparat cette deuxime dition.

Le fil directeur allant de lexposition des fondements conceptuels et mthodologiques, puis pro-gressant depuis des apprentissages trs guids par lexistence dune relation de gnralit danslespace des hypothses des apprentissages sappuyant sur des espaces de plus en plus dmunis

Ce d

ocum

ent e

st la

pro

pri

t e

xclu

sive

de O

livie

r BER

NHAR

D (ol

ivier.

simple

life@

gmail

.com)

- 12 m

ai 20

14

14:22

iv

de structure a t maintenu. Nous avons cependant ajout une partie indite sur de nouvellesquestions et de nouveaux types dapprentissage qui dpassent les cadres classiques des appren-tissages superviss, non superviss et par renforcement. Ainsi, par exemple, les apprentissagesdordonnancement, les apprentissages semi-superviss, actifs, partir de flux de donnes et enligne, font lobjet de sections ou de chapitres nouveaux.

Par ailleurs, le dveloppement considrable des mthodes base de fonctions noyau nous aconduit ddier tout un chapitre aux mthodes linaires classiques, et un grand chapitre auxmthodes noyaux. De mme, les mthodes densemble, boosting, bagging, etc. font maintenantlobjet dun chapitre part entire.

Finalement, tous les chapitres ont t mis jour pour tenir compte des progrs raliss. Denombreuses figures ont t refaites pour les rendre plus lisibles, et beaucoup dautres ont tajoutes. La typographie a volu afin de mieux mettre en vidence les dfinitions, les thormeset les formules principales. Lindex a t entirement revu et largement augment afin de faciliterlaccs direct aux concepts. Au bout du compte, et malgr notre souci de rester concis, le nombrede pages est pass en huit ans de 630 830. Cela reflte la vitalit du domaine et laccroissementdes ides, concepts et mthodes utiles connatre.

Nous esprons que cette deuxime dition sduira un public aussi large que pour la premiredition. Bienvenue dans le nouvel difice. Nous vous souhaitons une visite agrable, une ins-tallation heureuse et lenvie dapporter de nouvelles ides, douvrir de nouvelles fentres, et dedessiner de nouveaux horizons.

Antoine Cornujols et Laurent Miclet

Paris, Lannion, FranceLe 27 Mars 2010

Nous tenons remercier particulirement les personnes suivantes pour leur aide, leurs com-mentaires, leurs encouragements, et en gnral pour leurs contributions la ralisation de cetouvrage. Notre gratitude va aussi aux lecteurs critiques des versions prliminaires, ce qui inclutnotablement une certaine proportion de nos tudiants. Merci vous et aussi ceux que nousavons pu oublier ici mais qui sont importants pour nous.

Abdel Belad, Sami Bengio, Younes Bennani, Christophe Bernard, Marc Bernard, Olivier Bof-fard, Cdric Buche, Michel Cartier, Christophe Choisy, Delphine Cosandier, Franois Coste,Franois Denis, Grard Douaire, Pierre Dupont, Batrice Duval, Lou Fedon, Daniel Fredouille,Mirta Gordon, Colin de la Higuera, Ghazal Jaber, Yves Kodratoff, Isral-Csar Lerman, GalleLoosli, Christine Martin, Tristan Mary-huard, Stan Matwin, Maurice Milgram, Engelbert Me-phu Nguifo, Tom Mitchell, Jacques Nicolas, Laurent Orseau, Yann Prudent, Arpad Rimmel,Cline Rouveirol, Michle Sebag, Dominique Snyers, Franck Thollard, Fabien Torre, StphaneVandenmersch et Jean-Daniel Zucker.

Merci aussi notre ditrice, Muriel Shan-Sei-Fan, et Sophie Hincelin pour une relecturecomplte du manuscrit. Heureusement quil existe encore des diteurs de cette qualit.

Ce d

ocum

ent e

st la

pro

pri

t e

xclu

sive

de O

livie

r BER

NHAR

D (ol

ivier.

simple

life@

gmail

.com)

- 12 m

ai 20

14

14:22

v

Prface

Lapprentissage artificiel sintresse lcriture de programmes dordinateur capables de sam-liorer automatiquement au fil du temps, soit sur la base de leur propre exprience, soit partir dedonnes antrieures fournies par dautres programmes. Dans le domaine scientifique relativementjeune de linformatique, lapprentissage artificiel joue un rle de plus en plus essentiel. Au dbutde son existence, dans les annes 1950, linformatique se rsumait principalement program-mer des machines en leur spcifiant ligne aprs ligne la squence dinstructions que lordinateuraurait suivre. Autour des annes 1990, les logiciels taient devenus si complexes quune alter-native simposait naturellement : dvelopper des techniques pour que les programmes puissentsentraner sur des exemples. Le rsultat est quil existe aujourdhui de nombreux domaines dap-plication de linformatique dans lesquels les mthodes de lapprentissage artificiel sont employespour entraner les logiciels. Mieux, le code rsultant dpasse de beaucoup en performance lesralisations les plus abouties de programmation manuelle ligne aprs ligne . Cest ainsi quetous les meilleurs logiciels commercialiss de reconnaissance de la parole sont fonds sur lentra-nement de leurs programmes la reconnaissance des diffrents sons et mots. La plupart dentreeux permettent mme lutilisateur daccoutumer le systme aux caractristiques de sa voix.Dautres exemples existent dans des domaines tels que la vision par ordinateur, le traitementautomatique du texte et la commande de robot.Lapprentissage artificiel peut donc dj revendiquer des succs dans un grand nombre de do-

maines dapplication. Il en est ainsi de logiciels de fouille de donnes utiliss grande chelle pourdcouvrir la prescription la plus efficace pour un patient, partir de lanalyse de fichiers mdicauxantrieurs. Dautres applications vont de la prdiction de la demande en nergie, tant connulhistorique des consommations antrieures, lapprentissage de la reconnaissance de transactionsfrauduleuses par carte de crdit, par examen des transactions passes avres frauduleuses. Alorsque nous passons des cinquante premires annes de linformatique aux cinquante prochainesannes, il semble vident que le rle de lapprentissage artificiel ne cessera de crotre au centrede cette science.Pourquoi cette progression ? La rponse fondamentale est que nous possdons dsormais la

comprhension de plusieurs principes calculatoires qui guident tout processus dapprentissage,quil soit implment sur une machine ou sur un humain. La discipline de lapprentissage ar-tificiel possde dsormais de riches fondements thoriques : on commence savoir rpondre des questions comme : Combien au mimimum dexemples dentranement faut-il fournir un programme dapprentissage pour tre certain quil apprenne avec une efficacit donne ? et Quelles mthodes dapprentissage sont les plus efficaces pour tel ou tel type de problme ? Ces fondements proviennent de la thorie statistique de lestimation, de la thorie de lidentifi-cation et de la commande optimale, de travaux pionniers sur la complexit de lapprentissage degrammaires ou plus rcents sur linfrence baysienne algorithmique.Cet ouvrage fournit au lecteur francophone lintroduction la plus complte ce jour lap-

prentissage artificiel. Il traite de la thorie et des applications de cette discipline sous un grandnombre daspects, en couvrant des sujets comme les mthodes dapprentissage baysien, linf-rence grammaticale ou lapprentissage par renforcement. Cest avec plaisir que je recommande aulecteur de dcouvrir ce livre, et travers lui les ides et les mthodes de lapprentissage artificiel.

Tom M. Mitchell

Pittsburgh, Pennsylvania, USALe 29 Mai 2002

Ce d

ocum

ent e

st la

pro

pri

t e

xclu

sive

de O

livie

r BER

NHAR

D (ol

ivier.

simple

life@

gmail

.com)

- 12 m

ai 20

14

14:22

Ce d

ocum

ent e

st la

pro

pri

t e

xclu

sive

de O

livie

r BER

NHAR

D (ol

ivier.

simple

life@

gmail

.com)

- 12 m

ai 20

14

14:22

Table des matie`res

Avant-propos xiiiQuelques applications de lapprentissage artificiel. . . . . . . . . . . . . . . . . . . . . . xivQuelques dfinitions de base . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xivDeux champs industriels de lapprentissage artificiels : la reconnaissance des formes et

la fouille de donnes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xvLes caractristiques de lapprentissage artificiel . . . . . . . . . . . . . . . . . . . . . . xviiTrois exemples dapprentissage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xviiiOrganisation et plan de louvrage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xxiGuide de lecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xxiii

Notations xxvii

I Les fondements de lapprentissage 1

1 De lapprentissage naturel lapprentissage artificiel 31 Lapprentissage artificiel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 Deux exemples : apprendre jouer, apprendre lire . . . . . . . . . . . . . . . . 63 Deux approches : la cyberntique et les sciences cognitives . . . . . . . . . . . . . 104 Les concepts de base de lapprentissage . . . . . . . . . . . . . . . . . . . . . . . . 145 Linduction comme un jeu entre espaces . . . . . . . . . . . . . . . . . . . . . . . 226 Retour sur lorganisation de louvrage . . . . . . . . . . . . . . . . . . . . . . . . 29

2 Premire approche thorique de linduction 371 Poser un problme dapprentissage . . . . . . . . . . . . . . . . . . . . . . . . . . 402 Approches baysiennes et approche directe pour dcider . . . . . . . . . . . . . . 463 Le critre inductif . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 494 Analyse du principe de minimisation du risque empirique . . . . . . . . . . . . . 605 Le lien entre le pass et le futur et le no-free-lunch theorem . . . . . . . . . . . . 736 Notes historiques et bibliographiques . . . . . . . . . . . . . . . . . . . . . . . . . 78

Ce d

ocum

ent e

st la

pro

pri

t e

xclu

sive

de O

livie

r BER

NHAR

D (ol

ivier.

simple

life@

gmail

.com)

- 12 m

ai 20

14

14:22

viii Table des matires

3 Lenvironnement mthodologique de lapprentissage 811 Lespace des donnes dapprentissage . . . . . . . . . . . . . . . . . . . . . . . . . 852 Lespace des hypothses dapprentissage . . . . . . . . . . . . . . . . . . . . . . . 1013 Les protocoles dapprentissage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1124 Lvaluation de lapprentissage . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1135 La comparaison des mthodes dapprentissage . . . . . . . . . . . . . . . . . . . . 1246 Autres problmes pratiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129

II Apprentissage par exploration 135

4 Induction et relation dordre : lespace des versions 1371 Les concepts de base . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1402 La structuration de lespace des hypothses . . . . . . . . . . . . . . . . . . . . . 1443 La construction de lespace des versions . . . . . . . . . . . . . . . . . . . . . . . 1524 La reprsentation des connaissances par un treillis de Galois . . . . . . . . . . . . 156

5 La programmation logique inductive 1611 La programmation logique inductive : le cadre gnral . . . . . . . . . . . . . . . 1652 La logique des prdicats et les programmes logiques :

terminologie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1713 La structuration de lespace des hypothses en logique des prdicats . . . . . . . 1754 Lexploration de lespace des hypothses . . . . . . . . . . . . . . . . . . . . . . . 1825 Deux exemples de systmes de PLI . . . . . . . . . . . . . . . . . . . . . . . . . . 1866 La probabilisation de la PLI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1907 Les domaines dapplication de la PLI . . . . . . . . . . . . . . . . . . . . . . . . . 1918 Les chantiers de la PLI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193

6 Transfert de connaissances et apprentissage par analogie 1991 Lapprentissage en prsence de thorie . . . . . . . . . . . . . . . . . . . . . . . . 2002 Lapprentissage par examen de preuve (EBL) . . . . . . . . . . . . . . . . . . . . 2013 Abstraction et reformulation des connaissances . . . . . . . . . . . . . . . . . . . 2084 Changement de repre, raisonnement par analogie et RPC . . . . . . . . . . . . 2105 Lapprentissage par proportion analogique . . . . . . . . . . . . . . . . . . . . . . 2136 Bilan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 217

7 Linfrence grammaticale 2191 Dfinitions et notations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2252 Les protocoles de linfrence : quelques rsultats thoriques . . . . . . . . . . . . 2333 Lespace de recherche de linfrence rgulire . . . . . . . . . . . . . . . . . . . . 2404 Linfrence rgulire sans chantillon ngatif . . . . . . . . . . . . . . . . . . . . 2415 Linfrence rgulire sous contrle dun chantillon ngatif . . . . . . . . . . . . . 2466 Linfrence de grammaires algbriques . . . . . . . . . . . . . . . . . . . . . . . . 2507 Linfrence dautomates probabilistes . . . . . . . . . . . . . . . . . . . . . . . . . 2578 Quelques approches complmentaires . . . . . . . . . . . . . . . . . . . . . . . . . 260

Ce d

ocum

ent e

st la

pro

pri

t e

xclu

sive

de O

livie

r BER

NHAR

D (ol

ivier.

simple

life@

gmail

.com)

- 12 m

ai 20

14

14:22

Table des matires ix

8 Apprentissage par volution simule 2631 Trois espaces au lieu de deux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2652 Un modle formel simplifi de lvolution . . . . . . . . . . . . . . . . . . . . . . . 2683 Les algorithmes gntiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2694 Les stratgies dvolution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2815 La programmation gntique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2816 La covolution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 291

III Apprentissage par optimisation 297

9 Lapprentissage de modles linaires 2991 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3002 Rgression linaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3013 Sparatrices linaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3064 Modles linaires par morceaux et combinaisons de modles locaux . . . . . . . . 3175 La recherche des facteurs pertinents . . . . . . . . . . . . . . . . . . . . . . . . . 320

10 Lapprentissage de rseaux connexionnistes 3251 Les diffrents lments dun rseau connexionniste . . . . . . . . . . . . . . . . . 3282 Larchitecture multicouche . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3303 Lalgorithme dapprentissage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3354 Quelques rsultats thoriques sur les rseaux connexionnistes . . . . . . . . . . . 3445 Comment choisir larchitecture dun rseau ? . . . . . . . . . . . . . . . . . . . . . 3456 Les rseaux architecture profonde . . . . . . . . . . . . . . . . . . . . . . . . . . 3467 Rseaux et rgime dynamique : le Reservoir Computing . . . . . . . . . . . . . . 348

11 Lapprentissage de rseaux baysiens 3531 Les modles graphiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3552 Les rseaux dinfrence baysiens . . . . . . . . . . . . . . . . . . . . . . . . . . . 3573 Les infrences dans les rseaux baysiens . . . . . . . . . . . . . . . . . . . . . . . 3654 Lapprentissage des rseaux baysiens . . . . . . . . . . . . . . . . . . . . . . . . . 3695 Linfrence de relations causales . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3786 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3797 Quelques logiciels . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 380

12 Lapprentissage de modles de Markov cachs 3831 Les modles de Markov observables . . . . . . . . . . . . . . . . . . . . . . . . . . 3862 Les modles de Markov cachs (Hmm) . . . . . . . . . . . . . . . . . . . . . . . . 3873 Les Hmm comme rgles de classification de squences . . . . . . . . . . . . . . . . 3924 Lvaluation de la probabilit dobservation . . . . . . . . . . . . . . . . . . . . . 3935 Le calcul du chemin optimal : lalgorithme de Viterbi . . . . . . . . . . . . . . . . 3956 Lapprentissage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3987 Approfondissements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4038 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 404

13 Apprentissage par infrence darbres 4071 Les arbres de dcision . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4092 Les arbres de rgression . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 423

Ce d

ocum

ent e

st la

pro

pri

t e

xclu

sive

de O

livie

r BER

NHAR

D (ol

ivier.

simple

life@

gmail

.com)

- 12 m

ai 20

14

14:22

x Table des matires

IV Apprentissage par approximation et interpolation 427

14 Mthodes noyaux 4291 Trois voies vers les mthodes noyau . . . . . . . . . . . . . . . . . . . . . . . . . 4312 Philosophie des mthodes noyaux . . . . . . . . . . . . . . . . . . . . . . . . . . 4413 Les Sparatrices Vastes Marges (SVM) . . . . . . . . . . . . . . . . . . . . . . . 4434 Autres types dinduction avec fonctions noyau . . . . . . . . . . . . . . . . . . . . 4535 Ingnierie des fonctions noyau . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4586 Les mthodes noyaux en pratique . . . . . . . . . . . . . . . . . . . . . . . . . . 4777 Bilan et perspectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 483

15 Lapprentissage baysien et son approximation 4871 Lapprentissage baysien . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4902 Les mthodes paramtriques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4993 Les mthodes non paramtriques . . . . . . . . . . . . . . . . . . . . . . . . . . . 5094 Les mthodes semi-paramtriques . . . . . . . . . . . . . . . . . . . . . . . . . . . 523

16 Lapprentissage de rflexes par renforcement 5311 Description du problme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5342 Si tout est connu : lutilit de la fonction dutilit . . . . . . . . . . . . . . . . . . 5413 Lapprentissage des fonctions dutilit quand lenvironnement est connu . . . . . 5434 Sans modle du monde : la mthode de Monte-Carlo . . . . . . . . . . . . . . . . 5475 La mthode des diffrences temporelles . . . . . . . . . . . . . . . . . . . . . . . . 5486 La gnralisation dans lapprentissage par renforcement . . . . . . . . . . . . . . 5527 Contrle optimal par recherche arborescente et algorithme UCT . . . . . . . . . . 5588 Le cas des environnements partiellement observables . . . . . . . . . . . . . . . . 5619 Exemples dapplication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56210 Bilan et perspectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 565

V Au-del de lapprentissage supervis 569

17 Apprentissage de combinaisons dexperts 5711 Principes des mthodes par combinaison . . . . . . . . . . . . . . . . . . . . . . . 5722 Le vote de plusieurs classificateurs . . . . . . . . . . . . . . . . . . . . . . . . . . 5763 Les codes correcteurs de classes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5774 Le boosting dun algorithme dapprentissage . . . . . . . . . . . . . . . . . . . . . 5825 Le bagging . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5906 Les forts alatoires (random forests) . . . . . . . . . . . . . . . . . . . . . . . . . 5917 Lapprentissage en cascade (cascading) . . . . . . . . . . . . . . . . . . . . . . . . 591

18 La classification non supervise et la fouille de donnes 5931 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5962 Les mthodes de classification fondes sur les distances . . . . . . . . . . . . . . . 5973 Les mthodes de classification par des modles probabilistes . . . . . . . . . . . . 6094 Mthodes spectrales de catgorisation . . . . . . . . . . . . . . . . . . . . . . . . 6105 La classification de donnes symboliques . . . . . . . . . . . . . . . . . . . . . . . 6126 La fouille de donnes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6157 Les analyses en composantes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 625

Ce d

ocum

ent e

st la

pro

pri

t e

xclu

sive

de O

livie

r BER

NHAR

D (ol

ivier.

simple

life@

gmail

.com)

- 12 m

ai 20

14

14:22

Table des matires xi

19 Lapprentissage semi-supervis 6351 Prsentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6362 Les modles gnratifs : apprentissage dans lespace joint X Y . . . . . . . . . . 6403 Lauto-apprentissage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6434 Le co-apprentissage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6445 Lutilisation dhypothses fondamentales sur les donnes . . . . . . . . . . . . . . 6466 Quelques directions pour lapprentissage semi-supervis . . . . . . . . . . . . . . . 6557 Conclusion et petite discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 657

20 Vers de nouvelles tches et de nouvelles questions 6591 Apprentissage actif . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6612 Apprentissages en ligne, incrmental et par transferts . . . . . . . . . . . . . . . . 6693 Apprentissage partir de flux de donnes . . . . . . . . . . . . . . . . . . . . . . 6774 Apprentissage de sorties structures . . . . . . . . . . . . . . . . . . . . . . . . . . 6825 Apprentissage pour le filtrage collaboratif . . . . . . . . . . . . . . . . . . . . . . 686

21 Analyse de linduction : approfondissements et ouvertures 6951 Gnralisation de lanalyse du principe MRE . . . . . . . . . . . . . . . . . . . . 6962 Principes inductifs contrlant lespace des hypothses . . . . . . . . . . . . . . . . 7023 Prise en compte de lalgorithme dapprentissage dans la thorie . . . . . . . . . . 7154 Autres types danalyses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 720

VI Annexes techniques 727

22 Annexes techniques 7291 Exemples de fonctions de perte en induction . . . . . . . . . . . . . . . . . . . . . 7292 Le calcul de lintervalle de confiance de lestimation de la probabilit dune rgle

de classification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7323 Estimation dune densit de probabilit en un point. . . . . . . . . . . . . . . . . 7334 Lestimation des paramtres dune distribution gaussienne. . . . . . . . . . . . . . 7345 Pourquoi et comment la rgle du PPV converge-t-elle ? . . . . . . . . . . . . . . . 7356 Pourquoi la rgle de dcision baysienne est-elle optimale ? . . . . . . . . . . . . . 7367 Apprentissage par estimation-maximisation . . . . . . . . . . . . . . . . . . . . . 7368 Optimisation par descente de gradient . . . . . . . . . . . . . . . . . . . . . . . . 7409 La rtropropagation du gradient de lerreur . . . . . . . . . . . . . . . . . . . . . 74410 Lanalyse de linduction de Vapnik . . . . . . . . . . . . . . . . . . . . . . . . . . 74711 Linduction par compression dinformation . . . . . . . . . . . . . . . . . . . . . . 758

Index 795

Ce d

ocum

ent e

st la

pro

pri

t e

xclu

sive

de O

livie

r BER

NHAR

D (ol

ivier.

simple

life@

gmail

.com)

- 12 m

ai 20

14

14:22

Ce d

ocum

ent e

st la

pro

pri

t e

xclu

sive

de O

livie

r BER

NHAR

D (ol

ivier.

simple

life@

gmail

.com)

- 12 m

ai 20

14

14:22

Avant-propos

Ce livre prsente les thories, les algorithmes et les applications de lapprentissageartificiel. Son ambition est dune part dunifier le cadre mthodologique, et dautrepart de dcrire un ensemble dalgorithmes utiles, de manire cohrente avec ce cadre,et de prsenter ses applications existantes et potentielles. quoi sert lapprentissage artificiel ? La plupart des programmes dintelligence artificielle

possdent aujourdhui un module dapprentissage et tous les programmes de reconnaissance desformes sont fonds sur des algorithmes dapprentissage. Et que font ces programmes ? Ils sontcapables de reconnatre la parole humaine et de linterprter. Ils ralisent une analyse automatiquede photos satellites pour dtecter certaines ressources sur la Terre. Ils assistent les experts pourprendre des dcisions dans des environnements complexes et volutifs, par exemple le marchfinancier ou le diagnostic mdical. Ils fouillent dimmenses bases de donnes htrognes commeles millions de pages Web accessibles tous. Ils analysent les donnes clientle des entreprisespour les aider mieux cibler leurs campagnes de publicit. Ils participent aussi des tournois :le 11 mai 1997, le tenant du titre de champion du monde du jeu dchecs, Gary Kasparov, a tbattu en match par un programme.On sait donc programmer les ordinateurs pour leur faire excuter des tches considres comme

intelligentes, de multiples faons et de manire de plus en plus efficace. Cet ouvrage sintresse un aspect particulier de cette intelligence artificielle : la facult dapprentissage.Lapprentissage artificiel est une discipline dont les outils et les champs dapplications sont

assez disparates. Cependant, les connaissances de base ncessaires sa comprhension sont es-sentiellement une culture gnraliste que lon trouve par exemple dans les ouvrages de mathma-tiques pour linformatique : notions dalgbre linaire, de probabilits, de combinatoire, danalyselmentaire, dalgorithmique, de thorie des langages, de logique. Dans la mesure du possible,ces notions de base sont brivement rappelles selon la ncessit des chapitres de ce livre.

qui sadresse cet ouvrage ?

On peut tirer profit de cet ouvrage en autodidacte, comme le fera par exemple un ingnieurqui cherche connatre ce qui se cache derrire les mots ou acqurir une initiation destechniques quil ignore encore. On pourra aussi sen servir comme dun appui pour complter unenseignement : ce sera le cas pour un tudiant au niveau matrise, DEA ou eole dingnieurs,ou comme dun ouvrage de rfrence pour faire un cours sur le domaine.

Ce d

ocum

ent e

st la

pro

pri

t e

xclu

sive

de O

livie

r BER

NHAR

D (ol

ivier.

simple

life@

gmail

.com)

- 12 m

ai 20

14

14:22

xiv

Quelques applications de lapprentissage artificiel

Voyons maintenant comment rendre un programme plus efficace en le dotant dune possibi-lit dapprentissage. Reprenons pour cela les applications de lintelligence artificielle et de lareconnaissance des formes cites ci-dessus. Les performances dun programme dapplication augmentent au fur et mesure de sonutilisation par la mme personne : cest une exprience quil est aujourdhui facile de meneren pratique en utilisant un logiciel personnel de dicte vocale.

Un programme de dtection des ressources terrestres apprend reconnatre une zone depollution au milieu de la mer, partir dune base de donnes dexemples dimages de zonesconnues comme propres ou comme pollues : cette base de donnes lui sert dexpriencepour dterminer sa dcision sur une zone inconnue.

Un programme de diagnostic sur un ensemble dinformations volutives prises sur un patientdoit avoir t pourvu de connaissances, partir de diagnostics de praticiens et dexperts surdes situations types. Mais il doit aussi avoir t dot dun module de gnralisation, de faon ragir correctement des situations auxquelles il na jamais t confront exactement.

Les moteurs de recherche sur le Web pourraient tre munis dun module dadaptation austyle de navigation de lusager : cest une facult souhaitable pour augmenter lergonomiede leur utilisation. Les programmes ne sont pas encore rellement agrments de cette pro-prit, mais il est clair que cest une condition ncessaire pour franchir certains obstacles decommunication si vidents actuellement.

Lexploitation des fichiers client dune entreprise est souvent ralise par un expert ou un pro-gramme expert qui utilise des rgles explicites pour cibler un segment de clientle susceptibledtre intress par un nouveau produit. Mais ces rgles peuvent tre acquises automatique-ment, par un apprentissage dont le but est de fournir de nouvelles connaissances expertes, la fois efficaces et intelligibles pour lexpert.

Un programme de jeu dchecs possde en gnral une trs bonne efficacit a priori ; maisil est naturel dessayer de le doter dun module o il puisse analyser ses dfaites et sesvictoires, pour amliorer ses performances moyennes dans ses parties futures. Ce moduledapprentissage existe dans un certain nombre de programmes de jeux.

Quelques dfinitions de base

Apprentissage (sous-entendu : artificiel, automatique) (Machine Learning)Cette notion englobe toute mthode permettant de construire un modle de la ralit partir de donnes, soit en amliorant un modle partiel ou moins gnral, soit en crantcompltement le modle. Il existe deux tendances principales en apprentissage, celle issue delintelligence artificielle et qualifie de symbolique, et celle issue des statistiques et qualifiede numrique.

Fouille de donnes (Data Mining) ou Extraction de connaissances partir des donnes(Knowledge Discovery in Data)La fouille de donnes prend en charge le processus complet dextraction de connaissances :stockage dans une base de donnes, slection des donnes tudier, si ncessaire : nettoyage

Ce d

ocum

ent e

st la

pro

pri

t e

xclu

sive

de O

livie

r BER

NHAR

D (ol

ivier.

simple

life@

gmail

.com)

- 12 m

ai 20

14

14:22

Avant-propos xv

des donnes, puis utilisation des apprentissages numriques et symboliques afin de proposerdes modles lutilisateur, et enfin validation des modles proposs. Si ces modles sontinvalids par lutilisateur, le processus complet est rpt.

Prcision vs. gnralisation .Le grand dilemme de lapprentissage. La prcision est dfinie par un cart entre une va-leur mesure ou prdite et une valeur relle. Apprendre avec trop de prcision conduit un sur-apprentissage , comme lapprentissage par cur, pour lequel des dtails insigni-fiants (ou ds au bruit) sont appris. Apprendre avec trop peu de prcision conduit une sur-gnralisation telle que le modle sapplique mme quand lutilisateur ne le dsirepas. Les deux types dapprentissage, numrique et symbolique, ont dfini des mesures degnralisation et cest lutilisateur de fixer le seuil de gnralisation quil juge optimal.

Intelligibilit (devrait tre Comprehensibility mais tend devenir Understandability).Depuis quelques annes, principalement sous la pousse des industriels, les chercheurs sesont mis essayer de contrler aussi lintelligibilit du modle obtenu par la fouille dedonnes. Jusqu prsent les mthodes de mesure de lintelligibilit se rduisent vrifierque les rsultats sont exprims dans le langage de lutilisateur et que la taille des modlesnest pas excessive. Des mthodes spcifiques de visualisation sont aussi utilises.

Classification, classement et rgression. La classification, telle quelle est dfinie en analysede donnes, consiste regrouper des ensembles dexemples non superviss en classes. Cesclasses sont souvent organises en une structure (clustering). Si cette structure est unarbre, alors on parle de taxonomie ou de taxinomie (taxonomy). Sous linfluence du motanglais classification, on a tendance confondre classification et classement. Ce derniermot dsigne le processus de reconnaissance en intension (par leur proprits) de classesdcrites en extension (par les valeurs de leurs descripteurs). Lorsque les valeurs prdiresont des classes en petit nombre, on parle de classification. Il sagit par exemple de prvoirlappartenance dun oiseau observ la classe canard ou oie . La rgression traitedes cas o les valeurs prdire sont numriques, par exemple : nombre dexemplaires decet ouvrage qui seront vendus = 3900.

Deux champs industriels de lapprentissage artificiels : la recon-naissance des formes et la fouille de donnes

En quarante ans et plus dexistence, lapprentissage artificiel a fourni un grand nombre doutilsaux industriels et aux entrepreneurs. Nous les regroupons selon deux grands axes : la reconnais-sance des formes et la fouille de donnes ou pour tre plus prcis, lextraction de connaissancesdes donnes.Le second domaine est le moins bien connu des deux bien quil soit porteur de relles possibilits

conomiques.Quant au premier, rappellons seulement que les mthodes de lapprentissage artificiel sont la

base de la reconnaissance des images (criture manuscrite, signatures, dtection de ressources parsatellite, pilotage automatique, etc.), de la reconnaissance de la parole, du traitement avanc dessignaux bio-mdicaux, etc. Pour mesurer lextraordinaire vitalit des applications et des poten-tialits de la reconnaissance des formes, il suffit par exemple de suivre la parution incessante deslivres dans ce domaine. Pour ne citer que lui, lditeur World Scientific propose une cinquantaine

Ce d

ocum

ent e

st la

pro

pri

t e

xclu

sive

de O

livie

r BER

NHAR

D (ol

ivier.

simple

life@

gmail

.com)

- 12 m

ai 20

14

14:22

xvi

de titres son catalogue sous la rubrique Applications de la reconnaissance des formes et lesrenouvelle raison de prs dune dizaine par an.

Revenons maintenant la fouille de donnes. Les problmes pratiques que peut rsoudre en cedomaine lapprentissage artificiel se posent constamment dans la vie industrielle : distinguer unbon client dun mauvais, et reconnatre un mauvais procd de fabrication et lamliorer sont deuxexemples frappants parmi dautres. On constate pourtant que lancrage de ce type dapplicationdans la vie industrielle ne date que des annes 1990, avec la naissance dune discipline nouvelle,cre sous le nom de fouille de donnes (data mining ) ou ECD : extraction de connaissances partir des donnes (Knowledge Discovery in Databases, KDD). Nous prsentons rapidementle domaine avant den donner ltat de lart industriel dans le dernier paragraphe de cet avant-propos.

LECD est ne de la constatation que les trois approches qui permettaient de construire desmodles, savoir les statistiques exploratoires, lanalyse des donnes et lapprentissage symbo-lique automatique (ASA), souffraient de deux dfauts communs : exiger des donnes prsentessous une forme trs rigide et faire peu de cas de lintelligibilit des rsultats. De plus, chacuneprsentait un dfaut particulier gnant leur emploi : les statistiques exploratoires et lanalyse desdonnes sadressaient des donnes essentiellement numriques et lASA se limitait aux donnessymboliques ou discrtises en intervalles de valeurs.

Depuis, ces domaines ont volu et les critiques leur adresser ont chang, mais tel tait ltatde lart dans les annes 1990. LECD est donc ne dun quadruple effort :

permettre aux utilisateurs de fournir des donnes dans ltat o elles sont : ceci a donnnaissance aux techniques de nettoyage des donnes (ce point sera dvelopp au chapitre 3) ;

utiliser les donnes enregistres sous forme de bases de donnes (en gnral relationnelles) :ceci a provoqu un large courant de recherche au sein de la communaut des BD intressepar la cration de modles ;

fournir aux utilisateurs des outils capables de travailler sur des donnes mixtes, numriqueset symboliques ;

construire des outils produisant une connaissance intelligible aux utilisateurs.

Cest ainsi que lECD a pu trouver la large reconnaissance industrielle dont elle jouit actuellement.Elle a commenc rsoudre les deux problmes industriels principaux de lanalyse des donnes,ceux qui cotent le plus cher : le fait que le client est souvent imprcis dans la dfinition duproblme quil se pose et le fait que les donnes dont il dispose sont souvent de qualit discutable.

Ltude des applications industrielles de lECD montre quil existe une assez forte demandeen outils de cration de modles, autrement dit en apprentissage artificiel. Ceci se traduit parle fait quenviron cent cinquante compagnies se sont spcialises dans ce domaine. Certaines deces entreprises existent depuis plusieurs annes et dautres se sont vendues fort cher. Lensemblerevle bien un secteur en progression raisonnable sur plusieurs annes.

Notre estimation est que le march de lECD est occup par 60 % doutils dapprentissagestatistiques et 40 % doutils dapprentissage symbolique. Ces dernires techniques tant moinsenseignes que les premires dans les universits, on constate un hiatus entre lenseignement etlindustrie. En tous cas, le prsent livre cherche aller dans le sens dun meilleur enseignementdes mthodes de lapprentissage artificiel, symbolique comme statistique .s s

Ce d

ocum

ent e

st la

pro

pri

t e

xclu

sive

de O

livie

r BER

NHAR

D (ol

ivier.

simple

life@

gmail

.com)

- 12 m

ai 20

14

14:22

Avant-propos xvii

Les caractristiques de lapprentissage artificiel

Certaines des facults que lon peut lier naturellement lapprentissage ont t cites dansles exemples ci-dessus : entranement, reconnaissance, gnralisation, adaptation, amlioration,intelligibilit.Rappellons la dfinition classique de lapprentissage en sciences cognitives : capacit am-

liorer les performances au fur et mesure de lexercice dune activit . Cette dfinition sappliqueen particulier au comportement dun joueur dchecs au fil des parties, o lassimilation de lexp-rience et la puissance de raisonnement se combinent dans sa progression. Elle est aussi pertinentepour des tches perceptives : on shabitue un accent, une criture. On accumule des bonnes etdes mauvaises expriences. partir delles, on sait, consciemment ou non, en abstraire ou fairevoluer des rgles pour mieux effectuer la tche.Nous avons mentionn une autre facette de lapprentissage, souvent entremle la prcdente :

la facult gnraliser rationnellement. Si une exprience accumule sur un certain nombredexemples a permis de tirer des rgles de comportement, ces rgles doivent sappliquer aussi des situations non encore rencontres. Prenons quelquun qui apprend conduire sur une berlinede petite puissance. Ds quil a mrit le permis, la loi lautorise conduire une camionnetteutilitaire ou une voiture de sport. Cest que les rgles quil a apprises et les rflexes quil a acquissappliquent aussi (plus ou moins directement) ces vhicules.Quen est-il des machines ? Ds les dbuts de lintelligence artificielle, cest--dire en vrit

ds lapparition des ordinateurs, les chercheurs et les ingnieurs se sont poss le problme delapprentissage 1. Lapprentissage artificiel dans sa situation actuelle est donc le produit dunehistoire de cinquante ans de recherches et de ralisations. Comme on la vu, un grand nombre detches dintelligence artificielle et de reconnaissance des formes sappuient ou sont fondes surdes modules dapprentissage.On verra dans cet ouvrage comment des programmes peuvent mettre en uvre un apprentis-

sage par amlioration du comportement, en gnral grce des techniques doptimisation. Onverra aussi quil est possible dcrire des programmes qui ralisent un apprentissage par gn-ralisation : quand on leur donne suffisamment dexemples et le type du concept apprendre,ils choisissent un concept qui nest pas seulement valide sur les exemples quils ont vus, maisqui sera galement valable pour dautres. Cest ainsi quun programme de reconnaissance de laparole ne peut pas entendre tous les sons avant dlaborer une rgle de dcision. Il est critpour extraire une mthode de classification de ceux quon lui a prsents et traiter ensuite dumieux possible tous les sons quil aura dcoder.En ralit, dun point de vue informatique, la problmatique nest pas fondamentalement

diffrente dans les deux cas. Il sagit dans le premier de faire voluer des rgles de comportementau fil des exemples et dans le second dextraire des rgles partir dun ensemble dexemplesdonn a priori. De mme que dans lapprentissage naturel, un panachage de ces deux modes defonctionnement est facile concevoir dans lapprentissage artificiel.Il y a une autre facette de lapprentissage que lintelligence artificielle explore. Quand un

expert extrait des connaissances dun ensemble de donnes, il apprend une certaine faon de lesrsumer. Mais le rsultat de cet apprentissage ne sera opratoire que si la connaissance extraiteest intelligible, transmissible de lexpert aux utilisateurs, interprtable en clair . Il en est de

1 Alan Turing, dans son article Computing Machine and Intelligence, de la revue Mind en Octobre1950 (Vol LIX, No 236) avait intitul un paragraphe Learning Machines. On peut consulter unfac-simil du manuscrit sur le site http ://data.archives.ecs.soton.ac.uk/turing/ et le texte :http ://www.abelard.org/turpap/turpap.htm

Ce d

ocum

ent e

st la

pro

pri

t e

xclu

sive

de O

livie

r BER

NHAR

D (ol

ivier.

simple

life@

gmail

.com)

- 12 m

ai 20

14

14:22

xviii

mme pour un agent artificiel : certaines tches dapprentissage ne se mesurent pas seulementpar leur qualit de prdiction, mais aussi par la manire dont les rsultats sont expliqus. Cetaspect est reli oprationnellement lintelligence artificielle symbolique, aux systmes expertsen particulier : mieux vaut souvent un petit nombre de rgles comprhensibles quun fouillis dergles sophistiques, mme avec une performance objective suprieure.Avant de dcrire plus en dtail les motivations et lorganisation de cet ouvrage, prcisons

travers trois exemples comment sorganise lapprentissage dans des situations concrtes. Celanous permettra de donner une typologie des mthodes et de prsenter le plan de cet ouvrage.

Trois exemples dapprentissage

Un exemple ornithologique

Imaginons un tang sur lequel nagent des oies et des cygnes (nous admettons quil ny a pasdautres oiseaux dans cette rgion). Le brouillard est tomb, quand arrivent deux avimateursdont lun est expert et lautre dbutant. Ils naperoivent en arrivant quune partie des animaux,de manire peu distincte. Pour lexpert, lidentification est cependant facile (il nest pas expertpour rien). Quant au dbutant, il doit se contenter de mesurer ce qui lui parat caractristique :le niveau de gris du plumage et la taille de la bte. Pour reprsenter le problme, il va doncprendre ces deux mesures sur chaque animal quil voit et tablir un graphique : il se place ainsidans un certain espace de reprsentation (figure -1.1, gauche).

Fig. -1.1: Le premier graphique de lavimateur dbutant reprsente les oiseaux observs placsdans son espace de reprsentation. Le second graphique reprsente les mmes oiseaux,mais il est tiquet par lexpert. La lettre O signifie que loiseau est une oie, C quilest un cygne.

Maintenant, comment lancer une phase dapprentissage ? Il faut que le dbutant se place ensituation dapprenant vis--vis de lexpert, en lui demandant quelle est la dcision correcte pourchaque oiseau. Une fois que lexpert a agi comme un professeur en donnant toutes les rponses,notre apprenant possde un graphique enrichi (figure -1.1, droite) qui va lui permettre dedmarrer lapprentissage proprement dit.Le problme dapprentissage est maintenant bien pos. Il peut snoncer ainsi : comment

trouver une rgle qui dcide, dans lespace de reprsentation choisi, avec le moins derreurspossibles, quel oiseau est une oie et quel oiseau est un cygne ? La rgle trouve doit possder

Ce d

ocum

ent e

st la

pro

pri

t e

xclu

sive

de O

livie

r BER

NHAR

D (ol

ivier.

simple

life@

gmail

.com)

- 12 m

ai 20

14

14:22

Avant-propos xix

de bonnes proprits de gnralisation, cest--dire fonctionner au mieux non seulement sur cesexemples expertiss, mais par la suite sur des oiseaux non encore observs.Que sera une telle rgle ? Lapprenant peut imaginer de tracer dans le plan de reprsentation

une ligne (courbe ou droite) qui spare les cygnes des oies. partir des exemples connus, il auraalors induit une loi gnrale : tout oiseau observ dont la reprsentation est situe sous cetteligne sera un cygne. Ce sera une oie dans le cas contraire. Mais on peut tracer une infinit detelles lignes. Cest ici que lapprenant doit prciser le type des connaissances acqurir, le typedu concept apprendre, en lespce quelle est la forme gnrale de la ligne.Si lapprenant impose que la ligne soit droite, le but de lapprentissage sera de trouver la

meilleure ligne droite, en optimisant un critre dont il est matre. On remarque dailleurs quau-cune droite ne spare parfaitement les exemples, mais cest le prix payer pour un concept aussisimple. La figure -1.2 de gauche reprsente la rgle de dcision que notre dbutant en ornithologiepeut raisonnablement produire. Sil nimpose pas de restriction aussi stricte sur la forme de laligne, il pourra obtenir une dcision comme celle de la figure -1.2 droite.

Fig. -1.2: Une rgle de dcision simple et une rgle de dcision complexe pour sparer les oiesdes cygnes.

Quand le brouillard se lve, dautres oiseaux deviennent visibles. Lapprenant peut alors vrifierla qualit de la rgle quil a apprise, toujours avec laide de son professeur. Dans lexemple donnsur la figure -1.3, il est facile de constater que la droite quil a choisie mne une erreur environune fois sur cinq2. Pas trop mal, pour un dbutant ! Il est assez facile de transposer cet exemple lcriture dun programme dapprentissage. Remarquons bien quun tel programme napprend pastout court mais apprend quelque chose, en loccurence une rgle de dcision sous la forme dunequation de droite dans le plan. Cet exemple est caractristique de ce que font les programmesde reconnaissance des formes. Ce type dapprentissage par gnralisation est dune immenseimportance mthodologique et pratique.

Un exemple linguistique

Abordons un autre exemple. Supposons que nous disposions dun ensemble de phrases dunecertaine langue. Est-il possible dcrire un programme pour en apprendre automatiquement lagrammaire ? Pour une langue naturelle, le problme est certainement complexe, ne serait-ce queparce quun trs grand nombre dexemples est ncessaire. Mais on peut essayer de le rsoudredans le cas dun langage artificiel comme ceux qui servent interroger les bases de donnes ou2 La ligne courbe donnerait une erreur encore plus grande ; nous reviendrons sur ce phnomne aux chapitres 2et 3.

Ce d

ocum

ent e

st la

pro

pri

t e

xclu

sive

de O

livie

r BER

NHAR

D (ol

ivier.

simple

life@

gmail

.com)

- 12 m

ai 20

14

14:22

xx

Fig. -1.3: Le test de la rgle simple sur dautres oiseaux.

pour un sous-ensemble bien dlimit de langage naturel. Le langage des changes entre un clientet un employ dagence de voyage en est un exemple.Dans de tels cas, il est effectivement possible dapprendre une grammaire. Il faut cependant

imposer au programme des restrictions sur le type de la syntaxe que lon cherche. Lespace dereprsentation est ici lensemble de toutes les squences de mots possibles, dont on ne connatque certaines, linguistiquement correctes. Mais comment dfinir la grammaire apprendre ? Onverra au chapitre 7 que si on oblige cette grammaire tre un automate fini, on peut dmontrerque tous les automates finis qui sont compatibles avec les exemples forment un ensemble limit etstructur par une relation dordre. Le programme dapprentissage a alors pour tche de chercherle meilleur automate dans cet ensemble structur, encore une fois au sens dun critre luiprciser. Remarquons encore que le programme napprend pas tout court, mais apprend quelquechose : en lespce, une grammaire reprsente par un automate fini.

Un exemple dextraction de connaissances

Une compagnie dassurances cherche lancer un nouveau produit, destin couvrir le risquede vol dobjets de valeur domicile. Elle veut faire une campagne de publicit cible auprsdune partie de ses clients. Cette compagnie ne dispose que de peu de produits du mme type etpar consquent sa base de donnes ne comporte quune petite proportion denregistrements oun client est dj associ une assurance contre le vol domicile. De plus, comme ces clientspossdent dj un produit analogue, ce nest pas vers eux quil faut principalement cibler lacampagne. Mais comment savoir si un client qui na pas encore dassurance de ce type seraintress par le nouveau produit ?Une solution est de chercher un profil commun aux clients qui se sont dj montrs intresss

par un produit de ce type pour cibler parmi tous les clients ceux qui ont un profil analogue. Quesera un tel profil ? Dans la base de donnes, chaque client est dcrit par un certain nombre dechamps, que lon peut supposer binaires. Par exemples : ge infrieur trente ans , possdeune maison , a un ou plusieurs enfants , vit dans une zone risque de vol , etc. Certainschamps peuvent tre non remplis : les clients qui ont seulement une assurance automobile nontpas t interrogs la constitution de leur dossier sur lexistence dun systme dalarme dansleur appartement.Une faon de constituer un profil consiste dcouvrir des associations dans les donnes, cest-

-dire des implications logiques approximatives. Disons par exemple que la plupart des clientsqui possdent dj une assurance contre le vol dobjets de valeur domicile sont plutt gs etnont en gnral quune voiture, mais haut de gamme. Il semble raisonnable de dmarcher parmi

Ce d

ocum

ent e

st la

pro

pri

t e

xclu

sive

de O

livie

r BER

NHAR

D (ol

ivier.

simple

life@

gmail

.com)

- 12 m

ai 20

14

14:22

Avant-propos xxi

tous les clients ceux qui rpondent au mme profil. Lhypothse est donc que possder une seulevoiture (mais de luxe) et tre dge mr est un profil qui implique sans doute la possession domicile dobjets de valeur.Ce type dapprentissage relve de lextraction de connaissances et de lapprentissage non super-

vis. Ce dernier terme signifie que le programme dapprentissage se dbrouille sans professeur :lexpertise est prsente dans les donnes, mais de manire implicite, cest au programme de ladcouvrir et de lutiliser. La combinatoire sous-jacente ce type dapprentissage est videmmenttrs importante.

Organisation et plan de louvrage

Lorganisation de cet ouvrage reflte en partie des caractristiques importantes des exemplesprcdents. Nous disons que, pour le premier, lespace de recherche est peu structur. Pourquoicela ? Parce quon ne peut pas dire si telle droite est meilleure que telle autre sans les testertoutes les deux explicitement sur les donnes. Il sagit de ce quon appelle en gnral un problmedoptimisation. En revanche, dans le second exemple, nous avons mentionn une relation dordreentre deux solutions, intimement lie leur qualit relative. Dans ce cas, une exploration partiellede lensemble des solutions est possible ; elle sera guide la fois par sa structure algbrique etpar les donnes, exemples et contre-exemples, alors que seules les donnes pouvaient conduire leprogramme dans le premier cas. Pour le troisime exemple, il ny a mme pas de guidage danslespace de recherche par des exemples et des contre-exemples.Ces remarques sont cruciales pour la conception des algorithmes. Cest la raison pour laquelle

nous avons choisi dorganiser le prsent ouvrage selon le critre suivant : nous traitons les m-thodes dapprentissage en commenant par celles pour lesquelles lespace de reprsentation desconcepts apprendre est fortement structur, puis celles pour lesquelles cette hypothse doittre affaiblie et enfin celles pour lesquelles linformation a priori sur la nature des concepts apprendre est trs faible ou nulle.

Partie 1 : Les fondements de lapprentissage

Une partie de fondements mthodologiques est dabord ncessaire. Nous y faisons une prsen-tation gnrale de la problmatique de lapprentissage et nous donnons les dfinitions de base(Chapitre 1 : De lapprentissage naturel lapprentissage artificiel). Le chapitre suivantpropose une introduction aux thories de lapprentissage par gnralisation (Chapitre 2 : Pre-mire approche thorique de linduction). Un approfondissement de ce thme sera menau chapitre 21. Le troisime chapitre traite de la reprsentation des donnes et des connaissanceset des types dalgorithmes qui sont mis en jeu par la suite (Chapitre 3 : Lenvironnementmthodologique de lapprentissage).

Partie 2 : Apprentissage par exploration

Nous analysons dans la deuxime partie les mthodes dapprentissage quand les reprsentationsdes concepts forment des ensembles fortement structurs. Nous lavons appele lapprentissagepar exploration. On y trouve dabord une mthode trs gnrale (Chapitre 4 : Inductionet relation dordre : lespace des versions), puis un chapitre sur lapprentissage dans lalogique des prdicats (Chapitre 5 : La programmation logique inductive). Le chapitresuivant complte ce point de vue en montrant comment modifier des concepts dans des espaces

Ce d

ocum

ent e

st la

pro

pri

t e

xclu

sive

de O

livie

r BER

NHAR

D (ol

ivier.

simple

life@

gmail

.com)

- 12 m

ai 20

14

14:22

xxii

structurs ; il aborde aussi lapprentissage par analogie (Chapitre 6 : Transfert de connais-sances et apprentissage par analogie). Le septime chapitre (Chapitre 7 : Linfrencegrammaticale) traite de lapprentissage des automates et des grammaires. Enfin les mthodesdapprentissage par volution simule, fondes sur lexploration par algorithmes gntiques, sontexposes (Chapitre 8 : Apprentissage par volution simule).

Partie 3 : Apprentissage par optimisation et interpolation

Dans la troisime partie, les connaissances sur la structure des espaces sont plus faibles. En fait,il nexiste plus quune mesure de qualit des hypothses induites par le critre inductif et une dis-tance dans lespace des hypothse permettant de mettre en uvre des techniques doptimisationpar gradient. Il sagit de lapprentissage par optimisation. On y trouve le problme de lappren-tissage de droites, soit pour la rgression, soit pour la classification, mentionn ci-dessus, et leurgnralisation des hyperplans (Chapitre 9 : Lapprentissage de modles linaires). Uneextension dsormais classique mne aux rseaux connexionnistes multicouche (Chapitre 10 :Lapprentissage de rseaux connexionnistes). Le fonctionnement et lapprentissage des r-seaux de probabilits conditionnelles est ensuite abord (Chapitre 11 : Lapprentissage derseaux baysiens). Le chapitre suivant traite comme le chapitre 7 de lapprentissage de cer-taines machines produire des squences, mais sous un aspect probabiliste (Chapitre 12 :Lapprentissage de modles de Markov cachs).Pour finir cette partie, nous abordons dans le chapitre suivant lapprentissage des arbres de

dcision (Chapitre 13 : Apprentissage par infrence darbres).

Partie 4 : Apprentissage par approximation

La partie suivante, intitule lapprentissage par approximation et interpolation, traite des m-thodes les moins informes, celles o lespace des concepts cherchs possde le moins de proprits.Elle commence par un chapitre qui expose un ensemble de mthodes rcentes qui permettent de

prendre des dcisions non linaires tout en sappuyant sur des mthodes linaires (Chapitre 14 :Mthodes noyaux).Nous dcrivons ensuite les techniques dapprentissage de rgles de classification par des m-

thodes statistiques qui cherchent approcher la rgle de dcision baysienne. Ce chapitre in-clut aussi certains aspects de lapprentissage par analogie, en particulier la mthodes des plusproches voisins (Chapitre 15 : Lapprentissage baysien et son approximation ). Le cha-pitre suivant sintresse un apprentissage numrique de type punition ou rcompense ,typiquement applicable lapprentissage de son comportement par un robot (Chapitre 16 :Lapprentissage de rflexes par renforcement).

Partie 5 : Au-del de lapprentissage supervis.

La partie suivante, intitule au-del de lapprentissage supervis a pour ambition de regrouperun ensemble de techniques autour ou au-dessus de lapprentissage supervis. Le Chapitre 17 :Apprentissage de combinaison dexperts sintresse la combinaison de plusieurs mthodesde classification pour quelles sentraident sur un problme donn. La mthode du boosting y esten particulier traite. Dans le chapitre suivant, on sintresse aux donnes non tiquetes par unexpert : il sagit de les organiser et dy dcouvrir des rgularits et des associations ( Chapitre18 : La classification non supervise et la fouille de donnes). Ensuite, nous dvelopponsle cas o seulement une partie des exemples est supervise : il sagit de tirer parti des exemplesnon superviss pour aider la classification (Chapitre 19 : Lapprentissage semi-supervis).

Ce d

ocum

ent e

st la

pro

pri

t e

xclu

sive

de O

livie

r BER

NHAR

D (ol

ivier.

simple

life@

gmail

.com)

- 12 m

ai 20

14

14:22

Avant-propos xxiii

Le chapitre suivant dresse un panorama non exhaustif mais vocateur de nouvelles directionsde recherche visant dpasser les ides classiques de lapprentissage artificiel (Chapitre 20 :Vers de nouvelles tches et de nouvelles questions). Pour terminer, le chapitre suivantrevient sur les aspects thriques de lapprentissage abords au Chapitre 2 et explore la notiondinduction sous ses aspects mathmatiques, avant dvoquer dautres cadres possibles dappren-tissage (Chapitre 21 : Analyse de linduction : approfondissements et ouvertures).Ce livre se termine par des annexes, qui dtaillent des points techniques ; celles qui traitent de

lalgorithme estimation-maximisation et de loptimisation par gradient sont sans douteles plus rfrences dans les chapitres prcdents.Finalement, une bibliographie fournit les ouvrages fondamentaux et les articles plus pointus

cits dans le texte.

Guide de lecture

Aprs plus de quarante ans de recherches et de ralisations en apprentissage artificiel, il estdifficile pour un non initi de savoir comment aborder ce domaine et comment sy orienter. Noscollaborations avec des utilisateurs des techniques dapprentissage et avec des chercheurs dautresdisciplines, comme notre activit denseignement et dencadrement avec nos tudiants nous ontamplement montr lintrt dun ouvrage dintroduction cohrent, articul autour de grandeslignes directrices.Il existe dj des livres denseignement et de recherche sur pratiquement chaque sujet abord

dans les chapitres de ce livre et nous ne manquons pas dy faire rfrence. Mais si la sommedes connaissances qui sy trouvent est au total bien suprieure celle contenue dans notre livre,leur lecture conduit des contradictions dans les notations, des approfondissements thoriquesde niveau trs variable, des analyses diffrentes du mme problme et des prsentationsredondantes voire contradictoires des mmes sujets.Il nous a donc paru que la discipline de lapprentissage artificiel pouvait tre prsente de

manire unifie, dans un but dabord didactique. Ce souci commande le fond comme la forme decet ouvrage.Compte tenu de la varit technique des sujets abords et de lintrt personnel de chaque

lecteur (autodidacte, enseignant ou tudiant), des parcours de lecture diffrents peuvent tresuivis.Nous proposons en particulier les itinraires suivants, mais ce nest pas exclusif :1. Pour une vue densemble sur lapprentissage artificiel, un rapide aperu des mthodes et

un point de vue sur leurs applications : chapitres 1, 2 (paragraphes 2.1 et 2.2), 3 et 4.2. Pour un point de vue approfondi sur les principes mthodologiques, en particulier

statistiques de lapprentissage : chapitres 1, 2, 3, 8, 9, 13, 14, 15, 17, 18, 19, 20 et 21.3. Pour comprendre lapprentissage de phnomnes essentiellement numriques et pour les

applications la reconnaissance des formes : chapitres 1, 2 (paragraphes 2.1 et 2.2), 3,9, 10, 12, 13, 15, 16, 17 et 18.

4. Pour acqurir un point de vue sur lapprentissage dans les systmes experts et le trai-tement des donnes symboliques : chapitres 1, 3, 4, 5, 6, 7, 8, 11, 15 et ventuellement16.

5. Pour qui veut raliser lapprentissage de concepts partir de donnes squentielles(signaux, textes, etc.) : chapitres 1, 3, 5, 7 et 12.

Ce d

ocum

ent e

st la

pro

pri

t e

xclu

sive

de O

livie

r BER

NHAR

D (ol

ivier.

simple

life@

gmail

.com)

- 12 m

ai 20

14

14:22

xxiv

6. Pour qui sintresse plus la robotique, lapprentissage de comportement : chapitres 1,3, 7, 11, 12, 15 et 16.

7. Pour qui sintresse la fouille de donnes, lextraction de connaissances : chapitres9, 10, 17, 11, 15 et 18. 9, 10, 11, 13, 15 et 18.

Ce d

ocum

ent e

st la

pro

pri

t e

xclu

sive

de O

livie

r BER

NHAR

D (ol

ivier.

simple

life@

gmail

.com)

- 12 m

ai 20

14

14:22

Glossaire francais-anglais 3

Apprenant LearnerApprentissage actif Active learningApprentissage en ligne On-line learningApprentissage hors ligne Batch learningApprentissage par examen de preuve (EBL) Explanation-based learningApprentissage quand F 6= H Agnostic learningApprentissage de tri Learning to rankAstuce de reprsentation unique Single representation trickAttribut FeatureBiais de reprsentation Reprsentation biasCatgorisation ClusteringClasses dsquilibres Imbalanced data setsConnaissance a priori Domain theory (sometimes hints)chantillon dapprentissage Learning setchantillon de test Test setchantillon de validation Validation setExemple critique Support vector or near-missFonction de cot Loss functionFonction cible Target functionFonction de performance Fitness functionHypothse correcte (par rapport des donnes) Consistent hypothesisMthodes noyaux Kernel methodsOptimisation de performance Speed-up learningPerceptron multi-couches (PMC) Multi-layer perceptron (MLP)Point aberrant OutlierPrincipe de longueur minimale de description Minimum description length principleProgrammation logique inductive (PLI) Inductive logic programing (ILP)Raisonnement partir de cas Case-based reasoningReconnaissance des formes Pattern recognitionRseaux baysiens Bayes nets or graphical modelsRseaux connexionnistes Neural networksRisque empirique Empirical riskRisque rel Expected risk or true riskSparateurs vaste marge Support vector machinesSuradaptation ou surapprentissage Over-fittingSystme de classification Classifier

3 Les termes importants sont traduits en anglais au fil du texte.

Ce d

ocum

ent e

st la

pro

pri

t e

xclu

sive

de O

livie

r BER

NHAR

D (ol

ivier.

simple

life@

gmail

.com)

- 12 m

ai 20

14

14:22

Ce d

ocum

ent e

st la

pro

pri

t e

xclu

sive

de O

livie

r BER

NHAR

D (ol

ivier.

simple

life@

gmail

.com)

- 12 m

ai 20

14

14:22

Notations

Notations gnrales

# . . . Nombre de . . .

P Une probabilitp Une densit de probabilitsE[x] Lesprance de la variable x

N Lensemble des entiers naturelsIRd Lespace euclidien de dimension dBd = {0, 1}d Lespace boolen de dimension dO() Lordre de grandeur maximal de complexit dun algorithme

x =

x1...xd

Un vecteurx> = (x1, . . . , xd) Un vecteur transposx = (x1, . . . , xd)> Un vecteurxy = x>y Le produit scalaire des vecteurs x et y|| x || La norme du vecteur x

M1 La matrice inverse dune matrice carre MM> La matrice transpose dune matrice MM+ La matrice pseudo-inverse dune matrice M .

Par dfinition, M+ =M>(MM>)1

(x,y) La distance euclidienne entre deux vecteurs x et y de IRd

xf(x, y) La drive partielle par rapport x

de la fonction f des deux variables x et y

AJ(A,B) Le vecteur driv par rapport au vecteur Ade la fonctionnelle J des deux vecteurs A et B

Ce d

ocum

ent e

st la

pro

pri

t e

xclu

sive

de O

livie

r BER

NHAR

D (ol

ivier.

simple

life@

gmail

.com)

- 12 m

ai 20

14

14:22

xxviii

Les lments en jeu dans lapprentissage

X Lespace de reprsentation des objets (des formes)Y Lespace de sortieF Espace de redescription ou Feature space

S Lchantillon dapprentissage (un ensemble ou une suite dexemples)S+ Les exemples positifsS Les exemples ngatifsA Lchantillon dapprentissage quand on divise S en A, T et VT Lchantillon de testV Lchantillon de validationm La taille dun chantillon dapprentissage (le nombre dexemples)zi = (xi, ui) Un exemple (lment dun chantillon dapprentissage)xi La description dun objet dans un espace de reprsentationxij La valeur de la coordonne j de la description de lobjet xi dans IRd

Les principes de lapprentissage inductif

ui Y La supervision, ou sortie dsire, dun exemplef : X Y La fonction cible (celle que lon cherche apprendre)

H Lespace des hypothses dapprentissageh H Une hypothse produite par un apprenant (un algorithme dapprentissage)y = h(x) Y La prdiction faite par lhypothse h sur la description x dun exemple`(f, h) La perte (ou distance) entre la fonction cible et une hypothseRRel(h) Le risque rel associ lhypothse hREmp(h) Le risque empirique associ lhypothse hR? Le risque (optimal) de la rgle de dcision de Bayes

h? Lhypothse de H qui minimise le risque relh?S Lhypothse de H qui minimise le risque empirique sur Sh?S Lhypothse trouve par lalgorithme dapprentissage ayant S en entre

et cherchant h?S dans H

Lapprentissage dune rgle de classification

C Lensemble des classesC Le nombre de classesi Une classe de C

La logique

a b a ET b, quand a et b sont des valeurs binairesa b a OU ba NON aa b a implique b

Ce d

ocum

ent e

st la

pro

pri

t e

xclu

sive

de O

livie

r BER

NHAR

D (ol

ivier.

simple

life@

gmail

.com)

- 12 m

ai 20

14

14:22

Premire partie

Les fondements de lapprentissage

Ce d

ocum

ent e

st la

pro

pri

t e

xclu

sive

de O

livie

r BER

NHAR

D (ol

ivier.

simple

life@

gmail

.com)

- 12 m

ai 20

14

14:22

Ce d

ocum

ent e

st la

pro

pri

t e

xclu

sive

de O

livie

r BER

NHAR

D (ol

ivier.

simple

life@

gmail

.com)

- 12 m

ai 20

14

14:22

Chapitre 1

De lapprentissage naturel a`lapprentissage artificiel

Sommaire1 Lapprentissage artificiel . . . . . . . . . . . . . . . . . . . . . . . . . . 42 Deux exemples : apprendre jouer, apprendre lire . . . . . . . . . 6

2.1 Apprendre jouer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62.2 Apprendre reconnatre des caractres manuscrits . . . . . . . . . . . . 7

3 Deux approches : la cyberntique et les sciences cognitives . . . . . 103.1 La cyberntique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113.2 Le pari du cognitivisme . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

4 Les concepts de base de lapprentissage . . . . . . . . . . . . . . . . . 144.1 Un scnario de base pour linduction . . . . . . . . . . . . . . . . . . . . 144.2 Quelques notions cls . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

4.2.1 Le critre de succs . . . . . . . . . . . . . . . . . . . . . . . . 144.2.2 Notion de protocole dapprentissage . . . . . . . . . . . . . . . 154.2.3 Notion de tche dapprentissage . . . . . . . . . . . . . . . . . 16

4.3 Linduction considre comme estimation de fonction . . . . . . . . . . . 195 Linduction comme un jeu entre espaces . . . . . . . . . . . . . . . . 22

5.1 Lapprentissage est impossible. . . . . . . . . . . . . . . . . . . . . . . . . 235.2 . . . sans limiter lespace des hypothses . . . . . . . . . . . . . . . . . . . 255.3 Lexploration de lespace des hypothses . . . . . . . . . . . . . . . . . . 27

6 Retour sur lorganisation de louvrage . . . . . . . . . . . . . . . . . . 29

Ce d

ocum

ent e

st la

pro

pri

t e

xclu

sive

de O

livie

r BER

NHAR

D (ol

ivier.

simple

life@

gmail

.com)

- 12 m

ai 20

14

14:22

4 PARTIE 1 : Les fondements de lapprentissage

1. Lapprentissage artificiel

Mme les machines ont besoin dapprendre.Depuis plus dun demi-sicle, les chercheurs en intelligence artificielle travaillent programmer

des machines capables deffectuer des tches qui requirent lexercice de lintelligence. Nous cite-rons laide la dcision, par exemple laide au diagnostic mdical ; la reconnaissance de formes,par exemple la reconnaissance de la parole ou la vision artificielle ; le contrle de processus, parexemple la conduite de procds industriels ; la prdiction, par exemple la prdiction de consom-mation lectrique ou la prdiction de cours boursiers ; la conduite de robots, y compris dquipesde robots comme dans la RoboCup1 ; lexploration de grandes bases de donnes (on dit aussi lafouille de donnes), tant il est vrai que si nous croulons sous les informations, il nous manquesouvent la connaissance. Chacune de ces tches et bien dautres ont stimul linventivit deschercheurs et donn lieu de nombreuses ralisations impressionnantes. Cependant, program-mer des machines capables de sadapter toutes les situations et ventuellement dvoluer enfonction de nouvelles contraintes est difficile. Lenjeu est de contourner cette difficult en dotantla machine de capacits dapprentissage lui permettant de tirer parti de son exprience. Cestpourquoi, paralllement aux recherches sur le raisonnement automatique, se sont dveloppesdes recherches sur lapprentissage par les machines. Avant daborder ce type dap