Learning to Parse Database Queries Using Inductive Logic Programming

AAAI 1996

TL;DR

This paper introduces CHILL, a system that uses Inductive Logic Programming (ILP) to automatically learn parsers for translating natural language queries into executable database queries. Unlike previous work focusing on syntactic parsing, CHILL directly learns to map sentences to logical forms, demonstrating strong performance on a real-world geography database task and outperforming a hand-crafted system.

What Problem Does This Paper Address?

Building natural language interfaces (NLIs) for databases is a long-standing challenge in NLP. Traditional approaches often rely on extensive hand-crafted rules and linguistic expertise, which can be time-consuming and difficult to scale. While corpus-based methods have shown promise for syntactic parsing, their application to the more complex task of semantic parsing – directly mapping language to executable queries – has been less explored. This paper addresses the gap of automatically learning robust semantic parsers from data, specifically for database query tasks, aiming to reduce the reliance on manual rule creation and improve system performance.

Methods

The core of the paper is the CHILL system, which leverages Inductive Logic Programming (ILP) for parser acquisition. CHILL treats parser learning as learning "control rules" for a shift-reduce parser, represented as a Prolog program. The process involves:

  1. Parser Operator Generation: An overly-general shift-reduce parser is initially formulated based on the training examples. This involves identifying "operators" (e.g., "introduce," "co-reference," "conjoin") that correspond to building logical query structures.
  2. Example Analysis: The training examples (sentence-query pairs) are parsed using the overly-general parser. This step extracts contexts in which specific parsing operators should or should not be used.
  3. Control-Rule Induction: An ILP algorithm learns rules to classify these contexts, effectively teaching the parser when to apply each operator.
  4. Program Specialization: The learned control rules are integrated back into the parser to create a specialized, efficient parser.

A key innovation is adapting CHILL to handle structured logical forms (like those used in database queries) rather than just syntactic parse trees. This required defining new operators for constructing these logical structures.

Datasets

  • Training and Testing Data: A corpus of 250 sentences was collected from 50 subjects. This corpus was split into 225 training examples and 25 held-out test examples.
  • Database: The "Geobase" database, containing approximately 800 Prolog facts about U.S. geography (population, area, capitals, rivers, etc.), was used. This database was part of a commercial Prolog distribution.
  • Benchmark: The Geobase system, a pre-existing semantics-based parser for the same database, served as a benchmark for comparison.

Key Insights and Ideas

  • Direct Semantic Parsing: CHILL demonstrates that it's possible to learn parsers that directly map natural language sentences to executable database queries without an intermediate syntactic parsing step. This is a significant simplification and potential efficiency gain.
  • ILP for Relational Control: The use of Inductive Logic Programming is crucial for learning complex, relational control knowledge that governs the parser's actions. This allows for learning from structured data and producing symbolic, interpretable rules.
  • Empirical Approach for Full Applications: The success of CHILL on a complete, real-world database query application validates the empirical, corpus-based approach at a level beyond just syntactic analysis. It shows that learned parsers can be practically useful.
  • Corpus Annotation Simplicity: The paper highlights that annotating corpora with final logical representations (like database queries) is significantly easier than providing detailed linguistic annotations (like parse trees). This makes corpus creation more feasible.

Key Results

  • Performance Improvement: CHILL's learned parsers outperformed the existing Geobase system, especially when trained on more data.
  • Accuracy: In the best trial, CHILL's induced parser achieved 84% accuracy in answering novel queries.
  • Spurious Parses: CHILL produced a low rate of spurious parses (3.2% at 175 training examples, dropping to 2.3% at 200 examples), comparable to or better than the Geobase system (3.8%).
  • Efficiency: CHILL learned a parser comprising 1100 lines of Prolog code.

Limitations and Future Work

  • Corpus Size: While CHILL outperformed Geobase, the corpus size (250 sentences) is relatively small. The authors suggest that performance could be further improved by "corpus manufacturing" – generating more regular training data.
  • Lexicon Dependency: The current operator generation relies on a hand-built lexicon. Future work could involve automating lexicon acquisition, potentially using corpus-based methods for lexical mapping rules.
  • Domain Specificity: While the parsing framework is general, the Geoquery language and database are domain-specific. Extending CHILL to other domains and larger, more complex databases is a natural next step.
  • Broader Applicability: The authors envision CHILL's potential for automating the construction of semantic parsers for various NLP tasks, reducing the need for manual linguistic expertise.

Summary updated

BibTeX
@inproceedings{1996learning,
  title = {{Learning to Parse Database Queries Using Inductive Logic Programming}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1996},
}
Figure