Les techniques de décodage pour la traduction probabiliste

By 21 June 2012

” … logiciel de traduction nous donne donc une autonomie potentielle qu’aucune autre solution ne peut offrir.

La plupart des entreprises doivent diffuser l’information en plusieurs langues. Les collaborateurs doivent travailler sur l’information en plusieurs langues et donc traduire les documents avant de pouvoir les traiter ou les utiliser.

Les services de traduction sont de plus en plus débordés. En offrant aux traducteurs humains des outils pour accélérer leur processus de traduction, ils gagnent du temps sur la première phase de traduction et peuvent se concentrer sur l’exactitude et la précision des termes choisis ….”

Université de Montréal
Faculté des études supérieures
Faculté des arts et des sciences

Département d’Informatique et de Recherche Opérationnelle

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

Ce mémoire intitulé :

Comparaison de deux techniques de décodage pour la traduction probabiliste

Présenté par :
Ali Awdé

A été évalué par un jury composé des personnes suivantes :
François Major (Président – rapporteur)
Philippe Langlais (Directeur de recherche)
Jian Yun Nie (Membre du jury)

Mémoire accepté le 10 juillet 2003

Résumé :
La traduction automatique a connu une révolution majeure ces dernières années dans le domaine du traitement automatique des langues naturelles et de l’autre côté, les besoins en matière de traducteurs automatiques fiables augmentent sans cesse. De ce fait, nous nous sommes intéressés à ce domaine afin de concevoir un traducteur automatique basé sur un modèle statistique.

Premièrement, nous avons entraîné les trois premiers modèles d’alignement proposés par IBM tout en vérifiant l’efficacité de l’outil public GIZA.

Dans une seconde partie, nous avons concentré nos efforts sur la réalisation et la comparaison de décodeurs traductionnels. Un décodeur est un programme capable de traduire une phrase source en une phrase cible étant donné un modèle de traduction. Plus précisément, nous avons développé et comparé deux décodeurs pour les modèles de traduction IBM2. Le premier décodeur implémente une technique de programmation dynamique pour parcourir une partie importante de l’espace de recherche tandis que le second est un algorithme vorace (greedy) qui ne parcourt de manière adhoc qu’un très petit sous-ensemble de l’espace de recherche.

Mots clés: traduction automatique statistique, algorithme de recherche, modèle d’alignement, algorithme vorace, algorithme DP, GIZA.

Abstract :
In previous years, machine translation witnessed a major revolution in the area of natural language processing and the needs for reliable automatic translators increase ceaselessly. Therefore, we interested to bend in this domain to design an automatic translator based on statistical models.

First, we trained the first three alignment models proposed by IBM while verifying at the same time the efficiency of the public toolkit GIZA.

Then, we developed the translation decoder, to which our work is more concentrated. The decoder’s job is translating a source sentence to a target sentence given a model of translation. On the other hand, we developed and compared two decoders for the models of translation IBM2. The first decoder implements a technique of dynamic programming to cover an important part of the research space whereas the second is a greedy algorithm, which covers in an adhoc way only a very small subset of the research space.

Key word: Statistical Machine translation, search algorithm, IBM alignment model, greedy algorithm, DP algorithm, GIZA.

Remerciements
C’est une habitude saine que de remercier au début d’un tel travail tous ceux qui, plus ou moins directement, ont contribué à le rendre possible. C’est avec mon enthousiasme le plus vif et le plus sincère que je voudrais rendre mérite à tous ceux qui à leur manière m’ont aidé à mener à bien ce mémoire.

Je tiens d’abord à témoigner de ma plus profonde gratitude à mon directeur de recherche, monsieur Philippe Langlais. Il a su, par son extrême dévouement, sa gentillesse débordante, sa grande disponibilité et son soutien financier rendre mon travail fort agréable, voire même amusant. De conseils judicieux en mots d’encouragements, il a toujours été d’une aide précieuse et je lui en suis très reconnaissant.

Merci au département d’informatique et de recherche opérationnelle et à la Faculté des études supérieures de m’avoir si généreusement accordé une bourse de rédaction.

Je remercie tous les membres de RALI qui m’ont aidé surtout George, Simona, Michael, Elliott et Luc à évaluer mes résultats. Ainsi que tous les autres membres qui m’ont accueilli de manière très chaleureuse.

Je dois et j’adresse un remerciement tout particulier à mes amis qui me soutiennent toujours et particulièrement : Jacqueline, Hind, Mélanie et Youssef pour leurs aides dans ce mémoire (je ne peux pas nommer tous mes amis!).

