Apprentissage artificiel: Concepts et algorithmes

g

a

s

s

i

t

n

e

r

p

p

A

t

e

l

c

i

M

.

L

s

l

o

j

u

n

r

o

C

.

A

Antoine Cornu jols - Laurent Miclet

Avec la participation dYves Kodratoff

Apprentissage

artificiel

Concepts et algorithmes

Pr face de Tom Mitchell

r zo neur. 4/07/02 11:35 Page 1

Apprentissage

artificiel

Antoine Cornu jols est

ma tre de conf rences

lInstitut dinformatique

dentreprise et chercheur au

LRI de Paris XI Orsay. Il

enseigne lapprentissage

artificiel dans plusieurs

grandes coles et en DEA. Ses

recherches portent

notamment sur lutilisation

de lapprentissage pour

lanalyse de donn es en

m decine, en g nomique et

en vision artificielle.

Laurent Miclet est

professeur lENSSAT de

Lannion. Il est responsable

du projet CORDIAL de lINRIA

et enseigne lapprentissage

artificiel et la

reconnaissance des formes

dans plusieurs grandes

coles et en DEA. Ses

recherches portent en

particulier sur

lapprentissage pour le

dialogue homme-machine et

les technologies vocales.

Yves Kodratoff est directeur

de recherches au CNRS et

dirige au LRI l quipe

Inf rence et Apprentissage.

Il sint resse toutes les

techniques de raisonnement

inductif, et en particulier

leur application au data

mining.

Cet ouvrage est publi

avec le concours de l cole

Nationale Sup rieure des

Sciences Appliqu es et de

Technologie (Lannion).

Les programmes dintelligence artificielle sont aujourdhui

capables de reconna tre des commandes vocales, danalyser

automatiquement des photos satellites, dassister des experts

pour prendre des d cisions dans des environnements complexes

et volutifs (analyse de march s financiers, diagnostics m di-

caux&), de fouiller dimmenses bases de donn es h t rog nes,

telles les innombrables pages du Web&

Pour r aliser ces t ches, ils sont dot s de modules dapprentis-

sage leur permettant dadapter leur comportement des situa-

tions jamais rencontr es, ou dextraire des lois partir de bases

de donn es dexemples.

Ce livre pr sente les concepts qui sous-tendent lapprentissage

artificiel, les algorithmes qui en d coulent et certaines de leurs

applications. Son objectif est de d crire un ensemble dalgo-

rithmes utiles en tentant d tablir un cadre th orique unique

pour lensemble des techniques regroup es sous ce terme

dapprentissage artificiel .

qui sadresse ce livre ?

" Aux d cideurs et aux ing nieurs qui souhaitent comprendre

lapprentissage automatique et en acqu rir des connaissances

solides ;

" Aux tudiants de niveau ma trise, DEA ou cole ding nieurs

qui souhaitent un ouvrage de r f rence en intelligence

artificielle et en reconnaissance des formes.

Sommaire

I. Les fondements de lapprentissage " Premi re approche th orique de

linduction " Environnement m thodologique " II. Apprentissage par exploration "

Induction et relation dordre " Programmation logique inductive " Inf rence grammaticale "

Apprentissage par volution " III. Apprentissage par optimisation " Surfaces

s paratrices lin aires " R seaux connexionistes " R seaux bay siens " Mod les de Markov

cach s " IV. Apprentissage par approximation et interpolation " Classification

non supervis e " Apprentissage par renforcement " Annexes et bibliographie.

Collection Technique et Scientifique des T l communications

publi e sous l' gide de France Telecom Recherche et D veloppement

s

e

m

h

t

i

r

o

g

A

l

l

e

i

c

i

f

i

t

r

a

e

g

a

s

s

i

t

n

e

r

p

p

A

t

e

l

c

i

M

.

L

s

l

o

j

u

n

r

o

C

.

A

Antoine Cornu jols - Laurent Miclet

Avec la participation dYves Kodratoff

Apprentissage

artificiel

Concepts et algorithmes

Pr face de Tom Mitchell

Apprentissage artificiel

Concepts et algorithmes

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 doptimisation 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 lanalyse des donn es.

N 5256, 1999, 440 pages.

M. GONDRAN, M. MINOUX. Graphes et algorithmes.

N 1571, 1995, 622 pages.

BOURDA. Introduction linformatique th orique.

N 1642, 1994, 236 pages.

Apprentissage artificiel

Concepts et algorithmes

Antoine Cornu jols " Laurent Miclet

Avec la participation dYves Kodratoff

Deuxi me tirage 2003

DITIONS EYROLLES

61, Bld Saint-Germain

75240 Paris cedex 05

