e-means متا؛ جایگزین سریعتر k-means تو faiss
خلاصهٔ کاملتر
Meta FAIR یه جایگزین مدرن برای k-means ساخته به اسم e-means. k-means الگوریتم معروفیه که یه عالمه بردار رو تو k گروه (cluster) دستهبندی میکنه و برای هر گروه یه نقطهٔ مرکزی یا centroid پیدا میکنه. به گفتهٔ سازندهها، e-means نسبت به نسخهٔ کلاسیک Lloyd حدود ۱۰ برابر هم تو تعداد epoch و هم تو زمان واقعی سریعتره و loss نهاییش هم پایینتره.
ترفند اصلیش یه قانون بهروزرسانی mini-batch مخصوص مسئلهٔ k-means هست که بر پایهٔ میانگین متحرک نمایی (exponential moving average) کار میکنه. یعنی بهجای اینکه هر بار کل داده رو مرور کنه، centroidها رو با تکههای کوچیک داده کمکم جابهجا میکنه. هایپرپارامتر اضافه هم نداره: batch size و step size اولیه با فرمولهایی که از آزمایش به دست اومدن (scaling law) خودکار حساب میشن. معمولاً فقط nepochs رو تعیین میکنی که پیشفرضش ۵ـه و طبق README برای رد کردن loss نهایی k-means کافیه.
e-means داخل faiss عرضه شده و استفادهش سادهست. روی CPU با NumPy اینطوری کار میکنه:
em = NumpyEmeans(64, 500)
centroids, labels = em.train(x)
distances, new_labels = em.assign(x_new)روی GPU باید داده رو خودت قبلش بهصورت تنسور PyTorch روی GPU بذاری، چون e-means داده رو خودش جابهجا نمیکنه. سریعترین کرنلها CuTe هستن که فقط روی H100 و H200 با دادههای BF16 کار میکنن. روی بقیهٔ GPUهای جدید انویدیا (A100 به بالا) از Triton استفاده میشه و اگه هیچکدوم نشد، PyTorch خالی. یه هشدار مهم هم تو مستندات هست: مسیر GPU دنبال NaN یا بینهایت تو داده نمیگرده و یه مقدار خراب میتونه چندتا centroid رو بیسروصدا خراب کنه.
برای دادههایی که تو حافظه جا نمیشن، میشه batchها رو دستی با begin و update و finalize به مدل داد. برای چند GPU هم دو کلاس هست: DistributedEmeans وقتی centroidها روی یه GPU جا میشن، و EmeansShardedCentroids وقتی تعداد centroidها اونقدر زیاده که باید بین GPUها پخش بشن. چون batch size توان ۲ـه، بهتره ۲، ۴ یا ۸ GPU داشته باشی.
نکات کلیدی:
- e-means تو faiss.contrib.e_means عرضه شده و با faiss-cpu روی CPU هم اجرا میشه
- حدود ۱۰ برابر epoch کمتر از Lloyd's k-means برای رسیدن به همون loss
- پیشفرض nepochs برابر ۵ـه و مقدار کسری مثل ۲.۵ هم قبوله
- کرنل CuTe فقط برای H100 و H200 (SM90)؛ Triton برای A100 به بالا
- حالت quality batchهایی حدود ۸ برابر کوچیکتر از throughput میسازه
- مسیر GPU مقادیر NaN و بینهایت رو چک نمیکنه




