De nos jours, il n'est pas rare d'utiliser des logiciels capables d'avoir une conversation, d'interagir avec nous (systèmes questions/réponses pour les SAV, gestion d'interface ou simplement Intelligence Artificielle - IA - de discussion). Ceux-ci doivent comprendre le contexte ou réagir par mot-clefs, mais générer ensuite des réponses cohérentes, aussi bien au niveau du sens de la phrase (sémantique) que de la forme (syntaxe). Si les premières IA se contentaient de phrases toutes faites et réagissaient en fonction de mots-clefs, le processus s'est complexifié avec le temps. Pour améliorer celui-ci, il faut comprendre et étudier la construction des phrases. Nous nous focalisons sur la syntaxe et sa modélisation avec des grammaires catégorielles. L'idée est de pouvoir aussi bien générer des squelettes de phrases syntaxiquement correctes que vérifier l'appartenance d'une phrase à un langage, ici le français (il manque l'aspect sémantique). On note que les grammaires AB peuvent, à l'exception de certains phénomènes comme la quantification et l'extraction, servir de base pour la sémantique en extrayant des λ-termes. Nous couvrons aussi bien l'aspect d'extraction de grammaire à partir de corpus arborés que l'analyse de phrases. Pour ce faire, nous présentons deux méthodes d'extraction et une méthode d'analyse de phrases permettant de tester nos grammaires. La première méthode consiste en la création d'un transducteur d'arbres généralisé, qui transforme les arbres syntaxiques en arbres de dérivation d'une grammaire AB. Appliqué sur les corpus français que nous avons à notre disposition, il permet d'avoir une grammaire assez complète de la langue française, ainsi qu'un vaste lexique. Le transducteur, même s'il s'éloigne peu de la définition usuelle d'un transducteur descendant, a pour particularité d'offrir une nouvelle méthode d'écriture des règles de transduction, permettant une définition compacte de celles-ci. Nous transformons actuellement 92,5% des corpus en arbres de dérivation. Pour notre seconde méthode, nous utilisons un algorithme d'unification en guidant celui-ci avec une étape préliminaire de clustering, qui rassemble les mots en fonction de leur contexte dans la phrase. La comparaison avec les arbres extraits du transducteur donne des résultats encourageants avec 91,3% de similarité. Enfin, nous mettons en place une version probabiliste de l'algorithme CYK pour tester l'efficacité de nos grammaires en analyse de phrases. La couverture obtenue est entre 84,6% et 92,6%, en fonction de l'ensemble de phrases pris en entrée. Les probabilités, appliquées aussi bien sur le type des mots lorsque ceux-ci en ont plusieurs que sur les règles, permettent de sélectionner uniquement le "meilleur" arbre de dérivation.Tous nos logiciels sont disponibles au téléchargement sous licence GNU GPL.

Dans ce mémoire, nous nous penchons sur les expressions polylexicales (EP) et leurs relations avec l’analyse syntaxique, la tâche qui consiste à déterminer les relations syntaxiques entre les mots dans une phrase donnée. Le défi que posent les EP dans ce contexte, par rapport aux expressions linguistiques régulières, provient de leurs propriétés parfois inattendues qui les rendent difficiles à gérer dans te traitement automatique des langues. Dans nos travaux, nous montrons qu’il est pourtant possible de profiter de ce cette caractéristique des EP afin d’améliorer les résultats d’analyse syntaxique. Notamment, avec les grammaires d’arbres adjoints (TAGs), qui fournissent un cadre naturel et puissant pour la modélisation des EP, ainsi qu’avec des stratégies de recherche basées sur l’algorithme A* , il est possible d’obtenir des gains importants au niveau de la vitesse sans pour autant détériorer la qualité de l’analyse syntaxique. Cela contraste avec des méthodes purement statistiques qui, malgré l’efficacité, ne fournissent pas de solutions satisfaisantes en ce qui concerne les EP. Nous proposons un analyseur syntaxique novateur qui combine les grammaires TAG avec La technique A*, axé sur la prédiction des EP, dont les fonctionnalités permettent des applications à grande échelle, facilement extensible au contexte probabiliste. / In this thesis, we focus on multiword expressions (MWEs) and their relationships with syntactic parsing. The latter task consists in retrieving the syntactic relations holding between the words in a given sentence. The challenge of MWEs in this respect is that, in contrast to regular linguistic expressions, they exhibit various irregular properties which make them harder to deal with in natural language processing. In our work, we show that the challenge of the MWE-related irregularities can be turned into an advantage in practical symbolic parsing. Namely, with tree adjoining grammars (TAGs), which provide first-cLass support for MWEs, and A* search strategies, considerable speed-up gains can be achieved by promoting MWE-based analyses with virtually no loss in syntactic parsing accuracy. This is in contrast to purely statistical state-of-the-art parsers, which, despite efficiency, provide no satisfactory support for MWEs. We contribute a TAG-A* -MWE-aware parsing architecture with facilities (grammar compression and feature structures) enabling real-world applications, easily extensible to a probabilistic framework.

