Analyse syntaxique de la langue naturelle

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.

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

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 ${\displaystyle {\mathcal {O}}(n^{3}\cdot |R|)}$, où ${\displaystyle |R|}$ 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 ${\displaystyle {\text{NP}}\longrightarrow {\text{Pron}}}$) 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 ${\displaystyle [{\text{NP}}\longrightarrow {\text{DT}}\quad {\text{NN}}]}$ pour une PCFG pourrait devenir ${\displaystyle [{\text{NP(chien)}}\longrightarrow {\text{DT(le)}}\quad \mathbf {NN} {\text{(chien)}}]}$ si « le chien » fait partie de la phrase à analyser. Comme ${\displaystyle {\text{NN}}}$ est l'élément prépondérant pour cette règle, le parent ${\displaystyle {\text{NP}}}$ 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 ${\displaystyle [{\text{NP}}^{\text{PP}}\longrightarrow {\text{DT}}\quad {\text{NN}}]}$ si ${\displaystyle {\text{NP}}}$ 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).

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

On peut représenter un analyseur syntaxique par une fonction ${\displaystyle f:{\mathcal {X}}\to {\mathcal {Y}}}$, où ${\displaystyle {\mathcal {X}}}$ est l’ensemble des entrées possibles, sachant que ${\displaystyle {\boldsymbol {x}}\in {\mathcal {X}}}$ représente une séquence d’entrée ${\displaystyle {\boldsymbol {x}}=(t_{0},t_{1},\dots ,t_{n})}$, et ${\displaystyle {\mathcal {Y}}}$ est l’ensemble des représentations syntaxiques admissibles. Relevons que la nature de la représentation d’une analyse ${\displaystyle {\boldsymbol {y}}\in {\mathcal {Y}}}$ 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 ${\displaystyle \mathrm {GEN} }$, qui fait correspondre une entrée ${\displaystyle {\boldsymbol {x}}}$ à un ensemble d’analyses candidates ${\displaystyle \{{\boldsymbol {y}}_{1},{\boldsymbol {y}}_{2},\dots ,{\boldsymbol {y}}_{|{\mathcal {Y}}|}\}}$, donc ${\displaystyle \mathrm {GEN} ({\boldsymbol {x}})\subseteq {\mathcal {Y}},{\boldsymbol {x}}\in {\mathcal {X}}}$;
2. un composant évaluatif ${\displaystyle \mathrm {EVAL} }$, classant les analyses candidates selon un score numérique attribué, donc ${\displaystyle \mathrm {EVAL} ({\boldsymbol {y}})\in \mathbb {R} ,{\boldsymbol {y}}\in \mathrm {GEN} ({\boldsymbol {x}})}$.

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 ${\displaystyle f({\boldsymbol {x}}_{i})}$ un bon estimateur du ${\displaystyle {\boldsymbol {y}}_{i}}$ 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 ${\displaystyle f}$, 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 ${\displaystyle \mathrm {GEN} ({\boldsymbol {x}})}$ est vraisemblablement très grand, et que chaque ${\displaystyle {\boldsymbol {y}}_{i}\in \mathrm {GEN} ({\boldsymbol {x}})}$ est un objet possédant une structure interne riche ; ce constat contraste avec un simple problème de classification, pour lequel ${\displaystyle \mathrm {GEN} ({\boldsymbol {x}})}$ 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) 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 ${\displaystyle P({\boldsymbol {x}},{\boldsymbol {y}})}$, quel que soit ${\displaystyle {\boldsymbol {x}}\in {\mathcal {X}}}$ et ${\displaystyle {\boldsymbol {y}}\in {\mathcal {Y}}}$, en modélisant ${\displaystyle P({\boldsymbol {x}}|{\boldsymbol {y}})}$ et ${\displaystyle P({\boldsymbol {y}})}$, 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 ${\displaystyle P({\boldsymbol {y}}|{\boldsymbol {x}})}$ directement depuis les données. Encore, les deux approches peuvent être combinées de façon séquentielle (reranking) [21].

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 :

$${\displaystyle {\boldsymbol {y}}={\big \langle }d_{1},d_{2},\dots ,d_{m}{\big \rangle }}$$

$${\displaystyle P{\big (}{\boldsymbol {y}}{\big )}=\prod _{i=1}^{m}P{\big (}d_{i}|\Phi (d_{1},\dots ,d_{i-1}){\big )}}$$

