Mova0.5 pre-release⌕
☰
home / docs / papers / English / Inherent Dependency Displacement Bias of Transition-Based Algorithms

Inherent Dependency Displacement Bias of Transition-Based Algorithms

What it is about

The paper defines an algorithm's inherent dependency displacement distribution: the distribution of signed head-dependent distances that the algorithm produces when it picks transitions at random, which needs no training data. It compares that distribution with a treebank's observed displacements using the earth mover's distance. The data are 26 UD v2.1 treebanks with five MaltParser algorithms, three projective and two non-projective. Per-displacement precision and recall show no significant difference between the projective algorithms. Inside 10–12-token sentence bins the distance correlates strongly with each algorithm's UAS relative to the average, but over unbinned sentences the correlation is weak (r = -0.045 for projective and -0.252 for non-projective, neither significant). The paper suggests that the fit between an algorithm's bias and a corpus can be estimated from corpus statistics alone.

Ideas

For Mova

The chapter is 20-syntax-overview, and 37-register-and-variation matters because sentence length and displacement change with register. The code is tools/treeagree, the annot crate's silver corpus, and the eval commands in en. Measure first: the earth mover's distance between silver and gold per length bin (idea I1), since it needs only the trees already on disk.

Topics: Dependency parsing · Treebanks

Cite

The paper itself, not this card. BibTeX from the library's record of the work. arXiv 2003.14282

@inproceedings{anderson2020inherent,
  title = {{Inherent Dependency Displacement Bias of Transition-Based Algorithms}},
  author = {Anderson, Mark and Gómez-Rodríguez, Carlos},
  booktitle = {Proceedings of the Twelfth Language Resources and Evaluation Conference},
  year = {2020},
  eprint = {2003.14282},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2003.14282}
}

