Algorithmes

e
3é

3é
3e édition
Apprentissage

dit

dit
ion

ion
artificiel Antoine Cornuéjols
Laurent Miclet - Vincent Barra

Apprentissage artificiel
Apprentissage
Antoine Cornuéjols Les programmes d’intelligence artificielle sont aujourd’hui
est professeur à capables de reconnaître des commandes vocales, d’analyser
AgroParisTech. automatiquement des photos satellites, d’assister des experts
Il enseigne pour prendre des décisions dans des environnements complexes et
l’apprentissage évolutifs (analyse de marchés financiers, diagnostics médicaux...),
artificiel dans plusieurs de fouiller d’immenses bases de données hétérogènes, telles les
grandes écoles et en innombrables pages du Web...
Master. Ses recherches

artificiel
portent notamment sur Pour réaliser ces tâches, ils sont dotés de modules d’apprentissage
l’apprentissage en ligne, leur permettant d’adapter leur comportement à des situations
l’apprentissage à partir jamais rencontrées, ou d’extraire des lois à partir de bases
de flux de données ainsi de données d’exemples. Ce livre présente les concepts qui
que sur des applications sous-tendent l’apprentissage artificiel, les algorithmes qui en
en bio-informatique et découlent et certaines de leurs applications. Son objectif est de
sciences du vivant. décrire un ensemble d’algorithmes utiles en tentant d’établir un
cadre théorique pour l’ensemble des techniques regroupées sous
Laurent Miclet est ce terme « d’apprentissage artificiel ».
professeur émérite
d’informatique à l’Enssat, La troisième édition de ce livre a été complètement réorganisée
où il a en particulier
enseigné l’algorithmique.
Son domaine de
pour s’adapter aux évolutions très significatives de l’apprentissage
artificiel ces dernières années. Une large place y est accordée
aux techniques d’apprentissage profond et à de nouvelles
Deep learning, concepts
et algorithmes
recherche est applications, incluant le traitement de flux de données.
l’intelligence artificielle
et l’apprentissage À qui s’adresse ce livre ?
automatique.
Ce livre s’adresse tant aux décideurs et aux
Vincent Barra est ingénieurs qui souhaitent mettre au point des
professeur d’informatique applications qu’aux étudiants de niveau Master 1 et 2
à l’université Clermont et en école d’ingénieurs, qui souhaitent un ouvrage
Auvergne, où il enseigne de référence sur ce domaine clé de l’intelligence
: 978-2-212-67522-1

artificielle.
ISBN : 978-2-212-67522-1

l’apprentissage artificiel
Code éditeur : G67522
éditeur : G67522

et le traitement d’images
Sommaire
56 €
en école d’ingénieurs et
en Master. Ses activités Des machines apprenantes ! • L’induction exploitant la structure

A. Cornuéjols
de recherche portent de l’espace des hypothèses • L’induction par optimisation
sur l’analyse de données d’un système inductif • L’induction par comparaison à des
n-dimensionnelles,
Code

exemples (et par collaboration) • L’apprentissage descriptif •

L. Miclet
V. Barra
avec des volets
ISBN

Apprentissage en environnement et non stationnaire • Aspects

méthodologiques et pratiques et suppléments • Annexes et bibliographie
applicatifs dans divers
domaines. 56 E
 Algorithmes
e

e
3é

3é
3e édition
Apprentissage

dit

dit
ion

ion
artificiel Antoine Cornuéjols
Laurent Miclet - Vincent Barra

Apprentissage artificiel
Apprentissage
Antoine Cornuéjols Les programmes d’intelligence artificielle sont aujourd’hui
est professeur à capables de reconnaître des commandes vocales, d’analyser
AgroParisTech. automatiquement des photos satellites, d’assister des experts
Il enseigne pour prendre des décisions dans des environnements complexes et
l’apprentissage évolutifs (analyse de marchés financiers, diagnostics médicaux...),
artificiel dans plusieurs de fouiller d’immenses bases de données hétérogènes, telles les
grandes écoles et en innombrables pages du Web...
Master. Ses recherches

artificiel
portent notamment sur Pour réaliser ces tâches, ils sont dotés de modules d’apprentissage
l’apprentissage en ligne, leur permettant d’adapter leur comportement à des situations
l’apprentissage à partir jamais rencontrées, ou d’extraire des lois à partir de bases
de flux de données ainsi de données d’exemples. Ce livre présente les concepts qui
que sur des applications sous-tendent l’apprentissage artificiel, les algorithmes qui en
en bio-informatique et découlent et certaines de leurs applications. Son objectif est de
sciences du vivant. décrire un ensemble d’algorithmes utiles en tentant d’établir un
cadre théorique pour l’ensemble des techniques regroupées sous
Laurent Miclet est ce terme « d’apprentissage artificiel ».
professeur émérite
d’informatique à l’Enssat, La troisième édition de ce livre a été complètement réorganisée
où il a en particulier
enseigné l’algorithmique.
Son domaine de
pour s’adapter aux évolutions très significatives de l’apprentissage
artificiel ces dernières années. Une large place y est accordée
aux techniques d’apprentissage profond et à de nouvelles
Deep learning, concepts
et algorithmes
recherche est applications, incluant le traitement de flux de données.
l’intelligence artificielle
et l’apprentissage À qui s’adresse ce livre ?
automatique.
Ce livre s’adresse tant aux décideurs et aux
Vincent Barra est ingénieurs qui souhaitent mettre au point des
professeur d’informatique applications qu’aux étudiants de niveau Master 1 et 2
à l’université Clermont et en école d’ingénieurs, qui souhaitent un ouvrage
Auvergne, où il enseigne de référence sur ce domaine clé de l’intelligence
artificielle.
ISBN : 978-2-212-67522-1

l’apprentissage artificiel
Code éditeur : G67522

et le traitement d’images
Sommaire
56 €
en école d’ingénieurs et
en Master. Ses activités Des machines apprenantes ! • L’induction exploitant la structure

A. Cornuéjols
de recherche portent de l’espace des hypothèses • L’induction par optimisation
sur l’analyse de données d’un système inductif • L’induction par comparaison à des
n-dimensionnelles, exemples (et par collaboration) • L’apprentissage descriptif •

L. Miclet
V. Barra
avec des volets Apprentissage en environnement et non stationnaire • Aspects
méthodologiques et pratiques et suppléments • Annexes et bibliographie
applicatifs dans divers
domaines.
 Antoine Cornuéjols
Laurent Miclet - Vincent Barra

Apprentissage
artificiel
Deep learning, concepts
et algorithmes
3e édition
 Éditions Eyrolles
61, bd Saint-Germain
75240 Paris Cedex 05
[Link]

En application de la loi du 11 mars 1957, il est interdit de reproduire intégralement ou partiel-

lement le présent ouvrage, sur quelque support que ce soit, sans l’autorisation de l’Éditeur ou
du Centre français d’Exploitation du droit de copie, 20, rue des Grands-Augustins, 75006 Paris.

© Groupe Eyrolles, 2002, 2010, 2018, ISBN : 978-2-212-67522-1

 i

Avant-propos de la troisième édition

L’engouement pour l’intelligence artificielle a atteint récemment un niveau exceptionnel, en

particulier à la suite des succès du programme AlphaGo au jeu de go, des attentes entretenues
sur les véhicules autonomes, des performances croissantes de nos assistants personnels sur les
smartphones et, plus généralement, en raison de la révolution des « big data » dans laquelle l’IA
joue un rôle central.
L’intelligence artificielle est à la fois fascinante et inquiétante. Parvenir à mieux comprendre
l’intelligence et la pensée, créer des machines qui reproduisent des comportements jugés intel-
ligents, qui peut-être raisonnent et pourraient nous assister dans nos tâches cognitives, est un
puissant moteur d’intérêt pour cette science encore neuve. En tant qu’enseignants-chercheurs,
nous pouvons le mesurer dans le regard de nos étudiants, qui, souvent, exprime beaucoup d’at-
tentes, d’enthousiasme et d’envie de participer à l’exploration de la nouvelle frontière. Nous
percevons également, lors de nos diverses actions de vulgarisation, l’engouement, mais aussi les
craintes du grand public face au développement exponentiel de la discipline. En effet, les spécia-
listes de l’intelligence artificielle sont aussi, parfois, perçus comme des apprentis sorciers. L’IA
pourrait-elle un jour échapper à ses créateurs et décider de poursuivre son destin, un destin
indifférent, voire hostile, à l’humanité ?
Pour mettre en perspective les réalisations et les fantasmes et mesurer ce qui les sépare, rien
de tel que chercher à connaître et à comprendre l’état de l’art. C’est la meilleure propédeutique
pour être des citoyens éclairés.
Le renouveau de l’intérêt pour l’intelligence artificielle est en grande partie du aux travaux
récents en apprentissage artificiel, particulièrement ceux liés au développement des réseaux de
neurones profonds, que les médias égalent à l’apprentissage profond. Il est un fait que les progrès
récents en vision artificielle, en compréhension de la parole et du langage, en robotique, en
diagnostic, etc. sont, pour une large part, dus à l’incorporation de méthodes d’apprentissage
artificiel dans les algorithmes.
C’est pourquoi, si l’on veut comprendre comment l’intelligence artificielle fonctionne, ce qu’il
est possible d’en attendre dans les années à venir, quels sont les questions à résoudre et les
obstacles à surmonter, il est nécessaire d’étudier les grands concepts et les approches de l’ap-
prentissage artificiel. Cet ouvrage vise à fournir au lecteur les clés permettant d’appréhender
les fondements de l’apprentissage artificiel, les grandes directions, les approches algorithmiques
ainsi que les nouvelles questions qui émergent.
Il est original parce qu’il adopte le point de vue de l’intelligence artificielle, orienté vers la
décision, vers des solutions fondées mathématiquement, mais heuristiques aussi. En ceci, il dif-
fère de la plupart des ouvrages publiés qui ont un regard « bayésien » fondé sur la notion de
distribution de probabilité. Notre livre fait une place à ce regard là, très puissant et très utile,
mais il n’en fait pas le socle de son organisation.
Cet ouvrage est original aussi parce qu’il est rédigé en français. Nous croyons qu’il est essentiel
qu’une langue vive avec les sciences de son temps et soit capable d’en exprimer toutes les
subtilités sans devoir passer par un jargon, angliciste le plus souvent. L’accueil bienveillant et
reconnaissant des précédentes éditions de cet ouvrage dans les pays francophones nous conforte
dans notre conviction.
Un signe de l’évolution très rapide de l’apprentissage artificiel est, qu’au moment où il nous
fallut nous interroger sur l’opportunité d’une ré-impression de la deuxième édition, datant de

