Searching for alignments in SMT. A novel approach based on an Estimation of Distribution Algorithm

Proceedings of the Workshop on Statistical Machine Translation, pages 47–54, New York City, June 2006. c⃝2006 Association for Computational Linguistics Searching for alignments in SMT. A novel approach based on an Estimation of Distribution Algorithm ∗ Luis Rodr´ıguez, Ismael Garc´ıa-Varea, Jos´e A. G´amez Departamento de Sistemas Inform´aticos Universidad de Castilla-La Mancha luisr@dsi.uclm.es, ivarea@dsi.uclm.es, jgamez@dsi.uclm.es Abstract In statistical machine translation, an align- ment defines a mapping between the words in the source and in the target sen- tence. Alignments are used, on the one hand, to train the statistical models and, on the other, during the decoding process to link the words in the source sentence to the words in the partial hypotheses generated. In both cases, the quality of the alignments is crucial for the success of the translation process. In this paper, we propose an al- gorithm based on an Estimation of Dis- tribution Algorithm for computing align- ments between two sentences in a paral- lel corpus. This algorithm has been tested on different tasks involving different pair of languages. In the different experiments presented here for the two word-alignment shared tasks proposed in the HLT-NAACL 2003 and in the ACL 2005, the EDA- based algorithm outperforms the best par- ticipant systems. 1 Introduction Nowadays, statistical approach to machine trans- lation constitutes one of the most promising ap- proaches in this field. The rationale behind this ap- proximation is to learn a statistical model from a par- allel corpus. A parallel corpus can be defined as a set ∗This work has been supported by the Spanish Projects JCCM (PBI-05-022) and HERMES 05/06 (Vic. Inv. UCLM) of sentence pairs, each pair containing a sentence in a source language and a translation of this sentence in a target language. Word alignments are neces- sary to link the words in the source and in the tar- get sentence. Statistical models for machine trans- lation heavily depend on the concept of alignment, specifically, the well known IBM word based mod- els (Brown et al., 1993). As a result of this, differ- ent task on aligments in statistical machine transla- tion have been proposed in the last few years (HLT- NAACL 2003 (Mihalcea and Pedersen, 2003) and ACL 2005 (Joel Martin, 2005)). In this paper, we propose a novel approach to deal with alignments. Specifically, we address the prob- lem of searching for the best word alignment be- tween a source and a target sentence. As there is no efficient exact method to compute the optimal alignment (known as Viterbi alignment) in most of the cases (specifically in the IBM models 3,4 and 5), in this work we propose the use of a recently ap- peared meta-heuristic family of algorithms, Estima- tion of Distribution Algorithms (EDAs). Clearly, by using a heuristic-based method we cannot guarantee the achievement of the optimal alignment. Nonethe- less, we expect that the global search carried out by our algorithm will produce high quality results in most cases, since previous experiments with this technique (Larra˜naga and Lozano, 2001) in different …

Content truncated to 500 words