Décodage, l’algorithme DP : principe, description et filtrage

By 24 June 2012

Décodage – Chapitre 5 :

Nous avons abordé dans les sections précédentes le problème de l’entraînement des modèles. Nous nous concentrons dans ce chapitre sur le troisième problème de la traduction statistique « le décodage ». Nous expérimentons, ici des décodeurs traduisant du français vers l’anglais, bien qu’en principe, les modèles utilisés sont indépendants de la paire de langues.

Dans la traduction automatique probabiliste, le but d’un décodeur est de chercher la phrase anglaise eI=e1…eI la plus probable étant donnée une phrase source française fJ=f1,…,fJ et des modèles (modèle de langue et modèle de traduction) où I et ei i[1,I] sont des inconnus (figure 18).
L’architecture de la traduction probabiliste
Figure 18: L’architecture de la traduction probabiliste [Nießen et al. 1998].

Chaque phrase anglaise est considérée comme une traduction possible de la phrase source française. On assigne à chaque paire de phrases (eI,fJ) une probabilité P(eI|fJ). Il faut chercher un Iopt optimal et de même une phrase êIopt qui maximisent P(eI|fJ).

Revenons aux équations et modèles vus dans le chapitre 2, (2.1 et 2.2) :
équations et modèles(‎5.1)

Bien qu’il soit possible d’écrire un décodeur pour le modèle 3, nous avons concentré nos efforts sur l’écriture de deux décodeurs (DP et Greedy et nous les présentons plus tard dans ce chapitre) pour le modèle 2. Ce modèle est en effet plus simple et le décodeur DP résultant de ce modèle est donc plus rapide.

L’équation du modèle 2 donnée par [Brown 1993] est la suivante :
L’équation du modèle 2(‎5.2)

Comme nous l’avons déjà mentionné dans les chapitres précédents, nous utilisons un modèle trigramme pour construire nos décodeurs, l’équation de la maximisation (5.1) devient alors :
modèle trigramme( ‎5.3)

Un modèle de longueur est également mis en jeu tel que spécifié dans l’équation (5.3). Dans cette étude nous avons fait l’hypothèse que la longueur (comptée en mots) d’une phrase française, traduction d’une phrase anglaise était normalement distribuée.

Notez que dans la dernière équation, la somme sur tous les alignements a été remplacée par une maximisation. Ceci correspond à une hypothèse sous-jacente (souvent faite) que la probabilité de l’alignement le plus probable domine la somme. On parle souvent de maximum approximation. Cette simplification permet de factoriser certains calculs et diminue donc la complexité calculatoire de décodeur. Il a en effet été démontré que l’opération de maximisation de l’équation 5.1 est NP-complète [Knight et al, 1999].

Dans ce chapitre, on présente et on compare deux algorithmes de recherche :
1- Le premier est une technique de programmation dynamique (DP) pour parcourir une partie importante de l’espace de recherche.
2- Le second est un algorithme greedy qui ne parcours de manière « adhoc » qu’un très petit sous-ensemble de l’espace de recherche.

La comparaison entre les deux méthodes de décodage étant notre première préoccupation.

5.1 L’algorithme DP
5.1.1 Principe

Plusieurs décodeurs DP ont été proposés dans la littérature. Par exemple, [Tillmann et al., 1997] proposent un décodage où les alignements considérés obéissent à une hypothèse markovienne d’ordre 1: (l’alignement d’un mot au temps i est conditionné par l’alignement au temps i-1). Les auteurs font de plus l’hypothèse que les alignements sont monotones (pas de croisements). Sous ces contraintes, leur algorithme est capable de proposer de manière efficace une traduction.

Ce type d’algorithme contraint les traductions produites à être littérales, ce qui n’est en pratique pas souhaitable. C’est pour cela que [Nießen et al. 1998] ont proposé un décodeur où de telles hypothèses ne sont pas faites. Le prix à payer étant une complexité accrue, nous reviendrons sur ce point plus tard.

Ce décodeur basé sur la programmation dynamique examine les mots anglais séquentiellement. Pour qu’une phrase anglaise soit considérée comme une traduction complète de la phrase française, il faut qu’elle couvre toutes les positions françaises. L’idée de cet algorithme est d’étendre progressivement (mot à mot) les hypothèses de traduction, tout en couvrant progressivement les positions de la phrase française. Chaque mot français peut générer au plus un mot anglais à n’importe quelle position dans la phrase anglaise.

Nous étendons l’algorithme proposé par [Nießen et al. 1998] pour qu’un modèle trigramme soit utilisé à la place du modèle bigramme initial.

