- Instructor: Avrim Blum
- Time: TR 3:00-4:20
- Place: We've moved to
**Wean 4623**

**Text:**
*
An Introduction to Computational Learning Theory* by Michael Kearns
and Umesh Vazirani, plus papers and notes for topics not in the book.

**Office hours:** Just stop by my office or make an appointment.

The graded finals are now available in Dorothy's office (Wean 4116). Feel free to stop by and pick yours up.

- General Course Information
- Homework 1. Solutions.
- Homework 2. Solutions.
- Homework 3. Solutions.
*Oops:*Question 1 is a real pain to prove. Please ignore it. - Homework 4. Solutions.
- Homework 4.5.
- Homework 5. Solutions.
- Homework 6. Solutions.
- Homework 7. Solutions.
- Information on presentations and projects

- 01/15: Introduction, basic definitions, the consistency model.
- 01/17: The Mistake-bound model, relation to consistency, halving and Std Opt algorithms.
- 01/22: The weighted majority algorithm & applications.
- 01/24: The Perceptron and Winnow algorithms.
- 01/29: Intro to PAC model, Occam's razor.
- 01/31: Chernoff/Hoeffding bounds, MB->PAC. See also this handout on probabilistic inequalities.
- 02/05: Slides and Notes: finish MB->PAC, VC-dimension.
- 02/07: Today we will go to John Langford's thesis defense in NSH 3305.
- 02/12: VC-dimension: the proofs. Slides and Notes.
- 02/14: Boosting I: weak vs strong learning, Schapire's original method.
- 02/19: Boosting II: Adaboost.
- 02/21: Learning from random classification noise. The Statistical Query model.
- 02/26: Learning with noise and SQ model contd. Begin Fourier analysis. Notes and Slides.
- 02/28: Characterizing SQ learnability with Fourier analysis, contd (see notes from last time). One more SQ algorithm.
- 03/05: Membership queries: some basic algorithms (monotone DNF, log-n var functions); KM/GL alg for finding large fourier coeffs.
- 03/12: Membership queries II: finish KM/GL. Bshouty's alg for learning XOR of terms (and DTs).
- 03/14: Finish Bshouty's algorithm. Cryptographic hardness results for learning.
- 03/19: Finish crypto hardness. Angluin's algorithm for learning finite state automata. Notes, slides, more notes.
- 03/21: Learning finite state environments without a reset. Notes, and slides.
- 03/26: Maximum likelihood, EM, and hidden Markov models. Notes, slides, and more slides.
- 03/28: Strong-learning DNF over the uniform distribution [presentation by Shuchi and Nikhil]
- 04/09: Learning monotone boolean functions. Notes, and a paper.
- 04/11: Kedar Dhamdhere: random projection
- 04/16: Umut Acar: boosting and hard-core set construction.
- 04/18: Maximum entropy learning, connection to maximum likelihood and Winnow.
- 04/23: John Langford: PAC-Bayes bounds
- 04/25: Allison Bruce and Benoit Hudson: Q-learning
- 04/30: Si Luo / Rong Jin
- 05/02: TBD

- Nick Littlestone, Learning Quickly
when Irrelevant Attributes Abound: A New Linear-threshold Algorithm.
*Machine Learning*2:285--318, 1987. (The version pointed to here is the tech report UCSC-CRL-87-28.) This is the paper that first defined the Mistake-bound model, and also introduced the Winnow algorithm. A great paper. - Littlestone and Warmuth, The Weighted Majority Algorithm.
*Information and Computation*108(2):212-261, 1994. (The version pointed to here is the tech report UCSC-CRL-91-28.) Introduces the weighted majority algorithm, along with a number of variants. Also a great paper. - Nicoḷ Cesa-Bianchi, Yoav Freund, David Haussler, David
P. Helmbold, Robert E. Schapire, and Manfred K. Warmuth. How
to use expert advice. Journal of the ACM, 44(3):427-485, May 1997.
Continuing on with line of research in the [LW] paper, this gives
tighter analyses of multiplicative-weighting expert algorithms and
addresses a number of issues.
BTW, for fun, here is the Mindreading program of Rob Schapire and Yoav Freund compiled for sparc or linux (note: you need to hit ctrl-D to quit).

- Avrim Blum, "On-Line
Algorithms in Machine Learning" (a survey).
- David Haussler Chapter on PAC learning model, and decision-theoretic generalizations, with applications to neural nets. From Mathematical
Perspectives on Neural Networks, Lawrence Erlbaum Associates, 1995, containing reprinted material from "Decision Theoretic
Generalizations of the PAC Model for Neural Net and Other Learning Applications", Information and Computation, Vol. 100,
September, 1992, pp. 78-150. This is a really nice survey of the PAC
model and various sample-complexity results.
- Papers on Adaboost.
- The original paper: Yoav Freund and Rob Schapire, A decision-theoretic generalization of on-line learning and an application to boosting, Journal of Computer and System Sciences, 55(1):119-139, 1997.
- A recent overview by Rob Schapire: The boosting approach to machine learning: An overview. In MSRI Workshop on Nonlinear Estimation and Classification, 2002.

- Avrim Blum, Merrick Furst, Jeffrey Jackson, Michael Kearns, Yishay Mansour, and Steven Rudich, Weakly Learning DNF and Characterizing Statistical Query Learning Using Fourier Analysis., STOC '94 pp. 253--262.
- Web sites on maxent: