Noyaux De Mots Et D’arbres : Efficacité Et Unification

Résumé: L'apprentissage automatique fait appel à des méthodes intelligentes d'analyse de données qui consistent à extraire automatiquement de l'information significative à partir des collections de données massives. Cependant, les méthodes classiques d'apprentissage automatique sont des méthodes linéaires. Elles sont souvent très bien adaptées à des documents plats. Dans la pratique, de nombreuses applications disposent de données qui peuvent être représentées naturellement sous une forme structurée (séquences, arbres, graphes, ...). Les méthodes à noyaux constituent des approches efficaces disposant d'un fondement théorique solide pour prendre en charge ce type de données. Ils ont été largement utilisés pour l'apprentissage automatique à partir des données structurées. L'objectif de notre travail est double. En premier lieu, nous nous sommes focalisés sur l'aspect efficacité, qui est une propriété clé des méthodes à noyaux. Dans cette perspective nous avons ciblé le noyau sous-séquence de mots (string subsequence kernel, SSK), qui est utilisé avec succès dans plusieurs tâches de l'apprentissage automatique. L'idée de base de notre approche consiste à réduire le calcul du noyau SSK à un problème géométrique. Plus précisément, nous avons fait appel à un arbre d'intervalles en couches (layered range tree, LRT) dont nous avons appliqué les algorithmes de géométrie calculatoires correspondants. Dans une perspective d'améliorer notre approche, nous avons étendu la structure de données arbre d'intervalles en couches (LRT) à un arbre d'intervalles de sommation en couches (layered Range Sum Tree, LRST) doté des opérations d'agrégation. De même, nous avons présenté des évaluations empiriques de l'approche étendue, à la fois sur des données synthétiques et des données d'articles de presse. les résultats ont montré l'efficacité de notre approche pour l'alphabet de grande taille, sauf pour les mots de très petites tailles. Le second objectif de la thèse consiste à contribuer au développement d'une théorie d'unification de l'apprentissage automatique. En fait, dans les dernières années, un effort important a été consacré aux noyaux de séquences en se concentrant sur des problèmes individuels conduisant, ainsi, à une variété d'approches. Dans ce contexte, nous avons proposé une plate forme générale qui s'occupe de l'évaluation des noyaux de séquences. En effet, la projection d'un mot s dans un espace de redescription de haute dimension peut être modélisé par une série formelle réalisée par un automate pondéré (weighted automaton, WA) As représentant toutes les sous séquences de s. Le calcul du noyau toutes sous-séquences K(s,t) entre deux mots s et t est le comportement de l'automate pondéré A_s,t l'intersection des deux automates As et At. Pour une évaluation efficace d'un tel noyau, nous avons proposé une nouvelle technique d'intersection d'automates (intersection par anticipation). les résultats des expérimentations ont révélé que l'évaluation du noyau toutes sous-séquences utilisant notre technique est plus rapide que celle utilisant l'intersection standard. De plus, en utilisant le formalisme des automates pondérés, nous avons pu créer un nouveau noyau d'un ensemble de séquences qui peut être vu comme un noyau d'arbre.

Publié dans la revue: