# Alignements divisifs de textes parallèles: données, algorithme et évaluation

Joanna Radola, François Yvon

► To cite this version:

Joanna Radola, François Yvon. Alignements divisifs de textes parallèles: données, algorithme et évaluation. 32ème Conférence sur le Traitement Automatique des Langues Naturelles (TALN), ATALA, Jun 2025, Marseille, France. hal-05316630

HAL Id: hal-05316630

https://hal.science/hal-05316630v1

Submitted on 15 Oct 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Alignements divisifs de textes parallèles:
données, algorithme et évaluation

Joanna Radoła François Yvon

Sorbonne Université, CNRS, ISIR, 4, Place Jussieu, 75005 Paris, France
radola@isir.upmc.fr, yvon@isir.upmc.fr

## RÉSUMÉ

Nous présentons Alibi - un corpus d'alignements hiérarchiques sous-phrastiques français-anglais, annoté manuellement à l'aide d'une stratégie divisive. Nous comparons globalement les alignements ainsi obtenus avec plusieurs corpus parallèles alignés mot-à-mot et étalonnons sa difficulté en réalisant des alignements automatiques par des méthodes de l'état de l'art. Nous proposons également un algorithme exploitant des représentations neuronales des mots et des groupes de mots afin de reproduire les alignements hiérarchiques de référence. Enfin, nous proposons une métrique d'évaluation des arbres d'alignement avec laquelle nous comparons les performances de plusieurs variantes de l'algorithme d'alignement, obtenues en faisant varier les mesures d'appariemment de groupes de mots. Nos résultats montrent que (a) les arbres d'alignements de référence sont très ambigus et difficiles à reproduire automatiquement, cependant, les alignements mot-à-mot sont prédits de manière fiable ; (b) l'utilisation d'alternatives à la similarité cosinus pour évaluer l'appariemment de blocs permet d'améliorer significativement les résultats du système de base.

## ABSTRACT

### Divisive Alignment of Parallel Corpora - Data, Algorithm and Evaluation

We introduce Alibi - a corpus of French-English hierarchical sub-sentential alignments, human-annotated with use of the divisive methodology. We quantitatively compare these alignments to other parallel corpora aligned at word level and benchmark our corpus' difficulty using state-of-the-art alignment tools. Subsequently, we propose an algorithm that leverages neural representations of words and text segments to replicate the reference hierarchical alignments. Finally, we propose an evaluation metric for alignment trees and report scores obtained after testing multiple variations of the divisive alignment algorithm, using different metrics to pair sentence segments together. Our results suggest that (a) while reference alignment trees are highly ambiguous and difficult to reproduce automatically, word-level alignments are reliably predicted; (b) using alternatives to the cosine similarity to match segment pairs allows us to significantly improve baseline results.

**MOTS-CLÉS** : corpus parallèles, alignements de mots, alignements hiérarchiques, similarité lexicale, plongements lexicaux.

**KEYWORDS:** parallel corpora, word alignments, hierarchical alignments, lexical similarity, word embeddings.

Contribution originelle

<figure><img src="image_2.png" /></figure>
# 1 Introduction

L'alignement de mots au sein de segments parallèles est une tâche élémentaire en traitement automatique multilingue. Étant donné un couple de segments parallèles, il s'agit d'identifier des équivalents de traduction lexicaux entre la source et la cible (Tiedemann, 2011). Ces alignements sont utilisés pour extraire automatiquement des lexiques bilingues généralistes ou spécialisés (Liu et al., 2013), pour superviser l'attention dans des modèles de traduction neuronale (Alkhouli & Ney, 2017), pour analyser les sorties de systèmes de traduction (Stahlberg et al., 2018) ou encore pour détecter les confabulations des systèmes de traduction automatique (Wu et al., 2024). Il existe de multiples manières de résoudre ce problème, soit en s'appuyant sur des cooccurrences entre vocables cibles et sources, soit en construisant des modèles probabilistes de ces associations lexicales, comme le formulent les modèles de la famille IBM (Brown et al., 1993; Och & Ney, 2003) ou les modèles hiérarchiques de Wu (1997). Des évolutions récentes de ces méthodes exploitent des représentations denses calculées par des encodeurs neuronaux : par exemple, SimAlign (Jalili Sabet et al., 2020) et AwesomeAlign (Dou & Neubig, 2021) s'inspirent des méthodes heuristiques d'alignement en s'appuyant sur des représentations lexicales denses calculés par des modèles de langue; Wang et al. (2018) développent une version neuronale des modèles IBM. D'autres méthodes utilisent le mécanisme d'attention de modèles Transformer (Vaswani et al., 2017) pour extraire de tels alignements (Garg et al., 2019). Une autre approche récente consiste à entraîner des grands modèles de langue (LLMs) sur la tâche d'extraction de réponse. Cette méthode, introduite avec l'outil WSPAlign (Wu et al., 2023), est faiblement supervisée.

Les méthodes d'alignement restent toutefois majoritairement non-supervisées, les rares corpus annotés par des alignements de référence étant réservés à l'évaluation des méthodes automatiques. Pour le français, les principales ressources existantes sont Blinker (La Bible, Melamed, 2001), les données parlementaires des Hansards (Och & Ney, 2003) et les transcriptions de débats au parlement européen (Europarl) de Graça et al. (2008). Des différences fondamentales existent toutefois entre ces corpus, dues à la formulation des consignes d'annotation.

Dans ce travail, nous présentons une nouvelle ressource pour le français, correspondant à l'alignement intégral de cinq nouvelles avec leur traduction en anglais. Elle se distingue des autres ressources de ce type par la manière dont les annotations sont collectées, en adoptant une procédure itérative consistant à raffiner de manière itérative des alignements de phrase, selon une proposition initialement formulée par Xu & Yvon (2016). Cette procédure présente l'avantage de ne pas chercher à construire à priori des alignements au niveau des mots. Ceci permet de mieux aligner des expressions polylexicales, en gardant toujours un nœud pour l'expression entière et en divisant d'une manière plus fine seulement lorsque cela est possible. Nous décrivons en détail cette procédure, en contrastant les alignements ainsi collectés avec les autres données de référence pour les alignements français-anglais.

Dans un second temps, nous établissons des scores de référence pour l'alignement automatique de ces textes en utilisant des méthodes de l'état de l'art, puis discutons de la question plus complexe du calcul automatique d'alignements hiérarchiques et de leur évaluation, en nous appuyant sur plusieurs implémentations « neuronales » de l'algorithme de Lardilleux et al. (2012), pour lequel nous proposons diverses évolutions et variantes.

