Analyse syntaxique de la langue naturelle

Un article de Wikipédia, l'encyclopédie libre.
Sauter à la navigation Sauter à la recherche
Page d'aide sur l'homonymie Pour les articles homonymes, voir Analyseur.

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[modifier | modifier le code]

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 [1]. 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) [2] et D. H. Younger (1967) [3] : 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 dédié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) [4]. À la même époque, R. Kaplan [5] et M. Kay [6] 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 [7].

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 [8]. 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) [9] — 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 [10], ou l’utilisation d’un jeu plus précis de symboles non terminaux [11], entre autres. Du côté de la représentation en dépendances, le premier algorithme stochastique influant fut proposé par Jason Eisner [12].

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 [13].

Difficultés[modifier | modifier le code]

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[modifier | modifier le code]

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 [14]. 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[modifier | modifier le code]

Méthodes purement basées sur une grammaire[modifier | modifier le code]

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 [Note 1]. 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 [4] et le chart parsing [5],[6].

Méthodes aidées par la statistique[modifier | modifier le code]

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) [9]. Une version probabiliste de l'algorithme CKY existe, décrit avant tout par H. Ney [15]. 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 [13]. 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 [16], 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 [17], 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é [18]. 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 [19],[20]. 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[modifier | modifier le code]

Avantages de la statistique[modifier | modifier le code]

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[modifier | modifier le code]

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 [13] :

  1. un composant génératif , qui fait correspondre une entrée à un ensemble d’analyses candidates , donc ;
  2. 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 [13].

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) structure(s) 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) [21].

Modèles génératifs[modifier | modifier le code]

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 [22], 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 pas une grammaire formelle (le modèle de l'analyseur IDP est un exemple [23]). 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 impacte 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 [23]. 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[modifier | modifier le code]

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, et de l’entrée  ; 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 [13]. 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 [23]).

Modèles discriminants[modifier | modifier le code]

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 [21]. 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é d'utiliser ce genre de modèle uniquement pour un sous-ensemble de , lui-même obtenu via un modèle génératif [24],[25],[21]. Cependant, la meilleure analyse ne se trouve pas forcément dans ce dernier sous-ensemble [24], 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 [13] (voir section « méthodes basées sur des graphes »).

Paradigmes d'analyse[modifier | modifier le code]

Actuellement, la représentation des structures syntaxiques la plus populaire est celle en dépendances [Note 2], en raison du bon compromis expressivité/efficacité des algorithmes qu'elle propose [26],[27], et des performances obtenues pour une grande variété de langues [28],[29]. 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 [13]. Toutefois, il est intéressant de relever que certains systèmes récents (p. ex. [30], [31]), particulièrement performants, sont fondés sur l'assemblage de modèles de types différents (technique d'ensemble ou system combination) [32].

Exemple de structure en dépendances pour la phrase « J'ai un chien brun ».

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

  • 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 [34]. 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 [35]. 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 [36].

Méthodes basées sur des transitions[modifier | modifier le code]

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 [37]. 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 [13].

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 [38].

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 [39], 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 [34], 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 [40], avant d’être optimisée pour former le logiciel MaltParser [41]. Les premiers algorithmes sont limités aux structures projectives, mais G. Attardi [42], parmi d’autres [27],[43], 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 [44], 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) [45]. Une autre solution implique un pré/post-traitement des données (appelé pseudo-projectivization) [46].

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) [47] — associé parfois à un entrainement en tant que prédiction structurée [48], tandis que d'autres ont abandonné l'analyse purement séquentielle de gauche à droite (easy-first parsing) [49], 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 [50]. 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 [51], 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 [52]. À 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 impacté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) [53]. Par ailleurs, les analyseurs passent le plus clair de leur temps à extraire les caractéristiques [Note 3], et non à l'analyse en elle-même [54]. 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 [55],[56] 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 [23], 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 [53], ou même tout l'historique d'analyse lorsque le réseau est récurrent [23]. En bref, les représentations denses bénéficient d'une forte capacité de généralisation [57].

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 [58]).

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é [59], LSTM bidirectionnel [60], etc.), un ISBN [61], ou en utilisant des réseaux dénués de récurrence, comme la première couche d'un perceptron multicouche [53],[62]. Certaines approches (dites character-based) apprennent même à représenter les mots à partir de caractères individuels, à l'image de SyntaxNet (2ème ver.) [63] et LSTM-Parser [64].

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 [62], dont le système révisé (ParseySaurus [63]) 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 [53], 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 [62] ou avec autonormalisation [63],[Note 4]. Mais des systèmes du niveau de l'état de l'art, tels LSTM-Parser [64] ou DINN [61], 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[modifier | modifier le code]

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 [13]. En effet, une démarche répandue, initialement proposée par Ryan McDonald et coll. [35], 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 [65]. 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 [66]. 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 [67]. L'énorme majorité des systèmes de 1er ordre repose soir sur l'algorithme d'Eisner [68], soit sur l'algorithme glouton de algorithme de Chu-Liu-Edmonds (en) (CLE) [69]. 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 [70],[71],[72]. 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 ([73]) ,[74], ou le maintient d'un faisceau d'alternatives intégré à l'algorithme d'Eisner (esprit du cube pruning [75]) [76], 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 [65] ou CLE [77], qui réarrange les arcs ou combine les meilleurs arbres couvrants, respectivement. D'autres se basent sur le principe de décomposition duale [78],[79],[80], de relaxation continue [81], 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 [82],[83],[84],[85], 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) [86].