où la fonction ${\displaystyle \Phi }$ définit quels événements de l'historique sont pris en compte. Bien que ce soit souvent le cas, le composant génératif ${\displaystyle \mathrm {GEN} ({\boldsymbol {x}})}$ 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 [23]). L'évaluation ${\displaystyle \mathrm {EVAL} ({\boldsymbol {y}})}$ se fait selon la probabilité jointe, factorisée en probabilités conditionnelles. À noter que ${\displaystyle P({\boldsymbol {x}},{\boldsymbol {y}})}$ se ramène à ${\displaystyle P({\boldsymbol {y}})}$ car, pour une structure donnée, la probabilité ${\displaystyle P({\boldsymbol {x}}|{\boldsymbol {y}})}$ est égale à ${\displaystyle 1}$ si ${\displaystyle {\boldsymbol {x}}}$ est la phrase unique correspondant à cette structure ; par conséquent, ${\displaystyle P({\boldsymbol {x}},{\boldsymbol {y}})=P({\boldsymbol {y}})}$ si ${\displaystyle {\boldsymbol {y}}}$ engendre ${\displaystyle {\boldsymbol {x}}}$, ou ${\displaystyle P({\boldsymbol {x}},{\boldsymbol {y}})=0}$ 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.

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 :

$${\displaystyle {\boldsymbol {y}}={\big \langle }d_{1},d_{2},\dots ,d_{m}{\big \rangle }}$$

$${\displaystyle P{\big (}{\boldsymbol {y}}|{\boldsymbol {x}}{\big )}=\prod _{i=1}^{m}P{\big (}d_{i}|\Phi (d_{1},\dots ,d_{i-1},{\boldsymbol {x}}){\big )}}$$

Ici, la fonction ${\displaystyle \Phi }$ représente des propriétés/traits arbitraires dépendant de l’historique ${\displaystyle \langle d_{1},\dots ,d_{i-1}\rangle }$ des décisions prises, et de l’entrée ${\displaystyle {\boldsymbol {x}}}$ ; 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 ${\displaystyle \mathrm {GEN} ({\boldsymbol {x}})}$ est constitué d’un processus incrémental (p. ex. automate), alors que le composant évaluatif ${\displaystyle \mathrm {EVAL} ({\boldsymbol {y}})}$ 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]).

Cette classe de modèles définit typiquement la fonction d’évaluation comme étant le produit d’un vecteur de traits (caractéristiques) ${\displaystyle \mathbf {f} ({\boldsymbol {x}},{\boldsymbol {y}})=\langle f_{1}({\boldsymbol {x}},{\boldsymbol {y}}),\dots ,f_{m}({\boldsymbol {x}},{\boldsymbol {y}})\rangle \in \mathbb {R} ^{m}}$ et d’un vecteur de poids ${\displaystyle {\boldsymbol {w}}=\langle w_{1},\dots ,w_{m}\rangle \in \mathbb {R} ^{m}}$:

$${\displaystyle S({\boldsymbol {x}},{\boldsymbol {y}})\;=\;\mathbf {f} ({\boldsymbol {x}},{\boldsymbol {y}})\cdot {\boldsymbol {w}}\;=\;\sum _{k=1}^{m}f_{k}({\boldsymbol {x}},{\boldsymbol {y}})\cdot w_{k}}$$

où chaque ${\displaystyle f_{k}({\boldsymbol {x}},{\boldsymbol {y}}):{\mathcal {X}}\times {\mathcal {Y}}\to \mathbb {R} }$ représente une caractéristique de ${\displaystyle {\boldsymbol {x}}}$ et ${\displaystyle {\boldsymbol {y}}}$, et chaque ${\displaystyle w_{k}\in \mathbb {R} }$ quantifie l’importance de la caractéristique ${\displaystyle f_{k}}$ 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 ${\displaystyle \mathrm {GEN} ({\boldsymbol {x}})}$ est assez variable d’un système à l'autre, tandis que le composant d’évaluation ${\displaystyle \mathrm {EVAL} ({\boldsymbol {y}})}$ 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 ${\displaystyle \mathrm {GEN} ({\boldsymbol {x}})}$, 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 »).

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

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 ${\displaystyle {\boldsymbol {y}}}$ 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 ${\displaystyle P({\boldsymbol {y}}|{\boldsymbol {x}})}$ serait optimisée [37]. En supposant une fonction d’évaluation ${\displaystyle S(\Phi (\mathbf {c} ),d)}$ assignant un score aux transitions possibles ${\displaystyle d}$ en fonction d’une configuration, représentée par un vecteur ${\displaystyle \Phi (\mathbf {c} )}$, 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 à ${\displaystyle m}$ 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).

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 ${\displaystyle \mathrm {GEN} ({\boldsymbol {x}})}$ 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 1^er 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 1^er 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 1^er ordre repose soit sur l'algorithme d'Eisner [68], soit sur l'algorithme glouton de Chu-Liu-Edmonds (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 ${\displaystyle {\mathcal {O}}(n^{5})}$). 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 maintien 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].

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	${\displaystyle {\mathcal {O}}(n)}$[34]	${\displaystyle {\mathcal {O}}(n^{2})}$[27],[43] ${\displaystyle {\mathcal {O}}(n)}$ en pratique [44],[45]
Analyse graph-based — 1er ordre	${\displaystyle {\mathcal {O}}(n^{3})}$ [35]	${\displaystyle {\mathcal {O}}(n^{2})}$[35]
Analyse graph-based — nème ordre (n>1)	FP [65],[70],...	FNP-complet [66]

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.

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.

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

• 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

• 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

• Portail de la linguistique
• Portail de l’informatique