本期速览
Meta FAIR 团队推出 e-means,仅修改 K-Means 的聚类中心更新规则为指数移动平均(EMA),将达到同等聚类质量所需的训练轮次压缩至原有的十分之一,在 10 亿向量实验中实际耗时加速 45.5 倍,且误差不增反降。该方法通过幂律公式自动化超参数选择,结合融合核函数、死簇复活等工程优化,大幅降低大规模向量检索的索引重建成本。
为你解答
PRO members can sign in and request more information — or their own version of this digest, tuned to what they care about.
Sign in to unlock意想不到的发现
Lloyd 算法单调下降的训练误差反而让它更容易卡在糟糕的局部最优,而小批量的随机噪声反倒给了 e-means 修正的机会。
仅在 DEEP 一个数据集上拟合的幂律超参数公式,能迁移到图像、文本等多种高维数据集并接近最优表现,尽管数据的内在维度事前未知。
e-means 甚至不需要 k-means++ 初始化就能超越 Lloyd,因为 k-means++ 是串行的、难以并行,在大规模下收益抵不上成本。
本期要点
e-means 保留经典 K-Means 目标函数,改用 EMA 维护每个簇的样本计数与向量和,中心点由两者比值得出,使早期快速适应、后期平稳收敛,避免了小批量方法累积陈旧统计量的问题。
EMA 衰减率采用余弦退火调度,训练结束可用最后一轮分配结果零成本重算中心点降低训练误差;若面向新数据,可额外挂载更慢的 EMA 提升泛化,两套中心可同时产出。
死簇复活机制每 5 个批次检查一次,将样本数低于阈值的中心从最大簇拆分而来;消融实验显示,关闭该机制会导致 26.3% 中心分到不足 10 个样本,开启后仅 0.3%。
小批量带来的随机波动帮助 e-means 跳出劣质局部最优:在大小悬殊的两团数据上,Lloyd 有 26% 运行陷入不良分组,e-means 仅 3.5%;五团线性分布数据上,Lloyd 失败率 46%,e-means 为 0%。
超参数(批次大小、学习率)由在 DEEP 数据集上拟合的两条幂律公式给出,迁移至 SIFT、SPACEV、文本向量等数据集时,中位误差仅比逐数据集调优高出 0.19%,基本免去了超参搜索。
在 100 亿 DINO 向量(1677 万簇)实验中,e-means 仅用 2.5 轮(779 GPU 小时,32 台机器)即达到 Flash-KMeans 25 轮(6784 GPU 小时,64 台机器)的误差,且最终误差更低。
工程层面采用分块处理中心、融合距离计算与最近邻选择、低精度(BF16/FP8/INT8)分配、百万级簇时引入 IVF 近似,算法与系统层面的加速叠加造就了最终速度提升。
精彩语录
“K-Means 大概是机器学习里最不起眼的算法了”
▸ 精彩语录 · 0:03“目标函数一个字没动,只是重写了聚类中心的更新方式,就将达到同等聚类质量需要的训练轮次压到了原来的十分之一左右”
▸ 精彩语录 · 0:24“在 10 亿条向量的实验里,实际耗时快了 45.5 倍”
▸ 精彩语录 · 0:34“它把 K-Means 的更新当成了一种硬分配的 EM,只是统计量带了衰减”
▸ 精彩语录 · 3:30“调参也被省掉了”
▸ 精彩语录 · 7:04“少一轮是算法层面的事,而少一次显存读写是系统层面的事,两个叠加才有了最后那个数字”
▸ 精彩语录 · 11:12章节
0:00 — 引言与动机: 主持人介绍 K-Means 这一古老却无处不在的算法,Meta FAIR 的 e-means 仅重写中心更新规则,便将所需轮次压至十分之一、十亿向量实验加速 45.5 倍。
1:01 — 经典 Lloyd 算法及其瓶颈: 解释 Lloyd 双步循环(分配、重算均值)及其每轮线性扫描成本;Faiss 默认 25 轮在 100 亿规模下需数千 GPU 小时。
2:03 — 小批量 K-Means 及其未解难题: 回顾 MacQueen 和 Sculley 的小批量工作,指出其累积陈旧统计量、最终误差较高、批次与步长需逐数据集手动调优的问题。
3:00 — e-means:基于 EMA 的中心更新: 详述 e-means 对每簇计数与向量和做 EMA、衰减率调度、与硬分配 EM 的联系,以及相对 SGD 保持中心在凸包内的优势。
4:26 — 跳出局部最优与死簇复活: 展示随机波动帮助 e-means 逃离劣质局部最优(两团数据 Lloyd 失败 26% vs e-means 3.5%),并详述每 5 批次从大簇拆分复活死簇的机制。
6:18 — 训练稳定化与收尾打磨: 涵盖微权重随机初始化、余弦退火学习率、零成本最终重算中心、可选的慢速 EMA 用于泛化。
7:04 — 幂律公式自动化超参数选择: 作者在 DEEP 上跑 7.5 万次实验拟合批次与学习率幂律,迁移至 SIFT、SPACEV、文本向量中位误差仅增 0.19%,基本免调参。
8:52 — 大规模实验与检索影响: 报告 100 万到 100 亿规模上 9.5–45.5 倍加速、误差低于 Lloyd 与 Flash-KMeans;100 亿 DINO 向量 2.5 轮达标;IVF 近似进一步降本;同等训练时间下召回率更高。
出场人物
大飞 — Host