可组合核心集应用于行列式最大化的简单近优算法
利用贪心算法提供具有几乎最优逼近因子 O (k)^{3k} 的组合核心集,以支持一种名为 “确定最大化” 的确定点过程地图推理任务。
Sep, 2023
在此论文中,我们研究和改善了基于随机聚类的可组合核心集的构建方法,并将其应用于在计算复杂度受限制的分布式和流式处理设置下的覆盖和子模极大化问题,并采用改进的分析技术和新算法提出了首个能够在恒定轮数下打败因子 1/2 的 MapReduce 算法。
Jun, 2015
介绍了一种用于构建可组合核心集合的核心集合构建算法,用于总结用于活动学习环境的流数据,结合技术如 CRAIG 和启发式方法以增强构建速度,可以在大数据传感器数据量较大时实时训练模型。通过考虑外推数据进行这种蛮力算法的运行时间性能经验分析,并通过平均经验回归进行效率分析,提出了关键结果和改进方向以便进一步研究该主题。
Aug, 2023
本文提出了使用 log-determinants 和 stochastic trace estimators 的两种逼近方案来使得贪心算法更快速,从而解决大规模 determinantal point processes 的 MAP 问题。实验表明,该算法在不牺牲较少精度的情况下比其竞争对手快数个数量级。
Mar, 2017
我们研究了在公平性 / 分区约束条件下多样性最大化任务中的一种核心集构建算法。给定一个被划分为 m 组的度量空间中的点集 P,以及给定的每组 i 中的 ki 个点,该问题的目标是从每个组中选择 ki 个点,使得选择的 k 个点的整体多样性最大化。我们考虑了两种自然的多样性度量方法:对点对距离求和和对最近邻距离求和,并展示了针对这些度量方法的改进的核心集构建算法。具体而言,我们展示了第一种相对于点对距离求和而言大小与数据集大小和纵横比无关的核心集,同时我们还展示了第一个相对于最近邻距离求和而言的核心集。最后,我们进行了几个实验证明了我们的核心集方法的有效性。特别是,我们将约束的多样性最大化应用于一个考虑到消息的新旧的定时消息集的总结。具体而言,总结应该包含比较近期的消息而不是较早的消息。这是在一个最大的通信平台中的一个真实任务,每天活跃用户的体验都会受到影响。通过利用我们的核心集方法,我们实现了 100 倍的加速,只损失了少数百分比的多样性。此外,我们的方法还可以改进流式设置中算法的空间利用率。
Oct, 2023
对于一种新颖的分区约束 DPPs,我们提出了第一个多项式时间的算法,以在约束下准确地从中进行抽样,并发现这种方法比 k-DPPs 和其朴素扩展提供更多的灵活性和多样性。同时,我们通过实验发现,简单的贪心初始化和局部搜索可以提高从 k-DPPs 的 MAP 推断问题的近似保证,特别是在较大的 k 下。
Jul, 2016
本研究证明,匹配问题和点覆盖问题在同时通信模型中的不可承受性根源于基础图形跨机器的对抗性分区,进而展示这两个问题存在随机组分的可组合核的对数 O (n)。
May, 2017