MP4

Intelligent Information Gathering and Submodular Function Optimization
Andreas Krause and Carlos Guestrin

A key problem in AI is to develop intelligent systems and services that actively gather most relevant information. In recent years, a fundamental problem structure has emerged as extremely useful for addressing this problem: Submodularity is an intuitive diminishing returns property, stating that adding an element to a smaller set helps more than adding it to a larger set. Applications where this property is useful include active learning and experimental design, informative path planning, multi-agent coordination, structure learning, clustering, influence maximization, weblog ranking, trading off utility and privacy as well as game theoretic applications. In contrast to most existing approaches, submodularity allows to efficiently find provably near-optimal solutions.

In this tutorial, we will give an introduction to the concept of submodularity, discuss algorithms for optimizing submodular functions and illustrate their usefulness in solving difficult AI problems, with a special focus on active information gathering tasks. Since submodularity arises in so many different areas of AI, and since information gathering is central to many AI applications, we believe that this property is both of theoretical and practical interest to a large part of the AI community. This tutorial will not require prior knowledge beyond the basic concepts covered in an introductory AI class.

Andreas Krause is an Assistant Professor in Computer Science at Caltech. He received his Ph.D. from Carnegie Mellon University in 2008. He is a recipient of a Microsoft Research Graduate Fellowship, and his research on sensor placement and information acquisition received awards at several major conferences (KDD '07, IPSN '06, ICML '05 and UAI '05).

Carlos Guestrin is the Finmeccanica Assistant Professor in the Machine Learning and Computer Science Departments at Carnegie Mellon University. Previously, he was a senior researcher at Intel, and received his PhD from Stanford University. Carlos' work received awards at a number of major conferences and a journal. He is also a recipient of the ONR Young Investigator Award, the NSF Career Award, the Alfred P. Sloan Fellowship, the IBM Faculty Fellowship, and was named one of the 2008 Brilliant 10 by Popular Science Magazine. Carlos is currently a member of the Information Sciences and Technology (ISAT) advisory group for DARPA.

(back)