Les systèmes distribués modernes à large-échelle évoluent dans des contextes variables soumis à de nombreux aléas auxquels ils doivent s'adapter dynamiquement. Dans ce cadre, l'informatique autonome se propose de réduire les interventions humaines lentes et coûteuses, en leur préférant l'auto-gestion. Elle repose avant tout sur une description adéquate de ses composants, de leurs interactions et des différents aspects ou topologies qu'il peut adopter. Diverses approches de modélisation ont étés proposées dans la littérature, se concentrant en général sur certains du système dynamique et ne permettent ainsi pas de répondre à chacune des problématiques inhérentes à l'auto-gestion. Cette thèse traite de la modélisation basée graphes des systèmes dynamiques et de son adéquation pour la mise en œuvre des quatre propriétés fondamentales de l'informatique. Elle propose quatre principales contributions théoriques et appliquées. La première est une méthodologie pour la construction et la caractérisation générative de transformations correctes par construction dont l'application préserve nécessairement la correction du système. La seconde contribution consiste en une extension des systèmes de réécriture de graphe permettant de représenter, mettre à jour, évaluer et paramétrer les caractéristiques d'un système aisément et efficacement. Une étude expérimentale extensive révèle un net gain d'efficacité vis à vis de méthodes classiques. Les deux dernières contributions s'articulent autour de l'élaboration de deux modules de gestions visant : (1) des requêtes de traitement d'événements complexes et (2) tout système Machine-à-Machine se conformant au standard ETSI M2M. / Modern, large-scale systems are deployed in changing environments. They must dynamically adapt to context changes. In this scope, autonomic computing aims at reducing slow and costly human interventions, by building self-managed systems. Self-adaptability of a system is primarily based on a suitable description of its components, their interactions and the various states it can adopt. Various modeling approaches have been elaborated. They usually focus on some aspects or properties of dynamic systems and do not tackle each of self-management's requirements. This manuscript deals with graph-based representations of dynamic systems and their suitability for the implementation of autonomic computing's four fundamental properties : self-optimization, self-protection, self-healing and self-configuring. This thesis offers four principal theoretical and applied contributions. The first one is a methodology for the construction and generative characterization of transformations correct by construction whose application necessarily preserves a system's correctness. The second one consists in an extension of graph rewriting systems allowing to easily and efficiently represent, update, evaluate and configure a system's characteristics. An experimental study reveals a significant efficiency gain with regard to classical methods. The two lasts contribution are articulated around the design of two autonomic managers driving: (1) complex events processing requests and (2) any Machine-to-Machine system complying to the ETSI M2M2 standard.

Cette thèse explore l'usage des Grammaires Categorielles Abstraites (CGA) pour la Génération Automatique de Texte (GAT) dans un contexte industriel. Les systèmes GAT basés sur des théories linguistiques ont un long historique, cependant ils sont relativement peu utilisés en industrie, qui préfère les approches plus "pragmatiques", le plus souvent pour des raisons de simplicité et de performance. Cette étude montre que les avancées récentes en linguistique computationnelle permettent de concilier le besoin de rigueur théorique avec le besoin de performance, en utilisant CGA pour construire les principaux modules d'un système GAT de qualité industrielle ayant des performances comparables aux méthodes habituellement utilisées en industrie. / This thesis explores the usage of Abstract Categorial Grammars (ACG) for Natural Language Generation (NLG) in an industrial context. While NLG system based on linguistic theories have a long history, they are not prominent in industry, which, for the sake of simplicity and efficiency, usually prefer more ``pragmatic" methods. This study shows that recent advances in computational linguistics allow to conciliate the requirements of soundness and efficiency, by using ACG to build the main elements of a production grade NLG framework (document planner and microplanner), with performance comparable to existing, less advanced methods used in industry

