Algorithme de recherche “Greedy” : Principe et Description
5.2 L’algorithme de recherche “Greedy”
5.2.1 Principe
L’idée de l’algorithme “greedy” est d’appliquer un ensemble d’opérations en vu d’améliorer, au sens des modèles, une traduction initiale. L’idée a été proposée par [Germann U. et al, 2001] dans le cadre d’un modèle IBM4.
Cette idée sacrifie l’exhaustivité de l’exploration faite par l’algorithme DP avec un pari que la solution trouvée ne s’éloignera pas trop de la solution optimale (au sens des modèles).
On peut argumenter que cet algorithme de recherche est plus souple à adapter à un nouveau modèle que les formulations par programmation dynamique. Il suffit en effet de redéfinir l’ensemble des opérations à considérer.
L’algorithme greedy tente de manière systématique toutes les opérations partout où elles s’appliquent et retient l’opération et son emplacement qui améliorent plus la probabilité P(e|f). On itère alors le processus sur la nouvelle solution jusqu’à ce qu’aucune application d’une opération n’améliore la solution courante.
Plus formellement,
Soit f la phrase source, e sa traduction initiale et a l’alignement associé.
Fonction A
o 
O, l’ensemble des opérations valides
c, le contexte d’application de o.
Soit (e’,a’)=l’application de (o,c,(e,a)).
Si P(e’,a’|f)>P(e,a|f).
Max_o=o
Max_c=c
Max_s=P(e’,a’|f)
Fin de A.
Initialisation :
e’ est la première solution.
a’ est l’alignement entre f et e’.
Do
a a’ , e e’
Max_S =P(e,a|f)
Fonction A.
While (Max_s !=P(e,a|f))
e’ est la traduction de f avec la probabilité Max_s.
Dans notre cas, P(e,a|f) est calculé à l’aide d’un modèle de traduction IBM2 et un modèle trigramme (les même modèles que nous avons utilisés dans l’algorithme DP.)
Outre sa rapidité de convergence (vers une solution locale), l’algorithme greedy est peu consommateur de mémoire (en comparaison avec l’algorithme précédent). En contre-partie, il est très possible que la solution trouvée par l’algorithme ne soit pas la solution optimale au sens des modèles mis en jeu.
5.2.2 Description
Les hypothèses sont stockées dans une table de deux dimensions (I×4 cases) où I est la longueur de la phrase française et 4 est le nombre de paramètres de chacune des hypothèses (mot, position du mot source, fertilité, score).
On initialise l’algorithme avec une traduction simplifiée où chaque mot français fi est aligné avec le mot anglais ei le plus probable au sens du modèle de transfert 
(les valeurs de P(ei|fi) sont obtenues par l’application de Bayes).
Une fois l’alignement initial créé, le décodeur tente de l’améliorer en cherchant l’alignement le plus probable par l’application d’opérations parmi l’ensemble : substitution, insertion, permutation ou suppression. L’algorithme itère ces opérations sur toutes les hypothèses de l’alignement actuel.
À chaque itération, le décodeur choisit le meilleur alignement jusqu’à ce qu’aucune opération ne puisse être appliquée avec un gain. Ces opérations que nous décrivions dans la section suivante, ont été choisies pour deux raisons :
Elles sont tout d’abord peu coûteuses au niveau du temps de calcul, elles possèdent de plus la propriété souhaitée de perturber de manière non triviale les alignements considérés, ce qui offre à l’algorithme d’étudier divers types d’alignements.
À la limite, l’algorithme DP que nous avons vu possède en pratique ce problème car pour réduire les temps de calculs, nous filtrons une portion non négligeable de l’espace de recherche.