www.editions-eyrolles.com

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 sest

g n ralis e notamment dans les tablissements denseignement, provoquant une baisse

brutale des achats de livres, au point que la possibilit m me pour les auteurs de cr er

des Suvres nouvelles et de les faire diter correctement est aujourdhui 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 dExploitation 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

i

Pr(cid:19)eface

sint(cid:19)eresse (cid:18)a l(cid:19)ecriture de programmes dordinateur ca-

Lapprentissage artificiel

pables de sam(cid:19)eliorer automatiquement au (cid:12)l du temps, soit sur la base de leur propre

exp(cid:19)erience, soit (cid:18)a partir de donn(cid:19)ees ant(cid:19)erieures fournies par dautres programmes.

Dans le domaine scienti(cid:12)que relativement jeune de linformatique, lapprentissage ar-

ti(cid:12)ciel joue un r^ole de plus en plus essentiel. Au d(cid:19)ebut de son existence, dans les ann(cid:19)ees 1950,

linformatique se r(cid:19)esumait principalement (cid:18)a programmer des machines en leur sp(cid:19)eci(cid:12)ant ligne

apr(cid:18)es ligne la s(cid:19)equence dinstructions que lordinateur aurait (cid:18)a suivre. Autour des ann(cid:19)ees 1990,

les logiciels (cid:19)etaient devenus si complexes quune alternative simposait naturellement : d(cid:19)evelopper

des techniques pour que les programmes puissent sentra^(cid:16)ner (cid:18)a partir dexemples. Le r(cid:19)esultat est

quil existe aujourdhui de nombreux domaines dapplication de linformatique dans lesquels les

m(cid:19)ethodes de lapprentissage arti(cid:12)ciel sont employ(cid:19)ees pour entra^(cid:16)ner les logiciels. Mieux, le code

r(cid:19)esultant d(cid:19)epasse de beaucoup en performance les r(cid:19)ealisations les plus abouties de programma-

tion manuelle

ligne apr(cid:18)es ligne

. Cest ainsi que tous les meilleurs logiciels commercialis(cid:19)es

((

))

de reconnaissance de la parole sont fond(cid:19)es sur lentra^(cid:16)nement de leurs programmes (cid:18)a la recon-

naissance des di(cid:11)(cid:19)erents sons et mots. La plupart dentre eux permettent m^eme (cid:18)a lutilisateur

daccoutumer le syst(cid:18)eme aux caract(cid:19)eristiques de sa voix. Dautres exemples existent dans des

domaines tels que la vision par ordinateur, le traitement automatique du texte et la robotique.

La discipline de lapprentissage arti(cid:12)ciel peut donc d(cid:19)ej(cid:18)a revendiquer des succ(cid:18)es dans un

grand nombre de domaines dapplication. Des logiciels de fouille de donn(cid:19)ees sont utilis(cid:19)es (cid:18)a

grande (cid:19)echelle pour d(cid:19)ecouvrir quelle prescription est la plus e(cid:14)cace pour quel patient, (cid:18)a partir

de lanalyse de (cid:12)chiers m(cid:19)edicaux ant(cid:19)erieurs. La palette des applications va de la pr(cid:19)ediction de la

demande en (cid:19)energie, (cid:19)etant connu lhistorique des consommations ant(cid:19)erieures, (cid:18)a lapprentissage

de la reconnaissance de transactions frauduleuses par carte de cr(cid:19)edit, par examen des transac-

tions pass(cid:19)ees av(cid:19)er(cid:19)ees frauduleuses. Au moment o(cid:18)u nous passons des cinquante premi(cid:18)eres ann(cid:19)ees

de linformatique au les cinquante prochaines, il semble certain que le r^ole de lapprentissage

arti(cid:12)ciel ne cessera de cro^(cid:16)tre au centre de cette science.

Pourquoi cette progression ? La r(cid:19)eponse fondamentale est que nous poss(cid:19)edons d(cid:19)esormais

la compr(cid:19)ehension de plusieurs principes calculatoires qui guident tout processus dapprentis-

sage, quil soit impl(cid:19)ement(cid:19)e sur une machine ou sur un humain. La discipline de lapprentissage

arti(cid:12)ciel poss(cid:18)ede d(cid:19)esormais de riches fondements th(cid:19)eoriques : on commence (cid:18)a savoir r(cid:19)epondre

(cid:18)a des questions comme :

Combien au mimimum dexemples dentra^(cid:16)nement faut-il fournir (cid:18)a

((

un programme dapprentissage pour ^etre certain quil apprenne avec une e(cid:14)cacit(cid:19)e donn(cid:19)ee ?

))

((

))

et

Quelles m(cid:19)ethodes dapprentissage sont les plus e(cid:14)caces pour tel ou tel type de probl(cid:18)eme ?

Ces fondements proviennent de la th(cid:19)eorie statistique de lestimation, de la th(cid:19)eorie de lidenti(cid:12)-

cation et de la commande optimale, de travaux pionniers sur la complexit(cid:19)e de lapprentissage

de grammaires ou plus r(cid:19)ecents sur linf(cid:19)erence bay(cid:19)esienne algorithmique.

Cet ouvrage fournit au lecteur francophone lintroduction la plus compl(cid:18)ete (cid:18)a ce jour (cid:18)a lap-

prentissage arti(cid:12)ciel. Il traite de la th(cid:19)eorie et des applications de cette discipline sous un grand

nombre daspects, en couvrant des sujets comme lapprentissage bay(cid:19)esien, linf(cid:19)erence gramma-

ticale ou lapprentissage par renforcement. Cest avec plaisir que je recommande au lecteur de

d(cid:19)ecouvrir ce livre, et (cid:18)a travers lui les id(cid:19)ees et les m(cid:19)ethodes de lapprentissage arti(cid:12)ciel.

Tom M.

Mitchell

Pittsburgh, Pennsylvania, USA

Le 29 Mai 2002

The idea of a learning machine may appear paradoxical to some readers.

A. M. Turing, 1950.

iii

(cid:18)a Isabel le, Claire, Aur(cid:19)elie, S(cid:19)ebastien, Fanny

et (cid:18)a Maura, Fabien, Marion

Remerciements

Ce livre est publi(cid:19)e avec laide de lENSSAT. Nous remercions son directeur, Jo(cid:127)el Crestel, davoir

associ(cid:19)e cet (cid:19)etablissement (cid:18)a la publication de cet ouvrage.

Nous devons des remerciements particuliers aux personnes qui nous ont autoris(cid:19)es (cid:18)a reprendre

leurs (cid:19)ecrits, (cid:19)edit(cid:19)es ou non, ainsi qu(cid:18)a toutes celles qui nous ont fait b(cid:19)en(cid:19)e(cid:12)cier de leur expertise

pour nous aider dans la r(cid:19)edaction de cet ouvrage. Notre gratitude va aussi aux lecteurs critiques

des versions pr(cid:19)eliminaires, ce qui inclut notablement une certaine proportion de nos (cid:19)etudiants.

Il nous tient (cid:18)a c(cid:27)ur de remercier tout sp(cid:19)ecialement : Abdel Bela(cid:127)(cid:16)d, Sami Bengio, Christophe

Bernard, Marc Bernard, Olivier Bo(cid:127)e(cid:11)ard, Michel Cartier, Christophe Choisy, Fran(cid:24)cois Coste,

Fran(cid:24)cois Denis, Pierre Dupont, Daniel Fredouille, Colin de la Higuera, Yves Kodrato(cid:11), Isra(cid:127)el-

C(cid:19)esar Lerman, Stan Matwin, Engelbert Mephu Nguifo, Tom Mitchell, Jacques Nicolas, C(cid:19)eline

Rouveirol, Mich(cid:18)ele Sebag, Dominique Snyers, Franck Thollard, Fabien Torre, St(cid:19)ephane Vanden-

mersch et Jean-Daniel Zucker.

Ladresse Web :

contient les (cid:12)gures de cet ouvrage, les trans-

www.editions-eyrolles.com

parents des cours des auteurs et les errata.

Avant-propos

pr(cid:19)esente les th(cid:19)eories, les algorithmes et les applications de lapprentissage

arti(cid:12)ciel. Son ambition est dune part duni(cid:12)er le cadre m(cid:19)ethodologique, et dautre

part de d(cid:19)ecrire un ensemble dalgorithmes utiles, de mani(cid:18)ere coh(cid:19)erente avec ce cadre,

en(cid:12)n de faire conna^(cid:16)tre ses applications existantes et potentielles.

Ce livre

(cid:18)

A quoi sert lapprentissage arti(cid:12)ciel ? La plupart des programmes dintelligence arti(cid:12)cielle

poss(cid:18)edent aujourdhui un module dapprentissage et tous les programmes de reconnaissance

des formes sont fond(cid:19)es sur des algorithmes dapprentissage. Et que font ces programmes ? Ils

sont capables de reconna^(cid:16)tre la parole humaine et de linterpr(cid:19)eter. Ils r(cid:19)ealisent une analyse

automatique de photos satellites pour d(cid:19)etecter certaines ressources sur la Terre. Ils assistent

