Machine Translation Using Probabilistic Synchronous Dependency Insertion Grammars

What it is about

The paper proposes a synchronous dependency insertion grammar (SDIG), a version of synchronous grammar defined on dependency trees. The grammar is induced from parallel corpora: a dependency tree of the source is aligned with a tree of the target, and the aligned parts give elementary trees in which a dependent is inserted under a head. The translation model is a probabilistic tree-to-tree transducer over non-isomorphic trees, with a graphical model for it. Decoding is a polynomial-time search over a shared forest of the possible decompositions of the input dependency tree, which the paper shows to be linear in the input size once the parse is given. The system is evaluated with NIST and BLEU against a system built on IBM Model 4 trained on the same data. The printed table gives a cumulative 4-gram BLEU of 0.132 for SDIG against 0.109 for IBM Model 4, and the paper also reports that SDIG is faster. The authors name a full version and a trigram language model as future work.

Ideas

I1. Insertion as an operation on the reader's trees. A function word such as the or that can be inserted under a head with a count per (head concept, relation). Count these insertions per author and keep only those above a threshold, which is open problem 4 in count form.
I2. Forest of head attachments. Keep the decompositions of a verse's tree as a packed forest rather than one parse, and take the most probable attachment under the counts. This reduces the attachment noise of open problem 1 without a second parser.
I3. A classic baseline in the same table. The paper compares against IBM Model 4. Put a word-table baseline next to the meta-world on the same verses and report the residual of both, so a claim against a weak baseline is not made.

For Mova

The code is tools/translate (meta.rs for the insertion counts, the reader in hebrew.rs for attachments). The model is probabilistic but its tables are counts, so the ordered-map design holds. The result table is the reference: the claim is only what the paper reports, and a Mova gain needs its own residual measurement, run twice.

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/P05-1067.pdf

Summary

Ding and Palmer address a core obstacle for syntax-based statistical MT: dependency trees of a sentence and its translation are often not isomorphic, which makes tree-to-tree transduction hard to learn and slow to run. They model translation with a Synchronous Dependency Insertion Grammar (SDIG). In SDIG, the two trees are required to correspond only at the level of elementary trees (ETs), which are multi-word dependency fragments, not at the level of single words.

The grammar is induced from parallel dependency trees by iterative, category-driven hierarchical tree partitioning. This process is seeded with IBM Model 1 word translation probabilities. Translation is then treated as a stochastic tree-to-tree transducer, decoded top-down over a packed forest in time linear in input size.

On Chinese-English news data, with parses from the Bikel parser converted to dependencies, SDIG beat a GIZA++ IBM Model 4 baseline on both NIST and Bleu. It also decoded dramatically faster. This was offered as rare empirical evidence that syntax-based SMT can beat a pure string-based system.

Key points

Training data: Xinhua (56,263 pairs) and FBIS (45,212 pairs). Parses came from the Bikel parser trained on the Penn English/Chinese Treebanks and were converted to dependency trees with Xia's (2001) method.
Test data: 206 sentences from the 2001 NIST MT development set, each with 4 English references.
Translation quality: cumulative NIST rose from 3.034 to 5.987 (+97.3%). Bleu rose from 0.109 to 0.132 (+21.1%) against IBM Model 4 decoded with ISI Rewrite.
Decoding speed: SDIG needed about 3 seconds for the whole test set, excluding parsing. The Rewrite decoder needed 8,102 seconds.
Structural divergence: on a small hand-aligned Chinese-English corpus of 826 pairs, 4.7% of dependencies were crossing, while 59.3% were broken. The authors argue this makes top-down EM grammar induction difficult.

Interesting ideas

Isomorphism at the fragment level. Requiring the two trees to match only at the level of multi-word fragments lets non-isomorphic structures be mapped without explicit insertion or deletion operations. This relaxation could help any cross-lingual tree alignment or annotation-projection task, for example projecting UD trees to Ukrainian.
Greedy partitioning instead of EM. The grammar is induced by heuristic, category-ordered splitting of tree pairs at confidently aligned word pairs, avoiding expensive EM over all possible substructures. This is a cheap, scalable option when exhaustive structure search is intractable.
Simple seed model. A plain bag-of-words IBM Model 1 is enough to drive structural decisions. A simple lexical model can therefore bootstrap a much richer structural one.
Packed forest for decoding. Storing alternative decompositions of the input in a shared forest keeps decoding linear in input size. This dynamic-programming design applies to other tree-structured inference problems.
Checking output length. Comparing average output length with human references showed why the baseline had higher individual n-gram precision despite lower overall scores. Length statistics are a quick diagnostic to report alongside Bleu or NIST.

Topics: Dependency parsing · Machine translation

