Timezone: »

 
Scaling DPP MAP Inference
Jennifer Gillenwater

Sat Jul 18 07:10 AM -- 07:40 AM (PDT) @
in Negative Dependence and Submodularity: Theory and Applications in Machine Learning »
Event URL: http://slideslive.com/38930677 »

DPP MAP inference, the problem of finding the highest probability set under the distribution defined by a DPP, is of practical importance for a variety of areas such as recommender systems, active learning, and data compression. Unfortunately, finding the exact MAP solution is NP-hard. Often though, the standard greedy submodular maximization algorithm works well in practice for approximating the solution. In this talk, we discuss ways to speed up this simple greedy algorithm, as well as slower, but more accurate alternatives to it. We also discuss how to scale greedy for customized DPPs, where we want to solve the MAP problem multiple times with different weightings of item features. We conclude with a brief note on the complexity of MAP for nonsymmetric DPPs, where we show that greedy scales fairly well if we assume a particular kernel decomposition.

Author Information

Jennifer Gillenwater (Google Research NYC)

More from the Same Authors