Introduction à la Théorie de l’Apprentissage Statistique

Master Recherche M2MO - 2014/15
Université Denis Diderot Paris 7

Enseignants: 
 Stéphan Clémençon (Prof. Telecom-ParisTech)
 Joseph Salmon (MdC Telecom 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, multi-tâche, asynchrone, etc.) et les méthodes les plus récentes qui sont actuellement étudiées. 
«Nothing is more practical than a good theory» - V. Vapnik



MODALITÉS

8 séances de Cours/TD de 3h
1 examen écrit de 3h - 13H30/17h30 en salle 027C à la Halle aux Farines
Les séances de cours/TD ont lieu de 13h30 à 16h30 en salle 0011 à l’Université Denis Diderot Paris 7 (Bâtiment Sophie Germain - Grands Moulins)



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 huit séances de 3h incluant:

•	des séances de cours lors desquelles seront formulés les problèmes et décrites certaines solutions de l’état de l’art ;
•	des séances d’exercices.



Séance 1 - 25/11 - (Stéphan)

 Introduction générale du cours : repères historiques, enjeux, applications, nomenclature des problèmes
	Le problème de la classification binaire (pattern recognition) : Formalisme – Optimalité
    Lectures conseillées: Chapitre 2 de (1), Chapitres 1 et 2 de (9), article (4)
M2MO_Seance1.pdf

Séance 2 - 02/12 (Stéphan+Joseph)
 
Théorie probabiliste de la classification - Minimisation empirique du risque 
Théorie de Vapnik-Chervonenkis – Complexité combinatoire - Moyennes de Rademacher
Exercices
    Lectures conseillées: articles (3) et (4)
M2MO_seance2.pdf

Séance 3 - 09/12 (Stéphan)

Premières stratégies d’apprentissage supervisé: régression logistique - perceptron - arbres de classification –  K-plus proches voisins
    Lectures conseillées: Chapitres 4 et 9 de (1)
M2MO_seance3.pdf
M2MO_seance3bis.pdf


Séance 4 - 16/12 (Stéphan)

Exercices
Evaluation de l’erreur et sélection de modèles : plan expérimental – bootstrap – validation croisée – minimisation structurelle du risque 
    Lectures conseillées: Chapitre 7 de (1)
M2MO_seance4.pdf

Séance 5 - 06/01 (Stéphan+Joseph)

Peceptron et Gradient Stochastique
Exercices
Lectures conseillées: Chapitre 7 de (1)


Séance 6 - 13/01 (Stéphan+Joseph)

Les machines à vecteurs support (SVM) : linéaires/non linéaires
«Kernel trick»: ACP, régression 
Exercices
    Lectures conseillées: (8) et (9)
M2MO_Seance6.pdf

Séance 7 - 20/01 (Stéphan+Joseph)

Bagging, Boosting et Forêts Aléatoires
Convexification, régularisation, pénalisation du risque
 Exercices
M2MO_seance7.pdf
M2MO_seance7_bis.pdf

Séance 8 - 27/01 (Stéphan+Joseph)

 Apprentissage non supervisé
 Minimum volume set
•	Algorithme K-means
•	Approche probabiliste – l’algorithme EM
 Clustering et ACP
 Exercices
M2MO_seance8.pdf



TRAVAUX DIRIGES

learning_td1.pdf
learning_td2.pdf
learning_td3.pdf


DOCUMENTS PEDAGOGIQUES

Les «slides» du cours seront disponibles en version électronique. On se réfèrera en particulier aux documents suivants.

Friedman, Hastie & Tibshirani (2009). The Elements of Statistical Learning. Third edition, Springer. Disponible en ligne.
Bousquet, Boucheron & 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.
Bousquet, Boucheron & Lugosi (2004). Concentration Inequalities. In Advanced Lectures in Machine Learning, Springer, pp. 208-240. Disponible en ligne.
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.
Cesa-Bianchi & Lugosi (2006) Prediction, Learning, and Games. Cambridge. University Press.
Devroye, Györfi & Lugosi (1996) A Probabilistic Theory of Pattern Recognition. Springer
Györfi, Kohler, Krzyzak & Walk (2002) A Distribution-Free Theory of Nonparametric Regression. Springer
Burgess. A Tutorial on SVM for Pattern Recognition. Kluwer. Disponible en ligne.
Vapnik. The Statistical Nature of Learning Theory. Springer.



SUJETS D’EXAMEN

learning_exam_2009_v2.pdf
learning_exam_2010_v1.pdf
learning_exam_2011_v1.pdf
learning_exam_2012.pdf
learning_exam_2013.pdf
learning_exam_2014.pdf


Course_M2MO_files/M2MO_Seance1.pdfCourse_M2MO_files/M2MO_seance2.pdfCourse_M2MO_files/ENPC_Seance3.pdfCourse_M2MO_files/M2MO_seance3bis.pdfCourse_M2MO_files/M2MO_seance4.pdfCourse_M2MO_files/M2MO_Seance5.pdfCourse_M2MO_files/M2MO_seance7.pdfCourse_M2MO_files/M2MO_seance7_bis.pdfCourse_M2MO_files/M2MO_seance8.pdfCourse_M2MO_files/learning_td1.pdfCourse_M2MO_files/learning_td2.pdfCourse_M2MO_files/learning_td3.pdfhttp://www-stat.stanford.edu/~tibs/ElemStatLearn/http://www-stat.stanford.edu/~tibs/ElemStatLearn/http://www.econ.upf.edu/~lugosi/mlss_slt.pdfhttp://www.econ.upf.edu/~lugosi/mlss_slt.pdfhttp://www.econ.upf.edu/~lugosi/mlss_slt.pdfhttp://www.econ.upf.edu/~lugosi/mlss_conc.pdfhttp://www.econ.upf.edu/~lugosi/mlss_conc.pdfhttp://www.econ.upf.edu/~lugosi/survey.pshttp://www.econ.upf.edu/~lugosi/survey.pshttp://www.econ.upf.edu/~lugosi/survey.pshttp://www.econ.upf.edu/~lugosi/survey.pshttp://www.econ.upf.edu/~lugosi/survey.pshttp://research.microsoft.com/pubs/67119/svmtutorial.pdfCourse_M2MO_files/learning_exam_2009_v2.pdfCourse_M2MO_files/learning_exam_2010_v1.pdfCourse_M2MO_files/learning_exam_2011_v1.pdfCourse_M2MO_files/learning_exam_2012.pdfCourse_M2MO_files/learning_exam_2013.pdfCourse_M2MO_files/learning_exam_2014.pdfshapeimage_2_link_0shapeimage_2_link_1shapeimage_2_link_2shapeimage_2_link_3shapeimage_2_link_4shapeimage_2_link_5shapeimage_2_link_6shapeimage_2_link_7shapeimage_2_link_8shapeimage_2_link_9shapeimage_2_link_10shapeimage_2_link_11shapeimage_2_link_12shapeimage_2_link_13shapeimage_2_link_14shapeimage_2_link_15shapeimage_2_link_16shapeimage_2_link_17shapeimage_2_link_18shapeimage_2_link_19shapeimage_2_link_20shapeimage_2_link_21shapeimage_2_link_22shapeimage_2_link_23shapeimage_2_link_24shapeimage_2_link_25shapeimage_2_link_26shapeimage_2_link_27shapeimage_2_link_28shapeimage_2_link_29shapeimage_2_link_30