DO Trinh Minh Tri

doctorant à Sorbonne Université
Équipe : MALIRE
https://lip6.fr/Trinh-Minh-Tri.Do

Direction de recherche : Thierry ARTIÈRES

Méthode des plans sécants pour des problèmes d'apprentissage à grand échelle avec une application à l'apprentissage de modèle de Markov cachée par maximisation de la marge

L'apprentissage automatique est souvent posé sous la forme d'un problème d'optimisation où l'on cherche le meilleur modèle parmi une famille de modèle paramétré par optimisation d'une fonction réelle de l'ensemble des paramètres. Le meilleur modèle est défini comme celui qui correspond à une l'ensemble de paramètres qui minimise cette fonction objective appelée critère. De nombreux cas d'apprentissage se ramènent à un problème d'optimisation sans contraintes pour lequel de nombreuses techniques d'optimisation standards peuvent être utilisées. La régression logistique ou les champs de Markov conditionnels sont des exemples bien connus de ce cadre dans le domaine de l'apprentissage automatique. Souvent le critère à optimiser consiste en l'addition de deux termes, un terme d'adéquation aux données (le risque empirique) et un terme dit de régularisation. La stratégie du structural risk minimisation (Vapnik and Chervonenkis, 1974) vise en particulier à trouver un modèle paramétré qui réalise un bon compromis entre la minimisation du risque empirique et la capacité de généralisation en minimisant (une borne supérieure du) risque empirique régularisé.
D'autres critères donnent lieu à un cadre d'optimisation plus complexe. Par exemple l'apprentissage par maximisation de la marge, initialement proposé pour les machines à vecteur de support (Boser et al., 1992), se traduit par un problème d'optimisation avec des contraintes qui est généralement résolu dans sa forme duale via des algorithmes de programmation quadratique. Egalement, des travaux récents ont montré qu'il est possible de considérer ce problème d'apprentissage dans sa forme primale comme un problème d'optimisation sans contraintes, avec des avantages en termes de complexité dans le cas de sorties complexes et structurées (par exemple des séquences, des arbres, etc).
Les travaux présentés dans cette thèse ont été développés à partir d'une motivation initiale de développement d'algorithmes d'apprentissage efficaces pour la prédiction de sorties structurées, et en particulier pour des tâches d'étiquetage de séquences et signaux telles que l'écriture manuscrite ou la parole. Nous nous sommes focalisés sur l'apprentissage discriminant, en exploitant notamment le critère de maximisation de la marge, de systèmes pour le traitement de signaux. Nous avons proposé dans un premier temps quelques systèmes discriminants pour l'étiquetage de séquences. Ces travaux préliminaires ont permis de mettre en avant certaines limitations des approches standards. En particulier nous n'avons pas réussi à développer un système discriminant performant qui passe à l'échelle, nécessaire pour le développement d'applications réelles. Ce constat nous a conduit à travailler sur des algorithmes d'optimisation rapides et capables de traiter des fonctions objectifs non partout différentiables (ce que l'on obtient par exemple en utilisant un critère de marge) et éventuellement non-convexes (afin de se restreindre le moins possible a priori dans le choix des modèles). Dans cette optique nous avons choisi de travailler sur des algorithmes d'optimisation non contrainte, que nous voyons comme une approche prometteuse pour traiter des problèmes à grande échelle. Bien entendu l'ensemble de nos travaux théoriques ont trouvé des applications naturelles, on peut en imaginer d'autres encore qui constituent les perspectives applicatives de cette thèse.
Les contributions de cette thèse sont présentées en deux parties. La première partie présente nos travaux sur l'optimisation non contrainte. La seconde partie décrit les systèmes que nous avons développés pour l'apprentissage discriminant de modèles graphiques pour l'étiquetage de signaux et séquences, en nous appuyant lorsque nécessaire sur les algorithmes décrits dans la première partie.
Nous avons fondé nos travaux sur les algorithmes d'optimisation sur la méthode des plans sécants, où l'on cherche une approximation raisonnable de la fonction objective en utilisant des plans sécants, où un plan sécant d'une fonction est une approximation de Taylor au 1er ordre de cette fonction.
Dans un premier temps, nous considérons le cas simple de fonctions convexes et non partout différentiables pour lequel nous avons proposé une variante améliorée, plus rapide, d'une approche proposée récemment et nommée Convex Regularized Bundle Method (CRBM), qui permet de minimiser efficacement n'importe quelle fonction convexe régularisée. En particulier, nous avons fourni une analyse théorique détaillée qui montre que notre méthode hérite de la vitesse de convergence linéaire de la méthode CRBM (en nombre d'itérations), mais en limitant la mémoire nécessaire de l'algorithme ce qui réduit notablement les coûts algorithmiques. Nous avons appliqué cette méthode pour l'apprentissage de Machines à Vecteurs Supports (MVS) linéaires et montré que notre méthode se compare avantageusement, en termes de qualité et de vitesse de convergence, aux méthodes de l'état de l'art sur des base de données de référence.
Ensuite, nous considérons le cas de l'optimisation de fonctions non-convexes et non partout différentiables, qui est bien sur plus difficile mais qui offre un champs d'application bien plus large également. Nous avons proposé dans ce cadre une nouvelle méthode d'optimisation pour la minimisation de fonctions objectives non-convexes régularisées. Cette méthode est basée sur des idées similaires à celles utilisées dans le cas convexe, et en particulier sur l'utilisation de plans sécants. Nous fournissons des résultats théoriques partiels mais néanmoins intéressants sur les propriétés de convergence de la méthode, en termes de vitesse et en termes de qualité de la convergence. Nous présentons également des variantes de notre méthode et montrons notamment que celle-ci peut être accélérée en pratique par l'introdiction d'une procédure de recherche linéaire. Au final nous montrons expérimentalement la différence de comportement de notre méthode par rapport à des méthodes de référence pour l'optimisation non convexe.
Dans la partie applicative, nous considérons l'apprentissage des modèles graphiques pour l'étiquetage de séquences et de signaux comme l'écriture manuscrite et la parole. Ces travaux visent à étendre les approches majeures proposées pour la prédiction de sorties structurée comme les champs de Markov conditionnels et les champs de Markov à maximum de marge au traitement du signal. Nous explorons dans un premier temps l'adaptation des champs de Markov conditionnels pour des données de type signal, c'est à dire des séquences d'observations complexes et non linéairement séparables, multi modales, pour lesquelles l'information segmentale est majeure, et dans un cadre d'apprentissage partiellement étiqueté.
Ensuite, nous considérons l'apprentissage par maximisation de la marge de Modèles de Markov Cachés Gaussiens (GHMM ou MMC), qui constituent la modélisation de référence en traitement du signal et de la parole. Il s'agit d'un cadre d'apprentissage prometteur car les MMCs sont généralement appris par maximisation de vraisemblance, donc en mode non discriminant. Mais c'est un problème difficile pour lequel aucune approche n'existe aujourd'hui, les travaux précédents sur ce sujet sont le plus souvent basés sur de fortes hypothèses simplificatrices. Dans nos travaux, en formalisant le problème d'apprentissage comme une minimisation d'une fonction objectif non-convexe régularisée, nous pouvons exploiter nos outils d'optimisation décrits dans la première partie pour résoudre efficacement ce problème difficile. Notre approche été validée sur deux bases de données internationales en reconnaissance de la parole et en reconnaissance d'écriture manuscrite.

Soutenance : 17/06/2010

Membres du jury :

Prof. Thierry ARTIÈRES
Prof. Matthieu CORD
Prof. Patrick GALLINARI
Dr. Gunnar RATSCH (Rapporteur)
Prof. Gerhard RIGOLL
Dr. Jean-Philippe VERT (Rapporteur)

Date de départ : 30/09/2010

Publications 2005-2012