Inferring Probabilistic Theories from Data

AAAI 1988

TL;DR

This paper introduces a novel criterion for evaluating probabilistic theories based on their predictive power, framed as a gambling scenario. It also proposes a minimum description length-based rule for selecting theories from finite data, proving that this rule converges to optimal theories given sufficient observations. This work provides a theoretical foundation for inductive inference in the presence of uncertainty.

What Problem Does This Paper Address?

Inductive inference, the process of learning theories from data, traditionally focuses on error-free observations and deterministic models. However, real-world data is often noisy or inherently uncertain, making deterministic models inappropriate. In such cases, simply finding a theory that perfectly fits the observed data can lead to overfitting, where the model captures noise rather than underlying patterns. This is akin to fitting a high-degree polynomial to a few data points, which will perform poorly on new data. The core problem this paper addresses is how to judge when a probabilistic theory "agrees well enough" with uncertain data, especially when dealing with potentially infinite streams of observations. It seeks a criterion for predictive power and a practical method for selecting theories that are not only good fits but also generalize well.

Methods

The paper proposes two main contributions:

  1. A Criterion for Predictive Power (Gambling Scenario): The authors frame the evaluation of a theory's predictive power as a gambling scenario. Imagine using a theory to place bets on future observations (e.g., binary bits). A theory with high predictive power will win more bets over the long run, accumulating more "capital." This criterion defines a "suitable" theory as one that wins at least as much as any other computable theory, up to a constant factor, when betting on an infinite sequence of observations. This asymptotic approach helps avoid issues with unlikely events in finite datasets.
  2. A Theory Selection Rule (Minimum Description Length): For practical inference from finite data, the paper proposes a selection rule based on the Minimum Description Length (MDL) principle. The rule is to select the theory $T$ that minimizes the sum of two components:
  3. $l(T)$: The length (in bits) of a machine-readable representation of the theory $T$ (measuring complexity).
  4. $l(x_1...x_n | T)$: The number of bits needed to encode the observed data $x_1...x_n$ given theory $T$ (measuring goodness-of-fit).

    This MDL approach balances theory complexity with its ability to explain the data, preventing overfitting. A modified MDL rule, which minimizes $l(T) + d(x_1...x_n || T)$, where $d$ is a measure of "extra bits" needed relative to the best possible theory, is shown to guarantee convergence to optimal theories.

Datasets

Not discussed in the paper. The paper focuses on theoretical frameworks for inferring theories from abstract binary sequences rather than specific real-world datasets.

Key Insights and Ideas

  • Gambling as a Measure of Predictive Power: Framing theory evaluation as a gambling game provides an intuitive and robust way to quantify predictive success, especially in the long run. It naturally handles uncertainty and noise.
  • MDL for Theory Selection: The Minimum Description Length principle offers a principled way to balance model complexity and data fit, a fundamental challenge in inductive inference. It directly addresses the overfitting problem.
  • The Importance of Asymptotic Behavior: For judging "good enough" theories, considering an infinite sequence of observations is crucial. This avoids being misled by short-term lucky streaks or unlucky events.
  • Computability as a Practical Constraint: The paper acknowledges that ideal theories (e.g., ideal gambling functions) might not be computable. This leads to the need for computable approximations and the study of their convergence properties.
  • Philosophical Implications of Non-Computability: The paper touches upon the philosophical question of whether non-computable generating functions imply true randomness or simply a limitation of our knowledge and computational abilities.

Key Results

  • A criterion for evaluating predictive power based on asymptotic winnings in a gambling scenario is presented.
  • A theory selection rule based on minimizing $l(T) + d(x_1...x_n || T)$ is proposed.
  • A proof outline demonstrates that this selection rule converges to optimal gambling functions (theories) when an optimal one exists, ensuring that the selected theories satisfy the predictive power criterion given sufficient data.
  • Theorem 2 states that using the modified MDL rule (minimizing $l(T) + d(x_1...x_n || T)$) guarantees a finite set of distinct programs and that these programs are optimal for sufficiently large datasets.

Limitations and Future Work

  • Practical Implementation Challenges: The paper notes that applying the selection rule directly can be computationally expensive, as it may require comparing a vast number of theories. If theories can be described as Turing machines, the selection rule becomes undecidable due to the halting problem.
  • General Convergence Proof: While a proof outline is provided, a full general convergence proof for the MDL rule in all cases remains an open problem.
  • Characterizing Learnable Models: The authors suggest future work in characterizing classes of models that can be learned efficiently, similar to work in concept learning.
  • Philosophical Debate: The paper raises deep philosophical questions about randomness, determinism, and the limits of knowledge, inviting further discussion and research.

Summary updated

BibTeX
@inproceedings{1988inferring,
  title = {{Inferring Probabilistic Theories from Data}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1988},
}
Figure