Induction of Relational Productions in the Presence of Background Information

Steven A. Vere

TL;DR

This paper introduces a unified theory for generalizing relational productions, a formal model for describing changes in discrete systems. By incorporating "background information" (relevant facts not directly in the problem instance), the theory enables a single induction mechanism to solve diverse AI problems like sequence completion, visual analogies, and learning rules from examples.

What Problem Does This Paper Address?

The paper tackles the challenge of creating a general-purpose inductive learning system that can learn "rules" or "productions" from data. Many existing AI programs excel at specific tasks (e.g., letter sequence prediction, visual analogies), but they often rely on ad-hoc solutions. The authors argue that a common underlying principle, relational production induction, can unify these diverse paradigms. A key problem is how to leverage external, relevant knowledge (background information) to improve generalization, especially when the provided examples are sparse or incomplete.

Methods

The core of the paper is the theory of relational production generalization. Relational productions are defined as mechanisms that revise a "situation" (a conjunction of literals) based on a pattern-matching rule. The generalization process aims to find a more abstract production that can explain multiple specific instances.

Key methodological contributions include:

  • Relational Productions: A formal model combining string productions and STRIPS operators, allowing for mathematical analysis.
  • Generalization Definition: A formal definition of when one production is a generalization of another.
  • Maximal Common Generalizations (MCGs): A method for computing the most specific common generalization of multiple productions.
  • Background Information Integration: A novel approach to augment the context of productions with relevant background literals using association chains. This allows the system to infer more robust rules by connecting foreground information (from the problem instance) to background knowledge.
  • Deterministic Productions: A concept to ensure that generalized productions lead to uniquely determined outcomes, preventing overgeneralization.

Datasets

The paper does not introduce new datasets but rather uses established problem domains for evaluation:

  • Letter Sequence Completion: Problems similar to those in Simon and Kotovsky (1963).
  • Visual Analogies: Problems inspired by Evans (1968).
  • Before-and-After Pairs: Examples from chess (white pawn moves).
  • Situation Sequences: The Tower of Hanoi puzzle.

The "background information" for each domain (e.g., alphabet ordering, relative card ranks, chess board layout, disc sizes) is provided as part of the problem setup.

Key Insights and Ideas

  • Unified Induction: The paper demonstrates that a single, principled approach to relational production induction can effectively address seemingly disparate AI tasks. This suggests a fundamental mechanism for learning in intelligent systems.
  • Power of Background Knowledge: Integrating background information via association chains is crucial for robust generalization. It allows the system to infer rules that would be impossible to derive from foreground data alone, especially in complex domains.
  • Formalizing Generalization: The mathematical framework for relational productions and their generalization allows for rigorous proofs and a deeper understanding of the learning process, moving beyond heuristic approaches.
  • Context is Key: The concept of production context, especially when augmented with background information, plays a vital role in determining the applicability and determinism of learned rules.

Key Results

The paper presents a computer implementation (Thoth-pb) that successfully applies the theory to the four intelligence paradigms. Specific results include:

  • Letter Sequences: Solved 15 problems in 11 seconds, finding deterministic generalizations.
  • Visual Analogies: Selected the correct answer for a visual analogy problem in 11 seconds.
  • Before-and-After Pairs: Learned rules for chess pawn moves, distinguishing legal and illegal moves, in 100 seconds (or 84 seconds if ignoring nondeterministic generalizations).
  • Situation Sequences: Generalized the Tower of Hanoi operator in 36 seconds.

The implementation demonstrates the efficiency and generality of the proposed induction method.

Limitations and Future Work

  • Error-Free Data: The current theory assumes error-free input data. The authors acknowledge that handling "noisy" data is a significant area for future work.
  • Explicit Background Information: The background information is currently provided explicitly. A future direction is to generalize this by allowing background literals to be dynamically inferred.
  • Computational Complexity: While the examples are efficient, the paper notes that the computational cost can increase with the complexity of the problem and the size of the background information. Limiting association chain length is a practical measure to manage this.
  • Representation Influence: The authors briefly mention that the style of representation influences the difficulty of solutions, suggesting that exploring different representations could be beneficial.

Summary updated

BibTeX
@inproceedings{vere1977induction,
  author = {Steven A. Vere},
  title = {{Induction of Relational Productions in the Presence of Background Information}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1977},
}
Figure