A Fast, Accurate Deterministic Parser for Chinese

Proceedings of the 21st International Conference on Computational Linguistics and 44th Annual Meeting of the ACL, pages 425–432, Sydney, July 2006. c⃝2006 Association for Computational Linguistics A Fast, Accurate Deterministic Parser for Chinese Mengqiu Wang Kenji Sagae Teruko Mitamura Language Technologies Institute School of Computer Science Carnegie Mellon University {mengqiu,sagae,teruko}@cs.cmu.edu Abstract We present a novel classifier-based deter- ministic parser for Chinese constituency parsing. Our parser computes parse trees from bottom up in one pass, and uses classifiers to make shift-reduce decisions. Trained and evaluated on the standard training and test sets, our best model (us- ing stacked classifiers) runs in linear time and has labeled precision and recall above 88% using gold-standard part-of-speech tags, surpassing the best published re- sults. Our SVM parser is 2-13 times faster than state-of-the-art parsers, while produc- ing more accurate results. Our Maxent and DTree parsers run at speeds 40-270 times faster than state-of-the-art parsers, but with 5-6% losses in accuracy. 1 Introduction and Background Syntactic parsing is one of the most fundamental tasks in Natural Language Processing (NLP). In recent years, Chinese syntactic parsing has also received a lot of attention in the NLP commu- nity, especially since the release of large collec- tions of annotated data such as the Penn Chi- nese Treebank (Xue et al., 2005). Corpus-based parsing techniques that are successful for English have been applied extensively to Chinese. Tradi- tional statistical approaches build models which assign probabilities to every possible parse tree for a sentence. Techniques such as dynamic pro- gramming, beam-search, and best-first-search are then employed to find the parse tree with the high- est probability. The massively ambiguous nature of wide-coverage statistical parsing,coupled with cubic-time (or worse) algorithms makes this ap- proach too slow for many practical applications. Deterministic parsing has emerged as an attrac- tive alternative to probabilistic parsing, offering accuracy just below the state-of-the-art in syn- tactic analysis of English, but running in linear time (Sagae and Lavie, 2005; Yamada and Mat- sumoto, 2003; Nivre and Scholz, 2004). Encour- aging results have also been shown recently by Cheng et al. (2004; 2005) in applying determin- istic models to Chinese dependency parsing. We present a novel classifier-based determin- istic parser for Chinese constituency parsing. In our approach, which is based on the shift-reduce parser for English reported in (Sagae and Lavie, 2005), the parsing task is transformed into a suc- cession of classification tasks. The parser makes one pass through the input sentence. At each parse state, it consults a classifier to make shift/reduce decisions. The parser then commits to a decision and enters the next parse state. Shift/reduce deci- sions are made deterministically based on the lo- cal context of each parse state, and no backtrack- ing is involved. This process can be viewed as a greedy search where only one path in the whole search space is considered. Our parser produces both dependency and constituent structures, but in this paper we will focus on constituent parsing. By separating the classification task from the parsing process, …

Content truncated to 500 words