Inductive Inference by Refinement

Philip D. LairdAAAI 1986

Abstract

In the mid-1980s, the field of inductive learning—deriving general rules from specific examples—was characterized by domain-specific heuristics. P. D. Laird’s work, Inductive Inference by Refinement, provides a unified formal framework for this process, treating learning as an iterative search through a space of hypotheses. By mathematically defining the relationship between a rule's syntax and its semantic meaning, Laird bridges disparate learning domains, from logic programming to formal languages, under a single algorithmic model.

The Problem of Fragmentation

Before Laird’s formalization, inductive learning systems were often bespoke. Whether a system was learning LISP programs, chemical structures, or grammar, the underlying logic of "refinement"—making a hypothesis broader or narrower to fit new data—felt intuitively similar but lacked a rigorous, shared foundation. The challenge was to ensure that as a system changed the "syntax" of a rule (e.g., replacing a specific attribute with a "don't care" symbol), the "semantics" (the set of objects the rule describes) changed in a predictable, ordered way.

A Unified Formal Framework

Laird tackles this fragmentation by introducing a formal definition of an Inductive Inference Problem consisting of six core components. The most critical among these are:

  • Semantic Domain ($D, \ge$): A partially ordered set representing the "meanings" or objects described by rules.
  • Syntactic Domain ($E$): The language or expressions used to represent those rules.
  • Mapping ($h$): A function that connects a syntactic rule to its semantic meaning.

To ensure the system behaves logically, Laird specifies that the mapping must be an order-homomorphism. This means that if rule A is syntactically "greater" (more general) than rule B, its semantic meaning must also be broader. This alignment allows the learner to navigate the hypothesis space with mathematical certainty.

Refinement Operators and the UP-INFER Algorithm

The core innovation of the paper is the Refinement Operator. Laird defines two types:

  1. Upward Refinement ($\gamma$): Takes a rule and produces a set of more general rules.
  2. Downward Refinement ($\rho$): Takes a rule and produces a set of more specific rules.

Using these operators, Laird outlines the UP-INFER algorithm. This is a bottom-up approach that begins with a highly specific hypothesis. Whenever the current hypothesis fails to explain a new positive example, the algorithm applies upward refinement to generalize it. Laird proves that if a refinement operator is "complete"—meaning any valid generalization can eventually be reached by repeatedly applying the operator—the algorithm is guaranteed to converge to a correct hypothesis, provided it receives a sufficient set of examples.

Cross-Domain Validation

As a theoretical work, the paper validates its model by applying it to several classic illustrative domains:

  • Concept Learning: Objects with attributes like size, color, and shape (building on Mitchell’s Version Spaces).
  • Logic Programming: Learning first-order clauses and predicates (referencing Shapiro’s Model Inference System).
  • Formal Languages: Inferring regular sets and grammars from strings.
  • Functional Programming: Synthesizing LISP programs from input-output examples.

By expressing these diverse tasks in a single mathematical language, Laird successfully unified previously distinct work by Mitchell, Shapiro, and Biermann.

Key Insights

  • Refinement as Algebra: Laird argues that constructing a learning algorithm is essentially an algebraic task of defining the right refinement operators, rather than just a heuristic search.
  • Directional Asymmetry: The paper notes that some domains are easier to learn bottom-up (generalizing) while others are better top-down (specializing), often depending on "local finiteness"—whether a rule has a finite or infinite number of immediate generalizations.
  • Avoiding Triviality: A common pitfall in induction is the "disjunction problem," where a system simply lists all positive examples as its rule. Laird shows how refinement algorithms can avoid this by prioritizing elegant, compact rules in the search queue.
  • Oracular Abstraction: By using "oracles" for examples and partial orders, Laird separates the logic of induction from the computational complexity of testing if a rule matches an example.

Limitations and Future Directions

Despite its theoretical strength, the model has practical limitations. It provides a "skeleton" for algorithms but does not automatically yield the most efficient version for a specific task. Furthermore, refinement algorithms are sensitive to noise; a single incorrect example can lead to over-generalization from which the system cannot easily recover. Finally, the model relies on a fixed language. It cannot "invent" new intermediate concepts or predicates to simplify complex rules—a challenge Laird identifies as the next critical frontier for inductive learning research.

Summary updated

BibTeX
@inproceedings{laird1986inductive,
  author = {Philip D. Laird},
  title = {{Inductive Inference by Refinement}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1986},
}
Figure