Finalement, une attention toute particulière est dirigée vers ma famille, et en particulier mon père et ma mère qui n’ont pas négligé les sacrifices tout au long des mes études. Merci infiniment d’avoir toujours été si attentionnés et dévoués.

Chapitre 1 – Introduction :

La traduction automatique (T.A.) d’une langue humaine à une autre en utilisant les ordinateurs, désignée dans la littérature anglophone sous le terme de « Machine Translation » (M.T.), est un but de l’informatique depuis longtemps et à l’ère d’Internet et du commerce électronique, le besoin de communiquer rapidement dans toutes les langues devient une priorité. La mondialisation du commerce a eu des effets considérables sur l’essor de l’industrie de la langue, et plus particulièrement en traduction où la demande ne cesse de croître.

Les besoins majeurs de la traduction automatique se concentrent principalement sur la traduction de textes scientifiques, techniques, commerciaux, officiels et médicaux. La traduction d’œuvres littéraires reste assez marginale.

1.1 Histoire

La plupart des grands projets de traduction automatique sont nés entre 1958 et 1966 des besoins de traduction à partir du russe engendrés par la guerre froide. Il existe deux générations de systèmes de traduction:

– La première génération de programmes est ce qu’on appelle des systèmes directs. Ils se basent sur des équivalences de termes, traduisent mot à mot à partir de la consultation d’un dictionnaire et ne font aucune analyse. Ce sont des systèmes bilingues (ils traitent une seule paire de langues) et unidirectionnels. Ces systèmes sont limités, mais peuvent s’avérer utiles dans certains cas d’application restreinte (avec un vocabulaire limité).

– La deuxième génération de programmes de traduction regroupe les systèmes de traduction automatique et les systèmes de transfert. Ces programmes de deuxième génération ont un principe plus complexe que celui des systèmes directs. Les systèmes de transfert sont basés sur trois modules: l’analyse du texte en langue source, le transfert, et la génération dans la langue cible. Actuellement, les systèmes à architecture basée sur le transfert sont les plus couramment utilisés. Ils permettent plus facilement d’intégrer une nouvelle langue que les systèmes directs, pour lesquels ajouter une langue revient à créer un nouveau système.

Systran (utilisé entre autres par la Foreign Technology Division de l’armée de l’air américaine) est le système de transfert le plus connu du grand public (c’est le système auquel donne accès le moteur de recherche Altavista). Il est basé principalement sur la consultation de grands dictionnaires bilingues à grande couverture et mis au point à grands renforts des ressources humaines.

La recherche en traduction automatique a été freinée vers 1966, suite à la sortie du rapport ALPAC de la National Science Foundation qui concluait à l’impossibilité d’une traduction automatique de qualité.

Cependant le Canada, en raison de sa politique bilingue a connu une activité faste en traduction automatique. METEO est un système de traduction automatique parmi les premiers systèmes de deuxième génération, il est entré en exploitation le 24 mai 1977 à Montréal. C’est un système très spécifique qui traduit toutes les prévisions météorologiques destinées aux grand public, émises par le service d’environnement atmosphérique du Canada. Une mise à jour de ce système est encore utilisée quotidiennement à cette tâche.

Le milieu des années 1980 a été le témoin de l’essor des mémoires de traduction. Une mémoire de traduction est une base de données contenant un grand nombre de traductions existantes. L’idée des mémoires est de fournir automatiquement à un traducteur des traductions déjà faites à des phrases présentes dans la base. Les mémoires sont de plus souvent capables de proposer des suggestions pour des phrases proches de celles disponibles dans la base. Il existe plusieurs systèmes commerciaux exploitant cette idée (TransSearch , EUROLANG…) qui est très populaire chez les traducteurs professionnels.

Jusqu’à la fin des années quatre-vingt le cadre dominant a été l’approche basée sur les règles linguistiques, mais depuis 1990 ce cadre a été rompu par l’entrée en scène de méthodes et de stratégies nouvelles. Un projet important de IBM a donné naissance à un prototype de traduction CANDIDE [Berger et. al., 1994] introduisant l’approche probabiliste au sein de la communauté linguistique. L’équipe d’IBM a publié les résultats de ses expériences avec un système de traduction purement statistique. La caractéristique principale de cette approche est d’analyser une grande quantité de textes parallèles qui sont les traductions l’un de l’autre (bi-textes) et d’inférer à partir de ces textes les paramètres d’un modèle probabiliste de manière automatique.

