A New String-to-Dependency Machine Translation Algorithm with a Target Dependency Language Model

What it is about

The paper proposes a string-to-dependency statistical MT system. The source side of each rule is a string, as in the Hiero hierarchical model, but the target side is a dependency structure. Only "well-formed" target structures are allowed: fixed structures with a known head, and floating structures, which are sibling sets under an unspecified head (for example "the red" as a modifier of a noun). Because of this restriction, the rule set is about 80% smaller than the replicated Hiero baseline (27M rules against 140M). The main gain comes from a target dependency language model, a trigram model over heads and their children, which is applied bottom-up during decoding. On NIST MT04 Chinese-English it improves BLEU by 1.48 and TER by 2.53 over the baseline with a 3-gram LM, and by 1.21 BLEU after 5-gram rescoring.

Ideas

I1. Encoder output as well-formed target trees: the encoder in tools/translate/src/profile.rs builds word strings, and the open problem 3 asks for trees. Give each encoded chunk a fixed or floating category, and count how often a chunk's head and children can be joined under that rule. Report the share per author, run twice.
I2. A count-based dependency language model for the encoder: count (head, child, side) triples over the English UD trees that the standard was learned from, and score candidate orders of the children of a head. Keep the tables in BTreeMap, and use them to choose the order when en/src/lin.rs has several equal-score chains.
I3. Floating groups for function words: the paper handles "the red" as a floating sibling set. Try the same for determiners and "that" in the meta-world (open problem 4), so that an encoder can place them without a head.
I4. Control: report the size of the chunk table before and after a well-formedness filter, and the exact-match change on dev. The paper's own control is the filtered string-to-string model, which loses the gain. The translator should have the same control, the standard with the filter but without the dependency score.

For Mova

The code is tools/translate/src/profile.rs (the encoder) and en/src/lin.rs (word order). The paper's decoder is not for Mova, since the translator has no search over many derivations at test time. The useful parts are the well-formedness check and the head-child count model, both count-based and deterministic.

Library summary

The Research library's own summary of the paper, in our words — not the paper's text.

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/P08-1066.pdf

Summary

Hierarchical phrase-based MT systems such as Hiero use an n-gram language model, which only sees neighbouring words on the target side. Shen, Xu and Weischedel propose a string-to-dependency translation framework. Each rule keeps the source side as a plain string with non-terminals, and the target side carries a dependency structure. Target fragments must be "well-formed": either fixed (a subtree with a known head whose children are complete) or floating (complete sibling subtrees sharing a head that is not yet specified). A small set of category operations (raising and unification) makes sure that bottom-up chart decoding only builds well-formed partial structures. This allows dynamic programming and covers many non-constituent phrases, such as "the red". Because the target trees exist during decoding, a dependency language model can score word relations at long distances. On NIST MT04 Chinese-English, the system beats a replicated Hiero baseline by 1.48 BLEU and 2.53 TER, while using about 80% fewer rules. This shows that target-side syntax helps when it feeds a structural language model.

Key points

The paper compares three systems:
- baseline: a replication of Hiero.
- filtered: Hiero restricted to rules whose target side can come from a well-formed dependency structure.
- str-dep: string-to-dependency decoding with a 3-gram dependency LM.
Rule set sizes:
- baseline: 140M rules.
- filtered: 26M rules.
- str-dep: 27M rules, under 20% of the baseline.
Data:
- Bilingual training data of about 178M/191M source/target words comes from NIST 2006 large-track data and GALE LDC corpora (e.g. LDC2005E83, LDC2006E34, LDC2006G05).
- Hierarchical rules come from a 35M/41M-word subset, and the dependency LM was trained on its English side.
- The n-gram LMs (3-gram and 5-gram) were trained on about 6G words of LDC Gigaword plus web text.
Setup: weights were tuned on MT05 for BLEU, and the systems were tested on MT04 with both BLEU and TER.
Results:
- Decoding with the 3-gram LM: mixed-case BLEU goes from 35.77 to 37.25, and TER from 56.60 to 54.07.
- After rescoring 1000-best lists with the 5-gram LM: gains are 1.21 BLEU and 1.19 TER.
- The filtered system alone gives no BLEU gain.

Interesting ideas

Restricted structure classes as a middle ground. The model allows only fixed and floating fragments instead of arbitrary treelets. This keeps the search space manageable while still representing useful non-constituent pieces. The same compromise could help any syntax-aware generator or parser that must merge partial hypotheses efficiently.
A category algebra that guarantees validity. Each partial structure gets a compact signature: left dependents, head, right dependents. Combination is allowed only when signatures unify, so invalid outputs are ruled out by construction rather than filtered afterwards. This is reusable wherever chart-style combination must respect structural constraints.
A control experiment that isolates the gain. The "filtered" system uses the same rule inventory but without the dependency LM. It shows that the improvement comes from the structural LM, not from the rule restriction itself. Building such matched ablations is a good habit when a method changes several things at once.
Structural constraints as rule pruning. Requiring well-formed targets removed over 80% of the rules with no loss in quality. Linguistic well-formedness can therefore act as a cheap way to shrink extracted grammars or phrase tables.
Tune on one metric, report another. The systems are optimised for BLEU but also evaluated with TER. This exposes over-fitting to the tuning metric and is a simple safeguard for any metric-driven optimisation.

