随机组合核心集用于匹配和顶点覆盖
在此论文中,我们研究和改善了基于随机聚类的可组合核心集的构建方法,并将其应用于在计算复杂度受限制的分布式和流式处理设置下的覆盖和子模极大化问题,并采用改进的分析技术和新算法提出了首个能够在恒定轮数下打败因子 1/2 的 MapReduce 算法。
Jun, 2015
基于 Common randOm REconstruction (CORE) 技术,本研究提出了一种可以压缩传输信息、降低通信复杂度的分布式机器学习算法,并通过应用于线性模型和非凸优化等分布式任务,设计了新的具有更低通信复杂度的分布式算法。
Sep, 2023
本文研究 coresets 和机器学习领域中的最新进展,提出了一种理论上可行的框架来创建分类问题的 coresets,应用到了 $k$-means 聚类问题,同时总结了当前在 MLE 混合模型、贝叶斯非参数模型、主成分分析、回归和经验风险最小化等领域中已有的 coreset 构建算法。
Mar, 2017
我们研究了在公平性 / 分区约束条件下多样性最大化任务中的一种核心集构建算法。给定一个被划分为 m 组的度量空间中的点集 P,以及给定的每组 i 中的 ki 个点,该问题的目标是从每个组中选择 ki 个点,使得选择的 k 个点的整体多样性最大化。我们考虑了两种自然的多样性度量方法:对点对距离求和和对最近邻距离求和,并展示了针对这些度量方法的改进的核心集构建算法。具体而言,我们展示了第一种相对于点对距离求和而言大小与数据集大小和纵横比无关的核心集,同时我们还展示了第一个相对于最近邻距离求和而言的核心集。最后,我们进行了几个实验证明了我们的核心集方法的有效性。特别是,我们将约束的多样性最大化应用于一个考虑到消息的新旧的定时消息集的总结。具体而言,总结应该包含比较近期的消息而不是较早的消息。这是在一个最大的通信平台中的一个真实任务,每天活跃用户的体验都会受到影响。通过利用我们的核心集方法,我们实现了 100 倍的加速,只损失了少数百分比的多样性。此外,我们的方法还可以改进流式设置中算法的空间利用率。
Oct, 2023
提出了一种轻量级 coresets 算法,用于 k-means 聚类和 Bregman 聚类,能同时允许乘性和加性误差,在计算效率和结果集大小方面优于现有方法,并可用于统计 k-means 聚类的计算小型模型的摘要。
Feb, 2017
该文章提出了一种稳健的 coreset 构建算法,在中心化和分布式框架下生成符合一定理论条件的 coreset,以支持各类机器学习问题的高效求解。实验证明该算法具有较强的健壮性。
Apr, 2019
本文研究公平聚类问题,提出一种利用核心集合来显著减小输入数据规模的算法,证明了核心集合的可组合性,提出了 Lloyd 算法的变体,并将其扩展为公平 k-means ++ 聚类算法,实现了这些算法并提供了经验证据,表明我们的方法得以规模化运行。
Dec, 2018
通过在具有大量服务器的大型输入数据库上计算关系查询来解决分布式计算中通信协议的瓶颈,并且在单个和多个通信步骤中建立了下限,同时其下限证明了任何算法需要 epsilon 大于等于 1-1/tau*,同时结果也蕴含了不能在 O(1)个通信步骤内计算传递闭包。
Jun, 2013
本文提出了一种基于编码计算的分布式图处理框架,通过结构性冗余注入来在消息交换时实现编码的多播机会,从而大规模减少了通信负载,理论分析证明该方案在两种流行的随机图模型(Erdos-Renyi 模型和幂律模型)中实现了计算负载和平均通信负载之间的(近似)反比例线性折衷,实验结果表明该方案在 PageRank 计算中具有显着提高。
Jan, 2018