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

ACM

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 tackle the intractability issues.

Tests show translation improvements over Machine Translation Systems build using conventional methods.

Phrase Alignment Model

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 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 tackles 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.

Gibbs Sampler

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 operate 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 each reconfiguration, given the frozen region of the state. This frozen region of the state is called Markov blanket.

The SWAP operator freezes all phrases, and then chooses two target phrases $t_{1}$ and $t_{2}$. All alignments are also frozen, except for the alignments $[t_{1},s_{1}]$ and $[t_{2},s_{2}]$. The operator must choose to keep these alignments or switch to the alignments $[t_{2},s_{1}]$ and $[t_{1},s_{2}]$