机器学习和人工智能中的次模性
本文研究了一类新的子模函数优化问题,提出了一种基于平滑凸优化的算法SLG,可用于解决具有数万个变量的分解子模函数问题,而且在一些合成基准测试和联合分类和分割任务中优于现有的子模函数优化算法。
Oct, 2010
本研究扩展了Narasimhan和Bilmes的工作,提出了基于子模函数差别最小化的新算法,该算法能有效地解决多种组合约束的问题,并且能够用于许多机器学习问题中,它在性能上优于现有的算法。
Jul, 2012
本文通过基于凸凹过程的变分框架方法,提出了一种最小化两个次模函数之间差异的算法。该算法在机器学习中的应用包括生成式结构图模型和特征选择,结果表明使用此算法的判别式图模型分类器可以明显优于使用生成式图模型的分类器。
Jul, 2012
本文探究了三个相关且重要的机器学习问题。我们展示了这三个问题的复杂度都依赖于子模函数的'曲率',并提供了改进旧有结果的上下界。我们证明了曲率对于子模函数的近似、最小化和学习有影响,并通过实验结果支持了我们的理论结论。
Nov, 2013
该论文提出了一个简单的分布式算法来解决在机器学习中的受限次模最大化问题,该算法可以并行运行并且提供可证明的常数近似保证,即使在单个机器上无法解决的问题也可以通过该算法高效地解决。
Feb, 2015
针对大型数据集中贪心算法的运行时间会非常高的问题,本文介绍了2种运用分布式计算和随机评估技术的更快逼近贪心向前选择算法,并且证明了弱次模性的泛化概念足以为这2种算法提供乘性逼近保证。同时,研究者还表明这些快速贪心逼近算法在人工数据和真实数据集上的性能要优于多个已有的基线算法。
Mar, 2017
使用预计算复杂性模型和记忆化的方式来优化大规模子模量优化问题,该方法在许多约束和非约束的子模量最大化,最小化,差异最小化问题中都适用,且在数据子集选择和摘要方面表现出了明显的加速效果。
Feb, 2019
本论文研究广义独立性、熵、互信息和总相关度等集合上的组合信息度量,这些度量通过子模函数进行参数化,严格推广了相应的熵度量。我们证明,对于大类满足一种非负性条件的子模函数,与另一个参数固定的情况下,子模互信息实际上是一种子模函数。我们将这种度量与分类,可靠分区和物品覆盖等问题联系起来。
Jun, 2020