TY - GEN

T1 - CHARACTERIZATION OF PROBABILISTIC INFERENCE.

AU - Pitt, Leonard

N1 - Copyright:
Copyright 2011 Elsevier B.V., All rights reserved.

PY - 1984

Y1 - 1984

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0021548503&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0021548503&partnerID=8YFLogxK

U2 - 10.1109/SFCS.1984.715951

DO - 10.1109/SFCS.1984.715951

M3 - Conference contribution

AN - SCOPUS:0021548503

SN - 081860591X

SN - 9780818605918

T3 - Annual Symposium on Foundations of Computer Science (Proceedings)

SP - 485

EP - 494

BT - Annual Symposium on Foundations of Computer Science (Proceedings)

PB - IEEE

ER -