Abstract
We describe the first tractable Gibbs sampling procedure for estimating phrase pair frequencies under a probabilistic model of phrase alignment. We propose and evaluate two nonparametric priors that successfully avoid the degenerate behavior noted in previous work, where overly large phrases memorize the training data. Phrase table weights learned under our model yield an increase in BLEU score over the word-alignment based heuristic estimates used regularly in phrase-based translation systems.
Introduction
In the mid-2000s, phrase-based statistical machine translation (SMT) represented the state-of-the-art. However, these systems relied on a significant heuristic "hack": instead of learning phrase alignments directly, they first derived word-level alignments (using tools like GIZA++) and then applied fixed heuristics to extract consistent phrases. This paper presents a principled probabilistic model to learn phrase alignments directly from data, overcoming the historical roadblocks of inference complexity and model degeneracy.
The Challenge of Phrase Alignment
Transitioning from word-level to phrase-level alignment introduces two primary difficulties. First, computing expectations for phrase alignments is #P-hard, making exact calculation computationally explosive. Second, maximum likelihood models are prone to degeneracy; without constraints, they tend to treat entire sentences as single giant phrases to maximize likelihood, a form of memorization that fails to generalize to new data.
Bayesian Inference via Gibbs Sampling
To address inference complexity, we employ a Gibbs sampler to explore the alignment space. The sampler utilizes five specific operators to navigate possible configurations:
- SWAP: Exchanges the alignments of two phrases.
- FLIP: Modifies whether a word boundary serves as a phrase boundary.
- TOGGLE: Adds or removes an alignment link.
- FLIP TWO & MOVE: Advanced moves designed to accelerate the exploration of the alignment space.
To prevent model degeneracy, we introduce nonparametric Bayesian priors. A Dirichlet Process (DP) prior acts as a simplicity bias, encouraging the reuse of shorter, existing phrases. We also evaluate a Hierarchical Dirichlet Process (HDP), which encourages the model to compose new phrase pairs from previously observed sub-components. By using the "Chinese Restaurant Process" representation, we can marginalize out model parameters and sample alignment structures directly.
Experimental Results
The model was evaluated on the Spanish-English Europarl corpus using 177,000 sentence pairs. To maintain manageable quadratic-time sampling, training was restricted to sentences with a maximum length of 20 words.
Key findings include:
- Performance: The best-performing configuration (HDP-smooth + lex) achieved a BLEU score of 30.7, surpassing the standard heuristic baseline of 30.5.
- Efficiency: The Bayesian model produced a phrase table 92% smaller than the heuristic baseline while maintaining comparable performance, suggesting that standard systems contain significant noise.
- Degeneracy Avoidance: The DP/HDP models naturally favored small, reusable phrases (e.g., 1x1 or 1x2 blocks), mirroring the behavior of "minimal" heuristic extractions without explicit instruction.
Conclusion and Future Work
This work demonstrates that a well-defined probabilistic model can find high-quality, non-literal translations that heuristics often miss. While the current sampling process is computationally intensive—taking up to two days for HDP training on an 8-processor machine—it proves that the degeneracy problem is a matter of prior selection rather than an inherent flaw in phrase-based modeling. Future research will focus on scaling these techniques to the longer sentence lengths typical of real-world bitexts.
Summary updated