Scalable MCMC Sampling for Nonsymmetric Determinantal Point Processes
Scalable MCMC Sampling for Nonsymmetric Determinantal Point Processes
复制标题
DOI：
10.48550/arxiv.2207.00486
复制
发表时间：
2022-07
期刊：
影响因子：
--
通讯作者：
Insu Han;Mike Gartrell;Elvis Dohmatob;Amin Karbasi
中科院分区：
文献类型：
--
作者：
Insu Han;Mike Gartrell;Elvis Dohmatob;Amin Karbasi
决定点过程（DPP）是一个优雅的模型，它为n个项目的集合的每个子集分配概率。虽然传统的DPP参数化的对称核矩阵，消除这种对称性的约束，导致非对称DPP（NDPP），导致建模能力和预测性能的显着改善。最近的工作研究了一个近似的马尔可夫链蒙特卡罗（MCMC）抽样算法的NDPP限制到大小为k的子集（称为k-NDPP）。然而，这种方法的运行时间是n的二次函数，这使得它不适用于大规模设置。在这项工作中，我们开发了一个可扩展的MCMC采样算法的k -NDPP与低秩内核，从而使运行时间是次线性的n。我们的方法是基于一个国家的最先进的NDPP拒绝采样算法，我们提高了一种新的方法，有效地构建建议分布。此外，我们扩展我们的可扩展的k-NDPP采样算法的NDPP没有大小的限制。我们得到的采样方法在内核的秩中具有多项式时间复杂度，而现有的方法在秩中具有指数的运行时间。通过理论分析和在真实数据集上的实验，我们验证了我们的可扩展近似采样算法比现有的k-NDPP和NDPP采样方法快几个数量级。
A determinantal point process (DPP) is an elegant model that assigns a probability to every subset of a collection of n items. While conventionally a DPP is parameterized by a symmetric kernel matrix, removing this symmetry constraint, resulting in nonsymmetric DPPs (NDPPs), leads to significant improvements in modeling power and predictive performance. Recent work has studied an approximate Markov chain Monte Carlo (MCMC) sampling algorithm for NDPPs restricted to size- k subsets (called k -NDPPs). However, the runtime of this approach is quadratic in n , making it infeasible for large-scale settings. In this work, we develop a scalable MCMC sampling algorithm for k -NDPPs with low-rank kernels, thus enabling runtime that is sublinear in n . Our method is based on a state-of-the-art NDPP rejection sampling algorithm, which we enhance with a novel approach for efficiently constructing the proposal distribution. Furthermore, we extend our scalable k -NDPP sampling algorithm to NDPPs without size constraints. Our resulting sampling method has polynomial time complexity in the rank of the kernel, while the existing approach has runtime that is exponential in the rank. With both a theoretical analysis and experiments on real-world datasets, we verify that our scalable approximate sampling algorithms are orders of magnitude faster than existing sampling approaches for k -NDPPs and NDPPs.