M2 · Course resources
Machine Learning Theory
Lecturer
Course description
The aim of this course is to
introduce the main problems and theoretical aspects of Machine Learning.
The focus will be mainly on supervised classification, with a few extensions on
non-supervised learning (clustering) and regression.
Each course will be the opportunity of a focus on a particular technique or tool of
general interest (such as deviation inequalities, statistical tests, stochastic
optimization, etc.).
Course outline and slides
- 09.09 1. Introduction, nearest-neighbor classification
- 09.16 2. k-nearest neighbors, deviations for averages
- 09.23 3. KL divergence and lower bounds for deviations, PAC learning in the realizable case
- 09.30 4. Dimensionality reduction, numerical experimentation on the MNIST dataset.
- 10.07 5. No-free-lunch theorem, uniform convergence, VC dimension
- 10.14 6. Sauer's Lemma, Fundamental theorem of statistical learning, proof by uniform convergence theorem for finite VC-dim classes
- 10.21 7. Computational complexity of learning
-
11.04 8.
Linear classifiers, surrogate losses
Homework: due November 25th - 11.18 9. Convex optimization for Machine Learning
- 11.25 10. Regularization, stability and generalization
-
12.02 11.
SVM, Classification Trees, Bagging, Random Forests
- 12.09 12. Boosting, introduction to reinforcement learning
- 12.16 13 Final exam
-
01.06 14.
Reinforcement Learning: planning and learning in Markov Decision Processes,
Julia Notebook: Retail Store Management
-
01.13 15 Presentations of the research papers and challenge methodology. Planning:
- 15:45 - HOHNADEL: Rates of convergence for nearest neighbor classification
- 15:55 - PAVIET-SALOMON: Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithm
- 16:05 - GIOCANTI: The Tradeoffs of Large Scale Learning
- 16:15 - DEPRES: On the difficulty of approximately maximizing agreement
- 16:25 - POURNAJAFI: Classification in general finite dimensional spaces with the k-nearest neighbor rule
- 16:35 - PENEAU: Incremental Majorization-Minimization Optimization with Application to Large-Scale Machine Learning"
- 16:45 - FOURNIER: An Optimal Transport View on Generalization
- 16:55 - Challenge: team TENSOR
- 17:05 - Challenge: team SENSORS
- 17:15 - PETITHOMME: On the Difficulty of Approximately Maximizing Agreements
- 17:25 - VENTURINI: Non-Asymptotic Analysis of Stochastic Approximation Algorithms for Machine Learning
- 17:35 - LECUYER et VAREILLE: The Tradeoffs of Large Scale Learning
Prerequisite
Basic knowledge of probability theory, linear algebra and analysis over the reals
Evaluation
In addition to homework and in-class exercices, students will chose between
- a research article to analyze
- a participation in the Défi IA 2019-2020.
In both case, they will prepare a written report and an oral presentation. The final grade will be a function of all these.
Maybe useful information
- 2020 internship possibly followed by a PhD: Game theory and artificial intelligence at Université Toulouse Capitole
- 2020 internship possibly followed by a PhD: Causal inference and policy learning for personalized medicine at Ecole Polytechnique
- une offre de stage chez Airbus
- AIRBUS lance un nouveau challenge data science, ouvert aux étudiants (et aux chercheur.e.s chevronné.e.s aussi !)
- very accessible and yet rather informative keynote
- Internship propositions at Institut de Mathématiques de Toulouse : Statistical Inference under Differential Privacy, Theoretical challenges in deep learning, Sequential learning theory
- Internship and PhD proposition: Deep learning for texts and knowledge bases access at IRIT and Renault
- Internship: Active and semi-supervised learning using topological data analysis in Grenoble
- Internship: Recommandation / bandits at Moobifun
- Internship: Mathematics of deep learning at Institut de Mathématiques de Toulouse
- Internship: Christoffel functions for Machine Learning at Institut de Mathématiques de Toulouse
- Internship: Explainable AI at Institut de Mathématiques de Toulouse
Bibliography
- Understanding Machine Learning, From Theory to Algorithms, by Shai Shalev-Shwartz and Shai Ben-David
- A Probabilistic Theory of Pattern Recognition, by Luc Devroye, Laszlo Györfi and Gabor Lugosi
- The Elements of Statistical Learning, by Trevor Hastie, Robert Tibshirani and Jerome Friedman
- Introduction to Nonparametric Estimation, by Alexander Tsybakov
- Lectures notes on advanced Statistical Learning (archive lookup), by Martin Wainwright
Notebooks
- Introduction to ML: synthetic example
- Presentation of the MNIST dataset and nearest-neighbor classification
- Dimensionality reductions: numerical experimentation on the MNIST dataset, clustering IRIS (damaged legacy notebook source)
- Reinforcement Learning: Retail Store Management
Slides for 2018-2019
- 09.10 1. Introduction, nearest-neighbor classification
- 09.17 Pot du DI at IFE Descartes (meet your tutor)
- 09.24 2. k-nearest neighbors, deviations for averages
- 10.01 3. Kullback-Leibler divergence, PAC learning theory
- 10.08 4. No-free-lunch theorem, uniform convergence, VC dimension
- 10.15 5. Fundamental theorem of statistical learning, proof by uniform convergence theorem for finite VC-dim classes
- 10.22 6. Computational complexity of learning
- 10.29 holidays
- 11.5 7. Linear classifiers, surrogate losses
- 11.12 winter school on Algorithmic aspects of data analysis and machine learning
- 11.19 8. Convex optimization for Machine Learning
- 11.26 winter school on Computer virology
- 12.03 Exam (2 hours)
- 12.10 9. Stochastic gradient descent
- 12.17 10. Regularization, stability and generalization; Support Vector Machines and Kernels
- 01.07 11. Classification Trees, Boosting, Bagging, Random Forests
- 01.14 12 Presentations of the research papers and challenge methodology.
- 01.25 Dimensionality reduction (Master Math.en.Action), numerical experimentation on the MNIST dataset.
- 02.15 Penalized regression: LASSO (slides by Vivian Viallon)
