Elamur Research⌕
☰
home / papers / 2009 / Transition-Based Parsing of the Chinese Treebank using a Global Discriminative Model

Transition-Based Parsing of the Chinese Treebank using a Global Discriminative Model

Summary

The paper targets constituent parsing of Chinese with the Chinese Treebank (CTB). The best earlier transition-based system, Wang et al. (2006), relied on a greedy shift-reduce parser with a local SVM classifier at each step. Zhang and Clark keep the same shift-reduce transitions over binarized, head-lexicalized trees. They replace the local decisions with one linear model that scores whole action sequences. Weights are learned with an averaged generalized perceptron plus early update, and decoding uses beam search instead of greedy choice. Parsing still runs in linear time, and competing hypotheses in the beam can recover from early mistakes.

The authors also make three practical changes. They add a TERMINATE action so that unary-branching roots can be built. They impose a set of constraints that guarantees every output is a valid tree. They hand-craft combined features for the linear model.

On CTB 2 the parser matches the Parseval F-score of the state of the art. On the larger CTB 5, its output converted to dependencies gives the best dependency scores reported so far. Accuracy falls noticeably when POS tags are predicted automatically rather than taken from gold annotation.

Key points

  • Method: shift-reduce constituent parsing with a global discriminative model. Training uses an averaged perceptron with early update (Collins and Roark, 2004), and decoding is beam search that keeps the B best states.
  • New TERMINATE action: lets unary reduces apply at the root. This matters for 14 of the 3475 CTB 2 training sentences, which Wang et al.'s parser cannot produce correctly.
  • Binarization: a reversible, head-driven scheme introduces temporary "X*" labels. Restrictions on legal actions always yield well-formed trees, including a cap of three consecutive unary reduces.
  • Features: context windows come from Wang et al. (stack nodes S0–S3 and queue words N0–N3). Unigrams are combined by hand into bigram and trigram templates, alongside bracket and separator (punctuation) features.
  • Results and resource: accuracy is comparable to the best systems on CTB 2, and dependency accuracy on CTB 5 is the highest reported. The code is released as part of ZPar (sourceforge.net/projects/zpar, make target chinese.conparser).

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: Natural language processing

Topics: Dependency parsing · Treebanks

Institutions

🎓University of OxfordOxford · United Kingdom39 works · 153 213 citations🎓University of CambridgeCambridge · United Kingdom119 works · 110 950 citations

Cite

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

@inproceedings{zhang2009transition,
  title = {{Transition-Based Parsing of the Chinese Treebank using a Global Discriminative Model}},
  author = {Zhang, Yue and Clark, Stephen},
  booktitle = {Proceedings of the 11th International Conference on Parsing Technologies (IWPT'09)},
  year = {2009},
  doi = {10.3115/1697236.1697267},
  url = {https://doi.org/10.3115/1697236.1697267}
}

References

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

  1. Daniel M. Bikel and David Chiang. 2000. Two statistical parsing models applied to the Chinese Treebank. In Proceedings of SIGHAN Workshop, pages 1–6, Morristown, NJ, USA. find
  2. Daniel M. Bikel. 2004. On the Parameter Space of Generative Lexicalized Statistical Parsing Models. Ph.D. thesis, University of Pennsylvania. find
  3. Ted Briscoe and John Carroll. 1993. Generalized probabilistic LR parsing of natural language (corpora) with unification-based grammars. Computational Linguistics, 19(1):25–59. find
  4. Xavier Carreras, Michael Collins, and Terry Koo. 2008. Tag, dynamic programming, and the perceptron for efficient, feature-rich parsing. In Proceedings of CoNLL, pages 9–16, Manchester, England, August. find
  5. Eugene Charniak. 2000. A maximum-entropy-inspired parser. In Proceedings of NAACL, pages 132–139, Seattle, WA. find our card
  6. David Chiang and Daniel M. Bikel. 2002. Recovering latent information in treebanks. In Proceedings of COLING. find
  7. Stephen Clark and James R. Curran. 2007. Wide-coverage efficient statistical parsing with CCG and log-linear models. Computational Linguistics, 33(4):493–552. find our card
  8. Michael Collins and Brian Roark. 2004. Incremental parsing with the perceptron algorithm. In Proceedings of ACL, pages 111–118, Barcelona, Spain, July. find our card
  9. Michael Collins. 1997. Three generative, lexicalised models for statistical parsing. In Proceedings of the 35th Meeting of the ACL, pages 16–23, Madrid, Spain. find our card
  10. Michael Collins. 2002. Discriminative training methods for hidden markov models: Theory and experiments with perceptron algorithms. In Proceedings of EMNLP, pages 1–8, Philadelphia, USA, July. find our card
  11. Xiangyu Duan, Jun Zhao, and Bo Xu. 2007. Probabilistic models for action-based Chinese dependency parsing. In Proceedings of ECML/ECPPKDD, Warsaw, Poland, September. find
  12. Jenny Rose Finkel, Alex Kleeman, and Christopher D. Manning. 2008. Efficient, feature-based, conditional random field parsing. In Proceedings of ACL/HLT, pages 959–967, Columbus, Ohio, June. Association for Computational Linguistics. find our card
  13. Roger Levy and Christopher D. Manning. 2003. Is it harder to parse Chinese, or the Chinese Treebank? In Proceedings of ACL, pages 439–446, Sapporo, Japan, July. find
  14. Ryan McDonald, Koby Crammer, and Fernando Pereira. 2005. Online large-margin training of dependency parsers. In Proceedings of ACL, pages 91– 98, Ann Arbor, Michigan, June. find our card
  15. Joakim Nivre, Johan Hall, Jens Nilsson, Gülşen Eryiǧit, and Svetoslav Marinov. 2006. Labeled pseudo-projective dependency parsing with support vector machines. In Proceedings of CoNLL, pages 221–225, New York City, June. find our card
  16. Slav Petrov and Dan Klein. 2007. Improved inference for unlexicalized parsing. In Proceedings of HLT/NAACL, pages 404–411, Rochester, New York, April. Association for Computational Linguistics. find our card
  17. Adwait Ratnaparkhi. 1999. Learning to parse natural language with maximum entropy models. Machine Learning, 34(1-3):151–175. find
  18. Kenji Sagae and Alon Lavie. 2005. A classifier-based parser with linear run-time complexity. In Proceedings of IWPT, pages 125–132, Vancouver, British Columbia, October. find our card
  19. Honglin Sun and Daniel Jurafsky. 2003. The effect of rhythm on structural disambiguation in Chinese. In Proceedings of SIGHAN Workshop. find
  20. Mengqiu Wang, Kenji Sagae, and Teruko Mitamura. 2006. A fast, accurate deterministic parser for Chinese. In Proceedings of COLING/ACL, pages 425– 432, Sydney, Australia. find
  21. Deyi Xiong, Shuanglong Li, Qun Liu, Shouxun Lin, and Yueliang Qian. 2005. Parsing the Penn Chinese Treebank with semantic knowledge. In Proceedings of IJCNLP. find
  22. Yue Zhang and Stephen Clark. 2008. A tale of two parsers: investigating and combining graph-based and transition-based dependency parsing using beam-search. In Proceedings of EMNLP, pages 562–571, Hawaii, USA, October. find our card

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/zhang-2009-transition-based-parsing-chinese-treebank/