CSAIL Event Calendar: Previous Series

Fast Online Active Learning

Speaker: Claire Monteleoni , CSAIL, MIT
Date: May 9 2005
Time: 4:10PM to 5:00PM
Location: Star seminar room 32-D463
Contact: Louis-Philippe Morency, 617-253-4278, lmorency@csail.mit.edu
Relevant URL:

The online active learning problem is a realistic scenario, begging several interesting computational questions. Online or sequential learning is a framework in which training examples are received one at a time, and the learner must make a prediction at each time-step. The learner cannot store all previously seen examples and then apply a batch learning algorithm to them, but must instead intelligently summarize its observations. Additionally, the time complexity of the belief update step should be constrained against scaling with the number of past examples, in order for the algorithm to be effective in the online setting. Active learning is a situation in which the labels of the examples are missing, yet available at some cost. Beyond just minimizing the number of examples needed to learn a concept, the goal is to minimize the number of labels that the algorithm needs to check, in doing so. In fact, intelligent choices of which examples to label can even reduce the total number of examples needed for learning.

In this talk I will present an algorithm that performs fast online active learning: it uses at most O~(d log 1/e) labels to learn half-spaces in d dimensions to generalization error e. Such a guarantee previously existed only for an algorithm whose belief update step scaled polynomially with the number of past mistakes, violating the online constraint described above. For algorithms that obey this constraint, we are only aware of upper bounds of O~(d/e^2) mistakes. I will then present a lower bound of Omega~(1/e^2) labels, for standard Perceptron using any active learning rule. I will also discuss our analysis techniques, which interestingly also bound our algorithm's total errors (labeled and unlabeled) by O~(d log 1/e).

This is joint work with Sanjoy Dasgupta (UCSD) and Adam Tauman Kalai (TTI-Chicago).

See other events that are part of CSAIL Student Seminar Series Spring 2005

See other events happening in May 2005


About Us Research News Resources Directory