NIPSNov, 2017

基于分区阈值算法的流式鲁棒次模最大化

PDF
TL;DR本文研究在流式场景下，求解具有基数限制 k 的单调子模函数最大化问题，提出了一种基于 STAR-T 算法的新型分区结构和指数递减阈值规则，这种算法只需要一次遍历数据，即可保留简短而健壮的总结性概括，还证明了在删除汇总得到的任何 m 个元素后，基于剩余的元素运行的一种简单贪心算法 STAR-T-GREEDY 可获得近似，最后通过两项不同的数据汇总任务证明了 STAR-T 的性能媲美先前的贪心和流式方法。
submodular functionstreaming algorithmmemory constraintgreedy algorithmdata summarization
发现论文，激发创造
  • 鲁棒子模最大化：一种非均匀划分方法

    本文研究了在确定性的 $ au$ 时，如何在满足固定大小约束 $k$ 的条件下最大化单调子模函数。提出了新的分区鲁棒性子模最大化算法，其构造具有指数增加大小的桶的分区，并在桶上应用标准子模优化子例程，证明了我们的算法对于更一般的 $ au = o（k）$ 具有相同的保证。在数据汇总和影响最大化方面，数值上验证了 PRo 的性能，并展示了对贪婪算法和 Orlin 等人的算法的优势。

    Jun, 2017

  • 做更少，得更多：带子采样的流式子模最大化

    该论文提出了首个一次遍历的流算法，用于求解子模最大化问题，采用数据采样，能够在各种情况下获得最紧密的逼近保证，同时具有最小的内存占用和对函数评估数量的最低要求，试验表明该算法在进行大规模机器学习问题的子模最大化时能够将其表现提高 50 倍以上

    Feb, 2018

  • 全息子模流处理：紧密逼近、最小内存和低自适应复杂度

    本文讨论了在 streaming setting 下最大化单调次模函数，并给出了一种新的算法 Sieve-Streaming++ 以及其扩展到多源 streaming setting 的方案，最终将该算法应用于 twitter 和 youtube 视频的多源数据摘要任务中进行效率测试。

    May, 2019

  • 流式非单调子模最大化：实时个性化视频摘要

    本文提出了第一个高效的单遍流式计算算法 Streaming Local Search，用于在独立系统和多重背包约束下，同时最大化非单调子模函数，解决实时提取和总结大规模视频流的问题。

    Jun, 2017

  • 从数据流中公平且代表性地选择子集

    本研究旨在探究在数据流中从每个数据组中提取一定数量的代表项目的问题，并提出了一种公正的约束模型和有效的解决方案。该解决方案在最大化覆盖面和个性化推荐方面具有实际应用和较高的性能。

    Oct, 2020

  • 约束 k 次模最大化的在线和流式算法

    本文提出了单遍流式和在线算法的受约束 k - 次模最大化，其中包含基数和背包约束限制，该算法可以提供不错的近似解和高效的解决方案，并在广告分配等应用实例上得到了验证。

    May, 2023

  • 海量数据流中子模函数最大化问题的 $1/2$ 之外近似算法

    该论文研究设计了一种流式亚模量最大化算法 SALSA，用于提取数据多样性、非参数学习、核机器、聚类等方面的大规模数据集的代表性摘要，取得了比现有算法更好的近似效果。

    Aug, 2018

  • 在 Matroid 约束下流式子模最大化中的公平性

    论文研究流式子模最大化算法中公平性的应用，提出了针对劣模最大化算法的公平机器学习算法，包括在鸽子数量受限的情况下的流式算法以及无法实现的结果。最后，通过社会网络中的最大覆盖，电影推荐和样本聚类等应用的实验验证了其有效性。

    May, 2023

  • 基于拟阵的删除鲁棒子模型最大化

    本文研究在传统的拟阵约束下，单调子模函数的删除鲁棒版本的最大化问题，提出了空间复杂度依赖于拟阵的秩和删除元素数量的常数因子逼近算法，在中心化、流式环境下均获得了好的结果。

    Jan, 2022

  • 滑动窗口上的次模优化

    本文在数据流的上下文中，提供了一种基于滑动窗口模型的次模优化的近似算法，该算法维护了一个解决方案，考虑的仅是最后 $W$ 个元素，使用空间多项式对元素值的传播速度的对数级别，线性大小的解决方案，并保持高品质的解，实际表现远超理论界限。

    Oct, 2016