Cours présenté par : Guillaume LECUÉ
Nombre d’ECTS : 

Objectifs

L’objectif de ce cours est d’étudier des problèmes de statistiques en grandes dimensions afin de dégager trois idées fondamentales de cette thématique qui pourront par la suite être appliquées dans de nombreux autres problèmes liés aux sciences des données. Nous énonçons brièvement ces principes :

  1. Un grand nombre de données réelles appartiennent à des espaces de grandes dimensions dans lesquels les méthodes classiques de statistiques sont inefficaces (cf. fléau de la dimension). Néanmoins ces données sont pour la plupart d’entre elles structurées. Si bien que la “vraie” dimension du problème n’est plus celle de l’espace ambiant mais plutôt celle de la structure qui contient l’information utile des données. On parle de données structurées ou parcimonieuses. La construction de bases ou dictionnaires permettant de révéler les structures de faible dimension de ces données est une composante importante de la statistique en grande dimension.
  2. En première approche, la recherche de ces structures de faible dimension semble nécessiter le lancement d’une recherche combinatoire dans un espace de grande dimension. De telles procédures ne peuvent pas être utilisées en pratique. Une composante importante de la statistique en grande dimension est alors de proposer et d’analyser des algorithmes qui peuvent être implémentés même dans des espaces de grande dimension. Pour cela, deux approches ont reçu une attention particulière : la relaxation convexe (couplé à la boîte à outils de l’optimisation convexe) et les algorithmes itératifs qui permettent de résoudre parfois des problèmes d’optimisation non-convexe.
  3. Finalement, la troisième composante est le rôle joué par l’aléatoire dans la statistique en grande dimension. Il s’avère que les structures de faibles dimensions sont généralement révélées par des objets aléatoires et que, jusqu’à maintenant, on ne sait pas exhiber ces structures à l’aide de mesures déterministes aussi efficacement que le font, par exemple, les matrices aléatoires.

Descriptif du cours

Un cours de statistiques en grande dimension peut donc couvrir plusieurs pans des mathématiques dont la théorie de l’approximation, l’optimisation convexe et les probabilités. Dans ce cours, nous étudierons principalement l’aspect algorithmique et probabiliste de cette théorie. La théorie de l’approximation ne sera que très brièvement abordée au travers de l’exemple des images.

Ce cours abordera le paradigme de la statistique en grande dimension principalement autour de trois thématiques :

  1. problème de reconstruction exacte et approchée d’un signal de grande dimension à partir d’un petit nombre de mesures linéaires de ce vecteur sachant qu’il a un petit support;
  2. complétion de matrice / système de recommandation : comment compléter une matrice à partir de l’observation d’un petit nombre de ses entrées sachant que cette matrice est de faible rang;
  3. détection de communauté dans les graphes : trouver les sous-graphes de forte densité dans des ‘grands’ graphes.

Nous abordons donc le problème de la statistique en grande dimension au travers de trois objets/ types de données clefs pour la science des données : les vecteurs de grande dimension mais parcimonieux, les matrices de grande taille mais de faible rang et finalement, les graphes de ‘grande’ taille dont les noeuds sont organisés en communautés.

Le problème de Compressed Sensing sera utilisé comme le principale vecteur pédagogique pour l’apprentissage des trois idées clefs de la statistique en grandes dimensions mentionnés précédemment. On y consacrera donc 8 séances divisées comme suit : 5 séances de cours, 2 séances d’exercices et 1 séances de pratiques informatiques. Puis nous consacrerons les 4 dernières séances aux problèmes de complétion de matrices et de détection de communautés: 1 séance de cours/exercices et 1 séance d’informatique pour chacune des deux thématiques.

D’un point de vue des techniques mathématiques nous mettrons l’accent sur les thématiques suivantes :

  1. concentration de variables aléatoires et calcul de complexité;
  2. méthodes et analyse d’algorithmes en optimisation convexe.

Les séances de travaux pratiques informatiques s’effectueront en Python. On mettra particulièrement l’accent sur les librairies sklearn, cvxopt/cvxpy et networkx.

Prérequis : pas de prérequis à l’exception des connaissances élémentaires en algèbre des matrices, analyse convexe et probabilités.

Note finale : 1 mémoire sous forme de texte ou de notebook python commenté + soutenance par binôme.