Méthode lagrangienne pour les arborescences couvrantes avec application en traitement automatique des langues

Session : GC / Génération de colonnes
Vendredi 12 février 10:30 - 11:50 Salle : CI2-07
Caio Corro, Joseph Le Roux, Mathieu Lacroix, Antoine Rozenknop et Roberto Wolfler

Nous nous intéressons au calcul des arborescences couvrantes de poids maximum avec deux contraintes structurelles : degré de bloc (block degree) et bonne imbrication (well-nestedness). Ces contraintes sont motivées par des problèmes d’analyse syntaxique en traitement automatique des langues (TAL) dans lesquels une phrase est représentée sous forme d’une arborescence couvrante dans un graphe orienté. Nous proposons une formulation du problème en PLNE ainsi qu’une relaxation lagrangienne de celle-ci. Le problème relâché correspond à l’arborescence couvrante de poids maximal pouvant être efficacement calculée grâce à l’algorithme d’Edmonds.

Mots clés : langues naturelles, relaxation lagrangienne, non-delayed relax-and-cut, arborescence couvrante