An Alignment Algorithm Using Belief Propagation and a Structure-Based Distortion Model

Proceedings of the 12th Conference of the European Chapter of the ACL, pages 166–174, Athens, Greece, 30 March – 3 April 2009. c⃝2009 Association for Computational Linguistics An Alignment Algorithm using Belief Propagation and a Structure-Based Distortion Model Fabien Cromi`eres Graduate school of informatics Kyoto University Kyoto, Japan fabien@nlp.kuee.kyoto-u.ac.jp Sadao Kurohashi Graduate school of informatics Kyoto University Kyoto, Japan kuro@i.kyoto-u.ac.jp Abstract In this paper, we first demonstrate the in- terest of the Loopy Belief Propagation al- gorithm to train and use a simple align- ment model where the expected marginal values needed for an efficient EM-training are not easily computable. We then im- prove this model with a distortion model based on structure conservation. 1 Introduction and Related Work Automatic word alignment of parallel corpora is an important step for data-oriented Machine trans- lation (whether Statistical or Example-Based) as well as for automatic lexicon acquisition. Many algorithms have been proposed in the last twenty years to tackle this problem. One of the most suc- cessfull alignment procedure so far seems to be the so-called “IBM model 4” described in (Brown et al., 1993). It involves a very complex distor- tion model (here and in subsequent usages “dis- tortion” will be a generic term for the reordering of the words occurring in the translation process) with many parameters that make it very complex to train. By contrast, the first alignment model we are going to propose is fairly simple. But this sim- plicity will allow us to try and experiment differ- ent ideas for making a better use of the sentence structures in the alignment process. This model (and even more so its subsequents variations), al- though simple, do not have a computationally ef- ficient procedure for an exact EM-based training. However, we will give some theoretical and empir- ical evidences that Loopy Belief Propagation can give us a good approximation procedure. Although we do not have the space to review the many alignment systems that have already been proposed, we will shortly refer to works that share some similarities with our approach. In particu- lar, the first alignment model we will present has already been described in (Melamed, 2000). We differ however in the training and decoding pro- cedure we propose. The problem of making use of syntactic trees for alignment (and translation), which is the object of our second alignment model has already received some attention, notably by (Yamada and Knight, 2001) and (Gildea, 2003) . 2 Factor Graphs and Belief Propagation In this paper, we will make several use of Fac- tor Graphs. A Factor Graph is a graphical model, much like a Bayesian Network. The three most common types of graphical models (Factor Graphs, Bayesian Network and Markov Network) share the same purpose: intuitively, they allow to represent the dependencies among random vari- ables; mathematically, they represent a factoriza- tion of the joint probability of these variables. Formally, a factor graph is a bipartite graph with 2 kinds of nodes. On one side, the Variable Nodes (abbreviated …

Content truncated to 500 words