Elamur Research⌕
☰
home / papers / 2011 / Lexical Generalization in CCG Grammar Induction for Semantic Parsing

Lexical Generalization in CCG Grammar Induction for Semantic Parsing

Summary

CCG-based semantic parsers learn lexicons that map words to syntactic categories paired with lambda-calculus meanings. These lexicons are often redundant: words of the same class need several near-identical entries for different syntactic contexts. Such entries must each be learned separately from sparse data. The authors propose a factored lexicon that splits each entry into a lexeme (a word or phrase plus its logical constants) and a lexical template (a shared pattern that turns any lexeme into a full CCG item).

Their system, FUBL, extends the higher-order-unification induction of Kwiatkowski et al. (2010), the UBL approach. It proposes lexemes and templates rather than complete entries. Lexical induction is combined with online estimation of a log-linear parse-selection model, and derivations are treated as hidden variables.

Evaluated on Atis and GeoQuery (including Geo250 in several languages), FUBL reaches at or near state-of-the-art recall without English- or domain-specific rules. It clearly outperforms UBL on the unedited Atis sentences. This shows that factoring lexical knowledge improves generalization in language-independent grammar induction.

Key points

  • The factored lexicon (L, T) has two parts:
    • lexemes such as (Boston, [bos]);
    • templates such as one that yields NP : v₁ from a lexeme.
  • On Atis, FUBL's exact-match recall exceeds that of UBL by margins of 16 and 11 points across the two reported evaluations.
  • Comparison with ZC07 on Atis is mixed:
    • FUBL is 7.5% higher in recall on the development set;
    • it is about 2% lower on the test set.
  • On Geo250, FUBL gets the highest recall across all languages. However, its precision is notably lower than that of ZC07 and λ-WASP.
  • Novel lexical items (non-NP lexeme–template combinations unseen in training) appear in 6% of Atis development parses. Templates that add semantic content contribute only 1.2% of recall there.

Interesting ideas

  • I1. Separate content from usage pattern. Store what a word means (its constants) apart from how it combines syntactically (templates). Rare words can then borrow constructions learned from frequent words of the same type, which could help any sparse lexicalized model, such as low-resource Ukrainian grammars.
  • I2. Generate unseen entries at test time. Recombining known lexemes with known templates lets the parser handle a word in a construction it never appeared in during training. For example, "cheapest" in mid-sentence position was handled this way. This is a cheap form of compositional generalization.
  • I3. Model ellipsis through the lexicon, not the grammar. Lexemes carrying several constants, such as (to, [from, to]), let the parser cope with sloppy, unedited input without relaxing the combinators or writing language-specific rules.
  • I4. Expect a recall/precision trade-off. A very general lexicon parses more sentences but makes more wrong guesses. Reporting both metrics, rather than recall alone, exposes this cost of over-generalization.
  • I5. Transfer templates across domains. The authors suggest that templates could be reused in new domains, with only the domain-specific lexemes relearned. This is a plausible route to adapting a parser to new applications with little data.

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: Natural language processing

Cited by

95 papers of our library cite it (of the 140884 whose bibliographies we read); 3 of them have a page here, 92 not yet.

Cite

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