1.2 L’importance applicative.

L’importance applicative de la traduction automatique dans notre société est attestée par le développement rapide des technologies. Avec le développement d’Internet, du courrier électronique, des Intranets d’entreprise, des systèmes de gestion de documents, les utilisateurs ont besoin de plus en plus de comprendre immédiatement l’information dans différentes langues.

Par exemple sur Internet près de 60% des sites Web sont en anglais, le reste étant partagé entre des sites espagnols, allemands, français, chinois, etc. L’accès à toute l’information ne peut se faire que si l’on connaît une multitude de langues. Dans ce cas, un logiciel de traduction prend toute sa valeur : c’est un outil qui nous permet non seulement de comprendre un texte écrit dans une langue que nous ne maîtrisons pas, mais surtout de le comprendre instantanément sans avoir à faire appel à une autre personne. Un logiciel de traduction nous donne donc une autonomie potentielle qu’aucune autre solution ne peut offrir.

La plupart des entreprises doivent diffuser l’information en plusieurs langues. Les collaborateurs doivent travailler sur l’information en plusieurs langues et donc traduire les documents avant de pouvoir les traiter ou les utiliser.

Les services de traduction sont de plus en plus débordés. En offrant aux traducteurs humains des outils pour accélérer leur processus de traduction, ils gagnent du temps sur la première phase de traduction et peuvent se concentrer sur l’exactitude et la précision des termes choisis.

Par exemple, pour traduire un contrat, le traducteur doit être juriste et connaître le droit des deux langues pour pouvoir localiser (et pas seulement traduire) des contrats, donc pour pouvoir les adapter en fonction du droit de chaque pays.

1.3 Aperçu sur le contenu de mémoire :

Notre contribution dans ce projet est constituée de trois points principaux :

Premièrement, nous avons entraîné les trois premiers modèles d’alignement proposés par IBM tout en vérifiant l’efficacité de l’outil public GIZA.

Deuxièmement, nous avons concentré nos efforts sur la réalisation et la comparaison de décodeurs traductionnels. Plus précisément, nous avons développé et comparé deux décodeurs pour les modèles de traduction IBM2. Le premier décodeur implémente une technique de programmation dynamique tandis que le second est un algorithme vorace (greedy).

Enfin, nous avons comparé les performances des algorithmes de recherche que nous avons décrits en nous appuyant sur des méthodes d’évaluation de la traduction automatique.

Dans cette partie, nous allons présenter un bref aperçu sur le contenu des différents chapitres de notre mémoire.

Le mémoire contient sept chapitres :

Chapitre 1: Dans ce chapitre, nous parlons de l’état de l’art de la traduction automatique. Plusieurs générations de logiciels de la TA sont énumérés ainsi que l’approche probabiliste de la traduction qui fait l’objet de notre travail. D’autre part, nous présentons les intérêts scientifiques et pratiques de notre recherche.

Chapitre 2: L’approche proposée par [Brown et al, 93] fait le sujet de ce chapitre. En effet, les différents modules d’un engin de traduction probabiliste seront étudiés comme le modèle de langue, le modèle de traduction et le décodage.

Chapitre 3: Nous présentons le package « EGYPT » formé de plusieurs outils : Whittle est destiné à la préparation du corpus pour GIZA, l’outil GIZA dont nous nous servons pour entraîner les modèles de traduction (IBM 1,2 et 3) et enfin, CAIRO utilisé pour visualiser les résultats obtenus par le modèle 3.

Chapitre 4: Toutes les expérimentations ainsi que les résultats de l’entraînement des modèles de traduction obtenus à l’aide de GIZA sont montrés dans ce chapitre. Nous dressons aussi une comparaison entre les différents modèles 1, 2 et 3 ainsi que GIZA et un outil semblable RMTTK conçu au RALI.

Chapitre 5: Les efforts principaux de notre travail se sont concentrés sur le développement de deux décodeurs. En effet, nous expliquons dans cette partie et nous comparons deux techniques de décodage; la programmation dynamique (DP) et l’algorithme vorace (greedy).

Chapitre 6: Dans le chapitre 6, nous décrivons quelques méthodes d’évaluation de la traduction (WER, BLEU et l’évaluation humaine), puis nous comparons les performances de ces deux algorithmes de recherche.

Chapitre 7: Nous concluons et résumons notre travail par les points les plus intéressants dans cette recherche ainsi que les perspectives qui peuvent étendre notre projet dans le futur.

