Finalité M2 Statistiques et Machine Learning

Responsables : Bastien Dussap et Ibrahim Kaddouri
Crédits : 2,5 ECTS
Agenda du séminaire : https://docs.google.com/document/d/1hHVN...
Le séminaire accueille alternativement des académiques et des industriels qui viennent présenter un de leur domaine de recherche.
La présence est obligatoire.

Responsable : Yannig Goude, cours à EDF Lab
Crédits : 7,5 ECTS
page web du cours : https://www.math.u-psud.fr/ goude/Materials/ProjetMLF/intro.html
L’objectif du cours/projet est d’acquérir une expérience de modélisation statistique, de la préparation des données à la réponse au problème posé. Il s’agit de comparer différents modèles et méthodes statistiques pour analyser un jeu de données associé à une problématique de prévision. Nous travaillerons sur des données de séries temporelles issues de l’open data, notamment dans le domaine de l’énergie. Nous étudierons différentes méthodes de régression non-linéaire issues de récents développements en statistiques et machine learning et ayant faits leurs preuves dans ce contexte : generalized additive model, random forest, gradient boosting machine, curve linear regression, agrégation d’experts.

L’objectif du projet est d’aboutir à une modélisation performante des données (réalisant une faible erreur de prévision et pouvant raisonnablement être mise en œuvre). Le cours propose une démarche fréquente dans l’industrie ou lors de la conduite d’un projet de recherche en statistique appliquée. Plusieurs étapes seront menées : data mining exploratoire (analyse descriptive, visualisation, recherche bibliographique sur les données et le phénomène à modéliser), la modélisation proprement dite (choix de modèle, prétraitements/transformation des données, construction d’un code, validation) puis enfin l’évaluation des performances et la restitution des résultats (présentation et rédaction d’un rapport).

Volume Horaire : 36h présentielle + projet long

Modalités de contrôle : Soutenance orale et rapport écrit. Il y a une seule session d’évaluation de projet.

Responsable : Sylvain Arlot, cours à Orsay
Crédits : 5 ECTS
La première partie du cours présentera les fondements de la théorie statistique de l’apprentissage supervisé, en classification et en régression. Nous établirons des bornes sur l’erreur de prédiction de plusieurs méthodes d’apprentissage parmi les plus classiques : moyennage local (partitions, k plus proches voisins, noyaux) et minimisation du risque empirique. Ces résultats montreront en particulier que certaines de ces méthodes sont « universellement consistantes ». En revanche, nous verrons qu’un apprentissage totalement agnostique n’est possible que dans certaines limites (« on n’a rien sans rien »), ce qui se formalise mathématiquement par plusieurs théorèmes aux énoncés plutôt contre-intuitifs.

La deuxième partie du cours se focalisera sur les méthodes de rééchantillonnage (bootstrap, sous-échantillonnage, validation croisée, etc.) et à leur application en apprentissage. Nous étudierons en particulier leurs propriétés pour l’estimation de l’erreur de prédiction d’une méthode d’apprentissage, et pour la sélection parmi une famille de méthodes d’apprentissage.

Responsable : Pascal Massart, cours à Orsay
Crédits : 5 ECTS

Les inégalités de concentration jouent un rôle central dans l’analyse non-asymptotique des algorithmes de machine learning et des procédures statistiques. Le prototype de telles inégalités est l’inégalité de Talagrand pour les processus empiriques. La méthode entropique initiée par Michel Ledoux il y a une dizaine d’années sera développée. Cette méthode permet en effet d’accéder à des résultats fins avec une économie de moyens remarquable.

Responsables : Christophe Giraud et Matthieu Lerasle
Crédits : 10 ECTS
Objectifs principaux :

• comprendre les phénomènes liés à la grande dimension ;
• fournir des bases conceptuelles et méthodologiques solides ;
• acquérir des techniques mathématiques fondamentales en vue d’une thèse.

La principale difficulté du statisticien face aux données du XXI^e siècle est de vaincre le fléau de la grande dimension. Ce fléau oppose aux statisticiens deux difficultés : d’une part il rend les méthodes statistiques classiques totalement inopérantes par manque de précision, d’autre part il oblige à développer des approches gardant sous contrôle la complexité algorithmique des procédures d’estimation.

Dans la première partie du cours (commune avec le M2 MathSV), nous commencerons par comprendre d’où vient ce fléau et comment le vaincre dans un contexte général. Ensuite, nous verrons comment rendre opérationnels ces concepts, avec une attention sur les frontières du possible.

