机器学习中的差异、核心集和草图
应用偏差方法和串联方法提供改进的核函数广泛类别 Coreset 复杂性的界限,并给出对于高斯核和拉普拉斯核,在数据集均匀有界的情况下,产生 O (√d/ε√loglog (1/ε)) 大小的 Coreset 的随机多项式时间算法,这是以前的技术所不可能的改进。此外,对于恒定的 d,我们得到 O (1/ε√loglog (1/ε)) 大小的拉普拉斯核的 Coreset。最后,我们给出了指数核、Hellinger 核和 JS 核 Coreset 复杂性的最佳已知界限,其中 1/α 是核的带宽参数。
Oct, 2023
本文提出一种改进的 coreset 构建方法,利用 sensitivity sampling 技术,并对 VC dimension 类的函数的采样复杂度进行分析,从而能够更加高效地解决包括聚类等在内的机器学习问题。
Dec, 2016
使用核心集理论应用于 logistic 回归模型的研究,提出一个统计学上解释直观的复杂度度量方法,并发展了一个新的灵敏度采样方案来处理 logistic 回归中的大量数据,并在真实世界的 logistic 回归基准数据上比较了其性能。
May, 2018
本文研究 coresets 和机器学习领域中的最新进展,提出了一种理论上可行的框架来创建分类问题的 coresets,应用到了 $k$-means 聚类问题,同时总结了当前在 MLE 混合模型、贝叶斯非参数模型、主成分分析、回归和经验风险最小化等领域中已有的 coreset 构建算法。
Mar, 2017
通过敏感采样框架,我们对用于分类问题的核心集进一步细化和泛化。这种核心集寻求输入数据的最小可能子集,以便可以在核心集上优化损失函数,并且能够保证与原始数据的逼近保证。我们的分析提供了首个维度无关的核心集,因此大小不依赖于维度。此外,我们的结果很通用,适用于分布式输入,可以使用独立同分布的样本,从而提供了样本复杂度的边界,并且适用于各种损失函数。我们开发的一个关键工具是主要敏感采样方法的一个 Radamacher 复杂度版本,这可能是独立感兴趣的。
Feb, 2024
提出了一种使用 Bregman 差异构建强核心集的单一实用算法,可用于广泛的硬聚类和软聚类问题,并演示了该算法的实用性。
Aug, 2015
给定一种数据矩阵和标签向量,我们使用基于 $l_1$ 拉索 (weight) 的数据子采样方法构建相对误差 Coresets,用于训练包括逻辑损失和铰链损失在内的一系列损失函数的线性分类器,其结果不仅在理论上得到了显著提高,而且在实践中表现优异,可用于主动学习并用于多种训练方案。
Jun, 2021
该文章提出利用 coresets 的方法来对高斯混合模型进行计算,这种方法可以在保证训练精度的情况下减少数据量从而加快计算速度,经验结果表明,该方法可以显著减少训练时间而近似误差可以忽略不计。
Mar, 2017
该文章提出了一种稳健的 coreset 构建算法,在中心化和分布式框架下生成符合一定理论条件的 coreset,以支持各类机器学习问题的高效求解。实验证明该算法具有较强的健壮性。
Apr, 2019