Informatique et recherche
opérationnelle
IFT6010

Intelligence Artificielle
Traitement statistique des langues naturelles

Hiver 2003


Accueil

Cours après cours

Devoirs

Horaires et locaux

Au sujet du
livre de cours

Consultez vos notes

Liens utiles

Contact

Les séminaires
RALI/LLI

TP2 Alignement bilingue de mots

[Cahier des charges] | [Programme] | [Rapport] | [Ressources]

Cahier des charges

Le but de ce travail est de vous faire utiliser les modèles de traduction IBM1, 2 et 3 afin d'aligner des mots dans des paires de phrases alignées.

Vous devez remettre:

  • un programme aligne qui permet de réaliser l'alignement de mots dans des corpus alignés au niveau de la phrase. En fait, je vous demande de remettre les codes sources dont dépend le programme aligne qui vous est demandé, ainsi qu'un fichier Makefile qui me permettra de compiler (au besoin) votre projet à l'aide de la commande Make
  • un rapport (d'au plus quelques pages) au format postscript (ou pdf ou html) décrivant les expérimentations que vous avez effectuées (faites ressortir les points les plus intéressants de votre travail). Je vous encourage à utiliser LaTeX pour rédiger votre rapport.
Le tout est à remettre par la commande remise sur le compte pift6010, sous la référence TP2.

Prenez note que je compilerai (le cas échéant) et exécuterai vos programmes sous l'environnement Linux qui est le votre au département à l'aide des outils disponibles au département. Je ne considererai pas de code qui tourne (exclusivement) sous d'autres systèmes, ou à l'aide d'outils auxquels je n'ai pas accès.

Programme

Programme aligne

Votre programme doit respecter le sysnopsis suivant (vous pouvez ajouter des options)

Synopsys: aligne modele type fichier-source fichier-cible où:

  • modele est le nom de base (basename) du modèle qui servira à l'alignement. Voir la section ressources pour plus d'information sur la manière dont les modèles vous sont donnés.
  • type est un entier (1, 2 ou 3) qui spécifie le type du modèle (1 pour IBM1, 2 pour IBM2 et 3 pour IBM3). Voir la section ressources pour plus d'information sur la manière dont les modèles vous sont donnés.
  • fichier-source est le texte source. On supposera le format suivant: une ligne par phrase. Chaque ligne commence et termine par un tag s. Entre ces deux tags, les mots de la phrase sont séparés par un espace. Le tag ouvrant est de plus accompagné du numéro de la phrase. Voici un exemple de texte source bitexte2.e
  • fichier-cible est le texte cible au même format que le fichier source. On suppose dans ce TP que les fichiers source et cible sont synchronisés. C'est à dire que la première phrase du texte source est alignée (traduite par) la première phrase du fichier cible, etc. Voici le texte cible correspondant au texte source précédant bitexte2.f
et doit implémenter (idéalement) les alignements de viterbi pour les modèles 1 2 et 3 vus en cours (pour ceux qui ne viennent pas en cours, ou qui dorment dès la deuxième phrase que je prononce, relire les acétates du jeu de transparents traduc acétates 105-117). Les alignements de viterbi pour les deux premiers modèles sont triviaux (prise de maximum indépendante pour chaque mot cible); pour l'alignement de viterbi avec le modèle 3, une métode itérative de type hill climbing est à coder.

Rien ne vous interdit de tenter également d'autres stratégies d'alignement que l'approche viterbi (à discuter en cours).

Format de sortie de aligne

Les alignements produits par votre aligneur doivent respecter le format qui suit si vous voulez pouvoir mesurer la qualité de vos alignements avec la commande eval.

Chaque ligne décrit une paire de mots (source,cible) alignée et contient dans l'ordre: 1) le numéro de la phrase correspondant à la paire décrite, 2) l'indice dans la phrase source du mot source impliqué (premier mot = indice 1, etc.), 3) l'indice dans la phrase cible du mot cible impliqué (premier mot cible = indice 1, etc). Le quatrième champ est quant à lui facultatif et contient soit le caractère S pour indiquer une paire sure, soit le caractère P pour indiquer que la paire est possible. Si le quatrième champ n'est pas présent, alors S est implicitement assumé lors de l'évaluation par la commande eval.

