Colloquia

Efficient Algorithms for Active Learning

Claire Monteleoni
Department of Computer Science and Engineering
University of California, San Diego

Wednesday, April 2nd, 2008
Troy 2018 - 11:00 a.m. to 12:00 p.m.
Refreshments at 10:30 a.m.

Abstract:

The rapidly increasing abundance of data generated by internet transactions, satellite measurements, and environmental sensors, among other sources, creates new and urgent challenges for machine learning. My work on machine learning theory and algorithms is motivated by the problems posed by real-world data. This talk will focus on providing efficient algorithms for active learning, a rich model for learning when labels are missing.

In many data-rich problems, unlabeled data is much easier to obtain than labeled data (e.g. images on the web, unlabeled speech or video signal). An active learner receives unlabeled data and can make intelligent choices about which labels to request via some mechanism, for example by paying for annotation by a human. Active learning is useful in many practical applications, such as spam filtering, however most previous algorithms either lack formal performance guarantees, or are computationally prohibitive. First I will present an algorithm that, for uniformly distributed, linearly separable data, needs exponentially fewer labels than the analogous sample complexity of supervised learning. Our algorithm is extremely light-weight and easy to implement, and respects online constraints on time and memory. Then I will discuss our recent work on generalizing active learning to arbitrary data distributions and hypothesis classes, with no separability assumption. We provide an algorithm for general active learning via reduction, which is as efficient (up to polylogarithmic factors) as the supervised learning algorithm for the problem.

I will also mention other projects, including learning with online constraints, privacy-preserving machine learning, applications to networks and vision, and climate informatics.

Bio:

Claire Monteleoni is currently a postdoc in Computer Science and Engineering, at the University of California, San Diego. Her research focuses on machine learning theory and algorithms, motivated by practical applications. She completed her Ph.D. in 2006, and her Masters in 2003, in Computer Science, at MIT. She did her undergraduate work at Harvard, and grew up in New York City.

Hosted by: Boleslaw Szymanski (x2714)

Administrative support: Sharon Simmons (x8291)

For more information:

See Doctor Monteleoni's web page

Last updated: September 7, 2005