---
title: "Learning to Map Sentences to Logical Form — Zettlemoyer 2012"
description: "The proposed algorithm simultaneously induces a CCG (combinatory categorial grammar) and trains a log-linear… 23 references, cited by 345 papers here."
authors: ["Luke S. Zettlemoyer", "Michael Collins"]
year: 2012
venue: "arXiv:1207.1420"
source: "https://arxiv.org/abs/1207.1420"
doi: "10.48550/arxiv.1207.1420"
arxiv: "1207.1420"
licence: "arXiv — non-exclusive licence to distribute"
licence_url: "http://arxiv.org/licenses/nonexclusive-distrib/1.0/"
summary_licence: "Elamur Cosmic License"
canonical: "https://research.elamur.ai/free/en/papers/zettlemoyer-2012-learning-map-sentences-logical-form/"
---
[Elamur Research](https://md.research.elamur.ai/free/en/) · [this page in HTML](https://research.elamur.ai/free/en/papers/zettlemoyer-2012-learning-map-sentences-logical-form/)

[home](https://md.research.elamur.ai/free/en/) / [papers](https://md.research.elamur.ai/free/en/papers/) / [2012](https://md.research.elamur.ai/free/en/papers/2012/) / Learning to Map Sentences to Logical Form: Structured Classification with Probabilistic Categorial Grammars

# Learning to Map Sentences to Logical Form: Structured Classification with Probabilistic Categorial Grammars

**Authors:** [Luke S. Zettlemoyer](https://md.research.elamur.ai/free/en/authors/luke-zettlemoyer/) and [Michael Collins](https://md.research.elamur.ai/free/en/authors/michael-collins/) · **Year:** 2012 · **Venue:** arXiv:1207.1420 · **Licence:** [arXiv — non-exclusive licence to distribute](http://arxiv.org/licenses/nonexclusive-distrib/1.0/)

**Links:** [Publisher's page](https://arxiv.org/abs/1207.1420) · [PDF](https://arxiv.org/pdf/1207.1420) · [DOI 10.48550/arxiv.1207.1420](https://doi.org/10.48550/arxiv.1207.1420) · [arXiv 1207.1420](https://arxiv.org/abs/1207.1420)

**Citations:** [345](https://md.research.elamur.ai/free/en/papers/zettlemoyer-2012-learning-map-sentences-logical-form/cited-by/) in our library, of the 140,884 papers whose bibliographies we read

## Summary
The authors address the task of semantic parsing: a natural-language sentence must be mapped to a lambda-calculus formula that expresses its meaning. The main difficulty is that the training data contain only "sentence — logical form" pairs. They include no intermediate syntactic derivations, so the model must work out on its own which word corresponds to which predicate. The proposed algorithm simultaneously induces a CCG (combinatory categorial grammar) and trains a log-linear model similar to a CRF. This model defines probabilities over the possible parses of a sentence. The GENLEX procedure generates a large number of candidate lexical items, and the superfluous ones are pruned during training. The method was evaluated on queries to two databases: one on US geography (Geo880) and one on job listings (Jobs640). On both datasets, precision exceeded 95% and recall was 79%. In precision, the method outperformed the COCKTAIL system, even though that system was given a hand-built lexicon. The work showed that a natural-language interface to a database can be learned with minimal annotation. The approach later became one of the baselines in semantic parsing.

## Key points
- **Data:** Geo880 was split into 600 training and 280 test examples, and Jobs640 into 500 and 140. The authors manually rewrote the original Prolog annotation in lambda calculus.
- **Results:** precision above 95% and recall of 79% on both domains. Only a fully correct logical form was counted as correct. Compared with COCKTAIL, precision is higher and recall only slightly lower.
- **Compact lexicon:** on Geo880, GENLEX generated on average 393.8 candidates per example, and 5.1 remained after pruning. On Jobs640, this number dropped from 697.1 to 6.6.
- **Reason for the lower recall:** the system failed to parse about 9.3% of the training sentences in Geo880 and 8.7% in Jobs640. These are mostly complex constructions, for example with a preposition moved to the beginning of the sentence, for which GENLEX lacks the necessary rules.
- **Formalism:** CCG with application, composition and type-raising rules. Lexical items can consist of several words; for example, "the Mississippi" denotes a river.

*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: [AI & machine learning](https://md.research.elamur.ai/free/en/shelves/ai/)

Topics: [📐 Syntax & grammar formalisms](https://md.research.elamur.ai/free/en/topics/syntax-grammar/) · [🧾 Semantic parsing & meaning representation](https://md.research.elamur.ai/free/en/topics/semantic-parsing/)

## Cite

Cite as: Luke S. Zettlemoyer and Michael Collins. 2012. Learning to Map Sentences to Logical Form: Structured Classification with Probabilistic Categorial Grammars. arXiv:1207.1420.

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

```bibtex
@misc{zettlemoyer2012learning,
  title = {{Learning to Map Sentences to Logical Form: Structured Classification with Probabilistic Categorial Grammars}},
  author = {Luke S. Zettlemoyer and Michael Collins},
  year = {2012},
  doi = {10.48550/arxiv.1207.1420},
  eprint = {1207.1420},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.48550/arxiv.1207.1420}
}
```

- [← previous A Corpus for Research on Deliberation and Debate](https://md.research.elamur.ai/free/en/papers/walker-2012-corpus-research-deliberation-debate/)
- [next → Cross-lingual Word Clusters for Direct Transfer of Linguistic Structure](https://md.research.elamur.ai/free/en/papers/tackstrom-2012-cross-lingual-word-clusters-direct/)
- [↑ back to papers of 2012](https://md.research.elamur.ai/free/en/papers/2012/)

## References

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

1. Androutsopoulos, I., Ritchie, G., & Thanisch, P. (1995). Natural language interfaces to databases–an introduction. Journal of Language Engineering, 1(1), 29– 81. [find](https://scholar.google.com/scholar?q=Androutsopoulos%2C+I%2E%2C+Ritchie%2C+G%2E%2C+%26+Thanisch%2C+P%2E+%281995%29%2E+Natural+language+interfaces+to+databases%E2%80%93an+introduction%2E+Journal+of+Language+Engineering%2C+1%281%29%2C+29%E2%80%93+81%2E)
2. Baker, J. (1979). Trainable grammars for speech recognition. In Speech Communication Papers for the 97th Meeting of the Acoustical Society of America. [find](https://scholar.google.com/scholar?q=Baker%2C+J%2E+%281979%29%2E+Trainable+grammars+for+speech+recognition%2E+In+Speech+Communication+Papers+for+the+97th+Meeting+of+the+Acoustical+Society+of+America%2E)
3. Bos, J., Clark, S., Steedman, M., Curran, J. R., & Hockenmaier, J. (2004). Wide-coverage semantic representations from a CCG parser. In Proceedings of the 20th International Conference on Computational Linguistics, pp. 1240–1246. [find](https://scholar.google.com/scholar?q=Bos%2C+J%2E%2C+Clark%2C+S%2E%2C+Steedman%2C+M%2E%2C+Curran%2C+J%2E+R%2E%2C+%26+Hockenmaier%2C+J%2E+%282004%29%2E+Wide%2Dcoverage+semantic+representations+from+a+CCG+parser%2E+In+Proceedings+of+the+20th+International+Conference+on+Computationa)
4. Carpenter, B. (1997). Type-Logical Semantics. The MIT Press. [find](https://scholar.google.com/scholar?q=Carpenter%2C+B%2E+%281997%29%2E+Type%2DLogical+Semantics%2E+The+MIT+Press%2E)
5. Clark, S., & Curran, J. R. (2003). Log-linear models for wide-coverage CCG parsing. In Proceedings of the SIGDAT Conference on Empirical Methods in Natural Language Processing. [find](https://scholar.google.com/scholar?q=Clark%2C+S%2E%2C+%26+Curran%2C+J%2E+R%2E+%282003%29%2E+Log%2Dlinear+models+for+wide%2Dcoverage+CCG+parsing%2E+In+Proceedings+of+the+SIGDAT+Conference+on+Empirical+Methods+in+Natural+Language+Processing%2E)
6. He, Y., & Young, S. (2004). Semantic processing using the hidden vector state model. Computer Speech and Language. [find](https://scholar.google.com/scholar?q=He%2C+Y%2E%2C+%26+Young%2C+S%2E+%282004%29%2E+Semantic+processing+using+the+hidden+vector+state+model%2E+Computer+Speech+and+Language%2E)
7. Johnson, M., Geman, S., Canon, S., Chi, Z., & Riezler, S. (1999). Estimators for stochastic “unification-based” grammars. In Proceedings of the Association for Computational Linguistics, pp. 535–541. [find](https://scholar.google.com/scholar?q=Johnson%2C+M%2E%2C+Geman%2C+S%2E%2C+Canon%2C+S%2E%2C+Chi%2C+Z%2E%2C+%26+Riezler%2C+S%2E+%281999%29%2E+Estimators+for+stochastic+%E2%80%9Cunification%2Dbased%E2%80%9D+grammars%2E+In+Proceedings+of+the+Association+for+Computational+Linguistics%2C+pp%2E+535%E2%80%93541%2E)
8. Lafferty, J., McCallum, A., & Pereira, F. (2001). Conditional random fields: Probabilistic models for segmenting and labeling sequence data. In Proceedings of the 18th International Conference on Machine Learning. [find](https://scholar.google.com/scholar?q=Lafferty%2C+J%2E%2C+McCallum%2C+A%2E%2C+%26+Pereira%2C+F%2E+%282001%29%2E+Conditional+random+fields%3A+Probabilistic+models+for+segmenting+and+labeling+sequence+data%2E+In+Proceedings+of+the+18th+International+Conference+on+Mach)
9. LeCun, Y., Bottou, L., Bengio, Y., & Haffner, P. (1998). Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(11), 2278–2324. [find](https://scholar.google.com/scholar?q=LeCun%2C+Y%2E%2C+Bottou%2C+L%2E%2C+Bengio%2C+Y%2E%2C+%26+Haffner%2C+P%2E+%281998%29%2E+Gradient%2Dbased+learning+applied+to+document+recognition%2E+Proceedings+of+the+IEEE%2C+86%2811%29%2C+2278%E2%80%932324%2E)
10. Manning, C. D., & Schutze, H. (1999). Foundations of statistical natural language processing. The MIT Press. [find](https://scholar.google.com/scholar?q=Manning%2C+C%2E+D%2E%2C+%26+Schutze%2C+H%2E+%281999%29%2E+Foundations+of+statistical+natural+language+processing%2E+The+MIT+Press%2E)
11. Miller, S., Stallard, D., Bobrow, R. J., & Schwartz, R. L. (1996). A fully statistical approach to natural language interfaces. In Proceedings of the Association for Computational Linguistics, pp. 55–61. [find](https://scholar.google.com/scholar?q=Miller%2C+S%2E%2C+Stallard%2C+D%2E%2C+Bobrow%2C+R%2E+J%2E%2C+%26+Schwartz%2C+R%2E+L%2E+%281996%29%2E+A+fully+statistical+approach+to+natural+language+interfaces%2E+In+Proceedings+of+the+Association+for+Computational+Linguistics%2C+pp%2E+55%E2%80%93)
12. Papineni, K. A., Roukos, S., & Ward, T. R. (1997). Feature-based language understanding. In Proceedings of European Conference on Speech Communication and Technology. [find](https://scholar.google.com/scholar?q=Papineni%2C+K%2E+A%2E%2C+Roukos%2C+S%2E%2C+%26+Ward%2C+T%2E+R%2E+%281997%29%2E+Feature%2Dbased+language+understanding%2E+In+Proceedings+of+European+Conference+on+Speech+Communication+and+Technology%2E)
13. Popescu, A.-M., Armanasu, A., Etzioni, O., Ko, D., & Yates, A. (2004). Modern natural language interfaces to databases: Composing statistical parsing with semantic tractability. In Proceedings of the 20th International Conference on Computational Linguistics. [find](https://scholar.google.com/scholar?q=Popescu%2C+A%2E%2DM%2E%2C+Armanasu%2C+A%2E%2C+Etzioni%2C+O%2E%2C+Ko%2C+D%2E%2C+%26+Yates%2C+A%2E+%282004%29%2E+Modern+natural+language+interfaces+to+databases%3A+Composing+statistical+parsing+with+semantic+tractability%2E+In+Proceedings+of+the+)
14. Ramaswamy, G., & Kleindienst, J. (2000). Hierarchical feature-based translation for scalable natural language understanding. In Proceedings of 6th International Conference on Spoken Language Processing. [find](https://scholar.google.com/scholar?q=Ramaswamy%2C+G%2E%2C+%26+Kleindienst%2C+J%2E+%282000%29%2E+Hierarchical+feature%2Dbased+translation+for+scalable+natural+language+understanding%2E+In+Proceedings+of+6th+International+Conference+on+Spoken+Language+Processin)
15. Ratnaparkhi, A., Roukos, S., & Ward, R. T. (1994). A maximum entropy model for parsing. In Proceedings of the International Conference on Spoken Language Processing. [find](https://scholar.google.com/scholar?q=Ratnaparkhi%2C+A%2E%2C+Roukos%2C+S%2E%2C+%26+Ward%2C+R%2E+T%2E+%281994%29%2E+A+maximum+entropy+model+for+parsing%2E+In+Proceedings+of+the+International+Conference+on+Spoken+Language+Processing%2E)
16. Steedman, M. (1996). Surface Structure and Interpretation. The MIT Press. [find](https://scholar.google.com/scholar?q=Steedman%2C+M%2E+%281996%29%2E+Surface+Structure+and+Interpretation%2E+The+MIT+Press%2E)
17. Steedman, M. (2000). The Syntactic Process. The MIT Press. [find](https://scholar.google.com/scholar?q=Steedman%2C+M%2E+%282000%29%2E+The+Syntactic+Process%2E+The+MIT+Press%2E)
18. Tang, L. R., & Mooney, R. J. (2001). Using multiple clause constructors in inductive logic programming for semantic parsing. In Proceedings of the 12th European Conference on Machine Learning, pp. 466–477. [find](https://scholar.google.com/scholar?q=Tang%2C+L%2E+R%2E%2C+%26+Mooney%2C+R%2E+J%2E+%282001%29%2E+Using+multiple+clause+constructors+in+inductive+logic+programming+for+semantic+parsing%2E+In+Proceedings+of+the+12th+European+Conference+on+Machine+Learning%2C+pp%2E+466)
19. Taskar, B., Guestrin, C., & Koller, D. (2003). Max-margin markov networks. In Neural Information Processing Systems. [find](https://scholar.google.com/scholar?q=Taskar%2C+B%2E%2C+Guestrin%2C+C%2E%2C+%26+Koller%2C+D%2E+%282003%29%2E+Max%2Dmargin+markov+networks%2E+In+Neural+Information+Processing+Systems%2E)
20. Taskar, B., Klein, D., Collins, M., Koller, D., & Manning, C. (2004). Max-margin parsing. In Proceedings of the SIGDAT Conference on Empirical Methods in Natural Language Processing. [find](https://scholar.google.com/scholar?q=Taskar%2C+B%2E%2C+Klein%2C+D%2E%2C+Collins%2C+M%2E%2C+Koller%2C+D%2E%2C+%26+Manning%2C+C%2E+%282004%29%2E+Max%2Dmargin+parsing%2E+In+Proceedings+of+the+SIGDAT+Conference+on+Empirical+Methods+in+Natural+Language+Processing%2E)
21. Thompson, C. A., & Mooney, R. J. (2002). Acquiring word-meaning mappings for natural language interfaces. Journal of Artificial Intelligence Research, 18. [find](https://scholar.google.com/scholar?q=Thompson%2C+C%2E+A%2E%2C+%26+Mooney%2C+R%2E+J%2E+%282002%29%2E+Acquiring+word%2Dmeaning+mappings+for+natural+language+interfaces%2E+Journal+of+Artificial+Intelligence+Research%2C+18%2E)
22. Watkinson, S., & Manandhar, S. (1999). Unsupervised lexical learning with categorial grammars using the LLL corpus. In Proceedings of the 1st Workshop on Learning Language in Logic, pp. 16–27. [find](https://scholar.google.com/scholar?q=Watkinson%2C+S%2E%2C+%26+Manandhar%2C+S%2E+%281999%29%2E+Unsupervised+lexical+learning+with+categorial+grammars+using+the+LLL+corpus%2E+In+Proceedings+of+the+1st+Workshop+on+Learning+Language+in+Logic%2C+pp%2E+16%E2%80%9327%2E)
23. Zelle, J. M., & Mooney, R. J. (1996). Learning to parse database queries using inductive logic programming. In Proceedings of the 14th National Conference on Artificial Intelligence. [our card](https://md.research.elamur.ai/free/en/papers/zelle-1996-learning-parse-database-queries-using/)