Ce document présente une synthèse de mes travaux de recherche. Ceux-ci se répartissent sur trois thèmes: structures aléatoires discrètes construites à partir de sources dynamiques, algorithmes de gradient stochastique et théorème de la limite centrale presque-sûr. Dans ce mémoire, je décris l'évolution de mes travaux depuis ma thèse tout en mettant en relief le fil conducteur commun. Mon travail de recherche se situe à l'intersection des systèmes dynamiques dans l'analyse statistique de séquences, de l'analyse d'algorithmes dans les arbres aléatoires et des processus stochastiques discrets. Les résultats établis ont des applications dans des domaines variés allant des séquences biologiques aux modèles de régression linéaire, processus de branchement, en passant par la statistique fonctionnelle et les estimations d'indicateurs de risque appliqués à l'assurance.
Mon travail de thèse (2003-2006) au sein de l'équipe PREVAL de l'INRIA Rocquencourt portait sur la modélisation de séquences biologiques ainsi que sur des propriétés de convergence de martingales vectorielles. L'objet de la première partie était une représentation de séquences en système dynamique par un jeu du chaos, la CGR (de l'anglais Chaos Game Representation). L'originalité tenait dans l'utilisation de cette représentation (appliquée pour la première fois aux séquences d'ADN par Jeffrey [75]) pour construire des distances permettant de quantifier des différences de structure de séquences biologiques. La masse d'information accumulée, suite aux différents séquençages d'espèces, a soulevé de nombreux problèmes de stockage: il était devenu nécessaire de développer des outils permettant de retrouver rapidement l'information pertinente dans cet amas de données. La première partie de ma thèse formalise cette représentation en jeu du Chaos et permet de répondre à la question « Comment utiliser la CGR et l'information
qu'elle contient ? ». J'ai utilisé cette représentation pour caractériser la structure de dépendance dans une séquence et pour construire des arbres taxonomiques.
L'idée principale sur laquelle reposent les preuves des résultats énoncés est d'utiliser la récursivité sous-jacente à la représentation en jeu du Chaos pour exhiber des martingales et des séries génératrices que l'on sait contrôler. Le caractère récursif de la structure étudiée est de façon beaucoup plus générale à la base de la plupart des preuves des articles que je synthétise ici; il peut se traduire en « méthodes forward » et « méthodes backward ». En décrivant l'état d'un processus à l'instant $n+1$ en fonction de son état à l'instant $n$, on peut faire apparaître des invariants, comme des martingales, en calculant des espérances conditionnelles (méthodes forward). On décompose ensuite le processus étudié en un invariant sur lequel on dispose de résultats de convergence et on contrôle le reste. Dans un raisonnement backward, on décrit la situation à l'etape $n+1$ comme reproduisant la situation à l'étape $n$.
La seconde partie de ma thèse portait sur l'étude d'arbres aléatoires, les arbres-CGR, liés à des algorithmes de compression de données. Avec Brigitte Chauvin, Nicolas Pouyanne et Stéphane Ginouillac (LMV, Université de Versailles Saint-Quentin-en-Yvelines), nous avons établi le comportement asymptotique de certains paramètres (hauteur, niveau de saturation, niveau d'insertion) d'un arbre digital de recherche construit à partir des suffixes successifs d'un même mot infini.
Les résultats obtenus utilisent tant des outils purement probabilistes (martingales liées à la construction récursive de l'arbre, inégalités de concentration, théorème de Borel-Cantelli) que des outils d'analyse complexe (comportement du di-logarithme complexe, théorème de transfert basé sur l'analyse de singularités) en lien avec certaines séries génératrices. Les arbres digitaux poussent en insérant successivement de nouveaux suffixes. La vitesse de croissance possède des liens étroits avec les propriétés des temps d'attente d'occurrences de mots ainsi que leur auto-corrélation.
Ce premier travail sur les paramètres de cet arbre-CGR a été le début d'une fructueuse coopération avec Brigitte Chauvin et Nicolas Pouyanne qui se prolonge bien au-delà du travail de thèse.
L'objet martingale étant récurrent dans mes preuves, j'ai souhaité obtenir de nouvelles propriétés de convergence pour des martingales vectorielles. Dans la dernière partie de ma thèse, en collaboration avec mes deux directeurs de thèse, Bernard Bercu (IMB, Université de Bordeaux 1) et Guy Fayolle (INRIA Rocquencourt), nous avons prouvé la convergence des moments de martingales vectorielles dans le théorème de la limite centrale presque-sûr (TLCPS). Ce travail est la généralisation au cas vectoriel de celui qu'avait obtenu Bernard Bercu [13] dans le cas scalaire. Ces propriétés sont appliquées aux erreurs cumulées d'estimation et de prédiction dans des modèles stables de type processus auto-régressifs linéaires ou processus de branchement avec immigration.
Les tests de structure markovienne d'ordre fixe et déterministe effectués dans la première partie de ma thèse m'ont amenée à travailler sur un mécanisme plus général de production de mots permettant des corrélations de longue portée entre symboles et ainsi une modélisation plus réaliste: la source dynamique. En informatique, toute information se code sous forme de texte, que ce soit un texte initialement écrit en langue naturelle, une séquence biologique (génétique, protéique), musicale, le flux de données dans un réseau ou encore une base de données. L'algorithmique du texte est une branche de l'algorithmique qui vise à un traitement efficace de ces données. Il faut construire des structures qui permettent de rechercher et trier des « mots » et de déterminer le comportement des algorithmes correspondants. Le traitement doit être fiable, rapide et ne pas prendre trop de place en mémoire. Pour une source dynamique générale, l'analyse probabiliste des structures arborescentes construites sur ses mots s'avère beaucoup plus délicate et nécessite la confrontation entre des points de vue variés et complémentaires.
En collaboration avec Brigitte Chauvin, Nicolas Pouyanne (LMV, Université de Versailles Saint-Quentin-en-Yvelines) et Frédéric Paccaut (LAMFA, Université de Picardie Jules Verne) dans les articles [23, 24], nous nous sommes intéressés à un type particulier de sources, extensions « naturelles » de chaînes de Markov: les chaînes de Markov à mémoire variable, appelées aussi VLMC (de l'anglais Variable Length Markov Chains). Les VLMC étaient déjà abondamment utilisées dans des domaines d'applications variés, mais encore mal comprises du point de vue de la théorie « analytique » de l'information. Ce modèle est un bon compromis: suffisamment général pour pouvoir représenter des sources diverses et unifier le traitement de sources naturelles (sources sans mémoire et chaînes de Markov), suffisamment structuré pour pouvoir être précisément étudié, via en particulier l'opérateur de transfert du système dynamique. Dans l'article [23] nous explicitons une source dynamique permettant de produire des VLMC. Puis, nous nous intéressons à deux exemples particuliers pour lesquels nous donnons une condition nécessaire et suffisante d'existence et unicité de mesure invariante.
La manière dont les mots sont produits a une grande influence sur le comportement probabiliste des algorithmes ou des principales structures de données arborescentes de type dictionnaire associées (arbre binaire de recherche, arbre digital, arbre des suffixes, pour la compression). Une fois de plus la structure récursive de ces algorithmes est exploitée dans nos preuves. Ces arbres aléatoires dans lesquels on stocke des données sont connus dans la littérature pour « pousser » à vitesse logarithmique en fonction du nombre de données que l'on stocke. Dans l’article [24], il y a deux exemples d'arbres explicites, des tries des suffixes, dont la hauteur ou le niveau de saturation ne grandissent pas logarithmiquement. Ces deux exemples sont construits à partir d'un mot généré par une source VLMC.
Egalement à partir d'un mot généré par une VLMC, avec Brigitte Chauvin, Samuel Herrmann (IMB, Université de Bourgogne) et Pierre Vallois (Institut Elie Cartan, Université de Lorraine) nous avons étudié la marche aléatoire construite en sommant les codages des lettres du mot. Cette marche n'est en général pas markovienne. Elle est dite persistante. On montre que renormalisée, elle converge vers un processus continu de type processus zigzag.
Lors de mon séjour au LMV, des discussions avec Mariane Pelletier m'ont donné la curiosité de me pencher sur une autre structure récursive naturelle: les algorithmes de gradient. Pour calculer un minimum ou un zéro de fonction, lorsque la fonction a de nombreux minima locaux proches les uns des autres, les algorithmes déterministes risquent de rester piégés. De plus, très souvent en modélisation, la fonction dont on cherche un zéro ou un minimum n’est connue qu’à une perturbation près. Les algorithmes stochastiques sont des estimateurs particulièrement bien adaptés en grande dimension. Mon premier article sur les algorithmes stochastiques utilise des outils développés pendant ma thèse pour établir la convergence des moments de tout ordre dans le TLCPS [2].
J'ai ensuite utilisé de tels algorithmes dans différents contextes: estimation de courbe médiane, de médiane conditionnelle, minimisation de risque sous contrainte en assurance, classification non-supervisée. Une fois encore les martingales sont bien adaptées à ces structures récursives et sont des outils précieux pour obtenir le comportement asymptotique des algorithmes.
Avec Hervé Cardot (IMB, Université de Bourgogne) et Pierre-André Zitt (LAMA, Université Paris-Est), nous avons proposé un algorithme séquentiel extrêmement rapide de type gradient stochastique pour estimer la médiane géométrique. La médiane géométrique est une extension naturelle de la médiane pour des vecteurs aléatoires à valeurs dans des espaces vectoriels normés. La médiane géométrique est, contrairement à la moyenne, robuste et donc peu sensible aux points atypiques. Il est généralement difficile de détecter de tels points lorsqu'on dispose de grands échantillons de variables à valeurs dans des espaces de grande dimension ou de dimension infinie.
Avec Hervé Cardot et Jean-Marie Monnez (Institut Elie Cartan, Université de Lorraine), nous avons ensuite développé une extension directe de cet algorithme pour la classification non supervisée en introduisant un critère de type $k$-médianes. Cet algorithme peut s'interpréter comme une variante des $k$-means (à la MacQueen).
Tous les articles autour de la médiane sont illustrés sur des courbes d'audience relevées seconde par seconde par Médiamétrie au cours d'une journée.
En collaboration avec Clémentine Prieur (LJK, Université Joseph Fourier) et Véronique Maume-Deschamps (ISFA, Université de Lyon 1), nous avons utilisé un algorithme stochastique pour estimer le minimum de certains indicateurs de risque, sous contrainte d'un capital initial fixé à partager entre les différentes filiales d'une assurance. Nous considérons des indicateurs de risque de processus vectoriels qui prennent en compte des dépendance entre les filiales ainsi que certaines dépendances temporelles. Cette minimisation correspond à une allocation de réserve optimale.
Enfin, en continuité avec le dernier chapitre de ma thèse sur le théorème de la limite centrale presque-sûr, nous avons démontré avec Khalifa Es-Sebaiy (ENSA de Marrakech, Université Cadi Ayyad) que la suite des estimateurs des moindres carrés du paramètre d’un processus d’Ornstein-Uhlenbeck fractionnaire satisfait le TLCPS. Nous avons considéré le cas d'une observation du processus à temps continu aussi bien qu'une observation discrétisée.
La première partie de ce mémoire porte sur la modélisation de séquences, les chaînes de Markov à mémoire variable ainsi que les arbres et marches aléatoires associés. Elle rassemble les travaux
[133, 19, 23, 24, 21, 28].
La seconde partie est consacrée aux algorithmes stochastiques des articles
[39, 20, 25, 26, 30, 32].
Enfin la dernière partie traite du TLCPS en rassemblant les papiers
[6, 106, 2, 27].