A Linear Observed Time Statistical Parser Based on Maximum Entropy Models

By Adwait Ratnaparkhi. 1997

This paper presents a statistical parser for natural language that obtains a parsing accuracy---roughly 87% precision and 86% recall---which surpasses the best previously published results on the Wall St. Journal domain. The parser itself requires very little human intervention, since the information it uses to make parsing decisions is specified in a concise and simple manner, and is combined in a fully automatic way under the maximum entropy framework. The observed running time of the parser on a test sentence is linear with respect to the sentence length. Furthermore, the parser returns several scored parses for a sentence, and this paper shows that a scheme to pick the best parse from the 20 highest scoring parses could yield a dramatically higher accuracy of 93% precision and recall.

Subfields: Natural Language Processing, Model Architectures

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Natural Language Processing

In Model Architectures

Citations in the corpus

Grammar as a Foreign Language (2014, methodology): “As a sequence-to-sequence prediction model it is somewhat related to the incremental parsing models, pioneered by [26] and extended by [27].”
Head-Driven Statistical Models for Natural Language Parsing (2003, methodology): “• Section 8 discussed relationships to the generative model of Charniak (1997) and the history-based (conditional) models of Ratnaparkhi (1997), Jelinek et al. (1994), and Magerman (1995).”
The Proposition Bank: An Annotated Corpus of Semantic Roles (2005, neutral): “Robust syntactic parsers, made possible by new statistical techniques (Ratnaparkhi 1997; Collins 1999, 2000; Bangalore and Joshi 1999; Charniak 2000) and by the availability of large, hand-annotated training corpora (Marcus, Santorini, and Marcinkiewicz 1993; Abeille´ 2003), have had a major impact…”
MaltParser: A Data-Driven Parser-Generator for Dependency Parsing (2006, background): “History-based feature models for predicting the next parser action (Black et al., 1992; Magerman, 1995; Ratnaparkhi, 1997; Collins, 1999) 3.”
A Classifier-Based Parser with Linear Run-Time Complexity (2005, methodology): “Additionally, our parser is in some ways similar to the maximum-entropy parser of Ratnaparkhi (1997).”
A Neural Syntactic Language Model (2005, methodology): “A statistical parser based on maximum-entropy models has been developed by Ratnaparkhi (1997) and has shown state-of-the-art performance in parsing accuracy.”
Structured Training for Neural Network Transition-Based Parsing (2015, background): “Unfortunately we are not able to compare to several semi-supervised dependency parsers that achieve some of the highest reported accuracies on the WSJ, in particular Suzuki et al. (2009), Suzuki et al. (2011) and Chen et al.”
Fast and Accurate Shift-Reduce Constituent Parsing (2013, unknown): “We note that the performance is on the same level Parser #Sent/Second Ratnaparkhi (1997) Unk Collins (1999) 3.5 Charniak (2000) 5 The padding technique, supervised features, and semi-supervised features achieve an overall improvement of 1 .”
Algorithms for Deterministic Incremental Dependency Parsing (2008, background): “In this setting, more competitive results have been achieved using probabilistic classiﬁers and beam search, rather than strictly deterministic search, as in the work by Ratnaparkhi (1997, 1999) and Sagae and Lavie (2006).”
Discriminative Reranking for Natural Language Parsing (2000, methodology): “Della Pietra, Della Pietra, and Lafferty (1997) describe feature selection methods for log-linear models, and Rosenfeld (1997) describes application of these methods to language modeling for speech recognition.”
Corpus Variation and Parser Performance (2001, background): “The techniques of Char-niak (1997), Collins (1997), and Ratnaparkhi (1997) achieved roughly comparable results using the same sets of training and test data.”
Automatic Labeling of Semantic Roles Qualifying Exam Proposal (2000, background): “A great deal has been accomplished in the past several years in the eld of statistical syntactic parsing, shown by the work of (Charniak, 1997), (Collins, 1997), (Magerman, 1995), and (Ratnaparkhi, 1997).”
Better k-best Parsing (2005, methodology): “(Charniak and Johnson, 2005), (Collins, 2000) and (Ratnaparkhi, 1997).”
Relating Probabilistic Grammars and Automata (1999, background): “Most other probabilistic shiftreduce parsing models (Briscoe and Carroll, 1993; Black et al., 1992; Magerman, 1994; Ratnaparkhi, 1997) give only the conditional probability of a parse tree given a word sequence.”