Nov, 2018

无失真中间采样的快速行列式点过程

PDF
TL;DR研究使用确定性点过程（determinantal point process）对行子集进行采样的复杂度，提出了一种新的算法 —— 正则化确定性点过程（R-DPP），该算法在预处理步骤和采样步骤上分别具有两个独立的特性，适用于机器学习、数据概括和低秩矩阵重建等多个领域。
发现论文，激发创造
  • 具有亚线性时间预处理的确定性点过程的精确采样

    研究了确定性点过程的复杂性，提出了一个新的采样算法，其中预处理成本为 n*poly (k)，采样成本为 poly (k)。

    May, 2019

  • 非对称行列式点过程可伸缩抽样

    本论文研究基于对称核矩阵的确定性点过程，提出了一种可扩展和快速的拒绝采样方法，通过构建新的建议分布以及对核进行一定结构上的约束，控制拒绝率，从而能够应用于非对称确定性点过程的采样。

    Jan, 2022

  • k-DPP 有效采样

    本文提出了一种新的、高效的，近似采样来自离散 $k$-DPP 的方法，该方法利用了从 DPP 采样的子集的多样性属性，并分两个阶段进行：首先，对于项的基础集合，它构造核心集； 然后，基于构造的核心子集高效地采样子集，并旨在最小化到原始分布的总变分距离。在合成和实际数据集上的实验表明，相对于以前的方法，我们的采样算法在大数据集上可以有效地工作，并生成更准确的样本。

    Sep, 2015

  • 随机数值线性代数中的行列式点过程

    本研究概述了随机数值线性代数 (Randomized Numerical Linear Algebra) 和行列式点过程 (Determinantal Point Processes) 两个看似不相关的数学领域之间新的深入而有益的联系，以及这些联系带来的新保证和改进的算法，并且介绍了 DPP 对于经典线性代数任务，如最小二乘回归、低秩逼近和 Nystrom 方法的应用。

    May, 2020

  • 关于有约束行列式点过程复杂性的研究

    本文研究了约束 DPPs（具有 partition 或 matroid 约束的 DPPs）采样的复杂性，提出了一种精确有效的算法，并将其解决方案表达为多项式形式。

    Aug, 2016

  • 确定性点过程的精确采样

    本文介绍了行列式点过程 (Determinantal Point Processes, DPPs) 以及其在机器学习领域中的应用，比如主动学习、贝叶斯优化、强化学习和图形模型中的边缘化。同时，文章也指出了为许多与机器学习相关的设置提供了在连续域上从 DPPs 中精确采样的方法。

    Sep, 2016

  • 学习行列式点过程的定点算法

    本文提出了一种新的算法来学习 DPP kernel，其效果比以前的方法都要好，而且速度更快，实验表明该方法可以在实际数据和模拟数据上取得很好的数值表现。

    Aug, 2015

  • 非对称行列式点过程的可扩展 MCMC 采样

    本文提出了一种基于状态较好的拒绝抽样算法的可扩展 MCMC 采样算法，用于 kdeterminantal point process，使其在低秩核下的运行时间为 n 的次幂；进一步将其扩展到没有大小限制的 NDPP。实验结果表明，我们的方法比现有的采样方法快得多。

    Jul, 2022

  • 基于行列式点过程和广义容积抽样的加权最小二乘逼近

    通过使用随机点值函数的加权最小二乘逼近方法，该研究论文提供了一种依赖于投影行列式点过程（DPP）或体积采样的加权最小二乘泛化版本，证明了在期望意义下使用 O (mlog (m)) 个样本时预期的 L^2 误差受到常数倍的 L^2 最佳逼近误差的限制，并证明了在函数属于连续嵌入 L^2 的某个范数向量空间 H 的情况下，逼近几乎一定受到 H 范数下最佳逼近误差的限制，最后通过数值实验展示了不同策略的性能。

    Dec, 2023

  • 无需查看所有项，从 $k$-DPP 中进行抽样

    本论文提出了一种自适应算法用于在大型数据集中编织小型数据集，从而提高 $k$-DPP 采样算法的性能，并确保所生成的样本集合与原始数据集的目标分布相一致。

    Jun, 2020