k-means를 미니배치 지수이동평균으로 다시 써서 GPU에서 10~45배 빠르게 만든 e-means
- e-means는 미니배치마다 클러스터별 합과 개수를 지수이동평균으로 갱신하고 중심을 그 비율로 구하며, Lloyd가 25 epoch에 도달하는 테스트 손실을 1.2~3 epoch에 달성함
- GPU에서 Flash-KMeans 대비 10~45배, CPU에서 Faiss 대비 8~15배 wall-clock 단축을 기록했고, 보통 상충하는 속도와 손실을 함께 개선함
- 배치 크기와 스텝 크기를 스케일링 법칙(log n, log k, log T)으로 자동 산출해 하이퍼파라미터 튜닝이 필요 없음
- 작은 클러스터를 큰 클러스터를 쪼개 되살리는 dead-cluster revival, α0에서 0.1α0로 줄이는 코사인 스케줄링, 각 클러스터의 마지막 epoch 평균으로 끝내는 finalization 단계를 넣음
- Lloyd는 epoch당 1회, e-means는 epoch당 97회 갱신하며, 최근접 중심 배정을 융합한 전용 GPU 커널로 epoch 절감을 실제 시간 단축으로 바꿈
Hacker News 의견들
이거 진짜 멋지다. 뒤집고 보면 당연한 건데 시각화가 이해를 확실히 도와주네. scipy에 들어갔으면 좋겠음. faiss보다 훨씬 흔한 환경에서 바로 쓸 수 있으니까.
자동 하이퍼파라미터 법칙은 아직 직관이 안 옴. 배치 크기랑 스텝 크기가 왜 로그 스케일에서 나오는지 설명해줄 사람?
내 IVF 인덱스에 이 방식 적용해봤는데 GPU에서 146배 빨라졌음. 솔직히 놀랐음.
P=NP 논쟁이 왜 가끔은 잘못된 질문인지 보여주는 예임. NP-hard라도 근사해가 충분히 좋으면 되고, 그걸 45배 빨리 얻으면 더 좋고.
이런 부류 알고리즘 중 최고는 한 답이 불가능하고 다른 답이 확률적으로 높다는 걸 확실히 아는 쪽임. 블룸 필터나, 눈 크게 뜨면 일관성 해싱 같은 것들. 이런 알고리즘 다루는 책이 더 많았으면 좋겠음.
운영과학 전체가 NP-hard는 출발점일 뿐이라는 전제 위에 세워졌음.
epoch 줄어드는 건 좋은데 하이퍼파라미터 법칙은 사후에 피팅한 느낌이 듦.
구면 위 이등면적 메시 relaxation에 Lloyd를 쓰는 취미 프로젝트가 있는데 이걸로 바꿔봤음. 이 용도엔 더 안 좋음. 여긴 데이터셋이 없어서 각 Voronoi 셀 중심을 기하학으로 바로 계산하니까, 미니배치는 그걸 잡음 섞인 추정치로 바꾸는 것뿐임. 실제로 훨씬 느리고 그리드도 지저분해졌음.
Lloyd랑 아무것도 안 움직이는 것 사이의 선형 보간이라 최소한 같거나 낫겠지만 튜닝 없이는 이득이 제한적일 듯. 반대로 alpha를 -0.1로 두고 해보면 더 빨라질지도 모르겠음.
이런 알고리즘은 보통 EM이나 simulated annealing으로 등가 기술이 가능함. Sj = sj - a(sj - Sj)니까 friction 항이 붙은 EM 정도로 볼 수 있고, 중심이 convex hull 안에 남는다는 걸 짚은 게 중요함.
이게 대체 어떤 상황에 쓰는 건지 쉽게 설명해줄 사람?
벡터 계산이 빨라짐. ivfflat이나 prism 인덱스 빌드에 도움이 되고, 인덱스 빌드 시간이 50~80% 줄고 CPU 사용량도 50% 줄었다는 얘기도 있음.
클러스터링임. 데이터 포인트를 k개 묶음으로 나눠서 비슷한 것끼리 모으는 것. 고객을 고액, 중간, 소액으로 나눈다든가.
남은 하이퍼파라미터는 결국 k인데, 팔꿈치 방법 말고 요즘 state of the art는 뭐임?
팔꿈치 방법이 아직도 쓰임. k를 여러 개 훑으면서 지표가 완만해지는 지점을 고르는 식임. 클러스터링 자체가 주관적이라 딱 하나 좋은 방법은 없고, HDBSCAN처럼 k를 스스로 찾는 방법도 있음. 코드북 크기를 고정해야 하는 실용적 이유로 k를 직접 정할 때도 많고.