Elamur Research⌕
☰
home / papers / 2016 / Neural Shift-Reduce CCG Semantic Parsing

Neural Shift-Reduce CCG Semantic Parsing

Paper · 2016 · Dipendra Kumar Misra and Yoav Artzi

Summary

Semantic parsers built on CCG usually rely on CKY-style dynamic programming, which requires a polynomial number of operations and is too slow for large-scale or real-time use. Misra and Artzi propose a shift-reduce CCG semantic parser whose cost grows linearly with sentence length. A multilayer perceptron builds a rich representation of the parser state from simple feature embeddings. Each candidate action is represented cheaply by concatenating embeddings, so the model can score a variable and often large set of actions. Because AMR training data contain sentence–logical form pairs without derivations, the model is bootstrapped from an existing log-linear CKY parser (Artzi et al., 2015). An iterative learner chooses the best tree when many correct ones exist and falls back on partial derivations when the CKY parser produces no parse. On AMR, the new parser matches its CKY teacher while performing far fewer operations, and it remains strong under greedy decoding. This makes CCG semantic parsing practical and offers a general recipe for distilling slow structured predictors into fast ones.

Key points

  • On the AMR test set, the shift-reduce ensemble reaches 66.1 SMATCH F1, compared with 66.3 for the CKY parser and 63.2 for JAMR. The state of the art, Wang et al. (2015), scores 70.0.
  • The parser uses roughly two orders of magnitude fewer operations than CKY. Its wall-clock time is about 3× faster on average and up to 10× faster on long sentences.
  • Greedy decoding with beam 1 yields 59.77 SMATCH F1 on the development set, while the CKY parser with beam 1 drops to 19.2 F1.
  • The lexicon has 1.7M entries, so each step involves 146 candidate actions on average and as many as 2K at most. CKY supervision can produce as many as 49K correct parses for a single sentence.
  • Learning from partial derivations added 370K features, about 22% of the observed embeddings. The models were built with Deeplearning4j, and the code and pre-trained models are publicly released.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

 Fields, topics and concepts

📚 Shelves 6The field of science this work belongs to (OpenAlex fields).Computer Science · 16,667 worksArtificial Intelligence · 16,194 worksArts and Humanities · 16,039 worksLanguage and Linguistics · 15,891 worksNeuroscience · 165 worksCognitive Neuroscience · 164 works

🧭 Topics 2Research subjects and languages the work is about.Syntax & grammar formalisms · 214 worksSemantic parsing & meaning representation · 185 works

Cite

Cite as Dipendra Kumar Misra and Yoav Artzi. 2016. Neural Shift-Reduce CCG Semantic Parsing. Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing.

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.18653/v1/d16-1183