Les contributions de ce travail sont donc plurielles : elles consistent en un nouveau corpus annoté, ainsi que des propositions algorithmiques pour construire et évaluer des alignements hiérarchiques. Les données, les scripts et les documentations associées peuvent être téléchargées depuis le site web du projet : https://github.com/fyvo/AlibiWordAlignments.
<table><caption>TABLE 1 – Informations sur les œuvres, longueur en phrases et en nombre de mots.</caption><thead><tr><th></th><th>phrases</th><th>mots (FR)</th><th>mots (EN)</th></tr></thead><tbody><tr><td>[CHA] Le Chat botté (Charles Perrault, 1695)<br>Version française : https://fr.wikisource.org/wiki/Le_MaÂôtre kre chat_ou le kre bottÂl'<br>Traduction : https://en.wikisource.org/wiki/Old_time_stories_(Perrault,_Robinson)/Puss_in_Boots</td><td>52</td><td>1 861</td><td>2 036</td></tr><tr><td>[BAR] La Barbe-Bleue (Charles Perrault, 1697)<br>Version française : https://fr.wikisource.org/wiki/Contes de Perrault_(Âl'd._1902)/La Barbe-Bleue<br>Traduction : https://en.wikisource.org/wiki/The_fairy_ales_of(Charles Perrault_(Clarke,_1922)/Blue_Beard</td><td>68</td><td>2 145</td><td>2 234</td></tr><tr><td>[VIS] Vision de Charles XI (Prosper Mérimée, 1829)<br>Version française : https://fr.wikisource.org/wiki/Vision_de(Charles_XI<br>Traduction : https://en.wikisource.org/wiki/The_Writings_of_Prosper_M%C3%A9rim%C3%A9e/Volume_3/The_Vision_of(Charles_XI</td><td>106</td><td>2 912</td><td>2 790</td></tr><tr><td>[DER] La Dernière classe (Alphonse Daudet, 1873)<br>Version française : https://fr.wikisource.org/wiki/Les_Contes_du_lundi<br>Traduction : https://en.wikisource.org/wiki/The_Last_Lesson</td><td>92</td><td>2 045</td><td>1 935</td></tr><tr><td>[AUB] L'Auberge (Guy de Maupassant, 1886)<br>Version française : https://fr.wikisource.org/wiki/Le_Horla_(recueil)/L'Auberge<br>Traduction : https://en.wikisource.org/wiki/The_Inn</td><td>204</td><td>5 674</td><td>5 862</td></tr></tbody></table>

# 2 Un corpus littéraire d'alignements divisifs

## 2.1 Préparation du corpus

Nous avons sélectionné 5 courtes œuvres de la littérature française et leur traduction en anglais, choisies parmi un ensemble de textes libres de droits disponibles sur la toile<fnref n="1" />. Après suppression des balises HTML, ces textes ont été segmentés en phrases, puis annotés automatiquement en partie du discours et analysés syntaxiquement. Pour les versions françaises et anglaises, l'étiquetage morpho-syntaxique est calculé par le MaxentTagger de Stanford (Toutanova et al., 2003)²; les dépendances syntaxiques sont calculées respectivement par les modèles *frenchFactored* et *englishPCFG*.

Enfin, ces documents ont été alignés automatiquement au niveau des phrases avec l'outil hunalign (Varga et al., 2007). Cet alignement a ensuite été révisé et validé manuellement. Les statistiques de base concernant ces données sont dans le Tableau 1.

## 2.2 Procédure d'alignement

L'annotation des alignements a été réalisé par une unique annotatrice, traductrice professionnelle et rémunérée pour cette tâche, avec des échanges réguliers avec les responsables scientifiques pour discuter des alignements problématiques, sur une durée d'environ deux mois.

Chaque étape d'annotation manuelle se déroule comme suit : des segments parallèles sont préparés et rendus disponibles sur une interface d'annotation. L'annotatrice identifie alors un point de segmentation unique dans les côtés source et cible de chaque segment, ainsi que leur *orientation relative* (monotone, si les deux fragments sources et cibles apparaissent dans le même ordre, anti-monotone, sinon). Sur cette base, les segments parallèles en entrée sont effectivement divisés et sont inclus dans le prochain lot de segments à annoter. Cette procédure est illustrée sur la Figure 1.

<footnote n="1">1. Les textes originaux sont disponibles sur Wikisource, comme leurs traductions en anglais. Les licences et restrictions d'usage sont documentées sur ce même site (voir https://fr.wikisource.org/wiki/Aide:Droit_d'auteur).
2. Voir https://nlp.stanford.edu/software/tagger.shtml pour la documentation des annotations.</footnote>
<figure><img src="image_3.png" /><figcaption>FIGURE 1 – Annotation d'alignements hiérarchiques. La partie supérieure montre le texte en cours d'annotation, où les mots qui correspondent à des points de segmentation sont marqués. La partie inférieure représente les deux couples de segments résultant de cette segmentation (monotone), qui feront l'objet de la phase suivante de segmentation.</figcaption></figure>

<figure><img src="image_4.png" /><figcaption>FIGURE 2 – Un exemple d'arbre de segments alignés.</figcaption></figure>

Lorsque plusieurs points de segmentation sont possibles<fnref n="3" />, les consignes sont de segmenter préférentiellement à la frontière de constituant syntaxique de plus haut niveau ; puis de construire des segmentations en fragments équilibrés en taille. La segmentation s'arrête quand il n'est plus possible de segmenter en deux blocs, soit du fait de l'impossibilité de décomposer l'association bilingue en deux sous-parties (cas d'une locution ou d'un idiome ou d'un terme complexe) ; soit parce que l'un des côtés du segment parallèle ne contient qu'un seul mot ; soit, dans de rares cas, parce que les associations entre sous-parties des segments exigerait une segmentation en trois fragments. Des exemples de telles configurations difficiles à aligner et qui ne peuvent être prédites par l'algorithme divisif binaire sont donnés dans Kaeshammer & Westburg (2014), voir également Søgaard (2010).

La première de ces conditions d'arrêt est la principale justification de l'approche divisive et permet aux annotateurs de construire des associations lexicales au niveau le plus fin uniquement quand cela est pertinent, au lieu de prendre systématiquement les mots comme unités d'alignement.

Le résultat de cette procédure est un alignement hiérarchique complet des 5 œuvres, correspondant à un ensemble d'arbres binaires, où chaque phrase parallèle est représentée comme un arbre (voir l'exemple de la Figure 2). Le corpus complet représente un total d'environ 23 000 segments (nœuds) alignés. Le détail, œuvre par œuvre, ainsi que les statistiques sur la profondeur des arbres d'alignement sont dans le Tableau 2.

Le résultat de l'annotation est diffusé sous la forme d'un document XML pour chaque texte, contenant à la fois les informations linguistiques associées à chaque phrase, ainsi que la hiérarchie complète

<footnote n="3">3. Ainsi, il serait possible de segmenter l'exemple de la Figure 1 après (femmes, women), ou encore (sautèrent, jumped).</footnote>
<table><caption>TABLE 2 – Nombre de tous les segments et des feuilles uniquement, profondeur des arbres d'alignement et longueur moyenne des phrases pour les 5 textes parallèles du corpus.</caption><thead><tr><th rowspan="2">texte</th><th colspan="2">nb segments</th><th colspan="3">profondeur d'arbre</th><th colspan="2">mots/phrase</th></tr><tr><th>tous</th><th>feuilles</th><th>moy</th><th>max</th><th>min</th><th>FR</th><th>EN</th></tr></thead><tbody><tr><td>CHA</td><td>3091</td><td>1453</td><td>7,4</td><td>10</td><td>4</td><td>36,5</td><td>39,9</td></tr><tr><td>BAR</td><td>3311</td><td>1522</td><td>7,1</td><td>11</td><td>1</td><td>32,0</td><td>33,3</td></tr><tr><td>VIS</td><td>4480</td><td>2165</td><td>6,8</td><td>12</td><td>2</td><td>27,7</td><td>26,6</td></tr><tr><td>DER</td><td>2902</td><td>1420</td><td>5,5</td><td>11</td><td>1</td><td>22,5</td><td>21,3</td></tr><tr><td>AUB</td><td>9144</td><td>4368</td><td>6,9</td><td>12</td><td>2</td><td>28,0</td><td>28,9</td></tr><tr><td>Tous</td><td>22928</td><td>10928</td><td>6,7</td><td>12</td><td>1</td><td>28,3</td><td>28,7</td></tr></tbody></table>

