Elamur Research
☰
home / papers / 2008 / Simple Semi-supervised Dependency Parsing

Simple Semi-supervised Dependency Parsing

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/P08-1068.pdf

Summary

Word-to-word statistics help resolve attachment ambiguities in parsing, but they are too sparse to estimate reliably from treebanks alone. Koo, Carreras and Collins address this sparsity with a two-step semi-supervised recipe for dependency parsing. First, they run the Brown clustering algorithm, using Liang's (2005) implementation, over a large unannotated corpus. This yields a binary word hierarchy in which each word is identified by a bit-string path. Second, they add cluster-derived features to discriminative first-order and second-order parsers. Short bit-string prefixes act as coarse stand-ins for POS tags, and full bit strings replace word forms. Hybrid templates combine clusters with words or tags. The authors test the approach on the Penn Treebank for English and the Prague Dependency Treebank for Czech. The extra features consistently improve unlabeled parent-prediction accuracy. They also cut roughly in half the annotated data needed to reach a given accuracy. The method is cheap and leaves the parser itself untouched, which makes it a practical way to reduce reliance on costly annotation.

Key points

  • Accuracy gains (unlabeled, second-order): English rose from 92.02% to 93.16%, and Czech rose from 86.13% to 87.13%.
  • Data savings: cluster features help at every training-set size and save about half the supervised data. For example, on the PDT, dep1c trained on 4k sentences roughly matches dep1 trained on 8k.
  • Prefix lengths: 4–6-bit prefixes and full bit strings worked well. The 12–20-bit prefixes from Miller et al. (2004), originally used for named-entity recognition, performed poorly for syntax.
  • Feature design: hybrid cluster+POS/word features beat cluster-only features. Keeping word-based features only for the top-N most frequent words (N ≈ 100–1,000) barely affected the cluster models but hurt the baselines.
  • Clusters without POS tags: removing POS-based features still left cluster models close to the POS-based baselines on Section 22 (dep1c-P 90.69 vs. dep1 90.89; dep2c-P 91.84 vs. dep2 92.42).

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 · Treebanks · Part-of-speech tagging

Cited by

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

Cite

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