Cite

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

@inproceedings{ding2005machine,
  title = {{Machine Translation Using Probabilistic Synchronous Dependency Insertion Grammars}},
  author = {Ding, Yuan and Palmer, Martha},
  booktitle = {Proceedings of the 43rd Annual Meeting of the Association for Computational Linguistics (ACL'05)},
  year = {2005},
  doi = {10.3115/1219840.1219907},
  url = {https://doi.org/10.3115/1219840.1219907}
}

References

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

Y. Al-Onaizan, J. Curin, M. Jahr, K. Knight, J. Lafferty, I. D. Melamed, F. Och, D. Purdy, N. A. Smith, and D. Yarowsky. 1999. Statistical machine translation. Technical report, CLSP, Johns Hopkins University. find
H. Alshawi, S. Bangalore, S. Douglas. 2000. Learning dependency translation models as collections of finite state head transducers. Comp. Linguistics, 26(1):45-60. find
Daniel M. Bikel. 2002. Design of a multi-lingual, parallel-processing statistical parsing engine. In HLT 2002. find
Peter F. Brown, Stephen A. Della Pietra, Vincent J. Della Pietra, and Robert Mercer. 1993. The mathematics of statistical machine translation: parameter estimation. Computational Linguistics, 19(2): 263-311. find
Michael John Collins. 1999. Head-driven Statistical Models for Natural Language Parsing. Ph.D. thesis, University of Pennsylvania, Philadelphia. find our card
Ding and Palmer. 2004a. Automatic Learning of Parallel Dependency Treelet Pairs. In First International Joint Conference on NLP (IJCNLP-04). find
Ding and Palmer. 2004b. Synchronous Dependency Insertion Grammars: A Grammar Formalism for Syntax Based Statistical MT. Workshop on Recent Advances in Dependency Grammars, COLING-04. find
Bonnie J. Dorr. 1994. Machine translation divergences: A formal description and proposed solution. Computational Linguistics, 20(4): 597-633. find our card
Jason Eisner. 2003. Learning non-isomorphic tree mappings for machine translation. In ACL-03. (companion volume), Sapporo, July. find our card
Heidi J. Fox. 2002. Phrasal cohesion and statistical machine translation. In Proceedings of EMNLP-02. find
Ulrich Germann, Michael Jahr, Kevin Knight, Daniel Marcu, and Kenji Yamada. 2001. Fast Decoding and Optimal Decoding for Machine Translation. ACL-01. find
Daniel Gildea. 2003. Loosely tree based alignment for machine translation. ACL-03, Japan. find
Jonathan Graehl and Kevin Knight. 2004. Training Tree Transducers. In NAACL/HLT-2004 find our card
Jan Hajic, et al. 2002. Natural language generation in the context of machine translation. Summer workshop final report, Center for Language and Speech Processing, Johns Hopkins University, Baltimore. find
Rebecca Hwa, Philip S. Resnik, Amy Weinberg, and Okan Kolak. 2002. Evaluating translational correspondence using annotation projection. ACL-02 find
Ali Ibrahim, Boris Katz, and Jimmy Lin. 2003. Extracting Structural Paraphrases from Aligned Monolingual Corpora. In Proceedings of the Second International Workshop on Paraphrasing (IWP 2003) find
Dan Melamed. 2004. Statistical Machine Translation by Parsing. In ACL-04, Barcelona, Spain. find
Dan Melamed. 2003. Multitext Grammars and Synchronous Parsers, In NAACL/HLT-2003. find
K. Papineni, S. Roukos, T. Ward, and W. Zhu. 2002. BLEU: a method for automatic evaluation of machine translation. ACL-02, Philadelphia, USA. find our card
Ryan McDonald, Koby Crammer and Fernando Pereira. 2005. Online Large-Margin Training of Dependency Parsers. ACL-05. find our card
Franz Josef Och and Hermann Ney. 2003. A Systematic Comparison of Various Statistical Alignment Models. Computational Linguistics, 29(1):19–51. find
S. M. Shieber and Y. Schabes. 1990. Synchronous Tree-Adjoining Grammars, Proceedings of the 13th COLING, pp. 253-258, August 1990. find
Dekai Wu. 1997. Stochastic inversion transduction grammars and bilingual parsing of parallel corpora. Computational Linguistics, 23(3):3-403. find our card
Fei Xia. 2001. Automatic grammar generation from two different perspectives. PhD thesis, U. of Pennsylvania. find
Kenji Yamada and Kevin Knight. 2001. A syntax based statistical translation model. ACL-01, France. find our card
Kenji Yamada and Kevin Knight. 2002. A decoder for syntax-based statistical MT. ACL-02, Philadelphi a. find