DeNero et al, EMNLP 2008

Citation

Denero, J., Bouchard-ct, R., & Klein, D.(2008). Sampling alignment structure under a Bayesian translation model. In Proceedings of the Conference on Empirical Methods in Natural Language Processing (EMNLP '08). Association for Computational Linguistics, Stroudsburg, PA, USA, 314-323.

Online version

pdf

Summary

Unlike word-to-phrase alignments, computing the alignment and count expectations for phrase-to-phrase alignments is generally intractable due to the exponential growth of possible combination of phrases and alignments. Thus, previous attempts for building a fully joint phrase alignment model have been unsuccessful.

This paper describes the first tractable phrase-to-phrase Alignment Model, which relies on Gibbs sampling to address the intractability issues.

Tests show translation improvements over Machine Translation Systems build using traditional methods (Word Alignments + Phrase Extraction).

Description of the Method

The phrase-to-phrase alignment model used in this work is presented in Marcus and Wong, EMNLP 2002. An extension is made to allow null phrases, where a phrase does not have an equivalent in the other language. This is done by introducing another multinomial distribution $\theta _{N}$, from where unaligned phrase pairs are drawn.

This model involves the observed sentence pairs $x$, the latent phrase segmentations and alignments $z$ and the parameters $\theta$($\theta _{N}$ and $\theta _{J}$), from where phrase pairs are drawn. As with other alignment models, the Expectation Maximization Algorithm is used, where during the E-step the expected counts for phrase pairs are calculated under $P(z|x,\theta )$ by fixing $\theta$ and during the M-step a new $\theta$ is calculated based on these counts. However, computing the expected counts this way would involve computing the expected phrase pair counts under all possible segmentations and alignments $z$, which is too large to be computed one by one. This was the main drawback of the work in Marcus and Wong, EMNLP 2002.

This work addresses this problem using Gibbs sampling. Rather than iterating over all possible $z$, this work generates a sequence of samples that approximate the conditional distribution $P(z|x,\theta )$. Then, by averaging counts for phrase pairs using those samples, an approximation of the expected counts under $P(z|x,\theta )$ can be computed. In this work, these counts are directly used to calculate the Translation features, rather than considering the Word Alignments as a separate step.

The Gibbs Sampler presented in this work starts with the initial state $z_{0}$, which sets a initial configuration for the phrase segmentation and alignment. Then, by applying a set of local changes starting from $z_{0}$, a sequence of samples $z_{i},z_{i+1},\dots$ are produced. These samples are guaranteed to approximate the conditional distribution $P(z|x,\theta )$.

This work defines a set of operators that can be applied to a state $z_{i}$ to generate a new state $z_{i+1}$. Each operator freezes the state $z_{i}$, except for a local region, and chooses a reconfiguration, between all possible reconfigurations of that region, according to the conditional probability of each reconfiguration. This is done so that the sequence of generated samples approximate $P(z|x,\theta )$.

Finally, every phrase-to-phrase alignment model has to deal with degeneracy issues, since the joint model penalizes segmentations that use many small phrases, because additional phrases incur additional generation and distortion penalties. This means that the maximum likelihood estimation of the model puts weight on segmentations with only one phrase pair that translates the whole source sentence to the target sentence, which perfectly translates the sentences in the training corpus but are unlikely to be useful for decoding sentences that are not in the training corpus. This work addresses this problem by defining a Dirichlet process prior over phrase pairs, and selecting a base measure that prefers shorter phrase pairs and only uses longer phrase pairs when there is clear evidence for them.

Experimental Results

This work was tested using the setup from the Statistical Machine Translation Workshop shared task, where the model is trained using the EUROPARL dataset for Spanish-English. Using the expected counts to calculate the translation features, considerable improvements observed in terms of translation quality, measured with BLEU and METEOR, over the baseline trained using Moses, where features are calculated using the Word Alignments.

Related Work

The work in Marcus and Wong, EMNLP 2002, describes a joint probability distribution, which is used and extended in this work.

Similar approaches to address the problem of the intractability of all possible phrase segmentations and alignments have been tested using algorithms such as Hill Climbing in Birch et al, StatMT 2006.

Comment

Hey, if you want to see more work in word alignment, this recent paper is interesting. It may be an interesting contrast because it not use Gibbs sampling for inference. C. Dyer, J. H. Clark, A. Lavie, and N. A. Smith. Unsupervised Word Alignment with Arbitrary Features. --Brendan 18:36, 13 October 2011 (UTC)