In the setting of learning indexed families, probabilistic learning under monotonicity constraints is more powerful than deterministic learning under monotonicity constraints, even if the probability is close to 1, provided the teaming machines are restricted to proper or class preserving hypothesis spaces (cf. Meyer, Theoret. Comput. Sci. 185 (1997) 81-128). In this paper, we investigate the relation between probabilistic learning and oracle identification under monotonicity constraints. In particular, we deal with the question how much additional information provided by oracles is necessary for compensating the additional power of probabilistic learning machines. In Section 1. we show that K is necessary and sufficient to compensate the additional power of probabilistic learning machines in the case of conservative (monotonic) probabilistic learning with p > 1/2 (p > 2/3), and for strong-monotonic probabilistic learning with 1/2 < p less than or equal to2/3. In the case of strong-monotonic teaming with p > 2/3, however, every Peano-complete oracle is sufficient for compensating the power of probabilistic teaming machines. In contrast, the oracle H is not sufficient for compensating the power of conservative and strong-monotonic probabilistic learning with probability p = 1/2, and monotonic probabilistic learning with p = 2/3. The main result in Section 2 is that for each oracle A less than or equal to (T) K, there exists an indexed family L-A which is properly conservatively identifiable with p = 1/2, and which exactly reflects the Turing degree of A, i.e., L-A is properly conservatively identifiable by an oracle machine M[B] iff A less than or equal to (T) B. Thus, for every oracle A below K, we can construct a learning problem characterizing A within proper conservative learning. However, not every indexed family which is conservatively identifiable with probability p = 1/2 reflects the Turing degree of an oracle. Hence, the conservative probabilistic learning classes are higher structured than the Turing degrees below K. Finally, we prove that there exist learning problems which are conservatively (monotonically) identifiable with probability p = 1/2 (p = 2/3), but conservatively (monotonically) identifiable only by oracle machines having access to TOT strong-monotonic learning, this result does not hold. (C) 2001 Elsevier Science B.V. All rights reserved. [References: 44]
展开▼
