Probabilistic Inductive Inference

L. Pitt

Research output: Contribution to journalArticlepeer-review


Inductive inference machines construct programs for total recursive functions given only example values of the functions. Probabilistic inductive inference machines are defined, and for various criteria of successful inference, it is asked whether a probabilistic inductive inference machine can infer larger classes of functions if the inference criterion is relaxed to allow inference with probability at least p, 1989 as opposed to requiring certainty. For the most basic criteria of success (EX and BC), it is shown that any class of functions that can be inferred from examples with probability exceeding 1/2 can be inferred deterministically, and that for probabilities p ≤ 1/2 there is a discrete hierarchy of inferability parameterized by p. The power of probabilistic inference strategies is characterized by equating the classes of probabilistically inferable functions with those classes that can be inferred by teams of inductive inference machines (a parallel model of inference), or by a third model called frequency inference.

Original languageEnglish (US)
Pages (from-to)383-433
Number of pages51
JournalJournal of the ACM (JACM)
Issue number2
StatePublished - Jan 4 1989
Externally publishedYes

ASJC Scopus subject areas

  • Software
  • Control and Systems Engineering
  • Information Systems
  • Hardware and Architecture
  • Artificial Intelligence


Dive into the research topics of 'Probabilistic Inductive Inference'. Together they form a unique fingerprint.

Cite this