e-means ускоряет k-means в 10 раз без потери качества
E-means: 10x faster k-means at equal loss
e-means — новый метод оптимизации для k-means, который заменяет полный пересчёт центроидов на мини-батчи с экспоненциальным скользящим средним. Благодаря автоматической настройке гиперпараметров через scaling laws и специализированным GPU-ядрам он достигает тестовой ошибки ниже, чем у Lloyd, уже за 1,2–3 эпохи вместо 25, что даёт ускорение в 10–45 раз на GPU и в 8–15 раз на CPU. Кроме того, e-means реже застревает в локальных минимумах.
Lloyd — это крайний случай e-means без косинусного расписания скорости обучения. Однако наш поиск гиперпараметров показал, что эта крайняя настройка крайне неоптимальна, что объясняет, почему e-means значительно превосходит Lloyd.
- jlhawn
Интересно, можно ли это где-нибудь использовать как альтернативу алгоритму Ллойда. У меня есть хобби-проект, в котором алгоритм Ллойда используется для «релаксации» икосаэдрической равновеликой сетки на поверхности сферы [1]. Я собираюсь попробовать заменить его адаптацией этого метода и посмотреть, станет ли намного лучше или смогу ли я позволить себе больше итераций с этим методом.
Edit: попробовал, и для этого случая он определённо не лучше. e-means выигрывает за счёт того, что требует меньше проходов по огромному набору данных, но при релаксации сетки на сфере набора данных нет: центроид каждой ячейки Вороного можно вычислить напрямую из её геометрии. Мини-батчи просто заменяют это на зашумлённую выборочную оценку того же самого. У них одна и та же целевая функция и один и тот же оптимум, так что в лучшем случае это соответствует Ллойду. На практике это было гораздо медленнее и оставляло сетку зашумлённой, а при малых бюджетах выборки оно даже запутывало сетку.
[1] https://webgcm.app/explain/grid#nudging-the-cells-into-shape
- Luke2642
Это отличный пример того, почему p=np иногда неправильный вопрос. Для этой NP-трудной задачи приближённые решения достаточно хороши, а если вы получаете их в 45 раз быстрее, это ещё лучше!
- real_faxenoff
Я адаптировал метод для своего IVF-индекса (проект code-daemon) и добился ускорения в 146 раз на GPU.
Это впечатляет!