Meta FAIR, k-means 대안 e-means 공개... 10배 속도 향상 및 낮은 손실 달성

• Meta FAIR가 Lloyd's k-means 대비 에포크와 실제 소요 시간에서 약 10배의 속도 향상과 더 낮은 손실을 달성하는 k-means 대안인 e-means를 개발함
• 지수 이동 평균(EMA)을 활용한 미니배치 업데이트 규칙을 기반으로 하며, 중심점은 두 가지 실행 평균(포인트 수와 임베딩 합)의 비율로 계산됨
• 구현은 faiss 라이브러리의 contrib/e_means 모듈에서 제공되며, CPU(NumPy/PyTorch) 및 GPU(PyTorch/Triton/CuTe) 백엔드를 지원함
• 기본 설정은 nepochs(기본값 5)만 필요하며, 배치 크기와 초기 스텝 사이즈는 경험적 스케일링 법칙을 통해 자동 유도됨

Performance and Backends

• GPU 실행은 CuTe 커널을 통해 Hopper(H100/H200)를 지원하며, 이는 CUTLASS DSL 4.7.1+, QuACK 0.6.5+, cuda-python 13.x를 요구함. 기타 NVIDIA GPU(A100+)는 Triton을 통해 지원됨
• 백엔드 선택은 자동 또는 수동(assignment_backend)으로 가능하며, CuTe가 가장 빠르고 그 뒤를 이어 Triton, PyTorch가 폴백으로 사용됨
• GPU에서의 가장 가까운 중심점 탐색은 FP16, BF16, FP8, INT8 정밀도를 지원하며, 중심점과 반환되는 거리는 FP32로 유지됨

Configuration and Scaling

• batch_law의 기본값은 "auto"이며, d≤16이면 "quality", 그 외에는 "throughput"을 선택함. "quality"는 최종 MSE를 낮추기 위해 "throughput" 대비 약 1/8의 배치 크기를 사용함
• 스케일링 법칙은 벡터 수 $n$, 클러스터 수 $k$, 패스 수 $T$에 기반하여 배치 크기 $B$와 초기 스텝 사이즈 $α_0$를 결정함
• max_points_per_centroid는 학습 세트 크기를 제한하며, 초과 시 무작위 부분집합으로 학습하고 나머지 벡터에는 라벨 -1을 부여함

Advanced Features

• 구면(spherical) e-means는 벡터와 중심점을 단위 노름으로 정규화하여 코사인 유사도 클러스터링을 지원함
• 멀티 GPU 지원에는 대규모 학습을 위한 DistributedEmeans(복제된 중심점)와 EmeansShardedCentroids(분할된 중심점)가 포함됨
• 클러스터 부활 기능은 포인트가 부족한 클러스터를 되살리기 위해 바쁜 클러스터를 분할하며, d ≤ 2인 경우 기본적으로 비활성화됨