tailieunhanh - Báo cáo khoa học: "Incremental Parsing with Monotonic Adjoining Operation"

This paper describes an incremental parser based on an adjoining operation. By using the operation, we can avoid the problem of infinite local ambiguity in incremental parsing. This paper further proposes a restricted version of the adjoining operation, which preserves lexical dependencies of partial parse trees. Our experimental results showed that the restriction enhances the accuracy of the incremental parsing. | Incremental Parsing with Monotonic Adjoining Operation Yoshihide Kato and Shigeki Matsubara Information Technology Center Nagoya University Furo-cho Chikusa-ku Nagoya 464-8601 Japan yosihide matubara @ Abstract This paper describes an incremental parser based on an adjoining operation. By using the operation we can avoid the problem of infinite local ambiguity in incremental parsing. This paper further proposes a restricted version of the adjoining operation which preserves lexical dependencies of partial parse trees. Our experimental results showed that the restriction enhances the accuracy of the incremental parsing. 1 Introduction Incremental parser reads a sentence from left to right and produces partial parse trees which span all words in each initial fragment of the sentence. Incremental parsing is useful to realize real-time spoken language processing systems such as a simultaneous machine interpretation system an automatic captioning system or a spoken dialogue system Allen et al. 2001 . Several incremental parsing methods have been proposed so far Collins and Roark 2004 Roark 2001 Roark 2004 . In these methods the parsers can produce the candidates of partial parse trees on a word-by-word basis. However they suffer from the problem of infinite local ambiguity . they may produce an infinite number of candidates of partial parse trees. This problem is caused by the fact that partial parse trees can have arbitrarily nested left-recursive structures and there is no information to predict the depth of nesting. To solve the problem this paper proposes an incremental parsing method based on an adjoining operation. By using the operation we can avoid the problem of infinite local ambiguity. This approach has been adopted by Lombardo and Sturt 1997 and Kato et al. 2004 . However this raises another problem that their adjoining operations cannot preserve lexical dependencies of partial parse trees. This paper proposes a restricted version of