Elamur Research⌕
☰
home / papers / 2016 / Simpler Context-Dependent Logical Forms via Model Projections

Simpler Context-Dependent Logical Forms via Model Projections

Paper · 2016 · Reginald Long, Panupong Pasupat and Percy Liang

Summary

The paper tackles learning to carry out multi-step instructions when the only supervision is the resulting world state, not the logical forms behind it. Without annotated logical forms or a seed lexicon, the learner must search a huge space of candidate programs. Utterances that refer back to earlier steps through ellipsis, pronouns or repeated actions make that space even larger. Long, Pasupat and Liang respond by projecting a full parser onto coarser models that treat groups of logical forms as equivalent:

  • Model A keeps alignments between words and predicates.
  • Model B discards alignments and predicts whole logical forms.
  • Model C replaces arguments with concrete world objects, producing flat forms.

The authors also introduce a left-to-right parser that needs no explicit span alignment. They collect three grounded datasets via Amazon Mechanical Turk: ALCHEMY, SCENE and TANGRAMS. With a fixed beam, the simplest model, Model C, usually wins. On a synthetic task with a large beam, Model A becomes perfect. Because all three models share features, weights from Model C can initialize Model A. The study shows how trading expressivity for tractability can pay off, and it supplies new benchmarks for context-dependent semantic parsing.

Key points

  • Datasets: ALCHEMY (4560 examples), SCENE (4402) and TANGRAMS (4989) were collected via Amazon Mechanical Turk. Each example has 5 utterances describing successive world-state changes. They cover ellipsis, entity anaphora and action anaphora.
  • Context references: The grammar includes special tokens args[i][j] and actions[i], which point to arguments and actions of earlier logical forms. References are resolved jointly during parsing rather than in a separate step.
  • Synthetic task: Model A learns nothing with beam sizes below 240 but reaches 100% accuracy above that. Model C is best at small beams (under 40).
  • Bootstrapping: Initializing Model A with Model C's parameters gives 100% even with smaller beams.
  • Error analysis: Model B's errors come mostly from correct forms falling off the beam (47%). Model C's errors come mostly from misreading context (50%), reflecting its limited expressivity. Code and data are available 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 States506 works · 330,052 citations

 Fields, topics and concepts

📚 Shelves 4The field of science this work belongs to (OpenAlex fields).Computer Science · 18,614 worksArtificial Intelligence · 17,965 worksArts and Humanities · 17,450 worksLanguage and Linguistics · 17,296 works

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

Cite

Cite as Reginald Long, Panupong Pasupat and Percy Liang. 2016. Simpler Context-Dependent Logical Forms via Model Projections. arXiv:1606.05378.

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.48550/arxiv.1606.05378 · arXiv 1606.05378

@misc{long2016simpler,
  title = {{Simpler Context-Dependent Logical Forms via Model Projections}},
  author = {Reginald Long, Panupong Pasupat and Percy Liang},
  year = {2016},
  doi = {10.48550/arxiv.1606.05378},
  eprint = {1606.05378},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.48550/arxiv.1606.05378}
}

References

30 references, 11 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. Weakly supervised learning of semantic parsers for mapping instructions to actions. Transactions of the Association for Computational Linguistics (TACL), 1:49–62.
  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. A. Bordes, S. Chopra, and J. Weston. 2014. Question answering with subgraph embeddings. In Empirical Methods in Natural Language Processing (EMNLP). find
  4. S. R. Bowman, C. Potts, and C. D. Manning. 2014. Can recursive neural tensor networks learn logical reasoning? In International Conference on Learning Representations (ICLR). find
  5. Q. Cai and A. Yates. 2013. Large-scale semantic parsing via schema matching and lexicon extension. In Association for Computational Linguistics (ACL). find
  6. 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
  7. D. L. Chen. 2012. Fast online lexicon learning for grounded language acquisition. In Association for Computational Linguistics (ACL). find
  8. 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
  9. D. A. Dahl, M. Bates, M. Brown, W. Fisher, K. Hunicke-Smith, D. Pallett, C. Pao, A. Rudnicky, and E. Shriberg. 1994. Expanding the scope of the ATIS task: The ATIS-3 corpus. In Workshop on Human Language Technology, pages 43–48.
  10. J. Duchi, E. Hazan, and Y. Singer. 2010. Adaptive subgradient methods for online learning and stochastic optimization. In Conference on Learning Theory (COLT). find
  11. K. Guu, J. Miller, and P. Liang. 2015. Traversing knowledge graphs in vector space. In Empirical Methods in Natural Language Processing (EMNLP). find
  12. 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
  13. 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.
  14. P. Liang, M. I. Jordan, and D. Klein. 2009. Learning semantic correspondences with less supervision. In Association for Computational Linguistics and International Joint Conference on Natural Language Processing (ACL-IJCNLP), pages 91–99.
  15. P. Liang. 2013. Lambda dependency-based compositional semantics. arXiv. find
  16. 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
  17. F. J. Och and H. Ney. 2003. A systematic comparison of various statistical alignment models. Computational Linguistics, 29:19–51. find
  18. P. Pasupat and P. Liang. 2014. Zero-shot entity extraction from web pages. In Association for Computational Linguistics (ACL). find
  19. P. Pasupat and P. Liang. 2015. Compositional semantic parsing on semi-structured tables. In Association for Computational Linguistics (ACL).
  20. S. Reed and N. de Freitas. 2016. Neural programmer-interpreters. In International Conference on Learning Representations (ICLR). find
  21. J. Steinhardt and P. Liang. 2015. Learning with relaxed supervision. In Advances in Neural Information Processing Systems (NIPS). find
  22. A. Vlachos and S. Clark. 2014. A new corpus and imitation learning framework for context-dependent semantic parsing. Transactions of the Association for Computational Linguistics (TACL), 2:547–559. find
  23. Y. Wang, J. Berant, and P. Liang. 2015. Building a semantic parser overnight. In Association for Computational Linguistics (ACL). find
  24. J. Weston, A. Bordes, S. Chopra, and T. Mikolov. 2015. Towards AI-complete question answering: A set of prerequisite toy tasks. arXiv.
  25. 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.
  26. X. Yao, J. Berant, and B. Van-Durme. 2014. Freebase QA: Information extraction or semantic parsing. In Workshop on Semantic parsing. find
  27. 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.
  28. 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.
  29. 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
  30. L. S. Zettlemoyer and M. Collins. 2009. Learning context-dependent mappings from sentences to logical form. In Association for Computational Linguistics and International Joint Conference on Natural Language Processing (ACL-IJCNLP).

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/long-2016-simpler-context-dependent-logical-forms/