Pesquisadores da Meta FAIR lançaram o e-means, um substituto direto para o algoritmo k-means de Lloyd. O algoritmo de agrupamento e-means atinge a perda que o k-means de Lloyd obtém em 25 épocas, mas em 1,4 a 2,6 épocas. Ele é entregue no FAISS 1.16.0 sob faiss.contrib.e_means. Para qualquer pessoa que esteja construindo índices de vetores, quantizadores ou pipelines de curadoria de dados, o agrupamento é frequentemente a etapa offline mais lenta. O e-means visa exatamente essa etapa.
TL;DR Tamanho: É um algoritmo. Testado de 100 mil a 10 bilhões de pontos, até 16,7 milhões de clusters. Roda em: CPU ou GPU, com tensores PyTorch ou NumPy. As execuções de GPU do artigo usam H100s. Desempenho: Perda menor que o k-means de Lloyd em aproximadamente um décimo das épocas, em 24 configurações de dataset (autorrelatado). Melhor caso: Aceleração de tempo real na GPU de 10-45x em relação ao Flash-KMeans com perda igual. Pior caso: Execuções com 16 milhões de centróides exigem 64 GiB de acumuladores float32, então os centróides precisam ser fragmentados (sharded) entre GPUs.
O que é e-means? e-means é um algoritmo k-means em mini-lotes da Meta FAIR que atualiza os centróides com médias móveis exponenciais (exponential moving averages).
Como o e-means funciona? Cada variante do k-means mantém uma soma S e uma contagem N por cluster. O centróide é S dividido por N. Os métodos diferem apenas em como S e N mudam. Lloyd recalcula S e N a partir do dataset completo a cada iteração. MacQueen (1967) continua adicionando estatísticas de lote indefinidamente, então as atribuições antigas nunca são removidas. O e-means decai estatísticas antigas a uma taxa α: S ← (1−α)S + αs, e o mesmo para N. Atribuições mais antigas desaparecem, então os centróides acompanham os dados recentes. A equipe de pesquisa explicou que Lloyd é um caso de canto: lote completo com α = 1. No DEEP, esse canto fica 1,8% acima da melhor perda. A equipe testou o gradiente descendente simples como alternativa. Em sua melhor configuração, ele terminou 1,6% (DEEP) e 0,4% (SIFT) acima do EMA. Os autores suspeitam que o EMA vence porque os centróides sempre permanecem dentro do invólucro convexo de seus pontos atribuídos.
O que substitui o ajuste de hiperparâmetros? Duas leis de escala ajustadas definem o tamanho do lote B e o passo inicial α0 a partir do tamanho do dataset n, da contagem de clusters k e das épocas T. Em dados de validação...
Fonte: MarkTechPost
Publicado em 2026-11-10