Learning Context-Dependent Mappings from Sentences to Logical Form
Summary
The paper tackles semantic parsing for dialogue-like interactions, where a sentence's meaning often relies on earlier turns. For example, a follow-up request to list only the morning departures can be interpreted only after the flight constraints from earlier turns are known. Zettlemoyer and Collins learn from ATIS interactions in which each sentence is annotated only with its final lambda-calculus logical form. They converted the original SQL annotations by hand.
Analysis runs in two stages:
- Parsing: a probabilistic CCG parser, extended with typed reference placeholders, builds an underspecified meaning that does not depend on context.
- Resolution: a series of steps fills or edits that meaning using logical forms from earlier turns.
A single weighted linear model scores both stages. Because all intermediate decisions are unannotated, they are treated as hidden variables and learned with a hidden-variable perceptron, using approximate search.
On the ATIS DEC94 test set, the system produces fully correct logical forms 83.7% of the time. This beats the fully supervised approach of Miller et al. (1996), which needed far richer annotation, so the work shows that context-dependent interpretation can be learned from final meanings alone.
Key points
- Data: ATIS (Dahl et al., 1994), split into train (300 interactions / 2956 sentences), dev (99 / 857) and the standard DEC94 test set (127 / 826), for 526 interactions and 4637 sentences in total.
- Test results:
- Exact-match accuracy is 83.7%, compared with 78.4% for Miller et al. (1996).
- Partial-match scores on individual attributes are P 95.0, R 96.5 and F1 95.7.
- Context window (dev set):
- With no context (M=0), exact accuracy is only 45.4%.
- Using the last utterance (M=1) raises it to 79.8%.
- M=3 gives the best result at 82.1%.
- Error propagation: supplying gold-standard previous logical forms instead of system outputs gives 85.5% on dev. This gain of roughly 3 points suggests that errors carried over from earlier turns hurt only modestly.
- Setup:
- The CCG lexicon is hand-engineered: it was induced with the ZC07 algorithm on context-independent ATIS data, then manually corrected.
- Training runs for 4 perceptron iterations.
- Parsing features come from Zettlemoyer and Collins (2007), and context features include distance indicators.
Interesting ideas
- I1. Type-shifting rules for unmarked context: the parser can insert references even with no anaphoric word present, as in a one-word follow-up like "cheapest." This covers elliptical turns, which are common in real dialogue.
- I2. Hidden-variable learning: treating the whole derivation as latent and training a perceptron only against final outputs avoids the cost of annotating every intermediate decision. The same trick suits any pipeline where only end results are easy to label.
- I3. Context-limit and gold-context ablations: varying how many previous turns are visible, and comparing system-produced with gold context, separately measures how much history is needed and how much errors cascade. This is a cheap and informative evaluation design for any sequential task.
- I4. Recency prior at initialization: giving the distance features small negative starting weights builds in a mild preference for recent antecedents before learning begins.
For Mova
How these ideas could serve Mova, our small open language model — its files, stages and tests:
- Typed reference placeholders: markers such as
!eor!<e,t>let the parser leave a typed "hole" that a later stage fills from the discourse. This cleanly separates grammar from discourse resolution, which could transfer to coreference-aware parsing or multi-turn query systems.
Topics Semantic parsing & meaning representation
Institutions
United StatesCite
Cite as Luke Zettlemoyer and Michael Collins. 2009. Learning Context-Dependent Mappings from Sentences to Logical Form. Proceedings of the Joint Conference of the 47th Annual Meeting of the ACL and the 4th International Joint Conference on Natural Language Processing of the AFNLP.
@inproceedings{zettlemoyer2009learning,
title = {{Learning Context-Dependent Mappings from Sentences to Logical Form}},
author = {Luke Zettlemoyer and Michael Collins},
booktitle = {Proceedings of the Joint Conference of the 47th Annual Meeting of the ACL and the 4th International Joint Conference on Natural Language Processing of the AFNLP},
year = {2009},
doi = {10.3115/1690219.1690283},
url = {https://doi.org/10.3115/1690219.1690283}
}References
- Johan Bos, Stephen Clark, Mark Steedman, James R. Curran, and Julia Hockenmaier. 2004. Wide-coverage semantic representations from a CCG parser. In Proceedings of the International Conference on Computational Linguistics. find
- Jaime G. Carbonell and Philip J. Hayes. 1983. Recovery strategies for parsing extragrammatical language. American Journal of Computational Linguistics, 9. find
- Stephen Clark and James R. Curran. 2003. Log-linear models for wide-coverage CCG parsing. In Proceedings of the Conference on Empirical Methods in Natural Language Processing. find
- Michael Collins. 2002. Discriminative training methods for hidden markov models: Theory and experiments with perceptron algorithms. In Proceedings of the Conference on Empirical Methods in Natural Language Processing. our card
- Deborah A. Dahl, Madeleine Bates, Michael Brown, William Fisher, Kate Hunicke-Smith, David Pallett, Christine Pao, Alexander Rudnicky, and Elizabeth Shriberg. 1994. Expanding the scope of the ATIS task: the ATIS-3 corpus. In ARPA HLT Workshop. find
- Ruifang Ge and Raymond J. Mooney. 2005. A statistical semantic parser that integrates syntax and semantics. In Proceedings of the Conference on Computational Natural Language Learning. find
- Yulan He and Steve Young. 2006. Spoken language understanding using the hidden vector state model. Speech Communication, 48(3-4). find
- Mark Johnson, Stuart Geman, Steven Canon, Zhiyi Chi, and Stefan Riezler. 1999. Estimators for stochastic “unification-based” grammars. In Proc. of the Association for Computational Linguistics. find
- John Lafferty, Andrew McCallum, and Fernando Pereira. 2001. Conditional random fields: Probabilistic models for segmenting and labeling sequence data. In Proceedings of the International Conference on Machine Learning. find
- E. Levin, S. Narayanan, R. Pieraccini, K. Biatov, E. Bocchieri, G. Di Fabbrizio, W. Eckert, S. Lee, A. Pokrovsky, M. Rahim, P. Ruscitti, and M. Walker. 2000. The AT&T darpa communicator mixed-initiative spoken dialogue system. In Proceedings of the International Conference on Spoken Language Process… find
- Scott Miller, David Stallard, Robert J. Bobrow, and Richard L. Schwartz. 1996. A fully statistical approach to natural language interfaces. In Proc. of the Association for Computational Linguistics. find
- K. A. Papineni, S. Roukos, and T. R. Ward. 1997. Feature-based language understanding. In Proceedings of European Conference on Speech Communication and Technology. find
- Ana-Maria Popescu, Alex Armanasu, Oren Etzioni, David Ko, and Alexander Yates. 2004. Modern natural language interfaces to databases: Composing statistical parsing with semantic tractability. In Proceedings of the International Conference on Computational Linguistics. find
- Ganesh N. Ramaswamy and Jan Kleindienst. 2000. Hierarchical feature-based translation for scalable natural language understanding. In Proceedings of International Conference on Spoken Language Processing. find
- Stephanie Seneff. 1992. Robust parsing for spoken language systems. In Proc. of the IEEE Conference on Acoustics, Speech, and Signal Processing. find
- Mark Steedman. 1996. Surface Structure and Interpretation. The MIT Press. find
- Mark Steedman. 2000. The Syntactic Process. The MIT Press. find
- Lappoon R. Tang and Raymond J. Mooney. 2000. Automated construction of database interfaces: Integrating statistical and relational learning for semantic parsing. In Proceedings of the Joint Conference on Empirical Methods in Natural Language Processing and Very Large Corpora. find
- Ben Taskar, Dan Klein, Michael Collins, Daphne Koller, and Christopher Manning. 2004. Max-margin parsing. In Proceedings of the Conference on Empirical Methods in Natural Language Processing. find
- Wayne Ward and Sunil Issar. 1994. Recent improvements in the CMU spoken language understanding system. In Proceedings of the workshop on Human Language Technology. find
- Stephen Watkinson and Suresh Manandhar. 1999. Unsupervised lexical learning with categorial grammars using the LLL corpus. In Proceedings of the 1st Workshop on Learning Language in Logic. find
- Yuk Wah Wong and Raymond Mooney. 2007. Learning synchronous grammars for semantic parsing with lambda calculus. In Proceedings of the Association for Computational Linguistics. our card
- John M. Zelle and Raymond J. Mooney. 1996. Learning to parse database queries using inductive logic programming. In Proceedings of the National Conference on Artificial Intelligence. our card
- Luke S. Zettlemoyer and Michael Collins. 2005. Learning to map sentences to logical form: Structured classification with probabilistic categorial grammars. In Proceedings of the Conference on Uncertainty in Artificial Intelligence. our card
- Luke S. Zettlemoyer and Michael Collins. 2007. Online learning of relaxed CCG grammars for parsing to logical form. In Proc. of the Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning. find
This page in Markdown → https://md.research.elamur.ai/free/en/papers/zettlemoyer-2009-learning-context-dependent-mappings-sentences/