e-means 算法将十亿级嵌入聚类所需轮次降至传统 k-means 的十分之一

我用过也研究过很多次 k-means，所以 e-means 引起了我的注意。它解决的是同一个熟悉的问题：选出 k 个质心，让每个点到最近质心的平方距离之和最小。有意思的地方在于它达到目标要快多少。

论文报告称，把 100 亿个 DINO embedding 聚成大约 1670 万个簇，只用了 2.5 个 epoch，就达到了标准全批量 k-means 在 25 个 epoch 时的测试损失。也就是说，对训练点的遍历次数只有后者的十分之一。

标准全批量 k-means 会先把整个数据集分配给质心，然后再更新质心。e-means 则在每一轮遍历中持续更新，使用 mini-batch，并对每个簇的计数和求和采用指数移动平均。较早的分配会逐渐失去权重。

Mini-batch 和移动平均早已存在。它的贡献在于围绕这两者的一套配方：衰减的更新调度、改进的初始化、通过拆分活跃簇来复活使用不足的质心，以及一个收尾步骤。拟合出的 scaling law 根据数据集大小、簇数量和 epoch 预算来选择 batch size 和更新速率。它的 GPU kernel 让每一轮遍历都保持高效，因此更少的遍历次数就转化为运行时间的节省。

自动设置对我来说很重要。我不想把训练省下来的时间，又花在另一次超参数搜索上。

e-means 优化的仍然是 k-means 的目标函数。每个点都归到最近的质心，对于哪里都不适合的点，也没有噪声标签。

所以旧的几何限制依然存在。最近质心区域是凸的，这意味着它仍然不是基于密度的聚类，更低的损失也不一定意味着更有意义的类别。

项目网站用动画解释了这一方法。还有一个交互式 playground，你可以改变数据形状、簇数量和 epoch 预算，然后比较质心的移动以及训练和测试损失。那只是一个 2D 示意，并非大规模 benchmark 的复现；这个 demo 在这些低维示例中还禁用了 dead-cluster revival。作者也提醒说，他们的 scaling law 对于极小、极低维的数据集并不是最优的。

一次成本只有十分之一的 k-means 运行，并不意味着我的花费也只有十分之一。它意味着我不再只选一次 k。我会试十个值，换一换特征，然后再跑一遍。

这就是杰文斯与煤炭：蒸汽机效率提高了，英国烧掉的煤反而更多。TypeSafe 的 Jev 就是根据他命名的。Jev 返回一个带类型的决策和一个概率，从不写文本，这让一次调用的成本低到文档会建议你多问很多小问题。它放弃散文来换取这一点。e-means 保持相同的目标和数据，但需要更少的遍历。

我不指望我的算力账单会下降。我指望的是，我不再将就于第一个 k。