Ce qu'un sommaire de manuel d'apprentissage automatique dit du domaine

Foundations of Machine Learning (deuxième édition, MIT Press, 2018), de Mehryar Mohri, Afshin Rostamizadeh et Ameet Talwalkar, définit l'apprentissage comme l'usage de l'expérience pour faire des prédictions exactes, et bâtit un cursus rigoureux autour de la complexité d'échantillon, des bornes de Rademacher et des garanties théoriques.

La plupart des livres sur l'apprentissage automatique commencent par une promesse sur ce que vous saurez construire. Celui-ci commence par une définition et par la liste des grandeurs qui déterminent si un apprenant réussit. Cet ordre dit ce que les auteurs pensent de leur sujet, et je crois que c'est le bon choix. Un domaine qui se vend sur la prédiction doit à ses lecteurs d'expliquer quand la prédiction est digne de confiance, et c'est précisément ce que le livre entreprend.

Cet article lit le livre à travers ce que disent réellement ses pages liminaires, sa préface et ses premières pages. L'exercice est plus étroit qu'une recension de chaque chapitre, et il reconnaît ses limites : les sources sont ici la page de titre, la table des matières, la préface et le début de l'introduction. Dans ces limites, l'argument est clair. Il porte sur ce qu'est l'apprentissage automatique, sur ce dont il dépend, sur ce que les auteurs ont choisi de traiter et sur ce qu'ils ont choisi d'écarter.

Un livre à la généalogie précise #

Commençons par les faits qui ancrent l'objet. Le livre s'intitule Foundations of Machine Learning, et il s'agit de la deuxième édition. Il appartient à la collection Adaptive Computation and Machine Learning, dirigée par Francis Bach. Les auteurs sont Mehryar Mohri, Afshin Rostamizadeh et Ameet Talwalkar. L'éditeur est The MIT Press, à Cambridge, dans le Massachusetts, et le droit d'auteur appartient au Massachusetts Institute of Technology, avec la date de 2018. L'édition reliée porte l'ISBN 9780262039406.

Deux détails de fabrication méritent chacun une phrase. Le livre a été composé en LaTeX par les auteurs eux-mêmes, ce qui convient à un texte dense en bornes, en définitions et en démonstrations, et il a été imprimé et relié aux États-Unis. Aucun de ces détails ne change la façon de lire les mathématiques. Mais des auteurs qui composent eux-mêmes leur livre ont eu chaque page entre les mains, et dans un ouvrage de ce genre, c'est rassurant.

L'origine du contenu compte davantage. L'essentiel provient d'un cours de troisième cycle, lui aussi intitulé Foundations of Machine Learning, que le premier auteur donne au Courant Institute of Mathematical Sciences de l'université de New York depuis quatorze ans. C'est une provenance précise et vérifiable. Un manuel né de quatorze années d'enseignement d'un même cours a vraisemblablement été façonné par ce que les étudiants trouvaient difficile, et les exercices et annexes décrits plus bas donnent cette impression. Je me garderais de pousser l'inférence plus loin que la source ne le permet. La préface dit d'où vient le contenu, mais elle ne dit pas combien de révisions le cours a connues ni ce qui a donné du fil à retordre aux étudiants. Ce qu'elle dit suffit : il s'agit d'un matériau de cours, pas d'une synthèse assemblée à partir de la littérature.

La définition qui porte tout l'édifice #

Tout ce qui suit dépend d'une seule phrase. L'apprentissage automatique, écrivent les auteurs, peut se définir largement comme l'ensemble des méthodes computationnelles qui utilisent l'expérience pour améliorer leurs performances ou pour faire des prédictions exactes.

Chaque nom de cette phrase a un rôle. « Méthodes computationnelles » place le sujet dans l'informatique. « Expérience » est ensuite précisé : le mot désigne les informations passées dont dispose l'apprenant. La phrase ne prétend pas que l'apprenant comprenne quoi que ce soit, et elle ne dit rien de l'intelligence. Un apprenant dispose d'informations passées et d'un objectif, une meilleure performance ou une prédiction exacte, et toute la discipline porte sur la relation entre les deux.

Je soutiens que cette définition est plus utile aux lecteurs techniques et aux fondateurs que les définitions plus grandioses qui circulent, car elle désigne directement les leviers que vous maîtrisez. Si l'apprentissage est fonction des informations passées, alors votre prise sur le résultat tient aux informations que vous collectez et à leur quantité. L'affirmation suivante du texte le dit expressément : la qualité et la taille des données sont déterminantes pour la réussite des prédictions de l'apprenant. Le texte présente cette affirmation comme un mécanisme simple, sans la moindre réserve.

Les auteurs décrivent aussi les techniques elles-mêmes. Ce sont des méthodes guidées par les données, qui combinent des concepts fondamentaux de l'informatique avec des idées issues de la statistique, des probabilités et de l'optimisation. Cette phrase sert à la fois de liste de prérequis et de carte des voisins du domaine. Une équipe qui veut construire des systèmes d'apprentissage puise à la fois dans l'informatique, la statistique, les probabilités et l'optimisation. Traiter l'une d'elles comme facultative est un choix que le livre ne cautionne pas.

Un exemple détaillé : des documents et des thèmes #

L'introduction ancre la définition dans un problème d'apprentissage concret. Prenons un échantillon fini de documents choisis au hasard, chacun étiqueté par un thème. La tâche consiste à utiliser cet échantillon pour prédire le thème de documents encore jamais vus.

Le dispositif mérite une lecture lente. L'échantillon est fini, donc l'apprenant ne voit jamais tout. Les documents sont choisis au hasard, et c'est ce qui permet à un échantillon fini de dire quelque chose des documents non vus. Chacun porte une étiquette de thème, donc l'apprenant est supervisé. Et la cible, ce sont des documents qu'il n'a pas vus, ce qui fait toute la différence entre prédire et mémoriser.

Les auteurs dégagent ensuite deux éléments qui rendent la tâche plus facile ou plus difficile. Le premier est la taille : à l'évidence, plus l'échantillon est grand, plus la tâche est facile. Le second est la qualité des étiquettes. La difficulté de la tâche dépend aussi de la qualité des étiquettes attribuées aux documents de l'échantillon, puisqu'elles ne sont pas forcément toutes correctes, et du nombre de thèmes possibles.

Cette phrase contient trois curseurs distincts. La taille de l'échantillon en est un. L'exactitude des étiquettes en est un autre. Le nombre de thèmes possibles est le troisième. Aucun ne concerne l'algorithme. Ce sont tous des propriétés du problème et des données, et ils décident de la difficulté du problème avant même le choix d'une méthode. Pour un fondateur qui décide où dépenser son budget, l'observation est pertinente. Si vous pouvez améliorer les étiquettes ou agrandir l'échantillon, vous agissez sur les facteurs que les auteurs désignent expressément comme déterminant la difficulté.

L'exemple nomme aussi sa propre tâche. Prédire l'étiquette d'un document s'appelle aussi la classification de documents, et les auteurs s'empressent d'ajouter que ce n'est nullement la seule tâche d'apprentissage. Cette précaution passe facilement inaperçue. L'exemple des documents n'est qu'un véhicule, et l'affirmation qui le sous-tend est générale.

Trois complexités, et non deux #

C'est ici que le livre fait son geste le plus singulier, et il est facile de le manquer parce qu'il arrive sous la forme d'une brève remarque. L'apprentissage automatique, disent les auteurs, consiste à concevoir des algorithmes de prédiction efficaces et exacts. Comme dans d'autres domaines de l'informatique, la complexité en temps et en espace est une mesure essentielle de la qualité de ces algorithmes. Quiconque a étudié l'algorithmique reconnaîtra ces deux mesures. Combien de temps faut-il, et combien de mémoire ?

