e-means, Lloyd보다 10배 빠르면서 손실은 더 낮다
E-means: 10x faster k-means at equal loss
e-means는 k-means를 미니배치로 돌리면서 지수이동평균으로 중심점을 갱신하는 새로운 최적화 규칙이다. Lloyd 방식보다 낮은 테스트 손실에 1.2~3 에포크 만에 도달해, GPU에서는 Flash-KMeans 대비 10~45배, CPU에서는 Faiss 대비 8~15배 빠르다. 배치 크기와 스텝은 스케일링 법칙으로 자동 결정되어 하이퍼파라미터 튜닝이 필요 없고, 죽은 클러스터 부활과 코사인 스케줄링, 전용 GPU 커널을 갖췄다. 노이즈가 큰 미니배치 갱신 덕에 Lloyd가 빠지기 쉬운 국소 최솟값에서도 잘 벗어난다.
속도와 품질은 보통 k-means에서 서로 맞바꾸는 관계인데, e-means는 더 나은 속도와 더 낮은 손실을 동시에 달성한다.
HN 토론
20- jlhawn
이걸 Lloyd 알고리즘의 대안으로 어디에 쓸 수 있을지 궁금하다. 나는 구 표면의 정이십면체 등면적 메시를 "relax"하는 데 Lloyd를 사용하는 취미 프로젝트가 있다 [1]. 이걸 이 방법을 응용한 것으로 바꿔서 훨씬 나은지, 아니면 이 방법으로 더 많은 반복을 감당할 수 있는지 시험해볼 생각이다.
편집: 시험해봤는데, 이 용례에는 확실히 더 낫지 않다. e-means는 거대한 데이터셋을 더 적게 통과하는 것으로 이기지만, 구 위에서 메시를 relax하는 데는 데이터셋이 없다: 각 Voronoi 셀의 중심은 그 기하학으로부터 직접 계산할 수 있다. 미니배치는 그것을 같은 것의 잡음 섞인 샘플 추정으로 바꿔놓을 뿐이다. 목적 함수도 최적점도 같으므로 기껏해야 Lloyd와 동등하다. 실제로는 훨씬 느렸고 그리드를 잡음투성이로 남겼으며, 작은 샘플 예산에서는 메시를 엉키게까지 했다.
[1] https://webgcm.app/explain/grid#nudging-the-cells-into-shape
- Luke2642
이건 p=np가 때로는 잘못된 질문인 이유를 보여주는 좋은 예시다. 이 np-hard 문제에는 근사 해가 충분히 좋고, 그걸 45배 더 빠르게 얻는다면 더더욱 좋지!
- real_faxenoff
이 방법을 내 IVF 인덱스(code-daemon 프로젝트)에 적용해서 GPU에서 146배 속도 향상을 얻었다.
인상적이다!