Blog

Dependency Parser ou comment placer votre mot dans la syntaxe de la phrase

Date: 2019-05-05

Nous avons décidé de consacrer une série de 2 articles pour approfondir le cas du Dependency Parsing. Un premier article passera en revue la théorie pour démystifier cette partie insuffisamment connue du NLP. Dans un second temps, nous vous proposerons des outils pour vous aider à comprendre comment implémenter facilement un analyseur de dépendances syntaxiques.

Lorsque l'on pense aux voisins d'un mot, on peut penser à leur emplacement dans la phrase, à leur relation avec d'autres mots (sujet, déterminant, etc.), ce que l'on appelle la syntaxe, ou à leur similarité de sens, ce que l'on appelle la sémantique. Ce qui nous intéresse ici, c'est le voisinage syntaxique.

Vocabulaire

Tout d'abord, clarifions ensemble certains éléments de vocabulaire :

  • La sémantique est le domaine linguistique et philosophique qui étudie le sens et l'interprétation. Elle s'appuie beaucoup sur les liens entre les mots pour comprendre la phrase, et elle analyse les changements de sens. En programmation, la sémantique est le résultat attendu d'un programme.
  • Syntaxe est le domaine linguistique de la grammaire. C'est l'étude des règles qui régissent la structure des mots dans les phrases. En programmation aussi, les erreurs de syntaxe conduisent souvent à des bugs, car les règles sont souvent beaucoup plus strictes que dans le langage oral.

Qu'est-ce qu'un analyseur de dépendances ?

