Analyse syntaxique de la langue naturelle
En linguistique informatique ou en TALN, l'analyse syntaxique (syntactic parsing) réfère au processus d'analyse automatisé d'une chaine de mots — représentant une phrase — dans le but d'obtenir les relations coexistant entre ces mots, par l'intermédiaire d'un arbre syntaxique.
Lorsqu’on part de texte brut, ce dernier doit avoir été segmenté en unités lexicales au préalable (tokenization). Habituellement, une analyse lexicale (lemmatisation, analyse morphosyntaxique...) est exécutée avant l'analyse syntaxique proprement dite, afin d'identifier les unités lexicales et leurs propriétés. Le résultat de l'analyse est typiquement utilisé comme base dans l'analyse sémantique, construisant une représentation du sens du texte, ou directement dans des applications telles que la correction grammaticale.

Pour un système de réponse aux questions ou de recherche d'informations, il serait par exemple difficile de répondre correctement à la demande « quels ouvrages ont été écrits par des auteurs francophones avant 1900 ? » sans reconnaitre le sujet « ouvrages », car il faut notamment comprendre que l'utilisateur désire une liste d'ouvrages et non une liste d'auteurs.

Le processus d'analyse peut se reposer sur une grammaire formelle et/ou faire appel à des méthodes statistiques.

Historique 
L’analyse syntaxique remonte aux débuts de la recherche en TALN, puisqu’un des premiers algorithmes d’analyse fut introduit par Victor Yngve en 1955, avant même le développement de la théorie des langages formels par Noam Chomsky en 1956 . Dès lors, les analyseurs créés vont se fonder sur les grammaires formelles, particulièrement celles dites hors contexte ou de type 2. Entre autres, John Cocke a inventé un algorithme de programmation dynamique en 1960, qui fut ensuite formalisé par T. Kasami (1965)  et D. H. Younger (1967)  : le célèbre algorithme CKY, analysant une séquence en temps cubique grâce aux grammaires en Forme normale de Chomsky. Ce dernier est de type mixte, c’est-à-dire combinant les stratégies ascendantes et descendantes, individuellement moins efficaces.

Parallèlement, dans les années 1960, plusieurs autres formalismes destinés à l’analyse syntaxique voient le jour, dont les grammaires de dépendances inspirées par Lucien Tesnière (1959) et formalisées avant tout par David Hays (1960). Peu après N. Chomsky, John Backus (1959) et Peter Naur (1960) ont indépendamment réinventé les grammaires hors contexte dans leur description du langage ALGOL, donnant lieu à la célèbre forme de Backus-Naur. En 1968, Jay Earley inventa le premier algorithme d’analyse syntaxique en temps cubique pour toutes les grammaires hors contexte (pas nécessairement en forme normale) . À la même époque, R. Kaplan  et M. Kay  ont généralisé l’algorithme CKY à toutes les grammaires hors contexte pour en faire le chart parser, utilisant un graphe. Parmi les algorithmes similaires aux deux précédents, on peut encore citer celui du coin gauche (left-corner parser), en référence au premier symbole de la partie droite d’une règle de production .

Beaucoup d’autres formalismes ont été développés durant les années 1970-1980, dont les réseaux de transition augmentés (ATN), et les grammaires d’unification (Constraint-Based Grammars). Une représentation en dépendances de ces dernières a été originairement proposée par H. Maruyama . Durant les années 1990, les développements furent principalement tournés vers les méthodes statistiques, dont un travail important autour des grammaires hors contexte probabilistes (PCFG)  — un des modèles d’analyse statistique parmi les plus influents, qui est basé sur une grammaire formelle — dont les problèmes principaux sont l’ignorance des informations sémantiques et l’hypothèse d’indépendance de l’attachement structurel des syntagmes. Certaines approches plus récentes ont permis d’améliorer les faiblesses des PCFG par la lexicalisation de la grammaire , ou l’utilisation d’un jeu plus précis de symboles non terminaux , entre autres. Du côté de la représentation en dépendances, le premier algorithme stochastique influant fut proposé par Jason Eisner .

Pour les méthodes qui ne requièrent pas l’intervention d’une grammaire, les modèles sont directement induits depuis des données annotées (corpus), ce qui facilite le portage des systèmes à de nouvelles langues ou domaines. Bien que cette dernière possibilité soit majoritairement utilisée de nos jours, les méthodes basées sur des grammaires restent utilisées lorsqu’il n’existe pas suffisamment de données annotées nécessaires au fonctionnement des méthodes supervisées. Notons au passage qu’une grammaire peut très bien être extraite de données linguistiques ; les méthodes basées sur les grammaires (grammar-based parsing) et celles guidées par des données (data-driven parsing) ne sont donc pas mutuellement exclusives. La catégorisation suggérée des méthodes statistiques d’analyse est très répandue dans le domaine du TALN .

Difficultés 
L'analyse syntaxique est une tâche non triviale, principalement en raison de l’ambiguïté intrinsèque de la langue et de sa diversité. Un énoncé est dit ambigu si plusieurs structures linguistiques peuvent y être associées.

Voici quelques exemples d’ambiguïtés structurelles:« Jean a vu l’homme sur la colline avec un télescope »Dans cette phrase, l'attachement du syntagme prépositionnel est ambigu, et on ne sait pas si Jean a utilisé un télescope pour voir l'homme, ou si Jean a vu un homme utilisant lui-même un télescope.« À qui avez-vous promis d’écrire ? »La question précédente pourrait être paraphrasée de deux façons: « Vous avez promis d’écrire à qui ? » ou « Vous avez promis à qui d’écrire ? » ; on ne sait pas si la personne en question va écrire à quelqu'un, ou si elle a promis à quelqu'un d'écrire (quelque chose).

Lien avec l'analyse d'un langage formel 
Même si le but de l'analyse syntaxique d'un langage formel déterministe (p. ex. langage de programmation) est identique à celui de l'analyse syntaxique de la langue naturelle, la tâche est nettement plus ardue dans le second cas.

Premièrement, la capacité générative d’une grammaire — sa puissance — est beaucoup plus faible dans le cas des langages informatiques, car ceux-ci doivent être strictement non ambigus et rapidement analysables (donc la grammaire est restreinte). Comparativement, une grammaire prévue pour la langue naturelle doit permettre par exemple d’exprimer des dépendances entre des mots éloignés les uns des autres ; elle est donc plus complexe.

Deuxièmement, comme la langue naturelle souffre d’une ambiguïté structurelle, à chaque étape de l’analyse, plusieurs règles de la grammaire seront probablement applicables. Ainsi, une phrase telle que « Jean a vu l’homme [sur la colline] [avec un télescope] [accompagné de sa fille] [...] » verra le nombre de ses analyses possibles augmenter exponentiellement avec le nombre de constituants ajoutés . Au passage, c’est une des raisons qui a poussé le développement des méthodes statistiques.

La dernière différence notable se situe au niveau de la validité de la séquence d’entrée : un langage de programmation possède un nombre fini de constructions valides, alors qu’il est illimité pour une langue naturelle. De ce fait, l’impossibilité de produire une analyse existe dans le cas du TALN, erreur qui n’est d'ailleurs pas nécessairement due à une grammaire inadéquate, mais possiblement à une erreur grammaticale, une faute de frappe, un mot inconnu, etc.

Outre ces dissemblances caricaturales, de nombreuses autres existent, comme la délimitation stricte des « phrases » (déclarations, blocs) et mots dans le cas des langages formels avec des caractères bien définis.

Méthodes classiques

Méthodes purement basées sur une grammaire 
La majorité des premiers systèmes d'analyse syntaxique se fondent exclusivement sur une grammaire indépendante de contexte (context-free grammar) pour générer des structures syntaxiques correctes, bien que ce type de grammaire ne soit pas suffisant pour engendrer la langue naturelle dans son ensemble . Conjointement, il est nécessaire d'avoir un algorithme qui dicte comment ces structures seront efficacement produites. Dans ce cadre-là, l’algorithme de programmation dynamique CKY est énormément utilisé, dans lequel les sous-problèmes — maintenus dans un tableau — sont représentés par les arbres syntaxiques partiels enracinés sur les syntagmes de la phrase d'entrée. Grâce à la nature indépendante du contexte des grammaires, il est possible de réutiliser une sous-structure dans les dérivations suivantes qui la demande, rendant possible la programmation dynamique. Les algorithmes concurrents à CKY sont celui d'Earley  et le chart parsing .

Méthodes aidées par la statistique 
Le problème des algorithmes assimilés à CKY est leur incapacité à résoudre les ambiguïtés structurelles (voir section « difficultés »), bien qu'il soit possible de les détecter. Pour pallier ce manque, il est nécessaire d'ajouter une composante statistique au modèle; si chaque règle est accompagnée d'une probabilité, il suffit de sélectionner celle avec la probabilité la plus haute en cas d'ambiguïté. À ce titre, le formalisme le plus usité est la grammaire indépendante de contexte probabiliste (probabilistic context-free grammar ou PCFG) . Une version probabiliste de l'algorithme CKY existe, décrit avant tout par H. Ney . L'inférence exacte nécessite un temps en , où  représente le nombre de règles de la grammaire.

Cependant, le modèle de PCFG est relativement limité dans sa capacité à exceller, car il impose de fortes hypothèses d'indépendances. Le problème majeur est le fait que la probabilité d'une règle particulière soit indépendante du contexte dans lequel elle est produite ; par exemple, la probabilité qu'un syntagme nominal soit étendu en pronom (règle ) reste constante, que ce syntagme se trouve en position de sujet ou d'objet, alors que la première possibilité est bien plus fréquente pour certaines langues . Par ailleurs, si deux structures différentes utilisent exactement les mêmes règles, elles obtiendront la même probabilité ; or, pour une même phrase (donc mêmes règles), il y a souvent une structure qui est préférée à une autre (lorsque plusieurs possibilités existent), chose qui n'est pas véhiculée par le formalisme PCFG.

Plusieurs modèles furent proposés dans le but de résoudre les problèmes cités ci-devant. Un des plus influents est celui de Michael Collins, appelé LPCFG ou parfois head-driven , consistant à lexicaliser la grammaire par l'élection d'un élément prépondérant (head rule) pour chaque règle de la grammaire. De cette façon, chaque nœud parent de l'arbre syntaxique est "paramétré" par un mot de la phrase ; par exemple une règle  pour une PCFG pourrait devenir  si « le chien » fait partie de la phrase à analyser. Comme  est l'élément prépondérant pour cette règle, le parent  hérite du mot « chien ».

