## 15-850(C) Machine Learning Theory, Fall 1995

Instructor: Avrim Blum

When: Tuesday, Thursday 3:00--4:20
Where: Wean 5304
Here is a general description of the course.

### Lectures:

(Detailed scribe notes for topics not in the book, only rough notes
for topics in the book)
- Lecture 1: Overview, basic definitions, the
consistency model.
- 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
Algorithm.
- 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.

### Homework assignments:

### Other handouts:

### Other information: