Introduction
In the early 1990s, Natural Language Processing (NLP) faced a significant "knowledge acquisition bottleneck." While syntactic parsing (identifying nouns and verbs) was maturing, semantic parsing—mapping sentences to their underlying meaning—remained a manual, labor-intensive task. Researchers at the University of Texas at Austin addressed this by developing CHILL (Constructive Heuristics Induction for Language Learning), a system that uses Inductive Logic Programming (ILP) to automatically learn semantic grammars from examples.
The CHILL System: Parsing as Logic Programming
CHILL treats grammar acquisition as a search-control problem. Instead of hand-coding rules for every possible sentence structure, the system starts with a general, "dumb" shift-reduce parser written in Prolog. This parser knows the basic mechanics of moving words onto a stack and combining them but lacks the intelligence to know when to apply specific actions.
As shown in the trace above, the parser processes a sentence like "the man ate the pasta" by shifting words onto a stack and applying reduction rules (like det for determiners or agt for agents) to build a case-role structure. To prevent the parser from making incorrect "spurious" moves, CHILL uses ILP to induce control rules. These rules act as guards, ensuring that a reduction only occurs if the items on the stack satisfy specific semantic constraints.
Predicate Invention and Constructive Induction
A core innovation of CHILL is its ability to perform Predicate Invention. When the system encounters a semantic ambiguity—such as distinguishing between an animate "agent" (a boy) and an inanimate "instrument" (a hammer)—it doesn't require a pre-defined ontology. Instead, it "invents" its own internal categories. By observing how different words behave across hundreds of training examples, CHILL automatically groups words into functional classes like animate, human, or food. This "constructive induction" allows the system to build a domain-specific vocabulary tailored to the task at hand.
Experimental Results
The researchers evaluated CHILL against two primary datasets: the M & K Corpus (a standard baseline) and a more complex Tourist Domain.
In the M & K Corpus, CHILL achieved 98% accuracy after 650 training sentences, significantly outperforming the connectionist (neural) models of the era, which plateaued around 78%. The system's performance was even more striking in the Tourist Domain, a dataset capable of generating over 150,000 distinct sentences.
As illustrated in the learning curve, CHILL reached 99% accuracy with only 300 training examples in the Tourist Domain. Beyond accuracy, the system demonstrated remarkable efficiency; while neural networks of the time required days of training, CHILL converged in minutes on standard hardware.
Conclusion
CHILL demonstrated that symbolic learning techniques like ILP could effectively bridge the gap between raw text and semantic meaning. By framing parsing as a search-control problem and leveraging predicate invention, the system provided a more accurate, interpretable, and computationally efficient alternative to the "black box" neural models of its time. While future work would need to address noisier, real-world data, CHILL proved that semantic grammars could be learned, not just built.
Summary updated