大规模数据概括:一种两阶段次模方法
针对两阶段子模问题,使用提供的子模训练函数减少底层集合,以确保优化新的目标函数能在减少后的底层集合上获得与原始底层集合相当的结果。本研究突破性地将非单调子模函数引入此领域,并提出了首个常数因子近似算法。
Sep, 2023
本文提出了一种适用于分布式计算的子模函数最大化方法 GreeDi,该方法可在 MapReduce 框架下实现,初步实验表明该方法可应用于大规模机器学习任务中的子模优化问题,如稀疏高斯过程推断和样例聚类等问题,且在一定的自然条件下,可以达到接近于传统集中式计算模式下的性能表现。
Nov, 2014
本文提出了第一个高效的单遍流式计算算法 Streaming Local Search,用于在独立系统和多重背包约束下,同时最大化非单调子模函数,解决实时提取和总结大规模视频流的问题。
Jun, 2017
本文介绍一个基于子模函数的查询聚焦意见摘要框架,其中,相关性排序由统计排名器产生,并且涵盖了涉及主题分布和多样视角的信息覆盖,同时利用离散函数来最小化冗余。本文是第一个为基于子模性的摘要方法评估不同文本相似性度量的方法。通过在社区 QA 和博客摘要上的实验,我们表明,我们的系统在自动评估和人类评估方面都优于现有技术。并且在 Amazon Mechanical Turk 上进行了一个人类评估任务,展示我们的系统能够产生总体质量和信息多样性高的摘要。
Jun, 2016
通过将现有算法从顺序设定应用到分布式设定,仅利用恒定数量的 MapReduce 循环,在许多设置中实现了接近最优的近似比率。我们的技术还为满足矩阵约束的非单调最大化提供了快速的顺序算法。
Jul, 2015
本文研究在流式场景下,求解具有基数限制 k 的单调子模函数最大化问题,提出了一种基于 STAR-T 算法的新型分区结构和指数递减阈值规则,这种算法只需要一次遍历数据,即可保留简短而健壮的总结性概括,还证明了在删除汇总得到的任何 m 个元素后,基于剩余的元素运行的一种简单贪心算法 STAR-T-GREEDY 可获得近似,最后通过两项不同的数据汇总任务证明了 STAR-T 的性能媲美先前的贪心和流式方法。
Nov, 2017
通过提出一种新颖的分布式界限算法,并使用多轮基于分区的分布式贪心算法,此论文解决了子集选择问题,能够在没有或极小损失质量的情况下,找到高质量的子集。
Feb, 2024
本文介绍了两种在 MapReduce 模型中的基数约束子模规划的简单算法,第一种算法在 2 个 MapReduce 轮中可以实现 1/2 的近似度,第二种算法可以在 1+o (1)/ε 个 MapReduce 轮中实现 1−1/e−ε 的近似度。
Oct, 2018
通过子模最大化算法,我们设计了一个通用的、灵活的核心选择例程,可在使用最少内存的情况下从数据流中提取最有价值的子集,并在 ImageNet 和 MNIST 的学习任务中表现出了优于随机选择的性能
Jan, 2022
该论文提出了一个简单的分布式算法来解决在机器学习中的受限次模最大化问题,该算法可以并行运行并且提供可证明的常数近似保证,即使在单个机器上无法解决的问题也可以通过该算法高效地解决。
Feb, 2015