CCG parsing with one syntactic structure per n-gram

CCG parsing with one syntactic structure per n-gram Tim Dawborn and James R. Curran School of Information Technologies University of Sydney NSW, 2006, Australia {tdaw3088,james}@it.usyd.edu.au Abstract There is an inherent redundancy in natural languages whereby certain common phrases (or n-grams) appear frequently in general sen- tences, each time with the same syntactic anal- ysis. We explore the idea of exploiting this re- dundancy by pre-constructing the parse struc- tures for these frequent n-grams. When pars- ing sentences in the future, the parser does not have to re-derive the parse structure for these n-grams when they occur. Instead, their pre- constructed analysis can be reused. By gen- erating these pre-constructed databases over WSJ sections 02 to 21 and evaluating on sec- tion 00, a preliminary result of no signifi- cant change in F-score nor parse time was ob- served. 1 Introduction Natural language parsing is the task of assigning syntactic structure to text. Initial parsing research mostly relied on manually constructed grammars. Statistical parsers have been able to achieve high ac- curacy since the creation of the Penn Treebank (Mar- cus et al., 1993); a corpus of Wall Street Journal text used for training. Statistical parsers are typically in- efficient, parsing only a few sentences per second on standard hardware (Kaplan et al., 2004). There has been substantial progress on addressing this is- sue over the last few years. Clark and Curran (2004) presented a statistical CCG parser, C&C, which was an order of magnitude faster than those analysed in Kaplan et al. (2004). However the C&C parser is still limited to around 25 sentences per second. This paper investigates whether the speed of sta- tistical parsers can be improved using a novel form of caching. Currently, parsers treat each sentence independently, despite the fact that some phrases are constantly reused. We propose to store analyses for common phrases, instead of re-computing their syntactic structure each time the parser encounters them. Our first idea was to store a single, spanning analysis for frequent n-grams. However, the most frequent n-grams often did not form constituents. Given that n-gram distributions are very long-tailed, this meant that the constituent n-grams covered only a small percentage of n-grams in the corpus. We then turned our attention to the n-grams that were not forming constituents. First, we found that some actually should form constituents. However, the structure of noun-phrases in the Penn Treebank is underspecified, leading to incorrect derivations in the C&C parser’s training corpus (Hockenmaier, 2003). Secondly, we investigated whether the spuri- ous ambiguity of CCG derivations could be exploited to force frequent n-grams to compose into con- stituents, while still producing a semantically equiv- alent derivation. Here we encountered problems us- ing the composition rule to create new constituents. Some of these problems were due to further issues with the analyses in the corpus, while others were due to the ambiguity of the n-grams. The sparsity of n-grams in a corpus of this size meant that we had very few caching candidates to work …

Content truncated to 500 words