本文提出了一种适用于分布式计算的子模函数最大化方法GreeDi,该方法可在MapReduce框架下实现,初步实验表明该方法可应用于大规模机器学习任务中的子模优化问题,如稀疏高斯过程推断和样例聚类等问题,且在一定的自然条件下,可以达到接近于传统集中式计算模式下的性能表现。
Nov, 2014
通过将现有算法从顺序设定应用到分布式设定,仅利用恒定数量的MapReduce循环,在许多设置中实现了接近最优的近似比率。我们的技术还为满足矩阵约束的非单调最大化提供了快速的顺序算法。
Jul, 2015
提出了一种在数据流上优化代表性子集选择的动态RSS方法,即最大化子模函数在具有一般 d-背包约束(SMDK)的滑动窗口上。KnapWindow框架(KW)利用KnapStream算法(KS)为SMDK策略中的“添加仅”数据流实例,提出KnapWindowPlus框架(KW$^{+}$)来改进KW。实验结果表明,KW和KW$^{+}$在保持SMDK高质量解的同时,比批处理基线减少了两个数量级以上的运行时间。
Jun, 2017
该论文提出了首个一次遍历的流算法,用于求解子模最大化问题,采用数据采样,能够在各种情况下获得最紧密的逼近保证,同时具有最小的内存占用和对函数评估数量的最低要求,试验表明该算法在进行大规模机器学习问题的子模最大化时能够将其表现提高50倍以上
Feb, 2018
本文讨论了在streaming setting下最大化单调次模函数,并给出了一种新的算法Sieve-Streaming++以及其扩展到多源streaming setting的方案,最终将该算法应用于twitter和youtube视频的多源数据摘要任务中进行效率测试。
May, 2019
本研究旨在探究在数据流中从每个数据组中提取一定数量的代表项目的问题,并提出了一种公正的约束模型和有效的解决方案。该解决方案在最大化覆盖面和个性化推荐方面具有实际应用和较高的性能。
Oct, 2020
论文研究流式子模最大化算法中公平性的应用,提出了针对劣模最大化算法的公平机器学习算法,包括在鸽子数量受限的情况下的流式算法以及无法实现的结果。最后,通过社会网络中的最大覆盖,电影推荐和样本聚类等应用的实验验证了其有效性。
May, 2023
本文提出了单遍流式和在线算法的受约束k-次模最大化,其中包含基数和背包约束限制,该算法可以提供不错的近似解和高效的解决方案,并在广告分配等应用实例上得到了验证。
我们提出了一种新的算法,可以在实践中有效地解决非单调受限子模型最大化问题,结合了0.385的逼近保证和低的查询复杂度。通过在各种机器学习应用中进行实验,包括电影推荐、图像摘要等,我们评估了我们算法的实验性能,证明了我们方法的功效。
May, 2024
在具有一致性约束的动态环境中,我们研究了在基数约束下最大化单调次模函数,其在数据挖掘和机器学习中有多个应用。我们提供了在此场景中具有一致性和逼近质量之间不同权衡的算法。实验证明我们算法在真实世界实例中的有效性。