MIT Thesis Defense: Learning with Online Constraints: Shifting Concepts and Active Learning

Speaker: Claire Monteleoni , MIT CSAIL
Date: Friday, August 11 2006
Time: 2:00PM to 3:00PM
Host: Tommi Jaakkola, MIT CSAIL
Contact: Claire Monteleoni, cmontel@csail.mit.edu
Relevant URL: http://people.csail.mit.edu/cmontel

Many practical problems such as forecasting, real-time decision making, streaming data applications, and resource-constrained learning, can be modeled as learning with online constraints. This thesis is concerned with analyzing and designing algorithms for learning under the following online constraints: 1) The algorithm has only sequential, or one-at-time, access to data. 2) The time and space complexity of the algorithm must not scale with the number of observations. We analyze learning with online constraints in a variety of settings, including active learning. The active learning model is applicable in any domain in which unlabeled data is easy to come by and there exists a (potentially difficult or expensive) mechanism by which to attain labels.

We present the following algorithms, performance guarantees, and applications for learning with online constraints. In a supervised learning framework in which observations are assumed to be iid, we lower bound the mistake-complexity of Perceptron, a standard online learning algorithm, and then provide a modified update that avoids this lower bound, attaining the optimal mistake-complexity for the problem in question. In an analogous active learning framework, our lower bound applies to the label-complexity of Perceptron paired with any active learning rule. We provide a new online active learning algorithm that avoids this lower bound, and we upper bound its label-complexity. The upper bound is optimal and also bounds the algorithm's total errors (labeled and unlabeled). We analyze the algorithm further, yielding a label-complexity bound under relaxed assumptions, and we perform an empirical evaluation on problems in optical character recognition. Finally, in a supervised learning framework involving no statistical assumptions on the observation sequence, we provide a lower bound on regret for a class of shifting algorithms. We apply an algorithm we provided in previous work, that avoids this lower bound, to an energy-management problem in wireless networks, and demonstrate this application in a network simulation.

Thesis Committee:
Tommi Jaakkola, MIT CSAIL (Thesis Supervisor)
Piotr Indyk, MIT CSAIL
Sanjoy Dasgupta, UC San Diego