返回资讯中心
外部精选
软件工程
#社区热议

e-means:损失相同时 k-means 速度提升 10 倍

来源标题:E-means: 10x faster k-means at equal loss

e-means 在同等或更低损失下,将 k-means 聚类速度提升 10–45 倍。在 GPU 上,它相比 Flash-KMeans 端到端快 10–45 倍;在 CPU 上,相比 Faiss 快 8–15 倍。该方法在大范围规模与数据集上,用 1.2–3 个 epoch 即达到 Lloyd 算法 25 个 epoch 的测试损失。

Hacker Newsporridgeraisin2026/11/9 · 8 天前15 分钟阅读

以下正文由 AI 翻译自 Hacker News(原文版权归原站所有),可能存在偏差,重要内容请以原文为准。

10万个数据点分布在200个簇中,包含两个宽高斯分布和三个小高斯分布,在均匀浅色背景上被一个矩形框截断。Lloyd 每轮有1次更新,而 e-means 每轮有97次。

在大量不同的规模和数据集上,e-means 在1.2到3个epoch内就能达到Lloyd在25个epoch时的测试损失以下。端到端测量显示,在GPU上相比最先进的Lloyd实现(Flash-KMeans[2]),实际耗时减少10–45倍;在CPU上相比Faiss[1]减少8–15倍。在k-means中,速度和通常质量相互制约,而e-means同时实现了更好的速度和更低的损失。

给定一个包含n个点的固定数据集 X = {x1, ..., xn} ⊂ Rd 和一个整数k,k-means问题是找到k个质心 C = (c1, ..., ck),使得每个点到其最近质心的均方距离最小:

这是一个静态数据集,不同于VQ-VAE内部的码本学习,那里要聚类的分布是不断变化的。

e-means的目标是为k-means问题提供一种现代化的优化规则。我们从以下观察出发启动了这个项目:

对于e-means,我们选择使用指数移动平均[6]进行小批量更新,我们发现这对k-means问题最为高效。与之前的小批量方法不同,e-means不需要超参数调优,因为它通过缩放定律自动设置批量大小和步长(见使用缩放定律的自动超参数调优)。此外,e-means改进了初始化和死簇复活策略,增加了余弦调度的衰减率,并引入了一个最终化阶段,在训练结束时以可忽略的运行时开销降低训练损失。e-means高度可并行化,并附带专门的内核,将其算法优势转化为实际耗时加速。

每个小批量更新每个簇的计数和总和。质心是它们的比值。

新质心批量均值 无超参数调优 一切由缩放定律推导。 log n, log k, log T 开始与结束 新颖的初始化和最终化方法。运行结束时每个簇取其最后一轮的精确均值。 开始精确均值 余弦调度 步长α从α0退火到0.1α0,如同学习率一样。 α₀0.1 α₀ 死簇复活 大小低于阈值的簇通过分裂一个大簇来复活。 大簇一分为二 专用内核 GPU内核融合了最近质心分配,将上述epoch节省转化为匹配的实际耗时加速。

质心更新规则是e-means的核心组件。本节旨在概述k-means聚类的更新规则。所有方法都为每个簇j维护一个总和Sj和一个计数Nj,即分配给该簇的点的统计量,并取它们的比值作为质心:

它们仅在Sj和Nj的更新方式上有所不同。下面,sj和nj表示当前批次中分配给簇j的点的总和与计数(如果没有则为零)。

Lloyd算法[7]将每个点分配到其最近质心,并从头重新计算统计量,使用完整数据集作为批次:

因此cj是当前分配给它的点的精确均值。每次更新需要对数据做一次完整遍历,该过程重复固定次数(通常为20到50次迭代)。

MacQueen的更新[3]累积统计量而从不丢弃:

因此cj是自训练开始以来分配给簇j的每个点的均匀均值,包括在早期可能较差的质心位置下分配的点。后来Staleness-Reduction Mini-Batch K-Means[8]部分解决了这个问题,这是一种介于k-means和MacQueen之间的混合方法。他们获得了显著的加速,但仅在非常少的簇数量上。

e-means在小批量上工作,并用指数移动平均替代这个求和:

因此较早的分配以速率α被遗忘,质心跟踪最近的分配而非整个历史。这种更新规则通常用于移动分布,因此被用于训练VQ-VAE[6]。我们发现,如果与e-means的其他组件结合并正确调优超参数,它对静态数据集也非常高效。

e-means项目始于Meta FAIR的Hugo Touvron和Hervé Jégou的先前工作,他们发现通过梯度下降的小批量k-means可以胜过Lloyd算法。虽然我能复现这些结果,但我发现基于梯度下降的质心更新在大学习率下性能不稳定, unlike指数移动平均更新。我怀疑这是因为EMA更新保证质心始终位于分配给它的点的凸包内,而梯度下降更新可能超出该凸包。

为了在固定epoch数下达到最低损失,我们选择指数移动平均更新,因此我们的方法命名为e-means。

如果将批次设为完整数据集,B = n,且α = 1,那么Nj和Sj就恰好变成整个簇的计数和总和,因此一次e-means迭代就恰好变成一次Lloyd迭代。Lloyd是e-means在没有学习率余弦调度时的极端情况。然而,我们的超参数搜索发现这种极端设置高度次优,这解释了为什么e-means在很大程度上优于Lloyd。下面,对每个批量大小B和步长α测量损失:Lloyd落在一个角落里,远在损失最低区域之外。

这项超参数研究促使我们推导缩放定律,自动选择最优的批量大小B和步长α。

(原文较长,此处译出前 6000 字,完整内容请点「打开原文」。)

正文由 探How 从来源站点 RSS 同步,内容未经改写;遇到排版缺失或需要图片、视频时请以原文为准。

打开原文
去社区讨论 →