Meta 改写 K-Means,训练轮次降到十分之一 | K-Means | e-means | Meta FAIR | 聚类算法 | 向量检索 | Faiss | DINO10B | 向量数据库
三句話摘要
Meta FAIR 團隊將經典 K-Means 聚類算法的更新規則從累加改為指數移動平均,在保持聚類品質前提下,大幅降低所需訓練輪次和計算耗時。 深度學習工具(指數移動平均、餘弦退火)應用回經典優化問題反而獲得更顯著的改進,此事表明即便是已解決數十年的演算法,重新審視其核心更新規則仍有巨大潛力。 從累加到衰減的中心維護:傳統小批量更新會累積歷史統計量造成早期分配記錄長期影響,而 e-Means 用指數移動平均使新分配能即時調整中心,早先統計逐漸失效,避免陷入次優解。
重點整理
從累加到衰減的中心維護:傳統小批量更新會累積歷史統計量造成早期分配記錄長期影響,而 e-Means 用指數移動平均使新分配能即時調整中心,早先統計逐漸失效,避免陷入次優解。
死簇復活機制是關鍵改進:消融實驗顯示這項改動影響最大,透過每 5 批次檢查樣本不足的中心,從較大簇拆分一半重新安排,將樣本不足 10 個的中心比例從 26.3% 降到 0.3%。
破解參數調優瓶頸:作者用 7.5 萬次優化實驗,將批次大小和學習率與資料集規模、簇數、訓練輪次的關係擬合成幂律公式,使用者只需輸入三個參數就能自動生成最優配置。
收斂概率改善:Lloyd 演算法單調遞減誘發過早收斂,e-Means 的隨機波動反而給中心重新調整機會,在 200 次隨機初始化中不理想分組的發生率從 26% 降至 3.5%。
實用技巧與重點
- 核心數字與指標
- 訓練輪次:25 輪 → 1.4~2.6 輪達目標誤差
- 耗時加速:9.5 倍~45.5 倍(DINO 100 億向量實驗)
- 死簇改善:26.3% → 0.3%(樣本不足 10 個的中心比例)
- 參數遷移:在 DEEP 資料集擬合的公式,遷移到 SIFT、SPACEV、文本向量時中位誤差增幅只有 0.19%
- 硬體與規模
- 實驗規模:100 萬~100 億向量
- 硬體:H100 GPU、64 核英特尔至強 (Xeon) CPU
- 100 億規模試驗:Lloyd 25 輪需 6784 GPU 小時 (64 台機器);e-Means 2.5 輪僅需 779 GPU 小時 (32 台機器)
- 加倍索引方案:用 IVF (倒排文件索引) 進一步降至 23.2 GPU 小時,單台 8 卡 H100 只需 3 小時
- 關鍵技術元素
- 指數移動平均 (EMA) 維護中心的樣本計數和向量和
- 餘弦退火 (Cosine Annealing) 控制學習率
- 低精度計算:BF16、FP8、INT8 用於分配步驟
- 距離計算與最近中心選擇合併核函數
- k-means++ 因無並行實現在生產環境成本過高
- 參數推導公式
- 批次大小與步長用幂律擬合;批次取膝點(驗證誤差在最低點 0.2% 內的最大批次),大規模資料再除以 8
- 提供兩種批次口徑選擇:偏重吞吐 vs 偏重品質
- 實驗對照與基準
- 對標:Faiss、Flash-KMeans、Sculley 小批量 K-Means、SuperKMeans (CPU)
- 評價指標:均方誤差 (MSE)
- 合成資料測試:均勻立方體、各向同性高斯、拉伸高斯、高斯混合
- 真實規模試驗:DINO 10B (100 億 DINO 向量)、DEEP 資料集 (100 萬樣本)、YFCC100M (6000 萬張圖)
- 檢索評測:在 11 組資料上按 1% 掃描比例測 Recall@10
- 開源與可用性
- 程式碼已進 Faiss 儲存庫,模組名稱為 `e_means`
- 附帶實驗復現配置
- 尚未進正式發行版,需自行從源碼編譯
- 核心作者包括 Hervé Jégou 和 Matthijs Douze (Faiss 核心作者)
結論
深度學習工具(指數移動平均、餘弦退火)應用回經典優化問題反而獲得更顯著的改進,此事表明即便是已解決數十年的演算法,重新審視其核心更新規則仍有巨大潛力。
完整解析
K-Means 是機器學習中被廣泛應用卻少受關注的演算法,從 1950 年代至今已有數十年歷史。但在大規模向量檢索、圖片特徵壓縮、大模型注意力快取稀疏化等現代應用中,它仍在後台默默工作。Meta FAIR 團隊的貢獻在於,他們沒有改動 K-Means 的目標函數(最小化樣本到其所屬中心的平方距離之和),只是重新設計了聚類中心的更新方式,就將達到同等聚類品質所需的訓練輪次從 25 輪壓至 1.4~2.6 輪,實際耗時快了 45.5 倍。這一改進對產業的直接影響是:索引重建成本下降一個數量級,使得向量索引可以更頻繁地更新。
傳統 Lloyd 演算法的流程是每輪都完整掃描一遍資料集,將所有樣本分配給最近的中心,再用每簇的樣本均值重算中心。這造成一個固有限制:數據量越大,每一輪的成本越高。小批量更新的想法自 1967 年就有(MacQueen 的序列更新),但歷來的實現都面臨同一個根本問題:如何累積統計量。傳統小批量會把歷史統計一路加下去,導致早期中心位置不準時的分配記錄對後續結果長期施加影響,最終收斂速度快但誤差高於充分訓練的 Lloyd。而且批次大小和學習率兩個參數還得靠使用者自己調試。
e-Means 的突破在於改用指數移動平均 (EMA) 來維護中心。具體做法是:對每個簇記錄被分配過來的樣本數量和這些向量的和,中心本身不直接存儲而是用兩者的比值算出。每來一個小批次,這兩個量就按照衰減率做一次移動平均,新的分配能把中心及時拉過去,早先的統計則逐漸失去分量。這相當於把 K-Means 的更新視為一種帶衰減的硬分配 EM 演算法。雖然 EMA 這個概念在 VQ-VAE 和神經音頻編解碼器等領域並非新鮮事,但把衰減率當成可調度、可拟合的量進行系統設計卻是首次。此外,EMA 更新能讓中心保持在已分配樣本的凸包之內,大步長帶來的振蕩因此被限制,提高了收斂的穩定性。更重要的是,小批量帶來的隨機波動反而給了中心重新調整機會,讓演算法不易陷入 Lloyd 那樣的局部最優。實驗證明,在某些難以分解的資料分布上(如大小懸殊的多個簇),Lloyd 有高達 46% 的概率停在不理想的分組,而 e-Means 能將這一比例降至接近 0%。
另一項關鍵改進是死簇復活機制。在訓練過程中,有些中心會漸漸拿不到樣本分配,造成聚類容量浪費。e-Means 每 5 批次檢查一次,若某個中心的樣本數低於平均值的某個比例,就從較大的有效簇拆分一半出來給它重新安排位置。消融實驗顯示這項改動對最終誤差的影響最大,將樣本不足 10 個的中心比例從 26.3% 大幅降到 0.3%。結合這一機制,論文還提出了一套自動參數推導的方法。作者通過 7.5 萬次優化實驗,將批次大小和學習率與資料集規模、簇數、訓練輪次之間的關係擬合成了兩條幂律公式。批次大小的定義取決於「膝點」——驗證誤差還在曲線最低點 0.2% 以內的最大批次。有趣的是,這套公式雖然只在 DEEP 資料集上擬合,卻能迁移到 SIFT、SPACEV 和文本向量等其他領域,遷移誤差增幅僅 0.19%,使用者從此無需手工調參。
工程層面的優化同樣精細。e-Means 的 GPU 核函數在處理中心時按塊計算,每塊只保留最近候選而不輸出完整距離矩陣,節省顯存寫入。分配步驟使用低精度格式 (BF16、FP8、INT8),距離計算與最近中心選擇合併在一起,進一步減少訪存。在 100 億規模試驗中,Lloyd 跑 25 輪需 6784 GPU 小時,e-Means 只需 779 小時;若加用 IVF 倒排文件索引做近似最近鄰,更能降至 23.2 GPU 小時。對下游檢索任務的影響是,新聚類中心產生的倒排索引品質更高,在 11 個檢索基準上都達到或超過傳統方法充分訓練後的召回率,但耗時明顯更短。


