Accueil > Manifestations > Thèses et HDR > Thèses > James Scicluna

James Scicluna

Directeur de thèse

Colin de la Higuera

Résumé

L’inférence grammaticale consiste à apprendre, à partir de données provenant d’un langage, une grammaire susceptible d’expliquer ou de générer le langage en question. Ce travail, concerne les grammaires incontextuelles (ou context-free) probabilistes, plus puissantes que les grammaires régulières, objet de la plupart des travaux en inférence grammaticale. L’apprentissage est non supervisé : aucune information structurelle n’est connue.

Le travail comprend un état de l’art concernant l’inférence grammaticale, les grammaires probabilistes et les classes de grammaires permettant un apprentissage distributionnel. Puis nous étudions différents problèmes de décision concernant des questions de (calculs de) distances entre distributions et nous montrons qu’en général il s’agit de problèmes indécidables. Dans un second temps nous donnons une description mathématique de la classe de grammaires qui vont nous intéresser.

Le cœur de la thèse concerne le développement de l’algorithme COMINO, de l’analyse de ses propriétés et de l’étude empirique de ses capacités. L’algorithme se déroule en trois phases : durant la première, une relation d’équivalence sur les sous-mots est calculée. Durant la seconde, un solveur est utilisé pour sélectionner un nombre minimal de classes. Enfin, les classes deviennent les nonterminaux d’une grammaire dont les poids des règles sont estimés grâce à l’échantillon. Les résultats expérimentaux témoignent de la robustesse de l’approche mais montrent également les limites de l’approche sur des données réelles de langue naturelle.

Mots clés : Inférence grammaticale, grammaires probabilistes, apprentissage automatique

Composition du jury :

  • Alexander CLARK, Lecturer, King’s College, Rapporteur
  • Amaury HABRARD, Professeur, Université de Saint-Etienne, Rapporteur
  • François COSTE, CR1, INRIA Rennes, Examinateur
  • Jean-Christophe JANODET, Professeur, Université d’Evry, Examinateur
  • Colin DE LA HIGUERA, Professeur, Université de Nantes, Directeur de thèse

Abstract :

Probabilistic Context-Free Grammars (PCFGs) are formal statistical models which describe probability distributions on strings and on tree structures of the same strings. Grammatical Inference is a sub-field of machine learning where the task is to learn automata or grammars (such as PCFGs) from information about their languages. In this thesis, we are interested in Grammatical Inference of PCFGs from text. There are various applications for this problem, chief amongst which are Unsupervised Parsing and Language Modelling in Natural Language Processing and RNA secondary structure prediction in Bioinformatics. PCFG inference is however a difficult problem for a variety of reasons. In spite of its importance for various applications, only few positive results have up till now been obtained for this problem.

Our main contribution in this thesis is a practical PCFG learning algorithm with some proven properties and based on a principled approach. We define a new subclass of PCFGs (very similar to the one defined in (Clark, 2010)) and use distributional learning and MDL-based techniques in order to learn this class of grammars. We obtain competitive results on experiments that evaluate unsupervised parsing and language modelling.

A minor contribution in this thesis is a compendium of undecidability results for distances between PCFGs along with two positive results on PCFGs. Having such results can help in the process of finding learning algorithms for PCFGs.

Dernière modification : mardi 25 novembre 2014