Induction of Relational Productions in the Presence of Background Information

TL;DR

This paper introduces a unified theory for generalizing relational productions, a formal model for describing changes in discrete systems. The key innovation is incorporating "background information" to improve generalization accuracy, demonstrating its effectiveness across diverse AI paradigms like sequence completion, visual analogies, and learning rules from examples.

What Problem Does This Paper Address?

The field of Artificial Intelligence has seen numerous specialized programs designed to solve specific learning tasks, such as predicting the next letter in a sequence or solving visual analogies. However, a common theoretical foundation for these diverse programs has been elusive. This paper aims to bridge this gap by proposing a general-purpose mathematical theory for inductive learning, specifically focusing on how to generalize "relational productions" – a formal way to represent operators or rules that transform systems. A significant challenge in learning is dealing with incomplete information; this work tackles this by introducing the concept of "background information," which is potentially relevant knowledge not directly present in the learning examples themselves.

Methods

The core of the paper is the development of a theory for relational production generalization. Relational productions are defined as a mechanism for revising a "situation" (a conjunction of literals) based on a rule of the form $\alpha \rightarrow \beta$, where $\alpha$ is the antecedent (condition) and $\beta$ is the consequent (action).

Key methodological contributions include:

  • Formal Definition of Generalization: A production $p_1$ is a generalization of $p_2$ if $p_1$ can achieve any transformation $p_2$ can, and possibly more.
  • Maximal Common Generalizations (MCGs): A method for finding the "best" common generalization of multiple productions, ensuring it captures all shared features.
  • Incorporating Background Information: A novel approach that augments the context of productions with relevant background literals. This relevance is determined through "association chains," which link foreground (instance) literals to background literals.
  • Deterministic Productions: A concept to ensure that a generalized production, when applied, leads to a uniquely determined outcome, preventing ambiguity.

The theory is implemented in a SN0B0L4 program called Thoth-pb.

Datasets

The paper does not introduce new datasets but rather demonstrates the application of the theory on established problem types:

  • Letter Sequence Completion: Problems similar to those in Simon and Kotovsky (1963).
  • Visual Analogies: Problems exemplified by Evans (1968).
  • Before-and-After Pairs: Problems related to learning rules from examples, drawing on concepts from Hayes-Roth (1976).
  • Situation Sequences: Problems exemplified by the Tower of Hanoi puzzle.

The "background information" for these tasks is derived from domain knowledge (e.g., alphabet order, relative sizes of objects, chess board layout).

Key Insights and Ideas

  • Unified Theory for Diverse AI Tasks: The most significant insight is that relational production induction, augmented with background information, provides a common theoretical framework for seemingly disparate AI learning paradigms. This suggests a fundamental principle of inductive inference.
  • The Power of Background Information: The paper convincingly shows that incorporating relevant background knowledge, even if not directly present in the training examples, dramatically improves the quality and specificity of learned productions. This is crucial for real-world learning where data is often sparse or incomplete.
  • Formalizing Inductive Inference: By defining generalization mathematically and providing algorithms for computing MCGs, the paper offers a rigorous approach to inductive learning, moving beyond ad-hoc heuristics.
  • Context Matters: The distinction between the antecedent, consequent, and context of a production, and how background information augments this context, is key to the theory's success.

Key Results

The paper demonstrates the practical application of the theory through the Thoth-pb implementation, achieving:

  • Successful Generalizations: Thoth-pb successfully computed deterministic generalizations for all four paradigms.
  • Efficiency: The examples presented were solved with modest computation times (e.g., 11 seconds for letter sequences and visual analogies, 100 seconds for chess, 36 seconds for Tower of Hanoi).
  • Problem Solving: The program successfully solved all 15 problems from Simon and Kotovsky (1963) for letter sequences.
  • Correct Selection in Analogies: In visual analogies, the system correctly identified the best answer by comparing generalized productions.
  • Handling of Nondeterminism: The theory and implementation can identify and, if desired, discard nondeterministic generalizations, leading to more precise rules.

Limitations and Future Work

  • Error-Free Data Assumption: The paper explicitly states that the current theory assumes "error free data." Handling "noisy" data is identified as a topic for future work.
  • Static Background Information: The background information is provided explicitly and stored. The authors suggest generalizing this by allowing background literals to be dynamically inferred, rather than requiring them to be stored explicitly.
  • Association Chain Length Limit: A practical limit is placed on the length of association chains to prevent excessive computation. This comes at the cost of potentially ignoring relevant information.
  • Representation Dependence: The authors acknowledge that the style of representation influences the difficulty of solutions, and while this paper assumes error-free data, future work could explore more complex representations.

Summary updated

BibTeX
@inproceedings{1977induction,
  title = {{Induction of Relational Productions in the Presence of Background Information}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1977},
}

Loading related content...

Figure