Vient alors l'ajout. L'apprentissage automatique a besoin, en plus, d'une notion de complexité d'échantillon pour évaluer la taille d'échantillon dont l'algorithme a besoin pour apprendre une famille de concepts. C'est la mesure qui n'a pas d'équivalent dans une routine de tri. Un algorithme de tri n'a pas besoin qu'on lui dise combien d'exemples il lui faut. Un apprenant, si, car ce qu'il produit est une prédiction sur des cas qu'il n'a pas vus, et la quantité d'expérience derrière cette prédiction fait partie de ce que vous payez.

Je le formulerais ainsi : le temps et l'espace disent ce que coûte l'exécution d'un algorithme, et la complexité d'échantillon dit ce que coûte son apprentissage. Un apprenant rapide mais qui exige un échantillon d'une taille irréaliste n'est efficace dans aucun sens qui compte pour la personne qui collecte les données. Placer la troisième mesure à côté des deux autres, c'est la manière du livre de dire que les données sont une ressource qui a un prix, à budgéter comme le calcul et la mémoire.

Le texte poursuit dans la même direction. Plus généralement, les garanties théoriques d'apprentissage d'un algorithme dépendent de la complexité des classes de concepts considérées et de la taille de l'échantillon d'entraînement. C'est un énoncé compact de ce dont est faite une garantie. Il y a deux entrées, la richesse de la famille de concepts et la quantité de données d'entraînement, et une garantie est un énoncé qui les relie à la performance. Remarquez ce que cela implique pour la structure du livre. Les chapitres suivants doivent fournir des moyens de mesurer la complexité d'une classe de concepts, et la table des matières montre qu'ils le font.

Les auteurs expliquent aussi pourquoi le domaine se situe là où il se situe. Puisque la réussite d'un algorithme d'apprentissage dépend des données utilisées, l'apprentissage automatique est intrinsèquement lié à l'analyse de données et à la statistique. Le mécanisme est énoncé simplement : la réussite dépend des données, donc le sujet est imbriqué avec les disciplines qui étudient les données. C'est, à mes yeux, la phrase la plus honnête de l'introduction. Elle ne présente pas la statistique comme une rivale ni comme une ancêtre. Elle la présente comme une conséquence de ce dont dépend l'apprentissage.

Dimension	Complexité en temps	Complexité en espace	Complexité d'échantillon
Définition opérationnelle	Temps d'exécution asymptotique nécessaire pour produire l'hypothèse $h$	Empreinte mémoire nécessaire pendant l'entraînement et l'évaluation	Nombre d'exemples d'entraînement $m$ nécessaires pour apprendre une famille de concepts
Théorie de référence	Complexité computationnelle (P contre NP, difficulté de l'entraînement)	Contraintes mémoire de l'architecture et localité du cache	Apprentissage PAC, complexité de Rademacher et dimension VC
Conséquence en coût	Calcul serveur et budget d'inférence GPU/CPU	Capacité de RAM et de SRAM sur puce	Coût de collecte, d'annotation et d'étiquetage des données
Rôle théorique	Mesure l'efficacité de l'algorithme en temps d'exécution	Mesure l'efficacité en ressources mémoire	Détermine l'erreur de généralisation et les bornes sur les données non vues

L'ossature théorique #

La préface indique comment le livre est construit. Les trois ou quatre premiers chapitres posent les fondements théoriques de la suite. La table des matières permet de voir de quoi ces fondements sont faits, du moins d'après les titres.

Le premier chapitre de la table s'intitule « The PAC Learning Framework » (le cadre d'apprentissage PAC), et il contient des sections intitulées « Guarantees for finite hypothesis sets - consistent case » et « Guarantees for finite hypothesis sets - inconsistent case », soit les garanties pour les ensembles finis d'hypothèses dans le cas cohérent et dans le cas incohérent. Ces intitulés nous apprennent deux choses. D'abord, le cadre produit des garanties, ce qui rejoint l'insistance de l'introduction. Ensuite, les garanties sont réparties selon que le cas est cohérent ou incohérent, et le livre traite les deux séparément. Je ne spéculerai pas sur le contenu de ces deux cas, car les sources ne donnent ici que les titres des sections. Mais le couple montre que les auteurs ne se contentent pas d'un théorème propre avant de passer à autre chose. Ils accordent au cas le plus difficile et le plus désordonné sa propre section.

