formation par la recherche / formation doctorale / enseignement, stages / sujets de thèses

Inférence approchée de grammaires régulières

Localisation :ENSSAT, Lannion

Equipe CORDIAL et AÏDA

Responsable : Laurent MICLET (tél. direct : 02 96 46 66 28, email : miclet@enssat.fr)

Mot-clés : Apprentissage à partir d'exemples, Grammaires régulières.

Sujet : L'apprentissage d'une grammaire à partir d'exemples (ou inférence grammaticale) consiste classiquement à produire une grammaire, si possible de taille minimale, acceptant un échantillon (ensemble d'exemples) positif I₊ de phrases et n'acceptant pas un échantillon négatif I_-. Dans le cas des grammaires régulières, un théorème assure qu'il existe un espace fini et structuré de solutions possibles (sous forme d'automates finis), respectant certaines contraintes naturelles et construit à partir de I₊. Le problème de la recherche de l'automate minimal étant NP-difficile, des techniques heuristiques sont mises en oeuvre pour explorer cet espace sous le contrôle de I_-.

Ce sujet porte sur la recherche d'algorithmes d'inférence sous une contrainte un peu différente : on s'intéresse ici à trouver une grammaire aussi simple que possible, mais en tolérant qu'elle ne soit pas en accord total avec les échantillons positifs et négatifs. On cherche donc à apprendre une grammaire qui réalise un compromis entre simplicité maximale et adéquation aux données d'apprentissage. Une extension naturelle de ce problème conduira à s'intéresser à l'apprentissage combiné de C grammaires à partir d'un échantillon supervisé par C classes.

Le sujet s'insère dans un thème de recherche très actif dans les équipes CORDIAL et AÏDA. Il vise à approfondir les acquis récents et à explorer de nouvelles propriétés de l'espace de recherche pour proposer des algorithmes originaux. Ceux-ci seront testés sur les benchmarks mis à disposition par la communauté scientifique.

Référence :
[DM,98] Dupont P. et Miclet L. Inférence grammaticale régulière : fondements théoriques et principaux algorithmes Rapport de recherche INRIA 3449. Juillet 1998.