des points de segmentation. Ce corpus, ainsi que les éléments de documentation associés (contenu, formats, etc) est distribué sous licence *Creative Commons CC-BY-SA*<fnref n="4" />.

# 3 Comparaison avec les corpus existants

## 3.1 Nombre et type des liens

Les ressources existantes pour l'alignement mot-à-mot en français sont représentées, pour chaque phrase parallèle, par un ensemble de couples d'indices identifiant les mots associés. Un premier facteur qui distingue les corpus existants entre eux est le découpage en mots qui est sous-jacent aux alignements. Les annotations manuelles distinguent les associations dites **sûres** et celles qui sont simplement **possibles**, avec une interprétation qui varie d'un corpus à l'autre<fnref n="5" />, ce qui est un autre facteur majeur de différentiation.

Pour permettre la comparaison entre les alignements obtenus par l'annotation divisive et les autres alignements de référence, les heuristiques suivantes sont utilisées pour convertir les arbres d'alignement hiérarchiques en alignements mot-à-mot :

1. Un nœud feuille correspondant à un alignement un-à-un est transformé en un lien **sûr**.

2. Pour les feuilles contenant plus d'un mot, un lien **possible** est créé pour tout couple (mot source, mot cible) apparaissant dans ce bloc. Ainsi, un alignement de la feuille (*Barbe Bleue*, *Blue Beard*) associant deux segments de longueur 2 donnera lieu à quatre liens **possibles**.

Ainsi, l'alignement mot-à-mot correspondant à l'alignement de la Figure 2 est : 0-0 1-1 2-2 3-4 4p5 5p5 6p6 6p7.

Comme montre le Tableau 3, notre corpus excède en taille les ressources existantes, représentant un ajout encore plus significatif lorsqu'on l'évalue en nombre d'unités textuelles. Ceci est dû au fait que les autres corpus contiennent des textes juridiques, tandis que le nôtre est constitué sur de textes littéraires, avec des phrases plus longues en moyenne.

On observe que le corpus Hansards contient trois fois plus de liens possibles que de liens sûrs, alors qu'à l'inverse Europarl en contient très peu. Nos annotations représentent une situation intermédiaire,

<footnote n="4">4. https://creativecommons.org/licenses/by-sa/4.0/deed.en</footnote>

<footnote n="5">5. Documentant EPPS, (Graça et al., 2008) distingue ainsi : « an S-alignment is used when a translation is possible in every context, (...) we considered P-alignments when a translation was possible in certain contexts ».</footnote>
<table><caption>TABLE 3 – Comparaison des corpus alignés mot-à-mot pour la paire anglais-français (HANS-Hansards, EPPS-Europarl).</caption><thead><tr><th rowspan="2"></th><th rowspan="2">nb<br>phrases</th><th colspan="2">nb unités</th><th colspan="2">nb liens</th><th colspan="2">nb non-alignés</th></tr><tr><th>FR</th><th>EN</th><th>sûrs</th><th>poss.</th><th>FR</th><th>EN</th></tr></thead><tbody><tr><td>HANS</td><td>447</td><td>7 761</td><td>7 020</td><td>4 038</td><td>13 400</td><td>349</td><td>327</td></tr><tr><td>EPPS</td><td>100</td><td>1 227</td><td>1 072</td><td>1 009</td><td>437</td><td>76</td><td>75</td></tr><tr><td>Alibi</td><td>522</td><td>14 637</td><td>14 857</td><td>8 452</td><td>14 147</td><td>975</td><td>1 212</td></tr></tbody></table>

avec environ 60% de liens étiquetés comme **possibles**.

On observe aussi un nombre de liens nuls (mots non-alignés) assez significatif dans notre corpus. Ceci est dû au caractère littéraire des textes, qui ont moins tendance à être traduits mot-à-mot. Par exemple : la phrase française « *Un meunier ne laissa pour tous biens, à trois enfants qu'il avait, que (...)* » est rendue en anglais par « *Once upon a time there was a miller who left no more riches to the three sons he had than (...)* ». Cette traduction entraîne des liens nuls pour les six premiers mots en anglais, le premier segment aligné étant (*un meunier, a miller*).

## 3.2 Évaluation des alignements mot-à-mot

SimAlign (Jalili Sabet et al., 2020) exploite des plongements lexicaux multilingues pour construire automatiquement des alignements (au niveau des unités sous-lexicales ou des mots). Cet outil ne nécessite aucun pré-entraînement sur des données parallèles, et peut en particulier être utilisé pour aligner des langues rares ou minoritaires. Par défaut, SimAlign obtient des plongements à partir de mBERT (Devlin et al., 2019) ou XLM-R (Conneau et al., 2020) et calcule les similarités cosinus entre toutes les unités des phrases source et cible. Trois heuristiques permettent ensuite de dériver de cette matrice des alignements unitaires : Argmax, Itermax and Match. Les résultats obtenus avec ces méthodes<fnref n="6" />, en prenant les annotations hiérarchiques converties en format mot-à-mot comme référence, sont données dans le Tableau 4.

Les alignements mot-à-mot sont évalués à l'aide des métriques standard suivantes : précision, rappel, F-score, AER (pour *Alignment Error Rate*, taux d'erreur d'alignement), respectivement définies par :

$$ \text{Pr} = \frac{|A \cap (S \cup P)|}{|A|}, \quad \text{Ra} = \frac{|A \cap S|}{|S|}, \quad F_1 = \frac{2 \text{Pr} \times \text{Ra}}{\text{Pr} + \text{Ra}}, \quad \text{AER} = 1 - \frac{|A \cap S| + |A \cap (S \cup P)|}{|A| + |S|} $$

où *A* est l'ensemble des alignements prédits et *S* et *P* sont respectivement les ensembles d'alignements sûrs et possibles de référence.

On observe que les résultats d'alignement sur les cinq nouvelles sont plutôt homogènes ce qui indique qu'il n'y avait pas de différences majeures dans les annotations divisives. La méthode Argmax, qui favorise la précision, est celle qui conduit aux meilleurs scores d'AER.

Comme discuté par Ngo Ho (2021), la profusion de liens possibles a pour effet de biaiser la métrique d'AER en faveur des méthodes d'alignement qui privilégient la précision sur le rappel. C'est bien ce que l'on observe : les résultats sur notre ressource sont en moyenne un peu moins bon que sur le

