Elamur Research⌕
☰
home / papers / 2005 / A Classifier-Based Parser with Linear Run-Time Complexity

A Classifier-Based Parser with Linear Run-Time Complexity

Summary

Sagae and Lavie ask whether full constituent parsing can be done deterministically and greedily, as earlier classifier-driven dependency parsers did, while keeping accuracy competitive. Their parser runs a bottom-up shift-reduce procedure over POS-tagged input. It has no grammar. Instead, a trained classifier picks one action at each step: shift, unary reduce, or binary reduce with a constituent label and head direction. Training trees from the Penn Treebank are first binarized with head-preserving extra nodes, and these nodes are removed after parsing. Because the trees are lexicalized, the parser produces a dependency structure along with the constituents. Training data comes from replaying the correct derivations of treebank trees.

With an SVM classifier, the parser reaches about 87.5% labeled precision and recall on WSJ section 23 with gold tags, and about 86% with automatic tags. A memory-based learner using the same features does much worse. The work shows that a simple linear-time greedy parser can approach the accuracy of heavier lexicalized PCFG parsers while running much faster.

Key points

  • The algorithm extends the Nivre and Scholz (2004) deterministic dependency approach to constituent trees. The number of shift and binary reduce steps grows linearly with sentence length.
  • Classifier outputs combine the structural decision and the labeling decision: SHIFT, REDUCE-UNARY-XX, REDUCE-LEFT-XX, and REDUCE-RIGHT-XX.
  • SVMpar uses a degree-2 polynomial kernel with one-against-all classification, and its training data is split by POS tag. With gold tags it scores 87.54% precision, 87.61% recall and 90.3% dependency accuracy.
    • It parses the full test set in 11 minutes.
    • It rejects 26 of more than 2,400 sentences. These get flat partial analyses and are still included in the evaluation.
    • Even with splitting, training took about 62 hours.
  • With SVMTool tags, which are about 97% accurate, scores drop to 86.01% precision and 86.15% recall.
  • MBLpar (IB1, k=5, MVDM) trains in under 15 minutes but performs much worse:
    • 80.0% precision, 80.2% recall and 86.3% dependency accuracy.
    • It needs 127 minutes to parse the test set.
    • It uses roughly 1 GB of memory, compared with about 200 MB for SVMpar.

Interesting ideas

  • I1. Head-preserving binarization with reversible markers: Wide productions are split into chains of marked intermediate nodes that keep the original head. A simple binary-only algorithm can then learn and output arbitrary trees. The same trick could help any system that needs a fixed-arity representation but must return the original structures.
  • I2. Training from oracle replay: The parser is run on gold trees, the correct action is read off at every step, and each configuration is logged with that action. This reduces parser training to ordinary classification and fits many incremental structured-prediction tasks.
  • I3. Separating the parsing loop from the decision model: The parser and the classifier are independent modules. Classifiers or feature sets can therefore be swapped with very little work, which makes controlled comparisons cheap.
  • I4. Mixing constituent and dependency features: The classifier uses both constituent information (root and child labels) and dependency information (head distance, dependent counts, most recent dependents). This shows that building two views at once can give a greedy model richer context.
  • I5. Testing classifiers inside the full system: The authors found the SVM vs. MBL gap much larger than results on tasks like chunking would suggest. Their explanation is that greedy parsers compound early errors. Learners should therefore be judged by end-to-end pipeline results, not only by accuracy on isolated decisions.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

Fields: Linguistics & languages

Topics: Dependency parsing

Cited by

80 papers of our library cite it (of the 140673 whose bibliographies we read); 11 of them have a page here, 69 not yet.

Cite

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

@inproceedings{sagae2005classifier,
  title = {{A Classifier-Based Parser with Linear Run-Time Complexity}},
  author = {Sagae, Kenji and Lavie, Alon},
  booktitle = {Proceedings of the Ninth International Workshop on Parsing Technology},
  year = {2005},
  doi = {10.3115/1654494.1654507},
  url = {https://doi.org/10.3115/1654494.1654507}
}

References

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

  1. Charniak, E. 2000. A maximum-entropy-inspired parser. Proceedings of the First Annual Meeting of the North American Chapter of the Association for Computational Linguistics. Seattle, WA. find our card
  2. Collins, M. 1997. Three generative, lexicalized models for statistical parsing. Proceedings of the 35th Annual Meeting of the Association for Computational Linguistics (pp. 16-23). Madrid, Spain. find
  3. Daelemans, W., Zavrel, J., van der Sloot, K., and van den Bosch, A. 2004. TiMBL: Tilburg Memory Based Learner, version 5.1, reference guide. ILK Research Group Technical Report Series no. 04-02, 2004. find
  4. Gildea, D., and Palmer, M. 2002. The necessity of syntactic parsing for predicate argument recognition. Proceedings of the 40th Annual Meeting of the Association for Computational Linguistics (pp. 239-246). Philadelphia, PA. find
  5. Kalt, T. 2004. Induction of greedy controllers for deterministic treebank parsers. Proceedings of the 2004 Conference on Empirical Methods in Natural Language Processing. Barcelona, Spain. find
  6. Kudo, T., and Matsumoto, Y. 2004. A boosting algorithm for classification of semi-structured text. Proceedings of the 2004 Conference on Empirical Methods in Natural Language Processing. Barcelona, Spain. find
  7. Kudo, T., and Matsumoto, Y. 2001. Chunking with support vector machines. Proceedings of the Second Meeting of the North American Chapter of the Association for Computational Linguistics. Pittsburgh, PA. find
  8. Johnson, M. 1998. PCFG models of linguistic tree representations. Computational Linguistics, 24:613-632. find our card
  9. Marcus, M. P., Santorini, B., and Marcinkiewics, M. A. 1993. Building a large annotated corpus of English: the Penn Treebank. Computational Linguistics, 19. find our card
  10. Nivre, J., and Scholz, M. 2004. Deterministic dependency parsing of English text. Proceedings of the 20th International Conference on Computational Linguistics (pp. 64-70). Geneva, Switzerland. find our card
  11. Ratnaparkhi, A. 1997. A linear observed time statistical parser based on maximum entropy models. Proceedings of the Second Conference on Empirical Methods in Natural Language Processing. Providence, Rhode Island. find
  12. Veenstra, J., van den Bosch, A. 2000. Single-classifier memory-based phrase chunking. Proceedings of Fourth Workshop on Computational Natural Language Learning (CoNLL 2000). Lisbon, Portugal. find
  13. Wong, A., and Wu. D. 1999. Learning a lightweight robust deterministic parser. Proceedings of the Sixth European Conference on Speech Communication and Technology. Budapest. find
  14. Yamada, H., and Matsumoto, Y. 2003. Statistical dependency analysis with support vector machines. Proceedings of the Eighth International Workshop on Parsing Technologies. Nancy, France. find our card
  15. Zhang, T., Damerau, F., and Johnson, D. 2002. Text chunking using regularized winnow. Proceedings of the 39th Annual Meeting of the Association for Computational Linguistics. Tolouse, France. find

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/sagae-2005-classifier-based-parser-linear-run/