CHARACTERIZATION OF PROBABILISTIC INFERENCE.

Leonard Pitt

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Inductive Inference Machines (IIMs) attempt to identify functions given only input-output pairs of the functions. Probabilistic IIMs are defined, as is the probability that a probabilistic IIM identifies a function with respect to two common identification critera: EX and BC. Let ID denote either of these criteria. Then ID//p //r //o //b (p) is the family of sets of functions U for which there is a probabilistic IIM identifying every f belonging to U with probability greater than equivalent to p. It is shown that for all positive integers n, ID//p //r //o //b (1/n) is properly contained in ID//p //r //o //b (1/(n plus 1)), and that this discrete hierarchy is the finest possible. This hierarchy is related to others in the literature.

Original languageEnglish (US)
Title of host publicationAnnual Symposium on Foundations of Computer Science (Proceedings)
Pages485-494
Number of pages10
DOIs
StatePublished - 1984

Publication series

NameAnnual Symposium on Foundations of Computer Science (Proceedings)
ISSN (Print)0272-5428

ASJC Scopus subject areas

  • Hardware and Architecture

Fingerprint

Dive into the research topics of 'CHARACTERIZATION OF PROBABILISTIC INFERENCE.'. Together they form a unique fingerprint.

Cite this