Approximation stochastique dans les espaces de Hilbert.

Résumé L'objectif de l'apprentissage automatique supervisé est d'inférer des relations entre un phénomène que l'on cherche à prédire et des variables "explicatives". À cette fin, de multiples occurrences du phénomène sont observées, à partir desquelles une règle de prédiction est construite. Les deux dernières décennies ont vu l'apparition de très grands ensembles de données, tant en termes de nombre d'observations (par exemple, en analyse d'images) qu'en termes de nombre de variables explicatives (par exemple, en génétique). Cela a soulevé deux défis : premièrement, éviter l'écueil de l'ajustement excessif, en particulier lorsque le nombre de variables explicatives est beaucoup plus élevé que le nombre d'observations, et deuxièmement, faire face aux contraintes de calcul, par exemple lorsque la simple résolution d'un système linéaire devient une difficulté en soi. Les algorithmes qui prennent leurs racines dans les méthodes d'approximation stochastiques s'attaquent à ces deux difficultés simultanément : ces méthodes stochastiques réduisent considérablement le coût de calcul, sans dégrader la qualité de la règle de prédiction proposée, et elles peuvent naturellement éviter le surajustement. En conséquence, le cœur de cette thèse sera l'étude des méthodes de gradient stochastiques. Les méthodes paramétriques populaires donnent des prédicteurs qui sont des fonctions linéaires d'un ensemble de variables explicatives. Cependant, elles aboutissent souvent à une approximation imprécise de la structure statistique sous-jacente. Dans le cadre non-paramétrique, qui est primordial dans cette thèse, cette restriction est levée. La classe de fonctions à partir de laquelle le prédicteur est proposé dépend des observations. En pratique, ces méthodes ont des objectifs multiples, et sont essentielles pour l'apprentissage avec des données non vectorielles, qui peuvent être mappées sur un vecteur dans un espace fonctionnel en utilisant un noyau défini positif. Cela permet d'utiliser des algorithmes conçus pour des données vectorielles, mais nécessite de faire l'analyse dans l'espace associé non paramétrique : l'espace de Hilbert à noyau reproducteur. De plus, l'analyse de la régression non-paramétrique apporte également un éclairage sur le cadre paramétrique lorsque le nombre de prédicteurs est beaucoup plus grand que le nombre d'observations. La première contribution de cette thèse est de fournir une analyse détaillée de l'approximation stochastique dans le cadre non-paramétrique, précisément dans les espaces de Hilbert à noyau reproducteur. Cette analyse prouve des taux de convergence optimaux pour l'algorithme de descente de gradient stochastique moyenné. Comme nous prenons soin d'utiliser des hypothèses minimales, elle s'applique à de nombreuses situations, et couvre à la fois les situations dans lesquelles le nombre d'observations est connu a priori, et les situations dans lesquelles l'algorithme d'apprentissage fonctionne en ligne. La deuxième contribution est un algorithme basé sur l'accélération, qui converge à une vitesse optimale, tant du point de vue de l'optimisation que du point de vue statistique. Dans le cadre non-paramétrique, cela peut améliorer le taux de convergence jusqu'à l'optimalité, même dans des régimes particuliers pour lesquels le premier algorithme reste sous-optimal. Enfin, la troisième contribution de la thèse consiste en une extension du cadre au-delà de la perte des moindres carrés. L'algorithme de descente de gradient stochastique est analysé comme une chaîne de Markov. Ce point de vue conduit à une interprétation intuitive et perspicace, qui souligne les différences entre le cadre quadratique et le cadre plus général. Une méthode simple permettant de prouver l'amélioration de la convergence est ensuite proposée.