Abstract
We combine two complementary ideas for learning supertaggers from highly ambiguous lexicons: grammar-informed tag transitions and models minimized via integer programming. Each strategy on its own greatly improves performance over basic expectation-maximization training with a bitag Hidden Markov Model, which we show on the CCGbank and CCG-TUT corpora. The strategies provide further error reductions when combined. We describe a new two-stage integer programming strategy that efficiently deals with the high degree of ambiguity on these datasets while obtaining the full effect of model minimization.
Introduction
Supertagging is a fundamental task in natural language processing, particularly within the framework of Combinatory Categorial Grammar (CCG). While standard part-of-speech (POS) tagging involves a relatively small set of tags (e.g., ~45 in the Penn Treebank), supertagging requires assigning complex categories that encode syntactic combinatory potential. In the standard English CCGbank, there are over 1,200 distinct supertags.
This complexity leads to extreme ambiguity. For instance, the most ambiguous word in the English CCGbank can be associated with 126 different supertags. Standard semi-supervised learning techniques, such as Expectation-Maximization (EM), often fail in this high-dimensional search space when only provided with a lexicon and unlabeled text. This paper proposes a method to guide the model toward linguistically plausible and computationally sparse solutions.
Methodology
The authors introduce two primary strategies to improve supertagging performance in the absence of large-scale labeled data.
Grammar-Informed Initialization (GI)
Instead of initializing the EM algorithm with uniform or random probabilities, the authors leverage the underlying logic of CCG. CCG is governed by universal rules—such as functional application and composition—that define how categories can legally combine. By biasing the model's initial transition probabilities toward these "legal" combinations, the model starts from a linguistically informed state, significantly aiding convergence.
Model Minimization via Integer Programming (IP)
Applying the principle of Occam’s Razor, the authors seek the most parsimonious grammar that explains the observed data. This is framed as an optimization problem: find the minimum number of tag-to-tag transitions (grammar variables) necessary to account for the word sequences in the corpus.
The Two-Stage IP Strategy
Directly solving the IP for a large supertag set is computationally intractable. To address this, the authors developed a two-stage minimization process:
- MIN1: Minimizes the set of tag transitions required to explain every word bigram type in the data.
- MIN2: Further refines this set to explain the specific word sequences (sentences) in the corpus.
This approach ensures that the model remains sparse, effectively filtering out the "noise" of thousands of improbable transitions that typically plague EM.
Experimental Results
The proposed methods were evaluated on the English CCGbank and the Italian CCG-TUT corpora. The experiments focused on "unfiltered" lexicons to maintain the realistic difficulty of the task.
The results demonstrate a powerful synergy between Grammar-Informed initialization and IP-based minimization. As shown in the table below, the baseline EM model achieves only 38.7% accuracy on ambiguous tokens. Incorporating GI alone improves this to 56.3%, while IP alone reaches 52.1%. When combined (EM_GI + IP_GI), the accuracy climbs to 59.6%, and further to 64.3% when punctuation is excluded.
Similar trends were observed in the Italian CCG-TUT dataset, confirming that the approach is robust across different languages and grammar formalisms.
Conclusion
By combining linguistic priors with mathematical optimization for sparsity, this work significantly improves the state-of-the-art for semi-supervised supertagging. The two-stage IP strategy provides a scalable solution for high-ambiguity tagging tasks. While a gap remains compared to fully supervised models, this approach nearly halves the error rate of standard semi-supervised baselines, offering a promising path for low-resource grammar induction and lexicon refinement.
Summary updated