- SAP Module of Computational Learning:
- Presentation (10-11, Friday Nov. 11th, S2-217 Omega building)
- Online learning (10-12, Friday Nov. 18th, S2-217 Omega building)
- Material covered:
- Definition of Online Learning (aka Mistake Bound model)
- Learning Boolean conjunctions and disjunctions with the Elimination algorithm
- Attribute-efficient learning with Winnow
- The Perceptron algorithm
- Bibliographic notes:
- Most of the lecure was based on Roni Khardon's notes on online learning
- Winnow's algorithm for attribute-efficient learning was introduced in this Littlestone's paper
- You can find information on the perceptron on this Freund and Schapire's paper. In particular, there is a short proof of perceptron's mistake bound for the separable case (which is what we covered) on pages 4-5 (proof of their Theorem 1).
- Query learning (10-12, Friday Nov. 25th, S2-217 Omega building)
- Material covered:
- Definition of Query Learning using Membership and Equivalence queries
- Learning monotone conjunctions with EQs
- Learning monotone conjunctions with MQs
- Learning monotone DNFs with EQs + MQs
- Learning Horn CNFs
- Bibliographic notes:
- The algorithm for monotone DNFs has been explained in several classical papers, for example, Valiant's A theory of the learnable or Angluin's Queries and concept learning.
- The algorithm for Horn CNF is a classic result by Angluin et al. Learning conjunctions of Horn clauses.
- PAC learning I (10-12, Friday Dec. 2nd, S2-217 Omega building)
- Material covered:
- Definition of PAC algorithms and PAC learning
- Consistent learning for finite classes
- PAC-learning rectangles
- Bibliographic notes:
- Valiant's paper A theory of the learnable introduced the model and gave the first bounds.
- Much of what we did today is covered in the first chapter of the book An Introduction to Computational Learning Theory by Michael Kearns and Umesh Vazirani; the book is partially avaiable from Google Books.
- PAC learning II and VC Dimension (10-12, Friday Dec. 16th, S2-217 Omega building)
- Material covered:
- Consistent learning for infinite classes with finite VC Dimension
- PAC learning rectangles
- Definition of VC Dimension and examples: intervals on the real line, union of k intervals on the real line, rectangles, Boolean conjunctions
- Bibliographic notes:
- Much of what we did today is covered in the third chapter of the book An Introduction to Computational Learning Theory by Michael Kearns and Umesh Vazirani; the book is partially avaiable from Google Books.