Apprentissage Statistique
ENPC ParisTech - 2014/15



Enseignants:

  1. Stephan Clémençon (Prof. Telecom-ParisTech)

  2. Nicolas Baskiotis (UPMC)

  3. Guillaume Obozinski (ENPC ParisTech)


OBJECTIFS


Beaucoup d'applications modernes (génomique, finance, e-marketing, etc.) requièrent de manipuler et traiter des données de très grande dimension. La discipline qui développe et étudie des méthodes concrètes pour modéliser ce type de données s'appelle l'apprentissage statistique (statistical machine learning). Il s'agit, in fine, de produire des outils de prédiction et d'aide à la décision dédiés à une application spécifique. L'apparition d'algorithmes très performants pour la classification de données en grande dimension, tels que le boosting ou les Support Vector Machines dans le milieu des années 90, a progressivement transformé le champ occupé jusqu'alors par la statistique traditionnelle qui s'appuyait en grande partie sur le prétraitement réalisé par l'opérateur humain. En s'appuyant sur la théorie popularisée par Vapnik (The Nature of Statistical Learning, 1995), un nouveau courant de recherche est né: il se situe à l'interface entre les communautés mathématique et informatique et mobilise un nombre croissant de jeunes chercheurs tournés vers les applications liées à l'analyse de données massives. Dans ce module, on présentera le domaine, ses fondements, les problèmes qu'il permet d'aborder (apprentissage supervisé/non supervisé, batch/online, par renforcement, etc.) et les méthodes les plus récentes qui sont actuellement étudiées. Au delà de la description des concepts  théoriques (minimisation empirique du risque, complexité combinatoire, etc.), ce module propose de nombreux travaux pratiques permettant de mettre en œuvre numériquement les méthodes abordées (agrégation, validation croisée, etc.) et d’expérimenter certains phénomènes tels que le sur/sous apprentissage. Ces travaux seront réalisés sous l’environnement Python, certains requerront un peu de programmation, d’autres l’usage de packages dédiés.



PROGRAMME


L’objectif du cours est de découvrir les enjeux et paradigmes 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, principalement autour du problème fondamental de la "classification supervisée" (i.e. "reconnaissance de formes"). Il se déroulera sur douze séances de 3h incluant:


  1. des cours lors desquels seront formulés les problèmes et décrites certaines solutions de l’état de l’art ;

  2. des TP vous permettant de mettre en oeuvre et tester ces solutions.


Les sujets de TP sont disponibles en ligne ici



Séance 1 - 5/03 - Introduction (Guillaume)


  1. Machine Learning : repères historiques, enjeux, applications, nomenclature des problèmes

  2. Perte, risque, risque conditionnel, fonction cible, risque empirique

  3. Premiers algorithmes pour la classification: plug-in et régression logistique, LDA et Perceptron


Séance 2 - 12/03 - Théorie de la Décision (Guillaume)


  1. Régression des moindres carrés

  2. Régression linéaire

  3. Résolution du problème de classification via l’approche plug-in fondée sur la régression linéaire

  4. Exemple de surapprentissage pour la régression polynomiale

  5. Classe d’hypothèse

  6. Régularisation de Tikhonov



Séance 3 - 19/03 - TP Premiers algorithmes de classification (Nicolas)


  1. Prise en main de l’environnement Python

  2. Premiers algorithmes: le Perceptron mono-couche, LDA/QDA, etc.




Séance 4 - 26/03 - Evaluation/sélection de modèles & Moyennes locales (Stephan)


  1. Validation simple, plan expérimental

  2. Validation croisée, leave one out

  3. Bootstrap

  4. Courbe ROC, courbe précision/rappel

  5. K-NN et variantes

  6. Noyaux de convolution, estimateurs de Nadaraya Watson et «plug-in»

  7. Arbres de décision

  8. « Ensemble Learning » : bagging, boosting et forêts aléatoires



Séance 5 - 2/04 - SVM et méthodes à noyau (Guillaume)


• Eléments d’optimisation sous contraintes (Lagrangien, Karush Kuhn Tucker)

• Formulation géométrique

• Conditions d’optimalité et interprétation en supports vecteurs

• Interprétation en termes de «hinge loss»

•Kernel trick et SVM non-linéaires

•Kernel ridge regression

•RKHS

   


Séance 6 - 9/04 - TP Algorithmes Avancés (Nicolas)




Séance 7 - 23/04 - Théorie de l’apprentissage (Stephan)


  1. Le paradygme de la minimisation du risque empirique

  2. L’inégalité de McDiarmid

  3. Théorie de Vapnik-Chervonenkis – Complexité combinatoire

  4. Minimisation structurelle du risque



Séance 8 - 7/05 - Travaux Pratiques (Nicolas)




Séance 9 - 21/05 - Clustering et Parcimonie (Guillaume)


• K-means

  1. Algorithme EM

  2. Pénalité L1 et Lasso

  3. Algorithme LARS



Séance 10 - 28/05 - Travaux Pratiques (Nicolas)




Séance 11 - 4/06 - Classification multiclasse (Stephan)


•Régression logistique multiclasse

  1. SVM multiclasse

  2. Approches «un contre un» et «un contre tous»

  3. Calibration

  4. Précision vs rappel

  5. Ranking



Séance 11 - 11/06 - Travaux Pratiques (Nicolas)





MODALITÉS


12 séances (Cours et/ou TP) de 3h

1 séance de 3h dédiée à la présentation des projets réalisés le 18 juin 2014.

Les séances ont lieu de 8h45 à 11h45 en salle V002 pour les cours et en salle P320 pour les TP.






CONTRÔLE DES CONNAISSANCES ET RÈGLES DE VALIDATION


L’acquisition des connaissances sera évaluée à travers la l’évaluation de la qualité des TP réalisés (30% de la note finale) et de la réalisation (en binôme) et la présentation le 18 juin 2015 d’un projet au choix, autour de l’un des thèmes traités (70% de la note finale). Les projets proposés seront présentés à la fin de la 5ème séance. Les projets proposés requerront la lecture d’un ou plusieurs articles de recherche, une présentation des concepts abordés et des résultats obtenus, ainsi que la mise en œuvre des méthodes étudiées sur données réelles et/ou simulées. Vous rédigerez (seul ou en binôme) un rapport résumant vos avancées sur le projet choisi et vous présenterez (en équipe) les résultats obtenus (20 mn). Vous serez interrogés individuellement sur votre compréhension globale du cours et votre rôle dans le projet.



PROJETS






DOCUMENTS PEDAGOGIQUES


Les «slides» du cours seront disponibles en version électronique. Des sujets de TP seront distribués et on se réfèrera en particulier aux documents suivants.


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 & 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.