La thèse s'intéresse au problème de l'analyse syntaxique pour les langages de programmation. Si ce sujet a déjà été traité à maintes reprises, et bien que des outils performants pour la génération d'analyseurs syntaxiques existent et soient largement employés, l'implémentation de la partie frontale d'un compilateur reste encore extrêmement complexe.<br /><br />Ainsi, si le texte d'un programme informatique se doit de n'avoir qu'une seule interprétation possible, l'analyse des langages de programmation, fondée sur une grammaire algébrique, est, pour sa part, le plus souvent non déterministe, voire ambiguë. Confrontés aux insuffisances des analyseurs déterministes traditionnels, les développeurs de parties frontales se sont tournés massivement vers des techniques d'analyse générale, à même d'explorer des choix non déterministes, mais aussi au prix de la garantie d'avoir bien traité toutes les ambiguïtés grammaticales. Une difficulté majeure dans l'implémentation d'un compilateur réside alors dans l'identification (non décidable en général) et le traitement de ces ambiguïtés.<br /><br />Les techniques décrites dans la thèse s'articulent autour d'approximations des grammaires à deux fins. L'une est la génération d'a\-na\-ly\-seurs syntaxiques non canoniques, qui sont moins sensibles aux dif\-fi\-cultés grammaticales, en particulier parce qu'ils peuvent exploiter un langage algébrique non fini en guise de contexte droit pour résoudre un choix non déterministe. Ces analyseurs rétablissent la garantie de non ambiguïté de la grammaire, et en sus assurent un traitement en temps linéaire du texte à analyser. L'autre est la détection d'ambiguïté en tant que telle, avec l'assurance qu'une grammaire acceptée est bien non ambiguë quel que soit le degré d'approximation employé.

L'objectif principal de cette thèse est de développer des outils pour la reconstruction de l'environnement urbain à partir d'images. Les entrées typiques de notre travail est un ensemble d'images de façades, des empreintes au sol de bâtiments, et des modèles 3D reconstruits à partir d'images aériennes. Les principales étapes comprennent le calibrage des images,le recalage avec le modèle 3D, la récupération des informations de profondeur ainsi que la sémantique des façades.Pour atteindre cet objectif, nous utilisons des techniques du domaine de vision par ordinateur, reconnaissance de formes et de l'informatique graphique. Les contributions de notre approche sont présentés en deux parties.Dans la première partie, nous nous sommes concentrés sur des techniques de reconstruction multi-vues dans le but de récupérer automatiquement les informations de profondeur de façades à partir un ensemble des photographies non calibrées. Tout d'abord, nous utilisons la technique structure et mouvement pour calibrer automatiquement l'ensemble des photographies. Ensuite, nous proposons des techniques pour le recalage de la reconstruction avec un modèle 3D. Enfin, nous proposons des techniques de reconstruction 3d dense (stéréo multi-vues et voxel coloring) pour produire un maillage 3D texturé d'une scène d'un ensemble d'images calibrées.La deuxième partie est consacrée à la reconstruction à partir d'une seule vue et son objectif est de récupérer la structure sémantique d'une façade d'une image ortho-rectifiée. La nouveauté de cette approche est l'utilisation d'une grammaire stochastique décrivant un style architectural comme modèle pour la reconstruction de façades. nous combinons un ensemble de détecteurs image avec une méthode d'optimisation globale stochastique en utilisant l'algorithme Metropolis-Hastings. / The main goal of this thesis is to develop innovative and practicaltools for the reconstruction of buildings from images. The typical input to our workis a set of facade images, building footprints, and coarse 3d models reconstructedfrom aerial images. The main steps include the calibration of the photographs,the registration with the coarse 3d model, the recovery of depth and sematicinformation, and the refinement of the coarse 3d model.To achieve this goal, we use computer vision, pattern recognition and computergraphics techniques. Contributions in this approach are presented on two parts.In the first part, we focused on multiple view reconstruction techniques withthe aim to automatically recover the depth information of facades from a setof uncalibrated photographs. First, we use structure from motion techniques toautomatically calibrate the set of photographs. Then, we propose techniques for theregistration of the sparse reconstruction to a coarse 3d model. Finally, we proposean accelerated multi-view stereo and voxel coloring framework using graphicshardware to produce a textured 3d mesh of a scene from a set of calibrated images.The second part is dedicated to single view reconstruction and its aim is to recoverthe semantic structure of a facade from an ortho-rectified image. The novelty ofthis approach is the use of a stochastic grammar describing an architectural style asa model for facade reconstruction. we combine bottom-up detection with top-downproposals to optimize the facade structure using the Metropolis-Hastings algorithm.

