Machine Learning

Lecturer

Aurélien Garivier

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
  Team tENSors has won the challenge! see the the video of the final day.

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

1. Understanding Machine Learning, From Theory to Algorithms, by Shai Shalev-Shwartz and Shai Ben-David
2. A Probabilistic Theory of Pattern Recognition, by Luc Devroye, Laszlo Györfi and Gabor Lugosi
3. The Elements of Statistical Learning, by Trevor Hastie, Robert Tibshirani and Jerome Friedman
4. Introduction to Nonparametric Estimation, by Alexander Tsybakov
5. Lectures notes on advanced Statistical Learning , by Martin Wainwright

Notebooks

1. Introduction to ML: synthetic example
2. Presentation of the MNIST dataset and nearest-neighbor classification
3. Dimensionality reductions: numerical experimentation on the MNIST dataset, clustering IRIS
4. Reinforcement Learning: Retail Store Management