Abstract:
Determinantal point processes (DPPs) are a useful probabilistic model for selecting
a small diverse subset out of a large collection of items, with applications in
summarization, recommendation, stochastic optimization, experimental design and
more. Given a kernel function and a subset size k, our goal is to sample k out
of n items with probability proportional to the determinant of the kernel matrix
induced by the subset (a.k.a. k-DPP). Existing k-DPP sampling algorithms require
an expensive preprocessing step which involves multiple passes over all n items,
making it infeasible for large datasets. A naïve heuristic addressing this problem is
to uniformly subsample a fraction of the data and perform k-DPP sampling only on
those items, however this method offers no guarantee that the produced sample will
even approximately resemble the target distribution over the original dataset. In this
paper, we develop alpha-DPP, an algorithm which adaptively builds a sufficiently large uniform
sample of data that is then used to efficiently generate a smaller set of k items,
while ensuring that this set is drawn exactly from the target distribution defined
on all n items. We show empirically that our
algorithm produces a k-DPP sample after observing only a small fraction of all
elements, leading to several orders of magnitude faster performance compared to
the state-of-the-art. Our implementation of alpha-DPP is provided at https://github.com/guilgautier/DPPy/.
