DTED: Evaluation of Machine Translation Structure Using Dependency Parsing and Tree Edit Distance

What it is about

DTED is a word-order metric. It dependency-parses the hypothesis and the reference, aligns nodes by a preprocessing step, and counts the tree edit distance between the two ordered trees, with renaming, deletion and insertion as the operations. The algorithm is an extension of an O(n^3) method, and the count is turned into a score between 0 and 1. System-level scores are weighted by the share of aligned nodes. On WMT 2015 human rankings the unflattened version correlates moderately, about as well as WER, which was the weakest baseline. Flattened trees do clearly worse, which the authors take as evidence that the structure carries the signal. The paper names its main gap: an edit count treats moving a node across the sentence as one step, however far it moves.

Ideas

• I1. Tree edit distance between the translator's output tree and the reference tree, restricted to aligned nodes, as a word-order count in normal mode. Both trees come from the reader, so no parser is needed on the output.
• I2. Add a move-distance term, the number of positions a node moves, which the paper itself names as missing. A verb moved to the end then counts more than a shift by one. This bears on the verb and subject order problem in Hebrew (open problem 7).
• I3. The flattened-tree result is a negative control for Mova. A version with the tree flattened must score clearly worse; if it does not, the structure term is not doing any work.

For Mova

The places are tools/translate, en/src/lin.rs (the order that the metric checks) and tools/macula (Hebrew trees). The method is count-based and deterministic, and the cubic cost is acceptable for verse-length trees.

Topics: Dependency parsing · Machine translation

Cite

The paper itself, not this card. BibTeX from the library's record of the work. DOI 10.18653/v1/w16-2340

