Elamur Research⌕
☰
home / papers / 2015 / Imitation Learning of Agenda-based Semantic Parsers

Imitation Learning of Agenda-based Semantic Parsers

Paper · 2015 · Jonathan Berant and Percy Liang

Summary

Semantic parsers that answer questions over large knowledge bases like Freebase usually build logical forms bottom-up, span by span, keeping a fixed-size beam per chart cell. This wastes effort on huge numbers of partial parses that never contribute to the final answer. Even a short question can yield over a million candidate parses. Berant and Liang replace this with an agenda-based parser, where a priority queue decides which partial derivation to construct next. The scoring policy for this queue is learned through imitation learning: parsing is framed as a Markov decision process, and supervision comes only from question–answer pairs, not annotated logical forms. They also introduce a lazy agenda, which groups related derivations into streams that are expanded only when needed. In addition, they add new features that better connect phrases to KB predicates. On WebQuestions, the parser builds about ten times fewer partial parses and runs 6x–9x faster than fixed-order parsing, with comparable accuracy (49.7%). The work shows that learned search control can make semantic parsing over large KBs much cheaper.

Key points

  • Setup: trained on the WebQuestions dataset against Freebase (41M entities, 19K properties, 596M assertions), using simple λ-DCS logical forms and a grammar with 11 semantic functions (e.g., JOIN, LEX, INTERSECT, BRIDGE).
  • Results: AgendaIL performs an order of magnitude fewer parsing actions and achieves a 6x–9x speedup over a FixedOrder beam parser, at 49.7% accuracy. In one example, it built 1,198 derivations versus 15,543 for FixedOrder.
  • Lazy agenda: derivation streams cut the number of parses scored during training by 35% and give roughly a 1.5x training speedup. The NoStream variant was slower and slightly less accurate.
  • Feature ablation: removing the new template that conjoins binaries and lemmas during bridging (BinaryAndLemma) substantially lowers accuracy.
  • Code, data and experiments are released on the CodaLab platform.

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 Jonathan Berant and Percy Liang. 2015. Imitation Learning of Agenda-based Semantic Parsers. Transactions of the Association for Computational Linguistics.

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.1162/tacl_a_00157

