e-means - 같은 테스트 오차에 약 10배 빠른 k-means

e-means는 미니배치와 지수이동평균을 결합한 k-means 알고리듬. 여러 데이터셋과 규모에서 Lloyd 알고리즘이 25에포크에 기록한 테스트 오차를 1.2~3에포크 만에 밑돌았음 같은 테스트 오차에 도달하기까지 걸린 전체 실행 시간은 GPU에서 Flash-KMeans 대비 10~45배, CPU에서 Faiss 대비 8~15배 짧았음 클러스터별 합계와 개수를 지수이동평균(EMA) 으로 갱신해 오래된 할당의 영향을 줄이고, 최근 할당을 중심점에 반영함 데이터 수, 클러스터 수, 학습 에포크 수에 따른 스케일링 법칙으로 배치 크기와 스텝 크기를 자동 설정하므로 Lloyd 대비 추가 하이퍼파라미터 조정이 필요하지 않음 큰 클러스터를 분할해 비활성 클러스터를 복구하며, 무작위 표본으로 교체하는 방식보다 코드북 용량 유지에 더 효과적이었음 정적 데이터셋을 위한 새로운 k-means 최적화 k-means는 고정된 데이터셋의 각 점과 가장 가까운 중심점 사이의 평균제곱거리(MSE)를 최소화하는 k개 중심점을 찾는 문제임 클러스터링할 분포가 계속 바뀌는 VQ-VAE의 코드북 학습과 달리, 여기서는 정적 데이터셋을 대상으로 함 머신러닝에서 드물게 전체 배치 최적화가 여전히 널리 쓰이는 문제이며, 기존 미니배치 방법도 대부분 1967년의 MacQueen 갱신 규칙에 기반함 관련 방법으로 Web-Scale K-Means Clustering, Nested Mini-Batch K-Means가 있음 e-means는 현대 딥러닝의 최적화 도구를 적용해 속도와 손실을 함께 개선하는 것을 목표로 함 미니배치 EMA 갱신에 자동 하이퍼파라미터 설정, 초기화 개선, 비활성 클러스터 복구, 코사인 스케줄링, 최종 보정을 결합함 병렬화가 용이하며, 최근접 중심점 할당을 융합한 전용 GPU 커널로 에포크 감소를 실제 실행 시간 단축으로 연결함 Lloyd, MacQueen, EMA의 중심점 갱신 차이 세 방법 모두 클러스터 j의 점 합계 S_j와 개수 N_j 를 유지하고, 중심점을 c_j = S_j / N_j로 계산함 현재 배치에서 해당 클러스터에 할당된 점의 합계와 개수는 각각 s_j, n_j이며, 할당된 점이 없으면 둘 다 0임 Lloyd 알고리듬 은 전체 데이터를 배치로 사용해 S_j ← s_j, N_j ← n_j로 통계를 매번 새로 계산함 중심점은 현재 할당된 점들의 정확한 평균이며, 한 번 갱신할 때마다 전체 데이터를 순회함 보통 20~50...