Zonotope Hit-and-run for Efficient Sampling from Projection DPPs

Guillaume Gautier, Rémi Bardenet, Michal Valko
Proceedings of the 34th International Conference on Machine Learning, PMLR 70:1223-1232, 2017.

Abstract

Determinantal point processes (DPPs) are distributions over sets of items that model diversity using kernels. Their applications in machine learning include summary extraction and recommendation systems. Yet, the cost of sampling from a DPP is prohibitive in large-scale applications, which has triggered an effort towards efficient approximate samplers. We build a novel MCMC sampler that combines ideas from combinatorial geometry, linear programming, and Monte Carlo methods to sample from DPPs with a fixed sample cardinality, also called projection DPPs. Our sampler leverages the ability of the hit-and-run MCMC kernel to efficiently move across convex bodies. Previous theoretical results yield a fast mixing time of our chain when targeting a distribution that is close to a projection DPP, but not a DPP in general. Our empirical results demonstrate that this extends to sampling projection DPPs, i.e., our sampler is more sample-efficient than previous approaches which in turn translates to faster convergence when dealing with costly-to-evaluate functions, such as summary extraction in our experiments.

Cite this Paper

BibTeX
@InProceedings{pmlr-v70-gautier17a, title = {Zonotope Hit-and-run for Efficient Sampling from Projection {DPP}s}, author = {Guillaume Gautier and R{\'e}mi Bardenet and Michal Valko}, booktitle = {Proceedings of the 34th International Conference on Machine Learning}, pages = {1223--1232}, 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/gautier17a/gautier17a.pdf}, url = {https://proceedings.mlr.press/v70/gautier17a.html}, abstract = {Determinantal point processes (DPPs) are distributions over sets of items that model diversity using kernels. Their applications in machine learning include summary extraction and recommendation systems. Yet, the cost of sampling from a DPP is prohibitive in large-scale applications, which has triggered an effort towards efficient approximate samplers. We build a novel MCMC sampler that combines ideas from combinatorial geometry, linear programming, and Monte Carlo methods to sample from DPPs with a fixed sample cardinality, also called projection DPPs. Our sampler leverages the ability of the hit-and-run MCMC kernel to efficiently move across convex bodies. Previous theoretical results yield a fast mixing time of our chain when targeting a distribution that is close to a projection DPP, but not a DPP in general. Our empirical results demonstrate that this extends to sampling projection DPPs, i.e., our sampler is more sample-efficient than previous approaches which in turn translates to faster convergence when dealing with costly-to-evaluate functions, such as summary extraction in our experiments.} }
Endnote
%0 Conference Paper %T Zonotope Hit-and-run for Efficient Sampling from Projection DPPs %A Guillaume Gautier %A Rémi Bardenet %A Michal Valko %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-gautier17a %I PMLR %P 1223--1232 %U https://proceedings.mlr.press/v70/gautier17a.html %V 70 %X Determinantal point processes (DPPs) are distributions over sets of items that model diversity using kernels. Their applications in machine learning include summary extraction and recommendation systems. Yet, the cost of sampling from a DPP is prohibitive in large-scale applications, which has triggered an effort towards efficient approximate samplers. We build a novel MCMC sampler that combines ideas from combinatorial geometry, linear programming, and Monte Carlo methods to sample from DPPs with a fixed sample cardinality, also called projection DPPs. Our sampler leverages the ability of the hit-and-run MCMC kernel to efficiently move across convex bodies. Previous theoretical results yield a fast mixing time of our chain when targeting a distribution that is close to a projection DPP, but not a DPP in general. Our empirical results demonstrate that this extends to sampling projection DPPs, i.e., our sampler is more sample-efficient than previous approaches which in turn translates to faster convergence when dealing with costly-to-evaluate functions, such as summary extraction in our experiments.
APA
Gautier, G., Bardenet, R. & Valko, M.. (2017). Zonotope Hit-and-run for Efficient Sampling from Projection DPPs. Proceedings of the 34th International Conference on Machine Learning, in Proceedings of Machine Learning Research 70:1223-1232 Available from https://proceedings.mlr.press/v70/gautier17a.html.

Related Material