Ré-ordonnancement via programmation dynamique pour l’adaptation cross-lingue d’un analyseur en dépendances (Sentence reordering via dynamic programming for cross-lingual dependency parsing ) (2022)

Abstract: Cet article s’intéresse au transfert cross-lingue d’analyseurs en dépendances et étudie des méthodes pour limiter l’effet potentiellement néfaste pour le transfert de divergences entre l’ordre des mots dans les langues source et cible. Nous montrons comment apprendre et implémenter des stratégies de réordonnancement, qui, utilisées en prétraitement, permettent souvent d’améliorer les performances des analyseurs dans un scénario de transfert « zero-shot ».

## introduction dans cet article, nous nous intéressons au transfert entre langues d'analyseurs syntaxiques : à partir d'un modèle appris sur une ou plusieurs langues sources, nous souhaitons pouvoir analyser des textes dans une ou plusieurs langues cibles. pour rendre ce transfert possible, il est nécessaire de disposer de représentations similaires, ou du moins compatibles, dans les langues sources et cibles, qui s'appuient par exemple sur : nous montrons qu'un pré-traitement consistant à permuter les mots dans des phrases en langue cible de manière à reproduire l'ordre des mots en langue source peut permettre d'améliorer les performances du modèle, même lorsque les langues source et cible sont typologiquement proches. qui plus est, nous proposons une approche pour apprendre à réaliser cette permutation sans avoir accès à des données parallèles. en résumé, nos principales contributions sont les suivantes : ## modèles d'ordonnancement pour simplifier les notations, nous supposons que toutes les phrases ont une longueur de n mots. soit @xmath0. dans cette section, le vecteur peut être interprété comme un sac de mots, mais nous gardons la notation w pour des raisons de cohérence avec la suite de l'article. un ordonnancement de w est représenté par une fonction bijective π : {1 . . . n} → {1 . . . n} où π(i) donne la position du mot w i dans l'ordonnancement. l'ensemble de toutes les fonctions d'ordonnancement est noté π. notre objectif est de construire un modèle capable d'ordonner les mots de w tout en respectant l'ordre dominant des mots d'une langue. pour cela, nous utilisons un modèle de score bigramme s : v n × π × θ → r qui assigne un score à chaque ordonnancement possible selon : ## apprentissage par échantillonnage pour approximer le gradient de la fonction de log-partition, nous réécrivons ce gradient afin d'utiliser une approximation par échantillonnage @xcite , section 20.5.1.3) : cette espérance peut être approchée par un estimateur de monte-carlo, c'est-à-dire comme la moyenne empirique de k échantillons : même s'il n'est pas possible d'échantillonner directement dans la distribution p(π|w, θ), nous pouvons utiliser les méthodes de monte-carlo par chaînes de markov, ici l'algorithme de metropolis-hastings @xcite . soit q(π|π) un noyau de transition exprimant la probabilité de transformer une permutation π en une permutation π ′ , une séquence de permutations notons que les deux termes intractables c(w, θ) s'annulent, donc : cette variante est parfois appelée algorithme de metropolis. nous utilisons le noyau de transition 2-opt, initialement proposée comme heuristique locale pour résoudre le problème du voyageur de commerce @xcite . pour l'échantillonnage ## algorithmes de réordonnancement le calcul de l'ordonnancement de poids maximum, voir section 2, peut être réduit au problème du voyageur de commerce @xcite , un problème np-difficile @xcite . de plus, sans aucune contrainte supplémentaire, le problème d'ordonnancement considère w comme un sac de mots, ce qui peut être problématique. par exemple, supposons la phrase 3 , 3 , 3 , 3] axiome 2. [3 , 3 , 4 , 4] (d) avec 1 4. [1 , 1 , 1 , 1] axiome 5. [2 , 2 , 2 , 2] axiome 6. [1 , 4 , 1 , 2] ( suivante : « le philosophe grec lit un livre ». cette exemple est particulièrement intéressant car il est difficile de déterminer quel est l'adjectif et quel est le nom dans le premier groupe nominal, si cette différence est souhaitée @xcite . si nous analysons cette phrase avec un modèle cross-lingue entraîné sur des corpus en anglais, l'ordre des mots dans un groupe nominal est déterminant : les adjectifs précèdent toujours les noms en anglais. nous voulons donc, éventuellement, réordonner la phrase pour obtenir « le grec philosophe lit un livre », mais en aucun cas le réordonnancement « le philosophe lit un grec livre » n'est souhaité. lors de l'analyse, nous voulons donc réduire l'espace de recherche des ordonnancements à la fois pour des raisons computationnelles et pour des raisons de cohérence. de nombreux algorithmes de réordonnancement ont été proposés dans la littérature, par exemple dans le cadre du problème du voyageur du commerce @xcite et de la traduction automatique (ta) @xcite . dans un contexte de ta statistique, la sélection d'un ensemble de réordonnancements possibles contraint l'espace de recherche du décodeur et a un effet direct sur les performances du système, voir par exemple @xcite . notre contribution, dans cette section, est une présentation de trois algorithmes de réordonnancement sous une forme unifiée en utilisant des règles de déduction @xcite , une approche standard de présentation des algorithmes de programmation dynamique en traitement automatique des langues qui permet de facilement vérifier la spécification de l'algorithme et d'implémenter le calcul de différentes valeurs (maximum, k-meilleurs, fonction de partition, etc) @xcite . par « unifié », nous entendons que nous utilisons les mêmes éléments (items) pour les trois algorithmes, seules les règles de déduction changent. éléments. sans perte de généralité, nous supposons que l'ordonnancement d'origine est la fonction identité sur {1, . . ., n}. nos systèmes de déduction utilisent des éléments de forme [i, j, s, t] où : algorithme en o(n 6 ). cet algorithme explore l'espace des permutations correspondant au voisinage des itg (inversion transduction grammars) @xcite . il contient deux règles de déduction dont les antécédents correspondent à deux empans contigus de la phrase originale : la règle (a) n'intervertit pas l'ordre des mots contenus dans les antécédents, la règle (b) les intervertit. les deux règles sont décrites à l'aide de 7 variables correspondant à des indices positionnels, suggérant que la complexité de l'algorithme est de o(n 7 ). cependant, la complexité peut être diminuée en utilisant une astuce similaire au « hook trick » des grammaires lexicalisées @xcite , résultant en une complexité de o(n 6 ) @xcite . l'idée consiste à récrire chaque déduction en deux étapes. pour cela, nous introduisons deux nouveaux type d'éléments que nous écrivons @xcite , avec @xmath1, et @xcite , avec @xmath2. la règle (a) peut alors se récrire comme : intuitivement, la règle (a') produit un item (incomplet) exprimant une possible extension de l'empan courant d'une position à droite, donnant lieu au bigramme w u , w v , la règle (a") complète l'opération si l'item attendu à droite est disponible. de façon similaire, la règle (b) peut se récrire comme : les règles (a') et (b') possèdent 5 variables libres alors que les règles (a") et (b") ont 6 variables libres. on obtient donc une complexité temporelle en o(n 6 ). algorithme en o(n 4 ). afin de réduire la complexité de l'algorithme précédent, il est possible d'interdire les réordonnancements « récursifs », c-à-d que si un empan contigu n'a pas les mêmes voisins dans la phrase réordonnée, alors tous les mots dans ce segment doivent être dans le même ordre que dans la phrase originale. cet espace de recherche correspond au modèle mj-1 @xcite , à la différence que nous découpons et réordonnons les segments de façon jointe et non comme deux étapes successives. avec cette contrainte, nous pouvons écrire un algorithme en programmation dynamique qui visite les empans de la phrase de gauche à droite et non des plus petits aux plus grands. dans un sens, cet algorithme est plus proche des algorithmes d'inférence des modèles semi-markov @xcite que des algorithmes de type cyk. les règles de déduction correspondantes sont : les indices indiqués comme « ? » ne sont pas importants pour l'algorithme et leur valeur n'impacte pas la complexité de l'algorithme car ceux-ci peuvent être récrits avec des éléments intermédiaires. la déduction (c) avance d'un mot dans la phrase, en ajoutant celui-ci à la fin de la permutation en cours. la déduction (d) est utilisée pour construire un sous-segment qui sera permuté. la déduction (e) avance de deux segments dans la phrase en permutant l'ordre de ceux-ci. la déduction (f) réalise une permutation de segments dont le premier antécédent commence au début de la phrase algorithme en o(n). enfin, nous proposons un algorithme en temps linéaire qui n'autorise que des permutations d'un seul mot à la fois : la déduction (g) est similaire à la règle (c) ci-dessus, avec une contrainte en plus. la déduction (h) avance de deux mots en échangeant leurs positions respectives. afin d'autoriser la permutation des deux premiers mot de la phrase, nous ajoutons l'axiome [1, 2, ?, 1] avec comme poids d 2,1 . des exemples d'éxécution de ces trois algorithmes sont reproduits sur la figure 1 . ## conclusion nous avons proposé et évalué une approche pour l'adaptation cross-lingue d'un analyseur en dépendances qui ne nécessite pas de réentraîner le modèle et qui peut être appliquée dans un scénario « zéro-shot ». cette approche n'utilise que des données monolingues anglaises, et peut se combiner avec de multiples modèles de réordonnancement. les résultats expérimentaux obtenus sur une vingtaine de langues montrent que cette approche est viable et permet d'améliorer en moyenne les résultats obtenus. les variations observées entre langues cibles restent à analyser en profondeur en relation avec les différents composants du modèle (plongements lexicaux, modèles de réordonnancement) et les différences typologiques avec l'anglais utilisé comme langue source.