受限强凸性意味着弱子模性
针对大型数据集中贪心算法的运行时间会非常高的问题,本文介绍了 2 种运用分布式计算和随机评估技术的更快逼近贪心向前选择算法,并且证明了弱次模性的泛化概念足以为这 2 种算法提供乘性逼近保证。同时,研究者还表明这些快速贪心逼近算法在人工数据和真实数据集上的性能要优于多个已有的基线算法。
Mar, 2017
本文提出了一种随机贪心算法来最大化弱次模函数在一般拟阵约束下的值,其中距离次模性的距离由参数 γ 衡量,该算法在实践中表现良好,并且是第一个能够约束弱次模函数最大化具有非平凡逼近保证的算法。
Jul, 2017
本文研究了弱次模函数的性质及优化问题,其中包括了一些次超模函数,并提出了在均匀和一般性拟阵约束下最大化弱次模函数的优化问题,在此问题中,我们证明了标准贪心算法和简单局部搜索算法的算法近似比分别为 5.95 和 10.22。
Jan, 2014
本文通过扩展 Edmonds 和 Lovasz 的研究,提供了关于子模性与凸性和凹性之间关系的更完整的画面,同时探讨了子模最大化的优化条件和一些近似条件的应用。
Jun, 2015
本研究通过分析子模函数的最大化和谱分析的见解,引入了子模性比率作为一种关键性质,研究了从大量随机变量中选择 k 个变量的问题,以实现对另一个感兴趣的变量的最佳线性预测,取得了这个问题方面最强的现有近似保证,并运用了该技术进行了实验和分析。
Feb, 2011
本文提出一种针对子模函数的数据学习算法,可用于数据概括、特征选择和主动学习等机器学习领域。通过将贪婪最大化算法的输出解释为项目序列的分布,本文提出一种可微的方式对模型进行优化。实证研究表明,该方法对解决实际场景中的推荐和图像概括等问题有较好的效果。
Mar, 2018
通过定义锐度作为子模函数改善贪心算法性能的候选解释,本文探讨了贪心算法在最大化单调子模函数下的性能问题,显示子模函数的锐度影响贪心算法的表现,通过计算实验和理论结果,支持本文的说法。
Feb, 2020
本文提出了一种适用于分布式计算的子模函数最大化方法 GreeDi,该方法可在 MapReduce 框架下实现,初步实验表明该方法可应用于大规模机器学习任务中的子模优化问题,如稀疏高斯过程推断和样例聚类等问题,且在一定的自然条件下,可以达到接近于传统集中式计算模式下的性能表现。
Nov, 2014
研究了 Greedy 算法在非子模不减集函数基数约束最大化中的性能,并证明了在一些重要的非子模函数如贝叶斯 A - 最优目标函数中,该算法具有很强的经验性能。我们以广义曲率 α 和子模性比率 γ 的组合为特点,证明了其理论保证,特别地,对于基数约束最大化,我们证明了 Greedy 算法具有紧密的近似保证为 1/α(1-e^(-γα))。另外,我们还限制了在几个重要的真实世界目标中子模性比率和曲率,包括贝叶斯 A - 最优目标、方形子矩阵的行列式函数和具有组合约束的某些线性规划。
Mar, 2017
这篇论文研究了函数的最大化问题,其中由凸可解体 $P$ 所定义的一类 $F (x) = G (x)+C (x)$ 函数是凸函数和 DR 子模函数的一个严格扩展,提供了一些算法实现,并在实际应用中进行了验证。
Jun, 2021