@inproceedings{koo2008simple,
  title = {{Simple Semi-supervised Dependency Parsing}},
  author = {Koo, Terry and Carreras, Xavier and Collins, Michael},
  booktitle = {Proceedings of ACL-08: HLT},
  year = {2008},
  url = {https://aclanthology.org/P08-1068/}
}

References

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

  1. P.F. Brown, V.J. Della Pietra, P.V. deSouza, J.C. Lai, and R.L. Mercer. 1992. Class-Based n-gram Models of Natural Language. Computational Linguistics, 18(4):467–479. find
  2. S. Buchholz and E. Marsi. 2006. CoNLL-X Shared Task on Multilingual Dependency Parsing. In Proceedings of CoNLL, pages 149–164. find our card
  3. X. Carreras. 2007. Experiments with a Higher-Order Projective Dependency Parser. In Proceedings of EMNLP-CoNLL, pages 957–961. find
  4. E. Charniak, D. Blaheta, N. Ge, K. Hall, and M. Johnson. 2000. BLLIP 1987–89 WSJ Corpus Release 1, LDC No. LDC2000T43. Linguistic Data Consortium. find
  5. Y.J. Chu and T.H. Liu. 1965. On the shortest arborescence of a directed graph. Science Sinica, 14:1396– 1400. find
  6. M. Collins, J. Hajič, L. Ramshaw, and C. Tillmann. 1999. A Statistical Parser for Czech. In Proceedings of ACL, pages 505–512. find
  7. M. Collins. 2002. Discriminative Training Methods for Hidden Markov Models: Theory and Experiments with Perceptron Algorithms. In Proceedings of EMNLP, pages 1–8. find our card
  8. K. Crammer and Y. Singer. 2003. Ultraconservative Online Algorithms for Multiclass Problems. Journal of Machine Learning Research, 3:951–991. find
  9. K. Crammer, O. Dekel, S. Shalev-Shwartz, and Y. Singer. 2004. Online Passive-Aggressive Algorithms. In S. Thrun, L. Saul, and B. Schölkopf, editors, NIPS 16, pages 1229–1236. find
  10. J. Edmonds. 1967. Optimum branchings. Journal of Research of the National Bureau of Standards, 71B:233– 240. find
  11. J. Eisner. 2000. Bilexical Grammars and Their Cubic-Time Parsing Algorithms. In H. Bunt and A. Nijholt, editors, Advances in Probabilistic and Other Parsing Technologies, pages 29–62. Kluwer Academic Publishers. find
  12. Y. Freund and R. Schapire. 1999. Large Margin Classification Using the Perceptron Algorithm. Machine Learning, 37(3):277–296. find
  13. J. Hajič, E. Hajičová, P. Pajas, J. Panevova, and P. Sgall. 2001. The Prague Dependency Treebank 1.0, LDC No. LDC2001T10. Linguistics Data Consortium. find
  14. J. Hajič. 1998. Building a Syntactically Annotated Corpus: The Prague Dependency Treebank. In E. Hajičová, editor, Issues of Valency and Meaning. Studies in Honor of Jarmila Panevová, pages 12–19. find
  15. K. Hall and V. Novák. 2005. Corrective Modeling for Non-Projective Dependency Parsing. In Proceedings of IWPT, pages 42–52. find
  16. T. Koo and M. Collins. 2005. Hidden-Variable Models for Discriminative Reranking. In Proceedings of HLT-EMNLP, pages 507–514. find
  17. W. Li and A. McCallum. 2005. Semi-Supervised Sequence Modeling with Syntactic Topic Models. In Proceedings of AAAI, pages 813–818. find
  18. P. Liang. 2005. Semi-Supervised Learning for Natural Language. Master’s thesis, Massachusetts Institute of Technology. find
  19. M.P. 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
  20. T. Matsuzaki, Y. Miyao, and J. Tsujii. 2005. Probabilistic CFG with Latent Annotations. In Proceedings of ACL, pages 75–82. find
  21. D. McClosky, E. Charniak, and M. Johnson. 2006. Effective Self-Training for Parsing. In Proceedings of HLT-NAACL, pages 152–159. find our card
  22. R. McDonald and F. Pereira. 2006. Online Learning of Approximate Dependency Parsing Algorithms. In Proceedings of EACL, pages 81–88. find our card
  23. R. McDonald, K. Crammer, and F. Pereira. 2005a. Online Large-Margin Training of Dependency Parsers. In Proceedings of ACL, pages 91–98. find our card
  24. R. McDonald, F. Pereira, K. Ribarov, and J. Hajič. 2005b. Non-Projective Dependency Parsing using Spanning Tree Algorithms. In Proceedings of HLT-EMNLP, pages 523–530. find our card
  25. S. Miller, J. Guinness, and A. Zamanian. 2004. Name Tagging with Word Clusters and Discriminative Training. In Proceedings of HLT-NAACL, pages 337–342. find
  26. J. Nivre and J. Nilsson. 2005. Pseudo-Projective Dependency Parsing. In Proceedings of ACL, pages 99–106. find
  27. J. Nivre, J. Hall, S. Kübler, R. McDonald, J. Nilsson, S. Riedel, and D. Yuret. 2007. find
  28. The CoNLL 2007 Shared Task on Dependency Parsing. In Proceedings of EMNLP-CoNLL 2007, pages 915–932. find
  29. S. Petrov, L. Barrett, R. Thibaux, and D. Klein. 2006. Learning Accurate, Compact, and Interpretable Tree Annotation. In Proceedings of COLING-ACL, pages 433–440. find our card
  30. A. Ratnaparkhi. 1996. A Maximum Entropy Model for Part-Of-Speech Tagging. In Proceedings of EMNLP, pages 133–142. find
  31. I. Titov and J. Henderson. 2007. Constituent Parsing with Incremental Sigmoid Belief Networks. In Proceedings of ACL, pages 632–639. find
  32. Q.I. Wang, D. Schuurmans, and D. Lin. 2005. Strictly Lexical Dependency Parsing. In Proceedings of IWPT, pages 152–159. find
  33. H. Yamada and Y. Matsumoto. 2003. Statistical Dependency Analysis With Support Vector Machines. In Proceedings of IWPT, pages 195–206. find our card