Grammaires catégorielles abstraites pondérées

Offre de thèse

Date limite de candidature

13-05-2024

Date de début de contrat

01-10-2024

Directeur de thèse

DE GROOTE Philippe

Encadrement

Encadrement sur base de réunion hebdomadaires de suivi d'avancement en plus de celles consacrées au travail scientifique proprement dit. Participation à la vie de l'équipe (réunions, séminaires).

Type de contrat

Concours pour un contrat doctoral

Candidater à cette offre target="_blank"

école doctorale

IAEM - INFORMATIQUE - AUTOMATIQUE - ELECTRONIQUE - ELECTROTECHNIQUE - MATHEMATIQUES

équipe

SEMMAGRAMME

contexte

Le sujet proposé s'inscrit dans le projet de développement de l'utilisabilité des grammaires catégorielles abstraites, et notamment dans le cas de grammaires de grandes tailles. Les travaux théoriques ont pour but d'être à terme intégrés dans ACGtk, un outil de développement et d'utilisation de grammaires ACG.

spécialité

Informatique

laboratoire

LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications

Mots clés

informatique linguistique, théorie des langages formels, théorie des types, lambda calcul, grammaires pondérées

Détail de l'offre

L'équipe Sémagramme développe des outils théoriques et pratiques pour la modélisation et le traitement des langues naturelles. Elle porte une grande attention à la description et aux modèles des structures linguistiques comme les arbres (ou graphes) d'analyse et les représentations sémantiques. À cette fin, Sémagramme propose le formalisme des grammaires catégorielles abstraites (ACG). Il s'agit d'un cadre formel dans lequel l'encodage de différents formalismes grammaticaux, par exemple les grammaires non contextuelles, les grammaires d'arbres adjoints (TAG), peut être réalisé. Il s'appuie sur le langage des λ-termes qui généralise les langages de chaînes et d'arbres.

Ses caractéristiques principales sont: (i)un accès direct aux structures de dérivation, (ii)l'utilisation de lexiques afin de spécifier les interprétations des structures de dérivations (également appelées langage abstrait) dans des structures de surface (également appelée langage objet).

Typiquement, les langages objets sont des ensembles de &#955;-termes qui encodent des chaînes de caractères, notamment lorsqu'un souhaite analyser des expressions de la langue naturelle.

L'utilisation d'une même structure de donnée, les &#955;-termes, offre également plusieurs modes de composition de grammaires, ce qui permet une certaine modularité dans la définition et l'écriture de grammaires. Une manière habituelle de tirer partie de cette capacité est de définir une première grammaire qui surgénère puis une seconde grammaire qui contrôle les structures d'analyse de la première pour écarter les structures indésirables (par exemple, pour contrôler les arbres de dérivation dans l'encodage des TAG en ACG).

Cependant, tout comme les formalismes grammaticaux qu'elles peuvent encoder, les ACG à large couverture engendrent une très grande ambiguïté et une explosion du nombre d'analyses possibles d'une même expression. Une méthode traditionnelle de traiter ce genre de problème est d'utiliser des probabilités, ce qui a conduit par exemple au développement de grammaires non contextuelles probabilistes (pCFGs) ou à celui des grammaires d'arbres adjoints probabilistes (pTAGs). Nous avons proposé une extension avec des pondérations pour les ACGs, les wACGs. Elle s'appuie sur les ACG multitypées, et nous avons montré qu'elle permet par exemple d'encoder les modèles de Markov cachés (HMM).

L'objectif global de ce projet de thèse est d'étudier plus avant cette extension des ACG et de concevoir des algorithmes d'inférence de grammaires et des algorithmes d'analyse spécifiques.

Keywords

mathematics of language, formal language theory, type theory, lambda calculus, weighted grammars

Subject details

