TY - GEN

T1 - Scale-sensitive dimensions, uniform convergence, and learnability

AU - Alon, Noga

AU - Ben-David, Shai

AU - Cesa-Bianchi, Nicolo

AU - Haussler, David

PY - 1993/12/1

Y1 - 1993/12/1

N2 - Learnability in Valiant's PAC learning model has been shown to be strongly related to the existence of uniform laws of large numbers. These laws define a distribution-free convergence property of means to expectations uniformly over classes of random variables. Classes of real-valued functions enjoying such a property are also known as uniform Glivenko-Cantelli classes. In this paper we prove, through a generalization of Sauer's lemma that may be interesting in its own right, a new characterization of uniform Glivenko-Cantelli classes. Our characterization yields Dudley, Gine, and Zinn's previous characterization as a corollary. Furthermore, it is the first based on a simple combinatorial quantity generalizing the Vapnik-Chervonenkis dimension. We apply this result to characterize PAC learnability in the statistical regression framework of probabilistic concepts, solving an open problem posed by Kearns and Schapire. Our characterization shows that the accuracy parameter plays a crucial role in determining the effective complexity of the learner's hypothesis class.

AB - Learnability in Valiant's PAC learning model has been shown to be strongly related to the existence of uniform laws of large numbers. These laws define a distribution-free convergence property of means to expectations uniformly over classes of random variables. Classes of real-valued functions enjoying such a property are also known as uniform Glivenko-Cantelli classes. In this paper we prove, through a generalization of Sauer's lemma that may be interesting in its own right, a new characterization of uniform Glivenko-Cantelli classes. Our characterization yields Dudley, Gine, and Zinn's previous characterization as a corollary. Furthermore, it is the first based on a simple combinatorial quantity generalizing the Vapnik-Chervonenkis dimension. We apply this result to characterize PAC learnability in the statistical regression framework of probabilistic concepts, solving an open problem posed by Kearns and Schapire. Our characterization shows that the accuracy parameter plays a crucial role in determining the effective complexity of the learner's hypothesis class.

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

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

M3 - Conference contribution

AN - SCOPUS:0027802035

SN - 0818643706

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

SP - 292

EP - 301

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

A2 - Anon, null

PB - Publ by IEEE

T2 - Proceedings of the 34th Annual Symposium on Foundations of Computer Science

Y2 - 3 November 1993 through 5 November 1993

ER -