[Link] 3 16/03/2018 11:49

 ii

2010, il fut immédiatement évident qu’une profonde réorganisation de l’ouvrage avec l’ajout de
thèmes récents était souhaitable sinon nécessaire.
La nouvelle édition que vous avez entre les mains fait donc naturellement une large place aux
réseaux de neurones profonds, alors que ceux-ci étaient traités en quelques pages dans l’édition
précédente. L’apprentissage par renforcement, à la base des succès de AlphaGo, fait l’objet d’un
chapitre largement étendu. Le traitement du signal et des images a connu des évolutions rapides
ces dernières années avec l’acquisition comprimée (compressed sensing) et l’apprentissage de
dictionnaires par exemple. Nous avons donc introduit ces concepts et méthodes dans l’ouvrage.
Il en est de même pour les méthodes d’espaces latents et d’espaces sémantiques qui sont em-
ployées dans les applications de compréhension et de traitement de la langue naturelle. Étant
donné l’énorme développement des applications et du « big data », nous avons consacrés des
chapitres inédits aux aspects pratiques de développement de projets. Globalement, l’émergence
de nouveaux champs d’application de l’apprentissage artificiel incluant le traitement de flux de
données, le fonctionnement dans des environnements changeants et non plus stationnaires, l’ap-
prentissage de causalités, nous ont conduit à repenser l’organisation de l’ouvrage, qui est donc
novatrice par rapport aux deux précédentes éditions.
Nous espérons qu’avec cette nouvelle édition, qui reflète les évolutions de l’apprentissage ar-
tificiel, nous fournissons aux lecteurs le moyen de mieux comprendre les fondements de cette
science et des technologies qui en découlent, mais aussi les outils conceptuels et méthodologiques
pour aborder avec confiance le développement de projets dans ce domaine, si ouvert et si riche
de potentialités.

Un grand merci à Irène Demongeot, Germain Forestier et Colin de la Higuera qui ont contribué
respectivement aux chapitres « Apprentissage et théorie du domaine », « Apprentissage par
similarité » et « L’inférence grammaticale » de cette nouvelle édition.

Nous tenons aussi à remercier vivement l’accompagnement des Éditions Eyrolles depuis des
années, et le travail considérable des correcteurs pour traquer les imperfections à tous les niveaux
du manuscrit. Les erreurs et coquilles restantes sont de notre responsabilité, même si nous les
déplorons à l’avance et seront heureux de les corriger si elles nous sont signalées.

Antoine Cornuéjols, Laurent Miclet et Vincent Barra

Paris, Lannion, Clermont-Ferrand, France

Le 31 Janvier 2018

[Link] 4 16/03/2018 11:49

 Table des matières

Table des matières iii

Notations ix

I Des machines apprenantes ! 1

1 Des algorithmes qui apprennent ? 3

1 La révolution numérique en cours et le « big data » . . . . . . . . . . . . . . . . . 5
2 Apprentissage et induction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
3 Des apprentissages différents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
4 Les notions d’espace d’hypothèses et de critère inductif . . . . . . . . . . . . . . . 15
5 Les ingrédients de l’apprentissage . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
6 Les méthodes paramétriques et non paramétriques, et les autres . . . . . . . . . . 24
7 L’espace des hypothèses d’apprentissage . . . . . . . . . . . . . . . . . . . . . . . 25
8 Les protocoles d’apprentissage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
9 Une brève mise en perspective historique . . . . . . . . . . . . . . . . . . . . . . . 36
10 Des questions que tout le monde se pose . . . . . . . . . . . . . . . . . . . . . . . 39

2 Introduction à des approches théoriques de l’induction supervisée 43

1 Essayons d’apprendre un concept à partir d’exemples . . . . . . . . . . . . . . . . 45
2 Formalisation d’un problème d’apprentissage supervisé . . . . . . . . . . . . . . . 49
3 L’analyse bayésienne . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
4 Analyse du principe de Minimisation du Risque Empirique . . . . . . . . . . . . 64
5 Le lien entre le passé et le futur et le no-free-lunch theorem . . . . . . . . . . . . 77

II L’induction exploitant la structure de l’espace des hypothèses 85

3 Exploitation d’une relation de généralité entre hypothèses 87

1 Les concepts de base . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
2 La structuration de l’espace des hypothèses . . . . . . . . . . . . . . . . . . . . . 95
3 La construction de l’espace des versions . . . . . . . . . . . . . . . . . . . . . . . 101
4 La représentation des connaissances par un treillis de Galois . . . . . . . . . . . . 106

[Link] 5 16/03/2018 11:49

 iv Table des matières

4 L’inférence grammaticale 111

1 Définitions et notations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
2 Les protocoles de l’inférence : quelques résultats théoriques . . . . . . . . . . . . 126
3 L’espace de recherche de l’inférence régulière . . . . . . . . . . . . . . . . . . . . 132
4 L’inférence régulière sans échantillon négatif . . . . . . . . . . . . . . . . . . . . 134
5 L’inférence régulière sous contrôle d’un échantillon négatif . . . . . . . . . . . . 139
6 L’inférence d’automates probabilistes . . . . . . . . . . . . . . . . . . . . . . . . . 142
7 L’inférence de transducteurs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145
8 L’inférence d’automate fini avec oracle . . . . . . . . . . . . . . . . . . . . . . . . 147

5 La programmation logique inductive 153

1 La programmation logique inductive : le cadre général . . . . . . . . . . . . . . . 157
2 Logique des prédicats et programmes logiques : terminologie . . . . . . . . . . . . 163
3 La structuration des hypothèses en logique des prédicats . . . . . . . . . . . . . . 167
4 L’exploration de l’espace des hypothèses . . . . . . . . . . . . . . . . . . . . . . . 174
5 Deux exemples de systèmes de PLI . . . . . . . . . . . . . . . . . . . . . . . . . . 179
6 La probabilisation de la PLI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183
7 Un exemple d’application de la PLI . . . . . . . . . . . . . . . . . . . . . . . . . . 183
8 Les chantiers de la PLI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185

6 La recherche de motifs dans les données 191

1 La fouille de données pour redécrire le monde . . . . . . . . . . . . . . . . . . . . 193
2 La recherche de motifs fréquents . . . . . . . . . . . . . . . . . . . . . . . . . . . 195
3 Les règles d’association . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 200
4 Autres problèmes en fouille de données . . . . . . . . . . . . . . . . . . . . . . . . 202

7 Apprentissage et théorie du domaine 213

1 Apprentissage par examen de preuve (EBL) et apprentissage de structure . . . . 215
2 Abstraction et reformulation des connaissances . . . . . . . . . . . . . . . . . . . 222
3 Apprentissage et raisonnement . . . . . . . . . . . . . . . . . . . . . . . . . . . . 224
4 Apprentissage de liens de causalité . . . . . . . . . . . . . . . . . . . . . . . . . . 225
5 Apprentissage de sorties structurées . . . . . . . . . . . . . . . . . . . . . . . . . 232
6 L’apprentissage multi-instance . . . . . . . . . . . . . . . . . . . . . . . . . . . . 235

III L’induction par optimisation d’un critère inductif 237

8 L’apprentissage de modèles linéaires 239

1 Régression linéaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 241
2 Séparatrices linéaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 246
3 Modèles linéaires par morceaux et combinaisons de modèles locaux . . . . . . . . 260
4 La recherche des facteurs pertinents . . . . . . . . . . . . . . . . . . . . . . . . . 263

9 L’apprentissage de réseaux connexionnistes 269

1 Pourquoi vouloir dépasser les modèles linéaires . . . . . . . . . . . . . . . . . . . 272
2 Les différents éléments d’un réseau connexionniste . . . . . . . . . . . . . . . . . 274
3 L’architecture multicouche . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 275
4 L’algorithme d’apprentissage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 282
5 Quelques résultats théoriques sur les réseaux connexionnistes . . . . . . . . . . . 291

[Link] 6 16/03/2018 11:49

 Table des matières v

6 Comment choisir l’architecture d’un réseau ? . . . . . . . . . . . . . . . . . . . . . 292

7 Les réseaux à architecture profonde . . . . . . . . . . . . . . . . . . . . . . . . . . 293
8 Réseaux et régime dynamique : le Reservoir Computing . . . . . . . . . . . . . . 294

10 Apprentissage profond 301

1 Des réseaux aux réseaux profonds . . . . . . . . . . . . . . . . . . . . . . . . . . . 303
2 Réseaux convolutifs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 305
3 Réseaux récurrents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 327
4 Generative Adversarial Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . 334
5 Bilan et perspectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 337

IV L’induction par comparaison à des exemples (et par collaboration) 339

11 Apprentissage par similarité 341

1 La notion de distance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 343
2 Mesure de similarité dans des espaces non vectoriels . . . . . . . . . . . . . . . . 345
3 L’algorithme des plus proches voisins . . . . . . . . . . . . . . . . . . . . . . . . . 355
4 Raisonnement à partir de cas (RàPC) . . . . . . . . . . . . . . . . . . . . . . . . 356
5 L’apprentissage pour faire des recommandations . . . . . . . . . . . . . . . . . . 358

12 Méthodes à noyaux 371

1 Trois voies vers les méthodes à noyaux . . . . . . . . . . . . . . . . . . . . . . . . 373
2 Philosophie des méthodes à noyaux . . . . . . . . . . . . . . . . . . . . . . . . . . 384
3 Les Séparatrices à Vastes Marges (SVM) . . . . . . . . . . . . . . . . . . . . . . . 385
4 Autres types d’induction avec fonctions noyaux . . . . . . . . . . . . . . . . . . . 396
5 Ingénierie des fonctions noyaux . . . . . . . . . . . . . . . . . . . . . . . . . . . . 401
6 Les méthodes à noyaux en pratique . . . . . . . . . . . . . . . . . . . . . . . . . . 421
7 Bilan et perspectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 426

13 Apprentissage par combinaison d’experts 431

1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 433
2 Diviser et combiner : apprentissage d’arbres de décision . . . . . . . . . . . . . . 442
3 Méthodes d’ensemble en apprentissage supervisé . . . . . . . . . . . . . . . . . . 459

V L’apprentissage descriptif 471

14 Apprentissages non supervisés 473

