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.

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

This page in Markdown → https://md.mova.elamur.ai/free/en/docs/papers/ding-2005-machine-translation-probabilistic-synchronous-dependency/