Elamur Research
☰
home / papers / 2003 / Statistical Dependency Analysis with Support Vector Machines

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

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.

Library summary

The Research library's own summary of the paper, in our words — not the paper's text.

Written for the Research library (claude-opus-5-5) from the paper text, in our own words: the license "CC BY-NC-SA 3.0 (ACL Anthology, before 2016)" does not allow redistributing the text itself. Original — aclanthology.org/W03-3023.pdf

Summary

The authors ask whether English syntactic dependencies can be predicted accurately without phrase-structure analysis. Their motivation is practical. Domain experts, for example in medicine or law, can annotate word-to-word dependencies much more easily than Penn treebank–style constituency trees, and simpler annotation should produce cleaner training data. They build a deterministic, bottom-up parser that moves left to right over neighbouring word pairs. At each pair it chooses one of three actions: Shift, Right or Left. Support Vector Machines make this choice using POS tags, word forms and information about children already attached in a local context window. Because SVM margins are not probabilities, the authors use greedy decisions instead of dynamic-programming search. The training and test data are dependency trees converted from the Penn treebank with head rules. The parser reaches 90.3% word-level dependency accuracy on section 23. This is a little below the Charniak (MEIP) and Collins parsers, whose outputs were converted the same way. The result shows that a purely dependency-based learner can come close to constituency parsers, which supports cheaper treebank creation for new domains.

Key points

  • The parser has three actions. Shift moves the focus right. Right makes the left word a child of the right one. Left does the reverse. The parser makes repeated passes over the sentence until a single tree remains or a full pass builds nothing.
  • The three-way decision is split into three pairwise binary SVMs (Left/Right, Left/Shift, Right/Shift), and the final action is chosen by majority vote. The SVMs use C = 1.
  • The best setup combines a polynomial kernel of degree 2, a context of 2 nodes to the left and 4 to the right, and features built from POS tags, word strings and the children of nodes in the window.
  • Results on Penn treebank section 23 for this parser:
    • dependency accuracy 0.903
    • root accuracy 0.916
    • complete-sentence rate 0.384
    • leaf accuracy 0.935
  • The comparison systems scored as follows:
    • MEIP (Charniak): 0.921 dependency accuracy, 0.952 root accuracy
    • Collins models 1–3: 0.912–0.915 dependency accuracy
  • Leaf accuracy is roughly on par with Collins. The largest gap is near the root, where constituency parsers benefit from phrase labels such as VP or SBAR. Eisner's earlier 90.0% is not directly comparable, because his data differed and he excluded sentences containing conjunctions.

Interesting ideas

  • Choose the annotation format by who will annotate. Picking dependency structure because domain experts without linguistic training can produce it reliably is a sensible rule for building treebanks in specialised fields or for less-resourced languages.
  • Use greedy decoding when scores are not probabilities. Margin-based classifier outputs make poor costs for dynamic-programming search, so the authors use deterministic transitions instead. It is worth checking whether a classifier's scores really support global search before designing a decoder around them.
  • Let features change as the tree grows. The features include the children already attached to nearby nodes. For example, the verb under a relative pronoun helps decide which noun the pronoun attaches to. Feeding partial-structure information back into later decisions applies to many incremental structure-building tasks.
  • Report accuracy by position in the tree. Measuring leaf accuracy and root accuracy separately shows where a model fails (here, at clause-level attachments) and where it already matches stronger systems. This tells you where better features would help most.
  • Separate "no link" from "link not ready yet." As future work, the authors propose splitting Shift into two classes that behave identically but are learned separately. Separating classes that look the same in behaviour but differ in cause could reduce label noise in other transition-based or sequence models.

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