Efficient probabilistic top-down and left-corner parsing

Efficient probabilistic top-down and left-corner parsingt Brian Roark and Mark Johnson Cognitive and Linguistic Sciences Box 1978, Brown University Providence, RI 02912, USA brian-roark@brown, edu mj @cs. brown, edu Abstract This paper examines efficient predictive broad- coverage parsing without dynamic program- ming. In contrast to bottom-up methods, depth-first top-down parsing produces partial parses that are fully connected trees spanning the entire left context, from which any kind of non-local dependency or partial semantic inter- pretation can in principle be read. We con- trast two predictive parsing approaches, top- down and left-corner parsing, and find both to be viable. In addition, we find that enhance- ment with non-local information not only im- proves parser accuracy, but also substantially improves the search efficiency. 1 Introduction Strong empirical evidence has been presented over the past 15 years indicating that the hu- man sentence processing mechanism makes on- line use of contextual information in the preced- ing discourse (Crain and Steedman, 1985; Alt- mann and Steedman, 1988; Britt, 1994) and in the visual environment (Tanenhaus et al., 1995). These results lend support to Mark Steedman's (1989) "intuition" that sentence interpretation takes place incrementally, and that partial in- terpretations are being built while the sentence is being perceived. This is a very commonly held view among psycholinguists today. Many possible models of human sentence pro- cessing can be made consistent with the above view, but the general assumption that must un- derlie them all is that explicit relationships be- tween lexical items in the sentence must be spec- ified incrementally. Such a processing mecha- tThis material is based on work supported by the National Science Foundation under Grant No. SBR- 9720368. nism stands in marked contrast to dynamic pro- gramming parsers, which delay construction of a constituent until all of its sub-constituents have been completed, and whose partial parses thus consist of disconnected tree fragments. For ex- ample, such parsers do not integrate a main verb into the same tree structure as its subject NP until the VP has been completely parsed, and in many cases this is the final step of the entire parsing process. Without explicit on-line inte- gration, it would be difficult (though not impos- sible) to produce partial interpretations on-line. Similarly, it may be difficult to use non-local statistical dependencies (e.g. between subject and main verb) to actively guide such parsers. Our predictive parser does not use dynamic programming, but rather maintains fully con- nected trees spanning the entire left context, which make explicit the relationships between constituents required for partial interpretation. The parser uses probabilistic best-first pars- ing methods to pursue the most likely analy- ses first, and a beam-search to avoid the non- termination problems typical of non-statistical top-down predictive parsers. There are two main results. First, this ap- proach works and, with appropriate attention to specific algorithmic details, is surprisingly efficient. Second, not just accuracy but also efficiency improves as the language model is made more accurate. This bodes well for fu- ture research into the use of …

Content truncated to 500 words