A METRIC ENTROPY BOUND IS NOT SUFFICIENT FOR LEARNABILITY

Authors
DUDLEY RM KULKARNI SR RICHARDSON T ZEITOUNI O
Citation
Rm. Dudley et al., A METRIC ENTROPY BOUND IS NOT SUFFICIENT FOR LEARNABILITY, IEEE transactions on information theory, 40(3), 1994, pp. 883-885
Citations number
9
Categorie Soggetti
Information Science & Library Science","Engineering, Eletrical & Electronic
Journal title
IEEE transactions on information theory → ACNP
ISSN journal
00189448
Volume
40
Issue
3
Year of publication
1994
Pages
883 - 885
Database
ISI
SICI code
0018-9448(1994)40:3<883:AMEBIN>2.0.ZU;2-D
Abstract
We prove by means of a counterexample that it is not sufficient, for p robably approximately correct (PAC) learning under a class of distribu tions, to have a uniform bound on the metric entropy of the class of c oncepts to be learned. This settles a conjecture of Benedek and Itai.