<footnote n="6">6. Le modèle est xlm-roberta-base, les alignements sont calculés au niveau des mots, les autres paramètres de SimAlign ont leur valeur par défaut.</footnote>
<table><caption>TABLE 4 – Résultats d’alignement au niveau des mots avec SimAlign pour les corpus de référence Hansards et Europarl et pour notre nouvelle ressource, avec les détails oeuvre par oeuvre. Une valeur plus faible de l’AER indique un meilleur alignement.</caption><thead><tr><th rowspan="2"></th><th colspan="4">Argmax</th><th colspan="4">Itermax</th><th colspan="4">Match</th></tr><tr><th>Pr</th><th>Ra</th><th>F1</th><th>AER</th><th>Pr</th><th>Ra</th><th>F1</th><th>AER</th><th>Pr</th><th>Ra</th><th>F1</th><th>AER</th></tr></thead><tbody><tr><td>HANS</td><td>96,0</td><td>90,6</td><td>93,2</td><td>6,4</td><td>91,0</td><td>93,4</td><td>92,2</td><td>8,0</td><td>85,3</td><td>93,4</td><td>89,2</td><td>11,7</td></tr><tr><td>EPPS</td><td>94,2</td><td>71,0</td><td>81,0</td><td>18,5</td><td>88,9</td><td>74,4</td><td>81,0</td><td>18,6</td><td>84,3</td><td>75,0</td><td>79,4</td><td>20,3</td></tr><tr><td>Alibi</td><td>94,8</td><td>89,0</td><td>91,8</td><td>7,7</td><td>90,0</td><td>93,8</td><td>91,4</td><td>8,5</td><td>83,5</td><td>95,6</td><td>89,1</td><td>12,0</td></tr><tr><td>CHA</td><td>95,8</td><td>92,2</td><td>94,0</td><td>5,8</td><td>90,7</td><td>93,7</td><td>92,2</td><td>8,1</td><td>84,6</td><td>97,1</td><td>90,4</td><td>10,5</td></tr><tr><td>BAR</td><td>93,7</td><td>89,9</td><td>91,8</td><td>7,9</td><td>88,7</td><td>94,3</td><td>91,4</td><td>9,1</td><td>80,7</td><td>95,5</td><td>87,5</td><td>14,0</td></tr><tr><td>VIS</td><td>94,7</td><td>88,0</td><td>91,2</td><td>8,3</td><td>90,4</td><td>93,3</td><td>91,8</td><td>8,4</td><td>83,2</td><td>94,2</td><td>88,4</td><td>12,6</td></tr><tr><td>DER</td><td>94,3</td><td>86,9</td><td>90,4</td><td>8,9</td><td>89,8</td><td>91,5</td><td>90,6</td><td>9,6</td><td>84,6</td><td>95,0</td><td>89,5</td><td>11,7</td></tr><tr><td>AUB</td><td>95,7</td><td>88,1</td><td>91,7</td><td>7,7</td><td>90,4</td><td>96,1</td><td>93,2</td><td>7,2</td><td>84,3</td><td>96,1</td><td>89,8</td><td>11,2</td></tr></tbody></table>

Hansards, mais bien meilleurs que pour Europarl, illustrant l’effet du nombre de liens possibles et de mots non alignés sur les scores absolus d’alignement.

# 4 Algorithme d’alignement divisif

## 4.1 Version initiale

L’algorithme divisif de Lardilleux et al. (2012) construit récursivement une segmentation jointe de phrases parallèles, en se basant sur les scores d’associations lexicales bilingues dérivés de leurs cooccurrences dans un corpus parallèle. Cet algorithme a été initialement introduit pour la segmentation d’images par Shi & Malik (2000) et ensuite utilisé avec succès pour la segmentation de documents (Zha et al., 2001). Nous développons des variantes de cet algorithme, en l’appliquant aux mêmes matrices de similarité que celles qu’exploite SimAlign, pour reproduire les arbres d’alignement. L’algorithme complet se trouve en annexe A, avec une discussion de sa complexité.

De manière similaire à la procédure manuelle présentée §2.2, cet algorithme divise récursivement chaque couple de segments (S, T) en deux parties $S = A\bar{A}$ et $T = B\bar{B}$, puis aligne les nouveaux sous-segments soit de manière *monotone* ($A$ avec $B$, $\bar{A}$ avec $\bar{B}$), soit de manière *anti-monotone* ($A$ avec $\bar{B}$ et $\bar{A}$ avec $B$).

Chaque étape de l’algorithme implique deux décisions : (a) le choix du point de segmentation et (b) l’orientation associée. Pour optimiser ces choix, nous parcourons tous les indices possibles dans les deux segments et calculons le score NCut pour les deux orientations possibles. Pour expliciter ce calcul, nous commençons par définir le score d’association $W(S, T)$ du bitexte (S, T) selon $W(S, T) = \sum_{s \in S, t \in T} w(s, t)$, avec $w(s, t)$ une mesure d’association lexicale qui peut être définie au niveau des mots ou des unités sous-lexicales. Une première approche sélectionne la segmentation optimisant la coupure (cut) définie par$^7$ :

$$ \mathrm{cut}(A, B) = W(A, \bar{B}) + W(\bar{A}, B) $$

<footnote n="7">7. Ce critère étant symétrique en $(A, B)$ et $(\bar{A}, \bar{B})$, il suffit de le minimiser sur l’un de deux blocs.</footnote>
La meilleure segmentation monotone (resp. anti-monotone) minimise $cut(A, B)$ (resp. $cut(A, \bar{B})$) sur tous les points de coupure possibles ; on choisit finalement la meilleure des deux orientations. Cette approche conduit à minimiser les scores d'association des segments qui sont exclus de l'alignement ($(A, \bar{B})$ et $(\bar{A}, B)$ pour une segmentation monotone). Cependant, son utilisation tend à produire des segments déséquilibrés (Shi & Malik, 2000), puisque des segments non-alignés plus courts auront une association globale plus faible que des segments plus longs. C'est pourquoi Lardilleux et al. (2012) trouvent préférable de minimiser le score $NCut$ défini (pour une segmentation monotone) par :

$$NCut(A, B) = \frac{\mathrm{cut}(A, B)}{\mathrm{cut}(A, B) + 2 \times W(A, B)} + \frac{\mathrm{cut}(\bar{A}, \bar{B})}{\mathrm{cut}(\bar{A}, \bar{B}) + 2 \times W(\bar{A}, \bar{B})},$$

ce qui conduit à des segmentations plus équilibrées. L'algorithme termine lorsque l'un des segments a une longueur égale à 1. Le résultat final est un arbre binaire qui représente la structure hiérarchique des phrases parallèles ainsi que leurs alignements. En utilisant les heuristiques de conversion présentées en 3.1, on peut au besoin se ramener à des alignements de mots.

## 4.2 Introduction de similarités locales

L'algorithme de segmentation repose intégralement sur des calculs de similarité lexicales impliquées par $W(S, T)$ : pour pouvoir comparer nos résultats avec ceux de SimAlign, nous utilisons comme score $w(s, t)$ le cosinus des plongements 8 associés respectivement à $s$ et $t$, calculés en moyennant les plongements des unités sous-lexicales qui les composent. Comme le montrent Radovanovic et al. (2010), certains vecteurs dans l'espace de représentation des plongements lexicaux sont des hubs autour desquels d'autres vecteurs se concentrent : ces hubs sont les plus « populaires » parmi les plus proches voisins calculés par la similarité cosinus. En plus du phénomène de hubness, les données de grande dimension présentent également une tendance à l'uniformisation des similarités et concentration de distances entre toutes les paires de points, qui fait que tous les points sont presque également proches les uns des autres (Aggarwal et al., 2001). De ce fait, la plage des scores de similarité sous-jacents aux alignements est assez étroite.

