Inégalités de concentrations - structures discrètes et PGD

En théorie, l’habilitation à diriger des recherches est censée présenter une synthèse et une unification des travaux de recherche effectués. On est donc obligé de trouver un rapport intelligent entre
– les inégalités de concentration,
– les principes de grandes déviations,
– l’arbre binaire de recherche,
– les propriétés statistiques des estimateurs des indices de Sobol,
– l’existence de barycentres dans l’espace de Wasserstein,
– l’estimation de l’intensité de processus de Poisson,
– l’optimalité de l’algorithme des k-plus proches voisins,
– des problèmes de M-estimation lorsque l’on dispose de deux sources différentes de données,
– des problèmes d’estimation de probabilités de défaillance sous des hypothèses de monotonie. Il est assez facile de mettre dans une même boîte inégalités de concentration et principes de grandes déviations puisque les unes comme les autres ont pour objectif de quantifier la vitesse de convergence dans la loi forte des grandes nombres. Le lien entre les principes de grandes déviations et l’arbre binaire réside dans les objets étudiés, il s’agit de structures combinatoires discrètes venant du monde de l’informatique théorique et de la combinatoire.

Le type de résultats obtenus et les techniques de preuves permettent de relier (pas trop artificiellement) mes travaux sur les processus de Poisson et sur l’algorithme des k plus proches voisins. Ce sont des motivations industrielles qui permettent d’unifier la partie autour des indices de Sobol, celle autour de la M-estimation et celle de l’estimation de probabilités de défaillance. Finalement, on se trouve face à quatre blocs sans lien apparent (même si la partie sur l’espace de Wasserstein devrait fournir de nombreuses applications à des problèmes industriels) : – les inégalités de concentration – les principes de grandes déviations – l’arbre binaire de recherche. – l’existence de barycentres dans l’espace de Wasserstein – la notion d’analyse en composantes principales – l’estimation de l’intensité de processus de Poisson – l’optimalité de l’algorithme des k-plus proches voisins. – les propriétés statistiques des estimateurs des indices de Sobol – des problèmes de M-estimation lorsque l’on dispose de deux sources différentes de données et des problèmes d’estimation de probabilités de défaillances sous certaines contraintes de monotonie. Mis à part que l’on trouve des variables aléatoires dans chacun de mes travaux, il n’y a pas réellement de lien mathématique entre ces blocs. Le lien est tout autre. Il est à l’image de ma faç de faire de la recherche, je ne travaille jamais seul. Le choix de mes sujets de recherche est un choix humain commençant la plupart du temps devant une tasse de café. Il est donc à ce stade essentiel de préciser que ce document n’existerait pas sans le formidable travail de mes coauteurs. Nous allons donc expliquer comment ils sont apparus dans mon paysage mathématique.

La vie de chercheur commence généralement par une thèse et par un directeur de thèse qui influe sur les premières thématiques choisies. Emmanuel Rio (mon directeur de thèse) m’a mis le pied à l’étrier et m’a fait travailler sur l’un de ces thèmes de recherche – les inégalités de concentration. Nous avons travaillé d’une part sur l’amélioration des constantes dans les inégalités dites de Talagrand et d’autres part sur des inégalités de concentrations convexes [147, 151]. Ces inégalités de concentrations convexes n’étaient qu’au stade de genèse dans mes travaux de thèse et ont intéressées Nicolas Privault. Ce dernier ma gentiment proposé de continuer de travailler avec lui et son étudiante en thèse Yutao Ma sur cette thématique, ce qui nous a permis de concrétiser certaines idées présentes dans la thèse. Avant de rentrer, dans de sordides détails mathématiques, il me semble important ici de rendre hommage à Nicolas. On entend souvent parler de résultats et d’idées volés, en ce qui concerne [150] c’est tout le contraire. Début 2004, je reçois un mail de Nicolas qui me dit qu’il a lu mes travaux de thèse et me propose de travailler avec lui et Yutao sur certaines extensions de mes résultats. J’accepte, on discute deux jours ensemble à La Rochelle et quelques jours plus tard ils m’envoient une première version de [150]. A la lecture de cette première version, il est évident que Nicolas et Yutao auraient pu écrire cet article sans moi, ils ne l’ont pas fait ….

Inégalités de concentration – structures discrètes et principe de grandes déviations

Autour des inégalités de concentration

Ce chapitre rassemble d’une part les travaux effectués durant ma thèse à Versailles sous la direction d’Emmanuel, ainsi que ceux plus récents effectués à Toulouse autour des principes de grandes déviations (PGD). Les premiers résultats obtenus [147, 151] sont des inégalités de concentration pour des suprema de processus empiriques. Ces inégalités sont des généralisations des inégalités de Hoefffding, Bernstein, Bennett. Elles ont été bien comprises par Talagrand qui les a introduites dans le théorème qui suit.

Théorème 2.1.1 (Talagrand [237]). Soient X1, . . . , Xn des variables aléatoires indépendantes à valeurs dans R et F un ensemble de fonctions mesurables de R dans [−1, 1]. Alors si Z = sup{f ∈ F, Sn(f)}, il existe deux constantes positives a et b telles que pour tout t > 0, on ait

log E exp(tZ) ≤ tE(Z) + V ab−2 (e bt − bt − 1), (2.1)

