Efficient learning with combinatorial structure

Speaker: Stefanie Jegelka , University of California - Berkeley

Date: Thursday, April 10, 2014

Time: 3:00 PM to 4:00 PM Note: all times are in the Eastern Time Zone

Refreshments: 2:45 PM

Public: Yes

Location: 34-401A

Event Type:

Room Description:

Host: Tommi Jaakkola, CSAIL

Contact: Francis Doughty, 253-4602, francisd@csail.mit.edu

Relevant URL:

Speaker URL: None

Speaker Photo:
None

Reminders to: seminars@csail.mit.edu

Reminder Subject: TALK: Efficient learning with combinatorial structure

Learning from complex data such as images, text or biological measurements invariably relies on capturing long-range, latent structure. But the combinatorial structure inherent in real-world data can pose significant computational challenges for modeling, learning and inference.

In this talk, I will view these challenges through the lens of submodular set functions. Considered a "discrete analog of convexity", the combinatorial concept of submodularity captures intuitive yet nontrivial dependencies between variables and underlies many widely used concepts in machine learning. Practical use of submodularity, however, requires care. My first example illustrates how to efficiently handle the important class of submodular composite models. The second example combines submodularity and graphs for a new family of combinatorial models that express long-range interactions while still admitting very efficient inference procedures. As a concrete application, our results enable effective realization of combinatorial sparsity priors on real data, significantly improving image segmentation results in settings where state-of-the-art methods fail.

Motivated by good empirical results, we provide a detailed theoretical analysis and identify practically relevant properties that affect complexity and approximation quality of submodular optimization and learning problems.

Biography:
Stefanie Jegelka is a postdoctoral researcher at UC Berkeley. She received a Ph.D. from ETH Zurich in collaboration with the Max Planck Institute for Intelligent Systems, and a Diploma in Bioinformatics from the University of Tuebingen, Germany. She has received several fellowships, including one by the German National Academic Foundation, and an ICML 2013 Best Paper Award. Her research interests lie in algorithmic machine learning.

Research Areas:

Impact Areas:

See other events that are part of the CS Special Seminar Series 2014.

Created by Francis Doughty at Friday, March 14, 2014 at 9:19 PM.