Faster Greedy MAP Inference for Determinantal Point Processes

Insu Han, Prabhanjan Kambadur, Kyoungsoo Park, Jinwoo Shin
Proceedings of the 34th International Conference on Machine Learning, PMLR 70:1384-1393, 2017.

Abstract

Determinantal point processes (DPPs) are popular probabilistic models that arise in many machine learning tasks, where distributions of diverse sets are characterized by determinants of their features. In this paper, we develop fast algorithms to find the most likely configuration (MAP) of large-scale DPPs, which is NP-hard in general. Due to the submodular nature of the MAP objective, greedy algorithms have been used with empirical success. Greedy implementations require computation of log-determinants, matrix inverses or solving linear systems at each iteration. We present faster implementations of the greedy algorithms by utilizing the orthogonal benefits of two log-determinant approximation schemes: (a) first-order expansions to the matrix log-determinant function and (b) high-order expansions to the scalar log function with stochastic trace estimators. In our experiments, our algorithms are orders of magnitude faster than their competitors, while sacrificing marginal accuracy.

Cite this Paper

BibTeX
@InProceedings{pmlr-v70-han17a, title = {Faster Greedy {MAP} Inference for Determinantal Point Processes}, author = {Insu Han and Prabhanjan Kambadur and Kyoungsoo Park and Jinwoo Shin}, booktitle = {Proceedings of the 34th International Conference on Machine Learning}, pages = {1384--1393}, year = {2017}, editor = {Precup, Doina and Teh, Yee Whye}, volume = {70}, series = {Proceedings of Machine Learning Research}, month = {06--11 Aug}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v70/han17a/han17a.pdf}, url = {https://proceedings.mlr.press/v70/han17a.html}, abstract = {Determinantal point processes (DPPs) are popular probabilistic models that arise in many machine learning tasks, where distributions of diverse sets are characterized by determinants of their features. In this paper, we develop fast algorithms to find the most likely configuration (MAP) of large-scale DPPs, which is NP-hard in general. Due to the submodular nature of the MAP objective, greedy algorithms have been used with empirical success. Greedy implementations require computation of log-determinants, matrix inverses or solving linear systems at each iteration. We present faster implementations of the greedy algorithms by utilizing the orthogonal benefits of two log-determinant approximation schemes: (a) first-order expansions to the matrix log-determinant function and (b) high-order expansions to the scalar log function with stochastic trace estimators. In our experiments, our algorithms are orders of magnitude faster than their competitors, while sacrificing marginal accuracy.} }
Endnote
%0 Conference Paper %T Faster Greedy MAP Inference for Determinantal Point Processes %A Insu Han %A Prabhanjan Kambadur %A Kyoungsoo Park %A Jinwoo Shin %B Proceedings of the 34th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2017 %E Doina Precup %E Yee Whye Teh %F pmlr-v70-han17a %I PMLR %P 1384--1393 %U https://proceedings.mlr.press/v70/han17a.html %V 70 %X Determinantal point processes (DPPs) are popular probabilistic models that arise in many machine learning tasks, where distributions of diverse sets are characterized by determinants of their features. In this paper, we develop fast algorithms to find the most likely configuration (MAP) of large-scale DPPs, which is NP-hard in general. Due to the submodular nature of the MAP objective, greedy algorithms have been used with empirical success. Greedy implementations require computation of log-determinants, matrix inverses or solving linear systems at each iteration. We present faster implementations of the greedy algorithms by utilizing the orthogonal benefits of two log-determinant approximation schemes: (a) first-order expansions to the matrix log-determinant function and (b) high-order expansions to the scalar log function with stochastic trace estimators. In our experiments, our algorithms are orders of magnitude faster than their competitors, while sacrificing marginal accuracy.
APA
Han, I., Kambadur, P., Park, K. & Shin, J.. (2017). Faster Greedy MAP Inference for Determinantal Point Processes. Proceedings of the 34th International Conference on Machine Learning, in Proceedings of Machine Learning Research 70:1384-1393 Available from https://proceedings.mlr.press/v70/han17a.html.

Related Material