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.




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]
-- 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]
[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]
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]
(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]

29 mars
-- Bayesian model averaging [Olivier Catoni]
[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)

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]
-- Classification par méthodes PAC bayésiennes (1/2) [Olivier Catoni]
[Notes de cours]

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]

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]
-- 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]
[Notes de cours] [code matlab] [visages] [images couleurs]

31 mai
-- Examen final