Instructor: Rocco Servedio
||Computational Learning Theory
Class Manager: Andrew Wan
The question "Can machines learn from experience?" is one that has fascinated
people for a long time. Over the past few decades, many researchers in computer science
have studied this question from a range of applied and theoretical perspectives. This
course will give an introductiion to some of the central topics in computation learing theory.
We will study well-defined mathematical models of learning in which it is possible to give precise
and rigorous analyses of learning problems and learning algorithms. A big focus of the course
will be the computational efficiencey of learning in these models. We'll develop
computationally efficient algorithms for certain learning problems, and will show why
efficient algorithms are not likely to exist for other problems.
LIST OF TOPICS
This is a preliminary list of "core" topics. Other topics may be covered as well
depending on how the semester progresses. Some topics will take more than one lecture.
- Introduction: what is computational learning theory (and why)?
- The online mistake-bound learning model. Online algorithms for simple concept
- General algorithms for online learning. Lower bounds for online learning.
- The Probably Approximately Correct (PAC) learning model: definition and examples.
Online to PAC conversions.
- Occam's Razor: learning by finding a consistent hypothesis.
- The VC dimension and uniform convergence.
- Weak versus strong learning: boosting algorithms.
- Hardness results for efficient learning based on cryptography.
- PAC learning for noisy data. Malicious noise and classificatioin noise.
Learning from Statistical Queries.
- Exact learning from membership and equivalence queries. Learning monotone
DNF and learning finite automata.
You should be familiar with the following topics.
- Big-O notation and basic analysis of algorithms. Chapter 3 in "Introduction
to Algorithms" by Cormen, Leiserson, Rivest and Stein is more than sufficient.
- Basic discrete math and probability. The course CS3202 and the
"Mathematical Background" section (Appendix VIII) of CLRS are good sources
- Basic knowledge of finite automata. Chapter 1 of Sipser's book "Introduction
to the Theory of Computation," or the coverage of finite automata in CS326,
is more than sufficient.
- Most importantly, you should be comfortable with reading and writing
proofs. Chapter 0 of Sipser's book "Introduction to the Theory of Computation"
is a good source here.