Le chapitre suivant de la liste est « Rademacher Complexity and VC-Dimension » (complexité de Rademacher et dimension VC). Ses sections traitent de la complexité de Rademacher, de la fonction de croissance, de la dimension VC et des bornes inférieures. Lu à la lumière de l'introduction, ce chapitre répond naturellement à une question qu'elle soulève. Si les garanties dépendent de la complexité des classes de concepts considérées, il faut des outils pour mesurer cette complexité. La complexité de Rademacher, la fonction de croissance et la dimension VC sont les sections qui portent cette charge. La présence des bornes inférieures dans la liste mérite aussi d'être relevée. Un livre qui ne présente que des bornes supérieures vous dit ce qui est atteignable. Un livre qui inclut les bornes inférieures vous dit aussi ce qui ne l'est pas.

Vient ensuite le chapitre 4, « Model Selection » (sélection de modèles), avec notamment des sections sur la minimisation du risque empirique (ERM) et la minimisation du risque structurel (SRM). Nous y reviendrons à propos de la deuxième édition, car c'est l'un des endroits que la nouvelle édition modifie le plus.

La structure est délibérée. D'abord les fondements, puis l'outillage pour mesurer la complexité, puis la sélection de modèles, et seulement ensuite les algorithmes. C'est une façon défendable d'enseigner, et elle correspond au récit que le livre fait de lui-même : les premiers chapitres posent la théorie, et le reste s'appuie sur elle.

De la théorie aux algorithmes : machines à vecteurs de support et noyaux #

La table des matières nomme aussi les chapitres algorithmiques qui suivent. L'un s'intitule « Support Vector Machines » (machines à vecteurs de support), avec des sections sur le cas séparable et le cas non séparable. Chacune de ces sections traite du problème d'optimisation primal, des vecteurs de support et du problème d'optimisation dual. Un autre s'intitule « Kernel Methods » (méthodes à noyaux).

La forme du chapitre sur les machines à vecteurs de support est elle-même instructive. Les trois mêmes thèmes apparaissent sous les deux intitulés, séparable et non séparable : le problème d'optimisation primal, les vecteurs de support et le problème d'optimisation dual. Cette répétition suggère un traitement parallèle, les mêmes questions posées deux fois sous des hypothèses différentes. Le parallèle fait écho à la séparation entre cas cohérent et incohérent du chapitre PAC, si bien qu'un schéma se dessine à travers le livre : d'abord un cas propre, puis le cas où l'hypothèse propre ne tient plus.

Je me méfierais de trop lire dans une table des matières. Elle peut dire ce que le livre couvre et comment il découpe la matière. Elle ne peut pas dire si une section est bien écrite, et rien dans ces sources ne le dit. Ce qu'elle montre, c'est que le vocabulaire d'optimisation du chapitre sur les machines à vecteurs de support, primal et dual, renvoie à la description que l'introduction fait des techniques, qui combinent l'informatique avec des idées issues de la statistique, des probabilités et de l'optimisation. Le volet optimisation de cette liste apparaît concrètement dans ces intitulés.

Le livre réserve aussi un chapitre distinct à la classification multiclasse, au classement et à la régression. C'est un choix de conception qui se défend. Il aurait été facile de les traiter comme des notes de bas de page de la classification binaire. En donnant à chacun son propre chapitre, les auteurs signalent qu'ils les considèrent comme des problèmes distincts, avec leur propre analyse, ce qui correspond à l'objectif affiché d'une présentation unifiée de plusieurs sujets plutôt que d'une présentation qui privilégie un point de vue.

Ce que le livre choisit de ne pas traiter #

Le passage le plus intéressant de la préface porte sur l'omission. Le livre, disent les auteurs, est une introduction générale à l'apprentissage automatique qui peut servir d'ouvrage de référence aux chercheurs et de manuel aux étudiants. Après cette affirmation large, ils posent une limite : ils ont choisi d'omettre quelques sujets importants, dont les modèles graphiques et les réseaux de neurones.

