Альберт Эйнштейн однажды сказал: Воображение важнее знаний. Знания ограничены; воображение окружает мир . Хотя извлечение знаний необходимо для получения мудрости в любой научной дисциплине, именно получение ценных идей из наших данных ведет нас к пониманию.

По мере того, как наборы данных становились все больше и больше, реальность вычислительного времени затрудняла воображение и интуицию специалистов по обработке данных. Благодаря RAPIDS специалист по данным получает доступ к инструментам, позволяющим быстро реализовывать свои идеи, даже со скоростью воображения, что позволяет им поддерживать ход мыслей и поток вдохновения.

RAPIDS Release 0.9 представил два новых многоузловых алгоритма с несколькими графическими процессорами (MNMG) для cuML, библиотеки машинного обучения RAPIDS. Случайные леса и k-means получили возможность масштабирования с помощью библиотеки распределенных вычислений Dask. В этом блоге я сосредоточусь на том, как мы масштабировали наш алгоритм k-средних, первый алгоритм, полностью использующий нашу новую масштабируемую архитектуру (которую я подробно объясню в следующем блоге). Надеюсь, что к концу этого блога вы так же воодушевлены будущим масштабируемого и производительного машинного обучения, как и мы!

Что такое k-means?

В 1963 году Sokal & Sneath вызвали всеобщий интерес к методам кластеризации своей монографией Числовая таксономия. Эта монография послужила катализатором принятия приложений кластеризации в более широких сообществах, занимающихся наукой, статистикой и анализом данных ¹.

Ранние формы алгоритма были известны статистическому сообществу просто как критерий суммы квадратов после меры, которую мы теперь называем инерцией. K-means - это алгоритм обучения без учителя, поэтому он не требует ярлыков для обучения. Он принимает в качестве входных данных набор точек данных и количество кластеров k. K-средство выбирает набор центров кластеров, называемых центроидами, которые минимизируют расстояние от точек до ближайшего к ним центроида. Инерция измеряет сумму квадратов расстояний от точек до их ближайшего центроида в каждом кластере.

Алгоритм k-средних содержит два основных этапа с необязательным третьим этапом.

  1. Выберите начальный набор из k центроидов кластера
  2. Итеративно обновляйте центроиды до сходимости или достижения некоторого максимального количества итераций.
  3. Необязательно: используйте центроиды для прогнозирования невидимых точек данных.

K-means чувствителен к первоначальному выбору центроидов. Плохая инициализация может никогда не дать хороших результатов. Поскольку поиск оптимальной инициализации очень затратен и трудно верифицировать, мы обычно используем эвристику. Помимо случайного выбора, k-means cuML предоставляет метод инициализации scalable k-means++ (илиk-means||), который является эффективной параллельной версией изначально последовательного алгоритма kmeans++. Он комбинирует случайную выборку с распределением расстояний между точками до каждой выборки, чтобы лучше разбросать начальные центроиды по пространству, где существуют фактические точки.

K-средство назначает каждую точку данных одному кластеру в форме шара, который будет такого же размера, как и все другие кластеры. ² Ограничения формы и размера кластера в k-средних часто можно преодолеть с помощью преобразование входных данных или использование более сложных вариантов, таких как ядерные k-средние и спектральная кластеризация, которые отображают точки в новое пространство на основе некоторой меры сходства перед их кластеризацией. Однако эти варианты имеют тенденцию к усложнению и могут быть очень чувствительны к выбору функции сопоставления. Старое доброе k-среднее с несколькими простыми приемами предварительной обработки все еще используется специалистами по обработке данных на практике, поскольку оно простое, быстрое и практичное.

Стюарт Ллойд использовал k-средства для квантования цифровых сигналов в 1957 году ³. K-средство все еще используется для квантования сигналов - современные примеры - обработка изображения и речи. Квантование обычно полезно в машинном обучении в качестве метода предварительной обработки для уменьшения вариации между функциями до фиксированного размера (k в случае k-средних).

K-средства используются предприятиями для сегментации пользователей и / или клиентов на основе различных атрибутов и моделей поведения. Он также находит применение при обнаружении аномалий, обнаружении мошенничества и кластеризации документов.

Проект cuML содержит библиотеку C ++ с растущей коллекцией как плотных, так и разреженных примитивов для машинного обучения CUDA. Эти примитивы с ускорением на GPU предоставляют строительные блоки, такие как линейная алгебра и статистика, для вычислений с матрицами признаков. Многие алгоритмы в cuML, такие как k-means, построены на основе этих примитивов.

Мы сравнили реализацию k-средних с одним графическим процессором с scikit-learn, чтобы определить влияние ускорения графического процессора cuML. Хотя scikit-learn может распараллеливать k-средние с использованием нескольких ядер ЦП (путем установки аргумента n_jobs на -1), реализация k-средних графических процессоров продолжает демонстрировать лучшую производительность при увеличении размеров данных.

