Cours PESTO Web-Mining - Apprentissage statistique

Classification binaire supervisée : introduction aux paradigmes du "machine-learning"

Equipe encadrante: Stéphan Clémençon et Aurélien Garivier

L'objectif du cours est de découvrir les enjeux du "machine learning", une discipline en plein essor à l'interface des mathématiques (probabilités/statistiques, optimisation) et de l'informatique et qui joue aujourd'hui un rôle majeur en matière d'innovation technologique. Il s'agira ici d'en explorer quelques concepts et techniques essentiels, à travers un projet (décrit ci-dessous) autour du problème fondamental de la "classification supervisée" (i.e. "reconnaissance de formes"). Il se déroulera sur trois semaines, pendant lesquelles alterneront:

• des séances de cours où seront formulés les problèmes et décrites certaines solutions de l'état de l'art;
• des TP vous permettant de mettre en oeuvre et tester ces solutions.

En parallèle, vous devrez réaliser en équipe un projet de synthèse requérant l'utilisation des notions abordées en cours/TP. L'organisation du travail en équipe est laissée à votre discrétion. Vous disposerez d'un accès à une salle de TP (DB 001 sur le site Dareau). En ce qui concerne l'évaluation de votre travail (individuel et collectif), vous rédigerez ensemble:

• un rapport qui synthétisera ce que vous aurez fait pendant les TP;
• un rapport résumant vos avancées sur le projet de fond.

Vous présenterez en équipe les résultats obtenus sur le projet de fond (20 mn). Par ailleurs, vous exposerez individuellement votre compréhension globale du cours et décrirez votre rôle dans le projet (15 mn).

PROGRAMME DE TRAVAIL

Séance 1 (17/10/11) Le machine-learning : problèmes et principes généraux

TP 1 (17/10/11) Introduction au logiciel statistique R (slides d'introduction à R, le perceptron)

Séance 2 (18/10/11) Le problème de la classification binaire - Premiers algorithmes

TP 2 (18/10/11) Premiers algorithmes de classification

Séance 3 (19/10/11) Notions de complexité - Un peu de théorie

TP 3 (19/10/11) Premiers algorithmes de classification (suite)

Séance 4 (20/10/11) Evaluation du risque, sélection de modèle et bootstrap

TP 4 (20/10/11) Premiers algorithmes de classification (suite)

Séance 5 (21/10/11) Apprentissage en ligne et problèmes de bandits

TP 5 (21/10/11) Quelques expériences en apprentissage on-line et problèmes de bandits

Séance 6 (24/10/11) Travail sur projet

TP 6 (24/10/11) Travail sur projet en salle C129 exceptionnellement

Séance 7 (25/10/11) Machines à vecteurs support - cas linéaire et "kernel trick"

TP 7 (25/10/11) Mise en oeuvre des SVM

Séance 8 (26/10/11) Méthodes d'agrégation: bagging, boosting et forêts aléatoires

TP 8 (26/10/11) Mise en oeuvre des méthodes d'agrégation

Séance 9 (27/10/11) Apprentissage par renforcement

TP 9 (27/10/11) Optimisation de stock, corrigé

Séance 10 (28/10/11) Prédiction de séquences individuelles et soft-max

TP 10 (28/10/11) poursuite du meilleur expert, comparaisons EXP3/UCB

Projet (31/10-04/11) Finalisation du projet

QUELQUES RÉFÉRENCES

• J. Friedman, T. Hastie, R. Tibshirani (2009). The Elements of Statistical Learning. Third edition, Springer. Disponible en ligne .
• O. Bousquet, S. Boucheron,; G. Lugosi (2004). Introduction to statistical learning theory. In O. Bousquet, U.V. Luxburg, G. Rätsch (editors), Advanced Lectures in Machine Learning, Springer, pp. 169-207, 2004. Disponible en ligne.
• S. Kulkarni, G. Lugosi and S. Venkatesh (1998). Learning Pattern Classification. A Survey. 1948-1998 Special Commemorative Issue of IEEE Transactions on Information Theory, vol.44, 2178-2206. Reprinted in S. Verdú, S.W. McLaughlin (editors.), Information Theory: 50 Years of Discovery, IEEE Press, New York, 1999. Disponible en ligne.
• G. Lugosi (2006). Prédiction randomisée de suites individuelles. Journal de la Société Française de Statistique, 147:5-37. Disponible en ligne.
• G. Stoltz (2011). Prédiction de suites individuelles, notes de cours. Disponibles en ligne.
• J.Y. Audibert, R. Munos (2010). ICML Tutorial on bandits. Disponible en ligne .
• Sigaud, Buffet (2008) Processus Décisionnels de Markov en Intelligence Artificielle. Disponible en ligne.
• Bertsekas (1995) Dynamic Programming and Optimal Control. Disponible en ligne.
• Cesa-Bianchi, Lugosi (2006) Prediction, Learning, and Games.
• Devroye, Györfi, Lugosi (1996) A Probabilistic Theory of Pattern Recognition.
• Györfi, Kohler, Krzyzak, Walk (2002) A Distribution-Free Theory of Nonparametric Regression.
• Puterman (1994) Markov Decision Processes, Discrete Stochastic Dynamic Programming
• Sutton, Barto (1998) Reinforcement Learning.