@inproceedings{kwiatkowski2011lexical,
  title = {{Lexical Generalization in CCG Grammar Induction for Semantic Parsing}},
  author = {Kwiatkowski, Tom and Zettlemoyer, Luke and Goldwater, Sharon and Steedman, Mark},
  booktitle = {Proceedings of the 2011 Conference on Empirical Methods in Natural Language Processing},
  year = {2011},
  url = {https://aclanthology.org/D11-1140/}
}

References

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

  1. Bos, Johan, 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
  2. Branavan, S.R.K., Luke Zettlemoyer, and Regina Barzilay. 2010. Reading between the lines: Learning to map high-level instructions to commands. In Association for Computational Linguistics (ACL). find
  3. Carpenter, Bob. 1997. Type-Logical Semantics. The MIT Press. find
  4. Clark, Stephen 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
  5. Clark, Stephen and James R. Curran. 2007. Wide-coverage efficient statistical parsing with CCG and log-linear models. Computational Linguistics 33(4):493–552. find our card
  6. Clarke, James, Dan Goldwasser, Ming-Wei Chang, and Dan Roth. 2010. Driving semantic parsing from the world’s response. In Proceedings of the Fourteenth Conference on Computational Natural Language Learning (CoNLL-2010). Uppsala, Sweden, pages 18–27. find
  7. Ge, Ruifang and Raymond J. Mooney. 2006. Discriminative reranking for semantic parsing. In Proceedings of the COLING/ACL 2006 Main Conference Poster Sessions. find
  8. Goldwasser, Dan, Roi Reichart, James Clarke, and Dan Roth. 2011. Confidence driven unsupervised semantic parsing. In Association for Computational Linguistics (ACL). find
  9. He, Yulan and Steve Young. 2005. Semantic processing using the hidden vector state model. Computer Speech and Language . find
  10. He, Yulan and Steve Young. 2006. Spoken language understanding using the hidden vector state model. Speech Communication 48(3-4). find
  11. Hockenmaier, Julia and Mark Steedman. 2002. Generative models for statistical parsing with Combinatory Categorial Grammar. In Proceedings of the 40th Meeting of the ACL. Philadelphia, PA, pages 335–342. find
  12. Kate, Rohit J. and Raymond J. Mooney. 2006. Using string-kernels for learning semantic parsers. In Proceedings of the 44th Annual Meeting of the Association for Computational Linguistics. find
  13. Kate, Rohit J., Yuk Wah Wong, and Raymond J. Mooney. 2005. Learning to transform natural to formal languages. In Proceedings of the National Conference on Artificial Intelligence. find
  14. Kwiatkowski, Tom, Luke Zettlemoyer, Sharon Goldwater, and Mark Steedman. 2010. Inducing probabilistic CCG grammars from logical form with higher-order unification. In Proceedings of the Conference on Emperical Methods in Natural Language Processing. find
  15. LeCun, Y., L. Bottou, Y. Bengio, and P. Haffner. 1998. Gradient-based learning applied to document recognition. Proceedings of the IEEE 86(11):2278–2324. find
  16. Liang, P., 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). find our card
  17. Liang, P., M. I. Jordan, and D. Klein. 2011. Learning dependency-based compositional semantics. In Association for Computational Linguistics (ACL). find
  18. Lu, Wei, Hwee Tou Ng, Wee Sun Lee, and Luke S. Zettlemoyer. 2008. A generative model for parsing natural language to meaning representations. In Proceedings of The Conference on Empirical Methods in Natural Language Processing. find
  19. Miller, Scott, 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
  20. Nguyen, Le-Minh, Akira Shimazu, and Xuan-Hieu Phan. 2006. Semantic parsing with structured SVM ensemble classification models. In Proceedings of the COL-ING/ACL 2006 Main Conference Poster Sessions. find
  21. Och, Franz Josef and Hermann Ney. 2003. A systematic comparison of various statistical alignment models. Computational Linguistics 29(1):19–51. find
  22. Papineni, K. A., S. Roukos, and T. R. Ward. 1997. Feature-based language understanding. In Proceedings of European Conference on Speech Communication and Technology. find
  23. Poon, Hoifung and Pedro Domingos. 2009. Unsupervised semantic parsing. In Conference on Empirical Methods in Natural Language Processing (EMNLP). find our card
  24. Poon, Hoifung and Pedro Domingos. 2010. Unsupervised ontology induction from text. In Association for Computational Linguistics (ACL). find
  25. Ramaswamy, Ganesh N. and Jan Kleindienst. 2000. Hierarchical feature-based translation for scalable natural language understanding. In Proceedings of International Conference on Spoken Language Processing. find
  26. Steedman, Mark. 1996. Surface Structure and Interpretation. The MIT Press. find
  27. Steedman, Mark. 2000. The Syntactic Process. The MIT Press. find
  28. Tang, Lappoon R. 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
  29. Thompson, Cynthia A. and Raymond J. Mooney. 2002. Acquiring word-meaning mappings for natural language interfaces. Journal of Artificial Intelligence Research 18. find
  30. Vogel, Adam and Dan Jurafsky. 2010. Learning to follow navigational directions. In Association for Computational Linguistics (ACL). find
  31. Watkinson, Stephen 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
  32. Wong, Yuk Wah and Raymond Mooney. 2006. Learning for semantic parsing with statistical machine translation. In Proceedings of the Human Language Technology Conference of the NAACL. find
  33. Wong, Yuk Wah and Raymond Mooney. 2007. Learning synchronous grammars for semantic parsing with lambda calculus. In Proceedings of the Association for Computational Linguistics. find our card
  34. Zelle, John M. and Raymond J. Mooney. 1996. Learning to parse database queries using inductive logic programming. In Proceedings of the National Conference on Artificial Intelligence. find
  35. Zettlemoyer, Luke S. 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. find
  36. Zettlemoyer, Luke S. 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
  37. Zettlemoyer, Luke S. and Michael Collins. 2009. Learning context-dependent mappings from sentences to logical form. In Proceedings of The Joint Conference of the Association for Computational Linguistics and International Joint Conference on Natural Language Processing. find

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/kwiatkowski-2011-lexical-generalization-ccg-grammar-induction/