Elamur Research⌕
☰
home / papers / 2017 / Macro Grammars and Holistic Triggering for Efficient Semantic Parsing

Macro Grammars and Holistic Triggering for Efficient Semantic Parsing

Paper · 2017 · Yuchen Zhang, Panupong Pasupat and Percy Liang

Summary

Training a semantic parser from question–answer pairs alone is expensive. Without annotated logical forms, the learner must explore a huge space of candidate programs to find ones that produce the correct answer. Zhang, Pasupat and Liang address this with an online learning algorithm whose search gets cheaper over time. Each consistent logical form it discovers is abstracted into a macro: its relations and entities become placeholders, leaving a reusable computation template. These templates make up a macro grammar.

For a new question, holistic triggering selects only the macro rules that came from the K most similar training utterances. Because rules are tied to whole-sentence similarity rather than specific phrases, the method copes with lexical variation. The full base grammar is used only when the macros fail, and any new consistent form it finds is added to the macro grammar. At test time only the macro grammar is used.

On WikiTableQuestions, the authors first widen the search space of the Pasupat and Liang (2015) parser, setting a new state of the art. Adding macros then brings large speedups and a small further accuracy gain.

Key points

  • Expanding the base grammar of the Pasupat and Liang (2015) parser raises WikiTableQuestions test accuracy from 38.7% (Haug et al., 2017) to 42.7%. Macro grammars push it to 43.7%.
  • Macro grammars make training 11x faster and prediction 16x faster than using the base grammar alone. The baseline parser builds about 8,400 partial logical forms per example at beam size 100.
  • Accuracy peaks at K = 40 neighbors for holistic triggering. A competitive macro grammar needs base-grammar fallback on under 15% of the training data.
  • A faster setting (B = 50, K = 40, m = 2000 fallbacks) reaches 40.2% dev accuracy versus 40.4%. It speeds training up 15x and prediction 20x.
  • Logical forms are written in lambda DCS over Wikipedia tables. Code and data are released on CodaLab.

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

 Institutions

🎓Stanford UniversityStanford · United States434 works · 314,419 citations

 Fields, topics and concepts

📚 Shelves 4The 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 works

🧭 Topics 1Research subjects and languages the work is about.Semantic parsing & meaning representation · 185 works

Cite

Cite as Yuchen Zhang, Panupong Pasupat and Percy Liang. 2017. Macro Grammars and Holistic Triggering for Efficient Semantic Parsing. Proceedings of the 2017 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/d17-1125