5.1.2 Description

Cet algorithme de recherche interprète la notion d’alignement de mots comme suit: chaque image052 position i en est assignée à une position bi=j en image054.

À chaque position i de, chaque mot du vocabulaire actif anglais peut être inséré. De plus, on permet qu’un mot anglais ei soit aligné avec l mots français consécutifs (une sorte de fertilité non modélisée). Dans la plupart de cas, la fertilité optimale est égale à 1. Il est possible que le mot ei ait la fertilité zéro, ce qui signifie que ce mot ne corresponde directement à aucun mot français (spurious).

D’un point de vue formel, ce que nous cherchons à optimiser se décrit par:
formel
(‎5.4)

Où l désigne la fertilité du mot ei (on considère dans nos expériences une fertilité maximale de 3 mots français pour un mot anglais).

Cette équation ne garantie pas que toutes les positions sources sont couvertes. En d’autres termes, on doit forcer l’algorithme à couvrir toutes les positions françaises. [Nießen et al. 1998] proposent plusieurs stratégies pour résoudre ce problème (comme par exemple l’introduction d’une pénalité pour chaque position française non couverte) mais ils suggèrent une solution basée sur l’introduction d’un nouveau paramètre dans le critère de DP. Soit QI(c,i,j,e) la probabilité du meilleur chemin arrivant en position i dans eI, en position j dans fJ et tel que ei=e et c positions sources ont été couvertes. (Pour tous les détails voir [Nießen et al. 1998])

À noter que les coordonnées d’une hypothèse sont déterminées par les quatre paramètres (c,i,j,e). De ce fait, l’espace peut-être codé par une matrice à quatre dimensions; chaque item dans cet espace de recherche contenant des informations de chaînage arrière (backtracking) ainsi que le score de l’hypothèse associée.

Cette quantité QI(c,i,j,e) est définie récursivement : [Nießen et al. 1998] présentent deux cas :

Cas simple: le mot ei n’a pas de correspondant dans le texte français (skip).
le texte français(‎5.5)

On recherche dans la table la meilleure façon d’arriver à (e,i,j) depuis une cellule précédante.

Cas général : Dans l’équation (5.3), chaque position j de la phrase française est exactement alignée à une position anglaise i. De cela, si ei est associé à l mots français (l>0), on vérifie qu’aucune de ces positions françaises ne sont déjà couvertes : on définit une fonction v(c,l,j’,j,e’) qui retourne 1 si les l positions de fk à fj sont libres dans la phrase française; 0 sinon.
image057
image058
image059(‎5.6)

En gros, on cherche la meilleure fertilité, et la meilleure position française libre (via v).

Note : les choix l, j’ et e’ sont mémorisés pour pouvoir à la fin reconstruire la traduction « optimale ».

Nous avons alors tous les ingrédients de notre récursion:
image060(‎5.7)

La meilleure traduction qu’on peut trouver est en maximisant la longueur de la phrase anglaise I et recouvrant toutes les positions françaises J. Ainsi :
image061(‎5.8)

Chaque traduction possible a un score (le score de dernier mot de la phrase) calculé par l’accumulation des scores des items précédents (factorisation afin de réduire le temps de calcul). On choisit alors la phrase ayant le meilleur score et couvrant toutes les positions sources. La traduction est alors déterminée par le retour en arrière (backtracking).

5.1.3 Filtrage

Si nous parcourons l’ensemble de l’espace de recherche, nous trouvons l’alignement optimal au sens des modèles. Cependant, puisque le nombre des hypothèses augmente exponentiellement avec la longueur de la phrase, il est impraticable d’énumérer toutes les hypothèses possibles. On sacrifie alors l’optimalité pour la rapidité.

En effet, La figure 19 montre que la longueur de la phrase a une influence importante sur le temps de traduction. D’après [Nießen et al. 1998], la complexité de l’algorithme est:

où |ε| est la taille du vocabulaire cible, J est la longueur de la phrase source, Imax est la longueur la plus grande envisagée pour la phrase cible.

[Nießen et al. 1998] proposent cependant des optimisations qui permettent d’accélérer l’algorithme au détriment de la “souplesse” de son critère pour une complexité finale en .
L’accroissement du temps de la traduction avec la longueur de la phrase
Figure 19: L’accroissement du temps de la traduction avec la longueur de la phrase.

