Méthode de forme normale de Chomsky: implications de performances de l'analyseur CYK?

Les analyseurs de graphiques peuvent être implémentés sur la base de la forme normale de Chomsky ou directement sur la base des règles de production. Supposons pour le moment que nous avons un analyseur graphique CYK qui utilise la forme normale de Chomsky. La binarisation n'est pas définie de manière unique. Cela affecte-t-il les performances de l'analyse graphique CYK? Cela peut-il être exploité pour améliorer les performances d'un analyseur graphique CYK?

Bien que la réponse évidente soit que la complexité fondamentale ne peut pas changer, il peut y avoir des algorithmes meilleurs ou pires pour analyser les chaînes que vous allez réellement rencontrer. Cependant, il semble que le problème soit moins la fréquence relative des productions grammaticales individuelles (les A, B et C dans la question) et plus un problème des analyses de cul-de- sac inutilisées qu'une binarisation par rapport à une autre peut produire.

Avec un peu de recherche, j'ai trouvé une meilleure binarisation pour l'analyse CKY (Song, Ding et Lin, EMNLP 2008), qui semble définitivement conclure que vous pouvez choisir une binarisation "meilleure" ou "pire" par rapport aux chaînes que vous attendez réellement avoir à analyser. Leur nom pour les «impasses» que l'on espère minimiser dans la pratique semble être des constituants incomplets , et il y a un bon exemple sur la première page.

En fait, la forme normale de Chomsky (CNF) n'est pas nécessaire pour exécuter CYK, seulement une binarisation. La binarisation est essentielle pour préserver la complexité cubique de l'analyse, bien qu'elle ne soit essentielle qu'en ce qui concerne les non-terminaux (NT). Mais alors, si vous avez des règles comprenant seulement 2 non-terminaux et certains terminaux, l'algorithme CYK devient plus complexe à programmer et à expliquer.

Comme vous le dites, il existe de nombreuses façons de procéder à la binarisation. Certains donneront des grammaires plus petites que d'autres. Par exemple

X -> B C D
Y -> B C E 

peut être binarisé comme

X -> Z D
Y -> Z E
Z -> B C

économisant ainsi une règle par factorisation, ce qui peut économiser sur le calcul et sur sa taille de résultat.

Mais avec d'autres règles, vous souhaiterez peut-être factoriser la fin des règles plutôt que le début.

Je ne connais pas le travail de Song, Ding et Lin , cité par la réponse de Rob Simmons . L'idée est intéressante mais je me demande dans quelle mesure elle peut être comparée à d'autres moyens d'optimiser le calcul. Je ne crains pas tellement.

Le fait est que l'analyse des problèmes uniquement par rapport à un algorithme CKY pur semble un exercice un peu académique mais coûteux, car il existe d'autres types d'optimisation qui peuvent considérablement améliorer l'élimination des analyses sans issue.

CYK n'est qu'une des variantes les plus simples d'une famille d'algorithmes qui sont tous construits sur le même modèle de programmation dynamique, apparemment. Je dis apparemment parce que la version la plus simple de ces algorithmes n'est pas connue comme programmation dynamique, mais comme produit croisé. C'est l'ancienne construction d'une grammaire CF G qui génère l'intersection du langage de la grammaire CF F et du langage régulier d'un FSA A., due à Bar Hillel, Perles et Shamir (1961) , comme l'a fait remarquer Lang en 1995 .

Tous les analyseurs graphiques ou les analyseurs CF généraux basés sur une programmation dynamique peuvent être considérés comme une variante "optimisée" de cette construction multi-produits, l'optimisation étant principalement utilisée pour éviter des calculs inutiles de l'analyseur. Mais le problème est subtil car éviter les calculs inutiles peut entraîner la duplication de ceux utiles, ce qui peut être pire.

De bas en haut, l'algorithme CKY produit des calculs inutiles d'analyses partielles qui ne peuvent pas dériver de l'axiome de la grammaire.

Des algorithmes comme l' analyseur GLR (pour n'en nommer que l'un des plus connus, bien qu'une version imparfaite ait été publiée), ont des connaissances descendantes qui éviteront de nombreux calculs inutiles de ce type, éventuellement à un coût. Et il existe de nombreuses autres variantes avec un comportement différent en ce qui concerne les économies sur les calculs inutiles.

C'est avec ces stratégies d'optimisation à l'esprit que la stratégie de binarisation doit être analysée. Quel est l'intérêt d'optimiser ce qui peut être un problème mineur et d'ignorer les techniques plus puissantes.

L'optimisation du processus d'analyse est également étroitement liée à la «qualité» de la structure d'analyse obtenue, qui représente toutes les analyses possibles, et est souvent appelée forêt d'analyse (partagée). J'en discute dans une autre réponse .

Certaines de ces questions sont discutées dans la littérature. Par exemple, Billot et Lang analysent certains aspects de la binarisation en ce qui concerne les stratégies d'analyse.