Abstract
Via an oracle experiment, we show that the upper bound on accuracy of a CCG parser is significantly lowered when its search space is pruned using a supertagger, though the supertagger also prunes many bad parses. Inspired by this analysis, we design a single model with both supertagging and parsing features, rather than separating them into distinct models chained together in a pipeline. To overcome the resulting increase in complexity, we experiment with both belief propagation and dual decomposition approaches to inference, the first empirical comparison of these algorithms that we are aware of on a structured natural language processing problem. On CCGbank we achieve a labelled dependency F-measure of 88.8% on gold POS tags, and 86.7% on automatic part-of-speeoch tags, the best reported results for this task.
Introduction: The Pruning Paradox
Combinatory Categorial Grammar (CCG) parsing is a powerful tool for recovering semantic structure, but it is computationally demanding. A single word can have dozens of potential lexical categories, known as supertags, leading to an exponential number of possible sentence derivations. To maintain efficiency, traditional CCG parsers employ a two-stage pipeline: a "supertagger" first prunes the search space by selecting the most likely tags, and the parser then constructs a tree from this reduced set.
However, this pipeline approach introduces a significant bottleneck. If the supertagger prunes the correct tag, the parser cannot recover, leading to "error propagation." Oracle experiments demonstrate that aggressive pruning significantly lowers the theoretical accuracy ceiling of the parser. This paper addresses the problem by replacing the pipeline with an integrated model where the supertagger and parser influence each other.
Integrated Inference via Factor Graphs
The authors propose a single, integrated model where supertagging and parsing are treated as components of a unified system. Because exact inference in such a combined model is computationally prohibitive, two approximate inference algorithms are compared:
- Loopy Belief Propagation (BP): The model is represented as a factor graph. The supertagger (a sequence model) and the parser (a tree model) communicate by passing "messages" iteratively until they reach a consensus on the most likely tags.
- Dual Decomposition (DD): This approach decomposes the complex problem into two simpler sub-problems (tagging and parsing). It utilizes Lagrangian multipliers to penalize disagreements between the sub-models, forcing them to converge on a consistent solution.
This study provides the first side-by-side comparison of BP and DD on a complex, structured NLP task.
Experimental Setup
The models were evaluated using CCGbank, the standard corpus for CCG research. Training was conducted on Sections 02-21, with Section 00 used for development and Section 23 for testing. To ensure real-world applicability, evaluations were performed using both gold-standard and automatically assigned Part-of-Speech (POS) tags.
Key Insights and Results
The integrated approach allows the parser to "talk back" to the supertagger. If a high-probability tag chosen by the tagger prevents the formation of a valid sentence, the parser's feedback forces the system to reconsider alternatives that were previously pruned.
Convergence vs. Accuracy
An interesting empirical finding was the difference in behavior between the two inference methods. Belief Propagation often reached peak accuracy very quickly—sometimes in just a single iteration—even if mathematical convergence took longer. In contrast, Dual Decomposition was slower to improve initially but provided a more principled path to exact consensus.
State-of-the-Art Performance
The integrated model achieved a labelled dependency F-measure of 88.8% on gold POS tags and 86.7% on automatic POS tags. These results represent a new state-of-the-art for CCG parsing, outperforming previous benchmarks like the C&C and Petrov parsers. While the integrated model is significantly more accurate, it is 10x to 30x slower than highly optimized pipeline systems, highlighting a trade-off between speed and precision.
Conclusion and Future Work
The success of the integrated model demonstrates that overcoming error propagation is key to advancing CCG parsing accuracy. Future research will focus on optimizing runtime for production environments and exploring joint training, where supertagger and parser weights are optimized simultaneously. Additionally, integrating POS tagging directly into the factor graph could further reduce the impact of upstream errors.
Summary updated