Tout d’abord on peut limiter les couvertures sources par deux bornes majorante et minorante pour chaque niveau (ligne i) dans la matrice. En d’autres termes, on peut borner la recherche du meilleur l et du meilleur k (de l’équation 5.4 ) par un faisceau [cmin(i), cmax(i)] centré autour de la diagonale que l’on observerait si l’ordre des mots dans les deux phrases était le même;

Avec
image067,
image068

Où r est une constante (fixée à 3 dans nos expériences et qui représente un degré de tolérance à cette hypothèse de synchronisation des traductions.

Dans l’équation (5.4), on maximise sur I, la longueur de la traduction produite. En pratique, ça signifie que l’on recommence la programmation dynamique depuis le début, car le critère dépend de I par les probabilités d’alignement P(i|k,J,I). C’est pratiquement trop lourd pour notre algorithme qui doit être rapide. Ils proposent de remplacer dans le critère la valeur exacte de I par son estimée (autrement dit, on retire une dépendance directe à I dans les probabilités d’alignement pour introduire l’estimée de I): P(i|k,J,Imax). Dans nos expériences, nous estimons Imax par |I + log(I+1)|.

Même après ces contraintes sur l’algorithme, dès que la phrase française arrive à une longueur de 7 mots, le nombre de mots dans le vocabulaire actif devient trop important et impose un filtrage.

Au moins trois options de filtrage sont possibles en prenant compte de :
1. Le nombre de mots anglais associés à chaque mot source français (N).
2. Le score de l’hypothèse et les probabilités (transfert et alignement).
3. Les positions de mots sources et ses traductions.

Les tableaux 11 et 12 représentent une illustration en deux dimensions de la table de recherche, chaque case de tableau contient au moins N items. On peut remarquer sur les tableaux (11 et 12) l’effet de la contrainte sur le nombre de mots associés à chaque mot français. Après l’expérience, on trouve qu’à partir de 7 mots anglais associés, les résultats restent acceptables en terme de performance et de temps de calcul.

Les positions des mots anglais 5 348 348 348 Les positions des mots anglais 5 690 690 690
4 348 348 348 4 690 690 690
3 348 348 348 3 690 690 690
2 348 282 216 2 690 560 430
1 150 100 50 1 300 200 100
nous avons vu nous avons vu
Les mots français Les mots français
Tableau 9: Une phrase de 3 mots avec 50 mots anglais associés à chaque mot français, 116 vocabulaires actifs. Tableau 10: Une phrase de 3 mots avec 100 mots anglais associés à chaque mot français, 230 vocabulaires actifs.

Une grande taille du vocabulaire actif |ε| amène à un nombre important d’hypothèses. Le grand nombre d’hypothèses augmente l’espace de mémoire occupé par la table de recherche, ce qui augmente les risques de saturation de la mémoire.

Comme on l’a déjà mentionné, la taille du vocabulaire actif |ε| introduit dans la complexité de l’algorithme (), de ce fait le temps de traduction augmente exponentiellement avec la taille du vocabulaire actif (figure 20).

L’accroissement de temps avec la taille de l’ensemble de vocabulaire actif
Figure 20: L’accroissement de temps avec la taille de l’ensemble de vocabulaire actif (une phrase de 6 mots français et sa traduction de 6 mots anglais).

Des critères additionnels sur les scores ont également été ajoutés. On ne considère que les hypothèses ayant des scores supérieurs à un seuil : (par exemple le score maximal multiplié par un nombre BETA). Dans certains cas, on perd des bonnes hypothèses et cela influence les résultats.

Un filtrage des probabilités de transfert P(fj|ei) et d’alignements P(i|j,J,I) est aussi utile. On ignore toutes les probabilités inférieures à un certain seuil (par exemple Pr>10-3).

Evidemment, en relaxant les contraintes sur les positions de mots (tous les positions sont possibles avec une probabilité d’alignement P(i|j,J,I)), le nombre d’alignements est important ((I+1)J). Afin de réduire ce nombre, on introduit des contraintes sur les positions de mots. Le mot français de la position i peut se connecter aux mots anglais situés entre deux bornes inférieures et supérieures (par exemple [i-3;i+3] ). Nous vérifierons l’impact des filtrages dans la section 5.3.

Lire le mémoire complet ==> (Les techniques de décodage pour la traduction probabiliste)
Mémoire présenté à la Faculté des études supérieures en vue de l’obtention du grade de Maître ès sciences (M.Sc) en informatique
Université de Montréal – Département d’Informatique et de Recherche Opérationnelle

______________________________
Une description mathématique de l’algorithme est dans [Nießen et al. 1998].
Les nombres notés dans les cases de ces deux tableaux représentent les nombres des items