@inproceedings{zhang2017macro,
  title = {{Macro Grammars and Holistic Triggering for Efficient Semantic Parsing}},
  author = {Yuchen Zhang, Panupong Pasupat and Percy Liang},
  booktitle = {Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing},
  year = {2017},
  doi = {10.18653/v1/d17-1125},
  url = {https://doi.org/10.18653/v1/d17-1125}
}

References

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

  1. Y. Artzi and L. Zettlemoyer. 2013. UW SPF: The University of Washington semantic parsing framework. arXiv preprint arXiv:1311.3011. find
  2. J. Berant, A. Chou, R. Frostig, and P. Liang. 2013. Semantic parsing on Freebase from question-answer pairs. In Empirical Methods in Natural Language Processing (EMNLP).
  3. J. Berant and P. Liang. 2014. Semantic parsing via paraphrasing. In Association for Computational Linguistics (ACL).
  4. J. Berant and P. Liang. 2015. Imitation learning of agenda-based semantic parsers. Transactions of the Association for Computational Linguistics (TACL), 3:545–558.
  5. D. L. Chen and R. J. Mooney. 2011. Learning to interpret natural language navigation instructions from observations. In Association for the Advancement of Artificial Intelligence (AAAI), pages 859–865. find
  6. J. Clarke, D. Goldwasser, M. Chang, and D. Roth. 2010. Driving semantic parsing from the world’s response. In Computational Natural Language Learning (CoNLL), pages 18–27. find
  7. A. Desai, S. Gulwani, V. Hingorani, N. Jain, A. Karkare, M. Marron, S. R, and S. Roy. 2016. Program synthesis using natural language. In International Conference on Software Engineering (ICSE), pages 345–356. find
  8. L. Dong and M. Lapata. 2016. Language to logical form with neural attention. In Association for Computational Linguistics (ACL).
  9. J. Duchi, E. Hazan, and Y. Singer. 2010. Adaptive subgradient methods for online learning and stochastic optimization. In Conference on Learning Theory (COLT). grammars from logical form with higher-order unification. In Empirical Methods in Natural Language Processing (EMNLP), pages 1223–1233. find
  10. A. Fader, L. Zettlemoyer, and O. Etzioni. 2013. Paraphrase-driven learning for open question answering. In Association for Computational Linguistics (ACL).
  11. T. Kwiatkowski, L. Zettlemoyer, S. Goldwater, and M. Steedman. 2011. Lexical generalization in CCG grammar induction for semantic parsing. In Empirical Methods in Natural Language Processing (EMNLP), pages 1512–1523.
  12. K. Guu, P. Pasupat, E. Z. Liu, and P. Liang. 2017. From language to programs: Bridging reinforcement learning and maximum marginal likelihood. In Association for Computational Linguistics (ACL).
  13. C. Liang, J. Berant, Q. Le, and K. D. F. N. Lao. 2017. Neural symbolic machines: Learning semantic parsers on Freebase with weak supervision. In Association for Computational Linguistics (ACL). find
  14. T. Haug, O. Ganea, and P. Grnarova. 2017. Neural multi-step reasoning for question answering on semi-structured tables. arXiv preprint arXiv:1702.06589. — [arXiv:1702.06589](https://arxiv.org/abs/1702.06589) find
  15. P. Liang. 2013. Lambda dependency-based compositional semantics. arXiv preprint arXiv:1309.4408. find
  16. P. Indyk. 2004. Approximate nearest neighbor under edit distance via product metrics. In Symposium on Discrete Algorithms (SODA), pages 646–650. find
  17. R. Jia and P. Liang. 2016. Data recombination for neural semantic parsing. In Association for Computational Linguistics (ACL). find
  18. M. Johnson, T. Griffiths, and S. Goldwater. 2006. Adaptor grammars: A framework for specifying compositional nonparametric Bayesian models. In Advances in Neural Information Processing Systems (NIPS), pages 641–648. find
  19. R. J. Kate and R. J. Mooney. 2006. Using string-kernels for learning semantic parsers. In International Conference on Computational Linguistics and Association for Computational Linguistics (COL-ING/ACL), pages 913–920.
  20. T. Kociský, G. Melis, E. Grefenstette, C. Dyer, W. Ling, P. Blunsom, and K. M. Hermann. 2016. Semantic parsing with semi-supervised sequential autoencoders. In Empirical Methods in Natural Language Processing (EMNLP), pages 1078–1087. find
  21. J. Krishnamurthy and T. Kollar. 2013. Jointly learning to parse and perceive: Connecting natural language to the physical world. Transactions of the Association for Computational Linguistics (TACL), 1:193– 206.
  22. N. Kushman and R. Barzilay. 2013. Using semantic unification to generate regular expressions from natural language. In Human Language Technology and North American Association for Computational Linguistics (HLT/NAACL), pages 826–836. find
  23. P. Liang, M. I. Jordan, and D. Klein. 2011. Learning dependency-based compositional semantics. In Association for Computational Linguistics (ACL), pages 590–599. find
  24. A. Neelakantan, Q. V. Le, and I. Sutskever. 2016. Neural programmer: Inducing latent programs with gradient descent. In International Conference on Learning Representations (ICLR). find
  25. T. J. O’Donnell. 2011. Productivity and Reuse in Language. Ph.D. thesis, Massachusetts Institute of Technology. find
  26. P. Pasupat and P. Liang. 2015. Compositional semantic parsing on semi-structured tables. In Association for Computational Linguistics (ACL).
  27. H. Poon and P. Domingos. 2009. Unsupervised semantic parsing. In Empirical Methods in Natural Language Processing (EMNLP).
  28. S. Reddy, O. Täckström, M. Collins, T. Kwiatkowski, D. Das, M. Steedman, and M. Lapata. 2016. Transforming dependency structures to logical forms for semantic parsing. In Association for Computational Linguistics (ACL), pages 127–140. find
  29. Y. W. Wong and R. J. Mooney. 2007. Learning synchronous grammars for semantic parsing with lambda calculus. In Association for Computational Linguistics (ACL), pages 960–967.
  30. L. S. Zettlemoyer and M. Collins. 2007. Online learning of relaxed CCG grammars for parsing to logical form. In Empirical Methods in Natural Language Processing and Computational Natural Language Learning (EMNLP/CoNLL), pages 678–687. find
  31. T. Kwiatkowski, E. Choi, Y. Artzi, and L. Zettlemoyer. 2013. Scaling semantic parsers with on-the-fly ontology matching. In Empirical Methods in Natural Language Processing (EMNLP).
  32. T. Kwiatkowski, L. Zettlemoyer, S. Goldwater, and M. Steedman. 2010. Inducing probabilistic CCG find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/zhang-2017-macro-grammars-holistic-triggering-efficient/