Hidden Markov Tree Model for Word Alignment

Proceedings of the Eighth Workshop on Statistical Machine Translation, pages 503–511, Sofia, Bulgaria, August 8-9, 2013 c⃝2013 Association for Computational Linguistics Hidden Markov Tree Model for Word Alignment Shuhei Kondo Kevin Duh Yuji Matsumoto Graduate School of Information Science Nara Institute of Science and Technology 8916-5, Takayama, Ikoma, Nara, 630-0192, Japan {shuhei-k,kevinduh,matsu}@is.naist.jp Abstract We propose a novel unsupervised word alignment model based on the Hidden Markov Tree (HMT) model. Our model assumes that the alignment variables have a tree structure which is isomorphic to the target dependency tree and models the dis- tortion probability based on the source de- pendency tree, thereby incorporating the syntactic structure from both sides of the parallel sentences. In English-Japanese word alignment experiments, our model outperformed an IBM Model 4 baseline by over 3 points alignment error rate. While our model was sensitive to poste- rior thresholds, it also showed a perfor- mance comparable to that of HMM align- ment models. 1 Introduction Automatic word alignment is the first step in the pipeline of statistical machine translation. Trans- lation models are usually extracted from word- aligned bilingual corpora, and lexical translation probabilities based on word alignment models are also used for translation. The most widely used models are the IBM Model 4 (Brown et al., 1993) and Hidden Markov Models (HMM) (Vogel et al., 1996). These mod- els assume that alignments are largely monotonic, possibly with a few jumps. While such assump- tion might be adequate for alignment between sim- ilar languages, it does not necessarily hold be- tween a pair of distant languages like English and Japanese. Recently, several models have focused on in- corporating syntactic structures into word align- ment. As an extension to the HMM alignment, Lopez and Resnik (2005) present a distortion model conditioned on the source-side dependency tree, and DeNero and Klein (2007) propose a distortion model based on the path through the source-side phrase-structure tree. Some super- vised models receive syntax trees as their input and use them to generate features and to guide the search (Riesa and Marcu, 2010; Riesa et al., 2011), and other models learn a joint model for pars- ing and word alignment from word-aligned par- allel trees (Burkett et al., 2010). In the context of phrase-to-phrase alignment, Nakazawa and Kuro- hashi (2011) propose a Bayesian subtree align- ment model trained with parallel sampling. None of these models, however, can incorporate syntac- tic structures from both sides of the language pair and can be trained computationally efficiently in an unsupervised manner at the same time. The Hidden Markov Tree (HMT) model (Crouse et al., 1998) is one such model that sat- isfies the above-mentioned properties. The HMT model assumes a tree structure of the hidden vari- ables, which fits well with the notion of word-to- word dependency, and it can be trained from un- labeled data via the EM algorithm with the same order of time complexity as HMMs. In this paper, we propose a novel word align- ment model based on the HMT model …

Content truncated to 500 words