Cette thèse présente le résultat de plusieurs années de recherche dans le domaine de la génération automatique de résumés. Trois contributions majeures, présentées sous la forme d'articles publiés ou soumis pour publication, en forment le coeur. Elles retracent un cheminement qui part des méthodes par extraction en résumé jusqu'aux méthodes par abstraction. L'expérience HexTac, sujet du premier article, a d'abord été menée pour évaluer le niveau de performance des êtres humains dans la rédaction de résumés par extraction de phrases. Les résultats montrent un écart important entre la performance humaine sous la contrainte d'extraire des phrases du texte source par rapport à la rédaction de résumés sans contrainte. Cette limite à la rédaction de résumés par extraction de phrases, observée empiriquement, démontre l'intérêt de développer d'autres approches automatiques pour le résumé. Nous avons ensuite développé un premier système selon l'approche Fully Abstractive Summarization, qui se situe dans la catégorie des approches semi-extractives, comme la compression de phrases et la fusion de phrases. Le développement et l'évaluation du système, décrits dans le second article, ont permis de constater le grand défi de générer un résumé facile à lire sans faire de l'extraction de phrases. Dans cette approche, le niveau de compréhension du contenu du texte source demeure insuffisant pour guider le processus de sélection du contenu pour le résumé, comme dans les approches par extraction de phrases. Enfin, l'approche par abstraction basée sur des connaissances nommée K-BABS est proposée dans un troisième article. Un repérage des éléments d'information pertinents est effectué, menant directement à la génération de phrases pour le résumé. Cette approche a été implémentée dans le système ABSUM, qui produit des résumés très courts mais riches en contenu. Ils ont été évalués selon les standards d'aujourd'hui et cette évaluation montre que des résumés hybrides formés à la fois de la sortie d'ABSUM et de phrases extraites ont un contenu informatif significativement plus élevé qu'un système provenant de l'état de l'art en extraction de phrases. / This Ph.D. thesis is the result of several years of research on automatic text summarization. Three major contributions are presented in the form of published and submitted papers. They follow a path that moves away from extractive summarization and toward abstractive summarization. The first article describes the HexTac experiment, which was conducted to evaluate the performance of humans summarizing text by extracting sentences. Results show a wide gap of performance between human summaries written by sentence extraction and those written without restriction. This empirical performance ceiling to sentence extraction demonstrates the need for new approaches to text summarization. We then developed and implemented a system, which is the subject of the second article, using the Fully Abstractive Summarization approach. Though the name suggests otherwise, this approach is better categorized as semi-extractive, along with sentence compression and sentence fusion. Building and evaluating this system brought to light the great challenge associated with generating easily readable summaries without extracting sentences. In this approach, text understanding is not deep enough to provide help in the content selection process, as is the case in extractive summarization. As the third contribution, a knowledge-based approach to abstractive summarization called K-BABS was proposed. Relevant content is identified by pattern matching on an analysis of the source text, and rules are applied to directly generate sentences for the summary. This approach is implemented in a system called ABSUM, which generates very short and content-rich summaries. An evaluation was performed according to today's standards. The evaluation shows that hybrid summaries generated by adding extracted sentences to ABSUM's output have significantly more content than a state-of-the-art extractive summarizer.

Mémoire numérisé par la Division de la gestion de documents et des archives de l'Université de Montréal.

Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.

.

