The Problem of Induction and Machine Learning

Francesco BergadanoIJCAI 1991

Abstract

This paper bridges the gap between classical philosophy and modern artificial intelligence by examining the "problem of induction" in Machine Learning (ML). It argues that induction in symbolic domains is hindered by two primary obstacles: the Predictivity Problem, where complex languages lead to overfitting, and the Complexity Problem, where searching for optimal rules is computationally intractable. The author proposes that Explanation-based Learning (EBL) provides a necessary solution by using logical domain theories to constrain the hypothesis space, making induction both feasible and predictive.

Introduction

Philosophers have long grappled with the "Problem of Induction"—the realization that past observations do not logically guarantee future outcomes. In the realm of Machine Learning, this philosophical concern manifests as a practical crisis. As we move from simple numerical models to complex symbolic logic, the "leap" from examples to general rules becomes increasingly fraught with risk. The paper argues that the challenge is not just making the leap, but surviving the search through an exponential space of possibilities.

The Dual Challenges of Symbolic Induction

The author identifies two specific hurdles that make symbolic induction particularly difficult:

  1. The Predictivity Problem: As the language used to describe rules increases in expressivity, the number of possible hypotheses grows exponentially. With an overly large search space, a learner is likely to find a rule that fits the training data perfectly by chance but fails to generalize to new data—a classic case of overfitting.
  2. The Complexity Problem: Searching for the "best" rule within these massive symbolic spaces is often NP-hard. Unlike continuous spaces where gradient descent can navigate efficiently, discrete symbolic spaces (e.g., "If X and Y, then Z") require exhaustive or highly constrained searches.

Frameworks for Induction

The paper evaluates several existing frameworks for addressing these challenges:

  • Statistical Estimation: While useful for bounding error, it often requires unrealistic a priori knowledge of probability distributions.
  • Subjective Bayesian Inference: The author notes that in symbolic ML, the choice of "prior probabilities" is functionally equivalent to pre-selecting which hypotheses are even possible, making the "prior" the most critical component.
  • Computational Learning Theory (PAC Learning): This framework uses Vapnik-Chervonenkis (VC) bounds to relate the size of the hypothesis space to the number of examples required for reliable learning.

Explanation-based Learning (EBL) as Logical Bias

The core proposal of the paper is a reframing of Explanation-based Learning (EBL). Traditionally viewed as a method for speeding up reasoning, the author argues that EBL is actually a vital tool for defining a "plausible" hypothesis space. By requiring that all learned rules be derivable from a pre-existing "domain theory," EBL drastically prunes the search space. This "logical bias" ensures that the induction process is grounded in existing knowledge, mitigating both the complexity and predictivity problems.

Illustrative Examples

To demonstrate these concepts, the paper utilizes toy examples from discrete, symbolic domains such as Peano’s arithmetic and simple games.

Figure 1: A Tic-Tac-Toe board representing a discrete, symbolic state space used to illustrate logical induction.

In a game like Tic-Tac-Toe, the state space is finite but symbolic. Inducing a winning strategy requires navigating rules that are discrete rather than continuous. Without a domain theory (the rules of the game), a learner might induce "lucky" patterns that do not hold true in general play. EBL allows the system to use the rules of the game to "explain" a win, thereby generating a specialized rule that is deductively certain within that theory.

Conclusion: The Persistence of Intuition

While EBL offers a powerful way to constrain induction, it introduces the "Source of Knowledge" problem: where does the domain theory come from? If the initial theory is flawed, the induction will be as well. The author concludes that all machine induction eventually rests on "intuition" or a "lucky guess" regarding the fundamental constraints of the world. Future work should focus on knowledge transfer and developing more expressive yet constrained frameworks for defining hypothesis spaces.

Summary updated

BibTeX
@inproceedings{bergadano1991problem,
  author = {Francesco Bergadano},
  title = {{The Problem of Induction and Machine Learning}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1991},
}
Figure