A Classifier-Based Parser with Linear Run-Time Complexity
By Kenji Sagae, Alon Lavie. 2005
168 citations recorded by the source corpus.
We present a classifier-based parser that produces constituent trees in linear time. The parser uses a basic bottom-up shift-reduce algorithm, but employs a classifier to determine parser actions instead of a grammar. This can be seen as an extension of the deterministic dependency parser of Nivre and Scholz (2004) to full constituent parsing. We show that, with an appropriate feature set used in classification, a very simple one-path greedy parser can perform at the same level of accuracy as more complex parsers. We evaluate our parser on section 23 of the WSJ section of the Penn Treebank, and obtain precision and recall of 87.54% and 87.61%, respectively.
Subfields: Artificial Intelligence
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
Citations in the corpus
- Syntactic Processing Using the Generalized Perceptron and Beam Search (2011, methodology): “The incremental parsing process of our parser is based on the shift-reduce parsers of Sagae and Lavie (2005) and Wang et al. (2006), with slight modifications.”
- Fast and Accurate Shift-Reduce Constituent Parsing (2013, methodology): “Note that Sagae & Lavie (2005) and Sagae & Lavie (2006) are also shift-reduce parsers, and their running times were evaluated on different hardwares.”
- In-Order Transition-based Constituent Parsing (2017, unknown): “There are two popular transition-based constituent parsing systems, namely bottom-up parsing (Sagae and Lavie, 2005; Zhang and Clark, 2009; Zhu et al., 2013; Watanabe and Sumita, 2015) and top-down parsing (Dyer et al.”
- Joint POS Tagging and Transition-based Constituent Parsing in Chinese with Non-local Features (2014, methodology): “In order to construct lexicalized constituent parse trees, we define the following actions for the action set T according to (Sagae and Lavie, 2005; Wang et al., 2006; Zhang and Clark, 2009): • S HIFT ( sh ): remove the first word-POS pair from β , and push it onto the top of σ ; • R EDUCE - UNARY -”
- Wide-Coverage Efficient Statistical Parsing with CCG and Log-Linear Models (2007, background): “Sagae and Lavie (2005) is a classifier-based linear time parser.”
- Feature Optimization for Constituent Parsing via Neural Networks (2015, background): “Usually, an effective set of features have to be designed manually and selected through repeated experiments (Sagae and Lavie, 2005; Wang et al., 2006; Zhang and Clark, 2009).”