Apprentissage
Cours de la filière mathématiques-informatique à l'Ecole normale
supérieure
Peut également compter comme cours non-mathématique pour les
étudiants du département de mathématiques
Ou comme cours mathématique pour les étudiants du département
d'informatique
Enseignants
Ce cours est assuré en commun par cinq chercheurs :
-- au département d'informatique : Sylvain
Arlot, Francis Bach,
Guillaume Obozinski
-- au département de mathématiques : Olivier
Catoni, Gilles
Stoltz
Résumé du cours
L'apprentissage est un domaine à la frontière entre mathématiques
appliquées (statistique et optimisation) et informatique. On y
considère un environnement incertain, produisant des variables
observées (dites explicatives et qui sont souvent quantitatives)
auxquelles sont associées des variables inconnues (qui peuvent être
qualitatives ou quantitatives).
Ce type d'environnement est bien décrit par un modèle aléatoire,
précisant la loi jointe des variables observées et inconnues. La
théorie des probabilités et la statistique en déterminent le choix
et les procédures d'estimation. Cependant, la théorie de
l'apprentissage a un objectif plus simple et plus concret : il
s'agit surtout de bien prédire les variables inconnues à partir des
variables observées. (En clair, on s'intéresse surtout aux lois
conditionnelles des variables inconnues étant données les variables
observées.) Par ailleurs, on tâchera de faire les hypothèses les
plus faibles possibles sur la loi jointe de l'environnement. On
parle d'apprentissage statistique.
Le lien avec l'informatique se fait à travers la recherche de
méthodes si possible efficaces à mettre en oeuvre (du point de vue
de la complexité computationnelle et/ou mémoire). On vise également
l'obtention de procédures les plus automatiques possibles, qui se
calibrent elles-mêmes et sachent s'adapter à l'environnement, même
si celui-ci change : c'est pourquoi on parle d'apprentissage
automatique (machine learning),
puisque l'on veut que l'homme, hormis la construction initiale de la
méthode, intervienne le moins possible.
Il sera impossible, dans le cadre de ce cours, de dresser un
panorama exhaustif de ce domaine déjà vaste et encore en expansion
rapide. Les thèmes applicatifs suivants seront privilégiés :
- Classification (affectation d'une étiquette à des données)
- Débruitage d'un signal (à la fois pour des petits ou des grands
nombres de variables explicatives)
- Apprentissage avec données séquentielles
On étudiera les concepts théoriques et algorithmiques qui les
motivent et les justifient et on présentera des implémentations et
illustrations de ces méthodes sur données réelles ou simulées.
Les seuls pré-requis sont d'être familier avec les fondements de la
théorie des probabilités (notion de variables aléatoires, théorèmes
de convergence, espérance conditionnelle), ceux vus au cours
d'intégration et probabilités du premier semestre ; il n'est pas
nécessaire de suivre en parallèle le cours de processus aléatoires
du second semestre. En revanche, quelques nouveaux outils
probabilistes (et notamment, des inégalités de concentration) seront
introduits.
Méthode pédagogique, attendus et
critères d'évaluation
L'objectif de ce cours est de mêler
-- théorie (des théorèmes seront prouvés)
-- et pratique (des algorithmes seront à implémenter sur données
réelles ou artificielles).
Nous alternerons, dans la mesure du possible,
-- cours magistral,
-- exercices de mise en application ou d'approfondissement
(ensemble ou à la maison),
-- codage d'algorithmes (à la maison, dans le langage de son choix :
Matlab, R, Python, C, etc.).
Ce cours compte pour 12 ECTS et devrait durer 60 heures. Or seules
48 heures de cours peuvent être assurées au vu de l'emploi du temps.
Une partie importante de l'évaluation reposera donc sur les travaux
(exercices théoriques ou de programmation) à effectuer à la maison.
La note finale sera déterminée
-- pour 6 ECTS par l'examen final et l'examen partiel,
-- pour 6 ECTS par les travaux (mathématiques et de programmation) à effectuer à la
maison.
Résumé de ce qui précède, tel que
distribué en cours
Liste des étudiants suivant le
cours
Notes de cours et déroulement
prévisionnel
Les cours auront lieu les jeudis matins, de 8h30 à 12h30.
Vous pouvez compter sur une pause de 10h25 à 10h40 environ.
Dans la mesure du possible, nous éviterons de traiter le même sujet
pendant les 4 heures et essaierons plutôt d'étudier deux
modèles et théories en parallèle.
16 février
-- Introduction et panorama des méthodes d'apprentissage [Guillaume
Obozinski]
-- Méthodes supervisées [Guillaume Obozinski]
Notes de cours pour ces deux points
Travail à effectuer en autonomie : TP
de prise en main de Matlab / Octave / Scilab
23 février
-- Règles par partition en classification et régression [Sylvain
Arlot]
[Notes de cours]
[Preuves des lemmes]
[Solution de l'exercice de
programmation]
-- Boîte à outils de probabilités : inégalités de concentration et
de déviation [Gilles Stoltz]
[Notes de cours pour la boîte à
outils de probabilités]
[Solution de
l'exercice avec Borel-Cantelli]
[Exemples de
simulations pour illustrer l'inégalité de Hoeffding]
1er mars
-- Algorithmes par moyennage local [Guillaume Obozinski]
[ Notes de cours]
[ Preuve de
consistance des k.p.p.v.]
-- Boîte à outils de probabilités : liens entre inégalités en
espérance et en grande probabilité [Gilles Stoltz]
[Compléments
manuscrits de notes de cours]
[Débat : Une
variable sous-gaussienne est-elle toujours d'espérance nulle ?]
[Exemples
de simulations pour illustrer l'inégalité sur le maximum de
variables sous-gaussiennes]
8 mars
-- Résultats fondamentaux en optimisation et en analyse convexe
(1/2) [Francis Bach]
[Notes de
cours]
[Devoirs
pour le 15 mars]
-- Modélisation probabiliste, principe du maximum de vraisemblance [Guillaume
Obozinski]
[ Notes de cours]
15 mars
-- Résultats fondamentaux en optimisation et en analyse convexe
(2/2) [Francis Bach]
[Notes de cours]
-- Régression linéaire, régression logistique [Guillaume
Obozinski]
[Notes de cours]
[Devoir pour le 30 mars]
[classificationA.train][classificationA.test]
[classificationB.train][classificationB.test]
[classificationC.train][classificationC.test]
On peut utiliser la fonction textread dans Matlab/Scilab/Octave pour charger les données.
22 mars
-- Résultats fondamentaux en théorie de l'information [Olivier
Catoni]
[Notes de cours]
Devoirs pour le 5 avril : les quatre exercices des notes de cours,
(le quatrième est un exercice de programmation), à rendre par mail svp.
-- Méthodes par minimisation du risque empirique [Sylvain Arlot]
[Notes de cours]
[Preuves faites en cours]
[Devoir pour le 12 avril
/ Solution
/ Correction: Exercice 1
(Basile Clément), Exercice 2: questions 1-6 (Basile Clément), questions 1-8 (Rémi Varloot)
]
29 mars
-- Bayesian model averaging
[Olivier Catoni]
[Notes de cours]
Devoirs pour le 12 avril : les deux exercices des notes de cours.
-- Apprentissage séquentiel: prévision de suites arbitraires (1/2)
[Gilles Stoltz]
[Notes de cours]
[Jeu de données] / [Instructions -- devoirs à rendre pour le 5 avril]
2 avril, pendant 2h à choisir entre 11h et 15h, salle R
-- Examen partiel (documents autorisés)
[Sujet] [Corrigé du début de l'exercice 2] [Corrigé de la seconde partie de l'exercice faite en cours]
5 avril
-- Apprentissage séquentiel : prévision de suites arbitraires (2/2)
[Gilles Stoltz]
[Notes de cours]
[Illustrations sur données réelles : ozone, EDF, marché boursier, matchs de tennis]
[Exercice issu des annales -- rendu facultatif, pour début mai]
[Etude empirique -- devoir à rendre pour début mai]
-- Classification par méthodes PAC bayésiennes (1/2) [Olivier
Catoni]
[Notes de cours]
Exercices 7, 8 et 9 des notes de cours, à rendre le 3 mai.
12 avril
-- Classification par méthodes PAC bayésiennes (2/2) [Olivier
Catoni]
Mêmes notes de cours que précédemment : j'ai pris un peu de retard !
-- Pénalisation L0 [Sylvain Arlot]
[Notes de cours]
[Devoir pour le 10 mai]
19 avril / Vacances universitaires
26 avril / Vacances universitaires
3 mai
-- On n'a rien sans rien : les théorèmes no free lunch
[Sylvain Arlot]
[Notes de cours]
-- Méthodes à noyaux PAC bayésiennes [Olivier Catoni]
[Notes de cours]
[Notes manuscrites]
[Code octave]
10 mai
-- Validation croisée [Sylvain Arlot]
[Notes de cours]
[Devoir pour le 24 mai]
-- Apprentissage séquentiel : introduction à la théorie des jeux [Gilles Stoltz]
[Notes de cours]
17 mai / Jour férié
24 mai
-- Méthodes à noyaux 1 [Francis Bach]
-- Méthodes à noyaux 2 [Francis Bach]
31 mai
-- Examen final