Exact Sampling of Determinantal Point Processes without Eigendecomposition
Determinantal point processes (DPPs) enable the modeling of repulsion: they provide diverse sets of points. The repulsion is encoded in a kernel $K$ that can be seen as a matrix storing the similarity between points. The diversity comes from the fact that the inclusion probability of a subset is equal to the determinant of a submatrice of $K$. The exact algorithm to sample DPPs uses the spectral decomposition of $K$, a computation that becomes costly when dealing with a high number of points. Here, we present an alternative exact algorithm in the discrete setting that avoids the eigenvalues and the eigenvectors computation. Instead, it relies on Cholesky decompositions. This is a two steps strategy: first, it samples a Bernoulli point process with an appropriate distribution, then it samples the target DPP distribution through a thinning procedure. Not only is the method used here innovative, but this algorithm can be competitive with the original algorithm or even faster for some applications specified here.
Code (0)
등록된 구현이 없습니다.
Tasks
DiversityPoint ProcessesSimilar Papers 제목 키워드 기반
Exact sampling of determinantal point processes with sublinear time preprocessing
We study the complexity of sampling from a distribution over all index subsets of the set $\{1,...,n\}$ with the probability of a subset $S$ proportional to the determinant of the submatrix $\mathbf{L}_S$ of some $n\time…
Point ProcessesExact Sampling from Determinantal Point Processes
Determinantal point processes (DPPs) are an important concept in random matrix theory and combinatorics. They have also recently attracted interest in the study of numerical methods for machine learning, as they offer an…
Active LearningBayesian OptimizationBIG-bench Machine LearningPoint Processes+1Structured Determinantal Point Processes
We present a novel probabilistic model for distributions over sets of structures -- for example, sets of sequences, trees, or graphs. The critical characteristic of our model is a preference for diversity: sets containin…
DiversityPoint ProcessesPose EstimationKronecker Determinantal Point Processes
Determinantal Point Processes (DPPs) are probabilistic models over all subsets a ground set of $N$ items. They have recently gained prominence in several applications that rely on "diverse" subsets. However, their applic…
Point ProcessesStochastic OptimizationDPPy: Sampling DPPs with Python
Determinantal point processes (DPPs) are specific probability distributions over clouds of points that are used as models and computational tools across physics, probability, statistics, and more recently machine learnin…
BIG-bench Machine LearningDiversityPoint Processes