De nos jours, il n’est pas rare d’utiliser des logiciels capables d’avoir une conversation, d’interagir avec nous (systèmes questions/réponses pour les SAV, gestion d’interface ou simplement Intelligence Artificielle - IA - de discussion). Ceux-ci doivent comprendre le contexte ou réagir par mot-clefs, mais générer ensuite des réponses cohérentes, aussi bien au niveau du sens de la phrase (sémantique) que de la forme (syntaxe). Si les premières IA se contentaient de phrases toutes faites et réagissaient en fonction de mots-clefs, le processus s’est complexifié avec le temps. Pour améliorer celui-ci, il faut comprendre et étudier la construction des phrases. Nous nous focalisons sur la syntaxe et sa modélisation avec des grammaires catégorielles. L’idée est de pouvoir aussi bien générer des squelettes de phrases syntaxiquement correctes que vérifier l’appartenance d’une phrase à un langage, ici le français (il manque l’aspect sémantique). On note que les grammaires AB peuvent, à l’exception de certains phénomènes comme la quantification et l’extraction, servir de base pour la sémantique en extrayant des λ-termes. Nous couvrons aussi bien l’aspect d’extraction de grammaire à partir de corpus arborés que l’analyse de phrases. Pour ce faire, nous présentons deux méthodes d’extraction et une méthode d’analyse de phrases permettant de tester nos grammaires. La première méthode consiste en la création d’un transducteur d’arbres généralisé, qui transforme les arbres syntaxiques en arbres de dérivation d’une grammaire AB. Appliqué sur les corpus français que nous avons à notre disposition, il permet d’avoir une grammaire assez complète de la langue française, ainsi qu’un vaste lexique. Le transducteur, même s’il s’éloigne peu de la définition usuelle d’un transducteur descendant, a pour particularité d’offrir une nouvelle méthode d’écriture des règles de transduction, permettant une définition compacte de celles-ci. Nous transformons actuellement 92,5% des corpus en arbres de dérivation. Pour notre seconde méthode, nous utilisons un algorithme d’unification en guidant celui-ci avec une étape préliminaire de clustering, qui rassemble les mots en fonction de leur contexte dans la phrase. La comparaison avec les arbres extraits du transducteur donne des résultats encourageants avec 91,3% de similarité. Enfin, nous mettons en place une version probabiliste de l’algorithme CYK pour tester l’efficacité de nos grammaires en analyse de phrases. La couverture obtenue est entre 84,6% et 92,6%, en fonction de l’ensemble de phrases pris en entrée. Les probabilités, appliquées aussi bien sur le type des mots lorsque ceux-ci en ont plusieurs que sur les règles, permettent de sélectionner uniquement le “meilleur” arbre de dérivation.Tous nos logiciels sont disponibles au téléchargement sous licence GNU GPL. / Nowadays, we have become familiar with software interacting with us using natural language (for example in question-answering systems for after-sale services, human-computer interaction or simple discussion bots). These tools have to either react by keyword extraction or, more ambitiously, try to understand the sentence in its context. Though the simplest of these programs only have a set of pre-programmed sentences to react to recognized keywords (these systems include Eliza but also more modern systems like Siri), more sophisticated systems make an effort to understand the structure and the meaning of sentences (these include systems like Watson), allowing them to generate consistent answers, both with respect to the meaning of the sentence (semantics) and with respect to its form (syntax). In this thesis, we focus on syntax and on how to model syntax using categorial grammars. Our goal is to generate syntactically accurate sentences (without the semantic aspect) and to verify that a given sentence belongs to a language - the French language. We note that AB grammars, with the exception of some phenomena like quantification or extraction, are also a good basis for semantic purposes. We cover both grammar extraction from treebanks and parsing using the extracted grammars. On this purpose, we present two extraction methods and test the resulting grammars using standard parsing algorithms. The first method focuses on creating a generalized tree transducer, which transforms syntactic trees into derivation trees corresponding to an AB grammar. Applied on the various French treebanks, the transducer’s output gives us a wide-coverage lexicon and a grammar suitable for parsing. The transducer, even if it differs only slightly from the usual definition of a top-down transducer, offers several new, compact ways to express transduction rules. We currently transduce 92.5% of all sen- tences in the treebanks into derivation trees.For our second method, we use a unification algorithm, guiding it with a preliminary clustering step, which gathers the words according to their context in the sentence. The comparision between the transduced trees and this method gives the promising result of 91.3% of similarity.Finally, we have tested our grammars on sentence analysis with a probabilistic CYK algorithm and a formula assignment step done with a supertagger. The obtained coverage lies between 84.6% and 92.6%, depending on the input corpus. The probabilities, estimated for the type of words and for the rules, enable us to select only the “best” derivation tree. All our software is available for download under GNU GPL licence.