Tous ces systèmes utilisent un algorithme d'apprentissage tel que le perceptron structuré, MIRA [87] (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 [88], ou récurrent [60],[67] ; de plus, le score n'est plus calculé linéairement, mais notamment par un perceptron multicouche [88], [60], associé parfois à une transformation bilinéaire [67].

Complexité de l'analyse de dépendances[modifier | modifier le code]

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).

Proj. Non-proj.
Analyse transition-based [34] [27],[43]

en pratique [44],[45]

Analyse graph-based — 1er ordre [35] [35]
Analyse graph-based — nème ordre (n>1) FP [65],[70],... FNP-complet [66]

Évaluation de l'analyse[modifier | modifier le code]

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 [89], 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[modifier | modifier le code]

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

De structures en dépendances[modifier | modifier le code]

En ce qui concerne les structures de dépendances, la mesure communément utilisée est le score d’appartenance (attachment score) [92], 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[modifier | modifier le code]

  1. Typiquement, les dépendances croisées (ou non-projectives) — apparaissant dans certaines langues — ne peuvent pas être obtenues avec une grammaire de type 2. La langue naturelle est par conséquent de type 1 (contextuelle), mais néanmoins très proche du type 2.
  2. Un arbre de dépendances est formellement un graphe orienté étiqueté simple, connexe et acyclique, comportant une seule racine, muni d'une relation de préséance linéaire sur l'ensemble des sommets (ordre des mots).
  3. Cela correspond à la combinaison d'éléments linguistiques (mots...), puis à la recherche dans une structure de données contenant plusieurs millions d'éléments.
  4. Tous les systèmes précédents utilisent une normalisation locale, bien moins complexe à calculer. Il est d'ailleurs impossible de calculer des probabilités globalement normalisées en temps raisonnable; ces systèmes passent donc par une approximation.

