Statistical Dependency Analysis with Support Vector Machines

What it is about

The paper parses Penn Treebank sentences, converted to word-word dependencies with head rules, in a deterministic bottom-up way. Three actions (Left, Right, Shift) are chosen by pairwise SVMs over a window of context words and the children already attached to them. Training uses sections 02–21 (more than 1.5 million examples, split by the POS tag of the left target node to make it tractable) and testing uses section 23 (2,416 sentences). The best setting, a polynomial kernel of degree 2 with context (2,4), gives 90.3% dependency accuracy and 91.6% root accuracy. Features about already-attached children help: removing them drops accuracy from 90.3 to 89.0. The phrase-structure models of Collins (91.2–91.5) and Charniak (92.1) stay ahead, mostly on the root.

Ideas

• I1. en/src/parse.rs: add features about the children already attached to the stack top and to the buffer front (the paper's child features); measure cv LAS on the train folds, and EWT test once per release.
• I2. en/src/parse.rs: root attachment is the weak point in the paper (root accuracy 91.6 against about 95 for Collins); measure root accuracy with en parse-eval on EWT test and separately on GUM test (test only).
• I3. en/src/parse.rs: the paper finds degree 2 better than 1, and 3 worse than 2, so add one explicit conjunction feature (head tag times child tag) in place of a kernel and measure cv LAS.

For Mova

The paper's features are the design the en parser already uses (window of words, tags, attached children), so the chapters to read are 21-clause-structure and 22-phrases, where head-child choices are described. The code to touch is en/src/parse.rs, with the POS features from en/src/ptag.rs. Measure first: the child-feature ablation (idea I1) on cv, run twice, before anything else.

Cite

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

@inproceedings{yamada2003statistical,
  title = {{Statistical Dependency Analysis with Support Vector Machines}},
  author = {Yamada, Hiroyasu and Matsumoto, Yuji},
  booktitle = {Proceedings of the Eighth International Workshop on Parsing Technologies},
  year = {2003},
  url = {https://aclanthology.org/W03-3023/}
}

References

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

1. Internet Grateful Med Development Team, National Libarary of Medline: LINE(1996). find
2. Daniel Sleator and Davy Temperley. Parsing English with a Link Grammar. Technical report, Technical Report CMU-CS-91-196, Carnegie Mellon University, October 1991. find our card
3. Eugene Charniak. A Maximum-Entropy-Inspired Parser. In Proceedings of the Second Meeting of North American Chapter of Association for Computational Linguistics (NAACL2000), pages 132–139, 2000. find
4. Jason Eisner. An Empirical Comparison of Probability Models for Dependency Grammar. Technical report, IRCS-96-11, IRCS, Univ. of Pennsylvania, 1996. find
5. Jason Eisner. Three New Probabilistic Models for Dependency Parsing: An Exploration. In Proceedings of the 16th International Conference on Computational Linguistics (COLING-96), pages 340–345, 1996. find our card
6. Michael Collins. A New Statistical Parser Based on Bigram Lexical Dependencies. In Proceedings of the 34th Annual Meeting of the Association for Computational Linguistics, pages 184–191, 1996. find
7. Michael Collins. Three Generative, Lexicalised Models for Statistical Parsing. In Proceedings of the 35th Annual Meeting of the Association for Computational Linguistics (jointly with the 8th Conference of the EACL), pages 16–23, 1997. MED- find
8. Mitchell P. Marcus and Beatrice Santorini and Mary Ann Marcinkiewicz. Building a Large Annotated Corpus of English: The Penn Treebank. Computational Linguistics, 19(2):313– 330, 1993. find our card
9. Tetsuji Nakagawa, Taku Kudoh, and Yuji Matsumoto. Revision learning and its application to part-of-speech tagging. In Proceedings of Association for Computational Linguistics, pages 497–504, 2002. find
10. Adwait Ratnaparkhi. Learning to parse natural language with maximum entropy models. Machine Learning, 34(1-3):151–175, 1999. find
11. Vladimir N. Vapnik. The Nature of Statistical Learning Theory. New York, 1995. find
12. Vladimir N. Vapnik. Statistical Learning Theory. A Wiley-Interscience Publication, 1998. find

This page in Markdown → https://md.mova.elamur.ai/free/en/docs/papers/parsers-2003-yamada-statistical-dependency-analysis-support-vector/