CS4252: | Introduction to |

Computational Learning Theory | |

Summer 2005 |

Class Manager: Andrew Wan

Email: atw12@columbia.edu

CONTENTS

- Announcements,Reading and Homework
- Overview and Prerequisites
- Grading and Requirements
- Schedule of Lectures

INTRODUCTION

The question "Can machines learn from experience?" is one that has fascinated people for a long time. Over the past few decades, many researchers in computer science have studied this question from a range of applied and theoretical perspectives. This course will give an introductiion to some of the central topics in computation learing theory. We will study well-defined mathematical models of learning in which it is possible to give precise and rigorous analyses of learning problems and learning algorithms. A big focus of the course will be the computational efficiencey of learning in these models. We'll develop computationally efficient algorithms for certain learning problems, and will show why efficient algorithms are not likely to exist for other problems.

LIST OF TOPICS

This is a preliminary list of "core" topics. Other topics may be covered as well depending on how the semester progresses. Some topics will take more than one lecture.

- Introduction: what is computational learning theory (and why)?
- The online mistake-bound learning model. Online algorithms for simple concept classes.
- General algorithms for online learning. Lower bounds for online learning.
- The Probably Approximately Correct (PAC) learning model: definition and examples. Online to PAC conversions.
- Occam's Razor: learning by finding a consistent hypothesis.
- The VC dimension and uniform convergence.
- Weak versus strong learning: boosting algorithms.
- Hardness results for efficient learning based on cryptography.
- PAC learning for noisy data. Malicious noise and classificatioin noise. Learning from Statistical Queries.
- Exact learning from membership and equivalence queries. Learning monotone DNF and learning finite automata.

PREREQUISITES

You should be familiar with the following topics.

- Big-O notation and basic analysis of algorithms. Chapter 3 in "Introduction to Algorithms" by Cormen, Leiserson, Rivest and Stein is more than sufficient.
- Basic discrete math and probability. The course CS3202 and the "Mathematical Background" section (Appendix VIII) of CLRS are good sources here.
- Basic knowledge of finite automata. Chapter 1 of Sipser's book "Introduction to the Theory of Computation," or the coverage of finite automata in CS326, is more than sufficient.
- Most importantly, you should be comfortable with reading and writing proofs. Chapter 0 of Sipser's book "Introduction to the Theory of Computation" is a good source here.