tailieunhanh - Báo cáo khoa học: "Efficient probabilistic top-down and left-corner parsingt Brian Roark and Mark Johnson Cognitive and Linguistic "

This paper examines efficient predictive broadcoverage parsing without dynamic programming. 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 interpretation can in principle be read. We contrast two predictive parsing approaches, topdown and left-corner parsing, and find both to be viable. In addition, we find that enhancement with non-local information not only improves parser accuracy, but also substantially improves the search efficiency. . | Efficient probabilistic top-down and left-corner parsing Brian Roark and Mark Johnson Cognitive and Linguistic Sciences Box 1978 Brown University Providence RI 02912 USA brian-roark@ mj @ Abstract This paper examines efficient predictive broadcoverage parsing without dynamic programming. 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 interpretation can in principle be read. We contrast two predictive parsing approaches top-down and left-corner parsing and find both to be viable. In addition we find that enhancement with non-local information not only improves 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 human sentence processing mechanism makes online use of contextual information in the preceding discourse Crain and Steedman 1985 Altmann 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 interpretations 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 processing can be made consistent with the above view but the general assumption that must underlie them all is that explicit relationships between lexical items in the sentence must be specified incrementally. Such a processing mecha- This material is based on work supported by the National Science Foundation under Grant No. SBR-9720368. nism stands in marked contrast to dynamic programming parsers which delay construction of a constituent until all of its sub-constituents have been completed and whose partial parses thus consist of .