具有亚线性时间预处理的确定性点过程的精确采样
研究使用确定性点过程(determinantal point process)对行子集进行采样的复杂度,提出了一种新的算法 —— 正则化确定性点过程(R-DPP),该算法在预处理步骤和采样步骤上分别具有两个独立的特性,适用于机器学习、数据概括和低秩矩阵重建等多个领域。
Nov, 2018
对于一种新颖的分区约束 DPPs,我们提出了第一个多项式时间的算法,以在约束下准确地从中进行抽样,并发现这种方法比 k-DPPs 和其朴素扩展提供更多的灵活性和多样性。同时,我们通过实验发现,简单的贪心初始化和局部搜索可以提高从 k-DPPs 的 MAP 推断问题的近似保证,特别是在较大的 k 下。
Jul, 2016
本论文研究基于对称核矩阵的确定性点过程,提出了一种可扩展和快速的拒绝采样方法,通过构建新的建议分布以及对核进行一定结构上的约束,控制拒绝率,从而能够应用于非对称确定性点过程的采样。
Jan, 2022
本文介绍了行列式点过程 (Determinantal Point Processes, DPPs) 以及其在机器学习领域中的应用,比如主动学习、贝叶斯优化、强化学习和图形模型中的边缘化。同时,文章也指出了为许多与机器学习相关的设置提供了在连续域上从 DPPs 中精确采样的方法。
Sep, 2016
该论文提出了一种新的行列式点过程的类别,可用于推理和参数学习,特别适用于在指数级别上定义的文本文档的概率建模。应用该技术进行文档摘要,并对可能达到 2^500 个项目的情况进行了演示。
Oct, 2016
本文提出了一种新的、高效的,近似采样来自离散 $k$-DPP 的方法,该方法利用了从 DPP 采样的子集的多样性属性,并分两个阶段进行:首先,对于项的基础集合,它构造核心集; 然后,基于构造的核心子集高效地采样子集,并旨在最小化到原始分布的总变分距离。在合成和实际数据集上的实验表明,相对于以前的方法,我们的采样算法在大数据集上可以有效地工作,并生成更准确的样本。
Sep, 2015
本文研究了约束 DPPs(具有 partition 或 matroid 约束的 DPPs)采样的复杂性,提出了一种精确有效的算法,并将其解决方案表达为多项式形式。
Aug, 2016
本论文提出了一种自适应算法用于在大型数据集中编织小型数据集,从而提高 $k$-DPP 采样算法的性能,并确保所生成的样本集合与原始数据集的目标分布相一致。
Jun, 2020
通过使用随机点值函数的加权最小二乘逼近方法,该研究论文提供了一种依赖于投影行列式点过程(DPP)或体积采样的加权最小二乘泛化版本,证明了在期望意义下使用 O (mlog (m)) 个样本时预期的 L^2 误差受到常数倍的 L^2 最佳逼近误差的限制,并证明了在函数属于连续嵌入 L^2 的某个范数向量空间 H 的情况下,逼近几乎一定受到 H 范数下最佳逼近误差的限制,最后通过数值实验展示了不同策略的性能。
Dec, 2023
我们研究了行列式点过程的乘积作为行列式点过程的一种自然、有前途的推广,研究了计算其标准化常数的计算复杂性,特别地,我们证明了存在针对 输入矩阵强制具有有利结构 的高效算法,否则这一任务的计算复杂性非常困难,我们还探讨了该领域的两个应用。
Nov, 2021