L'inférence grammaticale désigne le problème qui consiste à découvrir les règles de formation des phrases d'un langage, c'est-à-dire une grammaire de celui-ci. Dans le modèle d'apprentissage de Gold, les exemples fournis sont constitués uniquement des phrases appartenant au langage. L'algorithme doit fournir une grammaire qui représente le langage énuméré. Les grammaires catégorielles sont l'un des nombreux formalismes existants pour représenter des langages. Kanazawa a montré que certaines sous-classes de ces grammaires sont apprenables, mais ses résultats ne sont pas applicables directement aux langues naturelles. Sur le plan théorique, nous proposons de généraliser les résultats de Kanazawa à différents types de grammaires. Les grammaires combinatoires générales sont un modèle flexible permettant de définir des systèmes grammaticaux à base de règles de réécriture. Nous démontrons dans ce cadre que certaines classes de langages sont apprenables. Dans un souci de généralité maximale, nos résultats sont exprimés sous forme de critères sur les règles des systèmes grammaticaux considérés. Ces résultats sont appliqués à plusieurs formalismes relativement adaptés à la représentation des langues naturelles. Nous abordons également le problème de la mise en œuvre de l'apprentissage sur des données réelles. En effet, les algorithmes existants capables d'apprendre des classes de langages intéressantes sont NP-complets. Afin de contourner cet obstacle, nous proposons un cadre d'apprentissage plus souple, l'apprentissage partiel : le contexte d'utilisation est modifié dans le but d'obtenir une complexité algorithmique plus réaliste. Nous testons cette approche sur des données de taille moyenne, et obtenons des résultats relativement encourageants.

Mémoire numérisé par la Division de la gestion de documents et des archives de l'Université de Montréal

Ce travail de thèse propose une nouvelle approche au traitement des langues naturelles. Plutôt qu'essayer d'estimer directement la probabilité d'une phrase quelconque, nous identifions des structures syntaxiques dans le langage, qui peuvent être utilisées pour modifier et créer de nouvelles phrases à partir d'un échantillon initial. L'étude des structures syntaxiques est accomplie avec des ensembles de substitution Markoviens, ensembles de chaînes de caractères qui peuvent être échangées sans affecter la distribution. Ces ensembles définissent des processus de substitution Markoviens qui modélisent l'indépendance conditionnelle de certaines chaînes vis-À-Vis de leur contexte. Ce point de vue décompose l'analyse du langage en deux parties, une phase de sélection de modèle, où les ensembles de substitution sont sélectionnés, et une phase d'estimation des paramètres, où les fréquences pour chaque ensemble sont estimées. Nous montrons que ces processus constituent des familles exponentielles quand la structure du langage est fixée. Lorsque la structure du langage est inconnue, nous proposons des méthodes pour identifier des ensembles de substitution à partir d'un échantillon, et pour estimer les paramètres de la distribution. Les ensembles de substitution ont quelques relations avec les grammaires hors-Contexte, qui peuvent être utilisées pour aider l'analyse. Nous construisons alors des dynamiques invariantes pour les processus de substitution. Elles peuvent être utilisées pour calculer l'estimateur du maximum de vraisemblance. En effet, les processus de substitution peuvent être vus comme la limite thermodynamique de la mesure invariante d'une dynamique de crossing-Over. / This thesis proposes a new approach to natural language processing. Rather than trying to estimate directly the probability distribution of a random sentence, we will detect syntactic structures in the language, which can be used to modify and create new sentences from an initial sample.The study of syntactic structures will be done using Markov substitute sets, sets of strings that can be freely substituted in any sentence without affecting the whole distribution. These sets define the notion of Markov substitute processes, modelling conditional independence of certain substrings (given by the sets) with respect to their context. This point of view splits the issue of language analysis into two parts, a model selection stage where Markov substitute sets are selected, and a parameter estimation stage where the actual frequencies for each set are estimated.We show that these substitute processes form exponential families of distributions, when the language structure (the Markov substitute sets) is fixed. On the other hand, when the language structure is unknown, we propose methods to identify Markov substitute sets from a statistical sample, and to estimate the parameters of the distribution. Markov substitute sets show some connections with context-Free grammars, that can be used to help the analysis. We then proceed to build invariant dynamics for Markov substitute processes. They can among other things be used to effectively compute the maximum likelihood estimate. Indeed, Markov substitute models can be seen as the thermodynamical limit of the invariant measure of crossing-Over dynamics.

