Where: Wean 5304
Here is a general description of the course.
(Detailed scribe notes for topics not in the book, only rough notes
for topics in the book)
- Lecture 1: Overview, basic definitions, the
- Lecture 2: The PAC model.
- Lecture 3: Relating PAC and consistency,
decision lists, Occam's razor. Also, slides.
- Lecture 4: Occam's razor contd, tail
inequalities, uniform convergence.
- Lecture 5: The Mistake bound model, general
transformations, infinite-attribute learning.
- Lecture 6: On-line learning as a
2-person game, the Perceptron
- Lecture 7: The Winnow Algorithm,
comparison to Greedy Set-Cover.
- Lecture 8: Inconsistent data in
mistake-bound learning, (randomized) weighted-majority.
- Lecture 9: PAC learning with classification noise, Statistical Queries.
- Lecture 10: More on SQ model, intro to Fourier.
- Lecture 11: Fourier analysis, lower bounds for SQ learning.
- Lecture 12: VC-dimension. notes, slides.
- Lecture 13: VC-dimension, contd. notes.
- Lecture 14: Weak and Strong Learning.
- Lectures 15 and 16: Membership
Queries: basic results, Bshouty's algorithm.
- Lecture 17: Learning Deterministic Finite State Environments in State-Space Representation.
- Lecture 18: Learning DFAs contd.
- Lecture 19: Fourier Analysis learning, the KM algorithm.
- Lecture 20: More on learning with Fourier Analysis.
- Lecture 21: Relationships between Learning and Cryptography.