CS4252: Computational Learning Theory

CS4252:	Introduction to
	Computational Learning Theory
	Summer 2005

Instructor: Rocco Servedio
Class Manager: Andrew Wan
Email: atw12@columbia.edu

CONTENTS

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.