e-means erreicht gleichen Loss wie k-means in einem Bruchteil der Epochen
E-means: 10x faster k-means at equal loss
e-means ersetzt die klassische k-means-Aktualisierung durch Mini-Batch-Updates mit exponentiellen gleitenden Mittelwerten und erreicht auf einer Vielzahl von Datensätzen und Skalen einen Test-Loss unter dem von Lloyd bereits nach 1,2 bis 3 statt 25 Epochen. Auf der GPU bedeutet das 10- bis 45-fach weniger Laufzeit gegenüber Flash-KMeans, auf der CPU 8- bis 15-fach gegenüber Faiss. Batch-Größe und Schrittweite werden automatisch über Scaling Laws gesetzt, sodass keine Hyperparameter-Tuning nötig ist.
Lloyd ist ein Spezialfall von e-means: Setzt man die Batch auf den gesamten Datensatz und α=1, wird aus einer e-means-Iteration exakt eine Lloyd-Iteration – doch unsere Hyperparametersuche zeigt, dass genau diese extreme Einstellung höchst suboptimal ist.
- jlhawn
Ich frage mich, ob das irgendwo als Alternative zu Lloyds Algorithmus verwendet werden könnte. Ich habe ein Hobbyprojekt, das Lloyd's verwendet, um ein ikosaedrisches Netz mit gleicher Fläche auf der Oberfläche einer Kugel zu „entspannen“ [1]. Ich werde versuchen, es durch eine Adaption davon zu ersetzen und zu sehen, ob es viel besser ist oder ob ich mir mit dieser Methode mehr Iterationen leisten kann.
Edit: ausprobiert, und für diesen Anwendungsfall ist es definitiv nicht besser. e-means gewinnt, weil es weniger Durchläufe über einen riesigen Datensatz braucht, aber das Entspannen eines Netzes auf einer Kugel hat keinen Datensatz: Der Schwerpunkt jeder Voronoi-Zelle kann direkt aus ihrer Geometrie berechnet werden. Mini-Batches tauschen das nur gegen eine verrauschte, gesampelte Schätzung desselben Dings aus. Es hat dasselbe Ziel und dasselbe Optimum, also ist es im besten Fall gleichwertig zu Lloyd. In der Praxis war es viel langsamer und hinterließ ein verrauschtes Gitter, und mit kleinen Sample-Budgets hat es das Netz sogar verheddert.
[1] https://webgcm.app/explain/grid#nudging-the-cells-into-shape
- Luke2642
Das ist ein großartiges Beispiel dafür, warum p=np manchmal die falsche Frage ist. Für dieses np-schwere Problem sind Näherungslösungen gut genug, und wenn man sie 45x schneller bekommt, ist das sogar noch besser!
- real_faxenoff
Ich habe die Methode an meinen IVF-Index (das code-daemon-Projekt) angepasst und eine 146-fache Beschleunigung auf der GPU erreicht.
Das ist beeindruckend!