LTAG Dependency Parsing with Bidirectional Incremental Construction

Proceedings of the 2008 Conference on Empirical Methods in Natural Language Processing, pages 495–504, Honolulu, October 2008. c⃝2008 Association for Computational Linguistics LTAG Dependency Parsing with Bidirectional Incremental Construction Libin Shen BBN Technologies lshen@bbn.com Aravind K. Joshi University of Pennsylvania joshi@cis.upenn.edu Abstract In this paper, we first introduce a new archi- tecture for parsing, bidirectional incremental parsing. We propose a novel algorithm for in- cremental construction, which can be applied to many structure learning problems in NLP. We apply this algorithm to LTAG dependency parsing, and achieve significant improvement on accuracy over the previous best result on the same data set. 1 Introduction The phrase “Bidirectional Incremental” may appear self-contradictory at first sight, since incremental parsing usually means left-to-right parsing in the context of conventional parsing. In this paper, we will extend the meaning of incremental parsing. The idea of bidirectional parsing is related to the bidirectional sequential classification method de- scribed in (Shen et al., 2007). In that paper, a tagger assigns labels to words of highest confidence first, and then these labels in turn serve as the context of later labelling operations. The bidirectional tagger obtained the best results in literature on POS tagging on the standard PTB dataset. We extend this method from labelling to structure learning, The search space of structure learning is much larger, so that it is appropriate to exploit con- fidence scores in search. In this paper, we are interested in LTAG depen- dency parsing because TAG parsing is a well known problem of high computational complexity in reg- ular parsing. In order to get a focus for the learn- ing algorithm, we work on a variant of LTAG based parsing in which we learn the word dependency re- lations encoded in LTAG derivations instead of the full-fledged trees. 1.1 Parsing Two types of parsing strategies are popular in nat- ural language parsing, which are chart parsing and incremental parsing. Suppose the input sentence is w1w2...wn. Let cell [i, j] represent wiwi+1...wj, a substring of the sen- tence. As far as CFG parsing is concerned, a chart parser computes the possible structures over all pos- sible cells [i, j], where 1 ≤ i ≤ j ≤ n. The order of computing on these n(n + 1)/2 cells is based on some partial order ⪯, such that [p1, p2] ⪯ [q1, q2] if q1 ≤ p1 ≤ p2 ≤ q2. In order to employ dynamic programming, one can only use a fragment of a hy- pothesis to represent the whole hypothesis, which is assumed to satisfy conditional independence as- sumption. It is well known that richer context rep- resentation gives rise to better parsing performance (Johnson, 1998). However, the need for tractability does not allow much internal information to be used to represent a hypothesis. The designs of hypothe- ses in (Collins, 1999; Charniak, 2000) show a del- icate balance between expressiveness and tractabil- ity, which play an important role in natural language parsing. Some recent work on incremental parsing (Collins and Roark, 2004; …

Content truncated to 500 words