Generating CCG Categories

Yufang Liu, Tao Ji, Yuanbin Wu, Man Lan

Abstract

Previous Combinatory Categorial Grammar (CCG) supertaggers typically predict categories using multi-class classification. Despite their simplicity, these models often ignore the internal structures of categories. The rich semantics within these structures are vital for handling relations among categories and improving supertagger robustness. In this work, we propose generating categories rather than classifying them: each category is decomposed into a sequence of smaller atomic tags, and the tagger aims to generate the correct sequence. This finer view allows for shared annotations across different categories and enhanced interaction with sentence contexts. Our proposed category generator achieves state-of-the-art tagging (95.5% accuracy) and parsing (89.8% labeled F1) on the standard CCGBank. Furthermore, its performance on infrequent and unseen categories, out-of-domain texts, and low-resource languages demonstrates the promise of generative models for general CCG analyses.

Introduction

In Combinatory Categorial Grammar (CCG), words are assigned "supertags" (categories) that dictate how they combine with neighbors to form a sentence. For instance, a transitive verb might be assigned the tag (S\NP)/NP, indicating it seeks a Noun Phrase (NP) to its right and then another to its left to form a Sentence (S).

Traditionally, NLP models treat these tags as atomic labels in a massive multi-class classification problem. This approach suffers from two major flaws: sparsity and the "unseen" wall. With thousands of possible categories, many appear only a few times in training data, making it difficult for classifiers to learn the "long-tail." Furthermore, a standard classifier can never predict a category it hasn't seen during training, even if that category is a logical combination of known parts.

Methodology: From Classification to Generation

We shift the paradigm from classification to generation by decomposing categories into their internal structures. We propose two primary architectures to handle this task:

  1. Tag-wise Generator: For every word in a sentence, an LSTM decoder generates a sequence of atomic tags (e.g., (, S, \, NP, ), /, NP). This approach is fast and allows for parallelization across the sentence.
  2. Transition-based Generator: This utilizes a stack-based transition system, similar to a shift-reduce parser, to ensure that every generated category is mathematically well-formed.
The transition-based system decomposes the generation of (S\NP)/NP into a sequence of stack and buffer operations.

To optimize performance, we also implemented Decoding Oracles using different atomic vocabularies and a Re-ranker that combines scores from the generator with a standard category classifier to leverage the strengths of both approaches.

Key Insights

  • Compositionality: The internal structure of a tag is highly informative. By decomposing tags, the model shares knowledge across related categories that utilize similar combining strategies.
  • Zero-Shot Capabilities: Because the model learns to assemble atoms, it can "invent" new categories. It successfully predicted the correct category for words with "unseen" tags in up to 21% of cases—a feat impossible for traditional classifiers.
  • Attention Mechanisms: Adding attention allows the generator to "look back" at the sentence context while deciding which atomic part to generate next, significantly boosting accuracy.

Results and Performance

The generative approach was evaluated on CCGBank, out-of-domain benchmarks (Wikipedia & Bioinfer), and the Italian CCGBank.

Learning curves showing the accuracy of the proposed generative models (CG, CGNG2, rerank) compared to the classification baseline (CC).
  • State-of-the-Art Accuracy: The model achieved 95.5% tagging accuracy on CCGBank (96.1% with BERT), outperforming previous classification-based models.
  • Handling the Long Tail: On infrequent categories (appearing 10–100 times), the generator outperformed the classifier significantly (65.83% vs 60.41%).
  • Robustness: The generation approach proved more resilient on out-of-domain data compared to the baseline, maintaining higher accuracy when faced with unfamiliar text styles.

Limitations and Future Work

While highly accurate, generating tags step-by-step is computationally more expensive than single-shot classification; the tag-wise generator operates at roughly 40% the speed of the baseline. Additionally, while the transition-based model guarantees valid tags, the faster tag-wise model can occasionally generate invalid structures (though this occurs in less than 0.05% of cases). Future work will explore non-deterministic oracles and improved handling of specific grammatical features to further enhance the accuracy of generated unseen categories.

Summary updated

Abstract

Previous CCG supertaggers usually predict categories using multi-class classification. Despite their simplicity, internal structures of categories are usually ignored. The rich semantics inside these structures may help us to better handle relations among categories and bring more robustness into existing supertaggers. In this work, we propose to generate categories rather than classify them: each category is decomposed into a sequence of smaller atomic tags, and the tagger aims to generate the correct sequence. We show that with this finer view on categories, annotations of different categories could be shared and interactions with sentence contexts could be enhanced. The proposed category generator is able to achieve state-of-the-art tagging (95.5% accuracy) and parsing (89.8% labeled F1) performances on the standard CCGBank. Furthermore, its performances on infrequent (even unseen) categories, out-of-domain texts and low resource language give promising results on introducing generation models to the general CCG analyses.
BibTeX
@inproceedings{liu2021generating,
  author = {Yufang Liu and Tao Ji and Yuanbin Wu and Man Lan},
  title = {{Generating CCG Categories}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2021},
  url = {https://openreview.net/forum?id=r2fl628CAGq},
}
Figure