L'annotation des nœuds non terminaux d'une PCFG, connue sous le nom de parent annotation , a aussi connu un grand succès pour l'analyse de constituants, car la précision des systèmes implémentant cette technique est similaire à ceux à base de LPCFG, avec une moindre complexité . Une telle annotation pourrait être par exemple  si  compose un syntagme prépositionnel.

Une autre solution au manque de sensibilité structurelle des PCFGs est le data oriented parsing (DOP) établi par Remko Scha et Rens Bod . Le principe est d'analyser des phrases en combinant des fragments d'analyses de phrases dont la structure est connue, comme celles provenant d'un corpus.

Deux classes de modèles probabilistes existent: ceux dits génératifs, comme les LPCFGs, et ceux dits discriminants (voir section « modèles statistiques d'analyse » pour plus de détails).

Méthodes statistiques

Avantages de la statistique 
Avec l’approche classique, l’analyse d’une phrase peut donner lieu à des millions d’arbres syntaxiques possibles en raison de la grande taille de la grammaire, avec l’impossibilité de choisir lequel reflète au mieux la structure de la phrase en question. Si des contraintes sont ajoutées à cette grammaire pour restreindre le nombre d’analyses possibles, une partie des phrases analysées risquent alors de ne plus avoir de structure correspondante. L’approche statistique a l’avantage de tolérer des millions d’analyses, tout en ayant la possibilité de sélectionner la meilleure en temps raisonnable ; à ce titre, il est souvent nécessaire de réduire l’espace de recherche tout au long du processus d’analyse, en éliminant les analyses partielles peu probables au plus tôt.

De nos jours, les grammaires (seules) ne sont quasiment plus utilisées, et les approches dans le domaine du TALN font essentiellement appel à des techniques d'apprentissage automatique.

Qui plus est, la formalisation des phénomènes linguistiques étant laborieuse, les techniques statistiques ont apporté l’énorme avantage d’extraire les connaissances linguistiques directement d’échantillons (réels) de données. Et si la construction d’un corpus (treebank) est plus fastidieuse que la construction d’une grammaire, ce premier a l’avantage d’être réutilisable dans d’autres systèmes (dont les analyseurs morphosyntaxiques), expliquant en partie le désintérêt à l’égard des grammaires. En outre, les données contiennent implicitement des statistiques, et l’évaluation d’un système est aisée. Notons qu’une grammaire peut très bien être extraite de données linguistiques ; les méthodes basées sur les grammaires (grammar-based parsing) et celles guidées par des données (data-driven parsing) — aujourd'hui majoritaires — ne sont donc pas mutuellement exclusives.

Bien que les techniques statistiques soient utilisées pour désambiguïser — le cas échéant — le processus d’analyse, l'espace de recherche ne peut qu'extrêmement rarement être exploré dans sa totalité, et il est nécessaire de le borner pour des raisons d’efficacité.

Modèles statistiques d'analyse 
On peut représenter un analyseur syntaxique par une fonction , où  est l’ensemble des entrées possibles, sachant que  représente une séquence d’entrée , et  est l’ensemble des représentations syntaxiques admissibles. Relevons que la nature de la représentation d’une analyse  est spécifique à la théorie utilisée, au même titre que son critère d’admissibilité.

Un modèle d'analyse syntaxique se décompose conceptuellement en deux parties  :

 un composant génératif , qui fait correspondre une entrée  à un ensemble d’analyses candidates , donc ;
 un composant évaluatif , classant les analyses candidates selon un score numérique attribué, donc .

Les deux composants ont généralement des paramètres dont les valeurs vont être estimées statistiquement, en commençant par l’analyse de données représentatives, nommées ensemble d’entrainement, afin de faire de  un bon estimateur du  correspondant. C’est l’étape d’apprentissage du modèle, qui peut être supervisée ou non supervisée (parfois semi-supervisée) ; un apprentissage supervisé nécessite que l’analyse correcte soit présente dans les données. Toute la difficulté de cette étape est donc d’utiliser correctement l’évidence partielle — contenue dans les données — pour créer une distribution de probabilité reflétant au plus près la réalité. À partir de la fonction , inférée au moment de l’apprentissage du modèle, la seconde étape consiste à ordonner efficacement les analyses candidates pour une phrase d’entrée (inédite) donnée : c’est le problème d’inférence. Cette dernière peut être exacte ou approximative, selon les garanties apportées par l’algorithme utilisé.

Il faut souvent trouver un juste compromis entre la complexité du modèle et le manque d’exactitude des solutions générées. Au passage, notons le fait que l’ensemble  est vraisemblablement très grand, et que chaque  est un objet possédant une structure interne riche ; ce constat contraste avec un simple problème de classification, pour lequel  serait beaucoup plus petit. Les systèmes utilisant un algorithme d’apprentissage supervisé sont beaucoup plus répandus, car ils sont bien plus performants .

En outre, deux grandes classes de modèles s’opposent en apprentissage automatique, pas nécessairement liées aux composants génératifs et évaluatifs mentionnés auparavant : la première possibilité, dite générative, est de voir le processus d’analyse comme un système de réécriture probabiliste, où le but est de produire une (ou plusieurs) structures en fonction d’une entrée donnée ; à chaque étape, il faudrait choisir la (ou les) meilleure(s) alternative(s) afin d’obtenir la structure la plus probable à l’issue de l’analyse. Ici, le but est de maximiser la probabilité jointe , quel que soit  et , en modélisant  et , puis en les recombinant avec la règle de Bayes (cas des PCFGs). La seconde possibilité, dite discriminante, est de voir la grammaire comme un ensemble de contraintes sur les structures correctes, et la séquence d’entrée comme une contrainte sur la position des mots ; l’analyse doit alors résoudre ces contraintes, puis sélectionner la structure syntaxique la plus probable parmi celles répondant le mieux aux contraintes. Dans ce cas, on cherche à modéliser la probabilité conditionnelle  directement depuis les données. Encore, les deux approches peuvent être combinées de façon séquentielle (reranking) .

Modèles génératifs 
La dérivation de la structure syntaxique est modélisée par un processus stochastique pour lequel chaque étape dépend d’événements apparus par le passé (historique). La forme générale de tels modèles, évoqués initialement par G. Leech , est la suivante :

où la fonction  définit quels événements de l'historique sont pris en compte. Bien que ce soit souvent le cas, le composant génératif  est un système de dérivations qui n'est pas forcément contraint par une grammaire formelle (le modèle de l'analyseur IDP est un exemple ). L'évaluation  se fait selon la probabilité jointe, factorisée en probabilités conditionnelles. À noter que  se ramène à  car, pour une structure donnée, la probabilité  est égale à  si  est la phrase unique correspondant à cette structure ; par conséquent,  si  engendre , ou  dans tous les autres cas.

Les modèles génératifs imposent des hypothèses d'indépendance rigides, ce qui a un impact sur la désambiguïsation (typiquement les PCFGs). Toutefois, l'adaptation de ces hypothèses donne des modèles plus complexes et l'inférence exacte n'est plus possible (voir aussi section « méthodes aidées par la statistique »). Fondamentalement, ce genre de modèle doit prédire le prochain mot à mesure que l'analyse avance, ce qui nécessite une normalisation globale à travers le vocabulaire entier, et souvent un faisceau plus grand (le cas échéant), de façon à pouvoir « essayer » un grand nombre de structures sur la partie de phrase incluant le mot prédit . Par ailleurs, l'entrainement des modèles génératifs cherche la plupart du temps à maximiser la probabilité jointe des entrées-sorties de l'ensemble d'entrainement ; or, le but de l'analyse est de maximiser la précision du modèle pour des phrases inédites. Pour ces raisons, les modèles discriminants sont de plus en plus utilisés.

Modèles localement discriminants 
Le but de ces modèles est de maximiser la probabilité de décisions locales, en espérant atteindre la meilleure solution globale grâce à la succession de décisions (locales) optimales, à l'instar des modèles génératifs basés sur un historique :

Ici, la fonction  représente des propriétés/traits arbitraires dépendant de l’historique  des décisions prises,  ; autrement dit, on définit une classe d’équivalence pour toute combinaison d’un historique et d’une entrée. En employant des méthodes de prévision sur l’entrée, certains analyseurs approchent une analyse déterministe (prédictive). Pour ce type de modèle, le composant génératif  est constitué d’un processus incrémental (p. ex. automate), alors que le composant évaluatif  doit être capable d’assigner un score à une décision locale donnée, et de combiner ces scores en scores globaux, évaluant une séquence complète de transitions.

Parfois, ce type de modèle est appelé « génératif », car il implique des hypothèses d'indépendance comme les modèles véritablement génératifs — modélisant la probabilité jointe — mais sur des décisions locales, et non pas sur des décisions globales . L'approche locale à l'avantage de favoriser la prise en considération de traits caractéristiques utiles à la désambiguïsation, problématique principale des véritables modèles génératifs. Cette catégorie de modèles permet d'obtenir des analyseurs beaucoup plus rapides que ceux à base de modèles génératifs (p. ex. de l'ordre de 35x ).

Modèles discriminants 
Cette classe de modèles définit typiquement la fonction d’évaluation comme étant le produit d’un vecteur de traits (caractéristiques)  et d’un vecteur de poids :

où chaque  représente une caractéristique de  et , et chaque  quantifie l’importance de la caractéristique  pour l’analyse optimale. Si ce poids est négatif, la caractéristique dessert l’analyse, alors que dans le cas contraire, la caractéristique influe positivement sur l’analyse optimale. La nature des caractéristiques n’est pas limitée ; la seule restriction est de pouvoir les encoder sous forme numérique. On peut par exemple utiliser le score fourni par un autre analyseur en tant que caractéristique, ou tenir compte de la présence/absence d'une sous-structure.

Donc, un modèle véritablement discriminant définit un unique score sur la structure globale d’une analyse. L’avantage est de pouvoir observer des propriétés globales des structures syntaxiques, et de pouvoir tenir compte (ajouter) de nouvelles contraintes sans altérer la dérivation du modèle . Pour cette classe, le composant génératif  est assez variable d’un système à l'autre, tandis que le composant d’évaluation  est établi par une combinaison linéaire de caractéristiques pondérées, non restreintes par un quelconque processus, et dont les poids sont fixés par un modèle d’apprentissage discriminant.

Le défaut de ce type de modèle est le besoin de réanalyser l'ensemble d'entrainement à chaque itération, ce qui est naturellement gourmand en ressources. Certaines approches, dites de reranking, se sont contentées d'utiliser ce genre de modèle uniquement pour un sous-ensemble de , lui-même obtenu via un modèle génératif . Cependant, la meilleure analyse ne se trouve pas forcément dans ce dernier sous-ensemble , ce qui en fait une technique pas idéale. Néanmoins, les problèmes d'efficacité sont moins marqués dans l'analyse de dépendances que dans celle de constituants, et ils sont beaucoup utilisés dans le premier cas où l'inférence exacte est même possible sous certaines conditions  (voir section « méthodes basées sur des graphes »).

Paradigmes d'analyse 
Actuellement, la représentation des structures syntaxiques la plus populaire est celle en dépendances , en raison du bon compromis expressivité/efficacité des algorithmes qu'elle propose , et des performances obtenues pour une grande variété de langues . Avec cette représentation, ce sont très souvent des modèles probabilistes localement discriminants ou discriminants qui sont utilisés, contrairement à la représentation en constituants, pour laquelle les modèles génératifs sont plus compétitifs . Toutefois, il est intéressant de relever que certains systèmes récents (p. ex.  ), particulièrement performants, sont fondés sur l'assemblage de modèles de types différents (technique densemble ou system combination) .

On peut classer l’immense majorité des modèles d’analyse statistique de dépendances en deux familles :

 Les méthodes basées sur des transitions (transition-based) reposent sur un automate à états finis permettant de générer une structure syntaxique à partir d’une phrase donnée. Au long de l’analyse, le modèle appris doit être en mesure de prédire la prochaine transition, en fonction de l’historique des transitions, de manière à pouvoir trouver la séquence optimale de transitions menant à la meilleure analyse possible de la phrase d’entrée.
 Les méthodes basées sur des graphes (graph-based) définissent un univers d’analyses candidates pour une phrase donnée. L’apprentissage se résume à induire un modèle capable d’évaluer ces analyses candidates dans leur ensemble ; le processus d’analyse doit trouver la structure, tel que son score soit le plus élevé, correspondant à la phrase d’entrée.

Dans le premier cas, la stratégie est de trouver la meilleure solution locale (approche gloutonne), alors que dans le second cas, le raisonnement revêt l’apparence d’une recherche exhaustive. En outre, la première méthode est parfois dénommée shift-reduce parsing, du nom de l’algorithme d’analyse utilisé par bon nombre d’implémentations . C'est une méthode très populaire en raison de son excellente efficacité: la complexité de l'algorithme d'analyse typique est linéaire (relativement au nombre de mots de la phrase d'entrée). Quant à la seconde méthode, on la retrouve parfois sous le nom de maximum spanning tree parsing (MST), qui correspond au nom de l’algorithme utilisé par le système ayant introduit cette technique . En 2015, Jinho Choi et coll. ont étudié les performances de dix analyseurs syntaxiques compétitifs de dépendances, de façon détaillée et selon différentes métriques .

 Méthodes basées sur des transitions 
Les modèles basés sur des transitions sont des modèles localement discriminants avec un apprentissage discriminant, dans le sens où seule l’estimation de l’analyse finale  est extraite de la distribution probabiliste, en recourant par exemple à une surface de décision. Cela s’oppose aux modèles conditionnels, où toute la densité de probabilité conditionnelle  serait optimisée . En supposant une fonction d’évaluation  assignant un score aux transitions possibles  en fonction d’une configuration, représentée par un vecteur , ainsi qu’un moyen d’évaluer une séquence complète de transitions, l’analyse revient à trouver la séquence ayant le score le plus élevé. À ce titre, la plupart des systèmes implémentent une recherche en faisceau .

Une méthode très en vogue pour l’analyse de structures de dépendances est l’usage d’un classificateur (entrainé sur un corpus), afin de prédire la prochaine action exécutée par un algorithme d’analyse déterministe. Cette démarche est parfois appelée « pseudo-déterministe », en référence aux algorithmes d’analyse déterministes appliqués à des grammaires non ambiguës (langages formels). Dans le cas présent, l’espace de recherche est intrinsèquement limité par le procédé de l’algorithme, puisqu’une seule action choisie implique l’abandon de toutes les autres ; en raison de cette approche gloutonne, l’élagage est donc très agressif. Cette force est également un désavantage, car un mauvais choix précoce peut se répercuter négativement sur l’analyse finale .

Un système d’analyse basé sur un classificateur se compose de trois ingrédients essentiels :
 un algorithme d’analyse syntaxique qui établit une analyse par la succession d’actions élémentaires (via un système de transitions) ;
 un modèle permettant de décrire tout état de l’analyseur (configurations du système de transitions) par un vecteur de caractéristiques ;
 un classificateur qui transforme un état, sous forme de vecteur de caractéristiques, en une action de l’algorithme d’analyse.

Cette approche a été initiée par T. Kudo et Y. Matsumoto , qui ont proposé une implémentation couplée à un classificateur de type machine à vecteur de support, pour l’analyse en dépendances non étiquetées du japonais. En utilisant la base de l’algorithme de Joakim Nivre , l’idée a par la suite été étendue itérativement aux dépendances étiquetées pour le suédois, puis pour l’anglais, puis à 19 langues , avant d’être optimisée pour former le logiciel MaltParser . Les premiers algorithmes sont limités aux structures projectives, mais G. Attardi , parmi d’autres , proposa un algorithme étendu à un sous-ensemble des structures non-projectives. À ce titre, J. Nivre propose une version online-reordering de son système de transitions , tandis que d'autres approches passent par une décomposition en (sous-)arbres de dépendances planaires et l'analyse de chaque plan séparément (mltiplanar parsing) . Une autre solution implique un pré/post-traitement des données (appelé pseudo-projectivization) .

Les problèmes principaux de ce paradigme sont la sensibilité aux erreurs de recherche et la propagation des erreurs due au processus incrémental univoque. Pour tenter d'améliorer la précision, tout en maintenant une analyse hautement efficace, plusieurs techniques ont vu le jour. Certains ont relaxé le processus strictement déterministe — en gardant les K meilleures analyses (recherche en faisceau)  — associé parfois à un entrainement en tant que prédiction structurée , tandis que d'autres ont abandonné l'analyse purement séquentielle de gauche à droite (easy-first parsing) , car la recherche en faisceau ralentit substantiellement l'analyse. Dans le même but, J. Nivre a expérimenté l'usage d'un oracle dynamique — à la fois non déterministe et complet (contrairement aux oracles statiques habituels) — pour son système de transitions arc-eager . Cependant, ces oracles induisent une grande complexité lorsqu'ils sont utilisés avec des systèmes généraux (non limités aux structures projectives), et il n'est pas toujours possible de les dériver. Pour cette raison, M. Straka et coll. ont introduit une nouvelle classe d'oracles dénommés search-based oracles , qui est une approximation des oracles dynamiques.

En pratique, des modèles probabilistes sont définis pour chaque action de l'algorithme d'analyse, en fonction de son contexte courant ; cependant, les modèles fondés sur un historique d’actions (ou transitions) doivent faire face à une quantité illimitée d’informations, rendant une modélisation probabiliste impossible. Ce problème est ordinairement résolu en limitant l’historique à un ensemble fini de caractéristiques . À ce moment-là, la difficulté majeure réside dans le choix de la représentation de cet historique, c’est-à-dire son aperçu, à partir duquel la probabilité de l’action suivante pourra être convenablement estimée. Comme cette probabilité est indépendante de toute information au sujet de l’historique qui ne serait pas contenue dans son aperçu, la qualité de l’analyse peut être fortement affectée par les caractéristiques retenues.

La recherche dans le domaine de l’analyse syntaxique statistique a débuté au milieu des années 1990, et s’est principalement focalisée sur les modèles linéaires, durant de nombreuses années. Avec de tels modèles, le score attribué à une analyse est calculé selon une combinaison de traits structurels ou de caractéristiques morphologiques — dont la représentation est naturellement éparse — liées à la structure en question. Or, cela demande une sélection manuelle, plausiblement fastidieuse, des combinaisons de traits à inclure dans l’évaluation, avant l’utilisation d’un algorithme d’apprentissage. Par conséquent, l’adaptation de ces modèles à de nouvelles langues ou de nouveaux domaines est difficile et coûteuse ; de plus, l’oubli d’une caractéristique importante peut se répercuter très négativement sur la précision (problème d'incomplétude) . Par ailleurs, les analyseurs passent le plus clair de leur temps à extraire les caractéristiques , et non à l'analyse en elle-même . Toutes ces raisons ont motivé le développement de modèles non linéaires''', susceptibles d’induire automatiquement une combinaison appropriée des traits prédictifs ; dans de tels cas, un réseau de neurones artificiels seconde ou remplace majoritairement le classificateur linéaire. Avec la plupart des modèles, il est néanmoins nécessaire de leur fournir un nombre restreint (env. 10-20) de caractéristiques dynamiques simples (c.-à-d. non combinées). Cette voie fut initiée par James Henderson  au début des années 2000, puis approfondie en 2007 avec un analyseur fondé sur un modèle probabiliste purement génératif et équipé d'un réseau ISBN (incremental sigmoid belief network) pour l'extraction des caractéristiques , assez proche d'un réseau bayésien dynamique. L'avantage de cette technique est d'obtenir une représentation dense des mots (c.-à-d. un plongement de mot), étiquettes morphosyntaxiques, et autres caractéristiques linguistiques; cette dernière représentation (de plus faible dimension) véhicule par exemple une notion de similarité entre les mots dans un espace continu à  dimensions , ou même tout l'historique d'analyse lorsque le réseau est récurrent . En bref, les représentations denses bénéficient d'une forte capacité de généralisation .

Les modèles de caractéristiques dynamiques (indépendantes) évoquées au paragraphe précédent sélectionnent des éléments linguistiques (mots, étiquettes de dépendance...), dont les vecteurs de représentation (embeddings) sont souvent concaténés à l'entrée du réseau de neurones. Si le nombre de caractéristiques est sujet à varier, un moyen de conserver des vecteurs de taille fixe s'impose, du fait que l'entrée d'un réseau est de taille fixe. On peut par exemple effectuer une moyenne des vecteurs (représentation par « sac de mots continu » ou CBOW ).

Aujourd'hui, l'extraction des caractéristiques est réalisée avec des réseaux d'une complexité variable, composés d'unités LSTM par exemple (réseau LSTM empilé , LSTM bidirectionnel , etc.), un ISBN , ou en utilisant des réseaux dénués de récurrence, comme la première couche d'un perceptron multicouche . Certaines approches (dites character-based) apprennent même à représenter les mots à partir de caractères individuels, à l'image de SyntaxNet (2ème ver.)  et LSTM-Parser .

Quant au classificateur à proprement parler, il s'agit souvent d'un perceptron structuré, à l'image du système SyntaxNet (Parsey's Cousins) proposé par Google , dont le système révisé (ParseySaurus ) est un des plus précis à l'heure actuelle. Ces derniers systèmes sont initialement basés sur le Stanford Parser mis au point par Danqi Chen et Christopher Manning en 2014 , mais intègrent un réseau de neurones profond (et des fonctions d'activation différentes) avec entrainement structuré, sans compter le modèle probabiliste à normalisation globale  ou avec autonormalisation . Mais des systèmes du niveau de l'état de l'art, tels LSTM-Parser  ou DINN , n'ont pas forcément recours à un réseau profond, et utilisent par exemple une couche softmax en guise de classificateur (prédiction des actions élémentaires d'analyse).

 Méthodes basées sur des graphes 
Les modèles d’analyse basés sur les graphes sont des modèles discriminants (voir section « modèles statistiques d'analyse »). L’avantage des structures en dépendances, par rapport à celles en constituants, est de rendre ce type d’approche compatible avec une inférence exacte . En effet, une démarche répandue, initialement proposée par Ryan McDonald et coll., est de trouver l’arbre couvrant de poids maximum dans un graphe complet. Remarquons que dans ces conditions, le composant  n’est pas modélisé par un système autonome, mais par une propriété de la théorie des graphes. Toutefois, l’inférence exacte présuppose la limitation de la portée des caractéristiques à des sous-graphes ; par conséquent, d’autres techniques d’approximation ont été développées . Par rapport aux modèles basés sur des transitions, l'avantage de ce type de modèle est l'observation — en théorie — de propriétés sur toute la structure globale et/ou la phrase d'entrée sans restriction, alors que les propriétés sont limitées à un contexte structurellement local avec la première catégorie.

En pratique, seuls les modèles traitant le score de chaque arc isolément — dits « de 1er ordre » ou arc-factored — sont solubles de manière exacte en temps raisonnable, car la moindre augmentation de ces modèles engendre un problème NP-difficile . Cela présuppose que chaque relation de dépendance est indépendante des autres, ce qui est loin d'être vrai d'un point de vue linguistique. Néanmoins, certains systèmes de 1er ordre sont extrêmement compétitifs sur le plan de la précision, à l'image de celui de T. Dozat et C. Manning basé sur le mécanisme de deep biaffine attention . L'énorme majorité des systèmes de 1er ordre repose soit sur l'algorithme d'Eisner , soit sur l'algorithme glouton de Chu-Liu-Edmonds (CLE) . Le premier est un algorithme de programmation dynamique dérivé de CKY qui ne trouve donc que des structures projectives, tandis que le second trouve l'arbre couvrant de poids maximal et est, de ce fait, aussi capable de retourner un arbre de dépendances non-projectif.

Afin d'entrevoir une amélioration des performances tout en conservant un algorithme en temps polynomial, certaines approches ont étendu le chart de l'algorithme d'Eisner, ajoutant un facteur quadratique à la complexité à chaque augmentation de l'ordre du modèle . Les recherches dans ce sens se sont plus ou moins arrêtées aux modèles du 4ème ordre (complexité temporelle en ). Des stratégies plus récentes — et respectivement 200x et 5x plus rapides qu'un modèle exact du 3ème ordre — ont exploré l'élagage de l'espace de recherche avec l'usage de l'algorithme de vine parsing () , ou le maintien d'un faisceau d'alternatives intégré à l'algorithme d'Eisner (esprit du cube pruning ) , entre autres. Ces approximations permettent de diminuer drastiquement le coût de l'analyse, tout en conservant une précision au niveau des modèles exacts du 3ème ou 4ème ordre !

Quant aux modèles d'ordre supérieur capables de produire toute sorte d'arbres de dépendances (y.c. non-projectifs), ils passent nécessairement par une approximation, soit du décodage, soit de l'espace de recherche. La première option comprend les systèmes intégrant un post-traitement à l'issue de l'algorithme d'Eisner  ou CLE , qui réarrange les arcs ou combine les meilleurs arbres couvrants, respectivement. D'autres se basent sur le principe de décomposition duale , de relaxation continue , etc. La seconde catégorie inclut les procédés ne considérant qu'une infime partie de l'ensemble des arbres de dépendances non-projectifs , car certaines structures sont improbables linguistiquement parlant, et il est complètement inutile de tenter de les produire (ces dernières sont appelées mildly non-projective structures). Néanmoins, des expériences moins fructueuses furent tentées avec une optimisation linéaire en nombres entiers (ILP) .

Tous ces systèmes utilisent un algorithme d'apprentissage tel que le perceptron structuré, MIRA  (extension de ce dernier), un classificateur à entropie maximale (MaxEnt), etc. La plupart des systèmes évoqués au cours de cette section sélectionnent les caractéristiques de chaque sous-graphe (p. ex. un arc) à l'aide de modèles préétablis (représentation éparse). Cependant, quelques techniques récentes emploient un réseau de neurones pour l'extraction des caractéristiques: à propagation avant , ou récurrent  ; de plus, le score n'est plus calculé linéairement, mais notamment par un perceptron multicouche  , associé parfois à une transformation bilinéaire .

 Complexité de l'analyse de dépendances 
Voici un aperçu de la complexité temporelle des algorithmes d'analyse syntaxique pour les structures en dépendances. On différencie ceux capables de produire uniquement des structures projectives des algorithmes généraux, mais on ne considère que des versions exactes (exclut les approximations).

 Évaluation de l'analyse 
Tout système d’analyse syntaxique a besoin d’être évalué, afin de mesurer ses performances. Pour cela, on exécute la procédure d’analyse sur un ensemble de données de test, différent de l’ensemble d’entrainement (le cas échéant), et généralement beaucoup plus petit. Les structures produites par l’analyseur seront comparées aux structures de référence (gold-standard parses), considérées comme les meilleures analyses — qui sont annotées par des linguistes. Les mesures habituellement utilisées sont la précision et le rappel, souvent réunis en un seul et unique score appelé F-score , correspondant à la moyenne harmonique de la précision () et du rappel ()  :

La méthode la plus simple est de compter le nombre de phrases pour lesquelles la structure produite est identique à la structure de référence (exact match). Il s’agit d’un critère extrêmement rude, dans le sens où une seule erreur d’étiquette a le même impact qu’une analyse complètement erronée ; dès lors, on favorise plutôt les métriques fondées sur une correspondance partielle, dont la granularité est plus fine.

 De structures en constituants 
Les mesures communément utilisées sont celles liées aux métriques PARSEVAL , comptant le nombre de constituants qui correspondent à ceux présents dans la structure de référence.

 De structures en dépendances 
En ce qui concerne les structures de dépendances, la mesure communément utilisée est le score d’appartenance (attachment score) , qui détermine la proportion de mots correctement reliés au juste parent, en regard de la référence. Plusieurs variantes existent :

 Unlabeled attachment score (UAS) : une relation est considérée comme correcte si l’enfant est lié au parent attendu.
 Labeled attachment score (LAS) : une relation est considérée comme correcte si l’enfant est lié au parent attendu, et le type de la relation est fidèlement reproduit.
 Label accuracy score (LS) : on n’examine que l’étiquette d’une relation, sans tenir compte du parent.

Comme chaque unité lexicale possède exactement un parent, une seule mesure suffit pour qualifier la précision. Au niveau d’un corpus, le score global peut être calculé à l’échelle du mot (micro-average), c’est-à-dire sans tenir compte de la phrase à laquelle un mot appartient, ou à l’échelle de la phrase (macro-average), en effectuant la moyenne des scores de chacune d’entre elles.

 Notes et références 

 Références bibliographiques 

 Voir aussi 
 Bibliographie 

 Daniel Jurafsky et James H. Martin, Speech and Language Processing (2nd Edition), Prentice Hall, , 1024 
 Nitin Indurkhya et Fred J. Damerau (ed.), Handbook of Natural Language Processing (2nd Edition), Chapman & Hall, , 702 p.
A. V. Aho et J. D. Ullman, The Theory of Parsing, Translation, and Compiling, Vol. 1. Prentice Hall, 1972.
Christophe Moor, Multilingual Dependency Parsing from Raw Text to Universal Dependencies : The CLCL entry'', MSc thesis, Université de Genève, 2018.

Articles connexes 

 Traitement automatique du langage naturel
 Analyse sémantique
 Analyse lexicale
 Analyse syntaxique
 Arbre syntaxique
 Grammaire non contextuelle
 Grammaire de dépendance
 Algorithme de Cocke-Younger-Kasami
 Analyse Earley
 Programmation dynamique
 Classifieur linéaire
 Perceptron multicouche
 Réseau de neurones artificiels

Liens externes 

 Collins' Parser analyseur syntaxique de constituants historique basé sur les grammaires hors contexte probabilistes lexicalisées
 MaltParser analyseur syntaxique de dépendances statistique basé sur des transitions (implémenté en Java)
 MSTParser analyseur de dépendances basé sur les graphes (Java)
 IDP analyseur de dépendances basé sur des transitions et un modèle probabiliste génératif, intégrant un réseau de neurones récurrent (C)
 Stanford Parser analyseur de dépendances récent basé sur des transitions et intégrant un réseau de neurones

Traitement automatique du langage naturel
Syntaxe
En linguistique informatique ou en TALN , l' analyse syntaxique ( syntactic parsing ) réfère à le processus d' analyse automatisé d' une chaine de mots — représentant une phrase — dans le but d' obtenir les relations coexistant entre ces mots , par l' intermédiaire d' un arbre syntaxique . Lorsqu’ on part de texte brut , ce dernier doit avoir été segmenté en unités lexicales à le préalable ( tokenization ) . Habituellement , une analyse lexicale ( lemmatisation , analyse morphosyntaxique ... ) est exécutée avant l' analyse syntaxique proprement dite , afin d' identifier les unités lexicales et leurs propriétés . Le résultat de l' analyse est typiquement utilisé comme base dans l' analyse sémantique , construisant une représentation de le sens de le texte , ou directement dans de les applications telles que la correction grammaticale . Pour un système de réponse à les questions ou de recherche d' informations , il serait par exemple difficile de répondre correctement à la demande « quels ouvrages ont été écrits par de les auteurs francophones avant ? » sans reconnaitre le sujet « ouvrages » , car il faut notamment comprendre que l' utilisateur désire une liste d' ouvrages et non une liste d' auteurs . Le processus d' analyse peut se reposer sur une grammaire formelle et / ou faire appel à de les méthodes statistiques . Historique L’ analyse syntaxique remonte à les débuts de la recherche en TALN , puisqu’ un de les premiers algorithmes d’ analyse fut introduit par Victor Yngve en avant même le développement de la théorie de les langages formels par Noam Chomsky en . Dès lors , les analyseurs créés vont se fonder sur les grammaires formelles , particulièrement celles dites hors contexte ou de type Entre autres , John Cocke a inventé un algorithme de programmation dynamique en qui fut ensuite formalisé par T. Kasami et D. H. Younger \ : le célèbre algorithme CKY , analysant une séquence en temps cubique grâce à les grammaires en Forme normale de Chomsky . Ce dernier est de type mixte , c’est-à-dire combinant les stratégies ascendantes et descendantes , individuellement moins efficaces . Parallèlement , dans les années plusieurs autres formalismes destinés à l’ analyse syntaxique voient le jour , dont les grammaires de dépendances inspirées par Lucien Tesnièreet formalisées avant tout par David Hays Peu après N. Chomsky , John Backuset Peter Nauront indépendamment réinventé les grammaires hors contexte dans leur description de le langage ALGOL , donnant lieu à la célèbre forme de Backus-Naur . En Jay Earley inventa le premier algorithme d’ analyse syntaxique en temps cubique pour toutes les grammaires hors contexte ( pas nécessairement en forme normale ) \ . À la même époque , R. Kaplan et M. Kay ont généralisé l’ algorithme CKY à toutes les grammaires hors contexte pour en faire le chart parser , utilisant un graphe . Parmi les algorithmes similaires à les deux précédents , on peut encore citer celui de le coin gauche ( left-corner parser ) , en référence à le premier symbole de la partie droite d’ une règle de production \ . Beaucoup d’ autres formalismes ont été développés durant les années dont les réseaux de transition augmentés ( ATN ) , et les grammaires d’ unification ( Constraint-Based Grammars ) . Une représentation en dépendances de ces dernières a été originairement proposée par H. Maruyama \ . Durant les années les développements furent principalement tournés vers les méthodes statistiques , dont un travail important autour de les grammaires hors contexte probabilistes ( PCFG ) — un de les modèles d’ analyse statistique parmi les plus influents , qui est basé sur une grammaire formelle — dont les problèmes principaux sont l’ ignorance de les informations sémantiques et l’ hypothèse d’ indépendance de l’ attachement structurel de les syntagmes . Certaines approches plus récentes ont permis d’ améliorer les faiblesses de les PCFG par la lexicalisation de la grammaire , ou l’ utilisation d’ un jeu plus précis de symboles non terminaux , entre autres . De le côté de la représentation en dépendances , le premier algorithme stochastique influant fut proposé par Jason Eisner \ . Pour les méthodes qui ne requièrent pas l’ intervention d’ une grammaire , les modèles sont directement induits depuis de les données annotées ( corpus ) , ce qui facilite le portage de les systèmes à de nouvelles langues ou domaines . Bien que cette dernière possibilité soit majoritairement utilisée de nos jours , les méthodes basées sur de les grammaires restent utilisées lorsqu’ il n’ existe pas suffisamment de données annotées nécessaires à le fonctionnement de les méthodes supervisées . Notons à le passage qu’ une grammaire peut très bien être extraite de données linguistiques ; les méthodes basées sur les grammaires ( grammar-based parsing ) et celles guidées par de les données ( data-driven parsing ) ne sont donc pas mutuellement exclusives . La catégorisation suggérée de les méthodes statistiques d’ analyse est très répandue dans le domaine de le TALN \ . Difficultés L' analyse syntaxique est une tâche non triviale , principalement en raison de l’ ambiguïté intrinsèque de la langue et de sa diversité . Un énoncé est dit ambigu si plusieurs structures linguistiques peuvent y être associées . Voici quelques exemples d’ ambiguïtés structurelles:« Jean a vu l’ homme sur la colline avec un télescope » Dans cette phrase , l' attachement de le syntagme prépositionnel est ambigu , et on ne sait pas si Jean a utilisé un télescope pour voir l' homme , ou si Jean a vu un homme utilisant lui-même un télescope . « À qui avez -vous promis d’ écrire ? » La question précédente pourrait être paraphrasée de deux façons : « Vous avez promis d’ écrire à qui ? » ou « Vous avez promis à qui d’ écrire ? » ; on ne sait pas si la personne en question va écrire à quelqu'un , ou si elle a promis à quelqu'un d' écrire ( quelque chose ) . Lien avec l' analyse d' un langage formel Même si le but de l' analyse syntaxique d' un langage formel déterministe ( p. ex. langage de programmation ) est identique à celui de l' analyse syntaxique de la langue naturelle , la tâche est nettement plus ardue dans le second cas . Premièrement , la capacité générative d’ une grammaire — sa puissance — est beaucoup plus faible dans le cas de les langages informatiques , car ceux-ci doivent être strictement non ambigus et rapidement analysables ( donc la grammaire est restreinte ) . Comparativement , une grammaire prévue pour la langue naturelle doit permettre par exemple d’ exprimer de les dépendances entre de les mots éloignés les uns de les autres ; elle est donc plus complexe . Deuxièmement , comme la langue naturelle souffre d’ une ambiguïté structurelle , à chaque étape de l’ analyse , plusieurs règles de la grammaire seront probablement applicables . Ainsi , une phrase telle que « Jean a vu l’ homme [ sur la colline ] [ avec un télescope ] [ accompagné de sa fille ] [ ... ] » verra le nombre de ses analyses possibles augmenter exponentiellement avec le nombre de constituants ajoutés \ . À le passage , c’ est une de les raisons qui a poussé le développement de les méthodes statistiques . La dernière différence notable se situe à le niveau de la validité de la séquence d’ entrée \ : un langage de programmation possède un nombre fini de constructions valides , alors qu’ il est illimité pour une langue naturelle . De ce fait , l’ impossibilité de produire une analyse existe dans le cas de le TALN , erreur qui n’ est d' ailleurs pas nécessairement due à une grammaire inadéquate , mais possiblement à une erreur grammaticale , une faute de frappe , un mot inconnu , etc. Outre ces dissemblances caricaturales , de nombreuses autres existent , comme la délimitation stricte de les « phrases » ( déclarations , blocs ) et mots dans le cas de les langages formels avec de les caractères bien définis . Méthodes classiques Méthodes purement basées sur une grammaire La majorité de les premiers systèmes d' analyse syntaxique se fondent exclusivement sur une grammaire indépendante de contexte ( context-free grammar ) pour générer de les structures syntaxiques correctes , bien que ce type de grammaire ne soit pas suffisant pour engendrer la langue naturelle dans son ensemble \ . Conjointement , il est nécessaire d' avoir un algorithme qui dicte comment ces structures seront efficacement produites . Dans ce cadre -là , l’ algorithme de programmation dynamique CKY est énormément utilisé , dans lequel les sous-problèmes — maintenus dans un tableau — sont représentés par les arbres syntaxiques partiels enracinés sur les syntagmes de la phrase d' entrée . Grâce à la nature indépendante de le contexte de les grammaires , il est possible de réutiliser une sous-structure dans les dérivations suivantes qui la demande , rendant possible la programmation dynamique . Les algorithmes concurrents à CKY sont celui d' Earley et le chart parsing \ . Méthodes aidées par la statistique Le problème de les algorithmes assimilés à CKY est leur incapacité à résoudre les ambiguïtés structurelles ( voir section « difficultés » ) , bien qu' il soit possible de les détecter . Pour pallier ce manque , il est nécessaire d' ajouter une composante statistique à le modèle ; si chaque règle est accompagnée d' une probabilité , il suffit de sélectionner celle avec la probabilité la plus haute en cas d' ambiguïté . À ce titre , le formalisme le plus usité est la grammaire indépendante de contexte probabiliste ( probabilistic context-free grammar ou PCFG ) \ . Une version probabiliste de l' algorithme CKY existe , décrit avant tout par H. Ney \ . L' inférence exacte nécessite un temps en , où représente le nombre de règles de la grammaire . Cependant , le modèle de PCFG est relativement limité dans sa capacité à exceller , car il impose de fortes hypothèses d' indépendances . Le problème majeur est le fait que la probabilité d' une règle particulière soit indépendante de le contexte dans lequel elle est produite ; par exemple , la probabilité qu' un syntagme nominal soit étendu en pronom ( règle ) reste constante , que ce syntagme se trouve en position de sujet ou d' objet , alors que la première possibilité est bien plus fréquente pour certaines langues \ . Par ailleurs , si deux structures différentes utilisent exactement les mêmes règles , elles obtiendront la même probabilité ; or , pour une même phrase ( donc mêmes règles ) , il y a souvent une structure qui est préférée à une autre ( lorsque plusieurs possibilités existent ) , chose qui n' est pas véhiculée par le formalisme PCFG . Plusieurs modèles furent proposés dans le but de résoudre les problèmes cités ci-devant . Un de les plus influents est celui de Michael Collins , appelé LPCFG ou parfois head-driven , consistant à lexicaliser la grammaire par l' élection d' un élément prépondérant ( head rule ) pour chaque règle de la grammaire . De cette façon , chaque nœud parent de l' arbre syntaxique est " paramétré " par un mot de la phrase ; par exemple une règle pour une PCFG pourrait devenir si « le chien » fait partie de la phrase à analyser . Comme est l' élément prépondérant pour cette règle , le parent hérite de le mot « chien » . L' annotation de les nœuds non terminaux d' une PCFG , connue sous le nom de parent annotation , a aussi connu un grand succès pour l' analyse de constituants , car la précision de les systèmes implémentant cette technique est similaire à ceux à base de LPCFG , avec une moindre complexité \ . Une telle annotation pourrait être par exemple si compose un syntagme prépositionnel . Une autre solution à le manque de sensibilité structurelle de les PCFGs est le data oriented parsing ( DOP ) établi par Remko Scha et Rens Bod \ . Le principe est d' analyser de les phrases en combinant de les fragments d' analyses de phrases dont la structure est connue , comme celles provenant d' un corpus . Deux classes de modèles probabilistes existent : ceux dits génératifs , comme les LPCFGs , et ceux dits discriminants ( voir section « modèles statistiques d' analyse » pour plus de détails ) . Méthodes statistiques Avantages de la statistique Avec l’ approche classique , l’ analyse d’ une phrase peut donner lieu à de les millions d’ arbres syntaxiques possibles en raison de la grande taille de la grammaire , avec l’ impossibilité de choisir lequel reflète à le mieux la structure de la phrase en question . Si de les contraintes sont ajoutées à cette grammaire pour restreindre le nombre d’ analyses possibles , une partie de les phrases analysées risquent alors de ne plus avoir de structure correspondante . L’ approche statistique a l’ avantage de tolérer de les millions d’ analyses , tout en ayant la possibilité de sélectionner la meilleure en temps raisonnable ; à ce titre , il est souvent nécessaire de réduire l’ espace de recherche tout à le long de le processus d’ analyse , en éliminant les analyses partielles peu probables à le plus tôt . De nos jours , les grammaires ( seules ) ne sont quasiment plus utilisées , et les approches dans le domaine de le TALN font essentiellement appel à de les techniques d' apprentissage automatique . Qui plus est , la formalisation de les phénomènes linguistiques étant laborieuse , les techniques statistiques ont apporté l’ énorme avantage d’ extraire les connaissances linguistiques directement d’ échantillons ( réels ) de données . Et si la construction d’ un corpus ( treebank ) est plus fastidieuse que la construction d’ une grammaire , ce premier a l’ avantage d’ être réutilisable dans d’ autres systèmes ( dont les analyseurs morphosyntaxiques ) , expliquant en partie le désintérêt à l’ égard de les grammaires . En outre , les données contiennent implicitement de les statistiques , et l’ évaluation d’ un système est aisée . Notons qu’ une grammaire peut très bien être extraite de données linguistiques ; les méthodes basées sur les grammaires ( grammar-based parsing ) et celles guidées par de les données ( data-driven parsing ) — aujourd'hui majoritaires — ne sont donc pas mutuellement exclusives . Bien que les techniques statistiques soient utilisées pour désambiguïser — le cas échéant — le processus d’ analyse , l' espace de recherche ne peut qu' extrêmement rarement être exploré dans sa totalité , et il est nécessaire de le borner pour de les raisons d’ efficacité . Modèles statistiques d' analyse On peut représenter un analyseur syntaxique par une fonction , où est l’ ensemble de les entrées possibles , sachant que représente une séquence d’ entrée , et est l’ ensemble de les représentations syntaxiques admissibles . Relevons que la nature de la représentation d’ une analyse est spécifique à la théorie utilisée , à le même titre que son critère d’ admissibilité . Un modèle d' analyse syntaxique se décompose conceptuellement en deux parties \ : un composant génératif , qui fait correspondre une entrée à un ensemble d’ analyses candidates , donc ; un composant évaluatif , classant les analyses candidates selon un score numérique attribué , donc \ . Les deux composants ont généralement de les paramètres dont les valeurs vont être estimées statistiquement , en commençant par l’ analyse de données représentatives , nommées ensemble d’ entrainement , afin de faire de un bon estimateur de le correspondant . C’ est l’ étape d’ apprentissage de le modèle , qui peut être supervisée ou non supervisée ( parfois semi-supervisée ) ; un apprentissage supervisé nécessite que l’ analyse correcte soit présente dans les données . Toute la difficulté de cette étape est donc d’ utiliser correctement l’ évidence partielle — contenue dans les données — pour créer une distribution de probabilité reflétant à le plus près la réalité . À partir de la fonction , inférée à le moment de l’ apprentissage de le modèle , la seconde étape consiste à ordonner efficacement les analyses candidates pour une phrase d’ entrée ( inédite ) donnée \ : c’ est le problème d’ inférence . Cette dernière peut être exacte ou approximative , selon les garanties apportées par l’ algorithme utilisé . Il faut souvent trouver un juste compromis entre la complexité de le modèle et le manque d’ exactitude de les solutions générées . À le passage , notons le fait que l’ ensemble est vraisemblablement très grand , et que chaque est un objet possédant une structure interne riche ; ce constat contraste avec un simple problème de classification , pour lequel serait beaucoup plus petit . Les systèmes utilisant un algorithme d’ apprentissage supervisé sont beaucoup plus répandus , car ils sont bien plus performants \ . En outre , deux grandes classes de modèles s’ opposent en apprentissage automatique , pas nécessairement liées à les composants génératifs et évaluatifs mentionnés auparavant \ : la première possibilité , dite générative , est de voir le processus d’ analyse comme un système de réécriture probabiliste , où le but est de produire une ( ou plusieurs ) structures en fonction d’ une entrée donnée ; à chaque étape , il faudrait choisir la ( ou les ) meilleure ( s ) alternative ( s ) afin d’ obtenir la structure la plus probable à l’ issue de l’ analyse . Ici , le but est de maximiser la probabilité jointe , quel que soit et , en modélisant et , puis en les recombinant avec la règle de Bayes ( cas de les PCFGs ) . La seconde possibilité , dite discriminante , est de voir la grammaire comme un ensemble de contraintes sur les structures correctes , et la séquence d’ entrée comme une contrainte sur la position de les mots ; l’ analyse doit alors résoudre ces contraintes , puis sélectionner la structure syntaxique la plus probable parmi celles répondant le mieux à les contraintes . Dans ce cas , on cherche à modéliser la probabilité conditionnelle directement depuis les données . Encore , les deux approches peuvent être combinées de façon séquentielle ( reranking ) \ . Modèles génératifs La dérivation de la structure syntaxique est modélisée par un processus stochastique pour lequel chaque étape dépend d’ événements apparus par le passé ( historique ) . La forme générale de tels modèles , évoqués initialement par G. Leech , est la suivante \ : où la fonction définit quels événements de l' historique sont pris en compte . Bien que ce soit souvent le cas , le composant génératif est un système de dérivations qui n' est pas forcément contraint par une grammaire formelle ( le modèle de l' analyseur IDP est un exemple ) . L' évaluation se fait selon la probabilité jointe , factorisée en probabilités conditionnelles . À noter que se ramène à car , pour une structure donnée , la probabilité est égale à si est la phrase unique correspondant à cette structure ; par conséquent , si engendre , ou dans tous les autres cas . Les modèles génératifs imposent de les hypothèses d' indépendance rigides , ce qui a un impact sur la désambiguïsation ( typiquement les PCFGs ) . Toutefois , l' adaptation de ces hypothèses donne de les modèles plus complexes et l' inférence exacte n' est plus possible ( voir aussi section « méthodes aidées par la statistique » ) . Fondamentalement , ce genre de modèle doit prédire le prochain mot à mesure que l' analyse avance , ce qui nécessite une normalisation globale à travers le vocabulaire entier , et souvent un faisceau plus grand ( le cas échéant ) , de façon à pouvoir « essayer » un grand nombre de structures sur la partie de phrase incluant le mot prédit \ . Par ailleurs , l' entrainement de les modèles génératifs cherche la plupart de le temps à maximiser la probabilité jointe de les entrées-sorties de l' ensemble d' entrainement ; or , le but de l' analyse est de maximiser la précision de le modèle pour de les phrases inédites . Pour ces raisons , les modèles discriminants sont de plus en plus utilisés . Modèles localement discriminants Le but de ces modèles est de maximiser la probabilité de décisions locales , en espérant atteindre la meilleure solution globale grâce à la succession de décisions ( locales ) optimales , à l' instar de les modèles génératifs basés sur un historique \ : Ici , la fonction représente de les propriétés / traits arbitraires dépendant de l’ historique de les décisions prises , ; autrement dit , on définit une classe d’ équivalence pour toute combinaison d’ un historique et d’ une entrée . En employant de les méthodes de prévision sur l’ entrée , certains analyseurs approchent une analyse déterministe ( prédictive ) . Pour ce type de modèle , le composant génératif est constitué d’ un processus incrémental ( p. ex. automate ) , alors que le composant évaluatif doit être capable d’ assigner un score à une décision locale donnée , et de combiner ces scores en scores globaux , évaluant une séquence complète de transitions . Parfois , ce type de modèle est appelé « génératif » , car il implique de les hypothèses d' indépendance comme les modèles véritablement génératifs — modélisant la probabilité jointe — mais sur de les décisions locales , et non pas sur de les décisions globales \ . L' approche locale à l' avantage de favoriser la prise en considération de traits caractéristiques utiles à la désambiguïsation , problématique principale de les véritables modèles génératifs . Cette catégorie de modèles permet d' obtenir de les analyseurs beaucoup plus rapides que ceux à base de modèles génératifs ( p. ex . de l' ordre de ) . Modèles discriminants Cette classe de modèles définit typiquement la fonction d’ évaluation comme étant le produit d’ un vecteur de traits ( caractéristiques ) et d’ un vecteur de poids \ : où chaque représente une caractéristique de et , et chaque quantifie l’ importance de la caractéristique pour l’ analyse optimale . Si ce poids est négatif , la caractéristique dessert l’ analyse , alors que dans le cas contraire , la caractéristique influe positivement sur l’ analyse optimale . La nature de les caractéristiques n’ est pas limitée ; la seule restriction est de pouvoir les encoder sous forme numérique . On peut par exemple utiliser le score fourni par un autre analyseur en tant que caractéristique , ou tenir compte de la présence / absence d' une sous-structure . Donc , un modèle véritablement discriminant définit un unique score sur la structure globale d’ une analyse . L’ avantage est de pouvoir observer de les propriétés globales de les structures syntaxiques , et de pouvoir tenir compte ( ajouter ) de nouvelles contraintes sans altérer la dérivation de le modèle \ . Pour cette classe , le composant génératif est assez variable d’ un système à l' autre , tandis que le composant d’ évaluation est établi par une combinaison linéaire de caractéristiques pondérées , non restreintes par un quelconque processus , et dont les poids sont fixés par un modèle d’ apprentissage discriminant . Le défaut de ce type de modèle est le besoin de réanalyser l' ensemble d' entrainement à chaque itération , ce qui est naturellement gourmand en ressources . Certaines approches , dites de reranking , se sont contentées d' utiliser ce genre de modèle uniquement pour un sous-ensemble de , lui-même obtenu via un modèle génératif \ . Cependant , la meilleure analyse ne se trouve pas forcément dans ce dernier sous-ensemble , ce qui en fait une technique pas idéale . Néanmoins , les problèmes d' efficacité sont moins marqués dans l' analyse de dépendances que dans celle de constituants , et ils sont beaucoup utilisés dans le premier cas où l' inférence exacte est même possible sous certaines conditions ( voir section « méthodes basées sur de les graphes » ) . Paradigmes d' analyse Actuellement , la représentation de les structures syntaxiques la plus populaire est celle en dépendances , en raison de le bon compromis expressivité / efficacité de les algorithmes qu' elle propose , et de les performances obtenues pour une grande variété de langues \ . Avec cette représentation , ce sont très souvent de les modèles probabilistes localement discriminants ou discriminants qui sont utilisés , contrairement à la représentation en constituants , pour laquelle les modèles génératifs sont plus compétitifs \ . Toutefois , il est intéressant de relever que certains systèmes récents ( p. ex . ) , particulièrement performants , sont fondés sur l' assemblage de modèles de types différents ( technique densemble ou system combination ) \ . On peut classer l’ immense majorité de les modèles d’ analyse statistique de dépendances en deux familles \ : Les méthodes basées sur de les transitions ( transition-based ) reposent sur un automate à états finis permettant de générer une structure syntaxique à partir d’ une phrase donnée . À le long de l’ analyse , le modèle appris doit être en mesure de prédire la prochaine transition , en fonction de l’ historique de les transitions , de manière à pouvoir trouver la séquence optimale de transitions menant à la meilleure analyse possible de la phrase d’ entrée . Les méthodes basées sur de les graphes ( graph-based ) définissent un univers d’ analyses candidates pour une phrase donnée . L’ apprentissage se résume à induire un modèle capable d’ évaluer ces analyses candidates dans leur ensemble ; le processus d’ analyse doit trouver la structure , tel que son score soit le plus élevé , correspondant à la phrase d’ entrée . Dans le premier cas , la stratégie est de trouver la meilleure solution locale ( approche gloutonne ) , alors que dans le second cas , le raisonnement revêt l’ apparence d’ une recherche exhaustive . En outre , la première méthode est parfois dénommée shift-reduce parsing , de le nom de l’ algorithme d’ analyse utilisé par bon nombre d’ implémentations \ . C' est une méthode très populaire en raison de son excellente efficacité : la complexité de l' algorithme d' analyse typique est linéaire ( relativement à le nombre de mots de la phrase d' entrée ) . Quant à la seconde méthode , on la retrouve parfois sous le nom de maximum spanning tree parsing ( MST ) , qui correspond à le nom de l’ algorithme utilisé par le système ayant introduit cette technique \ . En Jinho Choi et coll . ont étudié les performances de dix analyseurs syntaxiques compétitifs de dépendances , de façon détaillée et selon différentes métriques \ . Méthodes basées sur de les transitions Les modèles basés sur de les transitions sont de les modèles localement discriminants avec un apprentissage discriminant , dans le sens où seule l’ estimation de l’ analyse finale est extraite de la distribution probabiliste , en recourant par exemple à une surface de décision . Cela s’ oppose à les modèles conditionnels , où toute la densité de probabilité conditionnelle serait optimisée \ . En supposant une fonction d’ évaluation assignant un score à les transitions possibles en fonction d’ une configuration , représentée par un vecteur , ainsi qu’ un moyen d’ évaluer une séquence complète de transitions , l’ analyse revient à trouver la séquence ayant le score le plus élevé . À ce titre , la plupart de les systèmes implémentent une recherche en faisceau \ . Une méthode très en vogue pour l’ analyse de structures de dépendances est l’ usage d’ un classificateur ( entrainé sur un corpus ) , afin de prédire la prochaine action exécutée par un algorithme d’ analyse déterministe . Cette démarche est parfois appelée « pseudo-déterministe » , en référence à les algorithmes d’ analyse déterministes appliqués à de les grammaires non ambiguës ( langages formels ) . Dans le cas présent , l’ espace de recherche est intrinsèquement limité par le procédé de l’ algorithme , puisqu’ une seule action choisie implique l’ abandon de toutes les autres ; en raison de cette approche gloutonne , l’ élagage est donc très agressif . Cette force est également un désavantage , car un mauvais choix précoce peut se répercuter négativement sur l’ analyse finale \ . Un système d’ analyse basé sur un classificateur se compose de trois ingrédients essentiels \ : un algorithme d’ analyse syntaxique qui établit une analyse par la succession d’ actions élémentaires ( via un système de transitions ) ; un modèle permettant de décrire tout état de l’ analyseur ( configurations de le système de transitions ) par un vecteur de caractéristiques ; un classificateur qui transforme un état , sous forme de vecteur de caractéristiques , en une action de l’ algorithme d’ analyse . Cette approche a été initiée par T. Kudo et Y. Matsumoto , qui ont proposé une implémentation couplée à un classificateur de type machine à vecteur de support , pour l’ analyse en dépendances non étiquetées de le japonais . En utilisant la base de l’ algorithme de Joakim Nivre , l’ idée a par la suite été étendue itérativement à les dépendances étiquetées pour le suédois , puis pour l’ anglais , puis àlangues , avant d’ être optimisée pour former le logiciel MaltParser \ . Les premiers algorithmes sont limités à les structures projectives , mais G. Attardi , parmi d’ autres , proposa un algorithme étendu à un sous-ensemble de les structures non-projectives . À ce titre , J. Nivre propose une version online-reordering de son système de transitions , tandis que d' autres approches passent par une décomposition en ( sous-)arbres de dépendances planaires et l' analyse de chaque plan séparément ( mltiplanar parsing ) \ . Une autre solution implique un pré/ post-traitement de les données ( appelé pseudo-projectivization ) \ . Les problèmes principaux de ce paradigme sont la sensibilité à les erreurs de recherche et la propagation de les erreurs due à le processus incrémental univoque . Pour tenter d' améliorer la précision , tout en maintenant une analyse hautement efficace , plusieurs techniques ont vu le jour . Certains ont relaxé le processus strictement déterministe — en gardant les K meilleures analyses ( recherche en faisceau ) — associé parfois à un entrainement en tant que prédiction structurée , tandis que d' autres ont abandonné l' analyse purement séquentielle de gauche à droite ( easy-first parsing ) , car la recherche en faisceau ralentit substantiellement l' analyse . Dans le même but , J. Nivre a expérimenté l' usage d' un oracle dynamique — à la fois non déterministe et complet ( contrairement à les oracles statiques habituels ) — pour son système de transitions arc-eager \ . Cependant , ces oracles induisent une grande complexité lorsqu' ils sont utilisés avec de les systèmes généraux ( non limités à les structures projectives ) , et il n' est pas toujours possible de les dériver . Pour cette raison , M. Straka et coll . ont introduit une nouvelle classe d' oracles dénommés search-based oracles , qui est une approximation de les oracles dynamiques . En pratique , de les modèles probabilistes sont définis pour chaque action de l' algorithme d' analyse , en fonction de son contexte courant ; cependant , les modèles fondés sur un historique d’ actions ( ou transitions ) doivent faire face à une quantité illimitée d’ informations , rendant une modélisation probabiliste impossible . Ce problème est ordinairement résolu en limitant l’ historique à un ensemble fini de caractéristiques \ . À ce moment -là , la difficulté majeure réside dans le choix de la représentation de cet historique , c’est-à-dire son aperçu , à partir de lequel la probabilité de l’ action suivante pourra être convenablement estimée . Comme cette probabilité est indépendante de toute information à le sujet de l’ historique qui ne serait pas contenue dans son aperçu , la qualité de l’ analyse peut être fortement affectée par les caractéristiques retenues . La recherche dans le domaine de l’ analyse syntaxique statistique a débuté à le milieu de les années et s’ est principalement focalisée sur les modèles linéaires , durant de nombreuses années . Avec de tels modèles , le score attribué à une analyse est calculé selon une combinaison de traits structurels ou de caractéristiques morphologiques — dont la représentation est naturellement éparse — liées à la structure en question . Or , cela demande une sélection manuelle , plausiblement fastidieuse , de les combinaisons de traits à inclure dans l’ évaluation , avant l’ utilisation d’ un algorithme d’ apprentissage . Par conséquent , l’ adaptation de ces modèles à de nouvelles langues ou de nouveaux domaines est difficile et coûteuse ; de plus , l’ oubli d’ une caractéristique importante peut se répercuter très négativement sur la précision ( problème d' incomplétude ) \ . Par ailleurs , les analyseurs passent le plus clair de leur temps à extraire les caractéristiques , et non à l' analyse en elle-même \ . Toutes ces raisons ont motivé le développement de modèles non linéaires '' ' , susceptibles d’ induire automatiquement une combinaison appropriée de les traits prédictifs ; dans de tels cas , un réseau de neurones artificiels seconde ou remplace majoritairement le classificateur linéaire . Avec la plupart de les modèles , il est néanmoins nécessaire de leur fournir un nombre restreint ( env.de caractéristiques dynamiques simples ( c.-à -d. non combinées ) . Cette voie fut initiée par James Henderson à le début de les années puis approfondie enavec un analyseur fondé sur un modèle probabiliste purement génératif et équipé d' un réseau ISBN ( incremental sigmoid belief network ) pour l' extraction de les caractéristiques , assez proche d' un réseau bayésien dynamique . L' avantage de cette technique est d' obtenir une représentation dense de les mots ( c.-à -d. un plongement de mot ) , étiquettes morphosyntaxiques , et autres caractéristiques linguistiques ; cette dernière représentation ( de plus faible dimension ) véhicule par exemple une notion de similarité entre les mots dans un espace continu à dimensions , ou même tout l' historique d' analyse lorsque le réseau est récurrent \ . En bref , les représentations denses bénéficient d' une forte capacité de généralisation \ . Les modèles de caractéristiques dynamiques ( indépendantes ) évoquées à le paragraphe précédent sélectionnent de les éléments linguistiques ( mots , étiquettes de dépendance ... ) , dont les vecteurs de représentation ( embeddings ) sont souvent concaténés à l' entrée de le réseau de neurones . Si le nombre de caractéristiques est sujet à varier , un moyen de conserver de les vecteurs de taille fixe s' impose , de le fait que l' entrée d' un réseau est de taille fixe . On peut par exemple effectuer une moyenne de les vecteurs ( représentation par « sac de mots continu » ou CBOW ) . Aujourd'hui , l' extraction de les caractéristiques est réalisée avec de les réseaux d' une complexité variable , composés d' unités LSTM par exemple ( réseau LSTM empilé , LSTM bidirectionnel , etc. ) , un ISBN , ou en utilisant de les réseaux dénués de récurrence , comme la première couche d' un perceptron multicouche \ . Certaines approches ( dites character-based ) apprennent même à représenter les mots à partir de caractères individuels , à l' image de SyntaxNetme ver . ) et LSTM-Parser \ . Quant à le classificateur à proprement parler , il s' agit souvent d' un perceptron structuré , à l' image de le système SyntaxNet ( Parsey's Cousins ) proposé par Google , dont le système révisé ( ParseySaurus ) est un de les plus précis à l' heure actuelle . Ces derniers systèmes sont initialement basés sur le Stanford Parser mis à le point par Danqi Chen et Christopher Manning en , mais intègrent un réseau de neurones profond ( et de les fonctions d' activation différentes ) avec entrainement structuré , sans compter le modèle probabiliste à normalisation globale ou avec autonormalisation \ . Mais de les systèmes de le niveau de l' état de l' art , tels LSTM-Parser ou DINN , n' ont pas forcément recours à un réseau profond , et utilisent par exemple une couche softmax en guise de classificateur ( prédiction de les actions élémentaires d' analyse ) . Méthodes basées sur de les graphes Les modèles d’ analyse basés sur les graphes sont de les modèles discriminants ( voir section « modèles statistiques d' analyse » ) . L’ avantage de les structures en dépendances , par rapport à celles en constituants , est de rendre ce type d’ approche compatible avec une inférence exacte \ . En effet , une démarche répandue , initialement proposée par Ryan McDonald et coll. , est de trouver l’ arbre couvrant de poids maximum dans un graphe complet . Remarquons que dans ces conditions , le composant n’ est pas modélisé par un système autonome , mais par une propriété de la théorie de les graphes . Toutefois , l’ inférence exacte présuppose la limitation de la portée de les caractéristiques à de les sous-graphes ; par conséquent , d’ autres techniques d’ approximation ont été développées \ . Par rapport à les modèles basés sur de les transitions , l' avantage de ce type de modèle est l' observation — en théorie — de propriétés sur toute la structure globale et / ou la phrase d' entrée sans restriction , alors que les propriétés sont limitées à un contexte structurellement local avec la première catégorie . En pratique , seuls les modèles traitant le score de chaque arc isolément — dits « der ordre » ou arc-factored — sont solubles de manière exacte en temps raisonnable , car la moindre augmentation de ces modèles engendre un problème NP-difficile \ . Cela présuppose que chaque relation de dépendance est indépendante de les autres , ce qui est loin d' être vrai d' un point de vue linguistique . Néanmoins , certains systèmes der ordre sont extrêmement compétitifs sur le plan de la précision , à l' image de celui de T. Dozat et C. Manning basé sur le mécanisme de deep biaffine attention \ . L' énorme majorité de les systèmes der ordre repose soit sur l' algorithme d' Eisner , soit sur l' algorithme glouton de Chu-Liu-Edmonds ( CLE ) \ . Le premier est un algorithme de programmation dynamique dérivé de CKY qui ne trouve donc que de les structures projectives , tandis que le second trouve l' arbre couvrant de poids maximal et est , de ce fait , aussi capable de retourner un arbre de dépendances non-projectif . Afin d' entrevoir une amélioration de les performances tout en conservant un algorithme en temps polynomial , certaines approches ont étendu le chart de l' algorithme d' Eisner , ajoutant un facteur quadratique à la complexité à chaque augmentation de l' ordre de le modèle \ . Les recherches dans ce sens se sont plus ou moins arrêtées à les modèles dume ordre ( complexité temporelle en ) . De les stratégies plus récentes — et respectivement et plus rapides qu' un modèle exact dume ordre — ont exploré l' élagage de l' espace de recherche avec l' usage de l' algorithme de vine parsing ( ) , ou le maintien d' un faisceau d' alternatives intégré à l' algorithme d' Eisner ( esprit de le cube pruning ) , entre autres . Ces approximations permettent de diminuer drastiquement le coût de l' analyse , tout en conservant une précision à le niveau de les modèles exacts dume oume ordre ! Quant à les modèles d' ordre supérieur capables de produire toute sorte d' arbres de dépendances ( y.c. non-projectifs ) , ils passent nécessairement par une approximation , soit de le décodage , soit de l' espace de recherche . La première option comprend les systèmes intégrant un post-traitement à l' issue de l' algorithme d' Eisner ou CLE , qui réarrange les arcs ou combine les meilleurs arbres couvrants , respectivement . D' autres se basent sur le principe de décomposition duale , de relaxation continue , etc. La seconde catégorie inclut les procédés ne considérant qu' une infime partie de l' ensemble de les arbres de dépendances non-projectifs , car certaines structures sont improbables linguistiquement parlant , et il est complètement inutile de tenter de les produire ( ces dernières sont appelées mildly non-projective structures ) . Néanmoins , de les expériences moins fructueuses furent tentées avec une optimisation linéaire en nombres entiers ( ILP ) \ . Tous ces systèmes utilisent un algorithme d' apprentissage tel que le perceptron structuré , MIRA ( extension de ce dernier ) , un classificateur à entropie maximale ( MaxEnt ) , etc. La plupart de les systèmes évoqués à le cours de cette section sélectionnent les caractéristiques de chaque sous-graphe ( p. ex. un arc ) à l' aide de modèles préétablis ( représentation éparse ) . Cependant , quelques techniques récentes emploient un réseau de neurones pour l' extraction de les caractéristiques : à propagation avant , ou récurrent ; de plus , le score n' est plus calculé linéairement , mais notamment par un perceptron multicouche , associé parfois à une transformation bilinéaire \ . Complexité de l' analyse de dépendances Voici un aperçu de la complexité temporelle de les algorithmes d' analyse syntaxique pour les structures en dépendances . On différencie ceux capables de produire uniquement de les structures projectives de les algorithmes généraux , mais on ne considère que de les versions exactes ( exclut les approximations ) . Évaluation de l' analyse Tout système d’ analyse syntaxique a besoin d’ être évalué , afin de mesurer ses performances . Pour cela , on exécute la procédure d’ analyse sur un ensemble de données de test , différent de l’ ensemble d’ entrainement ( le cas échéant ) , et généralement beaucoup plus petit . Les structures produites par l’ analyseur seront comparées à les structures de référence ( gold-standard parses ) , considérées comme les meilleures analyses — qui sont annotées par de les linguistes . Les mesures habituellement utilisées sont la précision et le rappel , souvent réunis en un seul et unique score appelé F-score , correspondant à la moyenne harmonique de la précision ( ) et de le rappel ( ) \ : La méthode la plus simple est de compter le nombre de phrases pour lesquelles la structure produite est identique à la structure de référence ( exact match ) . Il s’ agit d’ un critère extrêmement rude , dans le sens où une seule erreur d’ étiquette a le même impact qu’ une analyse complètement erronée ; dès lors , on favorise plutôt les métriques fondées sur une correspondance partielle , dont la granularité est plus fine . De structures en constituants Les mesures communément utilisées sont celles liées à les métriques PARSEVAL , comptant le nombre de constituants qui correspondent à ceux présents dans la structure de référence . De structures en dépendances En ce qui concerne les structures de dépendances , la mesure communément utilisée est le score d’ appartenance ( attachment score ) , qui détermine la proportion de mots correctement reliés à le juste parent , en regard de la référence . Plusieurs variantes existent \ : Unlabeled attachment score ( UAS ) \ : une relation est considérée comme correcte si l’ enfant est lié à le parent attendu . Labeled attachment score ( LAS ) \ : une relation est considérée comme correcte si l’ enfant est lié à le parent attendu , et le type de la relation est fidèlement reproduit . Label accuracy score ( LS ) \ : on n’ examine que l’ étiquette d’ une relation , sans tenir compte de le parent . Comme chaque unité lexicale possède exactement un parent , une seule mesure suffit pour qualifier la précision . À le niveau d’ un corpus , le score global peut être calculé à l’ échelle de le mot ( micro-average ) , c’est-à-dire sans tenir compte de la phrase à laquelle un mot appartient , ou à l’ échelle de la phrase ( macro-average ) , en effectuant la moyenne de les scores de chacune d’ entre elles . Notes et références Références bibliographiques Voir aussi Bibliographie Daniel Jurafsky et James H. Martin , Speech and Language Processingd Edition ) , Prentice Hall , , Nitin Indurkhya et Fred J. Damerau ( ed. ) , Handbook of Natural Language Processingd Edition ) , Chapman & Hall ,,p. A. V. Aho et J. D. Ullman , The Theory of Parsing , Translation , and Compiling , Vol . Prentice Hall , Christophe Moor , Multilingual Dependency Parsing from Raw Text to Universal Dependencies \ : The CLCL entry '' , MSc thesis , Université de Genève , Articles connexes Traitement automatique de le langage naturel Analyse sémantique Analyse lexicale Analyse syntaxique Arbre syntaxique Grammaire non contextuelle Grammaire de dépendance Algorithme de Cocke-Younger-Kasami Analyse Earley Programmation dynamique Classifieur linéaire Perceptron multicouche Réseau de neurones artificiels Liens externes Collins' Parser analyseur syntaxique de constituants historique basé sur les grammaires hors contexte probabilistes lexicalisées MaltParser analyseur syntaxique de dépendances statistique basé sur de les transitions ( implémenté en Java ) MSTParser analyseur de dépendances basé sur les graphes ( Java ) IDP analyseur de dépendances basé sur de les transitions et un modèle probabiliste génératif , intégrant un réseau de neurones récurrent ( C ) Stanford Parser analyseur de dépendances récent basé sur de les transitions et intégrant un réseau de neurones Traitement automatique de le langage naturel Syntaxe