Une hypothèse dominant actuellement les théories sur l’évolution des capacités syntaxiques est celle d’une spécificité humaine pour le traitement des grammaires supra-régulières. Cette hypothèse est supportée par les données comparatives actuellement disponibles, qui ne fournissent pas de démonstration non ambiguë de cette capacité chez une autre espèce. Dans cette thèse, nous avons adopté une nouvelle approche consistant à examiner si ces échecs pourraient découler de la difficulté que représente l'extraction de régularités non-adjacentes. Pour tester cette hypothèse, nous avons mené une série de quatre études chez le babouin de guinée (Papio papio) et l’humain. La première étude montre que les babouins requièrent une quantité d’exposition beaucoup plus importante que l’humain pour apprendre des associations non-adjacentes. Dans une seconde étude, les babouins ont pu généraliser des patterns basés sur une répétition adjacente ou non-adjacente d’un élément, mais ils se sont montrés davantage sensibles à ces premiers. Une troisième étude, corrélationnelle, révèle que les babouins se montrant sensibles aux régularités non-adjacentes ne sont pas ceux obtenant les meilleures performances pour l’apprentissage de dépendances adjacentes. Une dernière étude suggère que les babouins sont sensibles à une structure en miroir (impliquant des dépendances centrées-emboitées), mais pas à une structure en copie (à dépendances croisées). Ces résultats mettent au jour une importante continuité des capacités syntaxiques au sein de la lignée des primates, mais révèlent également des différences inter-spécifiques importantes dans les contraintes mnésiques pesant sur celles-ci. / A current dominant hypothesis on the evolution of syntactic abilities propose that the processing of supra-regular grammars is a unique human capacity. In support of this hypothesis, artificial grammar learning studies conducted so far do not provide unambiguous demonstration of this capacity in a non-human species. In this thesis, we adopted a new approach by studying cognitive prerequisites for supra-regular grammar processing. Our hypothesis was that these previous failures could be attributed to a bias in these species towards the exploitation of local regularities and difficulties for processing more distant relationships, rather than an inability to master supra-regular grammars. We conducted a series of experiments in Guinea baboons (Papio papio) and humans to assess this hypothesis. In a first experiment, we show that baboons need much more exposure than humans to learn non-adjacent associations. In a second study, we show that baboons can generalize patterns involving an adjacent or a non-adjacent repetition of an element, but that they are more sensitive to the former. A third, correlational, study reveal that baboons succeeding to extract non-adjacent regularities are not those showing the best performance in learning local ones. A last study suggest that baboons are sensitive to a mirror structure (involving center-embedded dependencies), but not to a copy structure (crossed dependencies). Overall, our results reveal a stronger continuity in grammar processing capacities within the primate order than previously thought, but also highlight important species differences in memory constraints.

Cette thèse porte sur le traitement du langage oral spontané dans le contexte du dialogue homme-machine. En partant du constat que l'usage de la langue orale s'écarte d'une "bonne" syntaxe de l'écrit, des méthodes de traitement particulières sont alors développées pour adresser des phénomènes grammaticaux et extragrammaricaux comme les répétitions, hésitations, auto-corrections, faux-départs, etc. Une approche de traitement des extragrammaticalitks basée sur l'analyse d'un corpus ainsi qu'un formalisme grammatical pour l'oral (Sm-TAG) sont proposés et implémentés dans trois outils : Corrector, Oasis et Navigator. Les résultats d'évaluations quantitatives et qualitatives de ces outils sont donnés et commentés.

Les travaux de cette thèse portent sur l'analyse syntaxique et sémantique de la phrase, en utilisant pour l'analyse syntaxique un formalisme grammatical lexicalisé polarisé et en prenant comme exemple les grammaires d'interaction. Dans les formalismes grammaticaux lexicalisés, les polarités permettent de contrôler explicitement la composition des structures syntaxiques. Nous exploitons d'abord le besoin de composition exprimé par certaines polarités pour définir une notion faible de réduction de grammaire applicable à toute grammaire lexicalisée polarisée. Nous étudions ensuite la première phase de l'analyse syntaxique des formalismes lexicalisés: l'étiquetage grammatical. Nous exploitons là encore le besoin de composition de certaines polarités pour concevoir trois méthodes symboliques de filtrage des étiquetages grammaticaux que nous implantons sur automate. Nous abordons enfin l'interface syntaxe-sémantique des formalismes lexicalisés. Nous montrons comment l'utilisation de la réécriture de graphes comme modèle de calcul permet concrètement d'utiliser des structures syntaxiques riches pour calculer des représentations sémantiques sous-spécifiées.