Inference and Learning with Probabilistic Submodular Models

Speaker: Andreas Krause
Affiliation: ETH Zurich

Abstract: In recent years, submodular optimization has found many new applications, such as in machine learning and data mining. These include active learning, dictionary learning, data summarization, influence maximization and network structure inference. In this talk, I will present our recent work on quantifying uncertainty in submodular optimization. In particular, we carry out the first systematic investigation of inference and learning in probabilistic submodular models (PSMs). These are probabilistic models defined through submodular functions — log-sub/supermodular distributions — generalizing regular binary Markov Random Fields and Determinantal Point Processes. They express natural notions such as attractiveness and repulsion and allow to capture richly parameterized, long-range, high-order dependencies among the variables. I will present our recently discovered variational approach towards inference in general PSMs based on sub- and supergradients. Our approximation is exact at the mode (for log-supermodular distributions), and we provide bounds on the approximation quality of the log-partition function with respect to the curvature of the function. Exploiting additive structure in the objective leads to highly scalable, parallelizable message passing algorithms. We empirically demonstrate the accuracy of our inference scheme on several PSMs arising in computer vision and network analysis. I will also discuss some very recent work on learning PSMs from data.

Biography: Andreas Krause is an Associate Professor of Computer Science at ETH Zurich, where he leads the Learning & Adaptive Systems Group. Before that, he was an Assistant Professor of Computer Science at Caltech. He received his Ph.D. 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, received an ERC Starting Investigator grant, an NSF CAREER award as well as best paper awards at several premier conferences and journals.

For more information, contact Prof. Mihaela van der Schaar ()

Date(s) - Feb 17, 2016
2:00 pm - 3:30 pm

E-IV Tesla Room #53-125
420 Westwood Plaza - 5th Flr., Los Angeles CA 90095