找回密码
立即注册
搜索
发回帖 发新帖

6797

积分

0

好友

861

主题
发表于 6 小时前 | 查看: 0| 回复: 0

70 年的老算法 k-means 活跃在向量量化、检索索引和数据清洗等场景中,但大规模任务仍要反复扫描全部数据。

e-means 论文标题页:outperforming k-means in one-tenth the epochs

Meta 把 mini-batch、EMA(指数移动平均)和缩放定律重新组合,提出了 e-means。它只用 1.4~2.6 个 epoch,就达到了 Flash-KMeans 跑 25 轮的测试误差,墙钟时间最高加速 45.5 倍。

e-means 与 Lloyd 算法聚类对比的在线演示,右侧为训练 MSE 随轮数下降的曲线

这次改进并不只是优化 GPU 内核,而是改写了优化过程本身:收敛更快,最终误差还更低。

代码已开源,位于 Faiss 仓库的 contrib/e_means 目录。

Faiss 仓库 contrib/e_means 目录的文件列表

01 老算法的瓶颈:快与准难兼得

经典的 Lloyd k-means 每轮执行两步:先把全部样本分给最近的质心,再按归属重新计算均值。流程稳定,但每一轮都要对全量数据计算,通常需要多轮才能收敛。

mini-batch 版本能让误差更早下降,却常常停在更高的损失上。e-means 要解决的,正是这种速度与精度之间的取舍。

e-means 与 Faiss-GPU、Flash-KMeans 在 DINO10B 上的损失曲线与 GPU 耗时对比

图 1:e-means 的收敛速度与 GPU 耗时

图 1 左侧显示,在 DINO10B(1024 维)数据集上,e-means 只用约 2 轮,测试损失就低于两种 k-means 实现跑 25 轮的结果。右侧给出了不同数据规模下的累计 GPU 时间,e-means 在各规模下都更省时。

02 核心改动:把全量均值换成 EMA 更新

e-means 不再等一整轮结束才移动质心,而是每处理一个 batch 就更新一次,具体分为五步:

  • 先分配:样本仍归入最近的质心。
  • 再滑动平均:分别更新各簇的计数 N 与向量求和 S,质心随时按 c = S/N 读出。
  • 逐步降温:步长采用余弦衰减,前期移动快,后期更稳定。
  • 救活死簇:每 5 个 batch 检查一次低计数簇,通过拆分供体簇让它重新被利用。
  • 最后收尾:训练误差取末轮均值,泛化误差用慢速 EMA,额外开销很小。

e-means 各组件消融实验表:余弦调度、死簇复活、收尾、慢速 EMA 与 k-means++ 初始化

表 1:e-means 各组件的消融实验

哪个组件最关键?消融结果指向死簇复活。去掉它,训练 MSE 上升 2.97%,测试 MSE 上升 2.24%。k-means++ 初始化虽然略有收益,但顺序计算成本高,所以默认仍使用随机初始化。

03 不用扫参:把批大小和步长交给公式

以往 mini-batch 方法好不好用,很依赖调参。作者用 7.5 万次优化运行拟合了两条缩放定律,只需输入样本数 n、簇数 k、轮数 T 和批大小 B,就能自动给出峰值步长与批大小。

步长与批大小缩放定律的拟合曲线族:左为不同批大小下的最优步长,右为不同轮数预算下的批大小拐点

图 2:步长与批大小的缩放定律

图 2 左侧是步长的低谷:步长太小会欠训练,太大则不稳定。右侧用来找批大小的拐点,判定标准是误差比自身最低点高出不超过 0.2%。在留出数据集上,这条规则带来的额外 MSE 中位数为 0.19%,与设计目标接近。

这意味着调参不再靠反复试错,而是按问题规模直接计算。

04 45 倍怎么来的:是最高值,不是平均值

实验统一比较达到 Flash-KMeans 25 轮测试 MSE 所需的时间。e-means 只需 1.4~2.6 轮,对应 9.5~45.5 倍的墙钟加速。

不同数据规模和数据集上,e-means 达到 Flash-KMeans 25 轮误差所需的轮数与墙钟加速比

表 4:不同数据规模下的轮数与墙钟加速比

标题中的 45 倍来自 10 亿向量、1,048,576 个簇的 DINO10B 配置:e-means 用 1.6 轮达到基准误差,墙钟加速 45.5 倍。

看这组数字时要留意实验口径。1M~100M 规模取的是 10 个种子的中位数,1B 规模只有单个种子的结果,并且使用了 8 张 GPU。因此,45.5 倍是特定配置下的最高结果,不能理解为所有任务都能快 45 倍。

05 不只是跑得快,收敛质量也更好

如果只在早期领先,mini-batch 的老问题就没有真正解决。作者因此进一步比较了完全收敛后的损失分布,并加入了使用 k-means++ 初始化的 Lloyd 基线。

三个数据集上 40 个随机种子的训练与测试失真分布,对比 e-means 与 Lloyd 的不同初始化

图 5:40 个随机种子下的收敛损失分布

图 5 覆盖 AG-News、arXiv 和 SPACEV 三个数据集,每个数据集 40 个随机种子。无论看训练误差还是测试误差,随机初始化的 e-means 都落在更低的区间,甚至优于带 k-means++ 初始化的 Lloyd。

这篇论文真正的突破,不在于单独换上 EMA,而是把 EMA、步长调度、死簇复活、自动配参和 GPU 实现做成了一套完整方案。

它也有适用边界:缩放定律主要面向高维嵌入,在极低维或超小数据集上不一定最优。对向量检索、量化和亿级数据聚类来说,e-means 更像一次可以直接落地的优化器升级,而不只是一项跑分纪录。

论文信息

  • 论文:e-means: outperforming k-means (in one-tenth the epochs)
  • 作者:Swann Bessa、Pierre-Emmanuel Mazaré、Gergely Szilvasy、Hugo Touvron、David Picard、Matthijs Douze、Hervé Jégou
  • 单位:FAIR at Meta,École Nationale des Ponts et Chaussées
  • arXiv:2611.09501



上一篇:科研 Skills 索引:206 套工具覆盖论文写作与绘图
下一篇:RTX 5060游戏本650美元入手:百思买开箱机配置与价格
您需要登录后才可以回帖 登录 | 立即注册

关闭

站长推荐上一条 /1 下一条

手机版|小黑屋|网站地图|云栈社区 ( 苏ICP备2022046150号-2 )

GMT+8, 2026-11-21 15:31 , Processed in 1.291050 second(s), 47 queries , Gzip On.

Powered by Discuz! X3.5

© 2025-2026 云栈社区.

快速回复 返回顶部 返回列表