Analyse syntaxique par constituants et hors-contexte

Calcul de l'arbre syntagmatique d'une phrase à l'aide de grammaires hors-contexte, d'algorithmes de programmation dynamique tels que CKY et Earley, et de grammaires probabilistes qui résolvent l'ambiguïté.

Definition

L'analyse syntaxique par constituants attribue à une phrase un arbre syntagmatique imbriqué selon une grammaire hors-contexte, sélectionnant généralement l'arbre le plus probable sous une grammaire probabiliste.

Scope

Couvre l'analyse syntaxique avec les grammaires hors-contexte : les algorithmes CKY et Earley, la forme normale de Chomsky, les grammaires probabilistes hors-contexte et leurs raffinements lexicalisés, ainsi que les analyseurs statistiques entraînés sur des corpus annotés (treebanks). Il aborde la résolution de l'ambiguïté et l'évaluation des analyseurs. Les représentations de dépendance et les formalismes non hors-contexte sont traités dans des sujets connexes.

Core questions

• Comment l'algorithme CKY analyse-t-il une phrase en temps cubique ?
• Pourquoi les grammaires doivent-elles souvent être converties d'abord en forme normale de Chomsky ?
• Comment les grammaires probabilistes et lexicalisées améliorent-elles la désambiguïsation ?
• Comment la précision d'un analyseur est-elle mesurée par rapport à un corpus annoté (treebank) ?

Key concepts

• grammaire hors-contexte
• algorithme CKY
• algorithme d'Earley
• forme normale de Chomsky
• grammaire probabiliste hors-contexte
• lexicalisation
• arbre syntagmatique
• corpus annoté (treebank)

Key theories

Analyse syntaxique par programmation dynamique

Les algorithmes CKY et Earley calculent toutes les analyses en temps polynomial en remplissant un tableau de sous-constituants, évitant ainsi l'explosion exponentielle de la recherche naïve.

Analyse syntaxique probabiliste lexicalisée

Conditionner les probabilités des règles sur les mots-têtes améliore considérablement la précision de l'analyse syntaxique en capturant des préférences lexicales absentes des grammaires probabilistes hors-contexte (PCFG) simples.

History

L'algorithme CKY (années 1960) et l'algorithme d'Earley (1970) ont permis une reconnaissance hors-contexte efficace. Avec le Penn Treebank, les analyseurs probabilistes puis lexicalisés de Collins et Charniak ont atteint une grande précision à la fin des années 1990, définissant l'ère de l'analyse syntaxique statistique avant les modèles neuronaux.

Debates

Quel degré de lexicalisation est nécessaire ?

Les analyseurs lexicalisés sont précis mais peu denses ; le débat portait sur la question de savoir si les grammaires probabilistes hors-contexte (PCFG) non lexicalisées avec une division d'état (state-splitting) minutieuse pouvaient les égaler, ce que des travaux ultérieurs ont montré être partiellement possible.

Key figures

• Jay Earley
• Michael Collins
• Eugene Charniak

Seminal works

• earley1970
• collins2003

Frequently asked questions

Qu'est-ce qu'un tableau (chart) en analyse syntaxique ?

Un tableau (chart) est une structure de données qui stocke chaque constituant partiel trouvé sur chaque étendue de la phrase, de sorte que les sous-structures partagées sont calculées une seule fois et réutilisées, permettant une analyse syntaxique en temps polynomial.