References

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

  1. Ballesteros, M. and Nivre, J. (2012). MaltOptimizer: an optimization tool for MaltParser. In Proceedings of the Demonstrations at the 13th Conference of the European Chapter of the Association for Computational Linguistics, pages 58–62. Association for Computational Linguistics. find
  2. Ballesteros, M. and Nivre, J. (2013). Going to the roots of dependency parsing. Computational Linguistics, 39(1):5–13. find
  3. Buch-Kromann, M. (2006). Discontinuous grammar: A dependency-based model of human parsing and language learning. Ph.D. thesis, Copenhagen Business School. find
  4. Chen, D. and Manning, C. (2014). A fast and accurate dependency parser using neural networks. In Proceedings of the 2014 conference on empirical methods in natural language processing (EMNLP), pages 740–750. de Lhoneux, M., Stymne, S., and Nivre, J. (2017). Old school vs. new school: Comparing trans… find our card
  5. Dickinson, M. (2010). Detecting errors in automatically-parsed dependency relations. In Proceedings of the 48th Annual Meeting of the Association for Computational Linguistics, pages 729–738. find
  6. Eisner, J. and Smith, N. A. (2010). Favor short dependencies: Parsing with soft and hard constraints on dependency length. In Trends in Parsing Technology, pages 121–150. Springer. Fernández-González, D. and Gómez-Rodrı́guez, C. (2018). Non-projective dependency parsing with non-local transitions… find
  7. Ferrer-i-Cancho, R. and Liu, H. (2014). The risks of mixing dependency lengths from sequences of different length. Glottotheory, 5(2):143–155. find
  8. Ferrer-i-Cancho, R. (2004). Euclidean distance between syntactically linked words. Physical Review E, 70(5):056135. find
  9. Futrell, R., Mahowald, K., and Gibson, E. (2015). Large-scale evidence of dependency length minimization in 37 languages. Proceedings of the National Academy of Sciences, 112(33):10336–10341. find
  10. Gibson, E. (2000). The dependency locality theory: A distance-based theory of linguistic complexity. Image, language, brain, 2000:95–126. find
  11. Gildea, D. and Temperley, D. (2010). Do grammars minimize dependency length? Cognitive Science, 34(2):286– 310. find
  12. Goldberg, Y. and Elhadad, M. (2010). An efficient algorithm for easy-first non-directional dependency parsing. In Human Language Technologies: The 2010 Annual Conference of the North American Chapter of the Association for Computational Linguistics, pages 742–750. Association for Computational Lingu… find
  13. Gulordava, K. and Merlo, P. (2015). Diachronic trends in word order freedom and dependency length in dependency-annotated corpora of Latin and Ancient Greek. In Proceedings of the third international conference on dependency linguistics (Depling 2015), pages 121–130. find
  14. Gulordava, K. and Merlo, P. (2016). Multi-lingual dependency parsing evaluation: a large-scale analysis of word order properties using artificial data. Transactions of the Association for Computational Linguistics, 4:343–356. find
  15. Hudson, R. (2017). Cross-language diversity, head-direction and grammars. comment on “Dependency distance: A new perspective on syntactic patterns in natural languages” by Haitao Liu et al. Physics of life reviews, 21:204–206. find
  16. Jiang, J. and Liu, H. (2015). The effects of sentence length on dependency distance, dependency direction and the implications–based on a parallel english–chinese dependency treebank. Language Sciences, 50:93–104. find
  17. Kirilin, A. and Versley, Y. (2015). What is hard in universal Dependency parsing. In Proceedings of the 6th Workshop on Statistical Parsing of Morphologically Rich Languages (SPMRL 2015), pages 31–38. find
  18. Kulmizev, A., de Lhoneux, M., Gontrum, J., Fano, E., and Nivre, J. (2019). Deep contextualized word embeddings in transition-based and graph-based dependency parsing - a tale of two parsers revisited. In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9… find
  19. Liu, H., Xu, C., and Liang, J. (2017). Dependency distance: a new perspective on syntactic patterns in natural languages. Physics of life reviews, 21:171–193. find
  20. Liu, H. (2007). Probability distribution of dependency distance. Glottometrics, 15:1–12. find
  21. Liu, H. (2008). Dependency distance as a metric of language comprehension difficulty. Journal of Cognitive Science, 9(2):159–191. find
  22. Liu, H. (2010). Dependency direction as a means of word-order typology: A method based on dependency treebanks. Lingua, 120(6):1567–1578. find
  23. McDonald, R. and Nivre, J. (2011). Analyzing and integrating dependency parsers. Computational Linguistics, 37(1):197–230. find
  24. McDonald, R. and Satta, G. (2007). On the complexity of non-projective data-driven dependency parsing. In Proceedings of the 10th International Conference on Parsing Technologies, pages 121–132. Association for Computational Linguistics. find
  25. Mielke, S. J., Cotterell, R., Gorman, K., Roark, B., and Eisner, J. (2019). What kind of language is hard to language-model? In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pages 4975–4989, Florence, Italy, July. Association for Computational Linguistics.… find
  26. Nivre, J. (2008). Algorithms for deterministic incremental dependency parsing. Computational Linguistics, 34(4):513–553. find our card
  27. Rehbein, I., Steen, J., Do, B.-N., and Frank, A. (2017). Universal Dependencies are hard to parse–or are they? In Proceedings of the Fourth International Conference on Dependency Linguistics (Depling 2017), pages 218– 228. find
  28. Rubner, Y., Tomasi, C., and Guibas, L. J. (1998). A metric for distributions with applications to image databases. In Proceedings of the Sixth International Conference on Computer Vision, ICCV ’98, pages 59–, Washington, DC, USA. find
  29. IEEE Computer Society. Schwartz, R., Abend, O., and Rappoport, A. (2012). Learnability-based syntactic annotation design. Proceedings of COLING 2012, pages 2405–2422. Straka, M. and Straková, J. (2017). Tokenizing, POS tagging, Lemmatizing and Parsing UD 2.0 with UDPipe. In Proceedings of the CoNLL… find
  30. Temperley, D. and Gildea, D. (2018). Minimizing syntactic dependency lengths: typological/cognitive universal? Annual Review of Linguistics, 4:67–80. find

This page in Markdown → https://md.mova.elamur.ai/free/en/docs/papers/ud-2020-anderson-inherent-dependency-displacement-bias-transition/