Top-Down Nearly-Context-Sensitive Parsing

Proceedings of the 2010 Conference on Empirical Methods in Natural Language Processing, pages 674–683, MIT, Massachusetts, USA, 9-11 October 2010. c⃝2010 Association for Computational Linguistics Top-Down Nearly-Context-Sensitive Parsing Eugene Charniak Brown Laboratory for Linguistic Information Processing (BLLIP) Brown University, Providence, RI 02912 ec@cs.brown.edu Abstract We present a new syntactic parser that works left-to-right and top down, thus maintaining a fully-connected parse tree for a few alternative parse hypotheses. All of the commonly used statistical parsers use context-free dynamic programming al- gorithms and as such work bottom up on the entire sentence. Thus they only find a complete fully connected parse at the very end. In contrast, both subjective and experimental evidence show that peo- ple understand a sentence word-to-word as they go along, or close to it. The con- straint that the parser keeps one or more fully connected syntactic trees is intended to operationalize this cognitive fact. Our parser achieves a new best result for top- down parsers of 89.4%,a 20% error reduc- tion over the previous single-parser best result for parsers of this type of 86.8% (Roark, 2001). The improved performance is due to embracing the very large feature set available in exchange for giving up dy- namic programming. 1 Introduction We present a new syntactic parser that works top-down and left-to-right, maintaining a fully- connected parse tree for a few alternative parse hypotheses. It is a Penn treebank (Marcus et al., 1993) parser in that it is capable of parsing the Penn treebank test sets, and is trained on the now standard training set. best result for this parser type.It achieves a new All of the commonly used statistical parsers available on the web such as the Collins(/Bikel) (Collins, 2003) Charniak-Johnson(Charniak and Johnson, 2005), and Petrov-Klein (Petrov et al., 2006), parsers use context-free dynamic pro- gramming algorithms so they work bottom up on the entire sentence. Thus they only find a complete fully-connected parse at the very end. In contrast human syntactic parsing must be fully connected (or close to it) as people are able to apply vast amounts of real-world knowl- edge to the process as it proceeds from word-to- word(van Gompel and Pickering, 2007). Thus any parser claiming cognitive plausibility must, to a first approximation, work in this left-to- right top-down fashion. Our parser obtains a new best result for top- down parsers of 89.4% (on section 23 of the Penn Treebank). This is a 20% error reduction over the previous best single-parser result of 86.8%, achieved by Rork(Roark, 2001). Our model is in the tradition of this lat- ter parser. The current work’s superior per- formance is not due to any innovation in ar- chitecture but in how probability distributions are computed. It differs from Roark in its ex- plicit recognition that by giving up context-free dynamic programming we may embrace near context sensitivity and condition on many di- verse pieces of information. (It is only “near” because we still only condition on a finite amount of information.) This is made possi- ble by …

Content truncated to 500 words