Sujet de thèse / PhD thesis (autres sujets)

Learning categorial grammars from annotated corpora

Acquisition de grammaires catégorielles à partir de corpus annotés

Richard Moot, Christian Retoré

richard.moot@labri.fr, christian.retore@labri.fr

sujet attribué à Noémie-Fleur Sandillon-Rezer (Université Bordeaux 1)

(English description below)

Acquisition de grammaires catégorielles à partir de corpus annotés

Mots-clés: linguistique informatique, apprentissage, inférence grammaticale, grammaires catégorielles

Les travaux de Buskowski et Penn, étendus par Kanazawa fournit un cadre simple mais efficace pour inférer une grammaire catégorielle à partir d'exemples structurés. Etant donné un ensemble d'arbres binaires dont les feuilles sont des mots et les autres noeuds portent une étiquette "droite" ou "gauche", on commence par placer le symbole "S" à la racine et on propage cette information ainsi: si le noeud courant est déjà étiqueté "X" est marqué gauche (resp. droit) on inscrit "X/Y" (resp. "Y") sur le fils gauche et "Y" (resp. "Y\X") sur le fils droit, où "Y" est une variable. Ce processus attribue à chaque mot une formule, appelée catégorie syntaxique, décrivant le comportement syntaxique du mot.

Lorsqu'on essaie de mettre en œuvre cet algorithme aux ressources annotées disponibles, on rencontre un grand nombre de difficultés:

  1. En premier lieu les annotations syntaxiques des corpus sont bien plus pauvres des arbres étiquetés requis par l'algorithme de Buszkowski et Penn.
  2. Les annotations contiennent des erreurs qui introduisent des catégories syntaxiques erronées.
  3. Bien que cet algorithme s'étende en principe à l'assignation de plusieurs catégories syntaxiques par mot — ce qui est requis pour obtenir une grammaire réaliste à partir des données disponibles — trouver une grammaires optimale a une complexité rédhibitoire.
  4. Même si on peut rempalcer les variables par des constantes issues du corpus comme "n" pour nom commu ou "np" pour groupe nominal, le lexique extrait est d'une taille prohibitive.

L'objectif de cette thèse est de trouver des solutions, possible partielles, au problèmes exquissés ci-dessus, de manière à acquérir une grammaire de qualité à partir du copus annoté de Paris VII.

L'étudiant étudiera les automates et les transductions d'arbres pour définir des outils éliminant les les erreurs d'annotations fréquentes et pour transformer les arbres du corpus en structure adaptées à ce genre d'algorithmes (en réponse aux problèmes 1 et 2). On cherche a ensuite à calculer efficacement une approximation d'une grammaire optimale (3), et à réduire la taille du lexique obtenu (4).

Prérequis

Learning categorial grammars from annotated corpora

Keywords: computational linguistics, learning, grammatical inference, categorial grammars

The work of Buszkowski and Penn, which has been extended by Kanazawa, provides a simple but effective framework to induce a categorial grammar lexicon from annotated structures. Given a set of binary trees with words as its leaves with each internal node labeled with left or right, we start by assigning "s" (for sentence) to the root node, then descend the tree assigning X/Y and Y to the two daughters (where X is the category of the parent node and Y is a category variable) in case the node is marked as "left", indicating the node one the left is looking for a node of category Y to its right to form an X. Similarly, when the node is marked "right" we assign Y and Y\X to the two daughters, with Y again a variable and with the node on the right now looking for this Y to its left. Descending the tree to its leaves gives us (partial descriptions of) the formulas assigned to the corresponding words in the lexicon.

When trying to apply this algorithm to the annotated resources which are generally at our disposition, we encounter a number of problems:

  1. First of all, the syntactic annotation provided is often rather far removed from the annotated tree structures which can serve as input to the Buszkowski and Penn algorithm and transforming the annotation of a corpus into suitable input for the algorithm generally requires effort.
  2. In addition, the annotated resources tend to contain quite a few errors in the annotation, which results in incorrect lexical categories.
  3. Though the algorithm extends in principle to the case allowing multiple formulas to be assigned to each word - which is what we need if we want to handle realistic grammars and input trees - this will make finding an "optimal" grammar for the input trees intractable.
  4. Though we can replace the use of variables in the algorithm by using constants (such as "n" for common noun and "np" for noun phrase) which are provided - at least in part - by the annotation, doing so will explode the size of the extracted lexicon.

 

The goal of this PhD project is to find at least partial solutions to the problems sketched above in a way which allows the extraction of an accurate grammar from the Paris VII annotated corpus.

The PhD student will study tree transducers and tree automata in order to find the tools necessary to correct frequent annotation errors and transform the trees into a form suitable for grammar extraction (solving problems 1 and 2) then investigate different strategies either for approximating an "optimal" lexicon in a way which is tractable (3) or for reducing the size of the extracted lexicon (4).

Prerequisite: The ideal candidate has the following profile:

Bibliographie/bibliography