Abstract
Shankar Kumar and William Byrne (2003) present a reformulation of the phrase-based Alignment Template Translation Model (ATTM) into a framework of Weighted Finite State Transducers (WFSTs). This approach allows complex statistical machine translation tasks to be solved using standard, optimized finite-state operations, demonstrating superior performance over traditional word-to-word models like IBM Model 4.
Introduction: Beyond Word-to-Word Translation
In the early 2000s, Statistical Machine Translation (SMT) was dominated by word-to-word models, most notably the IBM Models. While foundational, these models struggled with "phrasal" translations—idioms or groups of words that move together—and required highly specialized, complex decoding algorithms (such as $A^*$ search or dynamic programming) to find the best translation.
The Alignment Template Translation Model (ATTM) emerged as a promising alternative by utilizing phrase-level alignments. However, its implementation and optimization remained challenging. Kumar and Byrne addressed this by representing the entire ATTM process as a series of finite-state machines, enabling the use of off-the-shelf, highly optimized Finite State Machine (FSM) toolkits for translation.
The WFST Framework
The core contribution of this work is the decomposition of the ATTM into several independent component distributions, each implemented as a specific WFST or acceptor.
The translation process is modeled as a composition of these transducers:
- Source Segmentation ($\Omega$): Breaks the source sentence into all possible phrase sequences.
- Phrase Permutation ($\Pi_V$ and $H$): Allows for reordering phrases to match target language word order, assigning probabilities based on positional deviation.
- Template Sequence ($Y$): Maps source phrases to "alignment templates"—pre-learned matrices describing internal word alignments.
- Phrasal Translation ($W$): A complex transducer that produces target language words.
- Target Language Model ($G$): A standard trigram language model ensuring output fluency.
By composing these transducers ($S \circ \Omega \circ \Pi_V \circ H \circ Y \circ W \circ G$), translation is reduced to finding the shortest path through a single, massive state graph.
Detailed Component Construction
A key technical challenge was the construction of the Phrasal Translation ($W$) transducer. As shown in Figure 5, this component is built from several sub-machines:
- O (Alignment): Models the alignment within the template.
- I (Indexing): Maps template indices to source words.
- D (Lexicon): Provides word-level translation probabilities.
- C (Target Phrase): Concatenates translated words into phrases.
This modularity allows researchers to improve individual components, such as the language model or the reordering model, independently of the search engine.
Experimental Results
The model was evaluated on the Canadian French-to-English Hansards task using a training set of 50,000 sentence pairs and a template library of over 1 million entries. The WFST-based ATTM was compared against the standard IBM Model 4 using the ReWrite decoder.
| Metric | IBM Model 4 | ATTM (WFST) |
|---|---|---|
| BLEU (Higher is better) | 0.1711 | 0.1941 |
| NIST (Higher is better) | 5.0823 | 5.3337 |
| WER (Lower is better) | 67.5% | 64.7% |
The ATTM outperformed IBM Model 4 across all major metrics. In word alignment tasks, the model achieved high precision (94.5%), though recall was lower (55.8%), suggesting that the template library's coverage was a limiting factor.
Conclusion and Future Work
Kumar and Byrne demonstrated that specialized decoders are not strictly necessary for state-of-the-art SMT. The WFST framework naturally produces translation lattices, which are highly valuable for downstream tasks. Future directions include improving template library coverage and moving toward iterative parameter estimation to refine model weights.
Summary updated