The Importance of Supertagging for Wide-Coverage CCG Parsing

What it is about

The paper shows how a supertagger, which gives each word only a few CCG categories, speeds up a wide-coverage log-linear CCG parser. The supertagger is tightly integrated with the grammar and the parser, so the parser asks for more categories only when it fails to find an analysis. A threshold beta controls how many categories the first pass keeps. Two normal-form constraints on derivations cut memory needs by 48%. Depending on the strategy, parse times fall by 72% to 90%. A setting with 94% coverage parses almost 50 sentences a second. The paper's companion model reaches 84.6 F-score on labelled dependencies.

Ideas

I1. en/src/ptag.rs: add a probability threshold on the tagger's output with a ladder of settings, loose first and tighter on failure. Report LAS, coverage and seconds on EWT test in en parse-eval, using the paper's ladder as the template.
I2. Derivation filter: a rule that bans arc patterns the treebank never uses, applied as a transition filter in en/src/parse.rs. Count how many transitions it removes and measure LAS and speed on EWT test.
I3. Coverage-speed table: report the trade-off between the share of parsed sentences and sentences per second, as the paper's 94% row does, for EWT test.

For Mova

The chapters are languages/en/20-syntax-overview.md and 21-clause-structure.md; the code is en/src/ptag.rs and en/src/parse.rs. The paper's numbers are for CCG and are not comparable with LAS. Its data are WSJ-derived and outside our licence list, so test on EWT only, with two identical runs before any claim.

Library summary

The Research library's own summary of the paper, in our words — not the paper's text.

Written for the Research library (claude-opus-5-5) from the paper text, in our own words: the license "CC BY-NC-SA 3.0 (ACL Anthology, before 2016)" does not allow redistributing the text itself. Original — aclanthology.org/C04-1041.pdf

Summary

Clark and Curran investigate how a supertagger, a statistical tagger that assigns CCG lexical categories to words before parsing, affects a wide-coverage CCG parser trained discriminatively with a log-linear model. Discriminative estimation needs every derivation of every training sentence, so the derivation space must be kept small. The supertagger is a Maximum Entropy multi-tagger trained on sections 2-21 of CCGbank. For each word it proposes every category whose probability lies within a factor β of the best one, and it is restricted by a tag dictionary. The authors integrate it tightly with the parser. The parser starts with very few categories per word and asks for more only when no spanning analysis is found. Normal-form constraints on category combination and a chart beam prune the search further. Together these techniques make the parser about 77 times faster with no loss in accuracy or coverage. The result is roughly ten times faster than comparable parsers for linguistically motivated formalisms. It shows that supertagging works with an automatically extracted grammar, which earlier LTAG attempts had not achieved.

Key points

Category set: Keeping only categories that occur at least 10 times in sections 2-21 of CCGbank leaves 409 category types instead of 1,225. On section 00, 0.2% of category tokens are missing from this reduced set.
Supertagger accuracy (section 00, gold POS):
- At β = 0.1, the tagger assigns about 1.4 categories per word with 97.0% per-word accuracy.
- Using the full tag dictionary entry gives 21.9 categories per word and 99.1% accuracy.
- Accuracy drops when automatically assigned POS tags are used.
Memory cost of training: Even with packed charts, discriminative training needed about 30 GB of memory, which motivated a parallel implementation.
Speed gains:
- Normal-form (Eisner) constraints cut parse times by 72% under the old strategy and 84% under the new one.
- The new strategy alone cuts times by 83–90%.
- The beam removes a further 33% at a cost of 0.3% labelled F-score.
- A reduced-coverage setting (94%) parses about 50 sentences per second, and slightly more with the beam.
Comparison with other systems:
- LFG parser from Kaplan et al.: 1.9 sentences per second.
- Collins parser: 2.8 sentences per second.
- LTAG supertagging by Sarkar et al.: parsed only 1,324 of 2,250 test sentences and took over 5 hours.

Interesting ideas

Let the grammar judge the tagger. Start with the most restrictive tagger setting and relax it only when the parser fails to find a spanning analysis. This lets the downstream component decide whether the cheap first pass was good enough, and the pattern fits any pipeline with a fast filter followed by an expensive model.
Tag with a probability threshold, not a single best label. Keeping every category within a factor β of the best one trades ambiguity against recall in a way that is easy to tune. This is useful for morphologically rich languages, where hard 1-best decisions cause errors to propagate.
Back off by word frequency. Frequent words may only receive categories seen with them in training, while rare words fall back to a dictionary keyed on POS tag. This is a simple way to restrict the label space without losing robustness on rare words.
Use an oracle to locate the bottleneck. Feeding the parser only the correct categories gives almost 98% labelled F-score. That measures how much accuracy and speed are held back by the tagger rather than the parser, and the same evaluation trick works for any staged system.
Repair instead of reparse. The authors suggest re-processing only the chart regions likely to contain errors rather than parsing again from scratch. This is an attractive direction for incremental or resource-limited processing.

