Towards Deterministic Diverse Subset Sampling
This work addresses the need for interpretable and reliable diverse subset selection in applications like recommendation and image search, but it appears incremental as it adapts an existing method deterministically.
The paper tackles the problem of diverse subset selection by proposing a deterministic greedy adaptation of k-DPP, which eliminates failure probability and ensures consistent results. It demonstrates the method's effectiveness through low-rank kernel approximations on multiple datasets and an image search task, though specific numerical results are not provided in the abstract.
Determinantal point processes (DPPs) are well known models for diverse subset selection problems, including recommendation tasks, document summarization and image search. In this paper, we discuss a greedy deterministic adaptation of k-DPP. Deterministic algorithms are interesting for many applications, as they provide interpretability to the user by having no failure probability and always returning the same results. First, the ability of the method to yield low-rank approximations of kernel matrices is evaluated by comparing the accuracy of the Nyström approximation on multiple datasets. Afterwards, we demonstrate the usefulness of the model on an image search task.