Meta FAIR открыла e-means: замену k-means с ускорением ~10×

Автор (текст написан от первого лица, имя в источнике не указано) открыл код e-means, алгоритма кластеризации k-means, разработанного в Meta FAIR. Он предлагается как замена классического алгоритма Ллойда и, по заявлению автора, даёт ускорение примерно в 10 раз и по числу эпох, и по времени работы при более низкой ошибке (loss). Код лежит в faiss/contrib/e_means, статья, arXiv:2611.09501.

Главные цифры: на широком диапазоне масштабов и наборов данных e-means достигает тестовой ошибки ниже, чем у алгоритма Ллойда после 25 эпох, за 1,2-3 эпохи. При измерении «от начала до конца» это сокращение времени в 10-45 раз на GPU относительно современной реализации Ллойда Flash-KMeans и в 8-15 раз на CPU относительно Faiss. Обычно в k-means скорость и качество уходят в компромисс, а e-means, как утверждает автор, улучшает и то и другое. Это собственные замеры авторов; о независимой проверке в тексте не сказано.

Как это устроено. Задача k-means: для заданного набора точек найти k центроидов, минимизирующих средний квадрат расстояния от каждой точки до ближайшего центроида. Алгоритм Ллойда на каждой итерации назначает все точки ближайшим центроидам и пересчитывает статистику заново по всему набору, это полный проход по данным, и так обычно повторяют 20-50 раз. Обновление MacQueen накапливает статистику, ничего не отбрасывая, поэтому в среднем остаются точки, назначенные при давно устаревших положениях центроидов; более поздний метод Staleness-Reduction Mini-Batch K-Means дал заметное ускорение, но лишь при очень малом числе кластеров. e-means работает на мини-батчах и заменяет накопленную сумму экспоненциальным скользящим средним: старые назначения забываются со скоростью α, а центроид следует за недавними назначениями. Такое правило обычно применяют для движущихся распределений, например при обучении VQ-VAE; автор пишет, что оно крайне эффективно и для статичных наборов, если сочетать его с остальными компонентами e-means и правильно подобрать гиперпараметры. В иллюстративном примере со 100 000 точек в 200 кластерах алгоритм Ллойда делает одно обновление за эпоху, а e-means, 97.

Происхождение идеи. Проект вырос из прежней работы в Meta FAIR Хьюго Туврона и Эрве Жегу, нашедших, что мини-батч k-means с градиентным спуском может обыграть алгоритм Ллойда. Автор воспроизвёл эти результаты, но обнаружил, что обновления градиентным спуском нестабильны при больших шагах обучения, в отличие от скользящего среднего. Он лишь предполагает причину: скользящее среднее гарантирует, что центроид остаётся в выпуклой оболочке назначенных ему точек, а градиентный спуск может «перелететь» за неё. Отсюда и название, e от exponential moving average.

Почему выигрыш. Если взять батч, равный всему набору (B = n), и α = 1, одна итерация e-means в точности превращается в итерацию Ллойда, то есть Ллойд, крайний случай e-means (без косинусного расписания шага). Поиск гиперпараметров показал, что эта крайняя точка сильно неоптимальна, и именно этим авторы объясняют превосходство e-means. Кроме того, на игрушечных наборах с повторами по 200 начальным значениям генератора случайных чисел e-means заметно реже попадал в патологические конфигурации, чем Ллойд. Объяснение авторов: зашумлённые обновления по мини-батчам лучше исследуют ландшафт ошибки и выбираются из локальных минимумов, а Ллойд с вечно убывающей ошибкой склонен застревать.

Без ручной настройки. Пользователю не нужно задавать ни одного дополнительного гиперпараметра по сравнению с алгоритмом Ллойда: два подогнанных закона масштабирования выбирают размер батча B и шаг α0 по характеристикам задачи (n, k, T). Авторы пишут, что законы хорошо обобщаются на неизвестные наборы данных и масштабы (отложенные наборы: SIFT, SPACEV, а также arXiv и AG-News из набора VIBE). Законов два: «по умолчанию» и «качества», второй жертвует пропускной способностью ради лучшего качества кластеризации.

Мёртвые кластеры. Главная беда мини-батч k-means, «мёртвые» кластеры, к которым не приписано ни одной точки, из-за чего эффективный размер словаря центроидов падает; это особенно болезненно для больших словарей. Распространённая мера, как в EnCodec, заменять такие центроиды случайными точками из батча. В e-means мёртвые кластеры «оживляют» иначе: выбирают активный кластер с вероятностью, пропорциональной его размеру, и делят его на два. Подход заимствован из k-means в Faiss и, по словам авторов, значительно эффективнее устраняет мёртвые кластеры. В абляции (1 млн векторов, k = 16 384, 5 эпох, среднее по 5 запускам) кластер считался мёртвым, если в конце к нему приписано менее десяти векторов, тысячная доля среднего кластера.