les experts pour prendre des d(cid:19)ecisions dans des environnements complexes et (cid:19)evolutifs, par

exemple le march(cid:19)e (cid:12)nancier ou le diagnostic m(cid:19)edical. Ils fouillent dimmenses bases de donn(cid:19)ees

h(cid:19)et(cid:19)erog(cid:18)enes comme les millions de pages Web accessibles (cid:18)a tous. Ils analysent les donn(cid:19)ees client(cid:18)ele

des entreprises pour les aider (cid:18)a mieux cibler leurs campagnes de publicit(cid:19)e. Ils participent aussi

(cid:18)a des tournois : le 11 mai 1997, le tenant du titre de champion du monde du jeu d(cid:19)echecs, Gary

Kasparov, a (cid:19)et(cid:19)e battu en match par un programme.

On sait donc programmer les ordinateurs pour leur faire ex(cid:19)ecuter des t^aches consid(cid:19)er(cid:19)ees

comme intelligentes, de multiples fa(cid:24)cons et de mani(cid:18)ere de plus en plus e(cid:14)cace. Cet ouvrage

sint(cid:19)eresse (cid:18)a un aspect particulier de cette intelligence arti(cid:12)cielle : la facult(cid:19)e dapprentissage.

Lapprentissage arti(cid:12)ciel est une discipline dont les outils et les champs dapplications sont

assez disparates. Cependant, les connaissances de base n(cid:19)ecessaires (cid:18)a sa compr(cid:19)ehension sont essen-

tiellement une culture g(cid:19)en(cid:19)eraliste que lon trouve par exemple dans les ouvrages de math(cid:19)ematiques

pour linformatique : notions dalg(cid:18)ebre lin(cid:19)eaire, de probabilit(cid:19)es, de combinatoire, danalyse (cid:19)el(cid:19)emen-

taire, dalgorithmique, de th(cid:19)eorie des langages, de logique. Dans la mesure du possible, ces notions

de base sont bri(cid:18)evement rappell(cid:19)ees selon la n(cid:19)ecessit(cid:19)e des chapitres de ce livre.

(cid:18)

A qui sadresse cet ouvrage ?

On peut tirer pro(cid:12)t de cet ouvrage en autodidacte, comme le fera par exemple un ing(cid:19)enieur

qui cherche (cid:18)a conna^(cid:16)tre ce qui se cache derri(cid:18)ere les mots ou (cid:18)a acqu(cid:19)erir une initiation (cid:18)a des

techniques quil ignore encore. On pourra aussi sen servir comme dun appui pour compl(cid:19)eter un

enseignement : ce sera le cas pour un (cid:19)etudiant au niveau ma^(cid:16)trise, DEA ou e(cid:19)cole ding(cid:19)enieurs,

ou comme dun ouvrage de r(cid:19)ef(cid:19)erence pour faire un cours sur le domaine.

vi

Quelques applications de lapprentissage arti(cid:12)ciel

Voyons maintenant comment rendre un programme plus e(cid:14)cace en le dotant dune possi-

bilit(cid:19)e dapprentissage. Reprenons pour cela les applications de lintelligence arti(cid:12)cielle et de la

reconnaissance des formes cit(cid:19)ees ci-dessus.

(cid:15)

(cid:15)

(cid:15)

(cid:15)

(cid:15)

(cid:15)

Un programme de reconnaissance de la parole augmente ses performances au fur et (cid:18)a

mesure de son utilisation par la m^eme personne : cest une exp(cid:19)erience quil est aujourdhui

facile de faire en pratique si on ach(cid:18)ete un logiciel personnel de dict(cid:19)ee vocale.

Un programme de d(cid:19)etection des ressources terrestres apprend (cid:18)a reconna^(cid:16)tre une zone de

pollution au milieu de la mer, (cid:18)a partir dune base de donn(cid:19)ees dexemples dimages de zones

connues comme propres ou comme pollu(cid:19)ees : cette base de donn(cid:19)ees lui sert dexp(cid:19)erience

pour d(cid:19)eterminer sa d(cid:19)ecision sur une zone inconnue.

Un programme de diagnostic sur un ensemble dinformations (cid:19)evolutives prises sur un

patient doit avoir (cid:19)et(cid:19)e pourvu de connaissances, (cid:18)a partir de diagnostics de praticiens

et dexperts sur des situations types. Mais il doit aussi avoir (cid:19)et(cid:19)e dot(cid:19)e dun module de

g(cid:19)en(cid:19)eralisation, de fa(cid:24)con (cid:18)a r(cid:19)eagir correctement (cid:18)a des situations auxquelles il na jamais (cid:19)et(cid:19)e

confront(cid:19)e exactement.

