A* CCG Parsing with a Supertag-factored Model

Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 990–1000, October 25-29, 2014, Doha, Qatar. c⃝2014 Association for Computational Linguistics A∗ CCG Parsing with a Supertag-factored Model Mike Lewis School of Informatics University of Edinburgh Edinburgh, EH8 9AB, UK mike.lewis@ed.ac.uk Mark Steedman School of Informatics University of Edinburgh Edinburgh, EH8 9AB, UK steedman@inf.ed.ac.uk Abstract We introduce a new CCG parsing model which is factored on lexical category as- signments. Parsing is then simply a de- terministic search for the most probable category sequence that supports a CCG derivation. The parser is extremely simple, with a tiny feature set, no POS tagger, and no statistical model of the derivation or dependencies. Formulating the model in this way allows a highly effective heuris- tic for A∗ parsing, which makes parsing extremely fast. Compared to the standard C&C CCG parser, our model is more ac- curate out-of-domain, is four times faster, has higher coverage, and is greatly simpli- fied. We also show that using our parser improves the performance of a state-of- the-art question answering system. 1 Introduction CCG is a strongly lexicalized grammatical formal- ism, in which the vast majority of the decisions made during interpretation involve choosing the correct definitions of words. We explore the ef- fect of modelling this explicitly in a parser, by only using a probabilistic model of lexical cate- gories (based on a local context window), rather than modelling the derivation or dependencies. Existing state-of-the-art CCG parsers use com- plex pipelines of POS-tagging, supertagging and parsing—each with its own feature sets and pa- rameters (and sources of error)—together with fur- ther parameters governing their integration (Clark and Curran, 2007). We show that much simpler models can achieve high performance. Our model predicts lexical categories based on a tiny fea- ture set of word embeddings, capitalization, and 2- character suffixes—with no parsing model beyond a small set of CCG combinators, and no POS- tagger. Simpler models are easier to implement, replicate and extend. Another goal of our model is to parse CCG optimally and efficiently, without using excessive pruning. CCG’s large set of lexical categories, and generalized notion of constituency, mean that sentences can have a huge number of potential parses. Fast existing CCG parsers rely on aggres- sive pruning—for example, the C&C parser uses a supertagger to dramatically cut the search space considered by the parser. Even the loosest beam setting for their supertagger discards the correct parse for 20% of sentences. The structure of our model allows us to introduce a simple but power- ful heuristic for A∗ parsing, meaning it can parse almost 50 sentences per second exactly, with no beam-search or pruning. Adding very mild prun- ing increases the speed to 186 sentences per sec- ond with minimal loss of accuracy. Our approach faces two obvious challenges. Firstly, categories are assigned based on a local window, which may not contain the necessary con- text for resolving some attachment decisions. For example, in I saw a squirrel 2 weeks ago …

Content truncated to 500 words