Jul, 2017

超越基数约束的弱次模最大化：贪心法是否受益于随机化？

PDF
TL;DR本文提出了一种随机贪心算法来最大化弱次模函数在一般拟阵约束下的值，其中距离次模性的距离由参数 γ 衡量，该算法在实践中表现良好，并且是第一个能够约束弱次模函数最大化具有非平凡逼近保证的算法。
submodular functionsweakly submodular functionsmaximizationgeneral matroid constraintapproximation ratio
发现论文，激发创造
  • 非子模函数的贪心最大化保证及应用

    研究了 Greedy 算法在非子模不减集函数基数约束最大化中的性能，并证明了在一些重要的非子模函数如贝叶斯 A - 最优目标函数中，该算法具有很强的经验性能。我们以广义曲率 α 和子模性比率 γ 的组合为特点，证明了其理论保证，特别地，对于基数约束最大化，我们证明了 Greedy 算法具有紧密的近似保证为 1/α(1-e^(-γα))。另外，我们还限制了在几个重要的真实世界目标中子模性比率和曲率，包括贝叶斯 A - 最优目标、方形子矩阵的行列式函数和具有组合约束的某些线性规划。

    Mar, 2017

  • 弱次模函数

    本文研究了弱次模函数的性质及优化问题，其中包括了一些次超模函数，并提出了在均匀和一般性拟阵约束下最大化弱次模函数的优化问题，在此问题中，我们证明了标准贪心算法和简单局部搜索算法的算法近似比分别为 5.95 和 10.22。

    Jan, 2014

  • 超模极大化 —— 非非负性保证、快速算法和应用

    本文研究次模函数的优化和算法问题，提出了一种在 $k$-cardinality 约束下最大化 $g-c$ 的算法，并通过实验设计对其进行了验证。

    Apr, 2019

  • 懒惰比贪心更懒惰

    本文提出了一种线性时间算法 STOCHASTIC-GREEDY 用于求解一般性单调子模函数最大化问题，旨在实现对数据的概括，比传统算法 lazy greedy 更快且表现基本一致。

    Sep, 2014

  • 弱次模可扩展的贪心特征选择

    针对大型数据集中贪心算法的运行时间会非常高的问题，本文介绍了 2 种运用分布式计算和随机评估技术的更快逼近贪心向前选择算法，并且证明了弱次模性的泛化概念足以为这 2 种算法提供乘性逼近保证。同时，研究者还表明这些快速贪心逼近算法在人工数据和真实数据集上的性能要优于多个已有的基线算法。

    Mar, 2017

  • 噪音下的次模优化

    本文考虑在噪声下最大化单调子模函数，探讨在噪声和误差存在的情况下，是否能获得算法的可证明保证，结论是对于基数约束 k>=2 的函数，有一个近似算法，其近似比例任意接近 1-1/e; 对于基数约束 k=1，有一种算法，其近似比率任意接近于 1/2。没有随机算法可以获得比 1/2+o (1) 更好的近似度；如果噪声是对抗性的，则不能获得任何非平凡的近似保证。

    Jan, 2016

  • 贪心算法的不合理有效性：贪心算法适应尖锐度

    通过定义锐度作为子模函数改善贪心算法性能的候选解释，本文探讨了贪心算法在最大化单调子模函数下的性能问题，显示子模函数的锐度影响贪心算法的表现，通过计算实验和理论结果，支持本文的说法。

    Feb, 2020

  • 分布式子模最大化

    本文提出了一种适用于分布式计算的子模函数最大化方法 GreeDi，该方法可在 MapReduce 框架下实现，初步实验表明该方法可应用于大规模机器学习任务中的子模优化问题，如稀疏高斯过程推断和样例聚类等问题，且在一定的自然条件下，可以达到接近于传统集中式计算模式下的性能表现。

    Nov, 2014

  • 子模最大化问题的确定性算法

    证明了在许多计算机科学中随机化的作用，以及针对次模函数最大化领域的一种新的去随机化算法技术

    Aug, 2015

  • 贪心最小化弱超模集合函数

    本文定义了集合函数的弱 α 超模性，证明了在基数约束下最小化此类函数问题中的贪婪扩展阶段的优点，并给出了在此框架下的 $k$-means，稀疏回归和列子集选择的新的双标准结果。

    Feb, 2015