Les moteurs de recherche sur le Web pourraient ^etre munis dun module dadaptation au

style de navigation de lusager : cest une facult(cid:19)e souhaitable pour augmenter lergonomie

de leur utilisation. Les programmes ne sont pas encore r(cid:19)eellement agr(cid:19)ement(cid:19)es de cette

propri(cid:19)et(cid:19)e, mais il est clair que cest une condition n(cid:19)ecessaire pour franchir certains obstacles

de communication si (cid:19)evidents actuellement.

Lexploitation des (cid:12)chiers client dune entreprise est souvent faite par un expert ou un

programme expert qui utilise des r(cid:18)egles explicites pour cibler un segment de client(cid:18)ele sus-

ceptible d^etre int(cid:19)eress(cid:19)e par un nouveau produit. Mais ces r(cid:18)egles peuvent ^etre acquises

automatiquement, par un apprentissage dont le but est de fournir de nouvelles connais-

sances expertes, (cid:18)a la fois e(cid:14)caces et intelligibles pour lexpert.

Un programme de jeu d(cid:19)echecs poss(cid:18)ede en g(cid:19)en(cid:19)eral une tr(cid:18)es bonne e(cid:14)cacit(cid:19)e a priori ; mais

il est naturel dessayer de le doter dun module o(cid:18)u il puisse analyser ses d(cid:19)efaites et ses

victoires, pour am(cid:19)eliorer ses performances moyennes dans ses parties futures. Ce module

dapprentissage existe dans un certain nombre de programmes de jeux.

Quelques d(cid:19)e(cid:12)nitions de base

Apprentissage

(sous entendu : arti(cid:12)ciel, automatique) (Machine Learning)

Cette notion englobe toute m(cid:19)ethode permettant de construire un mod(cid:18)ele de la r(cid:19)ealit(cid:19)e (cid:18)a

partir de donn(cid:19)ees, soit en am(cid:19)eliorant un mod(cid:18)ele partiel ou moins g(cid:19)en(cid:19)eral, soit en cr(cid:19)eant

compl(cid:18)etement le mod(cid:18)ele. Il existe deux tendances principales en apprentissage, celle is-

sue de lintelligence arti(cid:12)cielle et quali(cid:12)(cid:19)ee de symbolique, et celle issue des statistiques et

quali(cid:12)(cid:19)ee de num(cid:19)erique.

Fouille de donn(cid:19)ees

(Data Mining) ou Extraction de connaissances (cid:18)a partir des donn(cid:19)ees

(Know ledge Discovery in Data)

La fouille de donn(cid:19)ees prend en charge le processus complet dextraction de connaissances :

stockage dans une base de donn(cid:19)ees, s(cid:19)election des donn(cid:19)ees (cid:18)a (cid:19)etudier, si n(cid:19)ecessaire : nettoyage

des donn(cid:19)ees, puis utilisation des apprentissages num(cid:19)eriques et symboliques a(cid:12)n de proposer

des mod(cid:18)eles (cid:18)a lutilisateur, en(cid:12)n validation des mod(cid:18)eles propos(cid:19)es. Si ces mod(cid:18)eles sont

invalid(cid:19)es par lutilisateur, le processus complet est r(cid:19)ep(cid:19)et(cid:19)e.

Avant-propos

vii

Pr(cid:19)ecision

G(cid:19)en(cid:19)eralisation

vs.

Le grand dilemme de lapprentissage. La pr(cid:19)ecision est d(cid:19)e(cid:12)nie par un (cid:19)ecart entre une valeur

mesur(cid:19)ee ou pr(cid:19)edite et une valeur r(cid:19)eelle. Apprendre avec trop de pr(cid:19)ecision conduit (cid:18)a un

((

))

sur-apprentissage

, comme lapprentissage par c(cid:27)ur, pour lequel des d(cid:19)etails insigni-

(cid:12)ants (ou d^us au bruit) sont appris. Apprendre avec trop peu de pr(cid:19)ecision conduit (cid:18)a une

((

))

sur-g(cid:19)en(cid:19)eralisation

telle que le mod(cid:18)ele sapplique m^eme quand lutilisateur ne le d(cid:19)esire

pas. Les deux types dapprentissage, num(cid:19)erique et symbolique, ont d(cid:19)e(cid:12)ni des mesures de

g(cid:19)en(cid:19)eralisation et cest (cid:18)a lutilisateur de (cid:12)xer le seuil de g(cid:19)en(cid:19)eralisation quil juge optimal.

Intelligibilit(cid:19)e

(devrait ^etre Comprehensibility mais tend (cid:18)a devenir Understandability)