@inproceedings{mccaffery2016dted,
  title = {{DTED: Evaluation of Machine Translation Structure Using Dependency Parsing and Tree Edit Distance}},
  author = {McCaffery, Martin and Nederhof, Mark-Jan},
  booktitle = {Proceedings of the First Conference on Machine Translation: Volume 2, Shared Task Papers},
  year = {2016},
  doi = {10.18653/v1/w16-2340},
  url = {https://doi.org/10.18653/v1/w16-2340}
}

References

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

2. Philip Bille. 2005. A survey on tree edit distance and related problems. Theoretical Computer Science, 337(1-3):217–239, jun. find
3. Philipp Koehn, Hieu Hoang, Alexandra Birch, Chris Callison-Burch, Marcello Federico, Nicola Bertoldi, Brooke Cowan, Wade Shen, Christine Moran, Richard Zens, Chris Dyer, Ondej Bojar, Alexandra Constantin, and Evan Herbst. 2007. Moses: Open source toolkit for statistical machine translation. In Proceedings of the 45th Annual Meeting of the ACL on Interactive Poster and Demonstration Sessions, pages 177–180. Association for Computational Linguistics. find
4. Alexandra Birch, Miles Osborne, and Philipp Koehn. 2008. Predicting success in machine translation. In Proceedings of the Conference on Empirical Methods in Natural Language Processing, pages 745– 754. find
5. Alexandra Birch, Miles Osborne, and Phil Blunsom. 2010. Metrics for MT evaluation: evaluating reordering. Machine Translation, 24(1):15–26, jan. find
6. Alon Lavie and Abhaya Agarwal. 2007. METEOR: An automatic metric for MT evaluation with high levels of correlation with human judgments. In Proceedings of the Second Workshop on Statistical Machine Translation, pages 228–231. find
7. Steven Bird. 2006. NLTK: The Natural Language Toolkit. In Proceedings of the COLING/ACL on Interactive presentation sessions (COLING-ACL ’06), pages 69–72. find
8. Gregor Leusch, Nicola Ueffing, and Hermann Ney. 2006. CDer: Efficient MT evaluation using block movements. In Proceedings of EACL-2006 (11th Conference of the European Chapter of the Association for Computational Linguistics), pages 241–248. find
9. Ondej Bojar, Rajen Chatterjee, Christian Federmann, Barry Haddow, Matthias Huck, Chris Hokamp, Philipp Koehn, Varvara Logacheva, Christof Monz, Matteo Negri, Matt Post, Carolina Scarton, Lucia Specia, and Marco Turchi. 2015. Findings of the 2015 Workshop on Statistical Machine Translation. In Proceedings of the 10th Workshop on Statistical Machine Translation, pages 1–46, Lisboa, Portugal. find
10. Vladimir Iosifovich Levenshtein. 1965. Binary codes capable of correcting deletions, insertions, and reversals. Soviet Physics Dokl., 10(1):707–710. find
11. Margaret M Conlon, Maria Falidas, Mary Jane Forde, John W Kennedy, S McIlwaine, and Joseph Stern. 1999. Inversion numbers of graphs. Graph Theory Notes of New York, 37:42–48. find
12. Ding Liu and Daniel Gildea. 2005. Syntactic features for evaluation of machine translation. In Proceedings of the ACL Workshop on Intrinsic and Extrinsic Evaluation Measures for Machine Translation and/or Summarization, pages 25–32. find our card
13. Daniel Dahlmeier, Chang Liu, and Hwee Tou Ng. 2011. TESLA at WMT 2011: Translation evaluation and tunable metric. In Proceedings of the Sixth Workshop on Statistical Machine Translation, pages 78–84. find
14. Sonja Nießen, Franz-Josef Och, Gregor Leusch, and Hermann Ney. 2000. An evaluation tool for machine translation: fast evaluation for MT research. LREC, pages 0–6. find
15. Erik D. Demaine, Shay Mozes, Benjamin Rossman, and Oren Weimann. 2009. An optimal decomposition algorithm for tree edit distance. ACM Transactions on Algorithms, 6:1–19. find
16. Joakim Nivre. 2003. An efficient algorithm for projective dependency parsing. Proceedings of the 8th International Workshop on Parsing Technologies, pages 149–160. find our card
17. George Doddington. 2002. Automatic evaluation of machine translation quality using n-gram co-occurrence statistics. In Proceedings of the Second International Conference on Human Language Technology Research, pages 138–145. find
18. Karolina Owczarzak, Josef van Genabith, and Andy Way. 2007. Labelled dependencies in machine translation evaluation. In Proceedings of the Second Workshop on Statistical Machine Translation, pages 104–111. find
19. Haim Gaifman. 1965. Dependency systems and phrase-structure systems. Information and Control, 8(3):304–337. find
20. Kishore Papineni, Salim Roukos, Todd Ward, and Wei-Jing Zhu. 2002. BLEU: a method for automatic evaluation of machine translation. In Proceedings of the 40th Annual Meeting on Association for Computational Linguistics, pages 311–318. find our card
21. Michael Gamon, Anthony Aue, and Martine Smets. 2005. Sentence-level MT evaluation without reference translations: Beyond language modeling. In Proceedings of the European Association for Machine Translation, pages 103–111. find
22. Maja Popović. 2011. Hjerson: An open source tool for automatic error classification of machine translation output. The Prague Bulletin of Mathematical Linguistics, 96:59–67. find
23. Nizar Habash and Ahmed Elkholy. 2008. SEPIA: Surface Span Extension to Syntactic Dependency Precision-based MT Evaluation. In Proceedings of the NIST Metrics for Machine Translation Workshop C J Van Rijsbergen. 1979. Information Retrieval. Butterworth-Heinemann, Newton, MA, USA, 2nd edition. find
24. Matthew Snover, Bonnie Dorr, College Park, Richard Schwartz, Linnea Micciulla, and John Makhoul. 2006. A Study of Translation Edit Rate with Targeted Human Annotation. In Proceedings of the 7th Conference of the Association for Machine Translation in the Americas,, number August, pages 223– 231, Cambridge, Massachusetts. find our card
25. David Talbot, Hideto Kazawa, Hiroshi Ichikawa, Jason Katz-Brown, Masakazu Seno, and Franz-Josef Och. 2011. A lightweight evaluation framework for machine translation reordering. In Proceedings of the Sixth Workshop on Statistical Machine Translation, pages 12–21. Association for Computational Linguistics. find
26. C Tillmann, S Vogel, H Ney, A. Zubiaga, and H. Sawaf. 1997. Accelerated DP Based Search for Statistical Translation. Fifth European Conference on Speech Communication and Technology, pages 2667–2670. find
27. David Vilar, Jia Xu, Luis Fernando D’Haro, and Hermann Ney. 2006. Error analysis of statistical machine translation output. In Proceedings of the Conference on Language Resources and Evaluation, pages 697–702, Genoa. find our card
28. Hui Yu, Xiaofeng Wu, Jun Xie, Wenbin Jiang, Qun Liu, and Shouxun Lin. 2014. RED: A Reference Dependency Based MT Evaluation Metric. In Proceedings of COLING 2014, the 25th International Conference on Computational Linguistics: Technical Papers, pages 2042–2051. find our card
29. Daniel Zeman, Mark Fishel, Jan Berka, and Ondej Bojar. 2011. Addicter: What is Wrong with My Translations? The Prague Bulletin of Mathematical Linguistics, (96):79–88. find
30. Kaizhong Zhang and Dennis Shasha. 1989. Simple Fast Algorithms for the Editing Distance between Trees and Related Problems. SIAM Journal on Computing, 18(6):1245–1262. find

This page in Markdown → https://md.mova.elamur.ai/free/en/docs/papers/mccaffery-2016-dted-evaluation-machine-translation-structure/