Learning in Markov decision processes for structured prediction (applications to sequence labeling, tree transformation and learning for search) / Apprentissage dans les processus de décision Markoviens pour la prédiction saturée (applications à l'étiquetage de séquences, la transformation d'arbres et l'apprentissage dans les problèmes de recherche combinatoire)

De nombreux problèmes d'apprentissage supervisé font intervenir des sorties complexes : séquences, arbres ou graphes. La prédiction de sorties structurées pose d'importants défis, liés à la nature combinatoire du problème.Dans cette thèse, je propose une nouvelle formulation basée sur le cadre des processus de décision Markoviens. Cette formulation permet d'utiliser des algorithmes d'apprentissage par renforcement pour traiter des problèmes particulièrement complexes qu'aucun algorithme n'était en mesure de résoudre jusqu'alors. La validation est effectuée sur deux tâches: l'étiquetage de séquences et la transformation d'arbres. Les résultats obtenus sur les séquences sont compétitifs avec l'état de l'art et pour certains significativement meilleurs. La transformation d'arbres est un des problèmes d'apprentissage statistique les plus complexes abordés à ce jour. Je démontre l'efficacité de l'apprentissage par renforcement pour ce problème sur cinq jeux de données de large échelle. / PARIS-BIUSJ-Mathématiques rech (751052111) / Sudoc / Sudoc / France / FR