Finding Accurate Frontiers: A Knowledge-Intensive Approach to Relational Learning

Michael J. Pazzani, Clifford BrunkAAAI 1993

Introduction

In the early 1990s, machine learning research was divided between empirical learning—finding patterns directly from data—and analytic learning—using pre-existing domain theories to explain data. While systems like FOCL attempted to bridge this gap, they often relied on "operationalization," the process of translating high-level concepts entirely into basic, observable facts. This paper introduces FOCL-FRONTIER, a system that avoids the pitfalls of full operationalization by searching for an "accurate frontier": an optimal level of abstraction that balances general rules with specific empirical evidence.

The Problem with Operationalization

Standard Explanation-Based Learning (EBL) requires domain theories to be fully reduced to base-level facts. This approach suffers from several weaknesses:

  1. Overspecialization: Rules become too specific to training examples.
  2. Replicated Induction: The system may learn the same correction multiple times across different branches.
  3. Fragility: A single error in a high-level rule can render the entire operationalized version useless, even if other parts of the theory are sound.

The Frontier Approach

The authors propose that the most effective explanation is not always the deepest one. Instead, they define a Frontier as a set of predicates that can include both high-level (non-operational) and low-level (operational) terms.

Figure 1: A domain theory tree where the bold line represents a 'frontier'—a mix of high-level and low-level nodes used for classification.

To find the best frontier, FOCL-FRONTIER employs a hill-climbing search guided by information gain. Starting from the most general concept, it applies four key transformation operators:

  • Clause Specialization: Replacing a term with its definition.
  • Removing/Adding Disjunctions: Pruning or expanding paths based on data fit.
  • Literal Deletion: A form of abduction that ignores parts of a rule contradicting the evidence.

Experimental Results

The system was evaluated across three domains: Chess end games, educational loan repayments, and the Nynex Max expert system for telephone malfunctions. A key finding was the system's robustness to errors in the initial domain theory. In the Chess domain, the researchers intentionally corrupted a perfect theory with random modifications to test how well the system could recover.

Figure 3: Accuracy vs. Number of Modifications. FOCL-FRONTIER maintains significantly higher accuracy than standard FOCL as the initial theory becomes noisier.

As shown in the results, FOCL-FRONTIER achieved 98.3% accuracy compared to standard FOCL’s 92.6% when using a noisy theory and limited training data (50 examples). The "knowledge-intensive" frontier approach acts as a powerful regularizer, especially when data is sparse. In the real-world Nynex Max test, FOCL-FRONTIER was the only algorithm to outperform the original expert system theory it was given.

Conclusion

FOCL-FRONTIER demonstrates that searching for an intermediate level of abstraction—a frontier—leads to more robust and efficient relational learning. While the current greedy hill-climbing search may occasionally miss global optima, the approach significantly improves upon standard operationalization techniques. Future work will explore more complex transformation operators to handle a wider variety of errors in human-provided knowledge.

Summary updated

BibTeX
@inproceedings{pazzani1993finding,
  author = {Michael J. Pazzani and Clifford Brunk},
  title = {{Finding Accurate Frontiers: A Knowledge-Intensive Approach to Relational Learning}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1993},
}
Figure