Cite

The paper itself, not this card. BibTeX from the library's record of the work. DOI 10.3115/1220355.1220396

@inproceedings{clark2004importance,
  title = {{The Importance of Supertagging for Wide-Coverage CCG Parsing}},
  author = {Clark, Stephen and Curran, James R.},
  booktitle = {COLING 2004: Proceedings of the 20th International Conference on Computational Linguistics},
  year = {2004},
  doi = {10.3115/1220355.1220396},
  url = {https://doi.org/10.3115/1220355.1220396}
}

References

18 references, 1 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

Srinivas Bangalore and Aravind Joshi. 1999. Supertagging: An approach to almost parsing. Computational Linguistics, 25(2):237–265. find our card
John Chen and K. Vijay-Shanker. 2000. Automated extraction of TAGS from the Penn Treebank. In Proceedings of IWPT 2000, Trento, Italy. find
John Chen, Srinivas Bangalore, and K. Vijay-Shanker. 1999. New models for improving supertag disambiguation. In Proceedings of the 9th Meeting of EACL, Bergen, Norway. find
John Chen, Srinivas Bangalore, Michael Collins, and Owen Rambow. 2002. Reranking an N-gram supertagger. In Proceedings of the TAG+ Workshop, pages 259–268, Venice, Italy. find
Stephen Clark and James R. Curran. 2003. Log-linear models for wide-coverage CCG parsing. In Proceedings of the EMNLP Conference, pages 97–104, Sapporo, Japan. find
Stephen Clark and James R. Curran. 2004. Parsing the WSJ using CCG and log-linear models. In Proceedings of the 42nd Meeting of the ACL, Barcelona, Spain. find
Stephen Clark, Julia Hockenmaier, and Mark Steedman. 2002. Building deep dependency structures with a wide-coverage CCG parser. In Proceedings of the 40th Meeting of the ACL, pages 327–334, Philadelphia, PA. find
Stephen Clark. 2002. A supertagger for Combinatory Categorial Grammar. In Proceedings of the TAG+ Workshop, pages 19–24, Venice, Italy. find
Michael Collins. 1999. Head-Driven Statistical Models for Natural Language Parsing. Ph.D. thesis, University of Pennsylvania. find
James R. Curran and Stephen Clark. 2003. Investigating GIS and smoothing for maximum entropy taggers. In Proceedings of the 10th Meeting of the EACL, pages 91–98, Budapest, Hungary. find
Jason Eisner. 1996. Efficient normal-form parsing for Combinatory Categorial Grammar. In Proceedings of the 34th Meeting of the ACL, pages 79–86, Santa Cruz, CA. find
Julia Hockenmaier and Mark Steedman. 2002. Acquiring compact lexicalized grammars from a cleaner treebank. In Proceedings of the Third LREC Conference, pages 1974–1981, Las Palmas, Spain. find
Julia Hockenmaier. 2003. Data and Models for Statistical Parsing with Combinatory Categorial Grammar. Ph.D. thesis, University of Edinburgh. find
Ronald M. Kaplan, Stefan Riezler, Tracy H. King, John T. Maxwell III, Alexander Vasserman, and Richard Crouch. 2004. Speed and accuracy in shallow and deep stochastic parsing. In Proceedings of the HLT/NAACL Conference, Boston, MA. find
Jorge Nocedal and Stephen J. Wright. 1999. Numerical Optimization. Springer, New York, USA. find
Miles Osborne. 2000. Estimation of stochastic attribute-value grammars using an informative sample. In Proceedings of the 18th International Conference on Computational Linguistics, pages 586–592, Saarbrücken, Germany. find
Anoop Sarkar, Fei Xia, and Aravind Joshi. 2000. Some experiments on indicators of parsing complexity for lexicalized grammars. In Proceedings of the COLING Workshop on Efficiency in Large-Scale Parsing Systems, pages 37–42, Luxembourg. find
Mark Steedman. 2000. The Syntactic Process. The MIT Press, Cambridge, MA. find