La seconde partie du cours, sera plus consacrée aux outils probabilistes fondamentaux indispensables pour analyser des problèmes en grande dimension. L’accent sera mis sur les techniques mathématiques et sur la généricité des approches déployées.

website : https://www.imo.universite-paris-saclay.fr/ giraud/Orsay/HDPS.html

Responsable : Etienne Boursier
Crédits : 5 ECTS

Prerequisite : Probability and measure theory

Goals : Sequential learning deals with data observed on the fly. Algorithms treat these data in a sequential (or online) manner, hoping to maximise their cumulated reward. It has been popularised in the last decade due to its numerous applications, which include online recommandation, repeated auctions or spam detection.
The objective of this course is to introduce the main concepts of stochastic online learning (regret, adaptivity...) from a rigorous mathematical point of view. In particular, the course will focus on stochastic multi-armed bandits, aiming at understanding the main proofs techniques and algorithms.
This course will also introduce the technical tools used in the regret bounds proof, including concentration inequalities and information theory.

Content : The course will be organised in 9x2h lessons on blackboard, as well as 6x1.5h small classes. In particular, we will explore the following themes :
– Online learning with experts
– Azuma-Hoeffding inequality
– Stochastic multi-armed bandits : regret bounds of main algorithms
– Kullback Leibler divergence
– Lower bounds
– Linear bandits
– Contextual and continuous bandits
– Best arm identification

The evaluation will be based on a homework and a final written exam.

Bibliography :
« Prediction, learning, and games » Nicolò Cesa-Bianchi and Gábor Lugosi. Cambridge University Press, 2006

« Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems » Sebastien Bubeck and Nicolò Cesa-Bianchi. In Foundations and Trends in Machine Learning, 2012.

« Bandit algorithms » Tor Lattimore and Csaba Szepesvári. Cambridge University Press, 2020.

Responsable : Vianney Perchet
Crédits : 5 ECTS

In this research course, I will present the recent advances in online problems. The objectives is to construct algorithms that discover, and then treat, data one after the other one rather than directly with the whole batch. Typical examples are stopping times (prophets, secretary), online matching, k-servers, etc.
I will cover the main techniques used (related to linear optimisation, stochastic approximation, tree reductions..) and will provide as many open questions as possible.
Disclaimer : the concept of online algorithms is related to online learning (and bandits) but the main question is rather to figure *when* to make a decision than *which* decision to make. Techniques, tools and results are fundamentally different

Responsables : Pascal Bianchi, Olivier Fercoq, cours à Telecom
Crédits : 2.5 ECTS

Objectifs :

• Maîtriser les outils mathématiques pour la construction d’algorithmes d’optimisation convexe.
• Savoir démontrer la convergence des itérées.
• Savoir résoudre numériquement des problèmes d’optimisation comportant des termes de régularisation non dérivables et structurés.
• S’initier à l’optimisation distribuée et la programmation sous Hadoop Spark.

Le cours n’a pas vocation à fournir un répertoire d’algorithmes le plus abondant possible. Il s’agit de prendre du recul afin de comprendre les fondements mathématiques pour la construction d’une vaste classe de méthodes itératives. Après une introduction à la théorie de l’analyse convexe, nous verrons les conditions sous lesquelles on peut démontrer la convergence d’un algorithme du point fixe. Cette approche générale permet de d’obtenir, comme corollaire, la convergence de l’emblématique algorithme du gradient proximal. Elle permet également de construire d’autres algorithmes plus généraux : les méthodes primales-duales.
Ces méthodes permettent de résoudre des problèmes d’optimisation comportant des régularisations complexes et structurées, ou des problèmes d’optimisation sous contraintes. De tels problèmes se rencontrent fréquemment en apprentissage statistique, traitement du signal, et traitement de l’image.

Sur le plan pédagogique, un juste compromis entre fondements théoriques et applications est visé. Deux TP permettront de mettre en application les méthodes numériques vues en cours. Ils incluent une initiation à l’optimisation distribuée et grande échelle, sous Hadoop Spark.

Prérequis : pas de prérequis à l’exception des connaissances élémentaires en analyse convexe : fonctions et ensembles convexes, minimiseurs. Le premier cours est consacré à des rappels.

