E-means: Ondalık Oranda Daha Az Epoch ile k-means'i Geride Bırakmak

On Kat Daha Az Epoch#

Geniş bir ölçek ve veri kümesi yelpazesinde e-means, standart Lloyd algoritmasının 25 epoch'ta ulaştığı test kaybı (loss) seviyesinin altına sadece 1.2 ila 3 epoch içinde ulaşır. 100.000 veri noktası ve 200 kümeden oluşan senaryolarda, Lloyd epoch başına 1 güncelleme yaparken e-means 97 güncelleme gerçekleştirir.

Uçtan uca ölçüldüğünde bu yaklaşım, GPU üzerinde en gelişmiş Lloyd uygulamasına (Flash-KMeans) kıyasla 10–45 kat, CPU üzerinde ise Faiss'e kıyasla 8–15 kat gerçek zamanlı (wall-clock) hızlanma sağlar. Geleneksel k-means uygulamalarında hız ve kalite genellikle birbiriyle çelişirken, e-means hem daha yüksek hız hem de daha düşük kayıp oranı sunar.

k-means Problemi#

$\mathbb{R}^d$ uzayında $n$ noktadan oluşan sabit bir $X = {x_1, \dots, x_n}$ veri kümesi ve bir $k$ tam sayısı verildiğinde, k-means problemi her nokta ile en yakın merkez (centroid) arasındaki ortalama kare mesafesini (MSE) minimize eden $C = (c_1, \dots, c_k)$ merkezlerini bulmaktır:

$$\mathrm{MSE}(X, C) = \frac{1}{n} \sum_{i=1}^{n} |x_i - c_{a(i)}|^2, \qquad a(i) = \arg\min_{j \in {1,\dots,k}} |x_i - c_j|^2$$

Burada dağılımın sürekli değiştiği VQ-VAE içindeki kod kitabı (codebook) öğreniminin aksine, statik bir veri kümesi söz konusudur.

e-means Projesi#

Projenin amacı, k-means problemi için modern bir optimizasyon kuralı sunmaktır. Geliştirme süreci şu temel gözlemlere dayanır:

• k-means, makine öğrenmesinde tam yığın (full-batch) optimizasyonun hâlâ yaygın olarak kullanıldığı nadir problemlerden biridir.
• Literatürdeki mevcut mini-batch k-means yöntemleri çoğunlukla 1967 yılında yayınlanan MacQueen güncelleme kuralına dayanmaktadır.
• Modern derin öğrenme, mini-batch yöntemlerini güçlendirebilecek gelişmiş optimizasyon araçları sunmaktadır.

Bu doğrultuda e-means, k-means problemi için en verimli yöntem olduğu kanıtlanan üstel hareketli ortalamalarla (exponential moving averages - EMA) mini-batch güncellemeleri yapar.

Temel Bileşenler ve Mühendislik Çıkarımları#

Yazılım geliştirme ve büyük ölçekli veri işleme süreçlerinde e-means'i öne çıkaran 6 temel mimari özellik şunlardır:

• Hareketli ortalama güncellemeleri (Moving-average updates): Her mini-batch, her kümenin eleman sayısını ve toplamını günceller; merkez bunların oranıdır. Pratik Çıkarım: Tam veri kümesini bellekte tutmadan akıcı ve kararlı merkez güncellemeleri yapılabilir.
• Hiperparametre ayarı gerektirmeme (No hyperparameter tuning): Yığın boyutu (batch size) ve adım boyutu ($\log n, \log k, \log T$ üzerinden) ölçekleme yasalarıyla (scaling laws) otomatik belirlenir. Pratik Çıkarım: Üretim ortamlarında maliyetli hiperparametre arama (grid search) süreçlerini ortadan kaldırır.
• Başlangıç ve bitiş (Start and finish): Yeni başlatma ve sonlandırma yöntemleri sunar; çalışma, her kümenin son epoch'taki tam ortalaması üzerinde biter ve ihmal edilebilir bir süre maliyetiyle eğitim kaybını düşürür.
• Kosinüs zamanlaması (Cosine scheduling): Adım boyutu $\alpha$, tıpkı derin öğrenmedeki öğrenme oranı (learning rate) gibi $\alpha_0$'dan $0.1 \alpha_0$'a doğru kademeli olarak azalır.
• Ölü kümeleri canlandırma (Dead-cluster revival): Boyutu belirli bir eşiğin altına düşen kümeler, büyük bir kümenin ikiye bölünmesiyle yeniden canlandırılır. Pratik Çıkarım: Vektör indeksleme sistemlerinde sıkça karşılaşılan atıl merkez sorununu otomatik çözer.
• Özelleştirilmiş çekirdekler (Specialized kernels): Özel GPU çekirdekleri (kernels), en yakın merkez atama işlemini birleştirerek (fusing) saf PyTorch uygulamalarının ötesine geçer ve algoritmik epoch tasarrufunu doğrudan donanım hızlanmasına dönüştürür.