Pour atténuer ce phénomène, on remplace la similarité cosinus par une mesure locale, CSLS 9, qui ajuste la similarité cosinus entre deux unités source et cible $x$ et $y$ en fonction de la similarité moyenne de $x$ (resp. $y$) avec son voisinage dans l'espace cible (resp. source). Cette opération a pour effet de « dilater » les régions où la densité de points est élevée, éloignant ainsi les hubs de leurs voisins (Conneau et al., 2017; Joulin et al., 2018). CSLS est défini par

$$CSLS(x, y) = 2 \cos(x, y) - \frac{1}{k} \sum_{y' \in \mathcal{N}_y(x)} \cos(x, y') - \frac{1}{k} \sum_{x' \in \mathcal{N}_x(y)} \cos(x', y), \quad (1)$$

avec $\mathcal{N}_u$ l'ensemble des $k$-plus proches voisins de $u$.

Un autre changement apporté au calcul des similarités lexicales consiste à ajouter un paramètre de température, qui a pour effet d'amplifier les différences entre similarités. On remplace donc CSLS($x, y$) par $CSLS(x, y)^\tau$, avec $\tau \in [2 : 10]$, ce qui augmente l'impact des hautes valeurs de similarité et diminue les plus basses. Une comparaison de différents calculs des matrices de similarité est représenté sur la Figure 3.

<footnote n="8">8. Calculés, de nouveau, par xlm-roberta-base ou bert-base-multilingual-cased.</footnote>

<footnote n="9">9. Pour Cross-domain Similarity Local Scaling.</footnote>
<figure><img src="image_5.png" /><figcaption>FIGURE 3 – Visualisation de différentes matrices de similarité. L'utilisation de CSLS, avec un paramètre de température élevé, permet de concentrer les similarités sur la diagonale, où sont localisés les alignements corrects pour cet exemple.</figcaption></figure>

## 4.3 Seuil minimal de similarité

Une méthode pour améliorer la précision de l’algorithme consiste à introduire un seuil minimal de similarité ε dans une étape de post-traitement. Si la similarité entre deux mots est inférieure à ce seuil, l’alignement est rejeté. Ce seuillage est appliqué séparément aux similarités entre chaque alignement mot-à-mot inféré d’une feuille. L’introduction de ce seuillage permet d’éviter l’alignement de certains mots, ce qui n’est pas possible avec la version de base de l’algorithme.

## 4.4 Résultats

Afin de comparer les arbres obtenus à partir de l’algorithme d’alignement divisif aux arbres de référence, on représente chaque arbre sous la forme d’une liste de couples de segments alignés : au plus haut niveau le couple de phrases parallèles, au plus bas les feuilles de l’arbre. Pour comparer un arbre de référence avec un arbre prédit, on utilise alors les métriques classiques (précision, rappel, F-score) sur ces deux listes, en considérant pour les calculs :

- tous les segments ;

- uniquement les feuilles ;

- uniquement les segments non-feuilles.

Avec les améliorations introduites dans les sections 4.2 et 4.3, les résultats d’évaluation sur le format mot-à-mot et sur les arbres d’alignement sont dans le Tableau 5. Les méta-paramètres ont été optimisés sur *Le Chat Botté*, qui a servi de corpus de développement. Les précisions sur la recherche de méta-paramètres se trouvent en annexe C.

Les scores d’alignement mot-à-mot restent bien en deçà de ceux obtenus avec SimAlign (Tableau 4), essentiellement du fait d’un trop faible rappel, puisque la précision est dans l’ensemble très satisfaisante. Une indication est que notre algorithme ne prédit que 16 455 liens, quand le corpus total en comprend plus de 22 500 (Tableau 2). Ceci suggère que la procédure divisive automatique produit des segments trop fins<fnref n="10" />. Le seuil de similarité choisi est un autre facteur qui privilégie trop fortement la précision au détriment du rappel. Pour ce qui concerne la métrique de comparaison d’arbre, on constate que tous les scores sont assez faibles, en particulier pour les résultats relatifs aux segments

<footnote n="10">10. Les alignements fins produisent moins de liens que les alignements grossiers, qui construisent un nombre quadratique de liens en fonction de leur longueur : un alignement 1-1 produit 1 lien, un alignement 2-2 en produit 4, etc.</footnote>
<table><caption>TABLE 5 – Les résultats moyens de l’algorithme divisif sur le corpus de test, obtenus avec la version initiale (base : $\tau = 1, \varepsilon = 0.0$, sim = cos, model = mbert) et la meilleure version (best : $\tau = 7, \varepsilon = 0.008$, sim = csls, k = 2, model = mbert). Pour le meilleur jeu de paramètres on donne également le détail par œuvre. On compare les alignements mot-à-mot, ainsi que les résultats correspondants pour comparaisons exactes des nœuds des arbres de référence avec les arbres générés.</caption><thead><tr><th rowspan="2"></th><th colspan="4">mot-à-mot</th><th colspan="3">tous les segments</th><th colspan="3">feuilles</th><th colspan="3">non-feuilles</th></tr><tr><th>Pr</th><th>Ra</th><th>F1</th><th>AER</th><th>Pr</th><th>Ra</th><th>F1</th><th>Pr</th><th>Ra</th><th>F1</th><th>Pr</th><th>Ra</th><th>F1</th></tr></thead><tbody><tr><td>base</td><td>58,2</td><td>71,5</td><td>64,1</td><td>37,4</td><td>29,3</td><td>32,1</td><td>30,6</td><td>40,0</td><td>47,2</td><td>43,2</td><td>15,8</td><td>16,3</td><td>16,0</td></tr><tr><td>best</td><td><strong>93,2</strong></td><td><strong>76,6</strong></td><td><strong>85,0</strong></td><td><strong>13,8</strong></td><td>32,2</td><td>34,7</td><td>33,5</td><td>46,1</td><td>53,0</td><td>49,3</td><td>15,6</td><td>15,7</td><td>15,6</td></tr><tr><td>BAR</td><td>91,0</td><td>77,1</td><td>83,5</td><td>15,4</td><td>28,0</td><td>30,4</td><td>29,2</td><td>40,2</td><td>48,4</td><td>43,9</td><td>12,2</td><td>12,0</td><td>12,1</td></tr><tr><td>VIS</td><td>94,9</td><td>78,0</td><td>85,6</td><td>13,1</td><td>34,6</td><td>36,6</td><td>35,6</td><td>49,4</td><td>55,3</td><td>52,2</td><td>17,0</td><td>17,1</td><td>17,0</td></tr><tr><td>DER</td><td>93,8</td><td>79,5</td><td>86,1</td><td>12,6</td><td>32,3</td><td>36,3</td><td>34,2</td><td>45,8</td><td>53,9</td><td>49,5</td><td>16,0</td><td>17,1</td><td>16,5</td></tr><tr><td>AUB</td><td>93,2</td><td>77,7</td><td>84,7</td><td>14,1</td><td>34,0</td><td>35,6</td><td>34,8</td><td>48,8</td><td>54,5</td><td>51,5</td><td>17,0</td><td>16,7</td><td>16,8</td></tr><tr><td>CHA</td><td>93,2</td><td>77,4</td><td>84,6</td><td>14,4</td><td>33,5</td><td>34,7</td><td>34,1</td><td>50,0</td><td>56,0</td><td>52,8</td><td>14,1</td><td>13,6</td><td>13,8</td></tr></tbody></table>