Responsable : Eric Moulines, cours à Orsay
Crédits : 5 ECTS
L’objet de ce cours est d’introduire les outils d’analyse de chaînes de Markov sur des espaces généraux. Nous introduirons tout d’abord le formalisme de base (noyau, opérations sur les noyaux, opérateurs) puis étendrons au cas continu des résultats élémentaires (Chapman-Kolmogorov, Markov fort, problèmes de Dirichlet et Poisson). Nous étudierons ensuite l’ergodicité des chaînes et le contrôle de convergence. Nous présenterons tout d’abord l’ergodicité uniforme en variation totale (sous la condition de Doeblin uniforme), que nous étendrons à l’ergodicité non uniforme sous les conditions de Foster-Lyapounov (existence d’un petit ensemble et condition de dérive). Nous illustrerons ces théories avec de nombreux exemples, permettant de comprendre la richesse de cette méthode, mais aussi ses limites.

Nous spécialiserons ensuite ces résultats à des espaces topologiques, en introduisant tout d’abord des résultats généraux sur les chaînes Felleriennes et fortement Felleriennes puis en présentant des méthodes permettant d’obtenir des résultats de convergence plus quantitifs (convergence en distance de Wasserstein, étude des systèmes itératifs). Nous présenterons succinctement les extensions non géométriques. Ce cours permet de découvrir ou de voir en action de nombreuses méthodes de probabilités appliquées : couplage, renouvellement, régénération ; il permet aussi de découvrir des connexions intéressantes entre la théorie des opérateurs et les probabilités. Nous illustrerons les concepts introduits dans ce cours à travers de nombreux exemples de probabilités appliquées, théorie des processus, statistiques numériques, domaines dans lesquels les chaînes de Markov jouent un rôle fondamental.

Références Bibliographiques :
– Topics on Markov Chains, R. Douc, E. Moulines, P. Priouret, P. Soulier (Springer)
– Markov Chains and Stochastic stability, S. Meyn et R. Tweedie, 2009, Cambridge University Press
– Convergence of Markov Processes (notes de cours), M. Hairer

Responsable : Aymeric Dieuleveut, cours à Polytechnique
Crédits : 5 ECTS

La majorité des problèmes d’apprentissage sont formulés comme des problèmes d’optimisation, à partir de l’observation d’un échantillon de données (ensemble d’entrainement). L’optimisation d’un objectif défini à partir de cet échantillon permet de proposer un estimateur qui a une bonne performance sur l’ensemble d’apprentissage. Cependant, on s’intéresse généralement à la capacité de généralisation de cet estimateur, c’est à dire sa performance sur une nouvelle observation.

Dans ce cours, on s’intéresse à l’ensemble des résultats tant théoriques qu’heuristiques qui permettent d’aboder de problème.
Plus précisément, on étudiera dans un premier temps les différentes approches qui permettent d’obtenir des garanties théoriques quant à la généralisation des algorithmes, en particulier les approches liées à la complexité, à la stabilité, aux méthodes d’arrêt anticipé (Early stopping). Dans une seconde partie, on étudiera les approches heuristiques et les différences (expliquées ou constatées) dans le cadre du deep learning (non convexe et over-parametrized).

Quelques references :

• Rademacher and Gaussian Complexities : Risk Bounds and Structural Results, P. Bartlett, S. Mendelson
• The Tradeoffs of Large Scale Learning, L. Bottou, O. Bousquet
• Stability and Generalization, O. Bousquet, A. Elisseef
• Train faster, generalize better : Stability of stochastic gradient descent, M. Hardt, B. Recht, Y. Singer
• Non-strongly-convex smooth stochastic approximation with convergence rate O(1/n), F. Bach, E. Moulines
• Understanding deep learning requires rethinking generalization, C. Zhang, S. Bengio, M. Hardt, B. Recht, O. Vinyals
• On early stopping in gradient descent learning, Y Yao, L. Rosasco, and A. Caponnetto
• Generalization properties of multiple passes stochastic gradient method, S. Villa
• Competing with the empirical risk minimizer in a single pass, R. Frostig, R. Ge, S. M. Kakade, A. Sidford
• Deep Learning and Generalization, O. Bousquet

Modalités de contrôle : Examen + projet

Responsable : Cristina Butucea
Crédits : 2.5 ECTS

L’objet de ce cours est de présenter quelques méthodes classiques de l’estimation non-paramétrique. Les thèmes suivants seront abordés :
1. Estimateurs à noyaux et par projection d’une densité. Validation croisée. Vitesses de convergence et optimalité.
2. Estimation non-paramétrique de la fonction de régression. Estimateurs par polynômes locaux, par projection (bases de Fourier, bases d’ondelettes). Vitesses de convergence et adaptation.
3. Estimation de fonctionnelles et tests non paramétriques. Vitesses de convergence et de tests, principes des intervalles de confiance non paramétriques.

