Can I read Aspects of Complexity of Probabilistic Learning Under Monotonicity Constraints on EtoBox?

Aspects of Complexity of Probabilistic Learning Under Monotonicity Constraints by Léa Meyer is a Computer Science article available to read on EtoBox.

What is Aspects of Complexity of Probabilistic Learning Under Monotonicity Constraints about?

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 learning 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 identiÿcation 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 su cient 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 ¡ p62=3. In the case of strong-monotonic learning with p ¿ 2=3, however, every Peano-complete oracle is su cient for compensating the power of probabilistic learning machines. In contrast, the oracle K is not su cient for compensating the power of conservat

Who reads Aspects of Complexity of Probabilistic Learning Under Monotonicity Constraints?

Author

Léa Meyer

Publisher

Elsevier Science; Elsevier ; Elsevier BV (ISSN 0304-3975)

Published

2001

Language

EN

Field

Computer Science (Physical Sciences)