Submodularity in Machine Learning and Computer Vision

Description

Many problems in machine learning and computer vision are inherently discrete, and the resulting optimization problems can become computationally very challenging. While convexity is an important property when solving continuous optimization problems, submodularity is closely tied to the tractability of many discrete problems. Even more, the characterizing property of submodular functions, diminishing marginal returns, emerges naturally in various settings and is a rich abstraction for a myriad of problems. Long recognized for its importance in combinatorial optimization and game theory, submodularity is now emerging in an increasing number of applications in machine learning and computer vision.

This tutorial introduces researchers to the concept of submodular functions, their optimization, applications and relevant results in recent research directions. Illustrative examples and animations will help develop an intuition for the concept and algorithms. The tutorial aims at providing an overview of existing results that are important to machine learners, and will provide pointers to further, detailed resources.

Materials


Presenters

Andreas Krause is an Assistant Professor of Computer Science (tenure-track) at ETH Zurich, where he leads the Learning & Adaptive Systems Group. He received his Ph.D. and M.Sc. in Computer Science from Carnegie Mellon University (2008) and his Diplom in Computer Science and Mathematics from the Technical University of Munich, Germany (2004). He is a Microsoft Research Faculty Fellow (2012), a Kavli Frontiers Fellow of the US National Academy of Sciences, and received an NSF CAREER award and the Okawa Foundation Research Grant recognizing top young researchers in telecommunications. His research in learning and adaptive systems that actively acquire information, reason and make decisions in large, distributed and uncertain domains, such as sensor networks and the Web received awards at several premier conferences (AAAI, KDD, IPSN, ICML, UAI) and journals (JAIR, JWRPM).

Stefanie Jegelka is a postdoctoral researcher at UC Berkeley. Before that, she pursued a Ph.D. at the Max Planck Institute for Intelligent Systems in Tuebingen, Germany, and received her Ph.D. from ETH Zurich. During her studies at the University of Tuebingen and the University of Texas at Austin she was a scholar of the German National Academic Foundation (Studienstiftung des Deutschen Volkes). She has also received a fellowship from the Klee foundation and a Google Anita Borg Europe Scholarship. Her interests lie in combinatorial problems in Machine Learning, in particular submodularity, and include algorithms and complexity, and applications in particular in computer vision.

Last updated: August 2012