[Mova](https://md.mova.elamur.ai/free/en/) · [this page in HTML](https://mova.elamur.ai/free/en/docs/papers/mccaffery-2016-dted-evaluation-machine-translation-structure/)

[home](https://md.mova.elamur.ai/free/en/) / [docs](https://md.mova.elamur.ai/free/en/docs/) / [papers](https://md.mova.elamur.ai/free/en/docs/papers/) / [Machine translation](https://md.mova.elamur.ai/free/en/docs/papers/mtrans/) / DTED: Evaluation of Machine Translation Structure Using Dependency Parsing and Tree Edit Distance

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

**Authors:** Martin McCaffery, Mark-Jan Nederhof · **Year:** 2016 · **Venue:** Proceedings of the First Conference on Machine Translation: Volume 2, Shared Task Papers **Link:** [aclanthology.org/W16-2340](https://aclanthology.org/W16-2340/) · **Licence:** [CC BY 4.0](https://creativecommons.org/licenses/by/4.0/)

[**7** citations](https://openalex.org/works?filter=cites:W2509854663) openalex · 2026-10-18[**2** citations in our library](https://md.mova.elamur.ai/free/en/docs/papers/cited-by/mccaffery-2016-dted-evaluation-machine-translation-structure/) of the 140673 papers whose bibliographies we read[Proceedings of the First Conference on Machine Translation: Volume 2, Shared Task Papers](https://aclanthology.org/volumes/W16-23/)[licence](https://creativecommons.org/licenses/by/4.0/)

- [Publisher's page](https://aclanthology.org/W16-2340/)
- [PDF](https://aclanthology.org/W16-2340.pdf)
- [DOI 10.18653/v1/w16-2340](https://doi.org/10.18653/v1/w16-2340)
- [OpenAlex](https://openalex.org/W2509854663)

**Authors (2)**

1. [Martin McCaffery](https://openalex.org/A5030865635) h 2 · 13 citations · 9 works
2. [Mark-Jan Nederhof](https://openalex.org/A5088112856) [ORCID](https://orcid.org/0000-0002-1845-6829) · h 18 · 1281 citations · 124 works

Citations and author metrics from openalex (2026-10-18); authors with the same name are not always told apart.

## 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](https://md.mova.elamur.ai/free/en/docs/papers/topics/dependency-parsing/) · [Machine translation](https://md.mova.elamur.ai/free/en/docs/papers/topics/machine-translation/)

## Cite

The paper itself, not this card. BibTeX from the library's record of the work. [DOI 10.18653/v1/w16-2340](https://doi.org/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}
}
```

- [← previous Tangled up in BLEU: Reevaluating the Evaluation of Automatic Machine Translation Evaluation Metrics](https://md.mova.elamur.ai/free/en/docs/papers/mathur-2020-tangled-up-bleu-reevaluating-evaluation/)
- [next → Design of LMT: A Prolog-Based Machine Translation System](https://md.mova.elamur.ai/free/en/docs/papers/mccord-1989-design-lmt-prolog-based-machine/)
- [↑ back to Machine translation](https://md.mova.elamur.ai/free/en/docs/papers/mtrans/)

## 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.

1. Philip Bille. 2005. A survey on tree edit distance and related problems. Theoretical Computer Science, 337(1-3):217–239, jun. [find](https://scholar.google.com/scholar?q=Philip+Bille%2E+2005%2E+A+survey+on+tree+edit+distance+and+related+problems%2E+Theoretical+Computer+Science%2C+337%281%2D3%29%3A217%E2%80%93239%2C+jun%2E)
2. 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](https://scholar.google.com/scholar?q=Philipp+Koehn%2C+Hieu+Hoang%2C+Alexandra+Birch%2C+Chris+Callison%2DBurch%2C+Marcello+Federico%2C+Nicola+Bertoldi%2C+Brooke+Cowan%2C+Wade+Shen%2C+Christine+Moran%2C+Richard+Zens%2C+Chris+Dyer%2C+Ondej+Bojar%2C+Alexandra+Constan)
3. 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](https://scholar.google.com/scholar?q=Alexandra+Birch%2C+Miles+Osborne%2C+and+Philipp+Koehn%2E+2008%2E+Predicting+success+in+machine+translation%2E+In+Proceedings+of+the+Conference+on+Empirical+Methods+in+Natural+Language+Processing%2C+pages+745%E2%80%93+754)
4. Alexandra Birch, Miles Osborne, and Phil Blunsom. 2010. Metrics for MT evaluation: evaluating reordering. Machine Translation, 24(1):15–26, jan. [find](https://scholar.google.com/scholar?q=Alexandra+Birch%2C+Miles+Osborne%2C+and+Phil+Blunsom%2E+2010%2E+Metrics+for+MT+evaluation%3A+evaluating+reordering%2E+Machine+Translation%2C+24%281%29%3A15%E2%80%9326%2C+jan%2E)
5. 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](https://scholar.google.com/scholar?q=Alon+Lavie+and+Abhaya+Agarwal%2E+2007%2E+METEOR%3A+An+automatic+metric+for+MT+evaluation+with+high+levels+of+correlation+with+human+judgments%2E+In+Proceedings+of+the+Second+Workshop+on+Statistical+Machine+Tr)
6. 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](https://scholar.google.com/scholar?q=Steven+Bird%2E+2006%2E+NLTK%3A+The+Natural+Language+Toolkit%2E+In+Proceedings+of+the+COLING%2FACL+on+Interactive+presentation+sessions+%28COLING%2DACL+%E2%80%9906%29%2C+pages+69%E2%80%9372%2E)
7. 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](https://scholar.google.com/scholar?q=Gregor+Leusch%2C+Nicola+Ueffing%2C+and+Hermann+Ney%2E+2006%2E+CDer%3A+Efficient+MT+evaluation+using+block+movements%2E+In+Proceedings+of+EACL%2D2006+%2811th+Conference+of+the+European+Chapter+of+the+Association+for+C)
8. 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](https://scholar.google.com/scholar?q=Ondej+Bojar%2C+Rajen+Chatterjee%2C+Christian+Federmann%2C+Barry+Haddow%2C+Matthias+Huck%2C+Chris+Hokamp%2C+Philipp+Koehn%2C+Varvara+Logacheva%2C+Christof+Monz%2C+Matteo+Negri%2C+Matt+Post%2C+Carolina+Scarton%2C+Lucia+Specia%2C)
9. Vladimir Iosifovich Levenshtein. 1965. Binary codes capable of correcting deletions, insertions, and reversals. Soviet Physics Dokl., 10(1):707–710. [find](https://scholar.google.com/scholar?q=Vladimir+Iosifovich+Levenshtein%2E+1965%2E+Binary+codes+capable+of+correcting+deletions%2C+insertions%2C+and+reversals%2E+Soviet+Physics+Dokl%2E%2C+10%281%29%3A707%E2%80%93710%2E)
10. 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](https://scholar.google.com/scholar?q=Margaret+M+Conlon%2C+Maria+Falidas%2C+Mary+Jane+Forde%2C+John+W+Kennedy%2C+S+McIlwaine%2C+and+Joseph+Stern%2E+1999%2E+Inversion+numbers+of+graphs%2E+Graph+Theory+Notes+of+New+York%2C+37%3A42%E2%80%9348%2E)
11. 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](https://scholar.google.com/scholar?q=Ding+Liu+and+Daniel+Gildea%2E+2005%2E+Syntactic+features+for+evaluation+of+machine+translation%2E+In+Proceedings+of+the+ACL+Workshop+on+Intrinsic+and+Extrinsic+Evaluation+Measures+for+Machine+Translation+an) [our card](https://md.mova.elamur.ai/free/en/docs/papers/liu-2005-syntactic-features-evaluation-machine-translation/)
12. 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](https://scholar.google.com/scholar?q=Daniel+Dahlmeier%2C+Chang+Liu%2C+and+Hwee+Tou+Ng%2E+2011%2E+TESLA+at+WMT+2011%3A+Translation+evaluation+and+tunable+metric%2E+In+Proceedings+of+the+Sixth+Workshop+on+Statistical+Machine+Translation%2C+pages+78%E2%80%9384%2E)
13. 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](https://scholar.google.com/scholar?q=Sonja+Nie%C3%9Fen%2C+Franz%2DJosef+Och%2C+Gregor+Leusch%2C+and+Hermann+Ney%2E+2000%2E+An+evaluation+tool+for+machine+translation%3A+fast+evaluation+for+MT+research%2E+LREC%2C+pages+0%E2%80%936%2E)
14. 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](https://scholar.google.com/scholar?q=Erik+D%2E+Demaine%2C+Shay+Mozes%2C+Benjamin+Rossman%2C+and+Oren+Weimann%2E+2009%2E+An+optimal+decomposition+algorithm+for+tree+edit+distance%2E+ACM+Transactions+on+Algorithms%2C+6%3A1%E2%80%9319%2E)
15. Joakim Nivre. 2003. An efficient algorithm for projective dependency parsing. Proceedings of the 8th International Workshop on Parsing Technologies, pages 149–160. [find](https://scholar.google.com/scholar?q=Joakim+Nivre%2E+2003%2E+An+efficient+algorithm+for+projective+dependency+parsing%2E+Proceedings+of+the+8th+International+Workshop+on+Parsing+Technologies%2C+pages+149%E2%80%93160%2E) [our card](https://md.mova.elamur.ai/free/en/docs/papers/parsers-2003-nivre-efficient-algorithm-projective-dependency-parsing/)
16. 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](https://scholar.google.com/scholar?q=George+Doddington%2E+2002%2E+Automatic+evaluation+of+machine+translation+quality+using+n%2Dgram+co%2Doccurrence+statistics%2E+In+Proceedings+of+the+Second+International+Conference+on+Human+Language+Technology+R)
17. 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](https://scholar.google.com/scholar?q=Karolina+Owczarzak%2C+Josef+van+Genabith%2C+and+Andy+Way%2E+2007%2E+Labelled+dependencies+in+machine+translation+evaluation%2E+In+Proceedings+of+the+Second+Workshop+on+Statistical+Machine+Translation%2C+pages+104)
18. Haim Gaifman. 1965. Dependency systems and phrase-structure systems. Information and Control, 8(3):304–337. [find](https://scholar.google.com/scholar?q=Haim+Gaifman%2E+1965%2E+Dependency+systems+and+phrase%2Dstructure+systems%2E+Information+and+Control%2C+8%283%29%3A304%E2%80%93337%2E)
19. 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](https://scholar.google.com/scholar?q=Kishore+Papineni%2C+Salim+Roukos%2C+Todd+Ward%2C+and+Wei%2DJing+Zhu%2E+2002%2E+BLEU%3A+a+method+for+automatic+evaluation+of+machine+translation%2E+In+Proceedings+of+the+40th+Annual+Meeting+on+Association+for+Computat) [our card](https://md.mova.elamur.ai/free/en/docs/papers/papineni-2002-bleu-method-automatic-evaluation-machine/)
20. 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](https://scholar.google.com/scholar?q=Michael+Gamon%2C+Anthony+Aue%2C+and+Martine+Smets%2E+2005%2E+Sentence%2Dlevel+MT+evaluation+without+reference+translations%3A+Beyond+language+modeling%2E+In+Proceedings+of+the+European+Association+for+Machine+Trans)
21. 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](https://scholar.google.com/scholar?q=Maja+Popovic%CC%81%2E+2011%2E+Hjerson%3A+An+open+source+tool+for+automatic+error+classification+of+machine+translation+output%2E+The+Prague+Bulletin+of+Mathematical+Linguistics%2C+96%3A59%E2%80%9367%2E)
22. 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](https://scholar.google.com/scholar?q=Nizar+Habash+and+Ahmed+Elkholy%2E+2008%2E+SEPIA%3A+Surface+Span+Extension+to+Syntactic+Dependency+Precision%2Dbased+MT+Evaluation%2E+In+Proceedings+of+the+NIST+Metrics+for+Machine+Translation+Workshop+C+J+Van+R)
23. 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](https://scholar.google.com/scholar?q=Matthew+Snover%2C+Bonnie+Dorr%2C+College+Park%2C+Richard+Schwartz%2C+Linnea+Micciulla%2C+and+John+Makhoul%2E+2006%2E+A+Study+of+Translation+Edit+Rate+with+Targeted+Human+Annotation%2E+In+Proceedings+of+the+7th+Confer) [our card](https://md.mova.elamur.ai/free/en/docs/papers/snover-2006-study-translation-edit-rate-targeted/)
24. 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](https://scholar.google.com/scholar?q=David+Talbot%2C+Hideto+Kazawa%2C+Hiroshi+Ichikawa%2C+Jason+Katz%2DBrown%2C+Masakazu+Seno%2C+and+Franz%2DJosef+Och%2E+2011%2E+A+lightweight+evaluation+framework+for+machine+translation+reordering%2E+In+Proceedings+of+the+)
25. 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](https://scholar.google.com/scholar?q=C+Tillmann%2C+S+Vogel%2C+H+Ney%2C+A%2E+Zubiaga%2C+and+H%2E+Sawaf%2E+1997%2E+Accelerated+DP+Based+Search+for+Statistical+Translation%2E+Fifth+European+Conference+on+Speech+Communication+and+Technology%2C+pages+2667%E2%80%932670%2E)
26. 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](https://scholar.google.com/scholar?q=David+Vilar%2C+Jia+Xu%2C+Luis+Fernando+D%E2%80%99Haro%2C+and+Hermann+Ney%2E+2006%2E+Error+analysis+of+statistical+machine+translation+output%2E+In+Proceedings+of+the+Conference+on+Language+Resources+and+Evaluation%2C+pages) [our card](https://md.mova.elamur.ai/free/en/docs/papers/vilar-2006-error-analysis-statistical-machine-translation/)
27. 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](https://scholar.google.com/scholar?q=Hui+Yu%2C+Xiaofeng+Wu%2C+Jun+Xie%2C+Wenbin+Jiang%2C+Qun+Liu%2C+and+Shouxun+Lin%2E+2014%2E+RED%3A+A+Reference+Dependency+Based+MT+Evaluation+Metric%2E+In+Proceedings+of+COLING+2014%2C+the+25th+International+Conference+on+) [our card](https://md.mova.elamur.ai/free/en/docs/papers/yu-2014-red-reference-dependency-based-mt/)
28. 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](https://scholar.google.com/scholar?q=Daniel+Zeman%2C+Mark+Fishel%2C+Jan+Berka%2C+and+Ondej+Bojar%2E+2011%2E+Addicter%3A+What+is+Wrong+with+My+Translations%3F+The+Prague+Bulletin+of+Mathematical+Linguistics%2C+%2896%29%3A79%E2%80%9388%2E)
29. 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](https://scholar.google.com/scholar?q=Kaizhong+Zhang+and+Dennis+Shasha%2E+1989%2E+Simple+Fast+Algorithms+for+the+Editing+Distance+between+Trees+and+Related+Problems%2E+SIAM+Journal+on+Computing%2C+18%286%29%3A1245%E2%80%931262%2E)