混合鲁棒 / 平均次模划分：快速算法、保证和应用于并行机器学习和多标签图像分割

Oct, 2015

混合鲁棒 / 平均次模划分：快速算法、保证和应用于并行机器学习和多标签图像分割

Mixed Robust/Average Submodular Partitioning: Fast Algorithms, Guarantees, and Applications to Parallel Machine Learning and Multi-Label Image Segmentation

PDF

Kai Wei, Rishabh Iyer, Shengjie Wang, Wenruo Bai, Jeff Bilmes

TL;DR本文提出了新的算法解决通过分配数据任务和负载均衡来实现大规模机器学习的 submodular partitioning 问题，并在图像分割中也取得了很好的表现。

Abstract

We study two mixed robust/average-case submodular partitioning problems that we collectively call submodular partitioning. These problems generalize both purely robust instances of the problem (namely max-min sub

submodular partitioning machine learning data partitioning load balancing image segmentation

发现论文，激发创造

分布式基于配对次模函数的大于内存子集选择

通过提出一种新颖的分布式界限算法，并使用多轮基于分区的分布式贪心算法，此论文解决了子集选择问题，能够在没有或极小损失质量的情况下，找到高质量的子集。

Feb, 2024

分布式次模最大化的新框架

通过将现有算法从顺序设定应用到分布式设定，仅利用恒定数量的 MapReduce 循环，在许多设置中实现了接近最优的近似比率。我们的技术还为满足矩阵约束的非单调最大化提供了快速的顺序算法。

Jul, 2015

分布式子模最大化

本文提出了一种适用于分布式计算的子模函数最大化方法 GreeDi，该方法可在 MapReduce 框架下实现，初步实验表明该方法可应用于大规模机器学习任务中的子模优化问题，如稀疏高斯过程推断和样例聚类等问题，且在一定的自然条件下，可以达到接近于传统集中式计算模式下的性能表现。

Nov, 2014

随机化的威力：大规模数据集上的分布式子模最大化

该论文提出了一个简单的分布式算法来解决在机器学习中的受限次模最大化问题，该算法可以并行运行并且提供可证明的常数近似保证，即使在单个机器上无法解决的问题也可以通过该算法高效地解决。

Feb, 2015

水平可扩展次模最大化

该篇论文提出了一种针对固定容量的分布式子模型最大化的框架，应用于广泛的算法和约束条件，并且为任何可用容量提供近似因子的理论保证，并在多个数据集上进行了实证评估，表现竞争性与中心化贪婪算法相当。

May, 2016

鲁棒子模最大化：一种非均匀划分方法

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

Jun, 2017

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

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

Nov, 2017

通过随机化实现子模函数最大化的长期公平性

通过开发近似算法解决具有组内公平性约束的单调子模函数最大化问题。

Apr, 2023

子模近似：基于采样的算法与下界

本文介绍了通过使用广义子模函数代替较简单的目标函数获得的几个传统计算机科学问题的推广，包括子模型负载平衡，子模型最稀疏切割和子模型平衡切割等，并建立了这些问题的近似界限。

May, 2008

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

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

Aug, 2018