La conjecture concernant les constantes est a = b = 1. En 1997, Ledoux [164] a utilisé une méthode à la logSobolev ainsi qu’un joli argument de tensorisation de l’entropie pour réobtenir les inégalités de Talagrand. En appliquant la méthode de Ledoux, Massart [176] a montré que les inégalités de Talagrand étaient valides avec a = 8 et V comme facteur variance ou a = 4 et Vn + 16E(Z) comme facteur variance. En 2002, Rio [213] a prouvé les inégalités pour des variables aléatoires i.i.d. avec a = 1, b = 3/2 et le facteur variance v = Vn+2E(Z). Puis, toujours pour des variables aléatoires i.i.d. Bousquet [50] a obtenu (2.1) avec a = b = 1 et le facteur variance v. Si l’on regarde attentivement, le résultat de Talagrand le contrôle de la transformée de Laplace n’est obtenu que pour des valeurs de t positives. Cependant, si l’on désire avoir des inégalités de déviation à gauche, il est nécessaire d’avoir des contrôles pour des valeurs négatives de t.

Autour des structures discrètes

Dans cette partie, nous allons présenter d’une part le travail effectué avec Brigitte Chauvin, Jean-François Marckert et Alain Rouaut [70] autour des arbres binaires de recherche et d’autre part les deux travaux effectués autour des grandes déviations pour des variables discrètes conditionnées, le premier en collaboration avec Fabrice Gamboa et Clémentine Prieur [111] et le second avec Agnès Lagnoux et Pierre Petit [149].

L’arbre binaire de recherche
Dans ce travail, on s’est intéressé à deux modèles classiques de processus binaires: un processus à temps discret, l’arbre binaire de recherche et un processus à temps continu, le processus de Yule.
• Un arbre binaire de recherché labellisé (ABRL) est une structure utilisée en informatique pour stocker des données ordonnées. Au temps t = 0 l’ABRL est réduit à une feuille sans label. A chaque unité de temps, un nouvel objet est inséré sur une feuille de l’arbre. Cette feuille devient alors un nœud interne et donne naissance à deux nouvelles feuilles. On va s’intéresser à la suite des arbres délabélisées (Tn)n induits par cette construction. On appellera cette suite le processus d’arbre binaire de recherche (processus ABR).
• Le processes de Yule (Tt)t est un processus à temps continu à valeur arbre binaire, dans lequel les feuilles se comportent indépendamment les unes des autres (au temps t = 0 l’arbre est réduit à une feuille). Après un temps aléatoire de loi exponentielle, une feuille a deux enfants.

Le rapport de stage ou le pfe est un document d’analyse, de synthèse et d’évaluation de votre apprentissage, c’est pour cela chatpfe.com propose le téléchargement des modèles complet de projet de fin d’étude, rapport de stage, mémoire, pfe, thèse, pour connaître la méthodologie à avoir et savoir comment construire les parties d’un projet de fin d’étude.

Table des matières

1 Introduction
2 Synthèse générale
2.1 Inégalités de concentrations – structures discrètes et PGD
2.1.1 Autour des inégalités de concentration
2.1.2 Autour des structures discrètes
2.2 Moyennes de Fréchet – barycentres sur l’espace de Wasserstein
2.2.1 Caractérisation des moyennes de Fréchets
2.2.2 A.C.P. suivant une géodésique dans l’espace de Wasserstein
2.3 Deux exemples de bornes de risques minimax
2.3.1 Algorithme des plus proches voisins en dimension finie
2.3.2 Cadre statistique. Le classifieur des plus proches voisins
2.3.3 Cas des densités uniformément minorées sur leur support
2.3.4 Cas général pour les espaces de dimension finie
2.4 Analyse de sensibilité et quantification des incertitudes
2.4.1 La problématique de la quantification des incertitudes
2.4.2 Détection de variables importantes et indices de Sobol
2.4.3 Cadre mathématique
2.4.4 Estimateur Pick-Freeze en dimension 1
2.4.5 Indices de Sobol en dimension supérieure et leur estimateur Pick-Freeze
2.4.6 Indices basés sur la distance de Cramér-von Mises
2.4.7 Une méthode générale pour construire des indices bien adaptés
2.5 Les chantiers à venir
2.5.1 A partir du travail de Janson
2.5.2 A partir du travail de Agueh et Carlier
3 Inégalités de concentration – structures discrètes et PGD
3.1 Autour des inégalités de concentration
3.1.1 Inégalités de concentration pour le supremum de processus empiriques
3.1.2 Inégalités de concentration convexe
3.2 Etude de structures aléatoires discrètes
3.2.1 L’arbre binaire de recherche
3.2.2 Théorème de Berry-Esseen et principe de grandes déviations pour des variables discrètes conditionnées
4 Moyennes de Fréchet – Barycentres sur l’espace de Wasserstein
4.1 Caractérisation des moyennes de Fréchet
4.1.1 Introduction
4.1.2 Existence et unicité du barycentre théorique
4.1.3 Barycentre pour des mesures de probabilités sur R
4.1.4 Formulation duale
4.1.5 Une caractérisation explicite du barycentre théorique
4.1.6 Une application aux modèles de déformation en statistique
4.1.7 Convergence presque sûre du barycentre empirique vers le barycentre théorique
4.1.8 Pour dépasser l’hypothèse de compacité
4.2 A.C.P. suivant une géodésique dans l’espace de Wasserstein
4.2.1 Introduction
4.2.2 A une isométrie près l’espace de Wasserstein W2(Ω) est un sous-ensemble convexe fermé de L2 µ(Ω)
4.2.3 Analyse en composantes principales convexes CPCA
4.2.4 L’analyse en composantes principales géodésiques (GPCA)
4.2.5 Exemples de GPCA dans W2(R)
4.2.6 Etude de la convergence
4.2.7 A propos de la GPCA dans W2(Ω) et de la PCA dans les sous variétés Riemanniennes
4.2.8 Appendice
5 Conclusion