Références :
A.B.Tsybakov : Introduction to Nonparametric Estimation. Springer, New York, 2009.
A.B.Tsybakov : Apprentissage statistique et estimation non-paramétrique. Polycopié de l’Ecole Polytechnique, 2014.
L. Wasserman : All of Nonparametric Statistics. Springer, New York, 2006.
L. Devroye : A Course in Density Estimation. Birkhauser, Boston, 1987.
A.Nemirovski : Topics in non-parametric statistics. Ecole d’Eté de Probabilités de Saint-Flour XXVIII - 1998. Lecture Notes in Mathematics, v.1738. Springer, 2000.

Responsable : Pascal Massart, cours à Orsay
Crédits : 5ECTS

La sélection de modèles est un sujet classique en statistique. L’idée de choisir un modèle à partir d’un critère de type log-vraisemblance pénalisée remonte aux travaux séminaux de Mallows et Akaike au début des années 70. On peut trouver dans la littérature de nombreuses variantes de ces critères ainsi que des résultats asymptotiques précisant les propriétés de ces critères lorsque la liste de modèles est considérée comme fixée et le nombre d’observations tend vers l’inifini. Un des deux buts poursuivis dans ce cours est de donner un aperçu de la théorie non asymptotique pour la sélection de modèles qui s’est construite au cours de ces quinze dernières années. Dans différents contextes d’estimation fonctionnelle, il est possible de construire des critères de type log-vraisemblance pénalisée où la pénalité dépend non seulement du nombre de paramètres définissant des modèles comme dans les critères classiques, mais aussi de la « complexité » de la liste de modèles. Dans cette approche, les dimensions des modèles ainsi que la liste de modèles elle-même sont autorisés à dépendre du nombre d’observations. L’expression des pénalités tout autant que l’analyse des performances de ces procédures pénalisées en terme de risque dépendent de manière essentielle d’inégalités dites de concentration.

Responsable : Jaouad Mourtada, cours à l’ENSAE
Crédits : 2.5 ECTS

L’objectif de ce cours est de présenter les bases théoriques de l’apprentissage statistique en se focalisant essentiellement sur la classification binaire.

La complexité statistique (et algorithmique) de ce problème sera considérée à travers l’analyse de la Minimisation Empirique du Risque d’abord, puis par l’étude de classes générales d’algorithmes : SVM, réseaux neuronaux, Boosting et Random Forest (si le temps le permet). Leurs propriétés statistiques seront discutées et comparées.

Ces algorithmes seront appliqués à des données réelles pendant les sessions de TP.

Responsable : Laurent Massoulié
Crédits : 4 ECTS
Ce cours traite de problèmes d’inférence génériques aux applications nombreuses (en biologie, traitement de la parole, moteurs de recommandation, étude de réseaux sociaux,…) posés dans le contexte de graphes. Il traitera notamment : la détection de communautés (identification de groupes de sommets semblables d’un graphe), l’alignement de graphes (mise en correspondance des sommets de plusieurs graphes), et la reconstruction d’arbres (identification de caractéristiques de « l’ancêtre » d’un arbre généalogique d’après les traits de ses descendants).

Des modèles probabilistes de graphes seront introduits, ainsi que l’analyse d’algorithmes efficaces pour des données échantillonnées selon ces modèles. On s’intéressera notamment à des algorithmes spectraux, dont la compréhension repose sur l’étude de spectres de matrices aléatoires associées aux graphes considérés. On abordera aussi des algorithmes basés sur la programmation semi-définie.

Responsable : Edouard Maurel-Segala
Crédits : 4 ECTS

Responsables : Frédéric Chazal et Quentin Merigot
Crédits : 4 ECTS

L’estimation des propriétés de nature topologique et géométrique de données souvent représentées par des ensembles de points dans des espaces euclidiens de grande dimension (ou plus généralement des variétés riemanniennes ou des espaces métriques) connait un développement important depuis quelques années.
L’analyse topologique des données est motivée par l’observation que généralement les données, qui ne sont pas distribuées uniformément dans l’espace ambiant mais se concentrent autour de structures géométriques de plus petite dimension qu’il est important de comprendre.
L’objectif de ce cours est de donner une introduction à ce sujet en pleine expansion.
Les notions nécessaires de topologie et de géométrie seront introduite ou rappelée au fil du cours.

Plan du cours :

1. Introduction et rappels
2. Fonctions distance et reconstruction d’ensembles compacts.
3. Application à l’estimation de l’homologie de de sous-variétés à partir d’échantillon i.i.d. Aspects algorithmiques et statistiques.
4. Homologie persistente : définition, stabilité et applications (clustering, signatures topologiques,...).
5. Propriétés statistiques de l’homologie persistente.
6. Inférence géométrique pour les mesures de probabilité.

