Preliminary Steps Toward the Automation of Induction

Stuart RussellAAAI 1986

Abstract

This paper proposes a formal framework for automating induction by bridging the gap between raw observations and high-level world knowledge. It introduces "determinations"—a logical structure that explains why a single observation can sometimes justify a universal generalization, while others cannot. By treating induction as a search problem within a formal logical framework, the author provides a computational path toward solving classic philosophical paradoxes in artificial intelligence.

Introduction

In the field of machine learning, the transition from specific observations to general rules has historically relied on "linguistic bias"—pre-programmed constraints that dictate what a machine is allowed to learn. However, for an artificial intelligence to achieve true autonomy, it must possess a domain-independent theory of how existing knowledge justifies the acquisition of new rules. This paper addresses the fundamental "Problem of Induction" and Nelson Goodman’s "New Riddle of Induction," seeking to formalize why certain generalizations are considered "projectible" (rational to assume) while others are not.

The Problem of Projectibility

The core challenge lies in distinguishing between valid and absurd generalizations. For instance, why is it rational to assume "All emeralds are green" based on past observations, but irrational to assume "All emeralds are grue" (where "grue" implies an arbitrary color change at a future date)?

Russell argues that induction is rarely performed in vacuo. Human reasoning does not simply count instances; it utilizes a hierarchy of higher-level regularities. We believe all emeralds are green because we have a higher-level belief that the intrinsic properties of minerals are uniform—a belief itself induced from experiences with other minerals like rubies and sapphires.

The Determination Connective

The paper’s primary technical contribution is the formalization of "determinations." A determination is a higher-level regularity stating that one property or set of properties determines another. For example, the statement "Nationality determines Language" is a determination.

This logical structure serves as the missing link for both analogy and single-instance generalization. If a system knows that property $P$ determines property $Q$, it requires only a single instance of $P(a)$ and $Q(a)$ to validly conclude that $\forall x, P(x) \implies Q(x)$. This moves induction away from purely syntactic pattern matching and toward a semantic understanding of world regularities.

To implement this theory, the author approaches induction as a search problem using a "reverse resolution" algorithm. This process involves:

  1. Goal Identification: Starting with a base-level rule (the target generalization).
  2. Backward Mapping: Working backward to identify higher-level "schematic" rules.
  3. Deductive Justification: Finding the schematic rules that, if true, would deductively imply the base-level rule given the available instances.

While the paper is theoretical, it references the CYC project—a massive common-sense knowledge base—as the intended environment for testing these theories in a real-world context.

Key Insights

  • Induction as a Recursive Process: Base-level rules are confirmed by higher-level regularities, which are in turn confirmed by even higher-level ones, eventually reaching the "evolutionary" foundations of a knowledge stack.
  • Syntactic vs. Semantic Induction: Russell argues against purely syntactic induction. He suggests that human language has evolved to include terms like "green" because they are "well-entrenched" predictors of other properties, whereas "grue" lacks this predictive utility.
  • Computational Philosophy: The paper provides a computational logic equivalent to Goodman’s "Theory of Projectibility," transforming abstract philosophical concepts into calculable AI operations.

Results and Limitations

The search algorithm successfully identified several important classes of higher-level rules, most notably Determinations and Extended Determinations. The author concludes that the more classes of regularity a system is equipped to observe, the more inferences it can validly make from limited data.

However, several challenges remain:

  • Search Space: At the time of writing, the search space for regularities was sufficiently large that human evaluators were required to prune "implausible" paths.
  • Logic Constraints: The framework was limited to first-order regularities. Capturing "natural kinds" or statistical variations would require more complex, non-first-order logic.
  • Uncertainty: The current model assumes higher-level rules are "literally true." Future iterations must account for the degree of confirmation when regularities are less than 100% certain.

Conclusion

By formalizing the relationship between specific instances and high-level knowledge, this work provides a foundational step toward autonomous inductive systems. It suggests that the path to robust AI learning lies not just in more data, but in a more sophisticated logical understanding of how different properties of the world determine one another.

Summary updated

BibTeX
@inproceedings{russell1986preliminary,
  author = {Stuart Russell},
  title = {{Preliminary Steps Toward the Automation of Induction}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1986},
}
Figure