메타의 AI 연구 조직 FAIR 연구진이 데이터를 비슷한 것끼리 묶는 대표 알고리즘 ‘k-평균(k-means)’을 대체하는 새 알고리즘 ‘e-민즈(e-means)’를 공개했다. 논문은 11월 6일 논문 공개 사이트 아카이브에 올라왔고, 코드는 메타의 벡터 검색 라이브러리 ‘파이스(Faiss)’에 추가됐다.

k-평균은 데이터를 정해진 개수(k)의 묶음으로 나누는 방법이다. 각 묶음의 중심점을 정하고, 모든 데이터를 가장 가까운 중심점에 배정하는 과정을 반복한다. 데이터 분석, 검색, 양자화, AI 학습 데이터 선별 등에 쓰인다. 지금 가장 널리 쓰이는 ‘로이드 알고리즘’은 매번 전체 데이터를 한 번씩 처리해 중심점을 다시 계산하며, 이 과정을 보통 20~50회 반복한다.

e-민즈는 전체 데이터 대신 일부 데이터 묶음(미니 배치)으로 중심점을 자주 갱신하고, 이전 배정 결과는 지수이동평균 방식으로 서서히 반영 비중을 줄인다. 연구진은 데이터 수, 묶음 수, 학습 길이에 따라 배치 크기와 갱신 폭을 정하는 규칙을 실험으로 찾아내, 이용자가 별도로 설정값을 조정할 필요가 없게 했다. 초기화 방법, 너무 작아진 묶음을 큰 묶음을 나눠 되살리는 기능, 마지막에 각 묶음의 정확한 평균으로 마무리하는 단계, 연산을 합친 전용 GPU 커널도 더했다.

연구진에 따르면, e-민즈는 로이드 알고리즘이 25에포크 동안 도달하는 오차보다 낮은 오차에 1.2~3에포크 만에 도달했다. 에포크는 전체 데이터를 한 번 모두 처리하는 단위다. 실행 시간은 GPU에서 기존 최고 성능 구현 ‘플래시-K민즈’보다 10~45배, CPU에서 파이스보다 8~15배 짧았다. DINO 임베딩 100억 개로 구성된 데이터셋 ‘DINO10B’를 1,600만 개 묶음으로 나누는 실험에서는 2.5에포크 만에 로이드 알고리즘 25에포크보다 낮은 오차를 기록했다.

잘못된 배치에서 빠져나오는 능력도 개선됐다. 크기가 크게 다른 두 데이터 덩어리를 8개 묶음으로 나누는 실험을 200번 반복한 결과, 로이드 알고리즘은 26%가 잘못된 배치에 머물렀지만 e-민즈는 3.5%에 그쳤다. 논문에는 스완 베사, 위고 투브롱, 마테이스 다우저, 에르베 제구 등 7명이 참여했다.

자세한 내용은 e-민즈 프로젝트 페이지와 아카이브에서 확인할 수 있다.

이미지 출처: AI 생성