From Statistics to Beliefs

Fahiem Bacchus, Adam J. Grove, Daphne Koller, Joseph Y. HalpernAAAI 1992

Introduction: The Reference Class Problem

In the field of Artificial Intelligence, a central challenge is determining how an agent should assign a degree of belief to a specific proposition based on general statistical knowledge. Consider an AI diagnostic system tasked with assessing a patient's risk. If the system knows that 20% of American males are tall, but 25% of Californian males are tall, which statistic should it apply to Eric, a Californian male?

This dilemma is known as the Reference Class Problem. Traditional "direct inference" approaches typically rely on heuristic rules, such as picking the most specific class available. However, these heuristics often falter when faced with conflicting statistics, irrelevant data (e.g., Eric's musical preferences), or complex "disjunctive" classes. This paper moves beyond these ad-hoc rules to provide a principled mathematical framework for inductive reasoning.

Theoretical Framework: The Principle of Indifference

The authors' approach is rooted in the Principle of Indifference, which posits that in the absence of evidence to the contrary, all possibilities should be treated as equally likely. The paper explores how different interpretations of "possibility" lead to distinct methods for assigning degrees of belief.

Three Methods of Inductive Reasoning

The authors formalize three realizations of this principle, focusing on a simplified logic of properties (unary predicates) and individuals (constants):

  1. Random Worlds: This method assigns equal probability to every possible first-order structure (world) consistent with the agent's knowledge. It is mathematically linked to the Principle of Maximum Entropy, a standard tool in statistical inference.
  2. Random Structures: Here, worlds that are isomorphic—identical except for the names of individuals—are grouped into "situations." Each situation is assigned equal probability. This approach is characterized by a "Center of Mass" calculation.
  3. Random Propensities: Introduced as a novel approach, this method measures the propensity of an individual to satisfy specific predicates. It relies on a "Maximum Independence" principle, assuming properties are independent unless the data indicates a correlation.
Foundational literature cited in the development of the Random Worlds and Random Propensities methods.

Key Insights and Ideas

The comparison of these methods reveals several critical properties of inductive reasoning:

  • Automatic Specificity: Remarkably, all three methods naturally favor more specific information (e.g., Californian statistics over national ones) without requiring explicit heuristic rules.
  • The Role of Language: The choice of vocabulary is paramount. The "Random Propensities" method treats predicates as "natural" properties, which helps it avoid classic philosophical issues like the Grue/Bleen paradox.
  • Distinguishability and Scalability: The difference between "Random Worlds" and "Random Structures" hinges on whether individuals are considered distinguishable. As the vocabulary becomes "richer" (specifically, containing at least $3 \log N$ predicates for $N$ individuals), these two methods converge.
  • Robustness to Irrelevance: "Random Worlds" and "Random Propensities" successfully ignore irrelevant information. In contrast, "Random Structures" can be sensitive to it, as adding new names or properties alters the count of non-isomorphic situations.
Extended bibliography highlighting the historical context of direct inference and maximum entropy.

Results and Comparative Analysis

The paper establishes several formal results:

  • Deductive Consistency: All methods are "safe," assigning a degree of belief of 1 to any fact that is logically certain given the database.
  • Alignment with Direct Inference: In simple cases where statistics are clear and non-conflicting, all three methods align with traditional direct inference results.
  • Sampling vs. Defaulting: The methods diverge when statistics are missing for a general class but known for a small sample. "Random Propensities" tends to treat the sample as representative, whereas "Random Worlds" defaults to a 0.5 probability for the unknown population.

Conclusion and Future Work

The authors conclude that no single method is universally superior; rather, they represent different intuitions suitable for different domains. While the current work focuses on unary predicates, the framework is designed to extend to richer vocabularies involving relations. Future research will explore the computational complexity of these methods and the potential for hybrid approaches that combine their respective strengths.

Summary updated

BibTeX
@inproceedings{bacchus1992from,
  author = {Fahiem Bacchus and Adam J. Grove and Daphne Koller and Joseph Y. Halpern},
  title = {{From Statistics to Beliefs}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1992},
}
Figure