Introduction to Computational Learning Theory (First Semester 2004/5)

Instructors: Omer Reingold and Amir Shpilka
Teaching assistant: Ariel Gabizon

 

Thursday 10:00-12:00, Ziskind 1

 

Reminder:If you want to attend the seminar next semester please send Ariel an email so that we can get an estimate of the amount of people interested.

Learning Seminar

 

Revised course page

Exercises:

    Ex. 1-corrections made in questions 1(d) and 3 –you have a week extension till 2.12.04

    Ex. 2-minor corrections added-14.12.04 (Please write your ID number) –Please submit by 30.12.04

    Ex. 3-Please Submit on time.

    Ex. 4

Book(covers part of the course): An Introduction to Computational Learning Theory, by Michael Kearns and Umesh Vazirani

 

 Lecture Notes:

·         Avrim Blum

·         Rob Schapire

·         Yishay Mansour

·         Toni Pitassi

·         Tutorial by Avrim Blum

·         Sally Goldman

·         Ron Rivest

More Resources:

·        Nader Bshouty , www.learningtheory.org,  learningtheory.org/resources.html, Michael Kearns

Material Covered:

Here I will give references to the material covered in class, note that when I give reference to particular lecture notes the same material is probably covered in other lecture notes as well.

I will try to give references to specific pages with the material covered in class but a lot of times the pages before and after give more examples and explanations and might be helpful to look at.

General:

Basic Probability inequalities can be found at Mansour scribe 1, pages 12-13.

A formal definition of circuits can be  at page 6 of lecture 2 in Oded Goldreich's complexity lecture notes. The equivalent definition as a non-uniform turing machine is described in lecture 8 of these notes.

 

Specific lectures:

·        28/10: PAC Model(Schapire,2,3-4), Occam's Razor(Mansour,3,16-18), VC-Dimension(Mansour,6,2-7).

·        4/11: Occam algorithm for Conjunctions(Pittasi,4,1-2), VC-Dimension lower bound on learning(Mansour,7,5-6). 

·        11/11:VC-Dimension upper bound on learning+ sauer's lemma(Schapire,4-5,all pages),VC-dim of neural networks(Can be found in the book of Kears and Vazirani)

·        18/11: Review of last lessons, PacèConsistent learning,  Learning DNFè Solving 3-coloring (Goldman,3,1-4)

·        25/11: OWFàPRFàHardness of PAC learning circuits,  Survey of known results\open problems.

·        2-9/12: Boosting(Schapire,8-9)(The material in lecture 9 was covered very informally), See also Schapire's overview on boosting, Learning with errors(Blum,11,1-3).

·        23/12: Definition of SQ model, containment in PAC, SQ algorithm à learning with noise. The material can be found in the paper by Kearns.

·        30/12: Definition of SQ-Dimension, Using SQ-Dimension to get lower and upper bound on learning in SQ Model, Material appears in the paper Weakly Learning DNF and Characterizing Statistical Query Learning Using Fourier Analysis.

·        6/1: Learning using fourier analysis(Rivest, Lec. 21 and Lec. 22 pages 1-6). Material from the paper: Learning Decision trees using the fourier spectrum By Eyal Kushilevitz and Yishai Mansour

·        13/1: Learning Finite Automata with equivalence queries. Can be found in the book of Kearns and Vazirani.