A Comparison of Analytic and Experimental Goal Regression for Machine Learning

Bruce W. Porter, Dennis F. KiblerIJCAI 1985

Introduction

In the mid-1980s, Bruce W. Porter and Dennis F. Kibler published a seminal critique of problem-solving methodologies in artificial intelligence. Their work contrasts two primary approaches to "goal regression"—the process of reasoning backward from a desired state to identify necessary preconditions. While the prevailing "Analytic Goal Regression" relied on formal logic, Porter and Kibler proposed "Experimental Goal Regression," a more flexible, data-driven alternative that leverages inductive learning.

The Problem: The Analytic Bottleneck

Goal regression is fundamental to AI search and planning. Given a goal state ($G$) and an action or operator ($OP$), the system must determine the prior state ($S$) required for the action to succeed. Traditional analytic methods, rooted in Dijkstra’s "weakest pre-condition," faced three significant hurdles:

  1. Invertible Operators: Analytic regression requires operators to be mathematically reversible. This is often impossible for complex procedural code.
  2. Language Closure: The logical results of regression (e.g., complex nested conditionals) often exceed the descriptive power of the system's language.
  3. Pragmatism: Analytic methods identify what is possible (necessary conditions) but fail to identify what is effective (pragmatic conditions).

Experimental Goal Regression: An Inductive Alternative

To overcome these limitations, the authors introduced Experimental Goal Regression. Instead of symbolic inversion, this method treats operators as "black boxes" and employs:

  • Inductive Learning: The system observes multiple instances where an operator successfully leads to a goal and generalizes a rule.
  • Perturbation: To maximize data from limited examples, the system "perturbs" or slightly modifies a successful state to test if the operator remains effective, creating a neighborhood of training data.

Evaluation Domains

The authors validated their theory across three classic AI domains: Symbolic Integration, Gomoku (Five-in-a-row), and Simultaneous Linear Equations.

Figure 1: A symbolic integration operator demonstrating the transformation of a complex integral into a simpler form via substitution.

In the symbolic integration domain, for instance, the system uses the LEX system to solve calculus problems by identifying which substitutions actually simplify the expression rather than just being mathematically valid.

Key Insights: Pragmatism over Logic

The core contribution of the paper lies in the distinction between "required" and "pragmatic" preconditions. In the linear equations domain, an analytic rule might correctly state that one equation can be subtracted from another if their coefficients match. However, the experimental approach learns that one should only do so if it actually simplifies the problem (e.g., by eliminating a term).

While analytic regression is essentially "no-shot" learning—attempting to derive rules without experience—experimental regression is "few-shot," using a small set of trials to build robust, practical heuristics.

Conclusion

Porter and Kibler concluded that while experimental goal regression is more versatile, it relies heavily on the efficiency of example generation via perturbation. They suggested a hybrid future: using analytic regression to provide a logical "seed" and experimental induction to refine it into a high-performance heuristic. This work remains a cornerstone in the evolution from purely symbolic AI to inductive machine learning.

Summary updated

BibTeX
@inproceedings{porter1985comparison,
  author = {Bruce W. Porter and Dennis F. Kibler},
  title = {{A Comparison of Analytic and Experimental Goal Regression for Machine Learning}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1985},
}
Figure