Références bibliographiques[modifier | modifier le code]

  1. Jacqueline Léon, Histoire de l'automatisation des sciences du langage, ENS Éditions, coll. « Langages », (ISBN 9782847886801, DOI 10.4000/books.enseditions.3733, lire en ligne)
  2. Tadao Kasami, « An efficient recognition and syntax algorithm for context-free languages », Technical Report AFCLR-65-758, Air Force Cambridge Research Laboratory, 1965
  3. D. H. Younger, « Recognition of context-free languages in time n3 », Information and Control, vol. 10, no 2, 1967, p. 189-208.
  4. a et b Jay Earley, « An efficient context-free parsing algorithm », In : Communications of the ACM 13 (2), p. 94-102, 1970
  5. a et b Ronald M. Kaplan, « A general syntactic processor », In : Natural Language Processing, Sous la dir. de R. Rustin, Algorithmics Press, p. 193-241, 1973
  6. a et b Martin Kay, « Algorithm Schemata and Data Structures in Syntactic Processing », Report CSL–80–12, Xerox PARC, 1980
  7. Alan Demers, « Generalized Left Corner Parsing », In : Proceedings of the 4th ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages, ACM, p. 170-182, 1977
  8. Hiroshi Maruyama, « Structural disambiguation with constraint propagation », In : Proceedings of the 28th Meeting of the Association for Computational Linguistics, Association for Computational Linguistics, p. 31-38, 1990
  9. a et b T. L. Booth et R. A. Thompson, « Applying Probability Measures to Abstract Languages », In : IEEE Transactions on Computers 22.5, p. 442-450, 1973
  10. Eugene Charniak, « Statistical parsing with a context-free grammar and word statistics », In : Proceedings of 14th National Conference on Artificial Intelligence, Association for Computational Linguistics, p. 598-603, 1997
  11. Dan Klein et Christopher D. Manning, « Accurate unlexicalized parsing », In : Proceedings of the 41st Annual Meeting on Association for Computational Linguistics, Association for Computational Linguistics., 2003
  12. Jason M. Eisner, « Three New Probabilistic Models for Dependency Parsing : An Exploration », In : Proceedings of the 16th International Conference on Computational Linguistics, Association for Computational Linguistics, p. 340-345, 1996
  13. a b c d e f g h et i Joakim Nivre, « Statistical Parsing », In : Handbook of Natural Language Processing, Sous la dir. de Nitin Indurkhya et Fred J. Damerau, 2nd, Chapman & Hall/CRC, Chap. 11, p. 237-266, 2010
  14. Kenneth Church et Ramesh Patil, « Coping with syntactic ambiguity or how to put the block in the box on the table », Comput. Linguist. 8, 3-4, 139-149, 1982
  15. H. Ney, « Dynamic programming parsing for context-free grammars in continuous speech recognition », IEEE Transactions on Signal Processing, 39(2), 336–340, 1991.
  16. (en) Michael Collins, « Head-Driven Statistical Models for Natural Language Parsing », Computational Linguistics, vol. 29, no 4,‎ , p. 589–637 (ISSN 0891-2017, DOI 10.1162/089120103322753356, lire en ligne)
  17. (en) Dan Klein et Christopher D. Manning, « Accurate unlexicalized parsing », Proceedings of the 41st Annual Meeting on Association for Computational Linguistics, Association for Computational Linguistics,‎ , p. 423–430 (DOI 10.3115/1075096.1075150, lire en ligne)
  18. (en) Slav Petrov, Leon Barrett, Romain Thibaux et Dan Klein, « Learning Accurate, Compact, and Interpretable Tree Annotation », Proceedings of the 21st International Conference on Computational Linguistics and 44th Annual Meeting of the Association for Computational Linguistics,‎ (lire en ligne)
  19. R. Bod, « Enriching linguistics with statistics: Performance models of natural language », PhD thesis, University of Amsterdam, Amsterdam, the Netherlands, 1995.
  20. R. Bod, R. Scha, et K. Sima’an (Eds.), « Data-Oriented Parsing », CSLI Publications, Stanford, CA., 2003. (Lire en ligne)
  21. a b et c (en) Michael Collins et Terry Koo, « Discriminative Reranking for Natural Language Parsing », Computational Linguistics, vol. 31, no 1,‎ , p. 25–70 (ISSN 0891-2017 et 1530-9312, DOI 10.1162/0891201053630273, lire en ligne)
  22. (en) Geoffrey N. Leech, Statistically-driven Computer Grammars of English: The IBM/Lancaster Approach, Rodopi, (ISBN 9051834780)
  23. a b c d et e (en) Ivan Titov et James Henderson, « A latent variable model for generative dependency parsing », Proceedings of the 10th International Conference on Parsing Technologies, Association for Computational Linguistics,‎ , p. 144–155 (ISBN 9781932432909, lire en ligne)
  24. a et b (en) Michael Collins, « Discriminative Reranking for Natural Language Parsing », Proceedings of the Seventeenth International Conference on Machine Learning, Morgan Kaufmann Publishers Inc.,‎ , p. 175–182 (ISBN 1558607072, lire en ligne)
  25. (en) Michael Collins et Nigel Duffy, « New ranking algorithms for parsing and tagging: kernels over discrete structures, and the voted perceptron », Proceedings of the 40th Annual Meeting on Association for Computational Linguistics, Association for Computational Linguistics,‎ , p. 263–270 (DOI 10.3115/1073083.1073128, lire en ligne)
  26. Haim Gaifman, « Dependency systems and phrase structure systems », In : Information and Control 8.3, p. 304-337, 1965
  27. a b et c (en) Michael A. Covington, « A Fundamental Algorithm for Dependency Parsing », Proceedings of the 39th Annual ACM Southeast Conference,‎ , p. 95-102
  28. (en) Sabine Buchholz et Erwin Marsi, « CoNLL-X Shared Task on Multilingual Dependency Parsing », International Journal of Web Engineering and Technology - IJWET,‎ (DOI 10.3115/1596276.1596305, lire en ligne)
  29. (en) J. Nivre, J. Hall, S. Kübler, R. McDonald, J. Nilsson, S. Riedel, D. Yuret, « The CoNLL 2007 Shared Task on Dependency Parsing », Proceedings of the CoNLL Shared Task Session of EMNLP-CoNLL 2007,‎ , p. 915-932
  30. (en) Tianze Shi, Felix G. Wu, Xilun Chen et Yao Cheng, « Combining Global Models for Parsing Universal Dependencies », Proceedings of the CoNLL 2017 Shared Task: Multilingual Parsing from Raw Text to Universal Dependencies, Association for Computational Linguistics,‎ , p. 31–39 (DOI 10.18653/v1/K17-3003, lire en ligne)
  31. (en) Anders Björkelund, Agnieszka Falenska, Xiang Yu et Jonas Kuhn, « IMS at the CoNLL 2017 UD Shared Task: CRFs and Perceptrons Meet Neural Networks », Proceedings of the CoNLL 2017 Shared Task: Multilingual Parsing from Raw Text to Universal Dependencies, Association for Computational Linguistics,‎ , p. 40–51 (DOI 10.18653/v1/K17-3004, lire en ligne)
  32. (en) Joakim Nivre et Ryan McDonald, « Integrating Graph-Based and Transition-Based Dependency Parsers », Proceedings of ACL-08: HLT,‎ (lire en ligne)
  33. (en) Ryan Mcdonald, « Characterizing the errors of data-driven dependency parsing models », PROCEEDINGS OF THE CONFERENCE ON EMPIRICAL METHODS IN NATURAL LANGUAGE PROCESSING AND NATURAL LANGUAGE LEARNING,‎ (lire en ligne)
  34. a b et c Joakim Nivre, « An Efficient Algorithm for Projective Dependency Parsing », In: Proceedings of the 8th International Workshop on Parsing Technologies (IWPT), 2003
  35. a b c et d (en) Ryan McDonald, Fernando Pereira, Kiril Ribarov et Jan Hajič, « Non-projective dependency parsing using spanning tree algorithms », Proceedings of the Conference on Human Language Technology and Empirical Methods in Natural Language Processing, Association for Computational Linguistics,‎ , p. 523–530 (DOI 10.3115/1220575.1220641, lire en ligne)
  36. (en) Jinho D. Choi, Joel Tetreault et Amanda Stent, « It Depends: Dependency Parser Comparison Using A Web-based Evaluation Tool », Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Processing (Volume 1: Long Papers), Association for Computational Linguistics, vol. 1,‎ , p. 387–396 (DOI 10.3115/v1/P15-1038, lire en ligne)
  37. Tony Jebara, « Discriminative, Generative and Imitative Learning », PhD thesis, Massachusetts Institute of Technology, 212 p., 2002.
  38. (en) Joakim Nivre, « Algorithms for Deterministic Incremental Dependency Parsing », Computational Linguistics, vol. 34, no 4,‎ , p. 513–553 (ISSN 0891-2017 et 1530-9312, DOI 10.1162/coli.07-056-r1-07-027, lire en ligne)
  39. (en) Taku Kudo et Yuji Matsumoto, « Japanese dependency structure analysis based on support vector machines », Proceedings of the 2000 Joint SIGDAT Conference on Empirical Methods in Natural Language Processing and Very Large Corpora, Association for Computational Linguistics,‎ , p. 18–25 (DOI 10.3115/1117794.1117797, lire en ligne)
  40. (en) Joakim Nivre, Johan Hall, Jens Nilsson et Gülşen Eryiǧit, « Labeled pseudo-projective dependency parsing with support vector machines », Proceedings of the Tenth Conference on Computational Natural Language Learning, Association for Computational Linguistics,‎ , p. 221–225
  41. J. Nivre, J. Hall, J. Nilsson, A. Chanev, G. Eryigit, S. Kübler, S. Marinov, et E. Marsi, « MaltParser: A language-independent system for data-driven dependency parsing », Natural Language Engineering, 13, 95-135, 2007.
  42. Giuseppe Attardi, « Experiments with a multilanguage non-projective dependency parser », In Proceedings of the Tenth Conference on Computational Natural Language Learning (CoNLL-X '06). Association for Computational Linguistics, Stroudsburg, PA, USA, 166-170, 2006.
  43. a et b (en) Joakim Nivre, « Incremental Non-Projective Dependency Parsing. », Proceedings of Conference of the North American Chapter of the Association of Computational Linguistics,‎ , p. 396–403
  44. a et b Joakim Nivre, « Non-projective dependency parsing in expected linear time ». In Proceedings of the Joint Conference of the 47th Annual Meeting of the ACL and the 4th International Joint Conference on Natural Language Processing of the AFNLP: Volume 1 - Volume 1 (ACL '09), Association for Computational Linguistics, Stroudsburg, PA, USA, 351-359, 2009.
  45. a et b Carlos Gómez-Rodríguez et Joakim Nivre, « A transition-based parser for 2-planar dependency structures ». In Proceedings of the 48th Annual Meeting of the Association for Computational Linguistics (ACL '10), Association for Computational Linguistics, Stroudsburg, PA, USA, 1492-1501, 2010.
  46. (en) Joakim Nivre et Jens Nilsson, « Pseudo-projective dependency parsing », Proceedings of the 43rd Annual Meeting on Association for Computational Linguistics, Association for Computational Linguistics,‎ , p. 99–106 (DOI 10.3115/1219840.1219853, lire en ligne)
  47. Richard Johansson et Pierre Nugues, « Investigating multilingual dependency parsing », In Proceedings of the Tenth Conference on Computational Natural Language Learning (CoNLL-X '06), Association for Computational Linguistics, Stroudsburg, PA, USA, 206-210, 2006.
  48. (en) Yue Zhang et Stephen Clark, « A tale of two parsers: investigating and combining graph-based and transition-based dependency parsing using beamsearch », IN PROCEEDINGS OF EMNLP-08,‎
  49. Yoav Goldberg et Michael Elhadad, « An efficient algorithm for easy-first non-directional dependency parsing », In Human Language Technologies: The 2010 Annual Conference of the North American Chapter of the Association for Computational Linguistics (HLT '10), Association for Computational Linguistics, Stroudsburg, PA, USA, 742-750, 2010.
  50. Yoav Goldberg, Joakim Nivre, « A Dynamic Oracle for Arc-Eager Dependency Parsing », 2012
  51. Milan Straka, Jan Hajič, Jana Strakova et Jan jr. Hajič, « Parsing Universal Dependency Treebanks using Neural Networks and Search-Based Oracle », 2015.
  52. (en) Yue Zhang et Joakim Nivre, « Transition-based Dependency Parsing with Rich Non-local Features », Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics,‎
  53. a b c et d Danqi Chen et Christopher Manning, « A Fast and Accurate Dependency Parser using Neural Networks », Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP), Association for Computational Linguistics,‎ (DOI 10.3115/v1/d14-1082, lire en ligne)
  54. (en) Bernd Bohnet, « Very high accuracy and fast dependency parsing is not a contradiction », Proceedings of the 23rd International Conference on Computational Linguistics, Association for Computational Linguistics,‎ , p. 89–97
  55. (en) James Henderson, « Inducing history representations for broad coverage statistical parsing », Proceedings of the 2003 Conference of the North American Chapter of the Association for Computational Linguistics on Human Language Technology, Association for Computational Linguistics,‎ , p. 24–31 (DOI 10.3115/1073445.1073459, lire en ligne)
  56. (en) James Henderson, « Discriminative training of a neural network statistical parser », Proceedings of the 42nd Annual Meeting on Association for Computational Linguistics, Association for Computational Linguistics,‎ , p. 95 (DOI 10.3115/1218955.1218968, lire en ligne)
  57. (en) T Mikolov, W.-T Yih et G Zweig, « Linguistic regularities in continuous space word representations », Proceedings of NAACL-HLT,‎ , p. 746–751 (lire en ligne)
  58. (en) Tomas Mikolov, Kai Chen, Greg Corrado et Jeffrey Dean, « Efficient Estimation of Word Representations in Vector Space », arXiv:1301.3781 [cs],‎ (lire en ligne)
  59. (en) Chris Dyer, Miguel Ballesteros, Wang Ling et Austin Matthews, « Transition-Based Dependency Parsing with Stack Long Short-Term Memory », arXiv:1505.08075 [cs],‎ (lire en ligne)
  60. a b et c (en) Eliyahu Kiperwasser et Yoav Goldberg, « Simple and Accurate Dependency Parsing Using Bidirectional LSTM Feature Representations », arXiv:1603.04351 [cs],‎ (lire en ligne)
  61. a et b Majid Yazdani et James Henderson, Incremental Recurrent Neural Network Dependency Parser with Search-based Discriminative Training, In: Proceedings of the 19th Conference on Computational Language Learning, Beijing, China, 2015, p. 142-152.
  62. a b et c (en) Daniel Andor, Chris Alberti, David Weiss et Aliaksei Severyn, « Globally Normalized Transition-Based Neural Networks », Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), Association for Computational Linguistics,‎ (DOI 10.18653/v1/p16-1231, lire en ligne)
  63. a b et c (en) « An Upgrade to SyntaxNet, New Models and a Parsing Competition »,
  64. a et b (en) Miguel Ballesteros, Chris Dyer et Noah A. Smith, « Improved Transition-based Parsing by Modeling Characters instead of Words with LSTMs », Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing, Association for Computational Linguistics,‎ (DOI 10.18653/v1/d15-1041, lire en ligne)
  65. a b et c (en) Ryan Mcdonald et Fernando Pereira, « Online Learning of Approximate Dependency Parsing Algorithms », IN PROC. OF EACL,‎ , p. 81––88
  66. a et b (en) Ryan McDonald et Giorgio Satta, « On the complexity of non-projective data-driven dependency parsing », Proceedings of the 10th International Conference on Parsing Technologies, Association for Computational Linguistics,‎ , p. 121–132 (ISBN 9781932432909, lire en ligne)
  67. a b et c (en) Timothy Dozat et Christopher D. Manning, « Deep Biaffine Attention for Neural Dependency Parsing », arXiv:1611.01734 [cs],‎ (lire en ligne)
  68. (en) Jason M. Eisner, « Three new probabilistic models for dependency parsing: an exploration », Proceedings of the 16th conference on Computational linguistics, Association for Computational Linguistics,‎ , p. 340–345 (DOI 10.3115/992628.992688, lire en ligne)
  69. Jack Edmonds, « Optimum Branchings », In : J. Res. Nat. Bur. Standards 71B.4, p. 233-240, 1967.
  70. a et b (en) Xavier Carreras, « Experiments with a Higher-Order Projective Dependency Parser », Proceedings of the 2007 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning (EMNLP-CoNLL),‎ (lire en ligne)
  71. (en) Terry Koo et Michael Collins, « Efficient Third-Order Dependency Parsers. », Proceedings of the 48th Annual Meeting of the Association for Computational Linguistics,‎ , p. 1–11 (lire en ligne)
  72. (en) Xuezhe Ma et Hai Zhao, « Fourth-Order Dependency Parsing », Proceedings of COLING 2012,‎ , p. 785–796 (lire en ligne)
  73. (en) Markus Dreyer, David A. Smith et Noah A. Smith, « Vine parsing and minimum risk reranking for speed and precision », Proceedings of the Tenth Conference on Computational Natural Language Learning, Association for Computational Linguistics,‎ , p. 201–205 (lire en ligne)
  74. (en) Alexander M. Rush et Slav Petrov, « Vine pruning for efficient multi-pass dependency parsing », Proceedings of the 2012 Conference of the North American Chapter of the Association for Computational Linguistics, Association for Computational Linguistics,‎ , p. 498–507 (ISBN 9781937284206, lire en ligne)
  75. (en) Mark Hopkins et Greg Langmead, « Cube pruning as heuristic search », Proceedings of the 2009 Conference on Empirical Methods in Natural Language Processing, Association for Computational Linguistics,‎ , p. 62–71 (ISBN 9781932432596, lire en ligne)
  76. (en) Hao Zhang et Ryan McDonald, « Generalized Higher-Order Dependency Parsing with Cube Pruning », Proceedings of the 2012 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning,‎ (lire en ligne)
  77. (en) Keith Hall, « K-best Spanning Tree Parsing », Proceedings of the 45th Annual Meeting of the Association of Computational Linguistics,‎ (lire en ligne)
  78. (en) Terry Koo, Alexander M. Rush, Michael Collins et Tommi Jaakkola, « Dual decomposition for parsing with non-projective head automata », Proceedings of the 2010 Conference on Empirical Methods in Natural Language Processing, Association for Computational Linguistics,‎ , p. 1288–1298 (lire en ligne)
  79. (en) André F. T. Martins, Noah A. Smith, Pedro M. Q. Aguiar et Mário A. T. Figueiredo, « Dual decomposition with many overlapping components », Proceedings of the Conference on Empirical Methods in Natural Language Processing, Association for Computational Linguistics,‎ , p. 238–249 (ISBN 9781937284114, lire en ligne)
  80. (en) André Martins, Miguel Almeida et Noah A Smith, « Turning on the Turbo: Fast Third-Order Non-Projective Turbo Parsers », Proceedings of the 51st Annual Meeting of the Association for Computational Linguistics, vol. 2,‎ , p. 617–622 (lire en ligne)
  81. (en) Sebastian Riedel, David Smith et Andrew Mccallum, « Parse, price and cut: delayed column and row generation for graph based parsers », Proceedings of the 2012 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning,‎ , p. 732–743 (lire en ligne)
  82. (en) Carlos Gómez-Rodríguez, John Carroll et David Weir, « Dependency parsing schemata and mildly non-projective dependency parsing », Computational Linguistics, vol. 37, no 3,‎ , p. 541–586 (ISSN 0891-2017, DOI 10.1162/COLI_a_00060, lire en ligne)
  83. (en) Emily Pitler, Sampath Kannan et Mitchell Marcus, « Dynamic Programming for Higher Order Parsing of Gap-Minding Trees », Proceedings of the 2012 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning,‎ (lire en ligne)
  84. (en) Emily Pitler, Sampath Kannan et Mitchell Marcus, « Finding Optimal 1-Endpoint-Crossing Trees », Transactions of the Association of Computational Linguistics, vol. 1,‎ (lire en ligne)
  85. (en) Emily Pitler, « A Crossing-Sensitive Third-Order Factorization for Dependency Parsing », Transactions of the Association of Computational Linguistics, vol. 2, no 1,‎ (lire en ligne)
  86. (en) André F. T. Martins, Noah A. Smith et Eric P. Xing, « Concise integer linear programming formulations for dependency parsing », Proceedings of the Joint Conference of the 47th Annual Meeting of the ACL and the 4th International Joint Conference on Natural Language Processing of the AFNLP, Association for Computational Linguistics,‎ , p. 342–350 (ISBN 9781932432459, lire en ligne)
  87. (en) Koby Crammer et Yoram Singer, « Ultraconservative online algorithms for multiclass problems », The Journal of Machine Learning Research, vol. 3,‎ , p. 951–991 (ISSN 1532-4435, DOI 10.1162/jmlr.2003.3.4-5.951, lire en ligne)
  88. a et b (en) Wenzhe Pei, Tao Ge et Baobao Chang, « An Effective Neural Network Model for Graph-based Dependency Parsing », Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Processing (Volume 1: Long Papers), Association for Computational Linguistics, vol. 1,‎ , p. 313–322 (DOI 10.3115/v1/P15-1031, lire en ligne)
  89. C. J. van Rijsbergen, Information Retrieval, Butterworths, 1975.
  90. (en) S. Abney, S. Flickenger, C. Gdaniec et C. Grishman, « Procedure for quantitatively comparing the syntactic coverage of English grammars », Proceedings of the workshop on Speech and Natural Language, Association for Computational Linguistics,‎ , p. 306–311 (DOI 10.3115/112405.112467, lire en ligne)
  91. R. Grishman, C. Macleod, et J. Sterling, « Evaluating parsing strategies using standardized parse files », In Proceedings of the Third Conference on Applied Natural Language Processing (ANLP), Trento, Italy, p. 156–161, 1992.
  92. (en) Sabine Buchholz et Erwin Marsi, « CoNLL-X shared task on multilingual dependency parsing », Proceedings of the Tenth Conference on Computational Natural Language Learning (CoNLL-X), Association for Computational Linguistics,‎ , p. 149–164 (DOI 10.3115/1596276.1596305, lire en ligne)

Voir aussi[modifier | modifier le code]

Bibliographie[modifier | modifier le code]

  • Daniel Jurafsky et James H. Martin, Speech and Language Processing (2nd Edition), Prentice Hall, 16 mai 2008, 1024 p.
  • Nitin Indurkhya et Fred J. Damerau (ed.), Handbook of Natural Language Processing (2nd Edition), Chapman & Hall, 22 février 2010, 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[modifier | modifier le code]

Liens externes[modifier | modifier le code]

  • 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