L’apprentissage structuré est devenu omniprésent dans le traitement automatique des langues naturelles. De nombreuses applications qui font maintenant partie de notre vie telles que des assistants personnels, la traduction automatique, ou encore la reconnaissance vocale, reposent sur ces techniques. Les problèmes d'apprentissage structuré qu’il est nécessaire de résoudre sont de plus en plus complexes et demandent de prendre en compte de plus en plus d’informations à des niveaux linguistiques variés (morphologique, syntaxique, etc.) et reposent la question du meilleurs compromis entre la finesse de la modélisation et l’exactitude des algorithmes d’apprentissage et d’inférence. L’apprentissage par imitation propose de réaliser les procédures d’apprentissage et d’inférence de manière approchée afin de pouvoir exploiter pleinement des structures de dépendance plus riches. Cette thèse explore ce cadre d’apprentissage, en particulier l’algorithme SEARN, à la fois sur le plan théorique ainsi que ses possibilités d’application aux tâches de traitement automatique des langues, notamment aux plus complexes telles que la traduction. Concernant les aspects théoriques, nous présentons un cadre unifié pour les différentes familles d’apprentissage par imitation, qui permet de redériver de manière simple les propriétés de convergence de ces algorithmes; concernant les aspects plus appliqués, nous utilisons l’apprentissage par imitation d’une part pour explorer l’étiquetage de séquences en ordre libre; d’autre part pour étudier des stratégies de décodage en deux étapes pour la traduction automatique. / Structured learning has become ubiquitousin Natural Language Processing; a multitude ofapplications, such as personal assistants, machinetranslation and speech recognition, to name just afew, rely on such techniques. The structured learningproblems that must now be solved are becomingincreasingly more complex and require an increasingamount of information at different linguisticlevels (morphological, syntactic, etc.). It is thereforecrucial to find the best trade-off between the degreeof modelling detail and the exactitude of the inferencealgorithm. Imitation learning aims to perform approximatelearning and inference in order to better exploitricher dependency structures. In this thesis, we explorethe use of this specific learning setting, in particularusing the SEARN algorithm, both from a theoreticalperspective and in terms of the practical applicationsto Natural Language Processing tasks, especiallyto complex tasks such as machine translation.Concerning the theoretical aspects, we introduce aunified framework for different imitation learning algorithmfamilies, allowing us to review and simplifythe convergence properties of the algorithms. With regardsto the more practical application of our work, weuse imitation learning first to experiment with free ordersequence labelling and secondly to explore twostepdecoding strategies for machine translation.

.

L'accroissement explosif des connaissances dans le domaine médical et l'inflation textuelle et multilingue, notamment sur le Web, confèrent à l'accès, l'exploitation ou la traduction de ces informations un enjeu important. Ces traitements nécessitent des ressources lexicales multilingues qui font partiellement défaut. L'actualisation de ces ressources multilingues est donc une problématique clé dans l'accès à ces informations. Les travaux présentés ici ont été réalisés dans le cadre de l'extraction de lexique bilingue spécialisé à partir de textes médicaux comparables. L'objectif est d'évaluer et de proposer un outil d'aide à l'actualisation de lexique bilingue spécialisé et à la recherche d'information translangue en s'appuyant sur l'exploitation de ressources bilingues provenant du Web dans le domaine médical. Nous présentons un modèle fondé sur l'analyse distributionnelle en introduisant à cette occasion une nouvelle notion que nous nommons symétrie distributionnelle. En général, les modèles classiques d'extraction de lexique bilingue à partir de corpus comparables établissent la relation de traduction entre deux mots en calculant la ressemblance entre leurs distributions d'une langue vers l'autre (par exemple, du français vers l'anglais). L'hypothèse de symétrie distributionnelle postule que la ressemblance des distributions de deux mots dans les deux directions de langues est un critère fort du lien traductionnel entre ces mots. Deux grandes applications de ce modèle ont été expérimentées afin de le valider. Il s'agit de l'extraction d'un lexique bilingue médical (français-anglais) et de la recherche d'information translangue. Dans le cas de l'extraction lexicale bilingue, les résultats montrent que la prise en compte de la symétrie distributionnelle améliore la performance de manière significative par rapport aux modèles classiques. Dans le cas de la recherche d'information translangue, notre modèle a été appliqué pour traduire et étendre les requêtes. Les résultats montrent que lorsque les propositions de traduction ou d'extension sont supervisées par l'utilisateur, il améliore la recherche d'information par rapport à une traduction basée sur un dictionnaire initial.