Introduction
In the early 1990s, Natural Language Processing (NLP) began a significant transition toward corpus-based methodologies. While statistical models like stochastic context-free grammars gained prominence, they often lacked the structured, symbolic logic preferred for complex downstream reasoning and required vast datasets. This paper introduces CHILL (Constructive Heuristics Induction for Language Learning), a system designed to bridge this gap by automatically inducing deterministic, shift-reduce Prolog parsers from treebanks using Inductive Logic Programming (ILP).
The core challenge addressed is parser acquisition: the automated generation of efficient, symbolic parsers from annotated corpora without manual grammar engineering. CHILL produces symbolic rules capable of "inventing" syntactic and semantic categories to resolve ambiguities, offering a powerful alternative to purely probabilistic approaches.
Methodology: The CHILL Framework
CHILL operates through a two-stage process to transform a treebank into a functional parser:
- Initial Parser Formulation: The system starts with a general shift-reduce parser framework implemented in Prolog. This base parser understands fundamental operations—shifting words onto a stack or reducing stack elements into phrases—but lacks the logic to decide when to apply them, initially resulting in numerous incorrect analyses.
- Specialization via Inductive Logic Programming: To refine the parser, CHILL employs ILP to learn control heuristics. By analyzing training data, the system identifies which actions lead to correct parse trees (positive examples) versus dead ends (negative examples). It then uses a first-order induction algorithm to generate Horn-clause rules. These rules act as constraints, ensuring the parser only performs actions when the current stack and input buffer match specific learned patterns.
A defining feature of CHILL is predicate invention. The system can autonomously create internal categories—such as classes for specific prepositions or verbs—to aid deterministic decision-making, even when such labels are absent from the input data.
Experimental Setup
Evaluation was conducted using the ATIS (Air Travel Information System) corpus from the Penn Treebank. The dataset consisted of 729 sentences with an average length of 10.3 words. For computational tractability, a restricted set of 536 sentences (length < 13 words) was also utilized.
The authors tested CHILL under two primary conditions:
- Lexically Tagged Text: Words were pre-labeled with parts of speech.
- Raw Text: The system processed text without prior tagging, relying on its internal category induction.
Because CHILL requires binary-branching structures, the original Penn Treebank trees were "binarized" into a right-linear format prior to training.
Results and Discussion
CHILL demonstrated strong performance even with relatively small training sets. On the restricted tagged corpus, accuracy scaled with the number of training examples.
As shown in the table above, with 300 training sentences, CHILL achieved a 33.1% exact match accuracy and a 79.1% partial accuracy. Its "0-crossing" score—measuring how often parser brackets conflict with ground truth—reached 63.6%, comparable to contemporary transformation-based learners that performed simpler tasks.
The system's ability to handle raw text further validated its predicate invention capabilities.
On raw text with 300 training sentences, CHILL maintained a 17.4% exact match and 69.6% partial accuracy. This suggests that symbolic machine learning can effectively induce functional categories (e.g., for words like "to" or "of") to resolve complex attachments without manual feature engineering.
Conclusion
CHILL represents a significant advancement in symbolic NLP, proving that ILP can induce efficient, deterministic parsers that compete with statistical models. By leveraging the entire stack and remaining input buffer, CHILL's rules provide a high degree of context awareness.
However, challenges remain regarding scalability and robustness. Performance tends to degrade on longer sentences due to error propagation and the increased complexity of the induction task. Future work aims to improve ILP efficiency and develop "self-correcting" mechanisms to handle states where no learned rules apply, further enhancing the system's utility for large-scale language processing.
Summary updated