Responsable : Evgenii Chzhen
Crédits : 4 ECTS

With the ubiquitous deployment of machine learning algorithms in nearly every area of our lives, the problem of unethical or discriminatory algorithm-based decisions becomes more and more prevalent. To partially address these concerns, a new sub-field of machine learning has emerged. The goal of the course is to introduce the audience to recent developments of fairness aware algorithms. The emphasise will be made on those methods which are supported by statistical guarantees and that can be implemented in practice. We will study classification and regression problems under the so called demographic parity constraint—a popular way to define fairness of an algorithm. Several research directions will be proposed thought out the course.

Responsables : Pascal Bianchi, Walid Hachem and François Portier
Crédits : 4 ECTS

The purpose of this course is
1) to lay the foundations of the Stochastic Approximation theory, and
2) to study some typical applications in machine learning such as optimization algorithms in random environments, or reinforcement learning.

We first recall some fundamental results in probability theory (martingales, Markov chains, etc.). Next, we use these results to study the asymptotic behavior of iterative stochastic algorithms i.e., algorithm for which each iteration depends on the realization of a random variable. This covers many applications (stochastic optimization for machine learning, reinforcement learning, game theory, etc.). We especially emphasize two applications : in optimization, we focus on the analysis of the stochastic gradient descent and its variants ; in reinforcement learning, we analyze the convergence of temporal difference learning and Q-learning algorithms.

Prerequisite : Students are expected to have a good background in probability theory. It is strongly advised to follow the course on « Reinforcement learning » prior to this course. Although not mandatory, it is also advised to follow at least one of the following courses :
– Hidden markov chains and sequential Monte-Carlo
– Partially observed Markov chains in signal and image
– Bayesian Learning in partially observed evolving graphical models

Course schedule :
– Applicative context and mathematical foundations.
– The ODE method and almost sure convergence techniques in the decreasing step case.
– Weak convergence techniques and the constant step case.
– Fluctuations and saddle point avoidance.
– Applications : Convex and non-convex optimization, Reinforcement learning, Temporal Difference learning, Q-learning

Responsables : Marco Cuturi
Crédits : 4 ECTS
8 lectures + 4 practical sessions for a total of 18 hours

3 lectures on theory
– Monge and Kantorovich Problems, duality in OT, 2-Wasserstein geometry and the Brenier theorem.
– Closed forms : Applications to transport between Gaussians, Transport in 1D,
Caffarelli contraction theorem, regularity theory (Figalli).

3 lectures on computations and statistics
– Algorithmic overview : network flow solvers in the discrete world, Benamou-Brenier formula in the PDE world.
– Statistical results and the curse of dimensionality
– Regularized approaches to compute optimal transport.

2 lectures on applications
– Handling measures with the Wasserstein geometry : computation of barycenters, clusters
– Automatic differentiation with the Sinkhorn algorithm. Wasserstein regression Wasserstein GANs
– Applications to Biology (cell pathways) and NLP (alignment of multilingual corpora)

4 practical sessions
– 1D transport, transport between Gaussians, network flow solver type algorithms
Sinkhorn algorithm, color transfer, retrieval, biology.
– Sorting using the Sin.

Responsable : Vincent Rivoirard
Crédits : 4 ECTS
Un grand nombre de domaines scientifiques tels que la biostatistique ou l’apprentissage emploie naturellement le paradigme bayésien (où l’on suppose que le paramètre à inférer est une variable aléatoire). En particulier, en autorisant une grande flexibilité sur la modélisation des paramètres, l’approche non-paramétrique de la statistique bayésienne a connu un essor considérable ces dernières années. L’objectif de ce cours est de proposer un large panorama des méthodes et des résultats théoriques spécifiques à la statistique bayésienne non-paramétrique.

La première partie du cours présentera les principes de l’estimation fonctionnelle propre à l’approche bayésienne. On s’attardera notamment sur la construction des distributions a priori les plus classiques fondées sur les processus gaussiens et de Dirichlet. Dans un second temps, on analysera le comportement asymptotique des distributions a posteriori (consistance et vitesse de convergence). Bien que l’estimation de densité constituera le fil rouge de ce cours, on proposera également quelques extensions dans le cadre de la grande dimension ou pour d’autres modèles statistiques moins classiques.

Des pré-requis sur l’approche bayésienne classique seront utiles mais pas indispensables (une remise à niveau est prévue lors du premier cours)