@article{berant2015imitation,
  title = {{Imitation Learning of Agenda-based Semantic Parsers}},
  author = {Jonathan Berant and Percy Liang},
  journal = {Transactions of the Association for Computational Linguistics},
  year = {2015},
  doi = {10.1162/tacl\_a\_00157},
  url = {https://doi.org/10.1162/tacl_a_00157}
}

References

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

  1. P. Abbeel and A. Ng. 2004. Apprenticeship learning via inverse reinforcement learning. In International Conference on Machine Learning (ICML). find
  2. M. Auli and A. Lopez. 2011. Efficient CCG parsing: A* versus adaptive supertagging. In Association for Computational Linguistics (ACL). find
  3. J. Bao, N. Duan, M. Zhou, and T. Zhao. 2014. Knowledge-based question answering as machine translation. In Association for Computational Linguistics (ACL). find
  4. J. Berant and P. Liang. 2014. Semantic parsing via paraphrasing. In Association for Computational Linguistics (ACL).
  5. 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).
  6. N. Bodenstab, A. Dunlop, K. Hall, and B. Roark. 2011. Beam-width prediction for efficient context-free parsing. In Association for Computational Linguistics (ACL), pages 440–449. find
  7. A. Bordes, S. Chopra, and J. Weston. 2014. Question answering with subgraph embeddings. In Empirical Methods in Natural Language Processing (EMNLP). find
  8. Q. Cai and A. Yates. 2013. Large-scale semantic parsing via schema matching and lexicon extension. In Association for Computational Linguistics (ACL). 8 Our system uses the SEMPRE toolkit (http://nlp. stanford.edu/software/sempre). find
  9. S. A. Caraballo and E. Charniak. 1998. New figures of merit for best-first probabilistic chart parsing. Computational Linguistics, 24:275–298.
  10. K. Chang, A. Krishnamurthy, A. Agarwal, H. Daume, and J. Langford. 2015. Learning to search better than your teacher. arXiv. find
  11. 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
  12. H. Daume, J. Langford, and D. Marcu. 2009. Search-based structured prediction. Machine Learning, 75:297–325. find
  13. J. Duchi, E. Hazan, and Y. Singer. 2010. Adaptive subgradient methods for online learning and stochastic optimization. In Conference on Learning Theory (COLT). find
  14. N. FitzGerald, Y. Artzi, and L. S. Zettlemoyer. 2013. Learning distributions over logical forms for referring expression generation. In Empirical Methods in Natural Language Processing (EMNLP), pages 1914– 1925. find
  15. Y. Goldberg and J. Nivre. 2013. Training deterministic parsers with non-deterministic oracles. Transactions of the Association for Computational Linguistics (TACL), 1. find
  16. Google. 2013. Freebase data dumps (2013-06-09). https://developers.google.com/ freebase/data. ↗
  17. L. Huang and D. Chiang. 2005. Better k-best parsing. In Proceedings of the Ninth International Workshop on Parsing Technology, pages 53–64. find
  18. L. Huang and D. Chiang. 2007. Forest rescoring: Faster decoding with integrated language models. In Association for Computational Linguistics (ACL).
  19. L. Huang. 2008. Forest reranking: Discriminative parsing with non-local features. In Association for Computational Linguistics (ACL). find
  20. J. Jiang, A. Teichert, J. Eisner, and H. Daume. 2012. Learned prioritization for trading off accuracy and speed. In Advances in Neural Information Processing Systems (NIPS). find
  21. M. Kay. 1986. Algorithm Schemata and Data Structures in Syntactic Processing. Readings in Natural Language Processing. find
  22. D. Klein and C. Manning. 2003. A* parsing: Fast exact viterbi parse selection. In Human Language Technology and North American Association for Computational Linguistics (HLT/NAACL). find
  23. J. Krishnamurthy and T. Mitchell. 2012. Weakly supervised training of semantic parsers. In Empirical Methods in Natural Language Processing and Computational Natural Language Learning (EMNLP/CoNLL), pages 754–765.
  24. J. Kummerfeld, J. Roesner, T. Dawborn, J. Haggerty, J. Curran, and S. Clark. 2010. Faster parsing by supertagger adaptation. In Association for Computational Linguistics (ACL). find
  25. T. Kwiatkowski, L. Zettlemoyer, S. Goldwater, and M. Steedman. 2010. Inducing probabilistic CCG grammars from logical form with higher-order unification. In Empirical Methods in Natural Language Processing (EMNLP), pages 1223–1233. find
  26. 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).
  27. M. Lewis and M. Steedman. 2014. A* CCG parsing with a supertag-factored model. In Empirical Methods in Natural Language Processing (EMNLP).
  28. P. Liang, M. I. Jordan, and D. Klein. 2011. Learning dependency-based compositional semantics. In Association for Computational Linguistics (ACL), pages 590–599. find
  29. P. Liang. 2013. Lambda dependency-based compositional semantics. arXiv. find
  30. C. D. Manning, M. Surdeanu, J. Bauer, J. Finkel, S. J. Bethard, and D. McClosky. 2014. The Stanford CoreNLP natural language processing toolkit. In ACL system demonstrations.
  31. C. Matuszek, N. FitzGerald, L. Zettlemoyer, L. Bo, and D. Fox. 2012. A joint model of language and perception for grounded attribute learning. In International Conference on Machine Learning (ICML), pages 1671–1678. find
  32. A. Pauls and D. Klein. 2009. K-best A* parsing. In Association for Computational Linguistics (ACL), pages 958–966. find
  33. S. Ross, G. Gordon, and A. Bagnell. 2011. A reduction of imitation learning and structured prediction to no-regret online learning. In Artificial Intelligence and Statistics (AISTATS). find
  34. A. Rush and S. Petrov. 2012. Vine pruning for efficient multi-pass dependency parsing. In Human Language Technology and North American Association for Computational Linguistics (HLT/NAACL). find
  35. R. Sutton, D. McAllester, S. Singh, and Y. Mansour. 1999. Policy gradient methods for reinforcement learning with function approximation. In Advances in Neural Information Processing Systems (NIPS). find
  36. S. Tellex, T. Kollar, S. Dickerson, M. R. Walter, A. G. Banerjee, S. J. Teller, and N. Roy. 2011. Understanding natural language commands for robotic navigation and mobile manipulation. In Association for the Advancement of Artificial Intelligence (AAAI). find
  37. Z. Wang, S. Yan, H. Wang, and X. Huang. 2014. An overview of Microsoft deep QA system on Stanford WebQuestions benchmark. Technical report, Microsoft Research. find
  38. 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.
  39. M. Yang, N. Duan, M. Zhou, and H. Rim. 2014. Joint relational embeddings for knowledge-based question answering. In Empirical Methods in Natural Language Processing (EMNLP). find
  40. X. Yao and B. Van-Durme. 2014. Information extraction over structured data: Question answering with Freebase. In Association for Computational Linguistics (ACL). find
  41. W. Yih, M. Chang, X. He, and J. Gao. 2015. Semantic parsing via staged query graph generation: Question answering with knowledge base. In Association for Computational Linguistics (ACL).
  42. M. Zelle and R. J. Mooney. 1996. Learning to parse database queries using inductive logic programming. In Association for the Advancement of Artificial Intelligence (AAAI), pages 1050–1055.
  43. L. S. Zettlemoyer and M. Collins. 2005. Learning to map sentences to logical form: Structured classification with probabilistic categorial grammars. In Uncertainty in Artificial Intelligence (UAI), pages 658–666.
  44. 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
  45. Y. Zhang, B. Ahn, S. Clark, C. V. Wyk, J. R. Curran, and L. Rimell. 2010. Chart pruning for fast lexicalised-grammar parsing. In International Conference on Computational Linguistics (COLING). find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/berant-2015-imitation-learning-agenda-based-semantic/