Overview of an Example Generation System

Edwina L. Rissland, Elliot SolowayAAAI 1980

Abstract

This paper introduces Constrained Example Generation (CEG), a framework designed to automate the creation of examples—such as LISP code or mathematical functions—that satisfy specific, complex requirements. By mimicking the human cognitive process of retrieving and modifying known cases, the CEG system moves beyond simple database search toward active, knowledge-based construction. This approach prioritizes the intelligent modification of "near-miss" examples to meet new constraints, offering a flexible architecture applicable across multiple domains including computer science, geometry, and scene analysis.

Introduction

In fields like mathematics and computer science, examples serve as vital tools for testing hypotheses, debugging code, and pedagogical instruction. However, generating an example that satisfies a complex set of "desiderata" (constraints) is a non-trivial task. Traditional AI approaches often rely on searching static databases or following rigid, predefined templates. These methods lack the flexibility required to handle novel or highly specific constraints.

The authors argue that a truly intelligent system should emulate human experts, who often brainstorm by taking an existing example and intelligently tweaking it to fit new requirements. To this end, they propose the Constrained Example Generation (CEG) model, a system that treats example generation as a process of modification and construction rather than mere retrieval.

The CEG Framework

The CEG model is structured around four primary processes that govern how examples are handled:

  1. RETRIEVE: The system searches a "storehouse" of known examples to find candidates that partially match the target constraints.
  2. JUDGE: The system evaluates how well a candidate example satisfies the given constraints, identifying specific deficiencies.
  3. MODIFY: If a candidate is a "near-miss," the system applies transformation routines to fix its deficiencies.
  4. CONSTRUCT: If modification fails or no suitable candidate is found, the system attempts to build a new example from scratch using internal models or templates.

System Architecture

Implemented in LISP and running on a VAX 11/780, the system utilizes an EXECUTIVE process to manage the workflow. The core of the system is its dual-part knowledge base:

  • Examples-space: A permanent graph where examples are represented as "frames" (data structures with attributes). These frames are linked by "constructional derivation," tracking how one example was used to build another.
  • Temporary Knowledge Base: A workspace used during specific problem-solving sessions to store evaluation data and intermediate candidate examples.

An AGENDA-KEEPER maintains a prioritized list of examples to be modified, ranking them based on their proximity to the goal state.

Domain Applications and Data

Unlike modern machine-learning systems that rely on massive datasets, the CEG system utilizes domain-specific knowledge bases containing reference examples and counter-examples. Key domains include:

  • LISP Programming: Standard reference examples (e.g., empty lists) and counter-examples that typically reveal edge cases in programs.
  • Geometry and Functions: Generation of piecewise linear functions.
  • Scene Analysis: Descriptions of visual scenes for the VISIONS system.
  • Games: Generation of valid action sequences.

Key Insights

Modification over Construction

A central tenet of the CEG framework is the prioritization of modification. By tweaking a "close" example rather than starting from scratch, the system utilizes a cognitive shortcut that reduces computational overhead and leverages existing knowledge structures.

Constructional Derivation

By linking examples through their derivation history, the system creates a map of conceptual relationships. This allows the system to understand not just what an example is, but how it relates to other concepts in the mathematical or logical space.

Constraint Interaction

The authors highlight the challenge of constraint interaction: satisfying one requirement often violates another. For example, in the LISP domain, adding an element to a list to satisfy a "depth" requirement might inadvertently violate a "length" requirement. Managing these interdependencies is a primary focus of the JUDGE and MODIFY phases.

Results and Utility

The paper demonstrates the system's efficacy through qualitative walkthroughs. In one LISP-based example, the system was tasked with generating a list of length 3 with a specific nesting depth. It retrieved the list (A B C), identified it as a near-miss, and successfully modified it into ((A) B C) to satisfy the depth constraint.

Beyond code generation, the CEG architecture proved flexible enough to generate scene descriptions for computer vision and action sequences for games. Furthermore, the system was integrated into an Intelligent Computer-Assisted Instruction (ICAI) tutor, where it generated practice problems for students and evaluated student-submitted examples for underlying misconceptions or "bugs."

Limitations and Future Directions

While the CEG model represents a significant step forward, the authors identify several areas for improvement:

  • Complexity Management: The current approach, which utilizes a "General Problem Solver" (GPS) style of difference-reduction, struggles when constraints are highly interdependent or contradictory.
  • Planning: There is a recognized need for more sophisticated planning mechanisms to handle complex constraint interactions more strategically.
  • Self-Adaptation: Future iterations aim to incorporate "hill-climbing" techniques, allowing the system to learn which modification routines are most effective over time, thereby improving its own performance through experience.

In its current state, the system serves as a robust "first-pass" implementation of the theoretical CEG model, demonstrating the power of knowledge-based example construction.

Summary updated

BibTeX
@inproceedings{rissland1980overview,
  author = {Edwina L. Rissland and Elliot Soloway},
  title = {{Overview of an Example Generation System}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1980},
}
Figure