Elamur Research
☰
home / papers / 2014 / A* CCG Parsing with a Supertag-factored Model

A* CCG Parsing with a Supertag-factored Model

What it is about

The question is whether CCG parsing needs a full model of derivations and dependencies, or whether a model of lexical categories is enough. The parser (EasyCCG) takes the most probable sequence of categories that supports a CCG derivation. Its features are word embeddings, capitalization and two-character suffixes, with no POS tagger. An A* search with a simple heuristic parses exactly, without beam or pruning, at almost 50 sentences per second. Very mild pruning raises the speed to 186 sentences per second. The authors report that the parser is more accurate than the C&C pipeline out of domain, four times faster, and has higher coverage. It is not state of the art on CCGbank.

Ideas

For Mova

The chapters are languages/en/20-syntax-overview.md and 21-clause-structure.md; the code is en/src/parse.rs with en/src/ptag.rs. The numbers are CCG dependency F-scores and cannot be compared with LAS. Measure first: coverage and LAS on EWT test, with the two runs identical.

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/D14-1107.pdf

Summary

The paper addresses the complexity and heavy pruning of existing CCG parsers, such as the C&C parser. These systems chain POS tagging, supertagging and a separate parsing model, and their search restrictions can discard the correct analysis. Lewis and Steedman instead place the entire statistical model in the lexicon. A supertagger assigns each word a probability distribution over all 425 CCG categories, using a ±3 word window, word embeddings, 2-character suffixes and capitalization, with no POS tagger. Parsing then searches for the most probable category sequence that a small hand-coded set of combinators can assemble into a full derivation. Ties are broken deterministically by preferring longer dependency arcs. Because the score factors over words, an A* heuristic gives a tight upper bound on outside probability, so parsing is exact and fast without beam search. The resulting parser, EASYCCG, beats C&C out-of-domain, runs about four times faster and has higher coverage. It also improves a downstream question answering system. The work shows that a very simple, lexically factored model can compete with complex pipelines.

Key points

  • The grammar uses 425 lexical categories and 10 binary plus 13 unary rule schemata. The supertagger relies on 50-dimensional Turian et al. (2010) embeddings, which are fine-tuned during supervised training.
  • C&C prunes hard: its initial beam keeps about 1.2 categories per word, and its loosest beam keeps about 3.57. Even that loosest setting loses the correct parse for 20% of sentences.
  • EASYCCG parses nearly 50 sentences per second with exact search and 186 per second with mild pruning, with little accuracy loss. Compared with the null heuristic, the A* heuristic doubles parsing speed (excluding supertagging).
  • Adding a tag dictionary lowered accuracy only slightly, from 83.46 to 83.37, on CCGBank Section 23, but caused one test sentence to fail to parse.
  • Using EASYCCG inside the Reddy et al. (2014) QA system raised oracle accuracy by roughly 4 points compared with C&C. The parser is a simple Java implementation released as EASYCCG on GitHub (mikelewis0/easyccg).

Interesting ideas

  • Factor the model on tagging decisions. If a formalism is strongly lexicalized, almost all parsing decisions can be pushed into a local tagger, leaving a deterministic grammar for structure. This idea could carry over to other lexicalized formalisms, such as LTAG or HPSG-style setups.
  • Cheap, tight A bound.* The outside estimate assumes every word outside a span takes its single best tag. This is a per-sentence upper bound that can be cached, and it is often exact because the tagger is accurate. Any search over independently scored local choices could use the same kind of bound.
  • Deterministic tie-breaking by arc length. Parses with equal scores are ranked by the total length of their dependencies, which favours non-local attachments. The authors chose this direction because it worked better on development data. It is a zero-parameter way to resolve ambiguity that a model cannot score.
  • No POS tagger, embeddings instead. Using pretrained word embeddings in place of POS features removes one stage of error propagation. It also helps generalization to unseen words, which is attractive for lower-resource languages or noisy domains.
  • Evaluate parsers through a downstream task. Measuring parser quality via QA performance, including 100-best oracle scores, shows how much headroom a parser gives a later semantic component, beyond what treebank metrics capture.

Cite

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

@inproceedings{lewis2014ccg,
  title = {{A* CCG Parsing with a Supertag-factored Model}},
  author = {Lewis, Mike and Steedman, Mark},
  booktitle = {Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP)},
  year = {2014},
  doi = {10.3115/v1/d14-1107},
  url = {https://doi.org/10.3115/v1/d14-1107}
}

