Intelligent Information Gathering and Submodular Function Optimization

Description

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.

Materials

Outline

  1. Introduction
    • Motivating Applications
    • Why should the AI community care about submodularity?
  2. Submodular set functions
    • Definitions
    • Intuition: Why are submodular functions useful
    • Examples of submodular functions (entropy [8] and mutual information [10, 14], influence in graphs [9], etc.) and examples of functions which are not submodular
    • Operations preserving submodularity and relationship between submodularity and convexity [16]
  3. Minimizing submodular functions
    • Overview about known results for minimization [22, 7]
    • Queyranne’s algorithm for minimizing symmetric submodular functions [22], applications to factorizing distributions and clustering [20]
    • Learning structure of graphical models [19, 1]
  4. Maximizing submodular functions
    • The Greedy algorithm [21,32]
    • Lazy evaluations and scaling up to large data sets [28]
    • Applications of maximizing submodular functions
      • Informative path planning and multi-agent coordination [24]
      • Sensor placement and scheduling [39]
      • Information gathering in the presence of adversaries [13]
    • Online and stochastic optimization of submodular functions [5, 11]
  5. Conclusions
    • Current research directions / Open questions
    • Other pointers (submodularity in games / allocation problems [4,35])

Who should attend

The main objective of this tutorial is to introduce the concept of submodular function optimization and its emerging importance in solving complex AI problems. As a special focus, we illustrate the concept on a key AI task: Intelligent gathering of most relevant information, in a variety of complex real-world problems.
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..

Presenters

Andreas Krause is an assistant professor of Computer Science at the California Institute of Technology. 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) and the ASCE journal of Water Resource Planning and Management.

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.

References

The following references are used in the tutorial. A short high level summary is given, without any claim of completeness.
Last updated: June 9 2009