CS4252: | Introduction to |

Computational Learning Theory | |

Summer 2005 |

Class Manager: Andrew Wan

Email: atw12@columbia.edu

CONTENTS

- Announcements,Reading and Homework
- Overview and Prerequisites
- Grading and Requirements
- Schedule of Lectures

LECTURES

- Lecture 1 Introduction to machine learning theory. Learning models and learning problems.
- Lecture 2 Online mistake bound learning. Algorithms for simple concept classes. Attribute efficient learning with the Winnow algorithm.
- Lecture 3 Winnow algorithm continued. Perceptron algorithm. General bounds for online mistake bound learning. The Halving algorithm, the Standard Optimal Algorithm.
- Lecture 4 Best Experts and Weighted Majority.
- Lecture 5 Weighted Majority algorithm continued.
- Lecture 6 The Probably Approximately Correct(PAC) Learning model. PAC learning algorithms for simple concept classes.
- Lecture 7 More PAC learning algorithms. Conversions from online learning to PAC learning.(KV chapter 1)
- Lecture 8 Occam's Razor: learning by finding consistent hypotheses. Applications(KV chapter 2).
- Lecture 9 Computational hardness results for finding consistent hypotheses.
- Lecture 10 Vapnik-Chervonenkis dimension. Upper and lower bounds on sample complexity(KV chapter 3).
- Lecture 11 VC dimension and sample compelxity continued.
- Lecture 12 VC dimension and sample compelxity continued.
- Lecture 13 Weak learning, strong learning, and Boosting(KV chapter 4).
- Lecture 14 Boosting continued.
- Lecture 15 Boosting continued.
- Lecture 16 Cryptographic limitations on efficient learning(KV chapter 6).
- Lecture 17 Cryptographic limitations on learning continued. Reducability in PAC
- Lecture 18 learning(KV chapters 6,7).
- Lecture 19 Learning in the presence of noise. Classification noise, malicious noice,
- Lecture 20 Statistical Query learning (KV chapter 5).
- Lecture 21 Learning with noise continued.
- Lecture 22 Learning with noise continued.
- Lecture 23 The model of exact learning from membership and equivalence queries. Learning monotone DNF formulas.
- Lecture 24 Learning deterministic finite automata.
- Lecture 25 Learning deterministic finite automata continued.
- Lecture 26 Learning deterministic finite automata continued.