Abstract
In the mid-1990s, a significant gap existed between the experimental success of "speedup learning" systems and the rigorous mathematical foundations of computational learning theory. This paper by Prasad Tadepalli and Balas K. Natarajan bridges that gap by extending the Probably Approximately Correct (PAC) learning framework to the domain of problem-solving. By formalizing how a learner can acquire control knowledge from a teacher, the authors provide the first theoretical guarantees that AI systems can learn to solve NP-hard problems in polynomial time, provided the domains exhibit specific structural properties like serial decomposability.
Introduction
Historically, machine learning research was bifurcated. One branch focused on concept learning—classifying data points with mathematical rigor using PAC-learning theory. The other branch, speedup learning, focused on improving the efficiency of solvers (e.g., SOAR, PRODIGY) through experience in domains like symbolic integration or puzzle-solving. While these systems showed impressive empirical results, they lacked a formal guarantee of convergence or efficiency.
The central challenge in speedup learning is the inherent complexity of the search space. Many interesting domains are NP-hard; without guidance, a computer might spend exponential time searching for a solution. Tadepalli and Natarajan address this by asking: Can we prove that a learner can acquire "control knowledge" to transform an exponential search into a polynomial-time execution?
Formalizing the Learner-Teacher Framework
The authors redefine the PAC-learning task. Instead of learning to classify an input, the learner aims to output a program (a "solver") that maps a problem instance to a valid sequence of operators. The framework relies on a "target-consistent" teacher who provides example solutions. The learner's goal is to find a solver that is approximately as efficient and accurate as the teacher's strategy.
Knowledge Representations
The paper explores two primary methods for representing and learning speedup knowledge:
- Control Rules: These rules guide the solver by suggesting which operator to apply in a specific state. The authors utilize a Most Specific Generalization (MSG) algorithm. By analyzing the teacher's steps and identifying the most specific grammar that describes those states, the learner constructs rules that prune useless search paths.
- Macro-operators: These are sequences of moves treated as a single unit to achieve a specific subgoal. The authors introduce the Serial-parser algorithm, which decomposes a teacher's solution into a "macro table," allowing the solver to jump through state spaces efficiently.
The Role of Serial Decomposability
A critical contribution of this work is the formalization of Serial Decomposability. This property describes domains where a problem can be solved by achieving a sequence of subgoals such that once a subgoal is reached, it never needs to be violated to solve subsequent subgoals. A classic example is the Eight Puzzle or a Rubik's Cube, where specific tiles or rows can be placed in order. The authors prove that if a domain is serially decomposable and possesses a finite set of features, the Serial-parser is guaranteed to learn an approximately correct solver in polynomial time using a polynomial number of examples.
Empirical Validation
The theoretical framework was tested on two classic AI benchmarks to demonstrate its practical utility:
- Symbolic Integration (SIMPLEX): In a domain with 39 operators (e.g., integration by parts, power rule), the system reached 99% accuracy—matching the teacher's solution path—after observing only 30 training examples.
- The Eight Puzzle: Using the macro-learning approach, the program achieved approximately 98.7% accuracy within 40 training examples.
These results confirmed that the learner does not need to find the optimal (shortest) solution to be effective; it simply needs to be consistent with the teacher's style to achieve dramatic speedups.
Addressing the Utility Problem
A recurring issue in early AI was the "utility problem," where a system would learn so many rules that the overhead of searching through those rules actually slowed the solver down. Tadepalli and Natarajan’s framework offers a mathematical solution: by constraining the type of rules learned (specifically MSG rules) and ensuring they are derived from a consistent teacher, the system can guarantee that the resulting solver remains computationally efficient.
Conclusion and Future Directions
This paper provided the necessary theoretical scaffolding for speedup learning, moving it from an experimental heuristic to a provable science. However, the authors noted several limitations that paved the way for future research:
- Unsupervised Learning: Without a teacher to provide a consistent "style," the learner faces the difficult task of choosing which of many valid solutions to generalize from.
- Relational Predicates: While the framework works for feature vectors, moving to first-order logic (required for complex planning like "Blocks World") introduces significant complexity that may be NP-hard to generalize.
- Solution Quality: The current framework prioritizes finding a solution quickly over finding the shortest possible solution, suggesting a future trade-off analysis between speed and optimality.
Summary updated