Un arbre de dépendance est une structure qui peut être définie comme un graphe dirigé, avec |V| nœuds (sommets), correspondant aux mots, et |A| Arcs, correspondant aux dépendances syntaxiques entre eux. Nous pouvons également vouloir attribuer des étiquettes aux dépendances, appelées relations. Ces relations donnent des détails sur le type de dépendance (par exemple, Sujet, Complément d'objet direct, Déterminant...). Vous pouvez trouver toutes les relations de Universal Dependencies en suivant ce lien : https://universaldependencies.org/u/dep/index.html

https://cdn-images-1.medium.com/max/2000/1*M6hUDHa04FrcBn1LATqXMQ.png

Exemple d'arbre de dépendance : "Qu'est-ce qu'un parseur ? "

Dans un arc h -> d, h est la tête et d est le dépendant. La tête est le nœud le plus important d'une phrase, tandis que la racine est le nœud le plus important de toute la phrase : elle est directement ou indirectement la tête de tous les autres nœuds.

Un analyseur de dépendances transforme simplement une phrase en un arbre de dépendances.

Métriques : comment reconnaître un bon analyseur ?

Un analyseur de dépendances précis reconnaît bien les dépendances et les relations entre les mots. Deux métriques (scores) sont utiles pour cela :

  • Unlabeled Attachment Score (UAS), qui correspond au nombre de dépendances correctement prédites par rapport au nombre de possibilités ;
  • Labeled Attachment Score (LAS), qui correspond au nombre de dépendances et de relations correctement prédites par rapport au nombre de possibilités.

Le LAS est toujours inférieur ou égal au UAS, car une dépendance incorrecte entraîne un UAS et un LAS sous-optimaux, tandis qu'une relation (ou une étiquette) incorrecte n'entraîne qu'une diminution du LAS.

Algorithme : Comment ça marche ?

Comme vous avez pu l’imaginer, nous pourrions créer un analyseur syntaxique de dépendances à partir de règles développées par des linguistes. Ces analyseurs sont appelés Rationalistes. Ils ne sont pas du tout efficaces, car les langues sont très complexes, et elles changent avec le temps. Un infime changement dans la langue entraînerait d'énormes changements dans l'analyseur syntaxique. L'apprentissage automatique permet de développer des analyseurs Empiriques, qui sont basés sur des données. Alimentés par de nombreuses phrases, des probabilités de dépendances ou de relations peuvent être établies. Les connaissances linguistiques peuvent être utilisées, mais n'ont pas le dernier mot, ce qui est un bon point si, comme moi, vous avez oublié vos leçons d'école primaire...

Plusieurs étapes sont nécessaires pour créer un analyseur de dépendances. Nos entrées sont les mots de la phrase avec leurs propriétés (index, étiquette grammatical, lemme) ; ensuite, nous devons calculer les caractéristiques de tous les arcs possibles dans la phrase. Grâce à ces caractéristiques, nous calculons un score pour chaque possibilité, et nous décodons finalement les scores avec un décodeur.

Caractéristiques et score

Chaque mot de la phrase possède certains attributs, comme les balises de la partie du discours ou les lemmes. Vous les connaissez peut-être si vous avez déjà lu des articles sur la PNL. Sinon, vous pouvez vous renseigner ici :

Avec ces caractéristiques, nous formons un modèle de régression d'apprentissage automatique qui renvoie le score à exploiter par le décodeur.

La sélection des caractéristiques est cruciale, et certains modèles nous permettent de contourner cette partie via une partie d'apprentissage profond. C'est le cas de l'algorithme que nous allons présenter dans la section suivante.

Décodeurs

Il existe un grand nombre de décodeurs différents déjà développés. Nous pouvons les diviser en deux catégories majeures : les décodeurs basés sur les transitions et les décodeurs basés sur les graphiques. Les décodeurs basés sur les transitions sont plus rapides et nécessitent moins de mémoire pour décoder les scores, mais ils sont généralement moins précis que les décodeurs basés sur les graphiques. Dans cet article, je n'aborderai que les principes des modèles basés sur le graphique.

D'autres algorithmes peuvent appliquer des transitions différentes, mais celui-ci nous permet de comprendre le principe principal.

Décodeurs basés sur les graphes

Il est nécessaire d'aborder la théorie des graphes pour comprendre ces algorithmes.

Un graphe G=(V, A) est un ensemble de sommets V (appelés aussi nœuds), qui représentent les tokens, et d'arcs (i, j)" A où i, j " V. Les arcs représentent les dépendances entre deux mots.

Dans un analyseur de dépendance basé sur les graphes, les graphes sont dirigés, ce qui signifie que les liens ont des directions différentes, et qu'il peut y avoir plusieurs arcs entre les nœuds, on appelle cela un multi-digraphe.

https://cdn-images-1.medium.com/max/2000/1*95Ux0Sk4HWzpKknHYhvjCw.png

Graphe multidirigé pondéré (G)

Vous pouvez noter que certaines flèches sont plus épaisses que d'autres. Cela représente le poids des arcs. Plus un arc a de poids, plus le lien entre deux nœuds est fort. Nous pouvons interpréter cela comme la force de la dépendance syntaxique pour notre analyseur syntaxique. Par exemple, C et A semblent être très dépendants de B, mais B ne semble pas très dépendant de C et A.

Le graphique G est trop connecté. Afin d'obtenir un arbre de dépendance, nous voulons :

  • Relier chaque mot uniquement avec ses dépendants - pas avec tous les mots. Le nombre total d'arcs doit être égal au nombre de noeuds moins 1 (|A| = |V|-1).
  • Pour garder les mêmes noeuds (ou tokens ou mots).
  • Pour le rendre acyclique : nous ne voulons pas qu'une tête soit dépendante d'un de ses dépendants (direct ou indirect).

Heureusement, tout cela a déjà un nom : ce que nous voulons est un Spanning Tree !

https://cdn-images-1.medium.com/max/2000/1*BhbDV4B8dDlJDa4L6Hrlng.png

Exemple d'arbre couvrant à partir du graphe G

https://cdn-images-1.medium.com/max/2000/1*WzKuY-pmER770gIz9IrIdQ.png

Un autre exemple de Spanning Tree

Si j'ai été clair sur ce qu'est un Spanning Tree, vous devez garder à l’esprit qu'il y a plusieurs possibilités pour en obtenir un. Ce que nous voulons, c’est déterminer le meilleur. Comment l’identifier ?

Nous avons 3 nœuds ici, et nous voulons les garder. Cependant, nous avons 6 arcs et nous ne voulons en garder que 2. Le "meilleur" arbre de dépendance est celui qui a les poids les plus élevés : on l'appelle l'arbre à portée maximale (MST).

https://cdn-images-1.medium.com/max/2000/1*14X2qAxhHUZAW63Q3kJlrg.png

Arbre à portée maximale de G

https://cdn-images-1.medium.com/max/2000/1*ytg5pJWjapNewrGnbc77vQ.png

Arbre des portées minimales de G

Cet arbre à portée maximale nous donne notre arbre de dépendance, que nous allons utiliser pour trouver les voisins syntaxiques les plus proches dans la phrase.

Conclusion

La vision présentée dans cette article est très légère par rapport à d’autres algorithmes existants. Cependant, nous espérons que cela vous éclairera pour développer votre prochain Bist-Parser. Vous trouverez le détails de son implémentation via ce lien.

Author : Côme Cothenet

Lecture : 6 minutes

Prêt à extraire l'or dans vos données ?

Vous souhaitez en savoir plus sur le NLP ? Envoyez-nous un message ou inscrivez-vous gratuitement sur la plateforme Lettria pour vous lancer.

Lancez-vous

S'inscrire à notre newsletter

Recevez tous les mois les actualités de Lettria.