The first part of the course will be dedicated to PAC learning Boolean functions under an arbitrary distribution. We will discuss applications of linear programming (and its variants) for learning halfspaces and polynomial-threshold functions, among other concepts. In addition we will discuss structural properties of Boolean functions related to polynomial representation.
The second part of the course will focus on learning Boolean functions with respect to the uniform distribution. Here the main topic will be discrete Fourier analysis and its applications. We will discuss learning decision trees and DNF formulas, and we will combine this approach with Boosting based methods to push the envelope of what we can learn.
The third part of the course will focus on query learning, including automata and multiplicity automata. Additional discussion topics include polynomial interpolation, random projection, and cryptographic based hardness results.
We will have student paper presentations; topics will be chosen according to student interest.
Introductory Lecture; Outline
Lecture 1, Introduction to the mistake bounded model. Learning decision lists and decision trees.
Lecture 2, Bshouty's algorithm for learning DNF.
Lecture 3, Polynomial Threshold Functions; Expressing DNFs as PTFs Part 1.
Lecture 4, Expressing DNFs as PTFs Part 2; Parity/MP PTF lower bound.
Lecture 5, Voting Polynomials.
Lecture 6, Learning Intersections of Halfspaces
Lecture 7, PTF lower bounds; Introduction to Margins
Lecture 8, JL Lemma and Application: Learning Halfspaces with a Margin
Lecture 9, Finishing Halfspaces w/ Margin; Learning Parity with Noise
Lecture 10, Hardness of Properly Learning ANDs of Halfspaces
Lecture 11, More Hardness results for Proper Learning
Lecture 12, Introduction to Fourier Analysis
Lecture 13, The Sparse Algorithm; Learning Decision Trees (KM)
Lecture 14, The Harmonic Sieve
Lecture 15, Learning Constant Depth Circuits (LMN)
(Coming Soon) Lecture 16, Noise Stability: Learning Intersections of Halfspaces
Lecture 17, Learning Constant Depth Circuits with MAJ gates
Lecture 18, Learning with Queries: Polynomial Interpolation
Lecture 19, Polynomial Interpolation Continued, Exact Learning DFAs
Lecture 20, Angluin's algorithm and applications
(Coming Soon) Lecture 21 Multiplicity Automata
Assignments will include scribe notes, a student paper presentation, and a (relatively short) problem set or two. Grades will be based on performance on these assignments and class participation.
Problem Set 1. Due March 3, 2005.
Solution to Problem Set 1.
Problem Set 2. Due April 28, 2005.
Solution to Problem Set 2.
Mathematical maturity is required. A course in algorithms or complexity is recommended. A prior course in computational learning theory provides more than enough background for this seminar. An Introduction to Computational Learning Theory by Kearns and Vazirani is a good reference book for topics to be covered here.