Depuis quelques ann(cid:19)ees, principalement sous la pouss(cid:19)ee des industriels, les chercheurs se

sont mis (cid:18)a essayer de contr^oler aussi lintelligibilit(cid:19)e du mod(cid:18)ele obtenu par la fouille de

donn(cid:19)ees. Jusqu(cid:18)a pr(cid:19)esent les m(cid:19)ethodes de mesure de lintelligibilit(cid:19)e se r(cid:19)eduisent (cid:18)a v(cid:19)eri(cid:12)er

que les r(cid:19)esultats sont exprim(cid:19)es dans le langage de lutilisateur et que la taille des mod(cid:18)eles

nest pas excessive. Des m(cid:19)ethodes sp(cid:19)eci(cid:12)ques de visualisation sont aussi utilis(cid:19)ees.

Classi(cid:12)cation, classement et r(cid:19)egression.

La classi(cid:12)cation, telle quelle est d(cid:19)e(cid:12)nie en analyse de donn(cid:19)ees, consiste (cid:18)a regrouper des

ensembles dexemples non supervis(cid:19)es en classes. Ces classes sont souvent organis(cid:19)ees en

une structure (clustering). Si cette structure est un arbre, alors on parle de taxonomie ou

de taxinomie (taxonomy). Sous lin(cid:13)uence du mot anglais classi(cid:12)cation, on a tendance (cid:18)a

confondre classi(cid:12)cation et classement. Ce dernier mot d(cid:19)esigne le processus de reconnais-

sance en intension (par leur propri(cid:19)et(cid:19)es) de classes d(cid:19)ecrites en extension (par les valeurs

de leurs descripteurs). Lorsque les valeurs (cid:18)a pr(cid:19)edire sont des classes en petit nombre, on

parle de classi(cid:12)cation. Il sagit par exemple de pr(cid:19)evoir lappartenance dun oiseau observ(cid:19)e

(cid:18)a la classe

canard

ou

oie

. La r(cid:19)egression traite des cas o(cid:18)u les valeurs (cid:18)a pr(cid:19)edire sont

((

))

((

))

num(cid:19)eriques, par exemple : nombre dexemplaires de cet ouvrage qui seront vendus = 3900.

Deux champs industriels de lapprentissage arti(cid:12)ciel :

la reconnaissance des formes et la fouille de donn(cid:19)ees

En quarante ans et plus dexistence, lapprentissage arti(cid:12)ciel a fourni un grand nombre

doutils aux industriels et aux entrepreneurs. Nous les regroupons selon deux grands axes : la

reconnaissance des formes et la fouil le de donn(cid:19)ees ou pour ^etre plus pr(cid:19)ecis, lextraction de

connaissances des donn(cid:19)ees.

Le second domaine est le moins bien connu des deux bien quil soit porteur de r(cid:19)eelles possi-

bilit(cid:19)es (cid:19)economiques.

Quant au premier, rappellons seulement que les m(cid:19)ethodes de lapprentissage arti(cid:12)ciel sont (cid:18)a

la base de la reconnaissance des images ((cid:19)ecriture manuscrite, signatures, d(cid:19)etection de ressources

par satellite, pilotage automatique, etc.), de la reconnaissance de la parole, du traitement avanc(cid:19)e

des signaux bio-m(cid:19)edicaux, etc. Pour mesurer lextraordinaire vitalit(cid:19)e des applications et des

potentialit(cid:19)es de la reconnaissance des formes, il su(cid:14)t par exemple de suivre la parution incessante

des livres dans ce domaine. Pour ne citer que lui, l(cid:19)editeur World Scienti(cid:12)c a une cinquantaine

de titres (cid:18)a son catalogue sous la rubrique

Applications de la reconnaissance des formes

et les

((

))

renouvelle (cid:18)a raison de pr(cid:18)es dune dizaine par an.

Revenons maintenant (cid:18)a la fouille de donn(cid:19)ees. Les probl(cid:18)emes pratiques que peut r(cid:19)esoudre en

ce domaine lapprentissage arti(cid:12)ciel se posent constamment dans la vie industrielle : comment

distinguer un bon client dun mauvais, comment reconna^(cid:16)tre un mauvais proc(cid:19)ed(cid:19)e de fabrication

et lam(cid:19)eliorer, voil(cid:18)a deux exemples frappants parmi dautres. On constate pourtant que lancrage

viii

de ce type dapplication dans la vie industrielle ne date que des ann(cid:19)ees 1990, avec la naissance

dun discipline nouvelle, cr(cid:19)e(cid:19)ee sous le nom de

fouille de donn(cid:19)ees

(data mining ) ou ECD :

((

))

((

))