@inproceedings{misra2016neural,
  title = {{Neural Shift-Reduce CCG Semantic Parsing}},
  author = {Dipendra Kumar Misra and Yoav Artzi},
  booktitle = {Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing},
  year = {2016},
  doi = {10.18653/v1/d16-1183},
  url = {https://doi.org/10.18653/v1/d16-1183}
}

References

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

  1. Ammar, W., Mulcaire, G., Ballesteros, M., Dyer, C., and Smith, N. A. (2016). Many languages, one parser. Transactions of the Association for Computational Linguistics.
  2. Andor, D., Alberti, C., Weiss, D., Severyn, A., Presta, A., Ganchev, K., Petrov, S., and Collins, M. (2016). Globally normalized transition-based neural networks. CoRR.
  3. Artzi, Y. (2016). Cornell SPF: Cornell semantic parsing framework. ArXiv e-prints. find
  4. Artzi, Y., Das, D., and Petrov, S. (2014). Learning compact lexicons for CCG semantic parsing. In Proceedings of the Conference on Empirical Methods in Natural Language Processing. find
  5. Artzi, Y., Lee, K., and Zettlemoyer, L. (2015). Broad-coverage CCG semantic parsing with AMR. In Proceedings of the Conference on Empirical Methods in Natural Language Processing.
  6. Artzi, Y. and Zettlemoyer, L. S. (2011). Bootstrapping semantic parsers from conversations. In Proceedings of the Conference on Empirical Methods in Natural Language Processing. find
  7. Artzi, Y. and Zettlemoyer, L. S. (2013). Weakly supervised learning of semantic parsers for mapping instructions to actions. Transactions of the Association for Computational Linguistics, 1.
  8. Ballesteros, M., Dyer, C., and Smith, N. A. (2015). Improved transition-based parsing by modeling characters instead of words with LSTMs.
  9. Banarescu, L., Bonial, C., Cai, S., Georgescu, M., Griffitt, K., Hermjakob, U., Knight, K., Koehn, P., Palmer, M., and Schneider, N. (2013). Abstract meaning representation for sembanking. In Proceedings of the Linguistic Annotation Workshop.
  10. Berant, J. and Liang, P. (2015). Imitation learning of agenda-based semantic parsers. Transactions of the Association for Computational Linguistics, 3.
  11. Cai, S. and Knight, K. (2013). Smatch: an evaluation metric for semantic feature structures. In Proceedings of the Conference of the Association of Computational Linguistics. find
  12. Chen, D. and Manning, C. D. (2014). A fast and accurate dependency parser using neural networks. In Proceedings of the Conference on Empirical Methods in Natural Language Processing.
  13. Collins, M. and Roark, B. (2004). Incremental parsing with the perceptron algorithm. In Proceedings of the Annual Meeting on Association for Computational Linguistics.
  14. Duchi, J., Hazan, E., and Singer, Y. (2011). Adaptive subgradient methods for online learning and stochastic optimization. The Journal of Machine Learning Research. find
  15. Dyer, C., Ballesteros, M., Ling, W., Matthews, A., and Smith, N. A. (2015). Transition-based dependency parsing with stack long short-term memory. In Proceedings of the Annual Meeting on Association for Computational Linguistics.
  16. Flanigan, J., Thomson, S., Carbonell, J., Dyer, C., and Smith, N. A. (2014). A discriminative graph-based parser for the Abstract Meaning Representation. In Proceedings of the Conference of the Association of Computational Linguistics.
  17. Garg, S., Galstyan, A., Hermjakob, U., and Marcu, D. (2016). Extracting biomolecular interactions using semantic parsing of biomedical text. In Proceedings of the Conference on Artificial Intelligence. find
  18. Glorot, X. and Bengio, Y. (2010). Understanding the difficulty of training deep feedforward neural networks. In International Conference on Artificial Intelligence and Statistics. find
  19. Glorot, X., Bordes, A., and Bengio, Y. (2011). Deep sparse rectifier neural networks. In International Conference on Artificial Intelligence and Statistics. find
  20. Goldberg, Y. and Nivre, J. (2013). Training deterministic parsers with non-deterministic oracles. Transactions of the Association for Computational Linguistics, 1. find
  21. Hockenmaier, J. and Steedman, M. (2007). CCG-Bank: A corpus of CCG derivations and dependency structures extracted from the Penn Treebank. Computational Linguistics. find
  22. Kim, J. and Mooney, R. J. (2012). Unsupervised PCFG induction for grounded language learning with highly ambiguous supervision. In Proceedings of the Conference on Empirical Methods in Natural Language Processing. find
  23. Kiperwasser, E. and Goldberg, Y. (2016). Simple and accurate dependency parsing using bidirectional LSTM feature representations. Transactions of the Association for Computational Linguistics, 4.
  24. Kushman, N. and Barzilay, R. (2013). Using semantic unification to generate regular expressions from natural language. In Proceedings of the Human Language Technology Conference of the North American Association for Computational Linguistics. find
  25. Kwiatkowski, T., Zettlemoyer, L. S., Goldwater, S., and Steedman, M. (2010). Inducing probabilistic CCG grammars from logical form with higher-order unification. In Proceedings of the Conference on Empirical Methods in Natural Language Processing. find
  26. Matuszek, C., FitzGerald, N., Zettlemoyer, L. S., Bo, L., and Fox, D. (2012). A joint model of language and perception for grounded attribute learning. In Proceedings of the International Conference on Machine Learning. find
  27. Pan, X., Cassidy, T., Hermjakob, U., Ji, H., and Knight, K. (2015). Unsupervised entity linking with Abstract Meaning Representation. In Proceedings of the North American Association for Computational Linguistics. find
  28. Pust, M., Hermjakob, U., Knight, K., Marcu, D., and May, J. (2015). Parsing english into abstract meaning representation using syntax-based machine translation. In Proceedings of the Conference on Empirical Methods in Natural Language Processing.
  29. Ratinov, L. and Roth, D. (2009). Design challenges and misconceptions in named entity recognition. In Proceedings of the Conference on Computational Natural Language Learning.
  30. Kwiatkowski, T., Zettlemoyer, L. S., Goldwater, S., and Steedman, M. (2011). Lexical generalization in CCG grammar induction for semantic parsing. In Proceedings of the Conference on Empirical Methods in Natural Language Processing.
  31. Sawai, Y., Shindo, H., and Matsumoto, Y. (2015). Semantic structure analysis of noun phrases using abstract meaning representation. In Proceedings of the annual meeting on Association for Computational Linguistics. find
  32. Lewis, M. and Steedman, M. (2014). A* CCG parsing with a supertag-factored model. In Proceedings of the Conference on Empirical Methods in Natural Language Processing.
  33. Steedman, M. (1996). Surface Structure and Interpretation. The MIT Press. find
  34. Liang, P., Jordan, M., and Klein, D. (2009). Learning semantic correspondences with less supervision. In Proceedings of the Joint Conference of the Association for Computational Linguistics the International Joint Conference on Natural Language Processing.
  35. Wang, C., Xue, N., and Pradhan, S. (2015a). Boosting transition-based amr parsing with refined actions and auxiliary analyzers. In Proceedings of the Annual Meeting of the Association for Computational Linguistics.
  36. Liu, F., Flanigan, J., Thomson, S., Sadeh, N., and Smith, N. A. (2015). Toward abstractive summarization using semantic representations. In Proceedings of the North American Association for Computational Linguistics.
  37. Manning, C. D., Surdeanu, M., Bauer, J., Finkel, J., Bethard, S. J., and McClosky, D. (2014). The Stanford CoreNLP natural language processing toolkit. In Proceedings of the Annual Meeting of the Association for Computational Linguistics.
  38. Steedman, M. (2000). The Syntactic Process. The MIT Press. find
  39. Wang, C., Xue, N., Pradhan, S., and Pradhan, S. (2015b). A transition-based algorithm for AMR parsing. In Proceedings of the North American Association for Computational Linguistics.
  40. Weiss, D., Alberti, C., Collins, M., and Petrov, S. (2015). Structured training for neural network transition-based parsing. In Proceedings of the annual meeting on Association for Computational Linguistics. find
  41. Zettlemoyer, L. S. and Collins, M. (2005). Learning to map sentences to logical form: Structured classification with probabilistic categorial grammars. In Proceedings of the Conference on Uncertainty in Artificial Intelligence.
  42. Zettlemoyer, L. S. and Collins, M. (2007). Online learning of relaxed CCG grammars for parsing to logical form. In Proceedings of the Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning. find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/misra-2016-neural-shift-reduce-ccg-semantic/