CIS 625 Computational Learning Theory
Michael Kearns
Monday noon-3
Prerequisites: prior courses in algorithms, complexity and statistics would be helpful but are not necessary.
This course is an introduction to Computational Learning Theory, a field which attempts to provide algorithmic, complexity-theoretic and statistical foundations to modern machine learning. The focus is on topics in computational learning theory for researchers and students in artificial intelligence, neural networks, theoretical computer science, and statistics.
Course Goals:
The course will give a broad overview of the kinds of problems and techniques typically studied in Computational Learning Theory, and
provide a basic arsenal of powerful mathematical tools for analyzing machine learning problems. The first part of the course will closely
follow portions of An Introduction to Computational Learning Theory, by M. Kearns and U. Vazirani (MIT Press). We will cover perhaps 6 or 7 of
the chapters in K&V over (approximately) the first half of the course, often supplementing with additional readings and materials. The second
portion of the course will focus on a number of more recent but still fundamental topics in learning theory not covered in K&V. The topics
covered include the motivation, definitions, and fundamental results, both positive and negative, for the widely studied L. G. Valiant model
of Probably Approximately Correct Learning; Occam's Razor, which formalizes a relationship between learning and data compression; the
Vapnik-Chervonenkis dimension; the equivalence of weak and strong learning; efficient learning in the presence of noise by the method of
statistical queries; relationships between learning and cryptography, and the resulting computational limitations on efficient learning; reducibility between learning problems; and algorithms for learning finite automata from active experimentation.
Topics Covered:
• Basics of the Probably Approximately Correct (PAC) Learning Model
• Occam's Razor, Compression and Learning
• Uniform Convergence and the Vapnik-Chervonenkis Dimension
• Learning in the Presence of Noise and Statistical Query Learning
• Learning and Cryptography
• Query Models
• Boosting
• Online and No-Regret Learning
• Discrete Fourier Methods in Learning
• Active Learning
• Agnostic Learning
• PAC-style Analyses in Reinforcement Learning
• PAC-style Analyses in Probabilistic Inference
Textbook: An Introduction to Computational Learning Theory, Michael J. Kearns and Umesh V. Vazirani, MIT Press
More info @ www.cis.upenn.edu/~mkearns/teaching/COLT/ |
