本文从凸分析的角度介绍了子模函数,论述了子模函数最小化与各类凸优化问题的关系,提出了新的高效算法以及多种子模函数在机器学习中的应用。
Nov, 2011
本文研究了次模函数及其在凸优化和概率测度方面的应用,提出了连续化的概率测度拓展方式,利用多重边际最优传送理论对次模集函数情况下的推论进行了拓展,最终给出了离散域中通用次模函数的实际最小化算法及其收敛速率。
Nov, 2015
本文介绍了子模函数的连续松弛及其在优化问题中的应用,同时提出了一种基于对称子模函数的基数约束下,最小化函数的常系数逼近算法。
Dec, 2009
本文探究了三个相关且重要的机器学习问题。我们展示了这三个问题的复杂度都依赖于子模函数的 ' 曲率 ',并提供了改进旧有结果的上下界。我们证明了曲率对于子模函数的近似、最小化和学习有影响,并通过实验结果支持了我们的理论结论。
Nov, 2013
本文研究两个新的优化问题 —— 在满足子模下限的约束条件下最小化子模函数(子模覆盖)和在满足子模上限的约束条件下最大化子模函数(子模背包)。我们将这些问题表述为约束优化问题,并获得许多有界逼近保证。此外,我们证明了这两个问题的紧密关联,并提供了一种解决一个问题的逼近算法用于获得另一个问题的逼近保证。最后,我们通过实验证明了本文算法的效果和良好的可扩展性。
本文提出一种针对子模函数的数据学习算法,可用于数据概括、特征选择和主动学习等机器学习领域。通过将贪婪最大化算法的输出解释为项目序列的分布,本文提出一种可微的方式对模型进行优化。实证研究表明,该方法对解决实际场景中的推荐和图像概括等问题有较好的效果。
Mar, 2018
本文研究了 submodular functions 可以被其他简单类别的 submodular functions 逼近的程度和方法,并证明了一些上下界。
Apr, 2013
本文研究了弱次模函数的性质及优化问题,其中包括了一些次超模函数,并提出了在均匀和一般性拟阵约束下最大化弱次模函数的优化问题,在此问题中,我们证明了标准贪心算法和简单局部搜索算法的算法近似比分别为 5.95 和 10.22。
Jan, 2014
本文通过扩展 Edmonds 和 Lovasz 的研究,提供了关于子模性与凸性和凹性之间关系的更完整的画面,同时探讨了子模最大化的优化条件和一些近似条件的应用。
Jun, 2015
本文研究离散领域的函数特性 submodularity 及其在信号处理和机器学习中的应用。介绍了一些 submodular-friendly 的应用场景和优化算法,同时探索了 submodularity 与 convexity 和 concavity 之间的关系,讨论了建立最优性保证的方法。
Jun, 2020