Fast Determinantal Point Process Sampling with Application to Clustering
Determinantal Point Process (DPP) has gained much popularity for modeling sets of diverse items. The gist of DPP is that the probability of choosing a particular set of items is proportional to the determinant of a positive definite matrix that defines the similarity of those items. However, computing the determinant requires time cubic in the number of items, and is hence impractical for large sets. In this paper, we address this problem by constructing a rapidly mixing Markov chain, from which we can acquire a sample from the given DPP in sub-cubic time. In addition, we show that this framework can be extended to sampling from cardinality-constrained DPPs. As an application, we show how our sampling algorithm can be used to provide a fast heuristic for determining the number of clusters, resulting in better clustering.
Code (0)
등록된 구현이 없습니다.
Tasks
ClusteringSimilar Papers 제목 키워드 기반
Fast Sampling for Strongly Rayleigh Measures with Application to Determinantal Point Processes
In this note we consider sampling from (non-homogeneous) strongly Rayleigh probability measures. As an important corollary, we obtain a fast mixing Markov Chain sampler for Determinantal Point Processes.
Point ProcessesFast determinantal point processes via distortion-free intermediate sampling
Given a fixed $n\times d$ matrix $\mathbf{X}$, where $n\gg d$, we study the complexity of sampling from a distribution over all subsets of rows where the probability of a subset is proportional to the squared volume of t…
Data SummarizationPoint ProcessesStochastic OptimizationSignal reconstruction using determinantal sampling
We study the approximation of a square-integrable function from a finite number of evaluations on a random set of nodes according to a well-chosen distribution. This is particularly relevant when the function is assumed …
Point ProcessesKronecker 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 OptimizationA novel sampler for Gauss-Hermite determinantal point processes with application to Monte Carlo integration
Determinantal points processes are a promising but relatively under-developed tool in machine learning and statistical modelling, being the canonical statistical example of distributions with repulsion. While their mathe…
BIG-bench Machine LearningPoint Processes