extraction de connaissances (cid:18)a partir des donn(cid:19)ees

(know ledge discovery in databases, KDD).

Nous pr(cid:19)esentons rapidement le domaine avant den donner l(cid:19)etat de lart industriel dans le dernier

paragraphe de cet avant-propos.

LECD est n(cid:19)ee de la constatation que les trois approches qui permettaient de construire des

mod(cid:18)eles, (cid:18)a savoir les statistiques exploratoires, lanalyse des donn(cid:19)ees et lapprentissage symbo-

lique automatique (ASA), sou(cid:11)raient de deux d(cid:19)efauts communs : exiger des donn(cid:19)ees pr(cid:19)esent(cid:19)ees

sous une forme tr(cid:18)es rigide et faire peu de cas de lintelligibilit(cid:19)e des r(cid:19)esultats. De plus, chacune

pr(cid:19)esentait un d(cid:19)efaut particulier g^enant leur emploi : les statistiques exploratoires et lanalyse des

donn(cid:19)ees sadressaient (cid:18)a des donn(cid:19)ees essentiellement num(cid:19)eriques et lASA se limitait aux donn(cid:19)ees

symboliques ou discr(cid:19)etis(cid:19)ees en intervalles de valeurs.

Depuis, ces domaines ont (cid:19)evolu(cid:19)e et les critiques (cid:18)a leur adresser ont chang(cid:19)e, mais tel (cid:19)etait

l(cid:19)etat de lart dans les ann(cid:19)ees 1990. LECD est donc n(cid:19)ee dun quadruple e(cid:11)ort :

permettre aux utilisateurs de fournir des donn(cid:19)ees dans l(cid:19)etat o(cid:18)u elles sont : ceci a donn(cid:19)e

naissance aux techniques de nettoyage des donn(cid:19)ees (ce point sera d(cid:19)evelopp(cid:19)e au chapitre 3) ;

utiliser les donn(cid:19)ees enregistr(cid:19)ees sous forme de bases de donn(cid:19)ees (en g(cid:19)en(cid:19)eral relationnelles) :

ceci a provoqu(cid:19)e un large courant de recherche au sein de la communaut(cid:19)e des BD int(cid:19)eress(cid:19)ee

par la cr(cid:19)eation de mod(cid:18)eles ;

fournir aux utilisateurs des outils capables de travailler sur des donn(cid:19)ees mixtes, num(cid:19)eriques

et symboliques ;

construire des outils produisant une connaissance intelligible aux utilisateurs.

(cid:15)

(cid:15)

(cid:15)

(cid:15)

Cest ainsi que lECD a pu trouver la large reconnaissance industrielle dont elle jouit actuelle-

ment. Elle a commenc(cid:19)e (cid:18)a r(cid:19)esoudre les deux probl(cid:18)emes industriels principaux de lanalyse des

donn(cid:19)ees, ceux qui co^utent le plus cher : le fait que le client est souvent impr(cid:19)ecis dans la d(cid:19)e(cid:12)nition

du probl(cid:18)eme quil se pose et le fait que les donn(cid:19)ees dont il dispose sont souvent de qualit(cid:19)e dis-

cutable.

L(cid:19)etude des applications industrielles de lECD montre quil existe une assez forte demande

en outils de cr(cid:19)eation de mod(cid:18)eles, autrement dit en apprentissage arti(cid:12)ciel. Ceci se traduit par le

fait quenviron cent cinquante compagnies se sont sp(cid:19)ecialis(cid:19)ees dans ce domaine. Certaines de ces

compagnies existent depuis plusieurs ann(cid:19)ees et dautres se sont vendues fort cher. Lensemble

rev(cid:18)ele bien un secteur en progression raisonnable sur plusieurs ann(cid:19)ees.

Notre estimation est que le march(cid:19)e de lECD est occup(cid:19)e par 60 % doutils dapprentissage

statistique et 40 % doutils dapprentissage symboliques. Ces derni(cid:18)eres techniques (cid:19)etant moins

enseign(cid:19)ees que les premi(cid:18)eres dans les universit(cid:19)es, on constate un hiatus entre lenseignement et

lindustrie. En tous cas, le pr(cid:19)esent livre cherche (cid:18)a aller dans le sens dun meilleur enseignement

des m(cid:19)ethodes de lapprentissage arti(cid:12)ciel, symbolique comme statistique.

Les caract(cid:19)eristiques de lapprentissage arti(cid:12)ciel

Certaines des facult(cid:19)es que lon peut lier naturellement (cid:18)a lapprentissage ont (cid:19)et(cid:19)e cit(cid:19)ees dans