Topics: Machine translation

Cite

The paper itself, not this card. BibTeX from the library's record of the work.

@inproceedings{shen2008new,
  title = {{A New String-to-Dependency Machine Translation Algorithm with a Target Dependency Language Model}},
  author = {Shen, Libin and Xu, Jinxi and Weischedel, Ralph},
  booktitle = {Proceedings of ACL-08: HLT},
  year = {2008},
  url = {https://aclanthology.org/P08-1066/}
}

References

24 references, 10 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

I. Bulyko, S. Matsoukas, R. Schwartz, L. Nguyen, and J. Makhoul. 2007. Language model adaptation in machine translation from speech. In Proceedings of the 32nd IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP). find
E. Charniak, K. Knight, and K. Yamada. 2003. Syntax-based language models for statistical machine translation. In Proceedings of MT Summit IX. find
D. Chiang. 2005. A hierarchical phrase-based model for statistical machine translation. In Proceedings of the 43th Annual Meeting of the Association for Computational Linguistics (ACL). find our card
D. Chiang. 2007. Hierarchical phrase-based translation. Computational Linguistics, 33(2). find our card
S. DeNeefe, K. Knight, W. Wang, and D. Marcu. 2007. What can syntax-based mt learn from phrase-based mt? In Proceedings of the 2007 Conference of Empirical Methods in Natural Language Processing. find
Y. Ding and M. Palmer. 2005. Machine translation using probabilistic synchronous dependency insertion grammars. In Proceedings of the 43th Annual Meeting of the Association for Computational Linguistics (ACL), pages 541–548, Ann Arbor, Michigan, June. find our card
J. Eisner and G. Satta. 1999. Efficient parsing for bilexical context-free grammars and head automaton grammars. In Proceedings of the 37th Annual Meeting of the Association for Computational Linguistics (ACL). find
H. Fox. 2002. Phrasal cohesion and statistical machine translation. In Proceedings of the 2002 Conference of Empirical Methods in Natural Language Processing. find
M. Galley, M. Hopkins, K. Knight, and D. Marcu. 2004. What’s in a translation rule? In Proceedings of the 2004 Human Language Technology Conference of the North American Chapter of the Association for Computational Linguistics. find our card
M. Galley, J. Graehl, K. Knight, D. Marcu, S. DeNeefea, W. Wang, and I. Thayer. 2006. Scalable inference and training of context-rich syntactic models. In COLING-ACL ’06: Proceedings of 44th Annual Meeting of the Association for Computational Linguistics and 21st Int. Conf. on Computational Linguistics. find
J. Graehl and K. Knight. 2004. Training tree transducers. In Proceedings of the 2004 Human Language Technology Conference of the North American Chapter of the Association for Computational Linguistics. find our card
L. Huang and D. Chiang. 2005. Better k-best parsing. In Proceedings of the 9th International Workshop on Parsing Technologies. find
D. Magerman. 1995. Statistical decision-tree models for parsing. In Proceedings of the 33rd Annual Meeting of the Association for Computational Linguistics. find
D. Marcu, W. Wang, A. Echihabi, and K. Knight. 2006. SPMT: Statistical machine translation with syntactified target language phraases. In Proceedings of the 2006 Conference of Empirical Methods in Natural Language Processing. find
R. McDonald, K. Crammer, and F. Pereira. 2005. Online large-margin training of dependency parsers. In Proceedings of the 43th Annual Meeting of the Association for Computational Linguistics (ACL). find our card
F. J. Och and H. Ney. 2003. A systematic comparison of various statistical alignment models. Computational Linguistics, 29(1). find
F. J. Och. 2003. Minimum error rate training for statistical machine translation. In Erhard W. Hinrichs and Dan Roth, editors, Proceedings of the 41st Annual Meeting of the Association for Computational Linguistics (ACL), pages 160–167, Sapporo, Japan, July. find
M. Palmer, D. Gildea, and P. Kingsbury. 2005. The proposition bank: An annotated corpus of semantic roles. Computational Linguistics, 31(1). find our card
K. Papineni, S. Roukos, and T. Ward. 2001. Bleu: a method for automatic evaluation of machine translation. IBM Research Report, RC22176. find our card
C. Quirk, A. Menezes, and C. Cherry. 2005. Dependency treelet translation: Syntactically informed phrasal SMT. In Proceedings of the 43th Annual Meeting of the Association for Computational Linguistics (ACL), pages 271–279, Ann Arbor, Michigan, June. find our card
S. Shieber and Y. Schabes. 1990. Synchronous tree adjoining grammars. In Proceedings of COLING ’90: The 13th Int. Conf. on Computational Linguistics. find
M. Snover, B. Dorr, R. Schwartz, L. Micciulla, and J. Makhoul. 2006. A study of translation edit rate with targeted human annotation. In Proceedings of Association for Machine Translation in the Americas. find our card
W. Wang, K. Knight, and D. Marcu. 2007. Binarizing syntax trees to improve syntax-based machine translation accuracy. In Proceedings of the 2007 Conference of Empirical Methods in Natural Language Processing. find
P. Xu, C. Chelba, and F. Jelinek. 2002. A study on richer syntactic dependencies for structured language modeling. In Proceedings of the 40th Annual Meeting of the Association for Computational Linguistics (ACL). find