Abstract: Most modern machine translation systems use phrase pairs as translation units, allowing for accurate modelling of phraseinternal translation and reordering. However phrase-based approaches are much less able to model sentence level effects between different phrase-pairs. We propose a new model to address this imbalance, based on a word-based Markov model of translation which generates target translations left-to-right. Our model encodes word and phrase level phenomena by conditioning translation decisions on previous decisions and uses a hierarchical Pitman-Yor Process prior to provide dynamic adaptive smoothing. This mechanism implicitly supports not only traditional phrase pairs, but also gapping phrases which are non-consecutive in the source. Our experiments on Chinese to English and Arabic to English translation show consistent improvements over competitive baselines, of up to +3.4 BLEU.
Introduction
In the landscape of machine translation circa 2013, Phrase-Based Machine Translation (PBMT) was the dominant paradigm. PBMT operates by segmenting sentences into discrete "phrase pairs." While effective, this approach suffers from two primary limitations: a rigid independence assumption between phrases and an inability to handle "gapping" or discontinuous phrases (e.g., "green, delicious apple" when only "green apple" was learned).
This paper proposes a word-based Markov model that generates target translations from left to right. By replacing rigid phrase boundaries with a fluid, history-dependent generative process, the model captures complex dependencies and reordering patterns while remaining flexible enough to handle unseen word combinations.
The Generative Process
The core of the proposed system is a Markov Model that makes a sequence of four types of decisions for every target word produced:
- Finish: Determining if the translation is complete.
- Jump: Selecting the next source word to focus on (handling reordering).
- Emission: Choosing the target word given the current source word.
- Fertility: Deciding how many target words a single source word should produce.
As shown in the figure above, the model moves through the source sentence (e.g., "Je le prends") to generate the target ("I 'll take that one"). Each step involves a specific jump type—such as monotone, forward, or backward—and an emission that maps source units to target words.
Bayesian Smoothing with hPYP
To avoid the "curse of dimensionality" when conditioning decisions on long histories, the authors employ a Hierarchical Pitman-Yor Process (hPYP). This Bayesian non-parametric prior provides a mathematically elegant way to perform adaptive smoothing. If the model encounters a sequence it hasn't seen before, it gracefully "backs off" to shorter histories. Because it follows a power-law distribution, the hPYP is uniquely suited for the long-tail nature of natural language data.
Training is conducted via Gibbs Sampling, an MCMC technique that iteratively refines word alignments across the training corpus, allowing the model to learn from the entire dataset simultaneously rather than relying on local heuristics.
Key Results
The model was evaluated on several major tasks, including IWSLT (Chinese-to-English), FBIS, and NIST (Arabic-to-English). The results demonstrated that the Markovian approach significantly outperforms standard phrase-based baselines.
As illustrated in the table, the incremental addition of features—such as jump ($j$) and fertility ($f_t$)—leads to steady gains in BLEU scores. On the IWSLT05 task, the full model achieved a +3.43 BLEU improvement over the baseline. Beyond raw metrics, the model produced more accurate word alignments, particularly for function words that are often misaligned by standard tools like GIZA++.
Insights and Limitations
A profound takeaway from this research is that "phrases" do not need to be explicit units in a database; they can emerge naturally from correlations between word-level decisions. This allows the model to handle discontinuous phrases (e.g., German separable verbs) that traditional PBMT struggles to represent.
However, the approach has trade-offs. Gibbs sampling is computationally more expensive than the Expectation-Maximization algorithms used in traditional tools. Furthermore, while the model generates superior alignments, its full potential for decoding gapping phrases requires the development of a dedicated decoder, as it was primarily used in this study to augment existing phrase-based pipelines.
Summary updated