本文介绍了子模函数的连续松弛及其在优化问题中的应用,同时提出了一种基于对称子模函数的基数约束下,最小化函数的常系数逼近算法。
Dec, 2009
本文研究两个新的优化问题 —— 在满足子模下限的约束条件下最小化子模函数(子模覆盖)和在满足子模上限的约束条件下最大化子模函数(子模背包)。我们将这些问题表述为约束优化问题,并获得许多有界逼近保证。此外,我们证明了这两个问题的紧密关联,并提供了一种解决一个问题的逼近算法用于获得另一个问题的逼近保证。最后,我们通过实验证明了本文算法的效果和良好的可扩展性。
Nov, 2013
本文提出一种新的交互子模集覆盖问题,探讨了其在社交网络广告、有限假设类别的有误学习中的应用,给出了一种基于贪心算法的近似保证,并且证明了逼近难度。同时分享了早期实验结果。
Feb, 2010
本文提出一种针对子模函数的数据学习算法,可用于数据概括、特征选择和主动学习等机器学习领域。通过将贪婪最大化算法的输出解释为项目序列的分布,本文提出一种可微的方式对模型进行优化。实证研究表明,该方法对解决实际场景中的推荐和图像概括等问题有较好的效果。
Mar, 2018
本文研究了次模函数及其在凸优化和概率测度方面的应用,提出了连续化的概率测度拓展方式,利用多重边际最优传送理论对次模集函数情况下的推论进行了拓展,最终给出了离散域中通用次模函数的实际最小化算法及其收敛速率。
Nov, 2015
通过提出一种新颖的分布式界限算法,并使用多轮基于分区的分布式贪心算法,此论文解决了子集选择问题,能够在没有或极小损失质量的情况下,找到高质量的子集。
Feb, 2024
本文从凸分析的角度介绍了子模函数,论述了子模函数最小化与各类凸优化问题的关系,提出了新的高效算法以及多种子模函数在机器学习中的应用。
Nov, 2011
该研究提出了一种基于离散子模规划问题的连续最佳逼近算法,提高了优化子模函数的效率和精度,并在图像分割任务中展示了该算法的优越性。
本文提出了一种适用于分布式计算的子模函数最大化方法 GreeDi,该方法可在 MapReduce 框架下实现,初步实验表明该方法可应用于大规模机器学习任务中的子模优化问题,如稀疏高斯过程推断和样例聚类等问题,且在一定的自然条件下,可以达到接近于传统集中式计算模式下的性能表现。
Nov, 2014
介绍了子模函数的理论,包括在计算机科学和应用数学(如机器学习,计算机视觉,运筹学或电力网络)中发挥重要作用的集合函数,类似于向量空间上的凸函数。假定掌握了凸分析的基础知识。
Oct, 2010