DPP-VFX: Very Fast and eXact DPP sampler

Material related to the NeurIPS 2019 paper "Exact sampling of determinantal point processes with sublinear time preprocessing" by Michał Dereziński, Calandriello Daniele, and Michal Valko.

Resources

Link	Resource
ArXiv	Paper
Poster	Poster
Algorithm code	Implemented in DPPy ver. 0.3 or later
Experiment code	This repository

Algorithm code

dpp-vfx is the first sub-linear time exact DPP sampler. It is implmented as part of the DPPy library, which can be installed using the command

pip install dppy

An example usage on some gaussian data with linear kernel is

from dppy.finite_dpps import FiniteDPP
from dppy.utils import example_eval_L_linear
from numpy.random import randn

N = 1000
r = 100
k = 5

DPP = FiniteDPP('likelihood',
                **{'L_eval_X_data': (example_eval_L_linear, randn(N, r))})

for _ in range(10):
    sample = DPP.sample_exact('vfx')
    print(sample)

for _ in range(10):
    sample = DPP.sample_exact_k_dpp(size=k, mode='vfx')
    print(sample)

Experiments code

The experiments reported in the paper can be reproduced using the files exp_dppy_mnist_first_sample.py and exp_dppy_mnist_successive_sample.py, with the file postprocess_dppy_experiments.py containing the matplotlib code necessary to generate the plots.

The experiments require:

• Access to a scientific python stack, including numpy, scipy, and sklearn
• DPPy version 0.3 or higher, available on github and PyPi

The experiments also require access to the MNIST8M (now called infinite MNIST) dataset. To reproduce the experiments, download the dataset's source file, and convert it from the MNIST or svmlight format to a numpy .npz first.

Citation

If you use dpp-vfx or the related experiments code please cite:

@incollection{neurips2019dppvfx,
title = {Exact sampling of determinantal point processes with sublinear time preprocessing,
author = {Micha{\l} Derezi\'{n}ski and Daniele Calandriello and Michal Valko},
booktitle = {Advances in Neural Information Processing Systems 32},
year = {2019},
}

Contact

For any question, you can contact daniele.calandriello@iit.it or mderezin@berkeley.edu