Episodic Learning

Dennis F. Kibler, Bruce W. PorterAAAI 1983

Introduction

In the early 1980s, artificial intelligence research faced a significant hurdle known as the "macro-operator" problem. While systems could remember sequences of actions, they struggled to distinguish between useful strategies and "junk" sequences. For any given plan of $N$ steps, there are $N(N-1)/2$ possible sub-sequences that could be saved. Without a way to filter these, systems faced a combinatorial explosion that hindered rather than helped planning efficiency.

Kibler and Porter (1983) addressed this by distinguishing between Stage 1 learning (knowing when an operator can be applied) and Stage 2 learning (knowing why it should be applied). Their system, PET (implemented in Prolog), introduced a method to segment solution paths into discrete, reusable "episodes" that simplify problem states.

The PET System: Methods and Mechanisms

PET operates on three core pillars designed to minimize the need for explicit teacher guidance while maximizing the utility of learned rules.

1. Episodic Segmentation

Instead of indiscriminately saving every sequence, PET only forms an "episode" if a sequence meets specific criteria: it must either directly simplify the problem state (e.g., reducing the number of terms in an equation) or satisfy the preconditions for a rule that eventually leads to such a simplification. This "loose packaging" allows for branching within episodes, making them more flexible than rigid macro-operators.

2. Primitive Operators

To solve problems in the domain of simultaneous linear equations, PET utilizes a set of primitive operators. These operators define the basic transformations the system can perform on an algebraic state.

Table of primitive operators and their semantics used by the PET system.

3. Perturbation and Augmentation

To generalize from a single example, PET uses perturbation. It "pokes" the problem by modifying coefficients—zeroing them out or changing their values—to see if an operator still applies. This allows the system to discover the boundaries of a rule's applicability automatically.

When a teacher's action introduces a constant not found in the original input, PET triggers augmentation. It recognizes that the rule is not "predictive" and searches a second-order space of mathematical concepts to find the hidden relationship explaining the constant.

Predicates used during the augmentation process to discover hidden mathematical relationships.

Key Insights and Results

PET's approach to "understanding" an action is dual-natured: it looks for immediate gratification (simplification) or long-term enablement (setting up a future move). This allows the system to learn complex strategies like subtraction by recognizing that it enables a combination step which ultimately simplifies the equation.

Key findings from the PET experiments include:

  • Automated Conflict Resolution: The system assigns scores based on the distance to a simplification. Rules that simplify immediately are prioritized over those that merely enable future steps.
  • Minimal Guidance: By using perturbation, the teacher only needs to provide solution steps rather than explaining the underlying rules of algebra. The system experiments with the data to find those boundaries itself.

Limitations and Future Directions

While successful in junior high school algebra, PET assumes a "clean" teacher who never makes mistakes. It currently lacks the robustness to handle noise or incorrect examples. Furthermore, the system relies on a coarse definition of "simplification" (reducing term counts), which may not translate easily to more complex domains like symbolic integration or differential equations. Future work aims to expand these episodic and perturbation techniques into these more advanced mathematical fields.

Summary updated

BibTeX
@inproceedings{kibler1983episodic,
  author = {Dennis F. Kibler and Bruce W. Porter},
  title = {{Episodic Learning}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1983},
}
Figure