本文介绍了通过使用广义子模函数代替较简单的目标函数获得的几个传统计算机科学问题的推广,包括子模型负载平衡,子模型最稀疏切割和子模型平衡切割等,并建立了这些问题的近似界限。
May, 2008
本文研究了一类新的子模函数优化问题,提出了一种基于平滑凸优化的算法 SLG,可用于解决具有数万个变量的分解子模函数问题,而且在一些合成基准测试和联合分类和分割任务中优于现有的子模函数优化算法。
Oct, 2010
本文通过在 submodular 函数的 Lovasz 扩展上使用投影随机次梯度下降法,利用子模性和数据结构来获得快速的坐标轴下降算法,实现了针对整数值子模函数的超线性 SFM 算法和针对实值子模函数的几乎线性 SFM 算法。
Oct, 2016
本文介绍了一种基于判别学习的方法来寻找高阶先验,该方法采用了结构化 SVM 和用于求解子模流问题的延伸割算法,说明了如何更好地利用子模函数的表达能力,实现更好的交互式分割技术。
Sep, 2013
本研究扩展了 Narasimhan 和 Bilmes 的工作,提出了基于子模函数差别最小化的新算法,该算法能有效地解决多种组合约束的问题,并且能够用于许多机器学习问题中,它在性能上优于现有的算法。
Jul, 2012
本文研究两个新的优化问题 —— 在满足子模下限的约束条件下最小化子模函数(子模覆盖)和在满足子模上限的约束条件下最大化子模函数(子模背包)。我们将这些问题表述为约束优化问题,并获得许多有界逼近保证。此外,我们证明了这两个问题的紧密关联,并提供了一种解决一个问题的逼近算法用于获得另一个问题的逼近保证。最后,我们通过实验证明了本文算法的效果和良好的可扩展性。
Nov, 2013
提出了一种高效算法,可在任何基于包含关闭的集合家族中找到对称次模函数的非空最小化器,包括基于基数约束、背包约束、拟阵独立约束或这些约束的任何组合。
Jul, 2010
本文研究了 k - 次模函数及其在离散函数中的应用,给出了 k - 次模多面体概念及 k - 次模函数的极小 - 极大定理,同时将以前次模函数的极小 - 极大定理推广到了 k - 次模函数的情形。
本文介绍一种易用且可并行的用于最小化由 “简单” 子模函数组成的子模函数的算法,并在几何子模多面体的基础上,利用谱图理论结果证明该算法线性收敛,并给出了收敛速率的上下界。
Jun, 2014
该篇论文提出了一种针对固定容量的分布式子模型最大化的框架,应用于广泛的算法和约束条件,并且为任何可用容量提供近似因子的理论保证,并在多个数据集上进行了实证评估,表现竞争性与中心化贪婪算法相当。
May, 2016