Önce k-means
Elinde bir yığın vektör var diyelim. Belgelerin, görsellerin ya da cümlelerin sayıya çevrilmiş hali. k-means bunları k tane gruba ayırıyor. Her grubun bir merkezi var ve amaç, her vektörün kendi merkezine olan ortalama uzaklığını olabildiğince küçültmek.
Klasik yöntemin adı Lloyd algoritması ve 1982’den beri aynı. Her turda bütün vektörleri en yakın merkeze atıyorsun, sonra her merkezi kendi grubunun ortalamasına taşıyorsun. Bunu birkaç kez tekrarlıyorsun. Meta’nın vektör arama kütüphanesi FAISS’te varsayılan 25 tur.
Nerede kullanılıyor? Sandığından çok yerde:
- Vektör arama: IVF (inverted file) indeksleri, veritabanını k-means gruplarına bölüyor. Bir sorgu gelince her şeyi taramak yerine sadece en yakın birkaç gruba bakılıyor. Vektör veritabanı karşılaştırması yazısında anlattığımız sistemlerin çoğu bu fikri kullanıyor.
- Sıkıştırma (quantization): Vektörü, en yakın merkezin numarasıyla temsil edip yer kazanmak.
- Veri temizliği: Eğitim verisini gruplara ayırıp her konudan dengeli örnek seçmek.
- Dil modelleri: Makaleye göre son dönemde attention önbelleğini sıkıştırmak için de kullanılıyor.
Sorun şu: Her tur bütün veriyi baştan sona okuyor. Milyarlarca vektörde bu çok pahalı.
e-means ne değiştiriyor?
Meta FAIR’den Swann Bessa, Matthijs Douze, Hervé Jégou ve arkadaşlarının 6 Kasım’da yayımladığı makalenin fikri, bütün veriyi beklemeden küçük parçalarla (mini-batch) ilerlemek. Bu fikrin kendisi yeni değil. Ama eski mini-batch yöntemleri hızlı olup daha kötü sonuç veriyordu. e-means farkı birkaç parçayla kapatıyor:
- Merkezleri üstel hareketli ortalama (EMA) ile güncelliyor. Yani her yeni parça merkezi biraz kaydırıyor, eskiler yavaş yavaş unutuluyor. Adım büyüklüğü eğitim boyunca küçülüyor.
- Boş kalan “ölü” grupları, kalabalık bir grubu ikiye bölerek yeniden canlandırıyor.
- Sonda kısa bir toparlama adımı var.
- En önemlisi: Parça büyüklüğü ve adım büyüklüğü, veri boyutu ve grup sayısından hesaplanıyor. Yazarlar bunun için ölçekleme yasaları çıkarmış. Sonuç olarak hiçbir ayar denemesi yapman gerekmiyor.
Sayılar
Makaledeki sonuçlar, gömme (embedding) vektörlerinden oluşan geniş bir veri setleri yelpazesinde ölçülmüş:
- Lloyd’un 25 turda ulaştığı test hatasının altına 1,4 ile 2,6 turda iniyor.
- GPU’da en iyi k-means uygulamalarına (Flash-KMeans) göre 10 ile 45 kat hızlı. Videodaki “40 kat” bu aralığın üst ucu. Örneğin 1 milyar vektör ve yaklaşık 1 milyon grupta hızlanma veri setine göre 21 ile 45,5 kat arasında.
- CPU’da da hızlı: 64 çekirdekli bir sunucuda, FAISS’in 274 saniyede ulaştığı hatayı bir veri setinde 29 saniyede yakalıyor.
- En büyük deney: 10 milyar görsel vektörünü (DINO10B) 16 milyon gruba ayırmak. e-means bunu 2,5 turda, Lloyd’un 25 turluk hatasından daha iyi yapıyor. Bu ölçekte en yakın merkezi bulmak bile pahalı. O yüzden merkezler de bir IVF indeksine konuyor. 10 milyar vektörlük deneyde bu, gereken süreyi yaklaşık 779 GPU saatinden 23 GPU saatine indiriyor.
Asıl merak edilen soru da test edilmiş: IVF indeksinde arama doğruluğu (recall) bozuluyor mu? Hayır. Ek bölümdeki deneylerde e-means aynı doğruluğa çok daha erken ulaşıyor ve çoğu veri setinde benzer ya da biraz daha iyi sonuç veriyor.
Yazarların kendi belirttiği sınır: Ölçekleme yasaları yüksek boyutlu vektörlere göre ayarlanmış. Çok düşük boyutlu ve çok küçük veri setlerinde en iyi sonucu vermeyebilir.
Nasıl denersin?
e-means FAISS’in içinde geliyor. pip install faiss-cpu ile CPU’da çalıştırabilirsin. GPU’da PyTorch üzerinden Triton ya da CuTe çekirdekleri kullanıyor. En hızlı yol H100/H200, Triton yolu A100 ve sonrası için. Varsayılan ayar 5 tur ve README’ye göre bu çoğu zaman Lloyd’u geçmeye yetiyor. Tarayıcıda oynayabileceğin bir demo da var.
Düşün
- Kullandığın vektör veritabanı indeksini kurarken k-means’e ne kadar süre harcıyor? Hiç baktın mı?
- 40 yıllık bir algoritmanın bu kadar iyileşebilmesi, “çözülmüş” saydığımız başka hangi araçların yeniden ele alınmayı beklediğini düşündürüyor?
Videoyu izle
Kaynaklar (4, İngilizce)
- Better Stack: Meta Just Made K-Means 40x Faster (And It's Better Too) (video) (yeni sekmede açılır)
- arXiv: e-means: outperforming k-means (in one-tenth the epochs) (2611.09501) (yeni sekmede açılır)
- GitHub: facebookresearch/faiss, contrib/e_means (README) (yeni sekmede açılır)
- e-means browser demo (yeni sekmede açılır)
Kendi cümlelerimizle yazılmış bir özettir, çeviri değildir. Tüm kaynaklar yukarıda.