e-means logra un k-means 10 veces más rápido con la misma pérdida
E-means: 10x faster k-means at equal loss
e-means sustituye la actualización de Lloyd por medias móviles exponenciales sobre mini-batches y ajusta automáticamente el tamaño de lote y el paso mediante leyes de escala, sin hiperparámetros que afinar. En GPU alcanza una reducción de tiempo de 10 a 45 veces frente a Flash-KMeans y de 8 a 15 veces en CPU frente a Faiss, con una pérdida igual o menor. Además escapa de mínimos locales con mucha más frecuencia que Lloyd.
Lloyd es un caso extremo de e-means, y nuestra búsqueda de hiperparámetros encontró que esa configuración extrema es altamente subóptima, lo que explica por qué e-means supera ampliamente a Lloyd.
- jlhawn
Me pregunto si esto podría usarse en algún sitio como alternativa al algoritmo de Lloyd. Tengo un proyecto de hobby que usa Lloyd para "relajar" una malla icosaédrica de áreas iguales sobre la superficie de una esfera [1]. Voy a intentar cambiarlo por una adaptación de esto y ver si es mucho mejor o si puedo permitirme más iteraciones con este método.
Edición: lo probé, y definitivamente no es mejor para este caso de uso. e-means gana porque necesita menos pasadas sobre un conjunto de datos enorme, pero relajar una malla sobre una esfera no tiene conjunto de datos: el centroide de cada celda de Voronoi se puede calcular directamente a partir de su geometría. Los mini-batches simplemente cambian eso por una estimación muestreada y ruidosa de lo mismo. Tiene el mismo objetivo y el mismo óptimo, así que en el mejor de los casos iguala a Lloyd. En la práctica fue mucho más lento y dejó la cuadrícula ruidosa, y con presupuestos de muestra pequeños incluso enredó la malla.
[1] https://webgcm.app/explain/grid#nudging-the-cells-into-shape
- Luke2642
Este es un gran ejemplo de por qué p=np a veces es la pregunta equivocada. Para este problema NP-hard las soluciones aproximadas son suficientemente buenas, ¡y si las consigues 45 veces más rápido eso es aún mejor!
- real_faxenoff
Adapté el método a mi índice IVF (el proyecto code-daemon) y logré una aceleración de 146x en la GPU.
¡Eso es impresionante!