High-performance sampling of generic determinantal point processes
High-performance sampling of generic determinantal point processes
复制标题
通用行列式过程的高性能采样
DOI：
10.1098/rsta.2019.0059
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
J. Poulson
中科院分区：
文献类型：
--
作者：
J. Poulson
MacChi（Macchi 1975 Appl。prob。7，83-122）引入了确定点过程（DPP），作为排斥性（费米子）粒子分布的模型。推荐系统的最后阶段（Kulesza＆Taskar 2012找到。趋势马赫。学习5，123-286）。正交投影仅适用于Hermitian内核，并具有昂贵的设置成本。 。初始光谱分解，但现有的方法仅在特殊情况下优于光谱分解方法，其中保留模式的数量是地面尺寸的一小部分。对于非赫米特人和遗产的DPP内核，实验表明，即使是动态安排的，共享的，共享的记忆并行的高性能密度和稀疏导向因素，也可以进行琐碎的修改，以产生具有基本相同性能的DPP采样方案。该软件作为这项研究的一部分开发的capamari（hodgestar.com/catamari）在Mozilla公共许可证v.2.0下发布。和非热门DPP样本。本文是讨论问题的一部分。
Determinantal point processes (DPPs) were introduced by Macchi (Macchi 1975 Adv. Appl. Probab. 7, 83–122) as a model for repulsive (fermionic) particle distributions. But their recent popularization is largely due to their usefulness for encouraging diversity in the final stage of a recommender system (Kulesza & Taskar 2012 Found. Trends Mach. Learn. 5, 123–286). The standard sampling scheme for finite DPPs is a spectral decomposition followed by an equivalent of a randomly diagonally pivoted Cholesky factorization of an orthogonal projection, which is only applicable to Hermitian kernels and has an expensive set-up cost. Researchers Launay et al. 2018 (http://arxiv.org/abs/1802.08429); Chen & Zhang 2018 NeurIPS (https://papers.nips.cc/paper/7805-fast-greedy-map-inference-for-determinantal-point-process-to-improve-recommendation-diversity.pdf) have begun to connect DPP sampling to LDLH factorizations as a means of avoiding the initial spectral decomposition, but existing approaches have only outperformed the spectral decomposition approach in special circumstances, where the number of kept modes is a small percentage of the ground set size. This article proves that trivial modifications of LU and LDLH factorizations yield efficient direct sampling schemes for non-Hermitian and Hermitian DPP kernels, respectively. Furthermore, it is experimentally shown that even dynamically scheduled, shared-memory parallelizations of high-performance dense and sparse-direct factorizations can be trivially modified to yield DPP sampling schemes with essentially identical performance. The software developed as part of this research, Catamari (hodgestar.com/catamari) is released under the Mozilla Public License v.2.0. It contains header-only, C++14 plus OpenMP 4.0 implementations of dense and sparse-direct, Hermitian and non-Hermitian DPP samplers. This article is part of a discussion meeting issue ‘Numerical algorithms for high-performance computational science’.