在机器学习中,基于 matroid 约束的子模最大化是一个具有各种应用的基本问题。最近,已经在有限制条件下的流式和离线设置下考虑了基于基数约束的子模最大化中的公平性,但对于更一般的 matroid 约束问题,只有在流式设置下且只考虑单调目标。本文通过提出各种算法和不可能性结果,在质量、公平性和广泛性之间提供了不同的权衡。
Dec, 2023
论文研究流式子模最大化算法中公平性的应用,提出了针对劣模最大化算法的公平机器学习算法,包括在鸽子数量受限的情况下的流式算法以及无法实现的结果。最后,通过社会网络中的最大覆盖,电影推荐和样本聚类等应用的实验验证了其有效性。
May, 2023
本文提出了一种新型的随机子集选择框架,用于解决机器学习算法中存在的偏见或歧视问题,该框架结合了群体公平和最优化的因素,具有广泛的应用前景和优化效果。
Apr, 2023
本研究提出一种算法用于在考虑限制因素的情况下,最大化一类亚模模函数。算法能够保证在该模函数家族下,输出子集的效用最优,并均衡代表每个子集组。
该论文提出了一个简单的分布式算法来解决在机器学习中的受限次模最大化问题,该算法可以并行运行并且提供可证明的常数近似保证,即使在单个机器上无法解决的问题也可以通过该算法高效地解决。
Feb, 2015
证明了在许多计算机科学中随机化的作用,以及针对次模函数最大化领域的一种新的去随机化算法技术
Aug, 2015
本文提出了一种适用于分布式计算的子模函数最大化方法 GreeDi,该方法可在 MapReduce 框架下实现,初步实验表明该方法可应用于大规模机器学习任务中的子模优化问题,如稀疏高斯过程推断和样例聚类等问题,且在一定的自然条件下,可以达到接近于传统集中式计算模式下的性能表现。
Nov, 2014
本文提出一种针对子模函数的数据学习算法,可用于数据概括、特征选择和主动学习等机器学习领域。通过将贪婪最大化算法的输出解释为项目序列的分布,本文提出一种可微的方式对模型进行优化。实证研究表明,该方法对解决实际场景中的推荐和图像概括等问题有较好的效果。
Mar, 2018
本研究旨在探究在数据流中从每个数据组中提取一定数量的代表项目的问题,并提出了一种公正的约束模型和有效的解决方案。该解决方案在最大化覆盖面和个性化推荐方面具有实际应用和较高的性能。
Oct, 2020
通过直接优化偏差和方差的组合,该研究通过展示如何进行具有理论保证的高效算法,从而在次模函数中进行分布式鲁棒优化(DRO),从而实现在未知随机次模函数的情况下实现更好的性能和更好的推广。
Feb, 2018