Lecture 09:
Sayan Mukherjee
Description
Necessary and sufficient requirements for uniform convergence
for both real-valued loss functions and classification are introduced.
VC entropy, VC dimension, empirical covering numbers, and V-gamma
dimension are introduced and explained.
Slides
Slides for this lecture: PS,PDF
Suggested Reading
- N. Alon, S. Ben-David, N. Cesa-Bianchi, and D. Haussler Scale-sensitive Dimensions, Uniform Convergence, and Learnability.Journal of the ACM, 44(4):615-631, 1997.
- V. N. Vapnik. The Nature of Statistical Learning Theory. Springer,
1995.
- Cucker and Smale. On the mathematical foundations of learning. Bulletin of the American Mathematical Society, 2002.
- V. N. Vapnik and A. Ya. Chervonenkis. Necessary and Sufficient conditions for the uniform convergence of the means to their expectations. Probability Theory and Its Applications,26, 532-553 1981.