** DESCRIPTION: **
The general area of machine learning is a melting pot of ideas from a
wide variety of disciplines. This course will focus on the
theoretical side of machine learning. We will address questions such
as: What kinds of guarantees can one prove about learning algorithms?
What could one hope to prove? What are good models that are both
amenable to mathematical analysis and make sense empirically? Can we
use these models to come up with improved algorithms? 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,
as well as empirical machine learning and neural network research.

Specific topics to be covered include:

- Mistake-bound and PAC learning models: basic algorithms and hardness results
- Multiplicative linear threshold algorithms: Winnow, weighted majority, and others
- Focusing on relevant information, and related issues
- Occam's razor and the VC dimension. What do these results really mean?
- Dealing with noise; the Statistical Query model
- relationships with cryptography
- Active learning: guarantees for learning decision trees and learning finite automata
- Boosting weak learners
- Fourier analysis methods

PREREQUISITES:
Ideally students should either have an algorithms background with an
interest in how those tools can be applied to a new domain, or should
have a machine learning background with an interest in finding out the
theoretical tools and ideas that have been developed. No specific
courses are *required*. The algorithms core or 15-681(A) would be
* sufficient*.