Я провел этот тест на одном графическом процессоре NVIDIA (32 ГБ GV100) на NVIDIA DGX1. Тест scikit-learn был проведен на том же DGX1 с использованием всех 40 ядер (всего 80 потоков) процессора Intel Xeon E5–2698 v4 с тактовой частотой 2,20 ГГц. Мы наблюдаем более чем 100-кратное ускорение, поскольку количество выборок данных достигает миллионов.

Увеличение и уменьшение масштаба - предоставление пользователям возможности начать с малого и расти вместе с размером проблем

Наши многоузловые алгоритмы с несколькими графическими процессорами работают внутри среды Dask, что упрощает загрузку массивов данных большого размера в распределенные Pandas или кадры данных cuDF и использование моделей машинного обучения на графических процессорах. Многоузловая архитектура cuML с несколькими графическими процессорами использует парадигму один процесс на графический процессор (OPG), что означает, что каждый рабочий процесс Dask запускает ядра CUDA на одном графическом процессоре. Проект Dask-cuda с открытым исходным кодом упрощает запуск серии рабочих OPG Dask.

После обучения центроиды сохраняются на одном рабочем Dask. Прогнозирование выполняется досадно параллельным способом путем передачи центроидов рабочим, содержащим данные. Путем перемещения центроидов, а не данных, cuML может масштабироваться до большого количества графических процессоров и узлов. Этот общий дизайн также позволяет cuML хранить и загружать многоузловые модели с несколькими графическими процессорами почти так же, как и модель с одним графическим процессором.

Чтобы почувствовать производительность cuML по сравнению с алгоритмом на базе ЦП в среде Dask, я проверил время обучения, чтобы сравнить k-means cuML непосредственно с k-means Dask-ML. Оба алгоритма были протестированы на одной или двух машинах DGX1, соединенных Infiniband, с использованием 8 рабочих на узел. Как упоминалось ранее, DGX1 содержит процессор Intel Xeon E5–2698 v4 @ 2,20 ГГц.

Оба алгоритма использовали метод инициализации scalable k-means++. Максимальное количество итераций гиперпараметра оставалось равным 300, а допуск сходимости - 0,0001. ⁴

Сравнение времени обучения между cuML и Dask-ML

Чтобы увидеть, как k-средства cuML сравниваются с алгоритмами на основе Spark, мы обучили центроиды k-средних в Hi-Bench, тесте для больших данных с открытым исходным кодом, который поставляется с реализациями для Spark. Мы запустили Hi-Bench на платформе Google Cloud Platform с входной матрицей, содержащей 1,2 миллиарда образцов и 50 функций, всего 5 кластеров. Предварительные результаты показывают, что cuML на 4 машинах DGX1 с Infiniband (всего 32 графических процессора) почти в 200 раз быстрее, чем Spark, выполняющийся на 20 узлах. Эти результаты также показывают, что cuML в 22 раза быстрее Spark на 50 узлах.

Что дальше?

В ближайшем будущем мы будем модернизировать нашу существующую линейную регрессию на основе Dask, TSVD и реализации ближайших соседей, чтобы они соответствовали новому дизайну cuML с одним процессом для каждого графического процессора. PCA и логистическая регрессия также включены в этот список и должны быть выпущены примерно в то же время. Они будут следовать схеме, очень похожей на k-means.

Я также пишу более подробный блог о базовой архитектуре наших многоузловых алгоритмов с несколькими графическими процессорами и о том, как наше мышление развивалось по мере их разработки.

Вы можете опробовать наши K-средства MNMG на многих облачных провайдерах, а RAPIDS будет работать на любой архитектуре Pascal или более новой архитектуре NVIDIA GPU. Присоединяйтесь к нам и займитесь наукой о данных со скоростью воображения. Эйнштейн одобрил бы.

¹ Алгоритм K-средних существует в той или иной форме очень давно. Хотя его часто приписывают Джеймсу Маккуину, из статьи, написанной им в 1967 году, есть свидетельства того, что она использовалась еще раньше. Например, он поразительно похож на метод сжатия, использованный Bell Labs для обработки сигналов в 1957 году и разработанный Стюартом П. Ллойдом.

² В этом отличие от моделей смеси Гаусса, которые могут назначать точки данных множеству кластеров различной эллиптической формы и размеров.

³ Квантование ограничивает пространство возможных значений, которые может принимать каждый столбец вектора. Это делается путем замены входных сигналов ближайшими к ним центроидами.

⁴ Следует отметить, что тесты cuML k-means смогли использовать Infiniband во время обучения, в то время как k-means Dask-ML использовал только TCP-соединение между рабочими процессами Dask для обмена данными. Как только UCX будет полностью интегрирован в Dask, Dask-ML также сможет использовать Infiniband, что должно обеспечить повышение производительности.