Oct, 2023

通过链接实现内核密度估计的更强核心集界限

PDF
TL;DR应用偏差方法和串联方法提供改进的核函数广泛类别 Coreset 复杂性的界限，并给出对于高斯核和拉普拉斯核，在数据集均匀有界的情况下，产生 O (√d/ε√loglog (1/ε)) 大小的 Coreset 的随机多项式时间算法，这是以前的技术所不可能的改进。此外，对于恒定的 d，我们得到 O (1/ε√loglog (1/ε)) 大小的拉普拉斯核的 Coreset。最后，我们给出了指数核、Hellinger 核和 JS 核 Coreset 复杂性的最佳已知界限，其中 1/α 是核的带宽参数。
发现论文，激发创造
  • 核密度估计的近似最优核心集

    本文提出了一种能够有效构建 coresets 的方法，可以进行内核密度估计，特别适用于正定内核，且适用于机器学习中非常重要的信息距离和 sinc 内核。

    Feb, 2018

  • 基于统计学视角的 Coreset 密度估计

    该研究通过对 coresets 的研究，建立了一个统计框架，分析了非参数密度估计等任务的最小最大估计率，并表明实际 coreset 核密度估计器在很大程度上是接近最小最大优化的。

    Nov, 2020

  • 机器学习中的差异、核心集和草图

    该论文定义了函数族的类差异概念，并提出了一些技术来限制机器学习问题的班别差异，从而证明了高斯核密度估计的 coreset 复杂度存在 ε- 近似 O (sqrt {d}/epsilon) 的解法。除此之外，该论文还提供了两个与之相关的独立结果，提高了流式数据处理和核的低差异序列的发现。

    Jun, 2019

  • k 均值和 k 中位数聚类的核心集及其应用

    该研究的主要内容是利用 coreset 技术提高 k-means 和 k-median 聚类的近似算法，并且可以在流式数据中保持聚类结果。

    Oct, 2018

  • 针对聚类问题的近优量子核心集构建算法

    该研究在量子计算的框架下，提出了一种在时空复杂度上具有优势的 k - 聚类问题的量子算法，并在算法的基础上得到了一个核心集。

    Jun, 2023

  • 贝叶斯核心集质量的一般界限

    Bayesian coresets can speed up posterior inference by approximating the full-data log-likelihood function with a surrogate log-likelihood based on a small, weighted subset of the data. This paper provides general upper and lower bounds on the Kullback-Leibler divergence of coreset approximations, applicable in a wide range of models, and demonstrates the theory's flexibility in validation experiments involving multimodal, unidentifiable, heavy-tailed Bayesian posterior distributions.

    May, 2024

  • 多重 $\ell_p$ 回归的核心集

    通过构建核心集，我们实现了对多个响应的多元回归目标的近似，并得到了关于样本数量和子空间逼近的几乎最优的界限。

    Jun, 2024

  • 离线和流式 Coreset 构建的新框架

    本文提出一种改进的 coreset 构建方法，利用 sensitivity sampling 技术，并对 VC dimension 类的函数的采样复杂度进行分析，从而能够更加高效地解决包括聚类等在内的机器学习问题。

    Dec, 2016

  • 用于硬和软 Bregman 聚类的强核心集及其在指数族混合模型中的应用

    提出了一种使用 Bregman 差异构建强核心集的单一实用算法，可用于广泛的硬聚类和软聚类问题，并演示了该算法的实用性。

    Aug, 2015

  • 使用核心集降维海量稀疏数据集

    本文提出了一种解决大规模稀疏矩阵降维问题的实用方法，该方法使用核心集来近似计算矩阵的降维近似值，是计算低秩近似的有效算法。

    Mar, 2015