Sep, 2023

可组合核心集对决策极大化的应用：贪婪算法几乎是最优的

HTML
PDF
TL;DR利用贪心算法提供具有几乎最优逼近因子O(k)^{3k}的组合核心集，以支持一种名为“确定最大化”的确定点过程地图推理任务。
发现论文，激发创造
  • 学习行列式点过程的定点算法

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

    Aug, 2015

  • 关于约束行列式点过程的采样和贪婪 MAP 推理

    对于一种新颖的分区约束DPPs，我们提出了第一个多项式时间的算法，以在约束下准确地从中进行抽样，并发现这种方法比k-DPPs和其朴素扩展提供更多的灵活性和多样性。同时，我们通过实验发现，简单的贪心初始化和局部搜索可以提高从k-DPPs的MAP推断问题的近似保证，特别是在较大的k下。

    Jul, 2016

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

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

    Sep, 2016

  • 用于行列式点过程的更快贪婪MAP推断

    本文提出了使用log-determinants和stochastic trace estimators的两种逼近方案来使得贪心算法更快速，从而解决大规模determinantal point processes的MAP问题。实验表明，该算法在不牺牲较少精度的情况下比其竞争对手快数个数量级。

    Mar, 2017

  • 贪心是美德：通过贪心优化实现近似最优子模函数最大化

    本文介绍了针对具有限制条件的子模函数进行最大化的两种算法——Repeated Greedy和Sample Greedy，并比较了这两种算法在电影推荐方面的表现。结果表明，Sample Greedy在保证效用相同的情况下，性能至少比最佳基线提高了两个数量级。

    Apr, 2017

  • 用网络学习方法进行点过程的行列式稀疏化应用

    本研究提出了一种基于确定性点过程的依赖稀化方法，其可用于生成新的点过程用于网络建模以及概率传输调度方案，并利用统计学习技术优化了这些模型。

    Oct, 2018

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

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

    Nov, 2018

  • 具有亚线性时间预处理的确定性点过程的精确采样

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

    May, 2019

  • 可组合核心集应用于行列式最大化的简单近优算法

    提出了两种算法来有效地构建可组合核心集问题的解决方案，一种是更加实用的贪心算法，可获得${O(C^{k^2})}$的解；另一种是基于局部搜索的算法，可以获得近乎最优的解$O(k)^{2k}$，并证明了这些算法在标准数据集上的有效性。

    Jul, 2019

  • 贪心凸集合

    通过贪心算法学习基础模型的凸组合，得出结论：凸壳具有有限容量，良好的泛化性能，而线性壳的容量无限，容易出现过拟合情况。基于此，使用凸组合并结合早停法和拟定计算量可得的方法，可以实现贪心和非贪心学习。实验表明，贪心学习是一种有效的方法，且适应性强。

    Oct, 2019