Probabilistic Inductive Inference

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.