1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 475
2 Les méthodes de classification fondées sur les distances . . . . . . . . . . . . . . . 476
3 Modèles probabilistes : les mélanges de gaussiennes . . . . . . . . . . . . . . . . . 489
4 Méthodes spectrales de catégorisation . . . . . . . . . . . . . . . . . . . . . . . . 491
5 La classification de données symboliques . . . . . . . . . . . . . . . . . . . . . . . 492
6 L’évaluation et la validation de l’apprentissage non supervisé . . . . . . . . . . . 495

15 Les changements de représentation 501

1 La sélection des attributs de description . . . . . . . . . . . . . . . . . . . . . . . 503
2 Les analyses en composantes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 512

[Link] 7 16/03/2018 11:49

 vi Table des matières

3 L’acquisition comprimée (Compressive sensing) . . . . . . . . . . . . . . . . . . . 519

4 L’apprentissage de dictionnaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . 525
5 La représentation vectorielle de mots (word embedding) . . . . . . . . . . . . . . 527

16 L’apprentissage bayésien et son approximation 531

1 L’apprentissage bayésien . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 534
2 Les méthodes paramétriques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 544
3 Les méthodes non paramétriques . . . . . . . . . . . . . . . . . . . . . . . . . . . 553
4 Les méthodes semi-paramétriques . . . . . . . . . . . . . . . . . . . . . . . . . . . 568

17 L’apprentissage de réseaux bayésiens 573

1 Les modèles graphiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 575
2 Les réseaux d’inférence bayésiens . . . . . . . . . . . . . . . . . . . . . . . . . . . 577
3 Les inférences dans les réseaux bayésiens . . . . . . . . . . . . . . . . . . . . . . . 585
4 L’apprentissage des réseaux bayésiens . . . . . . . . . . . . . . . . . . . . . . . . 589
5 L’inférence de relations causales . . . . . . . . . . . . . . . . . . . . . . . . . . . . 598
6 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 599
7 Quelques logiciels . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 600

18 L’apprentissage de modèles de Markov cachés 603

1 Les modèles de Markov observables . . . . . . . . . . . . . . . . . . . . . . . . . . 606
2 Les modèles de Markov cachés (HMM) . . . . . . . . . . . . . . . . . . . . . . . . 607
3 Les Hmm comme règles de classification de séquences . . . . . . . . . . . . . . . . 612
4 L’évaluation de la probabilité d’observation . . . . . . . . . . . . . . . . . . . . . 613
5 Le calcul du chemin optimal : l’algorithme de Viterbi . . . . . . . . . . . . . . . . 616
6 L’apprentissage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 618
7 Approfondissements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 624
8 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 624

VI Apprentissage en environnement non stationnaire 627

19 L’apprentissage de réflexes par renforcement 629

1 Description du problème . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 632
2 Si tout est connu : l’utilité de la fonction d’utilité . . . . . . . . . . . . . . . . . . 637
3 L’apprentissage des fonctions d’utilité quand l’environnement est connu . . . . . 637
4 Sans modèle du monde : la méthode de Monte-Carlo . . . . . . . . . . . . . . . . 643
5 Évaluation de politique par la méthode des différences temporelles . . . . . . . . 644
6 Amélioration de politique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 646
7 La résolution du compromis exploration contre exploitation . . . . . . . . . . . . 649
8 La généralisation dans l’apprentissage par renforcement . . . . . . . . . . . . . . 656
9 Le cas des environnements partiellement observables . . . . . . . . . . . . . . . . 660
10 Exemples d’application . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 661
11 Bilan et perspectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 667

20 Nouveaux scénarios : apprentissages actif, en ligne et par transfert 671

1 L’apprentissage actif . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 673
2 L’apprentissage en ligne . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 682
3 Apprentissage à partir de flux de données . . . . . . . . . . . . . . . . . . . . . . 697

[Link] 8 16/03/2018 11:49

 Table des matières vii

4 Changement de repère et raisonnement par analogie . . . . . . . . . . . . . . . . 702

5 Apprentissage et transfert . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 703

VII Aspects pratiques et suppléments 707

21 L’apprentissage semi-supervisé 709

1 Présentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 711
2 Les modèles génératifs : apprentissage dans l’espace joint X × Y . . . . . . . . . 714
3 L’auto-apprentissage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 718
4 Le co-apprentissage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 718
5 L’utilisation d’hypothèses a priori sur les données . . . . . . . . . . . . . . . . . . 720
6 Quelques directions pour l’apprentissage semi-supervisé . . . . . . . . . . . . . . 730
7 Conclusion et petite discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 731

22 Analyse de l’induction : approfondissements et ouvertures 733

1 Généralisation de l’analyse du principe MRE . . . . . . . . . . . . . . . . . . . . 734
2 Principes inductifs contrôlant l’espace des hypothèses . . . . . . . . . . . . . . . . 740
3 Prise en compte de l’algorithme d’apprentissage dans la théorie . . . . . . . . . . 752
4 Autres types d’analyses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 759

23 Aspects pratiques de l’apprentissage 767

1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 770
2 L’espace des données d’apprentissage . . . . . . . . . . . . . . . . . . . . . . . . . 775
3 L’évaluation de l’apprentissage . . . . . . . . . . . . . . . . . . . . . . . . . . . . 790
4 La comparaison des méthodes d’apprentissage . . . . . . . . . . . . . . . . . . . . 801
5 Autres problèmes pratiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 806
6 Outils logiciels disponibles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 810
7 Un mot sur les formations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 813

VIII Annexes techniques 817

24 Annexes techniques 819

1 Le calcul de l’intervalle de confiance pour l’estimation de la probabilité d’une règle
de classification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 819
2 Estimation d’une densité de probabilité en un point . . . . . . . . . . . . . . . . 820
3 Pourquoi et comment la règle du PPV converge-t-elle ? . . . . . . . . . . . . . . . 821
4 Pourquoi la règle de décision bayésienne est-elle optimale ? . . . . . . . . . . . . . 822
5 Apprentissage par estimation-maximisation . . . . . . . . . . . . . . . . . . . . . 823
6 Optimisation par descente de gradient . . . . . . . . . . . . . . . . . . . . . . . . 827
7 La rétropropagation du gradient de l’erreur . . . . . . . . . . . . . . . . . . . . . 830
8 L’analyse de l’induction de Vapnik . . . . . . . . . . . . . . . . . . . . . . . . . . 834
9 L’induction par compression d’information . . . . . . . . . . . . . . . . . . . . . . 844

Bibliographie 851

Index 891

[Link] 9 16/03/2018 11:49

[Link] 10 16/03/2018 11:49
 Notations

#... Nombre de . . .

P Une probabilité
p Une densité de probabilités
E[x] L’espérance de la variable x

IN L’ensemble des entiers naturels

IRd L’espace euclidien de dimension d
Bd = {0, 1}d L’espace booléen de dimension d
O(·)   L’ordre de grandeur maximal de complexité d’un algorithme
x1
x =  ...  Un vecteur
 

xd

x> = (x1 , . . . , xd ) Un vecteur transposé

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

M−1 La matrice inverse d’une matrice carrée M

M> La matrice transposée d’une matrice M
M+ La matrice pseudo-inverse d’une matrice M .
Par définition, M+ = M> (MM> )−1
∆(x, y) La distance euclidienne entre deux vecteurs x et y de IRd

∂x f (x, y) La dérivée partielle par rapport à x

∂

de la fonction f des deux variables x et y

∇A J(A, B) Le vecteur dérivé par rapport au vecteur A

de la fonctionnelle J des deux vecteurs A et B

[Link] 11 16/03/2018 11:49

 x

Les éléments en jeu dans l’apprentissage

X L’espace de représentation des objets (des formes)

Y L’espace de sortie

A Un algorithme d’apprentissage

S L’échantillon d’apprentissage (un ensemble ou une suite d’exemples)

S+ Les exemples positifs
S− Les exemples négatifs
m La taille d’un échantillon d’apprentissage (le nombre d’exemples)
zi = (xi , yi ) Un exemple (élément d’un échantillon d’apprentissage)
xi La description d’un objet dans un espace de représentation

Les principes de l’apprentissage inductif

yi ∈ Y La supervision, ou sortie désirée, d’un exemple

f :X →Y La fonction cible (celle que l’on cherche à apprendre)

H L’espace des hypothèses d’apprentissage