Table des matières :
Résumé
Chapitre 1 : Introduction
1.1. Histoire
1.2. L’importance applicative
1.3. Aperçu sur le contenu de mémoire :
Chapitre 2 : Traduction statistique
2.1. L’idée originale Shanon (canal bruité)
2.2. Le modèle de langue
2.3. Les modèles de traduction
2.3.1. Les alignements
2.3.2. Idée initiale
2.3.3. Les modèles de traduction proposés par IBM
2.3.3.1. Modèle de traduction probabiliste IBM1
2.3.3.2. Modèle de traduction probabiliste IBM2
2.3.3.3. Modèle de traduction probabiliste IBM3
2.4. Conclusion
Chapitre 3 : L’estimation des paramètres
3.1. Le projet EGYPT
3.1.1. Bitexte
3.1.2. Whittle
3.1.3. GIZA
3.1.4. Cairo
3.2. Conclusion
Chapitre 4 : Les expériences avec GIZA
4.1. Préparation du corpus
4.2. Les paramètres
4.3. L’espace mémoire
4.4. Temps d’exécution
4.5. Mesure de la qualité d’un modèle de traduction.
4.6. Quelques exemples et chiffres pour commenter les résultats :
4.6.1. Les alignements des mots
4.6.2. Les probabilités de transfert :
4.6.3. Les fertilités
4.7. Une comparaison entre RMTTK et GIZA. 4.8. Conclusion
Chapitre 5 : Décodage.
5.1. L’algorithme DP
5.1.1. Principe
5.1.2. Description
5.1.3. Filtrage
5.1.4. Implémentation
5.1.5. Les problèmes rencontrés durant l’implémentation
5.1.6. Exemple
5.1.7. Exemples de résultats obtenus
5.2. L’algorithme de recherche “Greedy”. 5.2.1. Principe
5.2.2. Description
5.2.3. Implémentation des opérations
5.2.4. Exemple
5.2.5. Le nombre d’itérations et les temps de traduction. 5.2.6. Exemples de résultats obtenus
5.3. Greedy initialisé par la traduction produite par DP
5.3.1. Exemples de résultats obtenus
Chapitre 6 : Évaluation des résultats
6.1. WER et SER
6.2. BLEU
6.3. Évaluations et comparaison des décodeurs
6.4. Évaluation humaine
6.5. Exemple des traductions évaluées
Chapitre 7 : Conclusion
Bibliographie
Annexe

  1. Traduction statistique : Canal bruité et Modèle de langue
  2. Modèles de traduction: Les alignements et l’idée initiale
  3. Les modèles de traduction statistique proposés par IBM
  4. Paramètres des modèles IBM de traduction probabiliste: EGYPT
  5. Expériences de traduction avec GIZA : Paramètres et Temps
  6. Mesure de la qualité d’un modèle de traduction
  7. Comparaison entre RMTTK et GIZA, logiciels de la traduction
  8. Décodage, l’algorithme DP : principe, description et filtrage
  9. L’algorithme DP : Implémentation et Problèmes rencontrés
  10. Algorithme de recherche “Greedy” : Principe et Description
  11. Implémentation des opérations, Algorithme de recherche Greedy
  12. Le nombre d’itérations et les temps de traduction, Greedy
  13. Évaluation des résultats de la traduction: WER, SER et BLEU
  14. Évaluations humaine et comparaison des décodeurs de traduction
  15. Exemple des traductions évaluées – Techniques de décodage

Table de notation :

ei Le mot anglais à la position i.
eI Une phrase anglaise de I mots.
I La longueur de la phrase anglaise.
i Position en eI, i=0,1,…,I
fj Le mot français de la position j.
fJ Une phrase française de J mots.
J La longueur de la phrase française.
j Position en fJ, j=0,1,…,J
t(ei|fj) Probabilité de transfert
a Alignement
a(i|j,I,J) Probabilité d’alignmement
øi Fertilité du mot ei . (Modèle 3)
n(ø|e) Probabilité de la fertilité. (Modèle 3)

______________________________
Extraits pris du site du Centre Pluridisciplinaire de Sémio linguistique Textuelle, Université Toulouse-Le Mirail http://www.univ-tlse2.fr/gril/
babelfish.altavista.com/
www.tsrali.com/. TransSearch, système conçu au sein de Laboratoire RALI à l’université de Montréal.
the European Languages Centre, http://www.eurolang.com
www-2.cs.cmu.edu/afs/cs/user/aberger/www/html/candide.html
www.itu.int/mlds/briefingpaper/wipo/french/annexeI-fr.html