Peu de manuels le disent aussi franchement, et je soutiens que cette franchise est une force. Un lecteur qui sait d'avance ce qui manque peut s'organiser en conséquence. Celui qui a besoin des réseaux de neurones sait qu'il doit chercher ailleurs, au lieu de découvrir le manque au chapitre neuf.

Les raisons sont données elles aussi. L'omission tient à la fois au souci de concision et au manque actuel de garanties théoriques solides pour certaines méthodes. Deux raisons sont avancées. La concision est une contrainte pratique de tout livre. La seconde raison est celle qui dit quelque chose de la philosophie du livre.

Rattachons-la à l'introduction. Les garanties théoriques d'apprentissage sont ce autour de quoi ce livre est organisé. Elles dépendent de la complexité des classes de concepts et de la taille de l'échantillon d'entraînement, et les chapitres théoriques viennent en premier parce que tout le reste repose sur eux. Une méthode pour laquelle les garanties solides font actuellement défaut trouve mal sa place dans un livre construit ainsi. L'omission découle donc de l'engagement central du livre. Elle est cohérente avec la définition du sujet que les auteurs ont choisi de placer en ouverture.

Une précaution s'impose ici. Le texte dit « certaines méthodes », donc l'affirmation porte sur le manque de garanties solides pour certaines méthodes, pas pour l'ensemble des sujets omis, et il dit « actuel », ce qui rattache le jugement au moment de la rédaction. Je résisterais à la tentation de résumer cela par « les réseaux de neurones n'ont pas de théorie ». Ce n'est pas ce que dit la source. Elle dit que les garanties pour certaines méthodes font actuellement défaut, et que cela, avec le souci de concision, explique l'absence des modèles graphiques et des réseaux de neurones.

Pour les lecteurs techniques qui choisissent quoi étudier, la conséquence pratique est simple. Ce livre vous donne le vocabulaire des garanties, et il vous dit clairement quels domaines il ne couvre pas.

Ce que change la deuxième édition #

La deuxième édition est plus qu'une réimpression corrigée. La préface énumère des ajouts, et chacun indique où les auteurs jugeaient la première édition trop mince.

Le changement phare est un chapitre entier sur la sélection de modèles, le chapitre 4, consacré à un sujet que les auteurs décrivent comme important et qui n'était que brièvement abordé dans l'édition précédente. Le propos est direct. Ils ne prétendent pas que la première édition le traitait bien. Ils disent qu'il n'était que brièvement abordé et qu'ils lui consacrent désormais un chapitre entier. Les sections comprennent la minimisation du risque empirique (ERM) et la minimisation du risque structurel (SRM), comme le montre la table des matières.

Pourquoi la sélection de modèles mérite-t-elle cette promotion ? Les sources ne le disent pas, et je n'inventerai pas de raison à la place des auteurs. Mais l'emplacement est parlant. Le chapitre 4 suit directement les chapitres sur le cadre PAC et sur la complexité de Rademacher et la dimension VC, ce qui le place parmi ce que la préface appelle les trois ou quatre premiers chapitres qui posent les fondements théoriques. Les auteurs n'ont donc pas ajouté la sélection de modèles après coup. Ils l'ont intégrée aux fondements théoriques.

Les ajouts suivants sont un nouveau chapitre sur les modèles d'entropie maximale, le chapitre 12, et un nouveau chapitre sur les modèles d'entropie maximale conditionnelle, le chapitre 13. Deux chapitres entièrement nouveaux représentent une extension substantielle, et le livre consacre désormais deux chapitres consécutifs à cette paire.

