Implémentation des opérations, Algorithme de recherche Greedy
5.2.3 Implémentation des opérations
Nous utilisons les logarithmes (à base deux) pour remplacer les probabilités du score IBM2 (voir équation 5.7) et nous faisons des factorisations afin de simplifier les calculs et éviter certains termes à chaque modification d’alignement.
(5.10)
La première opération que nous avons considérée est la substitution d’un mot par un autre. Cette opération peut se produire à tout endroit dans la traduction en cours. Nous limitons la nature des mots “remplaçables” à ceux qui appartiennent au vocabulaire actif (section 5.1.5) calculé pour chaque mot.
Substituer ()
Pour toutes les positions cibles i=1,…,I
Pour tous les mots e, les traductions du mot fi (parmi le vocabulaire actif).
Substituer le mot ei par e.
Calculer le score de la phrase.
Garder le meilleur score, la position et le mot e correspondants.
Retourner le score, la position et le mot e.
Comme nous l’avons déjà vu, le modèle 2 introduit une probabilité d’alignement P(i|j,J,I) qui est la probabilité qu’un mot anglais en position i soit associé à un mot français en position j.
La fonction permuter () nous permet de permuter deux mots anglais en positions i et k dans la traduction. La probabilité d’alignement P(i|j,J,I) de l’équation (5.10) aide à déterminer la position optimale (au sens du modèle) du mot e dans la traduction.
Permuter ()
Pour toutes les positions cibles i=1,2,…,I-1
Pour toutes les positions cibles k=i+1,…I
Permuter les mots ei et ek
Calculer le score de la phrase.
Garder le meilleur score, les positions correspondantes i et k.
Retourner le score et les positions i et k.
Le modèle 2 ne gère pas la notion de fertilité, mais il recèle indirectement une indication de cette fertilité: le nombre de mots connectés à un mot est un indice de sa fertilité. La fonction suivante essaie les différentes fertilités possibles (1,2,… Max_f) pour les mots anglais dans la phrase proposée comme solution.
Autoriser fertilité ()
Pour toutes les positions cibles i=1,…,I-1
Pour tous les fertilités f=1,..Max_f
Calculer le score de la phrase.
Garder le meilleur score, la position et la fertilité correspondante.
Retourner le score, la position et la fertilité du meilleur alignement.
Il arrive qu’un mot anglais n’ait pas d’équivalent en français. Nous appelons ces mots “mots spurious” ([Brown et al, 1993] ). Nous proposons donc une fonction qui tente d’insérer un mot anglais (parmi les vocabulaires actifs) après chaque mot dans la phrase anglaise proposée.
Insérer spurious ();
Pour toutes les positions cibles i=1,2,…,I
Pour tous les mots e des vocabulaires actifs
Insérer le mot e dans la position i+1;
Calculer le score de la phrase;
Garder le meilleur score, la position et le mot e correspondants;
Retourner le score, la position et le mot e;
5.2.4 Exemple
Nous illustrons sur quelques exemples le déroulement de l’algorithme (les itérations et les opérations).
1-Phrase source : nous avons vu des résultats.
Figure 24: La traduction initiale par alignement un à un des mots à leur traduction la plus probable selon le modèle de transfert.
Dans cet exemple, la solution est atteinte dès l’initialisation : aucune opération n’améliore la traduction.
2- Phrase source: nous avons vu des outils importants
Figure 25: L’initialisation
Le score de l’alignement initial est -68.1119. L’algorithme tente d’appliquer les opérations possibles pour trouver le meilleur alignement. Deux opérations améliorent ce score : substituer (the par some) pour un score –65.217 et permuter (les positions 5 et 6) pour un score de -64.681, la deuxième opération est donc choisie.
Figure 26: Itération 1, une permutation à la position 5 et 6.
À la deuxième itération, seule la substitution (de the par some) améliore le score de l’étape 1.
Figure 27: Itération 2, une substitution à la positin 4.
À l’étape 3, aucune autre transformation n’apporte de meilleur score. La traduction est donc celle résultant de l’étape précédente.
3-Phrase source: nous avons vu des solutions remarquables avec d’autres mesures.
Figure 28: À l’initialisation, le score d’alignement est -133.518.
Les opérations suivantes améliorent l’alignement : Autoriser fertilité 2 pour le mot other avec un score de -115.237, Substituer (the , some) avec un score -129.697 et Permuter(les mots anglais des positions 5 et 6) avec un score –128.362. L’algorithme choisi donc la première des trois.
Figure 29: Itération 1: Le mot (other) à la position 8 est aligné avec 2 mots (d’ autres) (fertilité 2);
À l’itération 2, la substitution du mot the par some amène au meilleur alignement.
Figure 30: Itération 2: Substitution du mot (the) à la position 4 par (some).
À l’itération 3, le meilleur alignement trouvé est d’appliquer une permutation sur les positions 5 et 6.
Figure 31: Itération 3: Permutation des mots à la position 5 et 6.
Enfin, la dernière itération amène à la substitution de things par solutions.
Figure 32: Itération 4: Substitution du mot (things) à la position 6 par (solutions).
