E-means
lastmod 2026-11-11created 2026-11-112 edits
같은 테스트 오차에 약 10배 빠른 k-means
About
- 미니배치와 지수 이동 평균(EMA)을 결합한 k-means 알고리즘. 여러 데이터셋과 규모에서 Lloyd 25 에폭의 테스트 오차에 1.2~3 에폭 만에 도달함
- 같은 테스트 오차까지 걸리는 전체 실행 시간이 GPU에서 Flash-KMeans 대비 10~45배, CPU에서 Faiss 대비 8~15배 짧음
- 클러스터별 합 S_j와 개수 N_j를
S_j ← (1−α)S_j + αs_j,N_j ← (1−α)N_j + αn_j로 갱신해 오래된 할당의 영향을 줄임. Lloyd는 매 패스마다 통계를 초기화하고, MacQueen은 과거 통계를 모두 누적함 - 경사하강법 기반 미니배치 k-means(Meta FAIR)는 큰 학습률에서 불안정했으나, EMA는 중심점이 할당된 점들의 볼록 껍질 안에 머물러 안정적. DEEP 1M/SIFT 10M, 16,384 클러스터, 5 에폭 기준으로 튜닝한 경사하강법보다 테스트 오차가 각각 1.6%/0.4% 낮음
- 배치 크기와 초기 스텝을 점 개수(n)·클러스터 수(k)·에폭(T)에 따른 스케일링 법칙으로 자동 설정해 Lloyd 대비 추가 하이퍼파라미터 튜닝이 필요 없음
- 기본 배치:
B = 0.035 × k^0.13 × n^0.88 × T^0.81(품질 우선은 계수 0.0044) - 스텝:
α₀ = min(0.824 × k^−0.46 × B^0.90 × n^−0.45 × T^−0.11, 1), 코사인 스케줄로 0.1α₀까지 감소 - 마지막 에폭의 할당 평균으로 중심점을 다시 계산하는 마무리 단계로 학습 손실을 추가로 낮춤
- 기본 배치:
faiss/contrib/e_means 에 구현이 공개됐으며 PyTorch 텐서는 Emeans, NumPy는 NumpyEmeans 를 사용. 기본 학습 예산은 5 에폭이고 train(x) 가 중심점과 마지막 에폭의 클러스터 레이블을 반환함