Les annexes changent aussi. Les auteurs ont ajouté une section complète sur la dualité de Fenchel à l'annexe B, consacrée à l'optimisation convexe, et ils ont ajouté une annexe E sur la théorie de l'information. Le livre comprend aussi une annexe étendue qui propose une révision concise de l'algèbre linéaire. Ces changements vont dans une même direction : les mathématiques d'appui ont grandi en même temps que les chapitres. La dualité de Fenchel rejoint l'annexe sur l'optimisation convexe, et la théorie de l'information reçoit sa propre annexe. Je me garderais de dire que la théorie de l'information est là précisément pour soutenir les chapitres sur l'entropie maximale, car les sources n'établissent aucun lien de ce genre, et les deux ajouts figurent dans la préface comme des éléments distincts. Qu'ils arrivent dans la même édition est une coïncidence que je laisserai comme telle.

À qui s'adresse le livre, et comment il entend être lu #

Le livre précise son public : il s'adresse aux étudiants et aux chercheurs en apprentissage automatique, en statistique et dans d'autres domaines voisins. Cette liste nomme la statistique, ce qui fait écho à l'idée de l'introduction selon laquelle l'apprentissage automatique est intrinsèquement lié à l'analyse de données et à la statistique.

Il précise aussi ce qu'il suppose acquis. Le lecteur est censé connaître les notions de base de l'algèbre linéaire, des probabilités et de l'analyse des algorithmes. La liste est courte, et elle correspond à la liste des ingrédients de l'introduction, mais pas exactement. L'introduction cite l'informatique, la statistique, les probabilités et l'optimisation comme sources des techniques. Les prérequis citent l'algèbre linéaire, les probabilités et l'analyse des algorithmes. L'optimisation ne figure pas parmi les prérequis, et le livre comble ce point par l'autre bout : l'annexe B traite de l'optimisation convexe, avec la nouvelle section sur la dualité de Fenchel. L'algèbre linéaire est attendue comme bagage, et le livre fournit tout de même l'annexe étendue qui la révise. Les prérequis et les annexes se recouvrent donc à dessein, et un lecteur dont l'algèbre linéaire s'est rouillée trouve une révision concise entre les mêmes couvertures.

La pédagogie est elle aussi exposée simplement. Chaque chapitre se termine par une série d'exercices, dont les solutions complètes sont présentées séparément. C'est une organisation judicieuse pour un livre qui sert deux publics. Un étudiant peut s'essayer aux exercices et vérifier avec les solutions, et un chercheur qui utilise le livre comme référence n'est pas obligé de passer des corrigés à chaque page. La source ne dit pas si les solutions forment un volume séparé ou un autre document, seulement qu'elles sont présentées séparément, et je m'en tiendrai là.

Pris ensemble, le public, les prérequis, les exercices et les annexes décrivent un livre conçu pour être travaillé. Les quatorze années d'enseignement au Courant Institute sont derrière cette conception. Un cours donné de façon répétée tend à produire ce genre d'appareil, même si la préface ne revendique pas explicitement ce lien, et je ne le propose que comme une lecture des éléments, pas comme une constatation.

Les applications sont vastes, et le livre le dit #

Un livre aussi théorique pourrait passer pour éloigné de la pratique. L'introduction prévient ce malentendu par une affirmation simple : l'apprentissage automatique se prête à un très large éventail d'applications pratiques. Celle qu'elle nomme est la classification de textes ou de documents, qui inclut la détection du spam.

La détection du spam est un bon exemple, pour une raison que le cadre même des auteurs explique. C'est un problème de classification de documents exactement au sens de l'exemple précédent : des documents étiquetés en entrée, des prédictions sur des documents non vus en sortie. Les facteurs de taille d'échantillon et de qualité des étiquettes s'y appliquent directement. Un échantillon plus grand facilite la tâche, et des messages mal étiquetés la compliquent. Le nombre de catégories possibles est faible, ce qui, selon la logique du passage précédent, pèse aussi sur la difficulté. J'applique ici les facteurs énoncés par le livre à l'exemple qu'il donne, et je ne prétends rien sur les filtres antispam réels.

