Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Scale-sensitive dimensions, uniform convergence, and learnability
Alon N., Ben-David S., Cesa-Bianchi N., Haussler D. Journal of the ACM44 (4):615-631,1997.Type:Article
Date Reviewed: Oct 1 1998

Inspired by Valiant’s PAC learning model, the authors, using discretization techniques, seek a convergence of distribution-free expectations over classes of random variables. Real-valued functions (such as Glivenko-Cantelli classes) thus acquire a new uniformity. The model pioneers a simple combinatorial quantity generalized from the Vapnik-Chervonenkis dimension and implies learnability as a function of statistical regression. With learnability thus construed as probability, the accuracy parameter determines the complexity of the learner’s hypothesis class. Yet, can the authors’ refinements of quantitative elegance be transposed to pragmatic demonstrations?

Reviewer:  R. L. Frautschi Review #: CR121315 (9810-0841)
Bookmark and Share
 
Concept Learning (I.2.6 ... )
 
Would you recommend this review?
yes
no
Other reviews under "Concept Learning": Date
Parallelism and programming in classifier systems
Forrest S. (ed), Morgan Kaufmann Publishers Inc., San Francisco, CA, 1991. Type: Book (9780273088257)
Sep 1 1991
Learning structures of visual patterns from single instances
Suganuma Y. Artificial Intelligence 50(1): 1-36, 1991. Type: Article
Apr 1 1992
Learning simple concepts under simple distributions
Li M. (ed), Vitányi P. SIAM Journal on Computing 20(5): 911-935, 1991. Type: Article
Jul 1 1993
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy