Elamur Research⌕
☰
home / papers / 2006 / Using String-Kernels for Learning Semantic Parsers

Using String-Kernels for Learning Semantic Parsers

Paper · 2006 · Rohit J. Kate and Raymond J. Mooney

Summary

The paper addresses semantic parsing: converting natural-language sentences into formal, executable meaning representations (MRs). The authors argue that rule-based and feature-based learners struggle because they must explicitly list the many ways a concept can be phrased. Their system, KRISP, treats each production of the meaning representation language (MRL) grammar as a semantic concept. For each production, it trains an SVM whose kernel is a string-subsequence similarity, and the classifier estimates how likely that production is to cover a given span of the sentence. Parsing then searches for the most probable "semantic derivation": an MR parse tree whose nodes are tied to non-overlapping sentence substrings, with child order allowed to permute. The search uses an extended Earley algorithm. KRISP was evaluated with 10-fold cross validation on CLANG (RoboCup coaching advice) and GEOQUERY (US geography queries). It beat the rule-based parsers CHILL and SILT, matched the statistical parsers WASP and SCISSOR, and handled simulated speech-recognition noise especially well. The approach uses no language-specific knowledge, so it carries over directly to other languages.

Key points

  • Corpora:
    • CLANG has 300 coaching instructions from the 2003 RoboCup Coach Competition, manually translated into English. Sentences average 22.52 words and MRs average 13.42 tokens.
    • GEOQUERY has 880 English queries. Sentences average 7.48 words and MRs average 6.46 tokens.
  • Settings: threshold θ = 0.05, beam size ω = 20, and only 3 training iterations (MAX ITR). More iterations led to overfitting.
  • Baselines: SILT (string and tree versions), WASP, SCISSOR, CHILL, and the CCG parser of Zettlemoyer et al. (2005), which was reported only on GEO880.
    • SCISSOR reaches higher maximum recall on CLANG, but it needs semantically annotated syntactic trees.
    • CHILL ran out of memory beyond 160 examples. At that size it reached 49.2% precision and 12.67% recall.
  • Other languages: on the GEO250 subset, KRISP performed competently in Spanish, Turkish and Japanese as well as English.
  • Constants: productions for constants such as stateid('texas') are not learned. They are matched against substrings supplied by the user.

Interesting ideas

  • I1. One classifier per grammar production. Training a separate classifier for every production of the target formal language breaks structured prediction into many small "does this span express concept X?" decisions. This could transfer to any text-to-structure task that has a known output grammar, such as SQL or API calls.
  • I2. Kernels instead of hand-built features. A string-subsequence kernel implicitly compares all gappy word subsequences, so no one has to enumerate phrasing variants. This is attractive for morphologically rich or freely ordered languages like Ukrainian.
  • I3. Permutable children in derivations. Allowing children of an MR node to align to sentence spans in any order decouples surface word order from the formal structure. This is a cheap way to handle languages with flexible word order.
  • I4. Realistic noise injection. The authors corrupt test sentences in three ways that mimic ASR errors: - inserting words sampled by BNC frequency, - randomly dropping words, - swapping words for frequent phonetically similar ones. This recipe is a reusable robustness test for any NLU system that consumes speech or user input.
  • I5. Precision-recall curves from confidence scores. Evaluating at varying confidence thresholds, rather than at a single operating point, shows how a parser trades coverage for accuracy. This is useful when deployment needs to reject uncertain parses.

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

🎓The University of Texas at AustinAustin · United States72 works · 55,722 citations

📚 Shelves 4 Computer Science · 9,086 works Artificial Intelligence · 8,889 works Arts and Humanities · 9,296 works Language and Linguistics · 9,206 works

🧭 Topics 1 Semantic parsing & meaning representation · 135 works

Cite

Cite as Rohit J. Kate and Raymond J. Mooney. 2006. Using String-Kernels for Learning Semantic Parsers. Proceedings of the 21st International Conference on Computational Linguistics and 44th Annual Meeting of the Association for Computational Linguistics.

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