Il y a aussi un argument discret dans l'emplacement de ce passage. Les auteurs présentent la classification de documents comme une tâche d'apprentissage, puis notent aussitôt que ce n'est nullement la seule. Les applications sont vastes parce que la définition sous-jacente est vaste. Tout ce qui correspond à « des méthodes computationnelles qui utilisent l'expérience pour améliorer leurs performances ou pour faire des prédictions exactes » entre dans le champ. Cette généralité explique aussi pourquoi le livre s'embarrasse de théorie. Un cadre censé couvrir un très large éventail d'applications ne peut pas dépendre des détails de l'une d'elles, et des garanties formulées en termes de complexité des classes de concepts et de taille d'échantillon sont exactement celles qui se transposent d'un problème à l'autre.

Le pari du livre #

Rassemblons les fils, et une position cohérente apparaît, ce que peu de tables des matières peuvent revendiquer. Le livre définit l'apprentissage par l'expérience et la prédiction. Il nomme trois complexités, en temps, en espace et d'échantillon, comme mesures de la qualité. Il rattache les garanties à la complexité des classes de concepts et à la taille de l'échantillon, et il place en tête la théorie qui fournit ces garanties. Il construit ensuite les chapitres algorithmiques sur cette base et dit ouvertement quels domaines populaires il laisse de côté parce que les garanties de certaines méthodes ne sont pas, pour l'instant, solides.

C'est un pari sur la théorie comme ce qui dure. Je comprends pourquoi des auteurs qui ont passé des années à enseigner un cours de troisième cycle le feraient. Le pari a un coût, et les auteurs le nomment : l'omission des modèles graphiques et des réseaux de neurones est le prix de l'exigence de garanties solides. Un lecteur doit peser ce coût honnêtement. Si votre travail est dominé par les domaines omis, ce livre est un socle plutôt qu'un mode d'emploi. Si votre travail exige de raisonner sur la capacité d'un apprenant à généraliser à partir d'un échantillon fini, le vocabulaire du livre est précisément ce qui compte.

Pour les fondateurs, l'enseignement utile est le moins spectaculaire. La qualité et la taille des données sont déterminantes pour la réussite des prédictions, et la difficulté d'une tâche dépend de la qualité des étiquettes et du nombre de thèmes possibles. Ce sont des affirmations sur des entrées que vous pouvez souvent influencer. Le livre ne promet pas qu'un algorithme particulier sauvera un échantillon maigre ou mal étiqueté, et il a raison de ne pas le faire.

Pour les lecteurs techniques, la question la plus intéressante est celle que la préface laisse ouverte. Les auteurs ont omis certaines méthodes en raison du manque actuel de garanties théoriques solides. Le mot « actuel » présente cela comme un état de fait au moment de la rédaction, et les sources ne disent pas si, ni comment, il pourrait changer. Que faudrait-il pour que ces garanties deviennent assez solides pour mériter un chapitre ? Le livre ne peut pas répondre. Mais en étant précis sur ce qu'il laisse de côté et pourquoi, il montre au moins où chercher.

Ce que cela signifie par secteur #

L'insistance sur les garanties statistiques d'apprentissage et sur la complexité d'échantillon fixe des limites concrètes dans plusieurs domaines du logiciel et de la recherche.

Apprentissage automatique universitaire et conception des cursus #

Les programmes d'enseignement doivent résister à la tentation de traiter l'apprentissage automatique comme de l'ingénierie de prompts empirique ou de la plomberie de frameworks. Ancrer les étudiants dans le cadre PAC, la complexité de Rademacher et la minimisation du risque structurel forge des réflexes mathématiques durables qui survivent au renouvellement des architectures d'apprentissage profond éphémères.

Ingénierie de l'IA en entreprise et valorisation des données #

Les organisations d'ingénierie qui déploient des systèmes prédictifs consacrent souvent trop de capital au calcul (la taille des modèles) en négligeant la complexité d'échantillon et la fidélité des étiquettes. Comme l'erreur de généralisation est strictement bornée par la complexité de la classe de concepts rapportée à la taille de l'échantillon, les équipes obtiennent un meilleur retour sur investissement en misant sur une annotation propre et sur l'audit des échantillons plutôt que sur des modèles plus grands et non régularisés.

