Efficient Sampling for k-Determinantal Point Processes

Chengtao Li, Stefanie Jegelka, Suvrit Sra
Proceedings of the 19th International Conference on Artificial Intelligence and Statistics, PMLR 51:1328-1337, 2016.

Abstract

Determinantal Point Processes (DPPs) are elegant probabilistic models of repulsion and diversity over discrete sets of items. But their applicability to large sets is hindered by expensive cubic-complexity matrix operations for basic tasks such as sampling. In light of this, we propose a new method for approximate sampling from discrete k-DPPs. Our method takes advantage of the diversity property of subsets sampled from a DPP, and proceeds in two stages: first it constructs coresets for the ground set of items; thereafter, it efficiently samples subsets based on the constructed coresets. As opposed to previous approaches, our algorithm aims to minimize the total variation distance to the original distribution. Experiments on both synthetic and real datasets indicate that our sampling algorithm works efficiently on large data sets, and yields more accurate samples than previous approaches.

Cite this Paper

BibTeX
@InProceedings{pmlr-v51-li16f, title = {Efficient Sampling for k-Determinantal Point Processes}, author = {Li, Chengtao and Jegelka, Stefanie and Sra, Suvrit}, booktitle = {Proceedings of the 19th International Conference on Artificial Intelligence and Statistics}, pages = {1328--1337}, year = {2016}, editor = {Gretton, Arthur and Robert, Christian C.}, volume = {51}, series = {Proceedings of Machine Learning Research}, address = {Cadiz, Spain}, month = {09--11 May}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v51/li16f.pdf}, url = {https://proceedings.mlr.press/v51/li16f.html}, abstract = {Determinantal Point Processes (DPPs) are elegant probabilistic models of repulsion and diversity over discrete sets of items. But their applicability to large sets is hindered by expensive cubic-complexity matrix operations for basic tasks such as sampling. In light of this, we propose a new method for approximate sampling from discrete k-DPPs. Our method takes advantage of the diversity property of subsets sampled from a DPP, and proceeds in two stages: first it constructs coresets for the ground set of items; thereafter, it efficiently samples subsets based on the constructed coresets. As opposed to previous approaches, our algorithm aims to minimize the total variation distance to the original distribution. Experiments on both synthetic and real datasets indicate that our sampling algorithm works efficiently on large data sets, and yields more accurate samples than previous approaches.} }
Endnote
%0 Conference Paper %T Efficient Sampling for k-Determinantal Point Processes %A Chengtao Li %A Stefanie Jegelka %A Suvrit Sra %B Proceedings of the 19th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2016 %E Arthur Gretton %E Christian C. Robert %F pmlr-v51-li16f %I PMLR %P 1328--1337 %U https://proceedings.mlr.press/v51/li16f.html %V 51 %X Determinantal Point Processes (DPPs) are elegant probabilistic models of repulsion and diversity over discrete sets of items. But their applicability to large sets is hindered by expensive cubic-complexity matrix operations for basic tasks such as sampling. In light of this, we propose a new method for approximate sampling from discrete k-DPPs. Our method takes advantage of the diversity property of subsets sampled from a DPP, and proceeds in two stages: first it constructs coresets for the ground set of items; thereafter, it efficiently samples subsets based on the constructed coresets. As opposed to previous approaches, our algorithm aims to minimize the total variation distance to the original distribution. Experiments on both synthetic and real datasets indicate that our sampling algorithm works efficiently on large data sets, and yields more accurate samples than previous approaches.
RIS
TY - CPAPER TI - Efficient Sampling for k-Determinantal Point Processes AU - Chengtao Li AU - Stefanie Jegelka AU - Suvrit Sra BT - Proceedings of the 19th International Conference on Artificial Intelligence and Statistics DA - 2016/05/02 ED - Arthur Gretton ED - Christian C. Robert ID - pmlr-v51-li16f PB - PMLR DP - Proceedings of Machine Learning Research VL - 51 SP - 1328 EP - 1337 L1 - http://proceedings.mlr.press/v51/li16f.pdf UR - https://proceedings.mlr.press/v51/li16f.html AB - Determinantal Point Processes (DPPs) are elegant probabilistic models of repulsion and diversity over discrete sets of items. But their applicability to large sets is hindered by expensive cubic-complexity matrix operations for basic tasks such as sampling. In light of this, we propose a new method for approximate sampling from discrete k-DPPs. Our method takes advantage of the diversity property of subsets sampled from a DPP, and proceeds in two stages: first it constructs coresets for the ground set of items; thereafter, it efficiently samples subsets based on the constructed coresets. As opposed to previous approaches, our algorithm aims to minimize the total variation distance to the original distribution. Experiments on both synthetic and real datasets indicate that our sampling algorithm works efficiently on large data sets, and yields more accurate samples than previous approaches. ER -
APA
Li, C., Jegelka, S. & Sra, S.. (2016). Efficient Sampling for k-Determinantal Point Processes. Proceedings of the 19th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 51:1328-1337 Available from https://proceedings.mlr.press/v51/li16f.html.

Related Material