Abstract
We introduce a new CCG parsing model which is factored on lexical category assignments. Parsing is then simply a deterministic 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 heuristic for A* parsing, which makes parsing extremely fast. Compared to the standard C&C CCG parser, our model is more accurate out-of-domain, is four times faster, has higher coverage, and is greatly simplified. We also show that using our parser improves the performance of a state-of-the-art question answering system.
Introduction
Parsing with Combinatory Categorial Grammar (CCG) is notoriously difficult due to its "strongly lexicalized" nature. Words are assigned complex categories, or supertags, which dictate their syntactic behavior. Traditional state-of-the-art parsers, such as the C&C parser, employ complex pipelines involving POS tagging and log-linear models to rank dependencies. These systems often suffer from error propagation, aggressive pruning that discards correct parses, and poor portability to new domains.
This paper introduces EASYCCG, a minimalist parser that shifts the focus from complex dependency modeling to a simple, local supertagging model. By factoring the parse probability solely on lexical category assignments, the authors enable a highly efficient A* search strategy.
Methodology
EASYCCG utilizes a "factored" model where the probability of a derivation is determined by the product of the probabilities of the supertags assigned to each word.
- Lexical Model: A simple unigram log-linear classifier is used, relying on a minimal feature set: word embeddings, capitalization, and 2-character suffixes. Notably, the model operates without a POS tagger.
- A* Search and Heuristic: The parser finds the most probable derivation using A* search. The efficiency is driven by a novel heuristic that provides a tight upper bound on the "outside probability" by assuming all words outside the current span will take their most likely supertag.
- Grammar: The system uses a clean set of 10 binary and 13 unary hand-coded CCG combinators, avoiding the noisy rules common in legacy parsers.
Performance and Robustness
EASYCCG demonstrates significant improvements in speed and out-of-domain robustness. By simplifying the search space, the parser achieves a 4x speedup over the C&C parser, processing approximately 186 sentences per second with mild pruning.
While slightly less accurate than C&C on in-domain news text (83.37 vs 85.30 F1), EASYCCG excels in out-of-domain evaluations. On Wikipedia and biomedical text (Bioinfer), it outperforms the C&C parser, achieving 81.75 F1 and 77.24 F1 respectively. Furthermore, it provides nearly 100% coverage, successfully parsing complex sentences where traditional models often fail.
Downstream Application: Question Answering
The practical benefits of EASYCCG were evaluated using the WEBQUESTIONS dataset in a state-of-the-art question-answering system. Replacing the C&C parser with EASYCCG led to a 4-point increase in "oracle" accuracy, indicating that the simpler, factored model generates more useful structures for semantic analysis.
Discussion and Limitations
The success of EASYCCG suggests that supertagging accounts for the majority of the parsing challenge. However, the model's reliance on local context (a ±3 word window) introduces limitations in resolving long-distance ambiguities, such as prepositional phrase attachment and coordination. Future work involves developing targeted models for these specific structural decisions while preserving the simplicity and speed of the core lexicalized approach.
Summary updated