Прочее и проверка. Помимо правила обновления e-means улучшает инициализацию, добавляет косинусное расписание скорости забывания и финальный этап, снижающий ошибку обучения почти без затрат времени. Алгоритм хорошо параллелится и поставляется со специализированными ядрами, переводящими алгоритмический выигрыш в реальное время. Проверка проведена на 24 наборах эмбеддингов и синтетических данных и их конфигурациях; для видео сравнили 234 конфигурации e-means с k-means на 16 наборах от 100 тысяч до 100 миллионов точек.

Ключевые факты

  • Meta FAIR открыла код e-means, замены алгоритма Ллойда для k-means; код в faiss/contrib/e_means, статья arXiv:2611.09501.
  • Заявлено ускорение ~10× по эпохам и времени при более низкой ошибке: тестовая ошибка ниже, чем у Ллойда за 25 эпох, достигается за 1,2-3 эпохи.
  • Сокращение времени от начала до конца: 10-45× на GPU относительно Flash-KMeans и 8-15× на CPU относительно Faiss.
  • Основа метода: обновления по мини-батчам с экспоненциальным скользящим средним, размер батча и шаг подбираются законами масштабирования, ручная настройка не нужна.
  • Мёртвые кластеры оживляют делением крупных активных кластеров; проверка на 24 наборах и конфигурациях, цифры, собственные замеры авторов.

Почему это важно

k-means, базовый и очень массовый метод кластеризации, а на больших наборах эмбеддингов и больших словарях центроидов (например, для кодовых книг) его скорость упирается в дорогие полные проходы по данным. e-means предлагает отказаться от классической схемы Ллойда в пользу мини-батчей с экспоненциальным скользящим средним, не жертвуя качеством: по заявлению автора, скорость и ошибка улучшаются одновременно, хотя обычно они обмениваются друг на друга. Если заявленные 10-45× на GPU и 8-15× на CPU подтвердятся на других данных, это ощутимая экономия на задачах, где кластеризация, рабочая рутина.

Кому это важно

Тем, кто кластеризует большие наборы векторов: инженерам поиска и рекомендаций, кто работает с эмбеддингами и индексами на основе Faiss, исследователям, обучающим кодовые книги и квантователи, и всем, кто использует k-means как строительный блок. Проект выложен рядом с Faiss, поэтому ближе всего он к пользователям этой библиотеки.

Как это применить

Код находится по адресу faiss/contrib/e_means; статья доступна как arXiv:2611.09501. По описанию, дополнительных гиперпараметров по сравнению с алгоритмом Ллойда задавать не нужно: размер батча и шаг подбираются законами масштабирования по (n, k, T). Есть два варианта закона, «по умолчанию» и «качества» (второй жертвует пропускной способностью ради качества кластеризации). Лицензия кода в источнике не указана, это стоит проверить в репозитории перед использованием.

Можно ли доверять

Все цифры, собственные замеры авторов; независимой проверки в источнике не упоминается. Материал, страница проекта от первого лица, имя автора на ней не указано, а сообщается лишь, что работа сделана в Meta FAIR. Сведений о рецензировании статьи нет. Модели GPU и CPU, на которых получены 10-45× и 8-15×, не названы. Валидация довольно широкая: 24 набора и конфигурации, 234 запуска на 16 наборах от 100 тысяч до 100 миллионов точек, но источник не утверждает, что десятикратный выигрыш держится на каждом наборе. Объяснения (почему скользящее среднее устойчивее градиентного спуска) автор сам подаёт как предположение.

Риски и подводные камни

Речь о заявленных результатах: на ваших данных, железе и значениях k выигрыш может отличаться, а общие «~10×» и подробные диапазоны (1,2-3 эпохи против 25; 10-45× на GPU; 8-15× на CPU) нельзя путать. Точных значений ошибки или процентного улучшения над Ллойдом в тексте нет, только «ниже». Метод рассчитан на статичный набор данных; для движущихся распределений, как у кодовых книг внутри VQ-VAE, это отдельный случай. Кроме того, мини-батч-подходам свойственны мёртвые кластеры; e-means с ними борется, но об этом стоит следить на больших k.

Компания Meta Platforms признана экстремистской организацией, её деятельность на территории РФ запрещена.