滑动窗口上的次模优化
本文讨论了在 streaming setting 下最大化单调次模函数,并给出了一种新的算法 Sieve-Streaming++ 以及其扩展到多源 streaming setting 的方案,最终将该算法应用于 twitter 和 youtube 视频的多源数据摘要任务中进行效率测试。
May, 2019
该论文研究设计了一种流式亚模量最大化算法 SALSA,用于提取数据多样性、非参数学习、核机器、聚类等方面的大规模数据集的代表性摘要,取得了比现有算法更好的近似效果。
Aug, 2018
本研究在完全动态的环境下,旨在最大化基数约束下的单调子模函数,研究结果为一个具有多项式对数的摊销更新时间和可得到 0.5-ε 近似解的随机算法,并结合经验研究证明了算法性能的优越性。
Jun, 2020
该论文提出了首个一次遍历的流算法,用于求解子模最大化问题,采用数据采样,能够在各种情况下获得最紧密的逼近保证,同时具有最小的内存占用和对函数评估数量的最低要求,试验表明该算法在进行大规模机器学习问题的子模最大化时能够将其表现提高 50 倍以上
Feb, 2018
该研究主要针对单次流式处理的情况下,最大化一个非负子模集函数 f 编制一些确定性和随机算法,以实现对 p 匹配约束条件的大约 1 /p 的逼近,假设具有时间和资源约束。
Apr, 2015
在具有一致性约束的动态环境中,我们研究了在基数约束下最大化单调次模函数,其在数据挖掘和机器学习中有多个应用。我们提供了在此场景中具有一致性和逼近质量之间不同权衡的算法。实验证明我们算法在真实世界实例中的有效性。
May, 2024
本研究旨在探究在数据流中从每个数据组中提取一定数量的代表项目的问题,并提出了一种公正的约束模型和有效的解决方案。该解决方案在最大化覆盖面和个性化推荐方面具有实际应用和较高的性能。
Oct, 2020
本文研究在流式场景下,求解具有基数限制 k 的单调子模函数最大化问题,提出了一种基于 STAR-T 算法的新型分区结构和指数递减阈值规则,这种算法只需要一次遍历数据,即可保留简短而健壮的总结性概括,还证明了在删除汇总得到的任何 m 个元素后,基于剩余的元素运行的一种简单贪心算法 STAR-T-GREEDY 可获得近似,最后通过两项不同的数据汇总任务证明了 STAR-T 的性能媲美先前的贪心和流式方法。
Nov, 2017
本文研究了在满足基数约束的条件下,最大化单调子模函数的逼近保证和适应性之间的权衡问题。我们给出了第一个使用 O(lnn /epsilon^2)轮适应性实现 1-1 /e-epsilon 逼近的算法,同时算法的函数评估次数和额外运行时间分别为 O(npoly(logn,1 /epsilon))。
Apr, 2018
本文提出了第一个高效的单遍流式计算算法 Streaming Local Search,用于在独立系统和多重背包约束下,同时最大化非单调子模函数,解决实时提取和总结大规模视频流的问题。
Jun, 2017