15-854 MACHINE LEARNING THEORY
This course will focus on theoretical aspects of machine learning. We
will examine questions such as: What kinds of guarantees can one prove
about learning algorithms? What are good algorithms for achieving
certain types of goals? Can we devise models that are both amenable
to mathematical analysis and make sense empirically? What can we say
about the inherent ease or difficulty of learning problems?
Addressing these questions will require pulling in notions and ideas
from statistics, complexity theory, cryptography, and on-line
algorithms, and empirical machine learning research.
- Instructor: Avrim Blum
- Time: MW 1:30-2:50
- Place: Wean 4615A
- 12 Units, 1 CU
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.
Some ideas for presentations and projects.
- 01/12:Overview, basic definitions,
the consistency model
- 01/14:Consistency for simple
neural net is NP-hard. Intro to Mistake-Bound model
- 01/19:Decision lists, Halving alg, Std Opt,
- 01/21:The Weighted-Majority Algorithm, Randomized
- 01/26:Randomized WM contd, 2-player games,
the Winnow algorithm
- 01/28:Learning from string-valued features, intro
to PAC model
- 02/02:MB==>PAC, Occam's razor
- 02/04:Occam's razor cont, intro to VC-dim and C[m].
See also the slides.
- 02/09:VC-dim and splitting number: upper and
lower bound proofs.
- 02/11:Probabilistic inequalities and
proof of Chernoff, intro to weak-learning.
- 02/16:Weak and strong learning,
Adaboost. Here are
Yoav Freund's slides
- 02/18:Learning with noise.
- 02/23:The Statistical Query model.
- 02/25:Characterizing SQs with Fourier analysis.
- 03/04:Fourier analysis, intro to Memb queries,
- 03/09:Finding large Fourier coeffs,
Bshouty's alg for learning XOR of terms.
- 03/11:Learning deterministic finite-state environments. Text and Slides.
- 03/16:Learning finite-state environments
contd, Intro to HMMs.
- 03/18:HMMs and weak
learning of monotone functions.
- 03/30:Hardness results for learning based on
cryptography and vice versa.
- 04/01:Query-by-Committee [Kamal].
Paper by Freund et al.
- 04/06:Probabilistic concepts [Haiqin].
Paper by Kearns & Schaipre.
- 04/08:The EM algorithm [Dimitris].
Paper by Xu and Jordan.
- 04/13:VC-dimension and "margins" [Goran].
Paper by Schapire et al.
- 04/15:Bias and variance [Chuck].
- 04/20:Piecemeal exploration [Michael].
- 04/22:Intro to Reinforcement Learning [Jovan].
- 04/27:Combining Reinforcement Learning with
function approximation [Bryan]. Papers by Geoff Gordon: 1,
- 04/29:Projects [Paul, Jason, John].
(Related papers that go into more detail on topics discussed in class)