non-feuilles. Les segments initiaux produits par l’algorithme restent parfois très déséquilibrés en dépit du terme de normalisation introduit par Ncut, ce qui fait que les segments intermédiaires sont rarement retrouvés<fnref n="11" />. Une exploration d’alternatives à Ncut est dans l’annexe B. Ces faibles valeurs sont également liées à la procédure d’évaluation très stricte implémentée dans la métrique, qui ne vérifie que les correspondances exactes : elle considère donc qu’un segment comme (0,5-0,5) est incorrect aussi bien quand la référence est (0,5-0,4), que quand elle est (0,5-10,20). Si les alignements internes étaient aussi erronés que la métrique le suggère, les scores pour les feuilles seraient au moins aussi mauvais ; or, ils sont nettement meilleurs. Une amélioration serait alors de mieux prendre en compte les correspondances partielles, par analogie avec les propositions de Véronis & Langlais (2000) pour l’alignement de phrases.

# 5 Conclusion et perspectives

Dans cet article, nous avons introduit un corpus annoté d’alignements hiérarchiques, également disposables dans un format « mot-à-mot ». La méthodologie d’annotation hiérarchique présente l’avantage de fournir des alignements de groupes de mots, qui, couplés aux annotations syntaxiques disponibles, permettront de mieux analyser les divergences entre langues dans des textes parallèles. Cette ressource, librement disponible, peut servir comme un jeu de test pour des systèmes d’alignement des mots, ajoutant aux données existantes un autre genre textuel et une autre procédure d’annotation manuelle des alignements.

Nous avons ensuite utilisé un algorithme divisif s’appuyant sur des plongements multilingues pour reproduire ces annotations. Comme noté dans la section 4.4, la fonction Ncut produit souvent des segments déséquilibrés. Nos résultats confirment que le remplacement de la similarité cosinus avec CSLS, en utilisant le méta-paramètre de température, rend les différences entre les valeurs dans les matrices de similarité plus prononcées, ce qui fait aussi que ces valeurs sont mieux alignées avec les intuitions humaines. Cette étude souligne l’importance de la recherche sur les propriétés

<footnote n="11">11. Il arrive ainsi souvent que le premier niveau de segmentation isole un seul mot – par exemple la ponctuation finale – du reste de la phrase.</footnote>
de l'espace des plongements, dans le but de rendre la plage des similarités plus large et rendre cet espace plus facilement interprétable. Atténuer les phénomènes de concentration des distances et de hubness pourrait rendre de nombreux outils de TAL plus performants. Au final, ces expériences avec l'algorithme divisif ont apporté une amélioration significative de plus de 20 points de pourcentage d'AER par rapport à sa version de base.

Ce travail offre plusieurs perspectives. Du point de vue algorithmique, nous souhaitons poursuivre l'analyse approfondie de NCut et de ses variantes. Cela permettrait de produire des segments plus équilibrés. Du point de vue des similarités, au-dela de la question de la métrique de comparaison, nous souhaitons évaluer l'utilisation de plongements calculés directement au niveau des segments, plutôt que les déduire des unités qui les composent. Les plongements de phrases comme ceux calculés avec LASER (Artetxe & Schwenk, 2019) ou LaBSE (Feng et al., 2022) pourraient être utilisés à cet effet, avec toutefois un surcoût computationnel important, du fait de l'impossibilité d'utiliser des méthodes de programmation dynamique.

Une autre extension de ce travail consistera à explorer des métriques alternatives pour la comparaison d'arbres. Au lieu de rechercher des correspondances exactes entre les nœuds, d'autres caractéristiques pourraient être comparées, par exemple la profondeur ou le niveau d'équilibre des arbres. Prendre en compte la différence entre les tailles des segments pourrait limiter la chute des scores lorsque une ou deux unités se retrouvent dans le segment opposé. Une alternative sera de considérer une métrique comme *Tree Edit Distance* (TED, Schwarz et al., 2017).

## Remerciements

Ces travaux ont bénéficié d'un accès aux moyens de calcul de l'IDRIS au travers de l'allocation de ressources 2024-AD011011717R3 attribuée par GENCI. Ces travaux ont été réalisés dans le cadre du programme « Langues et numérique » 2016-2017 de la Délégation Générale à la Langue Française et aux langues de France.

Nous souhaitons remercier les relecteurs et relectrices pour leurs commentaires, Yong Xu pour sa gestion de la collecte des alignements, et Doriana Rüesch qui a réalisé les annotations manuelles.

## Références

AGGARWAL C. C., HINNEBURG A. & KEIM D. A. (2001). On the surprising behavior of distance metrics in high dimensional spaces. In *Proceedings of the 8th International Conference on Database Theory*, ICDT '01, p. 420–434, Berlin, Heidelberg : Springer-Verlag.

ALKHOULI T. & NEY H. (2017). Biasing attention-based recurrent neural networks using external alignment information. In O. BOJAR, C. BUCK, R. CHATTERJEE, C. FEDERMANN, Y. GRAHAM, B. HADDOW, M. HUCK, A. J. YEPES, P. KOEHN & J. KREUTZER, Éds., *Proceedings of the Second Conference on Machine Translation*, p. 108–117, Copenhagen, Denmark : Association for Computational Linguistics. DOI : 10.18653/v1/W17-4711.
ARTETXE M. & SCHWENK H. (2019). Massively multilingual sentence embeddings for zero-shot cross-lingual transfer and beyond. *Transactions of the Association for Computational Linguistics*, **7**, 597–610. DOI: 10.1162/tacl_a_00288.

BROWN P. F., DELLA PIETRA S. A., DELLA PIETRA V. J. & MERCER R. L. (1993). The mathematics of statistical machine translation: Parameter estimation. *Computational Linguistics*, **19**(2), 263–311.

CONNEAU A., KHANDELWAL K., GOYAL N., CHAUDHARY V., WENZEK G., GUZMÁN F., GRAVE E., OTT M., ZETTLEMOYER L. & STOYANOV V. (2020). Unsupervised cross-lingual representation learning at scale. In D. JURAFSKY, J. CHAI, N. SCHLUTER & J. TETREAULT, Éds., *Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics*, p. 8440–8451, Online: Association for Computational Linguistics. DOI: 10.18653/v1/2020.acl-main.747.

CONNEAU A., LAMPLE G., RANZATO M., DENOYER L. & JÉGOU H. (2017). Word translation without parallel data. *arXiv preprint arXiv:1710.04087*.

DEVLIN J., CHANG M.-W., LEE K. & TOUTANOVA K. (2019). BERT: Pre-training of deep bidirectional transformers for language understanding. In J. BURSTEIN, C. DORAN & T. SOLORIO, Éds., *Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers)*, p. 4171–4186, Minneapolis, Minnesota: Association for Computational Linguistics. DOI: 10.18653/v1/N19-1423.

DOU Z.-Y. & NEUBIG G. (2021). Word alignment by fine-tuning embeddings on parallel corpora. In P. MERLO, J. TIEDEMANN & R. TSARFATY, Éds., *Proceedings of the 16th Conference of the European Chapter of the Association for Computational Linguistics: Main Volume*, p. 2112–2128, Online: Association for Computational Linguistics. DOI: 10.18653/v1/2021.eacl-main.181.

FENG F., YANG Y., CER D., ARIVAZHAGAN N. & WANG W. (2022). Language-agnostic BERT sentence embedding. In S. MURESAN, P. NAKOV & A. VILLAVICENCIO, Éds., *Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)*, p. 878–891, Dublin, Ireland: Association for Computational Linguistics. DOI: 10.18653/v1/2022.acl-long.62.

GARG S., PEITZ S., NALLASAMY U. & PAULIK M. (2019). Jointly learning to align and translate with transformer models. In K. INUI, J. JIANG, V. NG & X. WAN, Éds., *Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP)*, p. 4453–4462, Hong Kong, China: Association for Computational Linguistics. DOI: 10.18653/v1/D19-1453.

GRAÇA J., PARDAL J. P., COHEUR L. & CASEIRO D. (2008). Building a golden collection of parallel multi-language word alignment. In N. CALZOLARI, K. CHOUKRI, B. MAEGAARD, J. MARIANI, J. ODIJK, S. PIPERIDIS & D. TAPIAS, Éds., *Proceedings of the Sixth International Conference on Language Resources and Evaluation (LREC'08)*, Marrakech, Morocco: European Language Resources Association (ELRA).

JALILI SABET M., DUFTER P., YVON F. & SCHÜTZE H. (2020). SimAlign: High Quality Word Alignments Without Parallel Training Data Using Static and Contextualized Embeddings. In *Findings of the Association for Computational Linguistics: EMNLP 2020*, p. 1627–1643, Online.

JOULIN A., BOJANOWSKI P., MIKOLOV T., JÉGOU H. & GRAVE E. (2018). Loss in translation: Learning bilingual word mapping with a retrieval criterion. In E. RILOFF, D. CHIANG, J. HOCKENMAIER & J. TSUJII, Éds., *Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing*, p. 2979–2984, Brussels, Belgium: Association for Computational Linguistics. DOI: 10.18653/v1/D18-1330.
KAESHAMMER M. & WESTBURG A. (2014). On complex word alignment configurations. In N. CALZOLARI, K. CHOUKRI, T. DECLERCK, H. LOFTSSON, B. MAEGAARD, J. MARIANI, A. MORENO, J. ODIJK & S. PIPERIDIS, Éds., *Proceedings of the Ninth International Conference on Language Resources and Evaluation (LREC’14)*, p. 1773–1780, Reykjavik, Iceland : European Language Resources Association (ELRA).

LARDILLEUX A., YVON F. & LEPAGE Y. (2012). Hierarchical sub-sentential alignment with anymalign. In M. CETTOLO, M. FEDERICO, L. SPECIA & A. WAY, Éds., *Proceedings of the 16th Annual Conference of the European Association for Machine Translation*, p. 279–286, Trento, Italy : European Association for Machine Translation.

LIU X., DUH K. & MATSUMOTO Y. (2013). Topic models + word alignment = a flexible framework for extracting bilingual dictionary from comparable corpus. In J. HOCKENMAIER & S. RIEDEL, Éds., *Proceedings of the Seventeenth Conference on Computational Natural Language Learning*, p. 212–221, Sofia, Bulgaria : Association for Computational Linguistics.

MELAMED I. D. (2001). *Manual Annotation of Translational Equivalence*, In *Empirical Methods for Exploiting Parallel Texts*, p. 65–77.

NGO HO A. K. (2021). *Generative Probabilistic Alignment Models for Words and Subwords : a Systematic Exploration of the Limits and Potentials of Neural Parametrizations*. Theses, Université Paris-Saclay. HAL : tel-03210116.

OCH F. J. & NEY H. (2003). A Systematic Comparison of Various Statistical Alignment Models. *Computational Linguistics*, **29**(1), 19–51.

RADOVANOVIC M., NANOPOULOS A. & IVANOVIC M. (2010). Hubs in space : Popular nearest neighbors in high-dimensional data. *Journal of Machine Learning Research*, **11**, 2487–2531.

SCHWARZ S., PAWLIK M. & AUGSTEN N. (2017). A new perspective on the tree edit distance. In C. BEECKS, F. BORUTTA, P. KRÖGER & T. SEIDL, Éds., *Similarity Search and Applications*, p. 156–170, Cham : Springer International Publishing.

SHI J. & MALIK J. (2000). Normalized cuts and image segmentation. *IEEE Transactions on Pattern Analysis and Machine Intelligence*, **22**(8), 888–905. DOI: 10.1109/34.868688.

SØGAARD A. (2010). Can inversion transduction grammars generate hand alignments. In F. YVON & V. HANSEN, Éds., *Proceedings of the 14th Annual Conference of the European Association for Machine Translation*, Saint Raphaël, France : European Association for Machine Translation.

STAHLBERG F., SAUNDERS D. & BYRNE B. (2018). An operation sequence model for explainable neural machine translation. In T. LINZEN, G. CHRUPAŁA & A. ALISHAHI, Éds., *Proceedings of the 2018 EMNLP Workshop BlackboxNLP : Analyzing and Interpreting Neural Networks for NLP*, p. 175–186, Brussels, Belgium : Association for Computational Linguistics. DOI: 10.18653/v1/W18-5420.

TIEDEMANN J. (2011). *Bitext alignment*. Synthesis lectures on human language technologies. Morgan & Claypool Publishers.

TOUTANOVA K., KLEIN D., MANNING C. D. & SINGER Y. (2003). Feature-rich part-of-speech tagging with a cyclic dependency network. In *Proceedings of the 2003 Human Language Technology Conference of the North American Chapter of the Association for Computational Linguistics*, p. 252–259.

VARGA D., HALÁCSY P., KORNAI A., NAGY V., NÉMETH L. & TRÓN V. (2007). Parallel corpora for medium density languages. In N. NICOLÓV, K. BONTCHEVA, G. ANGELOVA & R. MITKOV, Éds., *Selected papers from RANLP 2005*, p. 247–258 : John Benjamins Publishing Company. DOI : doi:10.1075/cilt.292.32var.
VASWANI A., SHAZEER N., PARMAR N., USZKOREIT J., JONES L., GOMEZ A. N., KAISER L. & POLOSUKHIN I. (2017). Attention is All you Need. In I. GUYON, U. V. LUXBURG, S. BENGIO, H. WALLACH, R. FERGUS, S. VISHWANATHAN & R. GARNETT, Éds., *Advances in Neural Information Processing Systems 30*, NeurIPS, p. 5998–6008 : Curran Associates, Inc.

VÉRONIS J. & LANGLAIS P. (2000). Evaluation of parallel text alignment systems. Text speech and language technology series, p. 369–388. Kluwer Academic Publishers.

WANG W., ZHU D., ALKHOULI T., GAN Z. & NEY H. (2018). Neural hidden Markov model for machine translation. In I. GUREVYCH & Y. MIYAO, Éds., *Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers)*, p. 377–382, Melbourne, Australia : Association for Computational Linguistics. DOI: 10.18653/v1/P18-2060.

