GIST：贪婪独立集合阈值用于多样数据摘要

May, 2024

GIST：贪婪独立集合阈值用于多样数据摘要

GIST: Greedy Independent Set Thresholding for Diverse Data Summarization

Matthew Fahrbach, Srikumar Ramalingam, Morteza Zadimoghaddam, Sara Ahmadian, Gui Citovsky...

TL;DR我们提出了一种新颖的子集选择任务，称为最小距离多样化数据汇总（MDDS），它在机器学习中有广泛的应用，例如数据采样和特征选择。我们介绍了 GIST 算法，它通过将一系列最大独立集问题近似为双准则贪婪算法来实现 MDDS 的 2/3 近似保证。我们还证明了对于任意 ε>0，存在一个补充的（2/3+ε）- 近似难度。最后，我们通过实证研究证明了 GIST 在合成数据上优于现有方法，并且对于一个真实的图像分类实验，GIST 用于 ImageNet 的单次子集选择也表现出色。

Abstract

We propose a novel subset selection task called min-distance diverse data summarization ($\textsf{MDDS}$), which has a wide variety of applications in machine learning, e.g., data sampling and →

min-distance diverse data summarization machine learning data sampling feature selection gist algorithm

发现论文，激发创造

公平且多样化的数据摘要核心集

我们研究了在公平性 / 分区约束条件下多样性最大化任务中的一种核心集构建算法。给定一个被划分为 m 组的度量空间中的点集 P，以及给定的每组 i 中的 ki 个点，该问题的目标是从每个组中选择 ki 个点，使得选择的 k 个点的整体多样性最大化。我们考虑了两种自然的多样性度量方法：对点对距离求和和对最近邻距离求和，并展示了针对这些度量方法的改进的核心集构建算法。具体而言，我们展示了第一种相对于点对距离求和而言大小与数据集大小和纵横比无关的核心集，同时我们还展示了第一个相对于最近邻距离求和而言的核心集。最后，我们进行了几个实验证明了我们的核心集方法的有效性。特别是，我们将约束的多样性最大化应用于一个考虑到消息的新旧的定时消息集的总结。具体而言，总结应该包含比较近期的消息而不是较早的消息。这是在一个最大的通信平台中的一个真实任务，每天活跃用户的体验都会受到影响。通过利用我们的核心集方法，我们实现了 100 倍的加速，只损失了少数百分比的多样性。此外，我们的方法还可以改进流式设置中算法的空间利用率。

Oct, 2023

基于不相似性的稀疏子集选择

本文提出了一种在计算机视觉、生物 / 健康信息学及图像和自然语言处理等领域中集合选择问题的求解方法，通过行稀疏的迹最小化问题的凸松弛，找到代表样本集，并赋予目标集合中的每个元素到代表样本的分配，实现集群化，并通过交替方向乘法法（ADMM）框架实现快速优化。实验证明，该算法在场景分类和时间序列建模和分割等问题上都具有优异的性能。

Jul, 2014

用最具信息量的项集简洁地总结数据

本文提出了一种基于最大熵模型的算法 MTV，该算法采用迭代更新的方式发现给定数据中最丰富的项目集合，从而构建出简洁但非冗余的数据摘要，并通过实验证明其有效性。

Apr, 2019

度量空间中有界倍增维度的多样性最大化的 MapReduce 和 Streaming 算法

该论文在关于点集的度量空间问题中，提出了一种基于流算法和 MapReduce 模型的高效多样性最大化算法，该算法通过核心集合和 α- 近似比的计算，能够在处理大量数据集时获得优秀的近似度。

May, 2016

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

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

Feb, 2024

最大独立集：动态规划自学习

本文提出了一种基于动态规划的图神经网络（GNN）框架来解决最大独立集（MIS）问题，通过递归算法构建子图并预测具有较大 MIS 的子图，进而在下一个递归调用中使用。我们通过对不同图形之间的 MIS 大小进行注释比较来训练算法，注释比较的输出结果用于自我训练过程，以提高注释比较的准确性。我们提供了在多个合成和真实数据集中证明我们算法优越性的数值证据。

Oct, 2023

最大和差异化，单调子模函数和动态更新

研究了一类问题，该问题的距离是一个度量，约束是一个 matroid 中的独立性，质量则由单调子模函数确定，多样性定义为 S 中物体之间的距离之和，提出了两种算法：基于基数约束的贪心算法和基于任意 matroid 约束的局部搜索算法，并证明了两种算法都达到了恒定的逼近比。

Mar, 2012

在线分布式数据选择的动态阈值法

通过子模最大化算法，我们设计了一个通用的、灵活的核心选择例程，可在使用最少内存的情况下从数据流中提取最有价值的子集，并在 ImageNet 和 MNIST 的学习任务中表现出了优于随机选择的性能

Jan, 2022

公正和多样化的基于 DPP 的数据概述

通过加入公平性约束条件，该文章提出了一种基于确定性多元分布的方法，并且使用了快速的抽样算法以产出多样化且公平的数据子集。

Feb, 2018

使用不完备最大均值差异估计器的后选择推论

本论文提出了一种基于 PSI 框架的分布差异度量方法，使用最大平均离差（MMD）的加性变体来确定特征并引入了一般的假设测试方法。通过合成和真实世界的特征选择实验，我们发现所提出的框架可以成功地检测出具有统计显著性的特征，并提出了一个用于分析 GAN 系列中不同成员的样本选择框架。

Feb, 2018