Note: Toutes les paires doivent être marquées. En particulier, si un mot source n'est pas aligné, alors la position cible 0 doit lui être associée dans le fichier produit. De la même manière, si un mot cible n'est aligné à aucun mot cible, alors la position source 0 doit lui être associée.

Voici un exemple d'extrait d'alignement où les deux fichiers alignés sont bitexte2.e et bitexte2.f:

1001 1 1 S
1001 2 2 P
1001 3 3 P
1001 3 4 P
  • La première ligne indique que le premier mot (each) de la phrase anglaise numéro 1001 est aligné avec le premier mot (chacun) de la phrase française de même numéro. C'est une paire que l'aligneur considère comme sure.
  • La deuxième ligne indique que le deuxième mot (of) de la phrase anglaise numéro 1001 est aligné avec le deuxième mot (en) de la phrase française de même numéro. C'est une paire que l'aligneur considère comme possible.
  • La troisième ligne indique que le troisième mot (them) de la phrase anglaise numéro 1001 est aligné avec le troisième mot (lui) de la phrase française de même numéro. C'est une paire que l'aligneur considère comme possible.
  • La quatrième ligne indique que le troisième mot (them) de la phrase anglaise numéro 1001 est aligné au quatrième mot (-) de la phrase française de même numéro. C'est une paire que l'aligneur considère comme possible.

Rapport

Vous devez remettre un rapport qui explique brièvement ce que vous avez implanté et expérimenté. Je m'attends par exemple à lire vos choix de structures pour le codage des modèles (influence sur les temps de chargement des paramètres, etc.)

C'est dans ce rapport que devraient figurer toutes les informations qui feraient ressortir des points particuliers que vous avez expérimentés. Voici à titre indicatif quelques questions que vous pourriez vous poser en faisant ce travail et que vous pourriez avoir envie d'expérimenter (et donc de décrire dans votre rapport):

  • Qui des modèles IBM1 2 ou 3 donne les meilleurs résultats d'alignement, pourquoi ?
  • Que se produit-il si je modifie les distributions comme ca ?
  • Que veut dire un bon algorithme d'alignement de mots ?
  • Que se passe-t-il lorsque je suis en présence de mots inconnus (du modèle) ? Quelle influence ces mots ont-ils sur les performances de mon aligneur ?
  • Rien ne m'interdit d'envisager d'autres stratégies d'alignement que l'alignement de viterbi. Quelle performance puis-je obtenir avec d'autres stratégies d'alignement ?
  • etc.

Ressources

Avant garde: Les fichiers décrits ci-bas sont assez gros, aussi préférerez-vous peut-être les télécharger en une seule fois à l'aide de ce fichier taré/gzipé. L'ensemble des ressources qui vous sont fournies ici est au format ASCII.

Les modèles de traduction

Trois modèles ont été entraînés pour vous avec un package du domaine public sur une petite portion (9000 phrases) des textes des débats parlementaires canadiens (Hansard). Ces modèles ont tous été entraînés dans le sens anglais->français, avec un même vocabulaire source (anglais) de 4872 formes et cible (français) de 5909 formes. Ces vocabulaires respectifs sont consignés dans les deux fichiers: 9000-e2f-src.v (le vocabulaire source) et 9000-e2f-tgt.v (le vocabulaire cible). Ils ont tous les deux le même format: une ligne par mot. La première colonne est le code du mot, la deuxième colonne est le mot, la troisième colonne est fréquence du mot dans le corpus d'entraînement (vous n'aurez pas nécessairement besoin de cette dernière information). Voici les 3 premières lignes du vocabulaire source:
1 UNK 2935
2 the 10293
3 . 7714
Cet exemple indique que UNK (un mot spécial qui représente tout mot inconnu) est de code 1 et de fréquence 2935, que le mot the (de fréquence 10293) a le code 2 et que le mot . (de fréquence 7714) a le code 3.