@inproceedings{kate2006using,
  title = {{Using String-Kernels for Learning Semantic Parsers}},
  author = {Rohit J. Kate and Raymond J. Mooney},
  booktitle = {Proceedings of the 21st International Conference on Computational Linguistics and 44th Annual Meeting of the Association for Computational Linguistics},
  year = {2006},
  doi = {10.3115/1220175.1220290},
  url = {https://doi.org/10.3115/1220175.1220290}
}

References

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

  1. Mao Chen et al. 2003. Users manual: RoboCup soccer server manual for soccer server version 7.07 and later. Available at http://sourceforge.net/projects/sserver/. ↗
  2. Nello Cristianini and John Shawe-Taylor. 2000. An Introduction to Support Vector Machines and Other Kernel-based Learning Methods. Cambridge University Press. find
  3. Jay Earley. 1970. An efficient context-free parsing algorithm. Communications of the Association for Computing Machinery, 6(8):451–455. find
  4. R. Ge and R. J. Mooney. 2005. A statistical semantic parser that integrates syntax and semantics. In Proc. of 9th Conf. on Computational Natural Language Learning (CoNLL-2005), pages 9–16, Ann Arbor, MI, July. find
  5. R. J. Kate, Y. W. Wong, and R. J. Mooney. 2005. Learning to transform natural to formal languages. In Proc. of 20th Natl. Conf. on Artificial Intelligence (AAAI-2005), pages 1062–1068, Pittsburgh, PA, July. find
  6. Rohit J. Kate. 2005. A kernel-based approach to learning semantic parsers. Technical Report UT-AI-05-326, Artificial Intelligence Lab, University of Texas at Austin, Austin, TX, November. find
  7. V. I. Levenshtein. 1966. Binary codes capable of correcting insertions and reversals. Soviet Physics Doklady, 10(8):707–710, February. find
  8. Huma Lodhi, Craig Saunders, John Shawe-Taylor, Nello Cristianini, and Chris Watkins. 2002. Text classification using string kernels. Journal of Machine Learning Research, 2:419–444. find
  9. Scott Miller, David Stallard, Robert Bobrow, and Richard Schwartz. 1996. A fully statistical approach to natural language interfaces. In Proc. of the 34th Annual Meeting of the Association for Computational Linguistics (ACL-96), pages 55–61, Santa Cruz, CA. find
  10. John C. Platt. 1999. Probabilistic outputs for support vector machines and comparisons to regularized likelihood methods. In Alexander J. Smola, Peter Bartlett, Bernhard Schölkopf, and Dale Schuurmans, editors, Advances in Large Margin Classifiers, pages 185–208. MIT Press. find
  11. 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 Proc. of 20th Intl. Conf. on Computational Linguistics (COLING-04), Geneva, Switzerland, August. find
  12. Patti J. Price. 1990. Evaluation of spoken language systems: The ATIS domain. In Proc. of 3rd DARPA Speech and Natural Language Workshop, pages 91–95, June. find
  13. Andreas Stolcke. 1995. An efficient probabilistic context-free parsing algorithm that computes prefix probabilities. Computational Linguistics, 21(2):165–201. our card
  14. L. R. Tang and R. J. Mooney. 2001. Using multiple clause constructors in inductive logic programming for semantic parsing. In Proc. of the 12th European Conf. on Machine Learning, pages 466–477, Freiburg, Germany. find
  15. Yuk Wah Wong and Raymond J. Mooney. 2006. Learning for semantic parsing with statistical machine translation. In Proc. of Human Language Technology Conf. / North American Association for Computational Linguistics Annual Meeting (HLT/NAACL-2006), New York City, NY. To appear. our card
  16. John M. Zelle and Raymond J. Mooney. 1996. Learning to parse database queries using inductive logic programming. In Proc. of 13th Natl. Conf. on Artificial Intelligence (AAAI-96), pages 1050–1055, Portland, OR, August. our card
  17. Luke S. Zettlemoyer and Michael Collins. 2005. Learning to map sentences to logical form: Structured classification with probabilistic categorial grammars. In Proc. of 21th Conf. on Uncertainty in Artificial Intelligence (UAI-2005), Edinburgh, Scotland, July. our card
  18. Victor W. Zue and James R. Glass. 2000. Conversational interfaces: Advances and challenges. In Proc. of the IEEE, volume 88(8), pages 1166–1180. find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/kate-2006-string-kernels-learning-semantic-parsers/