EE Special Seminar

Abstract:

Learning from complex data such as images, text or biological measurements invariably relies on capturing latent structure. But the combinatorial structure inherent in real-world data can pose significant computational challenges for modeling, learning and inference, bringing for example traditionally used probabilistic graphical models to their limits.

In this talk, I will describe work towards overcoming these challenges. In particular, we employ the combinatorial concept of submodular set functions: considered a "discrete analog of convexity", these functions capture intuitive yet nontrivial dependencies between variables. Nonetheless, their efficient practical use requires care. As a concrete example, I will show how the combination of graphs and submodularity leads to a new class of models whose inference procedures are not only efficient but also enjoy provable approximation bounds. Specifically, while in its general form the inference problem is extremely hard, several practically relevant properties admit improved approximations or even exact solutions. These benefits are reflected in empirical results. Moreover, it turns out that the same properties similarly affect related optimization and learning problems.

Our observations enable the implementation of new priors on real data, such as a combinatorial sparsity prior that significantly improves image segmentation results in settings where state-of-the-art methods fail. I will use this example to illustrate theoretical and empirical results, and will place them in a broader context within and beyond machine learning.

Bio:

Stefanie Jegelka is a postdoctoral researcher at UC Berkeley, supervised by Michael I. Jordan and Trevor Darrell. She received a Ph.D. in Computer Science from ETH Zurich in 2012, in collaboration with the Max Planck Institute for Intelligent Systems. She completed her studies for a Diploma in Bioinformatics with distinction at the University of Tuebingen (Germany) and the University of Texas at Austin. She was a fellow of the German National Academic Foundation (Studienstiftung) and its scientific college for life sciences, and has received a Google Anita Borg Europe Fellowship and an ICML Best Paper Award. She has also been a research visitor at Georgetown University Medical Center and Microsoft Research and has held tutorials and workshops on submodularity in machine learning.