Les distributions de chaque modèle qui vous est donné sont exprimées à l'aide des codes des mots plutôt que par les mots eux-mêmes (fichiers plus "compacts"). En voici maintenant un descriptif:

  • Modèle1 - est un modèle de type ibm1 et est donc caractérisé par le fichier des distributions de transfert 9000-e2f-ibm1.t
  • Modèle2 - est un modèle de type ibm3 et est donc caractérisé par le fichier des distributions de transfert 9000-e2f-ibm2.t et le fichier des distributions d'alignement 9000-e2f-ibm2.a
  • Modèle3 - est un modèle de type ibm3 et est donc caractérisé par le fichier des distributions de transfert 9000-e2f-ibm3.t, le fichier des distributions de distorsion 9000-e2f-ibm3.d, le fichier des distributions de fertilité 9000-e2f-ibm3.f et le fichier indiquant la valeur de p0 9000-e2f-ibm3.p0, la probabilité qu'un "vrai" mot cible généré n'engendre pas un mot "spurious".

Format:

  • distributions de transfert - une ligne par paramètre: colonne 1=code source, colonne 2=code cible, colonne 3=t(cible|source). Voici un exemple de distribution:
    3 2 0.992239       // t(. |.=3) = 0.992239
    3 4 2.14781e-06    // t(, |.=3) = 2.14781e-06
    3 46 0.0023407     // t(? |.=3) = 0.0023407
    3 138 0.00466965   // t(! |.=3) = 0.00466965
    3 140 0.000130889  // t(là |.=3) = 0.000130889
    3 4113 2.69285e-05 // t(exagéré |.=3) = 2.69285e-05
    
    Le fait que les distributions ne somment pas exactement à 1 (0.999409 dans l'exemple) est dû aux erreurs d'arrondis (vous pouvez laisser comme ça ou bien renormaliser après lecture).

  • distributions d'alignement - une ligne par paramètre: colonne 1=la position source (ps), colonne 2=la position cible (pc), colonne 3=la longueur source (LS), colonne 4=la longueur cible (LC), colonne 5= a(ps|pc,LS,LC). Voici un exemple de distribution:
    1 2 5 4 0.0208145 // a(1|2,5,4)
    2 2 5 4 0.264396  // a(2|2,5,4)
    3 2 5 4 0.479769  // a(3|2,5,4)
    4 2 5 4 0.235018  // a(4|2,5,4)
    
    Le fait que les distributions ne somment pas exactement à 1 (0.999998 dans l'exemple) est dû aux erreurs d'arrondis (vous pouvez laisser comme ça ou bien renormaliser après lecture). Toutes les positions sources ne sont pas nécessairement associées à toutes les positions cibles.

  • distributions de distorsion - une ligne par paramètre: colonne 1=la position cible (pc), colonne 2=la position source (ps), colonne 3=la longueur source (LS), colonne 4=la longueur cible (LC), colonne 5= d(pc|ps,LS,LC). Voici un exemple de distribution:
    1 2 4 5 0.0362579 // d(1|2,4,5)
    2 2 4 5 0.409095  // d(1|2,4,5)
    3 2 4 5 0.414227  // d(1|2,4,5)
    4 2 4 5 0.0685614 // d(1|2,4,5)
    5 2 4 5 0.0718584 // d(1|2,4,5)
    
    Le fait que les distributions ne somment pas exactement à 1 (ici elle somme à 1) est dû aux erreurs d'arrondis (vous pouvez laisser comme ça ou bien renormaliser après lecture). Toutes les positions cibles ne sont pas nécessairement associées à toutes les positions sources.

  • distributions de fertilité - une ligne par mot source: colonne 1=le code source, colonne i+1= n(i|source), la probabilité que le mot source ait une fertilité égale à i. On admettra ici que les fertilités ne peuvent pas dépasser 9 (il y a donc 10 valeurs de fertilité allant de 0 à 9). Voici un extrait d'un fichier de fertilités où la première ligne indique que le mot december a une probabilité de 0.927646 de générer un mot cible, et de 0.0723539 d'en générer 2.
    432 0 0.927646 0.0723539 0 0 0 0 0 0 0        // december
    433 0.127965 0.806917 0.0651185 0 0 0 0 0 0 0 // essential
    434 0.379882 0.529978 0.0901399 0 0 0 0 0 0 0 // level
    

  • valeur de p0 - une ligne qui contient la valeur de p0

Note 1: les distributions de transfert entre chaque modèle sont interchangeables. Chaque itération d'entraînement tend à réduire les probabilités de transfert qui contribuent le moins au calcul de vraisemblance du corpus d'entraînement; et les paramètres de probabilité faible sont éliminés (ici à l'aide d'un seuil fixe) après chaque itération. Ceci explique que les distributions de transfert du modèle 3 contiennent moins de paramètres que celles du modèle 2 (à fortiori du modèle 1).

Note 2: les fichiers de distributions d'alignement et de distribution sont assez volumineux. En regardant ces fichiers vous vous rendrez compte qu'il n'est pas nécéssaire de coder en memoire tous les paramètres. Beaucoup sont en effet simplement l'expression d'une équiprobabilité (c'est par exemple le cas de la distribution a(s|9 10 20) dans 9000-e2f-ibm2.a où toutes les probabilités sont de 0.0909091 cad 1/11).

Note 3: on admettra dans ce TP les conventions de nom suivantes: un modèle est spécifié par son nom de base basename (ici 9000-e2f) et son type type (1 2 ou 3). Les vocabulaires sources et cibles sont nommés basename-src.v et basename-tgt.v; les fichiers de transfert sont nommés basename-ibmtype.t; les fichiers d'alignements sont nommés basename-ibmtype.a (ne s'appliquent qu'aux modèles de type 2); les fichiers de distorsion sont nommés basename-ibmtype.d (ne s'appliquent qu'aux modèles de type 3); enfin les fichiers de fertilité sont nommés basename-ibmtype.f (ne s'appliquent qu'aux modèles de type 3). Cette convention sur les noms vous permet de n'avoir qu'à spécifier le nom de base et le type du modèle pour aller lire l'ensemble des distributions nécéssaires. Il est possible que je change les fichiers de distribution lors des tests de vos programmes, aussi je suivrai cette convention (-> ne pas "hardcoder" le nom des fichiers dans votre source).

Des fichiers de test

Voici deux bitextes sur lesquels vous pouvez travailler, tous les deux sont extraits du hansard. Pour le second, un alignement fait à la main existe qui vous permettra de mesurer vos progrès via le programme eval décrit plus bas.

Commande eval

Un programme disponible sur le compte pift6010 vous permet d'évaluer la qualité des alignements que vous proposez sur le corpus bitexte2 pour autant que votre programme suive à la lettre le format des alignements décrit plus haut.

La syntaxe de cette commande est simple:

~pift6010/bin/eval candidat [candidat..]
où au moins un alignement candidat est fourni à la ligne de commande. Voici à titre indicatif trois alignements (ali1,ali2,ali3) produits pour bitexte2 et la commande qui permet de les évaluer.
~pift6010/bin/eval ali1 ali2 ali3
Et la sortie de la commande:
candidat             P          R         Ps         Rs        AER
   ali-1    0.52704577 0.21300448 0.34119279 0.72781065 0.40887630
   ali-2    0.51317614 0.20739910 0.31622746 0.67455621 0.43531632
   ali-3    0.40915395 0.16535874 0.24965326 0.53254438 0.55146366
Les détails des métriques sont indiqués dans le jeu de transparents traduc (à la suite des acétates expliquant ce que vous devez coder). En gros, précisions et rappels sur les alignements surs et possibles (plus c'est élévé, mieux c'est), et AER, un taux d'erreur (plus c'est faible, mieux c'est). ali3 est donc moins bon que ali2 qui est légèrement meilleur que ali1.

[Cahier des charges] | [Programme] | [Rapport] | [Ressources]

Tip: deux difficultés dans ce TP: 1) lire et coder en mémoire les distributions qui vous sont données, 2) écrire les algorithmes d'alignement. La première tâche est à priori simple, mais en pratique, des choix de structures inadaptés peuvent rendre vos programmes particulièrement lents (et/ou gourmands en mémoire). La seconde tâche est quant à elle sans problème pour les alignements de viterbi 1 et 2. Pour les alignements viterbi 3, là encore, vos choix de codage peuvent grandement influer sur les temps de traitement. Si vous avez des questions, n'hésitez pas à me contacter.



Dernière mise à jour : Thu Apr 17 17:26:26 EDT 2003
felipe@iro.umontreal.ca