Polynomial Tree Substitution Grammars: Characterization and New Examples
Jean-Cédric Chappelier, Martin Rajman, Antoine Rozenknop
Résumé : Le but de ce papier est de caractériser (au moins partiellement) les Grammaires à Substitution d’Arbres Polynômiales (pSTSG), instances particulières de STSG pour lesquelles la recherche de l’analyse la plus probable peut être effectuée en un temps polynômial. Nous donnons tout d’abord diverses conditions suffisantes, utilisables en pratique, qui garantissent qu’une STSG est polynômiale. Une telle condition suffisante, fondée sur la notion de "tête de syntagme", est ensuite présentée et évaluée.
Abstract : Polynomial Tree Substitution Grammars, a subclass of STSGs for which finding the most probable parse is no longer NP-hard but polynomial, are defined and characterized in terms of general properties on the elementary trees in the grammar. Various sufficient and easy to compute properties for a STSG to be polynomial are presented. The min-max selection principle is shown to be one such sufficient property. In addition, another, new, instance of a sufficient property, based on lexical heads, is presented. The performances of both models are evaluated on several corpora.
Mots clés : Analyse Syntaxique Probabiliste, Grammaires à Substitution d’Arbres Polynomiales, Grammaires Hors-Contexte Probabilistes, Data-Oriented Parsing
Keywords : Stochastic Parsing, Polynomial Tree Substitution Grammars, Stochastic Context-Free Grammars, Data-Oriented Parsing