Mar, 2017

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

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

    通过连接高维度的子集选择和子模块化最大化，提出一种可以直接控制特征数目的贪心算法，将标准设置下的回复保证带入一般客观函数中，并在统计上达到可接受的性能。同时，我们的课题为组合结构的统计学习应用提供了独立的兴趣联系点。

    Dec, 2016

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

    本文提出了一种随机贪心算法来最大化弱次模函数在一般拟阵约束下的值，其中距离次模性的距离由参数 γ 衡量，该算法在实践中表现良好，并且是第一个能够约束弱次模函数最大化具有非平凡逼近保证的算法。

    Jul, 2017

  • 子模遇上谱：子集选择、稀疏逼近和字典选择的贪心算法

    本研究通过分析子模函数的最大化和谱分析的见解，引入了子模性比率作为一种关键性质，研究了从大量随机变量中选择 k 个变量的问题，以实现对另一个感兴趣的变量的最佳线性预测，取得了这个问题方面最强的现有近似保证，并运用了该技术进行了实验和分析。

    Feb, 2011

  • 弱次模函数

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

    Jan, 2014

  • 分布式基于配对次模函数的大于内存子集选择

    通过提出一种新颖的分布式界限算法，并使用多轮基于分区的分布式贪心算法，此论文解决了子集选择问题，能够在没有或极小损失质量的情况下，找到高质量的子集。

    Feb, 2024

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

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

    Feb, 2015

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

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

    Feb, 2020

  • 重新审视匹配追踪：超越近似子模性

    通过引入期望下具有子模性的函数，我们解决了从大量向量中选择子集问题。该函数的引入不仅在预期意义下通过贪心算法保证了接近最优，而且缓解了通常使用的匹配追踪算法的缺陷。同时，我们还探究了该贪心算法和匹配追踪算法之间的关系，并通过角度到达估计问题的数值实验证明了这种方法相对于传统的匹配追踪算法的优势。

    May, 2023

  • 分布式子模最大化

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

    Nov, 2014

  • 懒惰比贪心更懒惰

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

    Sep, 2014