WU D. (1997). Stochastic inversion transduction grammars and bilingual parsing of parallel corpora. *Computational Linguistics*, **23**(3), 377–403.

WU Q., NAGATA M., MIAO Z. & TSURUOKA Y. (2024). Word alignment as preference for machine translation. In Y. AL-ONAIZAN, M. BANSAL & Y.-N. CHEN, Éds., *Proceedings of the 2024 Conference on Empirical Methods in Natural Language Processing*, p. 3223–3239, Miami, Florida, USA : Association for Computational Linguistics. DOI: 10.18653/v1/2024.emnlp-main.188.

WU Q., NAGATA M. & TSURUOKA Y. (2023). WSPAlign : Word Alignment Pre-training via Large-Scale Weakly Supervised Span Prediction. In A. ROGERS, J. BOYD-GRABER & N. OKAZAKI, Éds., *Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)*, p. 11084–11099, Toronto, Canada : Association for Computational Linguistics. DOI: 10.18653/v1/2023.acl-long.621.

XU Y. & YVON F. (2016). Novel elicitation and annotation schemes for sentential and sub-sentential alignments of bitexts. In N. C. C. CHAIR), K. CHOUKRI, T. DECLERCK, M. GROBELNIK, B. MAEGAARD, J. MARIANI, A. MORENO, J. ODIJK & S. PIPERIDIS, Éds., *Proceedings of the Ninth Language Resources and Evaluation Conference (LREC 2016)*, p. 10, Portorož, Slovenia : European Language Resources Association (ELRA).

ZHA H., HE X., DING C., SIMON H. & GU M. (2001). Bipartite graph partitioning and data clustering. p. 25–32. DOI: 10.1145/502585.502591.

# 6 Annexe

## A Algorithme d'alignement divisif

Étant donné un couple de phrases (S, T) de longueurs respectives *I* et *J*, l'algorithme divisif demandera au plus $min(I, J)$ étapes de segmentation. Chaque étape de segmentation demande d'évaluer $O(I \times J)$ points de segmentation ; chaque évaluation demandant de sommer $O(I \times J)$ scores d'association lexicales $w(s_i, t_j)$ (cf. section 4.1). Au total, en supposant que $J < \alpha I$, où $\alpha$ est une constante proche de 1, ce qui est une hypothèse raisonnable pour des phrases parallèles, la complexité sera $O(I^5)$. En pré-calculant la table auxiliaire $W_c$ dont le terme général est $W(i, j) = \sum_{i' \leq i, j' \leq j} w(s_i, t_{j'})$, ce qui peut être fait une fois pour toutes avec une complexité $O(I^2)$ par programmation dynamique, l'évaluation de chaque point de segmentation peut être réalisée en temps constant, ce qui ramène la complexité globale à $O(I^3)$.
**Algorithm 1** Algorithme divisif

**procedure** `ALIGN(S, T)`

if length(S) = 1 or length(T) = 1 then

lier chaque mot de S à chaque mot de T

stop

end if

`minNcut` ← 2

(X, Y) ← (S, T), I ← |S|, J ← |T|

**for each** (i, j) ∈ {2, ..., I} × {2, ..., J} **do**

A ← [s₁...sᵢ₋₁], Ā ← [sᵢ...sᵢ]

B ← [t₁...tⱼ₋₁], B̄ ← [sⱼ...sⱼ]

if Ncut(A, B) < minNcut **then**

`minNcut` ← Ncut(A, B)

(X, Y) ← (A, B), (X̄, Ȳ) ← (Ā, B̄),

end if

if Ncut(A, B̄) < minNcut **then**

`minNcut` ← Ncut(A, B̄)

(X, Y) ← (A, B̄), (X̄, Ȳ) ← (Ā, B)

end if

end for

`ALIGN(X, Y)`

`ALIGN(X̄, Ȳ)`

end procedure

## B Versions alternatives de NCut

La normalisation utilisée dans la fonction NCut a été introduite afin d'éviter de choisir des points de coupure produisant des segments déséquilibrés. Cependant, après une analyse des sorties de l'algorithme, il a été observé que, malgré cela, de nombreuses divisions se contentaient de séparer le dernier symbole du reste du segment.

Deux alternatives à la fonction NCut, NCut₂ et NCut₃, issues de (Zha et al., 2001) et (Shi & Malik, 2000), ont alors été testées. Une visualisation du calcul de ces valeurs est dans la Figure 4.

$$ \text{NCut}_2(X, Y) = \frac{\text{cut}(X, Y)}{W(X, Y)} + \frac{\text{cut}(\bar{X}, \bar{Y})}{W(\bar{X}, \bar{Y})} \qquad (2) $$

$$ \text{NCut}_3(X, Y) = \frac{\text{cut}(X, Y)}{W(X, Y) + W(X, \bar{Y})} + \frac{\text{cut}(X, Y)}{W(X, Y) + W(\bar{X}, Y)} \qquad (3) $$

Les résultats obtenus avec NCut₃ étaient très bas par rapport à ceux de NCut (AER=76,0 sur Le Chat Botté). En revanche, les scores de NCut₂ étaient quasiment identiques à ceux de NCut, avec des écarts de seulement 0,3 points d'AER.
<figure><img src="image_6.png" /><figcaption>FIGURE 4 – Visualisation des fonctions NCut, NCut₂ and NCut₃ respectivement.</figcaption></figure>

# C Exploration des méta-paramètres

Les valeurs de paramètres testés :

1. température $\tau$: $\tau \in [2:10]$

2. seuil de similarité minimale $\varepsilon$: $\varepsilon \in [0:0.4]$

3. similarité sim: $sim \in \{\cos, \text{CSLS}\}$

4. nombre de plus proches voisins $k$ (seulement pour CSLS): $k \in [1:4]$

5. modèle utilisée pour calculer les plongements model: $model \in \{\text{mbert}, \text{xlmr}\}$

6. variant de la fonction de normalisation ncut: $ncut \in \{\text{ncut}, \text{ncut2}, \text{ncut3}\}$

<figure><img src="image_7.png" /><figcaption>FIGURE 5 – Résultats de recherche de meilleurs valeurs de F1 score en variant d'abord la température, ensuite le seuil $\varepsilon$ avec la température fixée.</figcaption></figure>

La version initiale :

$$ \tau = 1, \text{sim} = \cos, \varepsilon = 0.0, k = 2, \text{model} = \text{mbert}, \text{ncut} = \text{ncut} $$

La meilleure version trouvée :

$$ \tau = 7, \text{sim} = \text{CSLS}, \varepsilon = 0.008, k = 2, \text{model} = \text{mbert}, \text{ncut} = \text{ncut} $$

On a observé des performances légèrement meilleures avec mbert, néanmoins, les différences entre les deux modèles n'étaient pas très prononcées. Les résultats de recherche d'ε et τ sont dans la Figure 5.