Approximate Theory Formation: An Explanation-Based Approach

Thomas EllmanAAAI 1988

Abstract

This paper introduces POLLYANNA, a system designed to address the computational intractability of Explanation-Based Learning (EBL) in complex domains. By intentionally sacrificing theory accuracy for speed, POLLYANNA explores a lattice of simplifying assumptions guided by teacher-provided examples. The system performs abductive inference to identify approximate theories that balance tractability and performance. Experimental results in the domain of Hearts demonstrate the system's ability to discover Pareto-optimal theories that significantly reduce computational overhead while maintaining acceptable error rates.

1. Introduction

In the late 1980s, Explanation-Based Learning (EBL) faced a significant challenge: the requirement for a tractable domain theory. In domains like Chess or complex circuit design, the underlying rules are so computationally expensive to evaluate that standard EBL cannot construct explanations. While Similarity-Based Learning (SBL) can operate in these environments by identifying patterns in data, it ignores the rich background knowledge available in the domain's rules.

Thomas Ellman proposed a middle ground: approximate theory formation. By deliberately simplifying domain rules—making them technically "wrong" but computationally "cheap"—a system can use examples to find which simplifications are effective in practice. This approach treats learning as substantive theory revision rather than mere knowledge compilation.

2. The POLLYANNA System

The POLLYANNA system employs a three-stage methodology to navigate the tradeoff between accuracy and tractability:

  1. Assumption Generation: The system utilizes a predefined typology of simplifying assumptions, such as assuming a function is invariant or that random variables are independent.
  2. Theory Space Generation: These assumptions are integrated into the domain theory using polymorphic generic functions. This creates a lattice-structured search space of approximate theories, ordered from simplest to most complex.
  3. Theory Space Search: POLLYANNA conducts an "optimistic" search, starting with the simplest theory at the root of the lattice. It moves to more complex versions only when training examples contradict the simpler ones, effectively performing abductive inference to find the best-fitting assumptions.

3. Experimental Evaluation: The Hearts Domain

The system was evaluated using the card game Hearts, a domain characterized by computational intractability. Calculating a perfect move requires averaging over all possible card deals and performing a massive mini-max search. POLLYANNA was trained on sets of teacher-provided examples designed to reflect specific strategies, such as "lead with cards of minimal rank" or "lead with cards of minimal point value."

4. Results and the Accuracy-Tractability Tradeoff

The primary result of the evaluation is the identification of a Pareto frontier representing the optimal balance between error rate and computational cost.

Tradeoff between error rate and running time in the Hearts domain.

As shown in the figure above, the system measured the "false good" error rate (the probability that a card chosen by the approximate theory is incorrect) against the number of function calls required. The search successfully identified a set of "Pareto optimal" theories (circled points). For instance, one discovered theory ignored the odds of winning a trick but focused heavily on expected point values, resulting in a theory that was significantly faster than the "exact" version while maintaining acceptable performance.

Furthermore, POLLYANNA demonstrated flexibility by adopting different, even inconsistent, sets of assumptions based on the training context. This suggests that "truth" in complex domains is often relative to the specific goals of the agent.

5. Conclusion and Future Work

POLLYANNA provides a robust framework for trading accuracy for tractability in EBL. However, several limitations remain. Currently, the primitive refinement relations must be manually coded. Future work should focus on automating this process and developing more sophisticated search heuristics to manage the combinatorial explosion of the theory lattice as the number of generic functions grows. Additionally, further research is needed to determine how well the current typology of assumptions generalizes to non-game domains like scheduling or engineering design.

Summary updated

BibTeX
@inproceedings{ellman1988approximate,
  author = {Thomas Ellman},
  title = {{Approximate Theory Formation: An Explanation-Based Approach}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1988},
}
Figure