本文研究离散领域的函数特性 submodularity 及其在信号处理和机器学习中的应用。介绍了一些 submodular-friendly 的应用场景和优化算法,同时探索了 submodularity 与 convexity 和 concavity 之间的关系,讨论了建立最优性保证的方法。
Jun, 2020
本文从凸分析的角度介绍了子模函数,论述了子模函数最小化与各类凸优化问题的关系,提出了新的高效算法以及多种子模函数在机器学习中的应用。
Nov, 2011
本文介绍了子模函数的连续松弛及其在优化问题中的应用,同时提出了一种基于对称子模函数的基数约束下,最小化函数的常系数逼近算法。
Dec, 2009
本文提出一种针对子模函数的数据学习算法,可用于数据概括、特征选择和主动学习等机器学习领域。通过将贪婪最大化算法的输出解释为项目序列的分布,本文提出一种可微的方式对模型进行优化。实证研究表明,该方法对解决实际场景中的推荐和图像概括等问题有较好的效果。
Mar, 2018
通过提出一种新颖的分布式界限算法,并使用多轮基于分区的分布式贪心算法,此论文解决了子集选择问题,能够在没有或极小损失质量的情况下,找到高质量的子集。
Feb, 2024
本论文研究广义独立性、熵、互信息和总相关度等集合上的组合信息度量,这些度量通过子模函数进行参数化,严格推广了相应的熵度量。我们证明,对于大类满足一种非负性条件的子模函数,与另一个参数固定的情况下,子模互信息实际上是一种子模函数。我们将这种度量与分类,可靠分区和物品覆盖等问题联系起来。
本文介绍了通过使用广义子模函数代替较简单的目标函数获得的几个传统计算机科学问题的推广,包括子模型负载平衡,子模型最稀疏切割和子模型平衡切割等,并建立了这些问题的近似界限。
May, 2008
本文通过基于凸凹过程的变分框架方法,提出了一种最小化两个次模函数之间差异的算法。该算法在机器学习中的应用包括生成式结构图模型和特征选择,结果表明使用此算法的判别式图模型分类器可以明显优于使用生成式图模型的分类器。
Jul, 2012
该研究提出了一种基于离散子模规划问题的连续最佳逼近算法,提高了优化子模函数的效率和精度,并在图像分割任务中展示了该算法的优越性。
Nov, 2013
本文提出了一种适用于分布式计算的子模函数最大化方法 GreeDi,该方法可在 MapReduce 框架下实现,初步实验表明该方法可应用于大规模机器学习任务中的子模优化问题,如稀疏高斯过程推断和样例聚类等问题,且在一定的自然条件下,可以达到接近于传统集中式计算模式下的性能表现。
Nov, 2014