Sampling from a k-DPP without looking at all items
Type de document :
Communication dans un congrès avec actes
Titre :
Sampling from a k-DPP without looking at all items
Auteur(s) :
Calandriello, Daniele [Auteur]
DeepMind [Paris]
Dereziński, Michał [Auteur]
University of California [Berkeley] [UC Berkeley]
Valko, Michal [Auteur]
DeepMind [Paris]
Scool [Scool]
DeepMind [Paris]
Dereziński, Michał [Auteur]
University of California [Berkeley] [UC Berkeley]
Valko, Michal [Auteur]
DeepMind [Paris]
Scool [Scool]
Titre de la manifestation scientifique :
Neural Information Processing Systems
Ville :
Montréal
Pays :
Canada
Date de début de la manifestation scientifique :
2020
Discipline(s) HAL :
Statistiques [stat]/Machine Learning [stat.ML]
Résumé en anglais : [en]
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, stochastic optimization, active learning ...
Lire la suite >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, stochastic optimization, active learning 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 α-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 α-DPP is provided at https://github.com/guilgautier/DPPy/.Lire moins >
Lire la suite >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, stochastic optimization, active learning 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 α-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 α-DPP is provided at https://github.com/guilgautier/DPPy/.Lire moins >
Langue :
Anglais
Comité de lecture :
Oui
Audience :
Internationale
Vulgarisation :
Non
Collections :
Source :
Fichiers
- https://hal.inria.fr/hal-03287832/document
- Accès libre
- Accéder au document
- https://hal.inria.fr/hal-03287832/document
- Accès libre
- Accéder au document
- https://hal.inria.fr/hal-03287832/document
- Accès libre
- Accéder au document
- document
- Accès libre
- Accéder au document
- calandriello2020sampling.pdf
- Accès libre
- Accéder au document