The Sémagramme team develops theoretical and practical tools for natural language modeling and processing. It puts a strong focus on descriptions and models of linguistic structures, such as tree or graph parse structures, and semantic representations. To this end, Sémagramme has developed the Abstract Categorial Grammar framework (ACG). It is a grammatical framework in which the encoding of different grammatical formalisms is possible, for instance context-free grammars, tree adjoining grammars (TAG), etc. It relies on languages of λ-terms, that generalize string and tree languages. Key features of ACG are: (i)a direct access to derivation structures, (ii)lexicons to specify the interpretation of derivation structures (also called abstract language) into surface structures (also called object language). Typical object languages are based on sets of &#955;-terms that encode strings, in particular when we are interested in parsing natural language expressions. Dealing with a single data structure (&#955;-terms) also allows for various grammar composition modes. This composition ability provides some kind of modularity in grammatical design. A general usage is to combine an overgenerating grammar, that can, for instance, be easily provided with a semantic dimension, and a control grammar that prunes the undesired parse structures (for instance, to control derivation trees in the TAG into ACG encoding). However, just as for the symbolic grammatical formalisms ACGs can encode, large-scale grammars exhibit a combinatorial explosion of parsing ambiguity. A widespread method to tackle this issue is to use probabilities, leading for instance to probabilistic CFGs (pCFGs) and probabilistic TAGs (pTAGs). We proposed such a weighted extension for ACGs, based on multityped ACGs and we showed that they can for instance encode hidden Markov Models (HMM). The overall goal of this PhD project is to further study this extension of the ACG framework and to design grammatical inference algorithms and dedicated parsing algorithms.

Profil du candidat

Les compétences attendues sont:
+ connaissances et intérêt pour les méthodes formelles (logique, lambda calcul, automates)
+ connaissances des méthodes stochastiques
+ intérêt pour la pluridisciplinarité, et en particulier pour la linguistique

Candidate profile

Expected skills are:
+ background in formal methods (logic, lambda calculus, automata) and interest in those topics
+ knowledge about stochastics methods
+ interest in multidisciplinary approached, and in particular in linguistics

Référence biblio

Abiteboul, Serge, Richard Hull et Victor Vianu (1995). Foundations of Databases. Assison-Wesley. url : http://webdam.inria.fr/Alice/pdfs/all.pdf.

Booth, T.L. et R.A. Thompson (1973). “Applying Probability Measures to Abstract Languages”. In : IEEE Transactions on Computers C-22.5, p. 442-450. doi : 10.1109/T-C.1973.223746.

Buszkowski, Wojciech (1987). “Discovery procedures for categorial grammar”. In : Categories, Polymorphism, and Unification. Sous la dir. d'Ewan Klein et Johan van Benthem. Edinburgh et Amsterdam : Centre for Cognitive Science, University of Edinburgh, Institute for Language, Logic, et Information, University of Amsterdam, p. 36-64.

Chiang, David (octobre 2000). “Statistical Parsing with an Automatically-Extracted Tree Adjoining Grammar”. In : Proceedings of the 38th Annual Meeting of the Association for Computational Linguistics. Hong Kong : Association for Computational Linguistics, p. 456-463. doi : 10.3115/1075218.1075276. Anthologie ACL : P00-1058.

de Groote, Philippe (juillet 2001). “Towards Abstract Categorial Grammars”. In : Proceedings of 39th Annual Meeting of the Association for Computational Linguistics, p. 148-155. doi : 10 .3115 /1073012.1073045. Anthologie ACL : 01-1033.

de Groote, Philippe (2015). “Abstract Categorial Parsing as Linear Logic Programming”. In : Proceedings of the 14th Meeting on the Mathematics of Language (MoL 2015). Chicago, United States : Association for Computational Linguistics, p. 15-25. Archive ouverte hal : hal-01188632. Anthologie ACL : W15-2302.

de Groote, Philippe et Sylvain Pogodalla (2004). “On the expressive power of Abstract Categorial Grammars : Representing context-free formalisms”. In : Journal of Logic, Language and Information 13.4, p. 421-438. doi : 10.1007/s10849-004-2114-x. Archive ouverte hal : inria-00112956.

