次模性和成对独立性
本研究扩展了Narasimhan和Bilmes的工作,提出了基于子模函数差别最小化的新算法,该算法能有效地解决多种组合约束的问题,并且能够用于许多机器学习问题中,它在性能上优于现有的算法。
Jul, 2012
本文研究了次模函数及其在凸优化和概率测度方面的应用,提出了连续化的概率测度拓展方式,利用多重边际最优传送理论对次模集函数情况下的推论进行了拓展,最终给出了离散域中通用次模函数的实际最小化算法及其收敛速率。
Nov, 2015
本文考虑在噪声下最大化单调子模函数,探讨在噪声和误差存在的情况下,是否能获得算法的可证明保证,结论是对于基数约束k>=2的函数,有一个近似算法,其近似比例任意接近1-1/e;对于基数约束k=1,有一种算法,其近似比率任意接近于1/2。没有随机算法可以获得比1/2+o(1)更好的近似度;如果噪声是对抗性的,则不能获得任何非平凡的近似保证。
Jan, 2016
通过连接高维度的子集选择和子模块化最大化,提出一种可以直接控制特征数目的贪心算法,将标准设置下的回复保证带入一般客观函数中,并在统计上达到可接受的性能。同时,我们的课题为组合结构的统计学习应用提供了独立的兴趣联系点。
Dec, 2016
针对大型数据集中贪心算法的运行时间会非常高的问题,本文介绍了2种运用分布式计算和随机评估技术的更快逼近贪心向前选择算法,并且证明了弱次模性的泛化概念足以为这2种算法提供乘性逼近保证。同时,研究者还表明这些快速贪心逼近算法在人工数据和真实数据集上的性能要优于多个已有的基线算法。
Mar, 2017
本文提出了一种随机贪心算法来最大化弱次模函数在一般拟阵约束下的值,其中距离次模性的距离由参数γ衡量,该算法在实践中表现良好,并且是第一个能够约束弱次模函数最大化具有非平凡逼近保证的算法。
Jul, 2017
通过直接优化偏差和方差的组合,该研究通过展示如何进行具有理论保证的高效算法,从而在次模函数中进行分布式鲁棒优化(DRO),从而实现在未知随机次模函数的情况下实现更好的性能和更好的推广。
Feb, 2018
本文研究次模函数的优化和算法问题,提出了一种在 $k$-cardinality 约束下最大化 $g-c$ 的算法,并通过实验设计对其进行了验证。
Apr, 2019
本论文研究广义独立性、熵、互信息和总相关度等集合上的组合信息度量,这些度量通过子模函数进行参数化,严格推广了相应的熵度量。我们证明,对于大类满足一种非负性条件的子模函数,与另一个参数固定的情况下,子模互信息实际上是一种子模函数。我们将这种度量与分类,可靠分区和物品覆盖等问题联系起来。
Jun, 2020