Incremental Tree Substitution Grammar for Parsing and Sentence Prediction

Transactions of the Association for Computational Linguistics, 1 (2013) 111–124. Action Editor: David Chiang. Submitted 10/2012; Revised 2/2013; Published 5/2013. c⃝2013 Association for Computational Linguistics. Incremental Tree Substitution Grammar for Parsing and Sentence Prediction Federico Sangati and Frank Keller Institute for Language, Cognition, and Computation School of Informatics, University of Edinburgh 10 Crichton Street, Edinburgh EH8 9AB, UK federico.sangati@gmail.com keller@inf.ed.ac.uk Abstract In this paper, we present the first incremental parser for Tree Substitution Grammar (TSG). A TSG allows arbitrarily large syntactic frag- ments to be combined into complete trees; we show how constraints (including lexical- ization) can be imposed on the shape of the TSG fragments to enable incremental process- ing. We propose an efficient Earley-based al- gorithm for incremental TSG parsing and re- port an F-score competitive with other incre- mental parsers. In addition to whole-sentence F-score, we also evaluate the partial trees that the parser constructs for sentence prefixes; partial trees play an important role in incre- mental interpretation, language modeling, and psycholinguistics. Unlike existing parsers, our incremental TSG parser can generate partial trees that include predictions about the up- coming words in a sentence. We show that it outperforms an n-gram model in predicting more than one upcoming word. 1 Introduction When humans listen to speech, the input becomes available gradually as the speech signal unfolds. Reading happens in a similarly gradual manner when the eyes scan a text. There is good evidence that the human language processor is adapted to this and works incrementally, i.e., computes an interpre- tation for an incoming sentence on a word-by-word basis (Tanenhaus et al., 1995; Altmann and Kamide, 1999). Also language processing systems often deal with speech as it is spoken, or text as it is being typed. A dialogue system should start interpreting a sentence while it is being spoken, and a question answering system should start retrieving answers be- fore the user has finished typing the question. Incremental processing is therefore essential both for realistic models of human language processing and for NLP applications that react to user input in real time. In response to this, a number of in- cremental parsers have been developed, which use context-free grammar (Roark, 2001; Schuler et al., 2010), dependency grammar (Chelba and Jelinek, 2000; Nivre, 2007; Huang and Sagae, 2010), or tree- adjoining grammar (Demberg et al., 2014). Typical applications of incremental parsers include speech recognition (Chelba and Jelinek, 2000; Roark, 2001; Xu et al., 2002), machine translation (Schwartz et al., 2011; Tan et al., 2011), reading time modeling (Demberg and Keller, 2008), or dialogue systems (Stoness et al., 2004). Another potential use of incre- mental parsers is sentence prediction, i.e., the task of predicting upcoming words in a sentence given a prefix. However, so far only n-gram models and clas- sifiers have been used for this task (Fazly and Hirst, 2003; Eng and Eisner, 2004; Grabski and Scheffer, 2004; Bickel et al., 2005; Li and Hirst, 2005). In this paper, we present an incremental parser for Tree Substitution Grammar (TSG). …

Content truncated to 500 words