les exemples ci-dessus : entra^(cid:16)nement, reconnaissance, g(cid:19)en(cid:19)eralisation, adaptation, am(cid:19)elioration,

intelligibilit(cid:19)e.

Rappellons la d(cid:19)e(cid:12)nition classique de lapprentissage en sciences cognitives :

capacit(cid:19)e (cid:18)a

((

am(cid:19)eliorer les performances au fur et (cid:18)a mesure de lexercice dune activit(cid:19)e

. Cette d(cid:19)e(cid:12)nition

))

sapplique en particulier au comportement dun joueur d(cid:19)echecs au (cid:12)l des parties, o(cid:18)u lassimi-

lation de lexp(cid:19)erience et la puissance de raisonnement se combinent dans sa progression. Elle

Avant-propos

ix

est aussi pertinente pour des t^aches perceptives : on shabitue (cid:18)a un accent, (cid:18)a une (cid:19)ecriture. On

accumule des bonnes et des mauvaises exp(cid:19)eriences.

A partir delles, on sait, consciemment ou

(cid:18)

non, en abstraire ou faire (cid:19)evoluer des r(cid:18)egles pour mieux e(cid:11)ectuer la t^ache.

Nous avons mentionn(cid:19)e une autre facette de lapprentissage, souvent entrem^el(cid:19)ee (cid:18)a la pr(cid:19)ec(cid:19)edente :

la facult(cid:19)e (cid:18)a g(cid:19)en(cid:19)eraliser rationnellement. Si une exp(cid:19)erience accumul(cid:19)ee sur un certain nombre

dexemples a permis de tirer des r(cid:18)egles de comportement, ces r(cid:18)egles doivent sappliquer aussi (cid:18)a

des situations non encore rencontr(cid:19)ees. Prenons quelquun qui apprend (cid:18)a conduire sur une berline

de petite puissance. D(cid:18)es quil a m(cid:19)erit(cid:19)e le permis, la loi lautorise (cid:18)a conduire une camionnette

utilitaire ou une voiture de sport. Cest que les r(cid:18)egles quil a apprises et les r(cid:19)e(cid:13)exes quil a acquis

sappliquent aussi (plus ou moins directement) (cid:18)a ces v(cid:19)ehicules.

Quen est-il des machines ? D(cid:18)es les d(cid:19)ebuts de lintelligence arti(cid:12)cielle, cest-(cid:18)a-dire en v(cid:19)erit(cid:19)e

d(cid:18)es lapparition des ordinateurs, les chercheurs et les ing(cid:19)enieurs se sont pos(cid:19)es le probl(cid:18)eme de

lapprentissage

. Lapprentissage arti(cid:12)ciel dans sa situation actuelle est donc le produit dune

1

histoire de cinquante ans de recherches et de r(cid:19)ealisations. Comme on la vu, un grand nombre

de t^aches dintelligence arti(cid:12)cielle et de reconnaissance des formes sappuient ou sont fond(cid:19)ees

sur des modules dapprentissage.

On verra dans cet ouvrage comment des programmes peuvent mettre en (cid:27)uvre un appren-

tissage par am(cid:19)elioration du comportement, en g(cid:19)en(cid:19)eral gr^ace (cid:18)a des techniques doptimisation.

On verra aussi quil est possible d(cid:19)ecrire des programmes qui r(cid:19)ealisent un apprentissage par

g(cid:19)en(cid:19)eralisation : quand on leur donne su(cid:14)samment dexemples et le type du concept (cid:18)a apprendre,

ils choisissent un concept qui nest pas seulement valide sur les exemples quils ont vus, mais

qui sera (cid:19)egalement valable pour dautres. Cest ainsi quun programme de reconnaissance de la

parole ne peut pas

entendre

tous les sons avant d(cid:19)elaborer une r(cid:18)egle de d(cid:19)ecision. Il est (cid:19)ecrit

((

))

pour extraire une m(cid:19)ethode de classi(cid:12)cation de ceux quon lui a pr(cid:19)esent(cid:19)es et traiter ensuite du

mieux possible tous les sons quil aura (cid:18)a d(cid:19)ecoder.

En r(cid:19)ealit(cid:19)e, dun point de vue informatique, la probl(cid:19)ematique nest pas fondamentalement

di(cid:11)(cid:19)erente dans les deux cas. Il sagit dans le premier de faire (cid:19)evoluer des r(cid:18)egles de comportement

au (cid:12)l des exemples et dans le second dextraire des r(cid:18)egles (cid:18)a partir dun ensemble dexemples

donn(cid:19)e a priori. De m^eme que dans lapprentissage naturel, un panachage de ces deux modes de

fonctionnement...