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

• I1. en/src/ptag.rs and en/src/parse.rs: split the parser into a per-word label step with a fixed window and a transition step that only resolves what the labels leave open. Measure LAS on EWT test with and without the window labels, and on PUD as an out-of-domain check.
• I2. Coverage report: as in the paper, count the share of test sentences the parser covers without any fallback. Add this line to en parse-eval on EWT test, PUD and GUM (GUM is test only).
• I3. Speed profile: record sentences per second of en parse-eval before and after any change to the search bound. Run twice and check that the two runs are identical before a speed claim.

For Mova

The chapters are 20. Syntax: the Universal Dependencies frame 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.

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, 6 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
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
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
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

This page in Markdown → https://md.mova.elamur.ai/free/en/docs/papers/aclbulk-2014-lewis-ccg-parsing-supertag-factored-model/