Fülöp, Zoltán et Heiko Vogler (2009). “Weighted Tree Automata and Tree Transducers”. In : Handbook of Weighted Automata. Sous la dir. de Manfred Droste, Werner Kuich et Heiko Vogler. Berlin, Heidelberg : Springer Berlin Heidelberg, p. 313-403. doi : 10.1007/978-3-642-01492-5_9.

Joshi, Aravind K. et Yves Schabes (1997). “Tree-adjoining grammars”. In : Handbook of formal languages. Sous la dir. de Grzegorz Rozenberg et Arto K. Salomaa. T. 3. Springer. Chap. 2. doi : 10.1007/978-3-642-59126-6_2.

Kanazawa, Makoto (1998). Learnable Classes of Categorial Grammars. CSLI et FoLLI.

Kanazawa, Makoto et Sylvain Salvati (2007). “Generating Control Languages with Abstract Categorial Grammars”. In : Proceedings of the 12th conference on Formal Grammar (FG 2007). Sous la dir. de Gerald Penn. CSLI Publications. url: https://makotokanazawa.ws.hosei.ac.jp/publications/control.pdf.

Ludmann, Pierre, Sylvain Pogodalla et Philippe de Groote (septembre 2022). “Multityped Abstract Categorial Grammars and Their Composition”. In : WoLLIC 2022 - 28th International Workshop on Logic, Language, Information, and Computation. T. 13468. Lecture Notes in Computer Science.

Iaşi, Romania : Springer International Publishing, p. 105-122. doi : 10.1007/978-3-031-15298-6_7. Archive ouverte hal: hal-03781596. url : https://inria.hal.science/hal-03781596.

Manning, Christopher D. et Hinrich Schütze (1999). Foundations of Statistical Natural Language Processing. MIT Press. url : https://mitpress.mit.edu/books/foundations-statistical-natural-language-processing.

Pogodalla, Sylvain (2017). “A syntax-semantics interface for Tree-Adjoining Grammars through Abstract Categorial Grammars”. In : Journal of Language Modelling 5.3, p. 527-605. doi : 10.15398/jlm.v5i3.193. Archive ouverte hal : hal-01242154. url : https://inria.hal.science/hal-01242154.

Resnik, Philip (1992). “Probabilistic Tree-Adjoining Grammar as a Framework for Statistical Natural Language Processing”. In : COLING 1992 Volume 2 : The 14th International Conference on Computational Linguistics. doi:10.3115/992133.992135. Anthologie ACL : C92-2065.

Salomaa, Arto (1969). “Probabilistic and weighted grammars”. In : Information and Control 15.6, p. 529-544. doi : 10.1016/S0019-9958(69)90554-3.

Salvati, Sylvain (2005). “Problèmes de filtrage et problèmes d'analyse pour les grammaires catégorielles abstraites”. Thèse de doct. Institut National Polytechnique de Lorraine.

Salvati, Sylvain (2006). “Encoding second order string ACG with Deterministic Tree Walking Transducers”. In : Proceedings of The 11th conference on Formal Grammar (FG 2006). Sous la dir. de Shuly Wintner. FG Online Proceedings. Malaga, Spain : CSLI Publications, p. 143-156. url : http://cslipublications.stanford.edu/FG/2006/salvati.pdf.

Sandillon-Rezer, Noémie-Fleur (décembre 2013). “Apprentissage de grammaires catégorielles : transducteurs d'arbres et clustering pour induction de grammaires catégorielles”. Thèse de doct. Université Sciences et Technologies - Bordeaux I. Archive ouverte hal : tel-00946548. url : https://theses.hal.science/tel-00946548.

Yoshinaka, Ryo et Makoto Kanazawa (2005). “The Complexity and Generative Capacity of Lexicalized Abstract Categorial Grammars”. In : Logical Aspects of Computational Linguistics : 5th International Conference, LACL 2005, Bordeaux, France, April 28-30, 2005. Proceedings. Sous la dir. de Philippe Blache et al. T. 3492. LNCS/LNAI. Springer, p. 330-348. doi : 10.1007/11422532_22.