Incremental LTAG Parsing

Proceedings of Human Language Technology Conference and Conference on Empirical Methods in Natural Language Processing (HLT/EMNLP), pages 811–818, Vancouver, October 2005. c⃝2005 Association for Computational Linguistics Incremental LTAG Parsing Libin Shen and Aravind K. Joshi Department of Computer and Information Science University of Pennsylvania Philadelphia, PA 19104, USA � libin,joshi � @linc.cis.upenn.edu Abstract We present a very efficient statistical in- cremental parser for LTAG-spinal, a vari- ant of LTAG. The parser supports the full adjoining operation, dynamic predi- cate coordination, and non-projective de- pendencies, with a formalism of provably stronger generative capacity as compared to CFG. Using gold standard POS tags as input, on section 23 of the PTB, the parser achieves an f-score of 89.3% for syntactic dependency defined on LTAG derivation trees, which are deeper than the dependen- cies extracted from PTB alone with head rules (for example, in Magerman’s style). 1 Introduction Lexicalized Tree Adjoining Grammar (LTAG) is a formalism motived by both linguistic and computa- tional perspectives (for a relatively recent review, see (Joshi and Schabes, 1997)). Because of the intro- duction of the adjoining operation, the TAG formal- ism is provably stronger than Context Free Gram- mar (CFG) both in the weak and the strong genera- tive power. The TAG formalism provides linguisti- cally attractive analysis of natural language (Frank, 2002). Recent psycholinguistic experiments (Sturt and Lombardo, 2005) demonstrate that the adjoining operation of LTAG is required for eager incremental processing. Vijay-Shanker and Joshi (1985) introduced the first TAG parser in a CYK-like algorithm. Because of the adjoining operation, the time complexity of LTAG parsing is as large as ���� � , compared with � �� � of CFG parsing, where � is the length of the sentence to be parsed. Many LTAG parsers were proposed, such as the head-driven Earley style parser (Lavelli and Satta, 1991) and the head-corner parser (van Noord, 1994). The high time complexity prevents LTAG parsing from real-time applications. In this paper, we work on LTAG-spinal (Shen and Joshi, 2005), an interesting subset of LTAG, which preserves almost all of the strong generative power of LTAG, and it is both weakly and strongly more powerful than CFG 1. We will present a statistical incremental parsing for LTAG-spinal. As far as we know, this parser is the first comprehensive attempt of efficient statistical parsing with a formal grammar with provably stronger generative power than CFG, supporting the full adjoining operation, dynamic predicate coordination, as well as non-projective de- pendencies 2. 2 LTAG-spinal and the Treebank We first briefly describe the LTAG-spinal formalism and the LTAG-spinal treebank to be used in this pa- per. More details are reported in (Shen and Joshi, 2005). In LTAG-spinal, we have two different kinds of elementary trees, initial trees and auxiliary trees, which are the same as in LTAG. However, as the name implies, an initial tree in LTAG-spinal only contains the spine from the root to the anchor, and an auxiliary tree only contains the spine and the foot node directly connected to a node …

Content truncated to 500 words