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