h∈H Une hypothèse produite par un apprenant (un algorithme d’apprentissage)
y = h(x) ∈ Y La prédiction faite par l’hypothèse h sur la description x d’un exemple
`(f (x), h(x)) La fonction perte (ou coût) entre la fonction cible et une hypothèse sur x
RRéel (h) Le risque réel associéé à l’hypothèse h
REmp (h) Le risque empirique associé à l’hypothèse h
RReg (h) Le risque empirique régularisé associé à l’hypothèse h
R? Le risque (optimal) de la règle de décision de Bayes

h? L’hypothèse de H qui minimise le risque réel

h?S L’hypothèse de H qui minimise le risque empirique (régularisé) sur S
ĥ?S L’hypothèse trouvée par l’algorithme d’apprentissage ayant S en entrée
et cherchant h?S dans H

L’apprentissage d’une règle de classification

C L’ensemble des classes

C Le nombre de classes
ωi Une classe de C

La logique

a∧b a ET b, quand a et b sont des valeurs binaires

a∨b a OU b
¬a N ON a
a→b a implique b

[Link] 12 16/03/2018 11:49

 Première partie

Des machines apprenantes !

[Link] 13 16/03/2018 11:49

[Link] 14 16/03/2018 11:49
 Chapitre 1
Des algorithmes qui apprennent ?

Où l’on se demandera si des machines peuvent apprendre. Où l’on verra que l’in-
duction est au cœur de l’apprentissage et qu’elle n’est pas facile à dompter. Il faudra
alors parler d’hypothèses et même d’espaces d’hypothèses que la machine explore
lorsqu’elle apprend. Il faudra donc se demander comment elle peut évaluer les hypo-
thèses, comment elle peut sélectionner les hypothèses qu’elle souhaite retenir, et si
l’on peut avoir la moindre garantie sur la qualité de ces hypothèses sélectionnées.
Les approches et les méthodes d’apprentissage sont en grande partie déterminées
par la nature des hypothèses considérées. Ce chapitre examinera donc les grandes
familles d’hypothèses et d’espaces d’hypothèses. Mais l’apprentissage est un processus
dynamique qui se déroule selon un scénario réglant les échanges entre l’apprenant et
son environnement. Les grands scénarios étudiés actuellement seront donc présentés.
Revenant à la question du début : les machines peuvent-elles apprendre ? Il sera
temps de brosser un bref historique de la discipline de l’apprentissage artificiel et de
voir comment la question a évolué et comment on y a répondu depuis plus d’un demi-
siècle. Nous terminerons en examinant quelques questions souvent posées lorsque l’on
parle de machines apprenantes.

[Link] 15 16/03/2018 11:49

 4

Sommaire
1 La révolution numérique en cours et le « big data » . . . . . . . . . 5
1.1 Le « big data » . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.2 Une nouvelle ère scientifique s’ouvre . . . . . . . . . . . . . . . . . . 8
1.3 Une matière première et de nouvelles opportunités . . . . . . . . . . 8
1.4 Les risques et les défis . . . . . . . . . . . . . . . . . . . . . . . . . 10
2 Apprentissage et induction . . . . . . . . . . . . . . . . . . . . . . . 10
3 Des apprentissages différents . . . . . . . . . . . . . . . . . . . . . . 13
4 Les notions d’espace d’hypothèses et de critère inductif . . . . . . . 15
4.1 L’induction : un jeu entre un espace d’exemples et un espace d’hypothèses 16
4.1.1 L’apprentissage est impossible. . . . . . . . . . . . . . . . . 17
4.1.2 . . . sans limiter l’espace des hypothèses . . . . . . . . . . . 18
4.2 L’exploration de l’espace des hypothèses . . . . . . . . . . . . . . . . 21
5 Les ingrédients de l’apprentissage . . . . . . . . . . . . . . . . . . . 23
6 Les méthodes paramétriques et non paramétriques, et les autres . 24
7 L’espace des hypothèses d’apprentissage . . . . . . . . . . . . . . . . 25
7.1 Le problème général de la représentation des connaissances . . . . . . 25
7.2 La classification . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
7.2.1 Classe, concept . . . . . . . . . . . . . . . . . . . . . . . . 27
7.2.2 Les fonctions séparatrices entre classes . . . . . . . . . . . . 27
7.3 La régression . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
7.4 Les distributions de probabilités . . . . . . . . . . . . . . . . . . . . 29
7.5 Les arbres de décision . . . . . . . . . . . . . . . . . . . . . . . . . 29
7.6 Les hiérarchies de concepts . . . . . . . . . . . . . . . . . . . . . . 30
7.7 Les réseaux bayésiens et les modèles graphiques . . . . . . . . . . . . 30
7.8 Les chaînes de Markov et les modèles de Markov cachés . . . . . . . 31
7.9 Les grammaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
7.10 Les formalismes logiques . . . . . . . . . . . . . . . . . . . . . . . . 33
7.11 Les règles d’association . . . . . . . . . . . . . . . . . . . . . . . . 34
8 Les protocoles d’apprentissage . . . . . . . . . . . . . . . . . . . . . 35
8.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
8.2 Batch vs. en ligne . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
8.3 Passif vs. actif . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
9 Une brève mise en perspective historique . . . . . . . . . . . . . . . 36
10 Des questions que tout le monde se pose . . . . . . . . . . . . . . . 39

D
es algorithmes qui apprennent ! ? Cette idée si révolutionnaire, si provocante
tellement la notion de machine est associée à celle de fonctionnement laborieux, ré-
pétitif et ne pouvant échapper à une procédure soigneusement prédéfinie, est pour-
tant devenue complètement familière et banale. Est-elle pour autant comprise ? Les
médias nous parlent pratiquement tous les jours de « big data », d’« apprentissage profond », de

[Link] 16 16/03/2018 11:49

 Chapitre 1 Des algorithmes qui apprennent ? 5

« réseaux de neurones », de « véhicules autonomes », comme s’il s’agissait là simplement d’une

nouvelle génération de produits high-tech – on est bien loin de la conquête de la Lune – mais c’est
aussitôt, dans la foulée, pour s’extasier et pour distiller l’inquiétude. Plus du tiers des métiers
seraient réalisés par des machines « intelligentes » mieux que par des humains d’ici 20301 , déjà
les jeux réputés les plus difficiles, tels le go ou le poker, ou des jeux de type Atari, voient les ma-
chines l’emporter devant les meilleurs joueurs humains et inventer des coups « extra-terrestres ».
Demain, que restera-t-il à l’homme ? La créativité ? Le sens de l’humour ? Une perception et une
cognition de type « gesthalt » qui nous donnerait une compréhension de l’univers totalisante,
panthéique, qui échapperait à jamais à la machine ? On veut se rassurer, mais les discours s’ap-
puient pour la plupart sur du sable, c’est-à-dire sur une grande méconnaissance de la science
des machines apprenantes.
Des algorithmes qui apprennent ! Cette potentialité était évidente dès les travaux de Turing
inventant en 1936 la machine qui porte son nom. Si une machine suit aveuglément les instruc-
tions qui lui sont fournies sur un (très long) ruban et si cette machine est capable lors de son
fonctionnement, en fonction de son expérience dans le monde, de modifier ce qui est inscrit sur
ce ruban, alors la machine peut s’adapter, elle peut modifier ses réponses au monde, elle peut
apprendre. Dès lors, pourquoi ne pourrait-elle pas être créative ? Pourquoi ne pourrait-elle pas
avoir son propre destin ? Le fantasme de « la machine » contre l’homme surgit, et, posé en ces
termes, effraie.
De fait, si les progrès en apprentissage artificiel, et plus généralement en intelligence artificielle,
sont indéniables et impressionnants, il n’en reste pas moins que nous sommes encore loin de
réaliser des systèmes présentant même une toute petite partie des capacités cognitives d’un
bébé interagissant avec le monde et apprenant comment l’« utiliser ».
Dans cet ouvrage, nous n’allons pas chercher directement à extrapoler l’avenir possible des
machines « intelligentes » et envisager comment l’humanité peut apprendre elle-même à pro-
gresser grâce à elles. À toute petite échelle, il est intéressant et révélateur de regarder comment
la théorie du jeu de go et les pratiques des joueurs sont en train d’évoluer très rapidement
depuis que le système AlphaGo a prouvé son expertise dans ce jeu. Pour une réflexion à plus
grande échelle sur l’impact possible des machines intelligentes, les ouvrages suivants peuvent
faire réfléchir [AB16, Bos14, Dev17, Fer16, Gan17, Mal17, Teg17].

1. La révolution numérique en cours et le « big data »

Une révolution est en cours2 . Elle présente trois aspects concomitants : (i) une production
de données en croissance exponentielle, certains la qualifiant d’avalanche de données pour la
qualifier, (ii) la disponibilité partout et tout le temps de ressources de calcul, depuis les objets
connectés et smartphones jusqu’aux gros clusters de calcul et au « cloud computing », et (iii) la
mise au point et la diffusion de nouveaux algorithmes de science des données, de simulation, de
modélisation, de raisonnement automatique et d’aide à la décision.
Il n’est pas de semaine sans qu’une innovation liée à ces nouvelles données, aux nouveaux
moyens de calcul disponibles et nouveaux algorithmes, ne soit annoncée haut et fort dans la
presse. C’est ainsi que la revue Science, en août 2016, rapporte que l’on peut désormais détec-

1
Selon un étude récente de la firme de consultance PwC.
2
Cette section est en partie tirée de [Cor15a].

[Link] 17 16/03/2018 11:49

 6 PARTIE 1 : Des machines apprenantes !

ter les zones de pauvreté en Afrique, mieux et beaucoup moins cher qu’avec des experts sur le
terrain, grâce aux données satellitaires et à des algorithmes d’apprentissage automatique. La
Harvard Business Review de août-septembre 2016 décrit une nouvelle application qui permet de
détecter les restaurants à haut risque d’intoxication alimentaire par l’examen automatique des
avis des consommateurs, avec un très faible taux d’erreur, et ceci donc beaucoup plus rapide-
ment et beaucoup moins cher qu’en employant des inspecteurs. L’université de Harvard faisait
l’été 2016 la promotion des données ouvertes récoltées dans sa forêt, d’une superficie de 1600 ha.
L’Université souhaitait stimuler ainsi les recherches écologiques (millions de mesures en accès
libre) [Le Monde, 24/08/2016]. La génomique et les sciences en « omique » n’existeraient pas
sans la possibilité d’analyser de manière automatique les données produites en grande quantité
dans les laboratoires. La sociologie devient une science expérimentale à grande échelle grâce à
l’analyse désormais possible des réseaux sociaux. La climatologie et les sciences de l’environ-
nement reposent sur la récolte de données à grande échelle et leur traitement par des moyens
puissants de simulation et de modélisation. La médecine va demain connaître une révolution
avec l’arrivée massive d’objets connectés et la mise au point de systèmes experts. L’agriculture
aussi devient connectée et va faire un appel croissant aux technologies et méthodes du numérique
pour à la fois être capable de nourrir bientôt 9 milliards d’êtres humains, respecter et favoriser
la biodiversité et s’adapter au changement climatique. De plus, la confiance des citoyens de-
vrait s’améliorer grâce à la traçabilité accrue, plus transparente et quasiment en temps réel des
productions et des chaînes logistiques d’approvisionnement et de distribution.
Incroyablement, alors que la production de données est devenue phénoménale et qu’elle se
fait bien souvent en réaction de plus en plus rapide à d’autres données, une grande partie de
cette « écume numérique du monde » est stockée, ce qui ouvre des possibilités complètement
nouvelles d’analyse et provoque un débat entre droit à l’oubli et droit à l’histoire.

1.1 Le « big data »

Il faut bien comprendre que les technologies et approches classiques de gestion et de traitement
de données ne sont plus à même de nous permettre de faire face au « Big data » et ses nouvelles
caractéristiques. Il est ainsi devenu classique de mettre en avant au moins quatre problèmes avec
les défis qui les accompagnent :
1. Le volume. Comme nous l’avons vu, ce volume explose. Le mégaoctet a longtemps été
l’unité de mesure de la taille des mémoires des ordinateurs, puis le gigaoctet a témoigné
de l’arrivée de la numérisation de l’image animée, le téraoctet (1012 octets) désigne la puis-
sance de stockage désormais accessible à chacun d’entre nous, permettant en théorie de
conserver l’équivalent de fonds de grandes bibliothèques nationales. Le petaoctet (1015 oc-
tets) correspond aux masses d’informations entreposées dans les « fermes de données », et
l’exaoctet (1018 octets) est tutoyé dans certains domaines (physique des particules, astrono-
mie). Le stade de fichiers Excel que chacun pouvait examiner sur son ordinateur personnel
est complètement dépassé. On dit souvent que le « Big data » commence quand on ne
peut plus stocker les données concernées dans la mémoire centrale de son ordinateur, et
donc qu’il faut recourir à des traitements sophistiqués pour rendre les calculs réalisables,
c’est-à-dire faisables en un temps raisonnable.
2. La vélocité. Les données modernes sont maintenant produites en flux. Elles incluent les
millions de tweets échangés chaque heure, les centaines d’heures de média déposées sur
YouTube chaque minute, les données communiquées et produites par nos smartphones, les
séquences de clics et de transactions enregistrées sur les sites web, etc. Même les images
satellitaires de télé-détection vont maintenant être disponibles toutes les cinq heures pour

[Link] 18 16/03/2018 11:49

 Chapitre 1 Des algorithmes qui apprennent ? 7

chaque zone géographique au lieu d’une fois tous les 2 mois (cf. la mise en place du réseau
de satellites Sentinelles par l’Europe, sans compter les micro-satellites que des start-up
américaines envoient désormais par dizaines dans l’espace). Il faut donc être capable de
traiter une grande partie de ces données « à la volée ». De plus la « fraîcheur » des données
devient un critère qu’il devient important de prendre en compte.
3. La variété. Les données ne sont plus issues de processus bien définis de recueil dans un
format établi, mais elles sont désormais stockées au mieux dans des entrepôts de données,
au pire dans des fichiers d’origines diverses, avec des formats variés, impliquant possible-
ment des données multimédias audio et vidéo, du texte brut ou dans des formats plus ou
moins propriétaires, des transactions financières, des méta-données, etc. La question de la
mise en relation de tous ces types de données très hétérogènes devient ainsi cruciale.
4. La véracité. Les données étant issues de capteurs ou de sources humaines très diverses,
leur degré de précision et surtout de fidélité ainsi que le niveau de confiance qu’on peut leur
accorder sont très variés. Il faut donc savoir combiner les sources et raisonner en tenant
compte de ces indices de précision, des biais éventuellement connus ou identifiés et du
niveau de confiance.

Cette disponibilité quasi infinie de données et les nouvelles possibilités de traitements massifs
désormais accessibles à bas prix, grâce en particulier au « cloud computing », bouleversent
l’approche scientifique du monde.
Avant, la démarche était de réfléchir à une question, par exemple l’existence ou non d’une
corrélation entre deux variables (voire entre quelques variables peu nombreuses), d’établir avec
soin un « plan d’expériences », de récolter l’échantillon de données aussi limité et aussi propre que
possible pour satisfaire les contraintes de significativité statistique, et de mesurer la corrélation
faisant l’objet de notre attention, avant de conclure à son existence ou pas, par exemple en
comparant à une p-value.
Désormais, la démarche est de demander aux machines de découvrir toutes les corrélations
multi-variables existantes dans un énorme volume de données souvent bruitées et, seulement
ensuite, d’examiner ce qui peut présenter un intérêt dans cette masse de liens potentiels. De
manière alternative, on peut demander aux machines de détecter ce qui émerge comme étant la
norme et, à partir de là, d’identifier des « signaux faibles », c’est-à-dire des phénomènes étranges,
hors norme, qu’il peut être intéressant d’examiner.
De même, avant, on était centré sur l’ajustement des modèles statistiques aux données (pré-
dire le passé), on cherche maintenant des capacités prédictives par la généralisation et l’extra-
polation des régularités découvertes.
De plus, les corrélations ainsi découvertes peuvent à leur tour servir d’entrées pour d’autres
mécanismes de « data mining », participant ainsi à un processus d’enrichissement (ou de pollu-
tion) cumulatif et potentiellement exponentiel.
Il est en tous les cas essentiel de bien réaliser que d’un questionnement orienté et raisonné, on
passe avec le « Big data » à une exploration tous azimuts de corrélations ou de signaux faibles ou
de tendances, pour ensuite les filtrer, les recouper et alimenter l’univers numérique. Il n’y a plus
en pratique de question de taille d’échantillon et, de plus, les données ne servent plus seulement
à répondre à une question pour laquelle elles ont été récoltées, mais elles sont ré-utilisables à
l’infini en fonction de nouveaux traitements que n’importe quel « data scientist » qui en dispose
peut imaginer.

[Link] 19 16/03/2018 11:49

 8 PARTIE 1 : Des machines apprenantes !

1.2 Une nouvelle ère scientifique s’ouvre

À côté de ces caractérisations techniques, un autre regard sur le « Big data » fait ressortir la
nouvelle ère scientifique ouverte grâce à lui. Un découpage en quatre grandes ères scientifiques
et en quatre approches est ainsi formulé :
1. Approche empirique. Elle correspondrait à une première étape de la démarche scientifique
qui consiste à répertorier et à classer les objets, êtres vivants et phénomènes naturels.
2. Approche théorique. Inaugurée magistralement par Galilée et Newton, elle est associée à la
modélisation du monde et à sa mise en équations. Cependant, elle trouve des limites dans
son application car toutes les équations, tant s’en faut, n’ont pas de solutions analytiques.
3. Approche par la simulation. Heureusement, l’informatique, apparue dans les années 1940,
a offert le moyen de résoudre numériquement les équations et modèles mathématiques
du monde, et d’en étendre ainsi le champ bien au-delà des systèmes assez simples et
simplifiés de la physique du xixe siècle. Ainsi, ces simulations numériques ont permis à la
physique quantique, la physique des solides et la relativité générale de faire des prédictions
vérifiables. Elles contribuent aussi de manière essentielle au développement des sciences
du vivant et de l’environnement et, généralement, des sciences des systèmes complexes
naturels ou artificiels.
4. Approche par exploration des données. Finalement, nous serions entrés dans l’ère de nou-
velles découvertes rendues possibles par l’exploitation des énormes masses de données
acquises sur le monde grâce à toutes les nouvelles technologies du « Big data ».
Il est indéniable que des champs scientifiques tels que la sociologie ou les sciences de l’envi-
ronnement sont en profonde mutation grâce au « Big data ». De même, dans des domaines plus
« traditionnels » tel celui de la physique des particules, les nouvelles découvertes (ex. boson de
Higgs) seraient impossibles sans la capacité à traiter des données hyper-massives.

1.3 Une matière première et de nouvelles opportunités

Personne sans doute n’est encore capable de prédire avec précision quelles seront les appli-
cations du « Big data » et les (r)évolutions à en attendre. Très généralement, les possibilités
suivantes, qui sont neuves, font miroiter tout un ensemble de nouvelles opportunités :
1. Nouvelles possibilités pour comprendre le monde. La science s’appuie désormais autant
sur l’analyse de données que sur la modélisation mathématique ou la simulation. Certaines
sciences connaissent grâce au « Big data » des développements considérables : la géno-
mique, la climatologie, la physique des particules, l’astronomie. D’autres sont carrément
bouleversées, comme les sciences humaines et la sociologie qui deviennent des sciences
quantitatives grâce à l’analyse des réseaux sociaux et de l’usage massif des Smartphones
et autres objets connectés (voir aussi les villes intelligentes basées sur des mesures massives
de comportement : exemple le projet Living Lab à Trente en Italie). On parle désormais de
« physique sociale ». La médecine se renouvelle profondément grâce aux nouvelles possibili-
tés d’analyse du génome (voir par exemple l’entreprise 23andMe qui offre des services basés
sur l’analyse du génome de ses clients) et aux outils du « quantified self » en particulier
par l’usage de montres connectées, etc. On peut aussi mentionner le « crowd computing »
qui permet de faire appel au public, via des interfaces et des réseaux dédiés, pour aider
à résoudre des questions scientifiques ou autres : par exemple, étudier des configurations
de protéines, ou bien déchiffrer pour une numérisation ultérieure des manuscrits écrits en
vieux français. Finalement, le fait que chacun puisse a priori facilement poser des questions

[Link] 20 16/03/2018 11:49

 Chapitre 1 Des algorithmes qui apprennent ? 9

très variées via l’analyse des données rendues publiques ou de ses propres données ouvre
la perspective de découvertes et de services inattendus.
2. De nouvelles possibilités d’optimiser le fonctionnement de la société. On parle ainsi
de « villes intelligentes ». Les réseaux de transport pourront être reconfigurés en temps
réel pour répondre aux mesures sur les flux de personnes, la distribution de l’énergie et
les heures de consommation seront optimisées grâce aux compteurs « Linky » intelligents
et à des mesures en temps réel de la météo. La sécurité des lieux publics et privés sera de
même révolutionnée par la disponibilité de données multi-sources : caméras de surveillance,
objets connectés portés par les individus, traces d’ADN que l’on peut désormais détecter
dans l’atmosphère d’une pièce plusieurs jours après le départ de ses occupants.
3. Le développement de panoplies de services très ciblés, individualisés, par exemple
pour une médecine personnalisée, des conseils de consommation (livres, films...) et la vie en
général (ex. comment optimiser son sommeil en fonction des évènements de la journée et de
l’agenda du lendemain). Ces mêmes technologies permettent aussi la mise aux enchères en
quelques micro-secondes d’espaces publicitaires à introduire dans les pages qui s’affichent
durant les recherches internet d’un utilisateur. Généralement, le marketing va devenir une
science avec en particulier une mesure de l’impact en temps réel des messages, et un suivi
très fin des comportements, dans les magasins ou sur les sites marchands.
4. L’open data, c’est-à-dire l’accès libre et gratuit aux données, en particulier gouvernemen-
tales et des collectivités locales, avec l’espoir d’une démocratie participative et directe.

Pour prendre l’exemple des sciences du vivant et de l’environnement, on peut attendre des
impacts importants sur plusieurs secteurs. Ainsi :
• Les sciences de l’environnement vont bénéficier de la possibilité d’intégrer et de combiner des
données de capteurs très variés, très multi-échelles (des satellites aux drones et aux capteurs
dans les tracteurs et dans les champs) et avec suivi des évolutions. De fait, le changement
climatique ne serait peut-être pas encore perçu, et en tous les cas ne serait pas apprécié
pleinement, sans une capacité d’analyse multi-source et à grande échelle de données.
• La logistique et les chaînes de distribution, en particulier les chaînes d’approvisionnement en
produits frais, vont voir leur fonctionnement très optimisé, avec à la clé beaucoup moins de
déchets et des dates de péremption beaucoup plus précises attachées à chaque produit par
l’analyse de son « histoire » grâce à l’arrivée des multi-capteurs sur les produits eux-mêmes.
• L’agriculture se prépare également à une révolution. Pour donner un exemple, John Deere et
AGCO ont ainsi entrepris de relier les machines agricoles entre elles, mais aussi les systèmes
d’irrigation, des mesures sur les sols et sur les intrants, via éventuellement des drones,
tout cela en plus d’informations relatives à la météo locale à court et moyen terme et de
données sur les cours de bourse des produits récoltés et des matières premières, le tout afin
d’optimiser les performances d’une exploitation agricole dans son ensemble.

Ce tour d’horizon extrêmement rapide et nullement exhaustif souligne l’importance et le large

spectre des mutations attendues. Il est clair que l’on est en train d’assister à un transfert massif
de pouvoir des acteurs économiques qui maîtrisent les techniques et les procédés de fabrication
ou de services vers ceux qui maîtrisent l’information, c’est-à-dire qui détiennent les données et
savent en tirer des régularités exploitables et des prédictions. C’est pourquoi, pour essayer de
comprendre l’avenir, tant d’analystes se focalisent sur les GAFA (Google, Amazon, Facebook
et Apple) et leurs stratégies, c’est-à-dire sur ces entreprises (et d’autres) très jeunes qui ont
détrôné les acteurs traditionnels en récoltant énormément de données sur les utilisateurs, leurs

[Link] 21 16/03/2018 11:49

 10 PARTIE 1 : Des machines apprenantes !

machines, leurs comportements, et peuvent ainsi devenir les vrais donneurs d’ordre reléguant les
autres entreprises à de la sous-traitance.
Bien sûr, ce nouvel Eldorado annoncé s’accompagne de risques.

1.4 Les risques et les défis

Les risques concernent en premier lieu la vie politique. En vrac :
• Risque de surveillance généralisée, détaillée, en temps réel et à une échelle planétaire.
• Tentation de prédiction de comportements « déviants » avant le passage à l’acte.
• Croisement illégal et illicite de données.
• Cycles de décision raccourcis à l’extrême, en raison en particulier de l’utilisation de systèmes
de décision automatiques, au détriment du temps de la réflexion et de la consultation.
• Cacophonie sur la décision politique si des experts auto-proclamés de l’analyse de données
affirment n’importe quoi et s’appuient sur une pseudo objectivité pour dicter des sentences
et des ordonnances.
• Découverte de corrélations stupides par manque de recul et de réflexion, mais avec le sceau
de l’objectivité de « l’algorithme ».
• Recul de la solidarité par segmentation ultrafine des usagers. C’est certainement l’une des
tentations dans le domaine de l’assurance, qui va tendre à privilégier des offres hyper-
segmentées en fonction du profil mesuré des clients au détriment de la mutualisation des
risques.
Les défis technologies sont liés aux quatre « V » évoqués dans l’introduction : Volume, Vé-
locité, Variété, Véracité. De ces quatre V, les deux premiers sont les plus exigeants en termes
d’infrastructures. Il faut des capacités de stockage, d’interrogation et de visualisation des don-
nées performantes. De même, il faut être capable de traiter de gros volumes de données, ce qui
peut impliquer de manière routinière du swapping en mémoire centrale, le recours à des clusters
de calcul ou à du cloud computing. Certaines applications sur des flux de données demandent un
traitement « à la volée » qui impose ses propres contraintes, en particulier sur les systèmes de
requêtes et sur les traitements possibles. Les défis sont d’ordre techniques, mais ils sont surtout
humains, nous y reviendrons dans le chapitre 23.
Nous avons mis en perspective l’importance de la science des données dans la révolution
numérique qui bouleverse nos sociétés. Il est temps d’examiner les fondamentaux de cette science,
et, avant tout, le rôle de l’induction.

2. Apprentissage et induction

L’apprentissage s’appuie sur des observations ou sur des expériences pour produire des pré-
dictions, des règles de décision, des modèles du monde et pour améliorer les performances du
système au cours du temps. L’apprentissage est fondamentalement lié à l’induction, c’est-à-dire
au passage de l’observation de cas particuliers à des lois générales.
L’induction est partout présente dans nos processus cognitifs, simplement parce que nous
n’avons presque jamais toute l’information nécessaire pour prendre des décisions certaines. Il
nous faut pourtant agir, souvent rapidement, nous construire des images mentales du monde,
et même pouvoir communiquer en utilisant ces images avec d’autres agents, d’autres humains,

[Link] 22 16/03/2018 11:49

 Chapitre 1 Des algorithmes qui apprennent ? 11

dont les sources d’information et les capacités cognitives sont tout aussi faillibles que les nôtres.
L’induction, ce chateau de cartes fragile qui ne peut pas, selon David Hume en 1737, avoir de
bases solides, est mis en jeu à toutes les échelles de la cognition et, au bout du compte, cela ne
se passe pas si mal pour tous les êtres cognitifs. Il y a là un mystère.

(a) (b) (c)

Fig. 1.1 : Exemples de perceptions avec complétion de forme par induction. En (a), on ne
peut s’empêcher de voir un carré au milieu de l’ensemble de points. En (b), on perçoit
immédiatement une sphère, alors que de fait, nous sommes en présence d’une figure plane.
En (c), nous « voyons » un triangle blanc superposé à un triangle dessiné, lui-même
incomplet.

Reprenons. Dès nos perceptions, nous réalisons de l’induction de manière massive. Les figures
1.1 et 1.2 font prendre conscience de ce que notre système perceptif prête ou ajoute à ce qui est
donné pour former une interprétation du monde.

Fig. 1.2 : Exemples de perceptions avec interprétation par induction. Ici, deux perceptions sont
à peu près également possibles pour chacune des figures (visage de jeune femme ou trom-
pettiste, à gauche, visage de jeune femme de trois quart arrière ou visage de vieille femme
de profil à droite).

Les inductions sont faillibles et nos perceptions, basées sur des inductions, le sont également.
Il n’y a pas de miracle. La figure 1.3 révèle ce que l’on appelle des illusions d’optique, qui ne
sont autres que le résultat de ce qu’ajoute notre système visuel aux percepts pour interpréter le
monde. Ce qui est remarquable, c’est que ce « biais » est commun à tous les êtres humains, ou
au moins à tous ceux qui sont familiers des milieux à formes géométriques. Sans biais, nous ne
serions pas victimes de ces illusions d’optique, mais nous serions aussi incapables de percevoir
tout court, c’est-à-dire de compléter les données sensorielles.

[Link] 23 16/03/2018 11:49

 12 PARTIE 1 : Des machines apprenantes !

(a) (b)

Fig. 1.3 : Illusions d’optique. En (a), malgré les apparences, les trois silhouettes ont la même
taille. En (b), les lignes sont parallèles.

Si nos perceptions mettent en jeu l’induction, il en est de même de l’apprentissage de caté-

gories. Nous sommes tous d’accord pour désigner par la catégorie « chien » une forme à quatre
pattes (encore n’en voyons-nous que trois) approchant de nous, plus petite que nous qui aboie
et remue la queue. Pourtant aucun de nous n’a vu tous les chiens, et encore moins celui-ci que
nous découvrons au cours d’une promenade dans une région inconnue. Depuis notre enfance,
nous avons vu chacun des exemples particuliers de ces formes et l’on nous a dit qu’il s’agissait
de la catégorie « chien ». Comment pouvons-nous maintenant reconnaître une nouvelle forme,
jamais vue, comme étant membre de cette catégorie ? Et comment pouvons-nous être d’accord
entre nous malgré nos histoires différentes ?

Fig. 1.4 : Tâche de clustering. On demande à la machine d’identifier des nuages de points
distincts dans l’ensemble des points de la figure de gauche. Pourquoi le clustering réalisé à
droite, avec trois nuages, bleu, rouge et vert, serait-il le bon ?

Ce que nous faisons sans en avoir trop conscience, qui marche souvent bien mais qui est
faillible, c’est ce que nous allons demander à la machine. À elle aussi vont être présentées des
« entrées » incomplètes, particulières, et il va falloir qu’elle en tire des interprétations, des
modèles du monde, des règles de décision. Par exemple, dans la tâche dite de clustering, on
demande à la machine d’identifier des sous-populations à l’intérieur d’un ensemble d’exemples.
La figure 1.4 en fournit une illustration simple. Ici, des points sont décrits dans un espace à
deux dimensions x1 et x2 , et l’on demande à la machine d’identifier des sous-ensembles, prenant
la forme de « nuages » de points. Ici, la machine a identifié trois sous-populations, mais elle
aurait pu en identifier deux ou quatre. Quelle est la meilleure réponse ? Et pourquoi ? Y a-t-il

[Link] 24 16/03/2018 11:49

 Chapitre 1 Des algorithmes qui apprennent ? 13

une réponse à ces deux questions ? C’est ce que nous allons explorer dans cet ouvrage.
Considérons un dernier exemple illustré par la figure 1.5 (à gauche). Prenons à nouveau des
formes décrites par deux attributs, x1 et x2 , mais auxquelles on a également associé une étiquette,
ici des × ou des •. Une nouvelle forme arrive, d’étiquette inconnue (sur la figure 1.5, le carré
associé à un point d’interrogation). Il faut décider quelle étiquette lui attribuer. Comment faire ?
Des biais différents conduisent à des réponses différentes. Trois des quatre plus proches voisins
sont d’étiquette •, qu’il faudrait donc choisir, mais si on dessine un rectangle (noté h pour
« hypothèse ») englobant tous les points × et excluant tous les points − (voir figure 1.5 à
droite), celui-ci englobe le point d’étiquette inconnue et il faudrait donc décider +. Sur quelle
base décider ? Quel est le bon biais ? À nouveau, peut-on répondre à cette question ?

x2 x2

⇥ ⇥ ? ⇥ ⇥ ?
⇥ ⇥
⇥ ⇥
⇥ ⇥⇥ ⇥⇥⇥ ⇥ ⇥⇥ ⇥⇥⇥
⇥ ⇥ h⇥ ⇥ ⇥
⇥

x1 x1

Fig. 1.5 : Tâche de prédiction. (À gauche) On observe des exemples décrits par les attributs x1
et x2 . Ils sont associés à l’étiquette × ou à l’étiquette •. Quelle étiquette associer au carré
accompagné d’un point d’interrogation ? (À droite) Si l’on choisit l’hypothèse correspondant
au rectangle, tous les points intérieurs sont alors étiquetés × et le point d’étiquette inconnue
doit aussi l’être.

Dans son ouvrage Probably Approximately Correct. Nature’s algorithms for learning and pros-
pering in a complex world (2013), Leslie Valiant, pionnier d’une théorie de l’apprentissage, écrit :
« From this, we have to conclude that generalization or induction is a pervasive
phenomenon (. . . ). It is as routine and reproducible a phenomenon as objects falling
under gravity. It is reasonable to expect a quantitative scientific explanation of this
highly reproducible phenomenon . »
Peut-on dire que nous disposons finalement d’une telle théorie de l’induction et de la compré-
hension que nous souhaitons aller avec ? Et donc d’une théorie de l’apprentissage ?
Non. Il reste à faire pour les jeunes scientifiques, mais nous avons progressé.

3. Des apprentissages différents

Disons d’emblée que nous ne disposons pas à l’heure actuelle de machines capables de réaliser
tout le spectre des apprentissages dont nous, humains, sommes capables. Apprentissages que
nous intégrons les uns aux autres, qui nous permettent de comparer un coup appris au tennis

[Link] 25 16/03/2018 11:49

 14 PARTIE 1 : Des machines apprenantes !

avec une réponse à une situation politique et qui prennent place tout au long de la vie. Nos
machines sont encore spécialisées et il est utile de distinguer plusieurs types d’apprentissages.
Nous commençons ici par trois grandes catégories, mais nous en verrons bien d’autres dans la
suite de l’ouvrage.
L’apprentissage descriptif
L’un des grands buts de l’apprentissage est de « comprendre les données ». Cela signifie
identifier des régularités qui permettent d’un certain côté de comprimer l’information pré-
sente dans les données et de les décrire de manière synthétique. Un système pourrait ainsi
distinguer plusieurs catégories de consommateurs dans une base de données rassemblant
des informations sur les clients d’une entreprise, catégories qu’un expert pourrait interpré-
ter comme les clients de tel groupe socio-professionnel, ou les clients « early adopters »,
catégories qui pourront ensuite être ciblées par des campagnes de marketing différentes.
Dans l’apprentissage descriptif pur, le but n’est pas d’extrapoler à des données futures
possibles (ex. à des clients potentiels), mais bien de décrire les données disponibles, si
possible en y découvrant des structures inattendues et intéressantes.
Comme nous l’avons esquissé plus haut, des biais différents peuvent conduire un système à
mettre en évidence des régularités différentes et l’un des gros problèmes de l’apprentissage
descriptif est de savoir comment évaluer le résultat de l’apprentissage et comment guider
le choix d’un bon biais.
L’apprentissage descriptif est souvent aussi décrit comme apprentissage non supervisé (Un-
supervised learning) car il n’y a pas de professeur qui aide le système à savoir quoi trouver.
Cela contraste avec l’apprentissage prédictif.
L’apprentissage prédictif
L’apprentissage prédictif pourrait aussi être appelé apprentissage amplificatif. Le but cette
fois-ci est d’utiliser les données disponibles pour identifier des règles de décision permettant
de prédire quelque chose à propos de données futures, encore inconnues au moment de
l’apprentissage. Ce « quelque chose » peut prendre des formes variées. Dans le cas le
plus simple, il s’agit d’une variable, que l’on appelle souvent étiquette associée à l’entrée,
c’est-à-dire à la description de la donnée.
Par exemple, un système de diagnostic médical peut apprendre à reconnaître la maladie
d’un nouveau patient, à partir d’une base de données décrivant des malades pour lesquels
un diagnostic a été fait. Ce système va ainsi devoir apprendre un moyen d’associer à une
description (ici de chaque patient) que nous noterons x une prédiction (ici une pathologie)
que nous noterons y.
Il est plus simple d’évaluer la qualité de l’apprentissage réalisé dans les systèmes de pré-
diction. Il suffit de garder par devers soi un ensemble de données pour lesquelles l’étiquette
est connue et de mesurer à quel point la règle de décision apprise permet de bien prédire
ces étiquettes quand l’entrée x est fournie. Bien sûr, il faut prendre un certain nombre de
précautions et connaître les techniques d’évaluation de performance appropriées à chaque
situation spécifique. Elles seront décrites au moment opportun dans l’ouvrage, mais spé-
cialement dans le chapitre 23.
On parle souvent d’apprentissage supervisé (supervised learning) pour dénoter l’apprentis-
sage prédictif. En effet, on suppose qu’un professeur (un superviseur) a associé à chaque
exemple xi une étiquette yi dans la base de données servant à l’apprentissage.
L’apprentissage prescriptif
Le plus souvent, l’objectif ultime de l’apprentissage n’est pas seulement de savoir mieux dé-
crire les données, ou d’avoir identifié des règles de prédiction, mais de savoir que faire pour

[Link] 26 16/03/2018 11:49

 Chapitre 1 Des algorithmes qui apprennent ? 15

changer le monde. Or il ne suffit pas pour cela de connaître des corrélations prédictives.
Par exemple, supposons que je sois un fabricant de glaces et que je veuille augmenter mes
ventes. L’apprentissage prédictif peut m’avoir fourni une règle du type « si une personne
est en maillot de bain, alors il est probable qu’elle mange une glace ». Suffit-il alors de
demander aux gens de se mettre en maillot de bain pour qu’ils se mettent à consommer
des glaces ? Il est clair que cette règle prédictive n’est pas adéquate pour savoir quelle
action mettre en œuvre. Fondamentalement, corrélation n’égale pas causalité. Les gens ne
mangent pas des glaces parce qu’ils sont en maillot de bain, mais parce qu’un troisième
facteur, la chaleur, et la proximité de la mer ou d’une piscine, cause à la fois le fait de se
mettre en maillot de bain et de consommer des glaces. C’est seulement en découvrant cette
relation de causalité qu’une action efficace peut être déclenchée, par exemple installer un
magasin dans les régions chaudes.
L’apprentissage prescriptif demande donc que d’autres types de relations soient découverts
dans le monde et notamment des relations de causalité.

4. Les notions d’espace d’hypothèses et de critère inductif

Que ce soit pour identifier des régularités dans les données (apprentissage descriptif) ou pour
découvrir des règles de décision (apprentissage prédictif), il est utile de disposer d’un langage
permettant de décrire ou de désigner ces régularités ou ces règles de décision. En apprentissage
artificiel, on parle d’hypothèses et on parle d’espace d’hypothèses pour désigner l’ensemble des
hypothèses qui peuvent être considérées dans un problème d’apprentissage.
Chaque hypothèse peut être décrite en utilisant un langage, par exemple la logique du 1er ordre
(ex. ∀x, si possède(x, 4 pattes) et aboie(x) alors x est un chien), ou bien par un algorithme qui
retourne une valeur.
Dans ce cadre, l’apprentissage peut être vu comme la recherche d’une hypothèse permettant
de bien décrire les données, ou de bien prédire les étiquettes associées aux exemples. Il faut donc
savoir associer à chaque hypothèse une mesure d’adéquation aux données et de pertinence. C’est
ce que le critère inductif est chargé de faire.
Le critère inductif est une fonction qui associe à chaque couple (hypothèse, données d’ap-
prentissage) une valeur réelle évaluant la qualité de l’hypothèse h par rapport aux données
d’apprentissage que nous noterons Sm (S pour « sample », échantillon, de taille m). Nous note-
rons cette fonction Rreg (pour des raisons que nous verrons plus loin).

Rreg (h, Sm ) 7→ IR

Une fois fournis le critère inductif Rreg , un espace d’hypothèses H et un échantillon d’ap-
prentissage Sm , l’apprentissage peut être considéré comme un problème d’optimisation visant à
trouver une fonction h∗S ∈ H qui optimise Rreg (h, Sm ) (souvent on cherche à réduire un écart
entre h et Sm , d’où un problème de minimisation) :

h∗S = Argmin Rreg (h, Sm ) (1.1)

h∈H

[Link] 27 16/03/2018 11:49

 16 PARTIE 1 : Des machines apprenantes !

L’algorithme d’apprentissage devient une procédure d’exploration de H visant à cher-

cher h∗ , ou, au moins, à trouver une hypothèse qui soit bonne vis-à-vis de Rreg (h, Sm ). On
notera ĥ l’hypothèse retournée par l’algorithme d’apprentissage.

Selon la structure dont on pourra/saura doter l’espace des hypothèses H, on pourra inventer
des algorithmes d’apprentissage, donc d’exploration de H, plus ou moins efficaces.

4.1 L’induction : un jeu entre un espace d’exemples et un espace d’hypothèses

Dans le but de simplifier toute la discussion qui suit, nous nous focalisons dans cette section
sur l’apprentissage supervisé de concept, c’est-à-dire sur l’apprentissage de fonctions indicatrices
ou encore à valeur dans {0, 1}. Les notions abordées seront cependant d’une portée beaucoup
plus générale et valables pour l’essentiel dans toutes les situations d’apprentissage.
L’apprentissage supervisé de concept consiste à chercher une fonction f : X → {0, 1}, c’est-
à-dire un étiquetage de chaque forme x ∈ X par 0 (x n’appartient pas au concept visé) ou 1
(x appartient au concept)3 . Cette fonction est apprise à partir d’un échantillon de points éti-
quetés que l’on appelle échantillon d’apprentissage. Nous noterons4 :

S = h(x1 , y1 ), (x2 , y2 ), ..., (xm , ym )i

un échantillon d’apprentissage de m points non nécessairement tous distincts (lorsqu’il sera

important de préciser la taille de l’échantillon d’apprentissage, nous le noterons Sm ). Pour des
raisons évidentes, on appelle souvent exemples ou exemples positifs les points étiquetés par 1
ou par ‘+’, et contre-exemples ou exemples négatifs les points étiquetés par 0 ou par ‘−’. Il
arrivera cependant dans la suite de l’ouvrage que nous parlions d’exemples pour dénoter les
points étiquetés, qu’ils le soient positivement (exemples au sens propre) ou négativement (contre-
exemples). La figure 1.6 schématise la tâche d’apprentissage de concepts.

- -
- -
+
-
- - + + -
+ + +
+
+ -
+ +
- - -

- -
- X

Fig. 1.6 : À partir d’un échantillon de points étiquetés, ici figurés par des ‘+’ et des ‘−’, l’ap-
prenant cherche une partition de X permettant de discriminer les formes x appartenant
au concept de celles ne lui appartenant pas.
3
Ces deux classes sont aussi notées {+, −}.
4
Il arrivera également que nous notions S = {(x1 , y1 ), (x2 , y2 ), ..., (xm , ym )} l’échantillon d’apprentissage
quand la répétition des exemples n’est pas prise en compte par l’algorithme (ce qui est le cas par exemple de
l’algorithme de l’espace des versions – chapitre 3. Nous verrons également des cas dans lesquels les exemples sont
associés à un poids non entier (cas du boosting par exemple, au chapitre 13).

[Link] 28 16/03/2018 11:49

 Chapitre 1 Des algorithmes qui apprennent ? 17

Nous supposons maintenant, d’une part que l’échantillon d’apprentissage n’est pas bruité,
c’est-à-dire que les exemples sont correctement décrits et étiquetés, d’autre part que la même
forme n’est pas à la fois exemple et contre-exemple, plus généralement qu’elle n’est pas associée
à deux étiquettes différentes incompatibles.
Dans ce cadre, l’échantillon d’apprentissage S = h(x1 , y1 ), (x2 , y2 ), ..., (xm , ym )i fournit une
information cohérente à l’apprenant dans la mesure où la partie de X qu’il cherche doit couvrir
tous les exemples positifs de l’échantillon (ce que l’on appelle la propriété de complétude) et ne
couvrir aucun des exemples négatifs (ce que l’on appelle la propriété de correction).
Dans ce cadre restreint, on peut maintenant poser deux questions :
• Quelle est l’information fournie par chaque exemple ?
• Comment, sur la base de l’échantillon d’apprentissage, choisir une hypothèse c’est-à-dire,
dans le cas de l’estimation d’une fonction indicatrice, une partition de X ?

4.1.1 L’apprentissage est impossible. . .

Dans le cadre de l’induction de concept, donc d’une fonction indicatrice définie sur X , l’espace
des entrées, l’apprentissage revient à chercher une partition de l’espace X . En effet, il s’agit
d’identifier les régions de X , donc les formes x, correspondant au concept visé (voir figure 1.6).
Que peut nous apprendre un échantillon d’exemples S sur cette partition ?
Supposons que l’apprenant soit prêt à considérer toutes les partitions possibles de X , donc
que n’importe quel étiquetage des formes x ∈ X soit possible a priori. Cela signifie que si le
cardinal de X , noté |X |, est fini, il existe 2|X | partitions possibles de X .
Supposons alors que nous cherchions à déterminer la classe d’un point x ∈ X inconnu connais-
sant la classe de tous les points d’apprentissage xi ∈ X . Comment procéder ?
Puisque nous manipulons des partitions de X , nous pourrions considérer toutes les partitions
cohérentes avec l’échantillon d’apprentissage, puis décider alors de la classe de x en fonction de
ces dernières. Si toutes les partitions cohérentes avec l’échantillon S prescrivent que x appartient
au concept, ou au contraire n’y appartient pas, cela déterminera notre décision pour la classe
de x. Supposons même que toutes ces partitions ne soient pas d’accord sur la classe de x, nous
pourrions encore décider que celle-ci est la classe majoritairement attribuée.
Malheureusement, aucun de ces deux cas de figure ne se présente. Il se trouve que si l’on prend
toutes les partitions cohérentes avec n’importe quel ensemble de points d’apprentissage S (c’est-
à-dire prédisant correctement l’étiquette de chacun de ces points), et si l’on prend n’importe quel
point x 6∈ S, alors il existe autant de partitions prédisant l’étiquette 1 pour x que de partitions
prédisant l’étiquette 0. L’échantillon d’apprentissage à lui tout seul ne fournit donc pas une base
suffisante pour décider de la classe d’un point nouveau. L’induction, c’est-à-dire l’extrapolation
du connu à l’inconnu est impossible. Seul un apprentissage par cœur est réalisable.
Les deux questions soulignées dans la section précédente ont donc reçu une réponse qui jette
pour le moins une ombre sur la possibilité de l’induction. Aucun exemple d’apprentissage ne
fournit d’information au-delà de cet exemple lui-même. Toutes les partitions de l’espace X
cohérentes avec l’échantillon sont également probables et leurs prédictions s’annulent en chaque
point inconnu. L’aventure de l’apprentissage artificiel tournerait-elle court ?

Exemple Apprentissage de fonction boolénne (1)

Soit un ensemble X de points décrits par n attributs binaires. Chaque partition de X corres-
pond à un étiquetage particulier des 2n points de X . Il existe donc 22 partitions différentes
n

de X ou encore 22 fonctions indicatrices définies de X sur {0,1}.

n

[Link] 29 16/03/2018 11:49

 18 PARTIE 1 : Des machines apprenantes !

Supposons que l’échantillon d’apprentissage comporte m exemples distincts. Le nombre de

partitions de X compatibles avec ces m exemples est : 22 −m puisque m points sur les 2n
n

sont fixés.
Prenons le cas de n = 10 attributs binaires et de m = 512 exemples d’apprentissage. Le
cardinal de X est |X | = 210 , soit 1024 points différents, ce qui n’est pas un espace très
grand. Il existe 21024 manières différentes de les étiqueter par 1 ou 0. Après l’observation de
la moitié de ces 1024 points, il reste 21024−512 partitions possibles, soit 2512 . On voit que ces
512 exemples laissent un ensemble considérable de partitions possibles.

x1 x2 x3 f (x)
0 0 0 +
0 0 1 −
0 1 0 +
0 1 1 ?
1 0 0 +
1 0 1 ?
1 1 0 ?
1 1 1 −

Fig. 1.7 : Soit f une fonction binaire définie sur un espace d’entrée à trois attributs. La table
fournit un échantillon de 5 exemples de cette fonction.

Étudions un problème plus simple dans lequel les exemples sont décrits par trois attributs
binaires. Cela fait 23 = 8 formes possibles. Supposons que cinq exemples parmi ces huit
aient été étiquetés par l’oracle, comme le montre la figure 1.7. Pour fixer complètement une
fonction, il faut déterminer la valeur des trois dernières formes. Il faut donc faire un choix
entre 23 = 8 fonctions. Supposons que nous voulions déterminer la valeur associée à l’entrée
(0 1 1). Il y a quatre fonctions parmi les huit qui sont associées à la sortie + et quatre
associées à la sortie -. Il est donc impossible d’avoir même seulement une préférence pour
une prédiction plutôt qu’une autre concernant l’étiquette de ce point.

Nous nous sommes placés dans le cas où l’apprenant cherche directement une partition de
l’espace d’entrée X , c’est-à-dire qu’il cherche à déterminer l’étiquette de chaque forme x ∈ X .
C’est évidemment impossible, sauf dans le cas d’espaces X très restreints pour lesquels un
apprentissage par cœur est envisageable. En d’autres termes, il est généralement impossible
d’apprendre une partition de X en extension, c’est-à-dire en énumérant toutes les formes et leur
étiquette associée.

4.1.2 . . . sans limiter l’espace des hypothèses

C’est pourquoi on utilise généralement pour décrire des partitions de X un langage de des-
cription des hypothèses, que nous noterons LH . Il permet de définir un espace d’expressions ou
d’hypothèses H, par exemple l’espace des hypothèses décrites par une conjonction de conditions
sur les descripteurs5 .
Ainsi, dans l’exemple décrit précédement, on pourrait décrire des fonctions binaires du type
(x1 = 0) ∧ (x2 = 1) ∧ (x3 = 1). En revanche, ce langage interdit de considérer une fonction telle
que (x1 = 0 ∧ x2 = 1 ∧ x3 = 1) ∨ (x1 = 0 ∨ x2 = 0 ∧ x3 = 0).
5
Il s’agit du langage CNF (Conjunctive Normal Form), dans lequel les hypothèses prennent la forme de
conjonctions de disjonctions, par exemple : (x1 = 0 ∨ x7 = 1) ∧ (x3 = 1 ∨ x5 = 1 ∨ x8 = 0) ∧ x4 = 1.

[Link] 30 16/03/2018 11:49

 Chapitre 1 Des algorithmes qui apprennent ? 19

?
- -
+ - -
- xh
- - + + -
+ +
+ +
+
+ - +
- - -

- -
- X H

Fig. 1.8 : Rôle d’un espace d’hypothèses H dans le cas de l’apprentissage de concept. Chaque
point de H, ou encore hypothèse, correspond à une partition de l’espace des entrées X .

Lorsqu’un espace d’hypothèses H est disponible, la recherche d’une partition de X s’effectue

par l’intermédiaire de H. Il s’agit de chercher dans H, une hypothèse h correspondant à une
partition de X appropriée (voir figure 1.8).
Les avantages de l’utilisation explicite d’un espace d’hypothèses sont multiples :
1. D’abord, grâce au langage LH , l’apprenant manipule des partitions de X en intension et
non plus en extension. Il travaille sur des expressions du langage LH et non pas sur des
ensembles définis par l’énumération de leurs éléments.
2. Ensuite, et c’est un point capital d’après la discussion de la section précédente, il devient
possible d’effectuer une induction à partir d’un échantillon limité d’exemples. Il suffit pour
cela que LH ne permette pas de décrire toutes les partitions de X .
Voyons pourquoi.
Nous allons d’abord le montrer en reprenant l’exemple précédent.

Exemple Apprentissage de fonction boolénne (2)

Supposons que, pour une raison quelconque, l’apprenant qui reçoit des entrées décrites
sur les trois descripteurs binaires x1 , x2 , x3 ne puisse prendre en compte en fait que le
premier et le troisième descripteurs, c’est-à-dire x1 et x3 , pour décider de l’étiquette
de la forme reçue. Cela revient à dire que le nombre de fonctions que l’apprenant peut
considérer est de 4 (22 ) au lieu des 8 (23 ) possibles lorsque l’on prend en compte les
trois descripteurs.
Cela signifie en particulier que, si l’échantillon d’apprentissage contient les exemples
(000) → − et (010) → +, l’apprenant ne pourra pas construire une hypothèse, c’est-à-
dire une fonction, qui permette d’en rendre compte.
En revanche, cette fois-ci l’échantillon d’apprentissage fourni dans la table donnée pré-
cédemment lui permet de faire une prédiction pour le point (0 1 1). En effet, la seule
fonction à valeur sur x1 , x3 cohérente avec les exemples d’apprentissage est la fonction
dont le tableau est le suivant :
x1 x3 f (x)
0 0 +
0 1 −
1 0 +
1 1 −

Et selon cette fonction, l’étiquette de la forme (0 1 1) est ‘−’.

[Link] 31 16/03/2018 11:49