Non-Projective Dependency Parsing using Spanning Tree Algorithms

What it is about

The paper casts weighted dependency parsing as a search for maximum spanning trees in a directed graph. Eisner's algorithm covers all projective trees in O(n^3), and the Chu-Liu-Edmonds algorithm covers non-projective trees in O(n^2), with the same edge scores. The scores are trained with online large-margin learning (MIRA) on the Prague Dependency Treebank, where fewer than 2% of Czech dependencies are non-projective. The non-projective decoder gains up to 1.1 points of attachment accuracy over the projective one (factored MIRA 84.4% on all of PDT) and parses faster. On projective English trees from the Penn Treebank, the spanning-tree decoder is slightly worse than Eisner's (90.2% against 90.9%).

Ideas

I1. gparse: add a Chu-Liu-Edmonds decoder next to gparse/src/eisner.rs, run on the same biaffine arc scores and selected by a flag; measure LAS against Eisner on EWT test and on GUM test (test only).
I2. en: measure the ceiling of the projective arc-standard parser as the share of gold EWT test arcs that are non-projective and the UAS lost to projectivity, with en parse-eval; keep projective decoding if the loss is small.
I3. treeagree: report the share of non-projective content (non-punctuation) arcs in the silver corpus, so the projectivity gate rests on numbers rather than assumption.

For Mova

The non-projective cases in the paper are extraposed relative clauses, such as "a dog yesterday which was a Yorkshire Terrier", so the chapters to read are 21-clause-structure and 25-relative-clauses, with 29-ellipsis-word-order-information-structure for other displacement. The code touched is en/src/parse.rs (projective only), gparse/src/eisner.rs and tools/treeagree. Measure first: the non-projective arc share and the projective ceiling on EWT test (idea I2).

Topics: Dependency parsing

Cite

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

@inproceedings{mcdonald2005non,
  title = {{Non-Projective Dependency Parsing using Spanning Tree Algorithms}},
  author = {McDonald, Ryan and Pereira, Fernando and Ribarov, Kiril and Hajič, Jan},
  booktitle = {Proceedings of Human Language Technology Conference and Conference on Empirical Methods in Natural Language Processing},
  year = {2005},
  url = {https://aclanthology.org/H05-1066/}
}

References

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

Y.J. Chu and T.H. Liu. 1965. On the shortest arborescence of a directed graph. Science Sinica, 14:1396– 1400. find
M. Collins, J. Hajič, L. Ramshaw, and C. Tillmann. 1999. A statistical parser for Czech. In Proc. ACL. find
M. Collins. 2002. Discriminative training methods for hidden Markov models: Theory and experiments with perceptron algorithms. In Proc. EMNLP. find our card
T.H. Cormen, C.E. Leiserson, and R.L. Rivest. 1990. Introduction to Algorithms. MIT Press/McGraw-Hill. find
K. Crammer and Y. Singer. 2003. Ultraconservative online algorithms for multiclass problems. JMLR. find
K. Crammer, O. Dekel, S. Shalev-Shwartz, and Y. Singer. 2003. Online passive aggressive algorithms. In Proc. NIPS. find
K. Crammer, R. McDonald, and F. Pereira. 2004. New large margin algorithms for structured prediction. In Learning with Structured Outputs Workshop (NIPS). find
A. Culotta and J. Sorensen. 2004. Dependency tree kernels for relation extraction. In Proc. ACL. find
Y. Ding and M. Palmer. 2005. Machine translation using probabilistic synchronous dependency insertion grammars. In Proc. ACL. find our card
J. Edmonds. 1967. Optimum branchings. Journal of Research of the National Bureau of Standards, 71B:233– 240. find
J. Eisner. 1996. Three new probabilistic models for dependency parsing: An exploration. In Proc. COLING. find our card
J. Hajič, E. Hajicova, P. Pajas, J. Panevova, P. Sgall, and B. Vidova Hladka. 2001. The Prague Dependency Treebank 1.0 CDROM. Linguistics Data Consortium Cat. No. LDC2001T10. find
J. Hajič. 1998. Building a syntactically annotated corpus: The Prague dependency treebank. Issues of Valency and Meaning, pages 106–132. find
H. Hirakawa. 2001. Semantic dependency analysis method for Japanese based on optimum tree search algorithm. In Proc. of PACLING. find
Klaus-U. Höffgen. 1993. Learning and robust learning of product distributions. In Proceedings of COLT’93, pages 77–83. find
W. Hou. 1996. Algorithm for finding the first k shortest arborescences of a digraph. Mathematica Applicata, 9(1):1–4. find
R. Hudson. 1984. Word Grammar. Blackwell. find
G. Leonidas. 2003. Arborescence optimization problems solvable by Edmonds’ algorithm. Theoretical Computer Science, 301:427 – 437. find
M. Marcus, B. Santorini, and M. Marcinkiewicz. 1993. Building a large annotated corpus of English: the Penn Treebank. Computational Linguistics, 19(2):313–330. find our card
R. McDonald, K. Crammer, and F. Pereira. 2005. Online large-margin training of dependency parsers. In Proc. ACL. find our card
J. Nivre and J. Nilsson. 2005. Pseudo-projective dependency parsing. In Proc. ACL. find
J. Nivre and M. Scholz. 2004. Deterministic dependency parsing of english text. In Proc. COLING. find our card
Y. Shinyama, S. Sekine, K. Sudo, and R. Grishman. 2002. Automatic paraphrase acquisition from news articles. In Proc. HLT. find
R. Snow, D. Jurafsky, and A. Y. Ng. 2004. Learning syntactic patterns for automatic hypernym discovery. In NIPS 2004. find
R.E. Tarjan. 1977. Finding optimum branchings. Networks, 7:25–35. find
B. Taskar, C. Guestrin, and D. Koller. 2003. Max-margin Markov networks. In Proc. NIPS. find
B. Taskar, D. Klein, M. Collins, D. Koller, and C. Manning. 2004. Max-margin parsing. In Proc. EMNLP. find
W. Wang and M. P. Harper. 2004. A statistical constraint dependency grammar (CDG) parser. In Workshop on Incremental Parsing: Bringing Engineering and Cognition Together (ACL). find
H. Yamada and Y. Matsumoto. 2003. Statistical dependency analysis with support vector machines. In Proc. IWPT. find our card
D. Zeman. 2004. Parsing with a Statistical Dependency Model. Ph.D. thesis, Univerzita Karlova, Praha. find

This page in Markdown → https://md.mova.elamur.ai/free/en/docs/papers/narrative-2005-mcdonald-non-projective-dependency-parsing-spanning/