References

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

  1. Omri Abend and Ari Rappoport. 2013. Universal conceptual cognitive annotation (ucca). In Proceedings of ACL. find our card
  2. Michael Auli and Adam Lopez. 2011a. A comparison of loopy belief propagation and dual decomposition for integrated CCG supertagging and parsing. In Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies-Volume 1, pages 470–480. Associatio… find
  3. Michael Auli and Adam Lopez. 2011b. Efficient CCG parsing: A* versus adaptive supertagging. In Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies-Volume 1, pages 1577–1585. Association for Computational Linguistics. find
  4. Jason Baldridge and Geert-Jan M Kruijff. 2003. Multimodal combinatory categorial grammar. In Proceedings of the tenth conference on European chapter of the Association for Computational Linguistics-Volume 1, pages 211–218. Association for Computational Linguistics. find
  5. Laura Banarescu, Claire Bonial, Shu Cai, Madalina Georgescu, Kira Griffitt, Ulf Hermjakob, Kevin Knight, Philipp Koehn, Martha Palmer, and Nathan Schneider. 2013. Abstract Meaning Representation for sembanking. In Proceedings of the 7th Linguistic Annotation Workshop and Interoperability with Discou… find our card
  6. Srinivas Bangalore and Aravind K Joshi. 1999. Supertagging: An approach to almost parsing. Computational linguistics, 25(2):237–265. find our card
  7. Jonathan Berant, Andrew Chou, Roy Frostig, and Percy Liang. 2013. Semantic parsing on freebase from question-answer pairs. In Proceedings of EMNLP. find
  8. Johan Bos. 2008. Wide-coverage semantic analysis with boxer. In Johan Bos and Rodolfo Delmonte, editors, Semantics in Text Processing. find
  9. STEP 2008 Conference Proceedings, Research in Computational Semantics, pages 277–286. College Publications. find
  10. Stephen Clark and James R Curran. 2007. Wide-coverage efficient statistical parsing with CCG and log-linear models. Computational Linguistics, 33(4):493–552. find our card
  11. Ronan Collobert, Jason Weston, Léon Bottou, Michael Karlen, Koray Kavukcuoglu, and Pavel Kuksa. 2011. Natural language processing (almost) from scratch. The Journal of Machine Learning Research, 12:2493–2537. find our card
  12. Ronan Collobert. 2011. Deep learning for efficient discriminative parsing. In International Conference on Artificial Intelligence and Statistics, number EPFL-CONF-192374. find
  13. Gregory F Coppola, Alexandra Birch, Tejaswini Deoskar, and Mark Steedman. 2011. Simple semi-supervised learning for prepositional phrase attachment. In Proceedings of the 12th International Conference on Parsing Technologies, pages 129–139. Association for Computational Linguistics. find
  14. Tejaswini Deoskar, Christos Christodoulopoulos, Alexandra Birch, and Mark Steedman. Generalizing a Strongly Lexicalized Parser using Unlabeled Data. In Proceedings of the 14th Conference of the European Chapter of the Association for Computational Linguistics. Association for Computational Linguisti… find
  15. Jason Eisner. 1996. Efficient normal-form parsing for combinatory categorial grammar. In Proceedings of the 34th annual meeting on Association for Computational Linguistics, pages 79–86. Association for Computational Linguistics. find
  16. Timothy AD Fowler and Gerald Penn. 2010. Accurate context-free parsing with combinatory categorial grammar. In Proceedings of the 48th Annual Meeting of the Association for Computational Linguistics, pages 335–344. Association for Computational Linguistics. find
  17. Yoav Goldberg and Michael Elhadad. 2010. An efficient algorithm for easy-first non-directional dependency parsing. In Human Language Technologies: The 2010 Annual Conference of the North American Chapter of the Association for Computational Linguistics, pages 742–750. Association for Computational L… find
  18. Brian Harrington. 2010. A semantic network approach to measuring relatedness. In Proceedings of the 23rd International Conference on Computational Linguistics: Posters, COLING ’10, pages 356–364. Association for Computational Linguistics. find
  19. Julia Hockenmaier and Mark Steedman. 2007. CCGbank: a corpus of CCG derivations and dependency structures extracted from the Penn Treebank. Computational Linguistics, 33(3):355–396. find our card
  20. Julia Hockenmaier. 2003. Data and models for statistical parsing with combinatory categorial grammar. find
  21. Matthew Honnibal and James R Curran. 2009. Fully lexicalising CCGbank with hat categories. In Proceedings of the 2009 Conference on Empirical Methods in Natural Language Processing: Volume 3-Volume 3, pages 1212–1221. Association for Computational Linguistics. find
  22. Dan Klein and Christopher D Manning. 2003a. A* parsing: fast exact viterbi parse selection. In Proceedings of the 2003 Conference of the North American Chapter of the Association for Computational Linguistics on Human Language Technology-Volume 1, pages 40–47. Association for Computational Linguisti… find
  23. Dan Klein and Christopher D Manning. 2003b. Accurate unlexicalized parsing. In Proceedings of the 41st Annual Meeting on Association for Computational Linguistics-Volume 1, pages 423–430. Association for Computational Linguistics. find our card
  24. Jayant Krishnamurthy and Tom M Mitchell. 2014. Joint syntactic and semantic parsing with combina-2014. tory categorial grammar. June. find
  25. Jonathan K. Kummerfeld, Jessika Roesner, Tim Daw-born, James Haggerty, James R. Curran, and Stephen Clark. 2010. Faster parsing by supertagger adaptation. In Proceedings of the 48th Annual Meeting of the Association for Computational Linguistics, ACL ’10, pages 345–355. Association for Computational… find
  26. Mike Lewis and Mark Steedman. 2013a. Combined Distributional and Logical Semantics. Transactions of the Association for Computational Linguistics, 1:179–192. find
  27. Mike Lewis and Mark Steedman. 2013b. Unsupervised induction of cross-lingual semantic relations. In Proceedings of the 2013 Conference on Empirical Methods in Natural Language Processing, pages 681–692, Seattle, Washington, USA, October. Association for Computational Linguistics. find
  28. Mike Lewis and Mark Steedman. 2014. Improved CCG parsing with Semi-supervised Supertagging. Transactions of the Association for Computational Linguistics (to appear). find
  29. Takashi Ninomiya, Takuya Matsuzaki, Yoshimasa Tsuruoka, Yusuke Miyao, and Jun’ichi Tsujii. 2006. Extremely lexicalized models for accurate and fast hpsg parsing. In Proceedings of the 2006 Conference on Empirical Methods in Natural Language Processing, EMNLP ’06, pages 155–163, Stroudsburg, PA, USA.… find
  30. Joakim Nivre. 2003. An efficient algorithm for projective dependency parsing. In Proceedings of the 8th International Workshop on Parsing Technologies (IWPT. find our card
  31. Sampo Pyysalo, Filip Ginter, Juho Heimonen, Jari Björne, Jorma Boberg, Jouni Järvinen, and Tapio Salakoski. 2007. Bioinfer: a corpus for information extraction in the biomedical domain. BMC bioinformatics, 8(1):50. find
  32. Siva Reddy, Mirella Lapata, and Mark Steedman. 2014. Large-scale Semantic Parsing without Question-Answer Pairs. Transactions of the Association for Computational Linguistics (to appear). find
  33. Laura Rimell and Stephen Clark. 2008. Adapting a lexicalized-grammar parser to contrasting domains. In Proceedings of the Conference on Empirical Methods in Natural Language Processing, pages 475–484. Association for Computational Linguistics. find
  34. Mark Steedman. 2000. The Syntactic Process. MIT Press. find
  35. Mark Steedman. 2012. Taking Scope: The Natural Semantics of Quantifiers. MIT Press. find
  36. Emily Thomforde and Mark Steedman. 2011. Semi-supervised CCG lexicon extension. In Proceedings of the Conference on Empirical Methods in Natural Language Processing, pages 1246–1256. Association for Computational Linguistics. find
  37. Stephen Tratz and Eduard Hovy. 2011. A fast, effective, non-projective, semantically-enriched parser. In Proceedings of EMNLP. find
  38. Joseph Turian, Lev Ratinov, and Yoshua Bengio. 2010. Word representations: a simple and general method for semi-supervised learning. In Proceedings of the 48th Annual Meeting of the Association for Computational Linguistics, pages 384–394. Association for Computational Linguistics. find our card
  39. Wenduan Xu, Stephen Clark, and Yue Zhang. 2014. Shift-reduce ccg parsing with a dependency model. In Proceedings of the 52nd Annual Meeting of the Association for Computational Linguistics (ACL 2014). Association for Computational Linguistics, June. find
  40. Yue Zhang and Stephen Clark. 2011. Shift-reduce CCG parsing. In Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies-Volume 1, pages 683–692. Association for Computational Linguistics. find