Using String-Kernels for Learning Semantic Parsers

Rohit J. Kate, Raymond J. MooneyACL 2006 · DOI

Abstract

KRISP (Kernel-based Robust Interpretation for Semantic Parsing) is a novel system that maps natural language sentences to formal meaning representations by training Support Vector Machine (SVM) classifiers for every production in a formal grammar. By utilizing string subsequence kernels, the system moves away from rigid rule-matching, resulting in a semantic parser that is exceptionally robust to noise and performs competitively across multiple languages.

Introduction

Semantic parsing—the task of transforming natural language (NL) into a computer-executable format—is inherently difficult due to the flexibility of human language. Traditional rule-based systems often struggle with the nearly infinite ways to express the same concept and are sensitive to "noisy" data, such as disfluencies in speech or errors from speech recognition software. KRISP addresses these challenges by learning mappings implicitly through string similarity rather than strict pattern matching.

Methodology

KRISP treats the productions of a formal Meaning Representation Language (MRL) grammar as semantic concepts. The core components of the system include:

  1. String-Kernel Classifiers: For every production in the grammar, KRISP trains an SVM classifier using a normalized string subsequence kernel. This kernel measures similarity based on common word subsequences, allowing the model to recognize concepts despite wording variations or noise.
  2. Iterative Training: The system refines its classifiers over several rounds. It initially assumes that if a sentence is paired with a specific meaning representation, all grammar productions used in that representation are present. It then iteratively identifies which substrings correspond to specific productions.
  3. Extended Earley Parsing: To generate a final meaning representation, KRISP uses a modified Earley’s algorithm to search for the most probable "semantic derivation"—a tree structure where nodes represent grammar productions covering specific sentence segments.
A semantic derivation tree mapping a natural language query to its formal grammar productions.

Experimental Evaluation

The system was evaluated on two primary benchmarks: CLANG (300 robotic soccer instructions) and GEOQUERY (880 U.S. geography queries). Additionally, a multilingual subset (GEO250) was used to test performance across Spanish, Turkish, and Japanese.

Key Results

KRISP demonstrated competitive accuracy compared to contemporary state-of-the-art systems like WASP and SCISSOR. A defining characteristic of KRISP is its superior noise tolerance; when artificial noise was added to the CLANG dataset, KRISP’s performance degraded much more gracefully than its competitors. At high noise levels, KRISP maintained significantly higher F-measures than other statistical parsers.

Performance comparison of KRISP against other state-of-the-art semantic parsers on the Geoquery dataset.

Discussion and Conclusion

By using string kernels, KRISP avoids manual feature engineering and handles the "feature explosion" problem by working in a high-dimensional space of word subsequences. The use of a formal grammar ensures that the output is always syntactically valid. While computationally intensive due to training multiple SVMs, KRISP provides a flexible bridge between ambiguous human language and rigid computer code. Future work may address overfitting issues and the high supervision requirements of parallel corpora.

Summary updated

BibTeX
@inproceedings{kate2006using,
  author = {Rohit J. Kate and Raymond J. Mooney},
  title = {{Using String-Kernels for Learning Semantic Parsers}},
  booktitle = {Annual Meeting of the Association for Computational Linguistics},
  year = {2006},
  doi = {10.3115/1220175.1220290},
}
Figure