Recherche en IA de pointe et audit des modèles #

À mesure que des cadres réglementaires comme le règlement européen sur l'IA exigent des bornes prévisibles pour les systèmes de décision automatisés, les garanties statistiques d'apprentissage formalisées dans Foundations of Machine Learning deviennent des nécessités de conformité. Les régulateurs et les auditeurs de sécurité exigent des bornes de généralisation démontrables et des protocoles rigoureux de sélection de modèles plutôt que des scores de validation heuristiques.

Conclusion #

Foundations of Machine Learning reste un point d'ancrage indispensable dans un domaine souvent tenté par l'empirisme brut. En construisant tout un cursus autour de l'apprentissage PAC, de la complexité de Rademacher et de la dimension VC, Mehryar Mohri, Afshin Rostamizadeh et Ameet Talwalkar rappellent aux chercheurs que l'élégance algorithmique ne remplace pas les garanties mathématiques. L'omission assumée des réseaux de neurones et des modèles graphiques, faute de garanties sous forme close, n'est pas un défaut : c'est la force qui définit le livre, en séparant nettement ce que la discipline peut démontrer rigoureusement de ce qu'elle se contente d'observer.

Questions ? Réponses.

Pourquoi les auteurs ont-ils omis les réseaux de neurones et les modèles graphiques de la deuxième édition ?

Les auteurs ont délibérément omis les réseaux de neurones et les modèles graphiques par souci de concision et en raison du manque actuel de garanties théoriques solides pour plusieurs de ces méthodes. Le livre est organisé strictement autour d'algorithmes qui admettent des bornes de généralisation rigoureuses.

Qu'est-ce qui distingue la complexité d'échantillon de la complexité en temps et en espace ?

La complexité en temps évalue la vitesse d'exécution et la complexité en espace mesure la consommation de mémoire, tandis que la complexité d'échantillon quantifie le volume de données d'entraînement dont un algorithme a besoin pour apprendre une famille de concepts dans des tolérances d'erreur et de confiance données.

Quelle est la différence fondamentale entre la minimisation du risque empirique et la minimisation du risque structurel ?

La minimisation du risque empirique (ERM) choisit l'hypothèse qui minimise directement l'erreur d'entraînement, au risque de surapprendre lorsque la complexité des hypothèses est élevée. La minimisation du risque structurel (SRM) met en balance l'erreur d'entraînement et la complexité des hypothèses (par exemple la dimension VC ou la complexité de Rademacher), ce qui fournit des bornes formelles sur le risque de généralisation.

Références #

Mehryar Mohri, Afshin Rostamizadeh et Ameet Talwalkar, (2018). Foundations of Machine Learning, deuxième édition ⧉. The MIT Press.
Leslie G. Valiant, (1984). Une théorie de l'apprenable ⧉. Communications of the ACM.
Vladimir N. Vapnik, (1998). Théorie statistique de l'apprentissage ⧉. John Wiley & Sons.

Dernière révision 2026-10-10.

Dernière révision 2026-10-27.

Republier cet article

Ce qu'un sommaire de manuel d'apprentissage automatique dit du domaine — Sebastien Rousseau

Le manuel de Mohri, Rostamizadeh et Talwalkar (MIT Press, 2018) bâtit l'apprentissage automatique sur la complexité d'échantillon, les bornes et les garanties.

Cet article est sous licence Creative Commons Attribution 4.0 International. La republication nécessite l'attribution à l'URL canonique.

Ce qu'un sommaire de manuel d'apprentissage automatique dit du domaine — Sebastien Rousseau

Le manuel de Mohri, Rostamizadeh et Talwalkar (MIT Press, 2018) bâtit l'apprentissage automatique sur la complexité d'échantillon, les bornes et les garanties.

Originally published at https://sebastienrousseau.com/fr/2026-10-10-sommaire-de-manuel-apprentissage-automatique-dit/ by Sebastien Rousseau.
Licensed under CC-BY-4.0.

SEBASTIEN ROUSSEAU FONDATEUR · INGÉNIEUR