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.