Un réseau de transition récursif à filtrage par pop (FPRTN) est un modèle computationnel pour l'analyse syntaxique du langage naturel, décrit pour la première fois dans un rapport technique de 1988 par des chercheurs de l'Université d'Édimbourg. Il étend le formalisme antérieur du réseau de transition récursif (RTN) en ajoutant un mécanisme appelé filtrage par pop, qui permet au réseau de traiter certaines constructions grammaticales sensibles au contexte que les RTN simples ne peuvent pas traiter. Les FPRTN ont été développés dans le cadre de recherches sur l'analyse déterministe et ont ensuite été reconnus comme une influence précoce sur les approches connexionnistes et neuronales de l'analyse syntaxique.
L'idée centrale d'un FPRTN est un réseau d'états et de transitions qui peut appeler récursivement des sous-réseaux, similaire à un automate à pile. Dans un RTN standard, une opération de pop retourne le contrôle d'un sous-réseau à l'appelant, mais cela peut entraîner une ambiguïté lorsque plusieurs sous-réseaux sont actifs. Le filtrage par pop ajoute une condition - un filtre - qui doit être satisfaite avant qu'un pop ne soit autorisé, contraignant ainsi l'espace de recherche et permettant à l'analyseur de gérer les dépendances à longue distance et les phénomènes d'accord. Le filtre est généralement basé sur des structures de traits ou des informations de contexte propagées à travers le réseau.
Développement historique
Le FPRTN a été introduit à la fin des années 1980 dans le cadre du programme de recherche Alvey sur le langage naturel au Royaume-Uni. La publication principale était un rapport de 1988 intitulé « Filtered Popping in Recursive Transition Networks » par des chercheurs, dont Chris Mellish et d'autres à l'Université d'Édimbourg. Les travaux s'appuyaient sur des modèles RTN antérieurs des années 1970, tels que ceux de William Woods chez Bolt Beranek and Newman (BBN), utilisés dans le système de questions-réponses LUNAR. Le groupe d'Édimbourg visait à améliorer l'efficacité et la couverture des analyseurs basés sur RTN pour les textes réels.
L'approche a ensuite été discutée dans le contexte des « réseaux de transition augmentés » (ATN), qui ajoutaient des mécanismes de registres et de conditions aux RTN. Les FPRTN offraient une alternative plus contrainte aux ATN, en se concentrant sur l'analyse déterministe et la réduction du retour arrière. La technique a également été explorée dans l'analyse connexionniste, où les conditions de filtre étaient implémentées comme des activations de réseaux neuronaux, reliant les paradigmes symbolique et subsymbolique.
Description technique
Formellement, un FPRTN est un graphe orienté avec un ensemble d'états, un ensemble de transitions étiquetées, et un ensemble d'opérations d'appel et de retour de sous-réseaux. Chaque transition peut être associée à une condition, et chaque opération de pop a un filtre qui doit être satisfait. L'analyseur maintient une pile de contextes de sous-réseaux actifs. Lorsqu'un pop est tenté, le filtre vérifie l'entrée courante et le sommet de la pile ; si le filtre échoue, le pop est bloqué, et l'analyseur doit explorer des chemins alternatifs. Ce mécanisme est similaire à l'utilisation de l'unification de traits dans les grammaires à unification et peut être vu comme un précurseur de l'analyse basée sur les traits utilisée dans les systèmes modernes de TALN.
Une propriété clé des FPRTN est qu'ils sont plus expressifs que les grammaires régulières mais moins expressifs que les grammaires contextuelles complètes. Ils peuvent gérer les dépendances croisées, courantes dans des langues comme le néerlandais et le suisse allemand, mais de manière computationnellement traitable. Le mécanisme de filtrage peut être implémenté efficacement, et le modèle a été montré pour analyser certaines constructions en temps polynomial, alors que les ATN non restreints pouvaient être exponentiels.
Influence sur les modèles neuronaux
Bien que les FPRTN aient été développés dans la tradition symbolique, ils ont été cités comme une inspiration pour les modèles neuronaux ultérieurs d'analyse syntaxique. Dans les années 1990, des chercheurs de l'Université d'Édimbourg et d'ailleurs ont exploré des implémentations connexionnistes des RTN, où les décisions de transition étaient prises par des réseaux de neurones. Cette ligne de travail a influencé le développement des modèles séquence à séquence et des réseaux récurrents pour le traitement du langage. Plus récemment, l'idée d'utiliser des structures de type pile avec des contrôleurs appris est apparue dans des modèles tels que la machine à pile neuronale et l'ordinateur neuronal différentiable, développés chez Google DeepMind dans les années 2010.
Le mécanisme de filtrage par pop est conceptuellement lié aux mécanismes d'attention et de gating dans les transformeurs modernes. Par exemple, l'attention multi-têtes dans les transformeurs peut être vue comme une version douce du filtrage, où l'information est sélectivement propagée en fonction d'une pertinence apprise. La pile explicite dans les FPRTN est analogue à l'encodage positionnel et au traitement par couches dans les transformeurs, bien que ces derniers ne soient pas explicitement conçus pour la structure syntaxique. Les chercheurs ont noté que les FPRTN fournissent un cadre formel clair pour comprendre les biais inductifs des analyseurs neuronaux.
Applications et héritage
Les FPRTN ont été principalement utilisés dans des analyseurs expérimentaux pour l'anglais et d'autres langues. Ils ont été intégrés dans le kit d'outils Alvey pour le langage naturel, distribué aux universités britanniques à la fin des années 1980. Le formalisme a également été utilisé dans le développement du moteur de langage central (CLE) chez SRI International, un projet majeur dans les années 1990. Le CLE utilisait une combinaison de grammaire à unification et de structures de contrôle de type RTN, et sa conception a influencé des systèmes commerciaux ultérieurs, tels que les composants de compréhension du langage des premiers assistants vocaux.
Dans les années 2000, l'intérêt pour l'analyse symbolique a décliné au profit des approches statistiques et neuronales, mais le concept de FPRTN reste pertinent dans l'étude des formalismes grammaticaux et dans la conception de systèmes hybrides. L'idée de filtrage par pop a été appliquée à d'autres domaines, comme l'analyse de programmes et l'analyse sémantique, où des contraintes sensibles au contexte sont nécessaires. Dans les années 2020, le formalisme est occasionnellement cité dans la recherche sur les grands modèles de langage et leur capacité à capturer la structure syntaxique, certaines études comparant le comportement des transformeurs à celui des analyseurs basés sur RTN.
Voir aussi
- réseau de transition récursif
- réseau de transition augmenté
- traitement du langage naturel
- analyse syntaxique
- grammaire à unification
- réseau de neurones
- transformeur
- séquence à séquence
- Google DeepMind