Dependency Treelet Translation: Syntactically Informed Phrasal SMT
What it is about
The system takes a source sentence, parses it into a dependency tree, and projects that tree onto the target sentence through the word alignment. From the projected pairs it extracts treelet translation pairs: connected subtrees of the source with their aligned target words. A tree-based order model then decides how the target treelets are arranged, and a decoder combines the treelets with conventional phrase-table and language-model scores. Experiments use BLEU on a 10,000-sentence test set with one reference. The treelet system scores 40.66, against 38.83 for the phrasal decoder Pharaoh and 35.26 for an example-based hybrid. The gap is widest with small phrases and with small training sets: with single-word treelets the treelet system gets 37.50 BLEU where Pharaoh with the same settings gets 23.18. All differences are significant at the 99 percent level. The decoder is slower than Pharaoh, about 10 sentences per minute against 162.
Ideas
- I1. Treelet pairs as units of the encoder. A treelet is a connected subtree of the source with its target words, which is the chunk that open problem 3 asks for. Extract treelet pairs from verse pairs, using the projected head of each target word, and keep the pairs whose count passes a threshold.
- I2. A count-based order model. For each head and child relation, count whether the child precedes its head in the aligned target order. The result is a small table that can serve the linearizer side tables in
en/src/lin.rs, and it is the count form of the Hebrew order normaliser (open problem 7). - I3. Phrase-size sweep as the paper does in its Table 5.2. Run the meta-world encoder with chunks of one word, two words and four words on the same dev verses, and report the residual for each size.
- I4. Training-size sweep as in Table 5.3. The tree model gains most at small corpora, so repeat the sweep on subsets of the Bible pairs to check whether the gain holds for the small translators.
For Mova
The code is tools/translate (the encoder in profile.rs, the lexicon in meta.rs) and the order table for en/src/lin.rs. The model here is counted, not neural, so it fits the ordered-map design. The first measure is the phrase-size sweep of I3, since it shows whether one-word chunks with a tree order model are enough.
Library summary
Written for the Research library (claude-opus-5-5) from the paper text, in our own words: the license "CC BY-NC-SA 3.0 (ACL Anthology, before 2016)" does not allow redistributing the text itself. Original — aclanthology.org/P05-1034.pdf
Summary
Phrase-based SMT systems of the time memorized contiguous word strings and reordered them with weak, position-based models. They could not generalize word-order patterns to unseen phrases or handle discontiguous correspondences such as English not and French ne…pas. Quirk, Menezes and Cherry bring source-side syntax into phrasal SMT, and they need only a source dependency parser, target word segmentation and GIZA++ alignments.
The method has four steps:
- Parse the source side of a parallel corpus.
- Project the dependency trees onto the target sentences through the word alignments.
- Extract "treelet" pairs, meaning connected subgraphs of the trees.
- Train a tree-based model that predicts where each modifier lands relative to its head.
A decoder then covers the input parse with treelets, scoring candidates log-linearly with standard SMT features.
Training used 100k sentence pairs, with a 10k-sentence test set. The Treelet system scored 40.66 BLEU, compared with 38.83 for Pharaoh and 35.26 for MSR-MT. Its advantage was largest with short phrases and small training sets. This points to syntax-aware ordering as a cheap way to help low-resource translation directions.
Key points
-
Main comparison (100k training pairs, max phrase size 4, single reference):
System BLEU Speed (sentences/min) Treelet 40.66 10.1 Pharaoh 38.83 162 Pharaoh monotone 37.06 4286 MSR-MT 35.26 453 The Treelet vs. Pharaoh difference was significant at 99% (paired t-test).
-
Single-word phrases: Treelet reached 37.50 BLEU while Pharaoh collapsed to 23.18.
-
Training size:
- At 1k pairs: Treelet 18.70 vs. Pharaoh 17.20.
- At 300k pairs: Treelet 44.32 vs. Pharaoh 42.75.
-
Ablations:
- Allowing discontiguous treelets raised BLEU from 40.08 to 40.66.
- Ordering strategy: monotone 35.35, greedy 38.85, exhaustive search 40.66.
-
Requirements: an unlabeled, ordered source dependency parser with POS tags, GIZA++ run in both directions, and a combination heuristic that keeps many-to-one links contiguous in the source tree. No target-language parser is needed.
Interesting ideas
- Projection with repair: Map source dependencies onto the target via alignments, attach unaligned words heuristically, then run a reattachment pass so the tree reads off in surface order. This is a handy recipe for bootstrapping rough dependency trees in a language without a treebank, such as projecting from English onto Ukrainian.
- Wildcard-root treelets: Treelets whose root is left unspecified capture correspondences between sibling words, like split negation, without binding them to a particular head word. This could suit any language with discontiguous constructions, including particles and clitics.
- Independent head-relative ordering: Word order is factorized into separate predictions of each modifier's position relative to its head, using local lexical and POS features. This keeps the model simple, and it generalizes across phrases with the same structure. It could transfer to text generation or linearization tasks.
- Asymmetric syntax requirement: Syntax is required only on the source side. This greatly widens the range of usable language pairs compared with systems that must parse both languages, which matters when one side is under-resourced.
- Stress-test evaluation: Comparing systems while shrinking the maximum phrase length and the training data exposes where the structural model really helps. It is a good template for judging methods aimed at low-resource settings.
Cite
@inproceedings{quirk2005dependency,
title = {{Dependency Treelet Translation: Syntactically Informed Phrasal SMT}},
author = {Quirk, Chris and Menezes, Arul and Cherry, Colin},
booktitle = {Proceedings of the 43rd Annual Meeting of the Association for Computational Linguistics (ACL'05)},
year = {2005},
doi = {10.3115/1219840.1219874},
url = {https://doi.org/10.3115/1219840.1219874}
}References
- Alshawi, Hiyan, Srinivas Bangalore, and Shona Douglas. Learning dependency translation models as collections of finite-state head transducers. Computational Linguistics, 26(1):45–60, 2000. find
- Aue, Anthony, Arul Menezes, Robert C. Moore, Chris Quirk, and Eric Ringger. Statistical machine translation using labeled semantic dependency graphs. TMI 2004. find
- Charniak, Eugene, Kevin Knight, and Kenji Yamada. Syntax-based language models for statistical machine translation. MT Summit 2003. find
- Cherry, Colin and Dekang Lin. A probability model to improve word alignment. ACL 2003. find
- Chickering, David Maxwell. The WinMine Toolkit. Microsoft Research Technical Report: MSR-TR-2002-103. find
- Ding, Yuan and Martha Palmer. Automatic learning of parallel dependency treelet pairs. IJCNLP 2004. find
- Heidorn, George. (2000). “Intelligent writing assistance”. In Dale et al. Handbook of Natural Language Processing, Marcel Dekker. find
- Koehn, Philipp, Franz Josef Och, and Daniel Marcu. Statistical phrase based translation. NAACL 2003. find
- Lin, Dekang. A path-based transfer model for machine translation. COLING 2004. find
- Menezes, Arul and Stephen D. Richardson. A best-first alignment algorithm for automatic extraction of transfer mappings from bilingual corpora. DDMT Workshop, ACL 2001. find
- Och, Franz Josef and Hermann Ney. A systematic comparison of various statistical alignment models, Computational Linguistics, 29(1):19-51, 2003. find
- Och, Franz Josef. Minimum error rate training in statistical machine translation. ACL 2003. find
- Och, Franz Josef, et al. A smorgasbord of features for statistical machine translation. HLT/NAACL 2004. find
- Papineni, Kishore, Salim Roukos, Todd Ward, and Wei-Jing Zhu. BLEU: a method for automatic evaluation of machine translation. ACL 2002. find our card
- Quirk, Chris, Arul Menezes, and Colin Cherry. Dependency Tree Translation. Microsoft Research Technical Report: MSR-TR-2004-113. find
- Ringger, Eric, et al. Linguistically informed statistical models of constituent structure for ordering in sentence realization. COLING 2004. find
- Thurmair, Gregor. Comparing rule-based and statistical MT output. Workshop on the amazing utility of parallel and comparable corpora, LREC, 2004. find
- Vogel, Stephan, Ying Zhang, Fei Huang, Alicia Tribble, Ashish Venugopal, Bing Zhao, and Alex Waibel. The CMU statistical machine translation system. MT Summit 2003. find
- Wu, Dekai. Stochastic inversion transduction grammars and bilingual parsing of parallel corpora. Computational Linguistics, 23(3):377–403, 1997. find our card
- Yamada, Kenji and Kevin Knight. A syntax-based statistical translation model. ACL, 2001. find our card