Tree-distance and some other variants of evalb

What it is about

The question is whether the standard evalb scores (labelled precision, recall and F1 over constituent spans) give a stable picture of parser quality. The author compares them with a tree-distance measure (Zhang and Shasha) that counts deletions, insertions and swaps under mappings that keep left-to-right order and ancestry. Six parsers are scored on section 23 of the Penn Treebank, with whole-tree and roof-only variants and micro and macro averaging. The ranking of the parsers changes with the measure. The ranking of parses for one parser also changes, and the two measures disagree on the pairwise order of parses in about 4-5% of pairs. The author argues that tree distance avoids penalising a single attachment error at every node on the path.

Ideas

I1. Tree distance for UD trees in en parse-eval (a new flag): an edit cost over a mapping that keeps head-dependent order and ancestry, with labels as the swap test. Measure on EWT test: the ranking of Mova configurations (own tags against gold tags, beam 1 against beam 8) under LAS and under this cost.
I2. Averaging: print both the pooled and the per-sentence average in en parse-eval. Measure whether the ordering of the same configurations changes on EWT test and on PUD.
I3. Ranking check before a claim: compute the rank agreement (Kendall tau) between LAS and the tree-distance cost over sentences in each en folds dev fold. A gain that holds for only one measure is not reported as a gain.

For Mova

The chapter is 20. Syntax: the Universal Dependencies frame. The code is en/src/parse.rs, the en parse-eval command and en folds. Mova's trees are dependency trees, so evalb's constituent spans do not apply; the idea is an analogue, not a copy of the paper's numbers, which are for Penn Treebank constituency parsers. The cost must stay deterministic and CPU only, and two identical runs come before any claim.

Cite

The paper itself, not this card. BibTeX from the library's record of the work. DOI 10.63317/3gozzi5qoifm

@inproceedings{emms2008tree,
  title = {{Tree-distance and some other variants of evalb}},
  author = {Emms, Martin},
  booktitle = {Proceedings of the Sixth International Conference on Language Resources and Evaluation (LREC'08)},
  year = {2008},
  doi = {10.63317/3gozzi5qoifm},
  url = {https://doi.org/10.63317/3gozzi5qoifm}
}

References

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

Srinivas Bangalore, Anoop Sarkar, Christy Doran, and Beth-Ann Hockey. 1998. Grammar and parser evaluation in the xtag project. In Proceedings of LREC Workshop on Evaluation of Parsing Systems. find
Philip Bille. 2005. A survey on tree edit distance and related problems. Theor. Computer. Sci., 337(1-3):217– 239. find
Ezra Black, Steven P. Abney, D. Flickenger, Claudia Gdaniec, Ralph Grishman, P. Harrison, Donald Hindle, Robert Ingria, Frederick Jelinek, Judith L. Klavans, Mark Liberman, Mitchell P. Marcus, Salim Roukos, Beatrice Santorini, and Tomek Strzalkowski. 1991. A procedure for quantitatively comparing the syntactic coverage of english grammars. In Proceedings of HLT. find
Eugene Charniak. 2000. A maximum-entropy-inspired parser. In Proceedings of NAACL 2000, pages 132–139. find
Michael Collins. 1997. Three generative, lexicalized models for statistical parsing. In Proceedings of ACL 97. find
Michael Collins. 2003. Head-driven statistical models for natural language parsing. Computational Linguistics, 29(4):589–637. find our card
Martin Emms. 2006a. Clustering by tree distance for parse tree normalisation. In Proceedings of NLUCS 2006, pages 91–100. find
Martin Emms. 2006b. Variants of tree similarity in a question answering task. In Proceedings of the Workshop on Linguistic Distances, pages 100–108, Sydney, Australia, July. Association for Computational Linguistics. find
Martin Emms. 2008. Tree distance software at www.cs.tcd.ie/Martin.Emms/tdist. find
Milen Kouylekov and Bernardo Magnini. 2005. Recognizing textual entailment with tree edit distance algorithms. In Ido Dagan, Oren Glickman, and Bernardo Magnini, editors, Pascal Challenges Workshop on Recognising Textual Entailment. find
K.Zhang and D.Shasha. 1989. Simple fast algorithms for the editing distance between trees and related problems. SIAM Journal of Computing, 18:1245–1262. find
Mitchell P. Marcus, Beatrice Santorini, and Mary Ann Marcinkiewicz. 1994. Building a large annotated corpus of english: The penn treebank. Computational Linguistics, 19(2):313–330. find our card
Slav Petrov, Leon Barret, Romain Thibaux, and Dan Klein. 2006. Learning accurate, compact, and interpretable tree annotation. In Proceedings of COLING/ACL 2006, pages 433–440. find our card
Vasin Punyakanok, Dan Roth, and Wen tau Yih. 2004. Natural language inference via dependency tree mapping: An application to question answering. Computational Linguistics. find
Ines Rehbein and Josef van Genabith. 2007. Treebank annotation schemes and parser evaluation for German. In Proceedings of the 2007 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning (EMNLP-CoNLL), pages 630–639. find
B. Roark. 2002. Evaluating parser accuracy using edit distance. In Proceedings of the LREC 2002 workshop: Beyond PARSEVAL: Towards Improved Evaluation Measures for Parsing Systems, pages 30–36. find
Geoffrey Sampson and Anna Babarczy. 2003. A test of the leaf-ancestor metric for parse accuracy. Nat. Lang. Eng., 9(4):365–380. find
Satoshi Sekine and Michael Collins. 1997. evalb software at nlp.cs.nyu.edu/evalb. find
S.Siegel and N.J.Castellan. 1988. Non-Parametric Statistics for the Behavioural Sciences. McGraw-Hill. find
C. J. van Rijsbergen. 1979. Information Retrieval, 2nd edition. Dept. of Computer Science, University of Glasgow. find
V.I.Levenshtein. 1966. Binary codes capable of correcting insertions and reversals. Sov. Phys. Dokl, 10:707–710. find

This page in Markdown → https://md.mova.elamur.ai/free/en/docs/papers/lingbulk-2008-emms-tree-distance-some-other-variants/