TSNE (T-Distributed Stochastic Neighbor Embedding) - популярный алгоритм уменьшения размерности без учителя, который находит такие разнообразные применения, как неврология, сходство изображений и визуализация нейронных сетей. К сожалению, его самым большим недостатком было долгое время обработки в большинстве доступных реализаций. RAPIDS теперь обеспечивает быстрое ускорение TSNE с помощью графического процессора, основанное на подходе Barnes-Hut на основе графического процессора, разработанном в CannyLab. TSNE в библиотеке машинного обучения cuML от RAPIDS может работать до 2000 раз быстрее , чем соответствующая реализация ЦП (Scikit-Learn), и использует на 30% меньше памяти графического процессора, чем текущие версии графического процессора, и может быть в 2 раза быстрее . (BH TSNE CannyLab).

Этот блог начинается с представления некоторых примеров использования, за которыми следуют тесты, сравнивающие реализацию TSNE GPU в cuML с scikit-learn. Затем дается подробное объяснение того, как работает TSNE и как он был оптимизирован в cuML для работы на графических процессорах.

Приложения ЦНЭ

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

На рисунке 2 выше TSNE применяется к набору данных о моде, который состоит из 60 000 изображений предметов одежды. Это полезно для поиска естественной группировки, в которой похожие предметы одежды будут сближены. TSNE может уменьшить сложное пространство модных образов до меньшего пространства, с которым легче работать. Векторы пикселей для каждого изображения используются в качестве входных данных, и TSNE отображает их в 2 измерения или 2 значения для каждого изображения. На рисунке 5 двухмерный результат TSNE нанесен на график и имеет цветовую кодировку в соответствии с категорией одежды исходного ввода (например, ботинки синие). TSNE не знает об этих категориях, но находит группу, которая может объединить больше похожих предметов.

Вот еще один пример использования набора цифр MNIST. Учитывая рукописные цифры, задача состоит в том, чтобы классифицировать каждую цифру как 0, 1, 2 и т. Д. После применения TSNE ко всем 60 000 изображениям цифр, мы обнаруживаем, что без каких-либо меток TSNE удается разделить данные. Вы можете увидеть на рисунке 3, как есть четкие кластеры, обозначенные цветом по типу цифр (от 0 до 9).

TSNE также используется для визуализации сверточных нейронных сетей, чтобы помочь практикам определить, действительно ли сложные классификаторы учатся. Ниже показан TSNE, примененный к AlexNet, где вывод CNN изображений до фактического классификатора (4096 измерений) сокращается до двух измерений, а затем визуализируется с фактическим входным изображением. Обратите внимание на рисунок 4, похожие изображения имеют тенденцию быть близкими, что подразумевает, как AlexNet видит их как похожие.

TSNE и анализ главных компонентов (PCA)

TSNE - это нелинейный алгоритм уменьшения размерности, в то время как Анализ главных компонент является линейным. Компоненты PCA этого средства часто имеют какое-то значение, в то время как TSNE больше не упорядочены по важности и вообще не могут быть интерпретированы за пределами создаваемых ими районов. На ЦП часто рекомендуется уменьшить размеры с помощью PCA до 50, прежде чем вводить TSNE для повышения производительности. Это не относится к графическим процессорам.

RAPIDS Ускорение cuML по сравнению с Scikit-Learn

Многие специалисты по данным начинают с популярной реализации TSNE от scikit-learn. TSNE (однопоточный) Scikit-learn предоставляет знакомый, простой в использовании интерфейс, но может столкнуться с проблемами масштабируемости. Например, набор данных из 60 000 примеров может занять 1 час , чтобы сойтись в scikit-learn на ЦП. Реализация cuML TSNE, работающая на графическом процессоре NVIDIA V100, может завершиться за 3 секунды на том же наборе данных.

Обратите внимание на шкалу журнала в таблице 1.

Таким образом, TSNE cuML работает в 1000 раз быстрее, и он также достигает аналогичных показателей надежности.

В наборе данных с 204800 образцами и 80 функциями cuML занимает 5,4 секунды, в то время как Scikit-learn занимает почти 3 часа. Это колоссальное ускорение в 2000 раз . Мы также протестировали TSNE на компьютере NVIDIA DGX-1 с использованием только одного графического процессора V100 (DGX1: 32 ГБ GV100 GPU, Intel Xeon E5–2698 v4 CPU @ 2,20 ГГц с 20 ядрами и 40 потоками). Время передачи данных также было включено в этот тест. На рисунке 5 показан набор данных, содержащий 100 выборок и 80 столбцов. Обратите внимание, как cuML может быть быстрее даже на небольших наборах данных. Кроме того, RAPIDS TSNE примерно в 200 раз быстрее, чем многоядерный TSNE.

Использование трюка PCA, описанного выше, действительно дает scikit-learn TSNE небольшое повышение сквозной производительности, однако RAPIDS cuML TSNE по-прежнему демонстрирует более чем 1000-кратное ускорение для высоких наборов данных с 204800 выборками и 50 столбцами. Это позволяет обучать TSNE на наборах данных без предварительного уменьшения размеров с помощью PCA.

Как работает TSNE

TSNE cuML в значительной степени основан на оригинальной реализации CannyLab Barnes Hut. В настоящее время поддерживаются два алгоритма: Barnes Hut TSNE и Exact TSNE. Barnes Hut работает намного быстрее, чем версия Exact, но немного менее точен (самое большее ошибка 3%). Для больших наборов данных (выборки ›= 2000) рекомендуется алгоритм Barnes Hut для обеспечения максимальной скорости.

TSNE преследует 2 основные цели:

  1. Близкие точки должны оставаться близкими.
  2. Дальние точки должны оставаться далекими.

Учитывая некоторые точки данных в параметрах большой размерности (скажем, 3D или 1000 D), цель состоит в том, чтобы встроить точки в более низкое пространство (например, в 2 измерениях), чтобы локальная структура соседства входных данных сохранялась в той мере, в какой возможно во встроенном виде.

Более конкретно, точки в исходном многомерном пространстве сначала преобразуются в плотности вероятности, которые выглядят как колоколообразная кривая или нормальное распределение, как красная линия на рисунке 6 ниже. Соседние точки увеличивают вероятность друг друга, поэтому плотные области обычно имеют более высокие значения. Точно так же выбросы и несходные точки имеют небольшие значения.

И вот здесь появляется часть «T-Distributed» в названии TSNE. Точки в нижнем пространстве также моделируются с использованием колоколообразной кривой, хотя она растянута, как синяя линия на рисунке 6.

Люди пытались использовать нерастянутую версию, но это вызывает проблему, известную как проблема скученности, когда встроенные точки слипаются.

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

  1. Точки, расположенные близко друг к другу, изначально будут дергать друг друга. (Достопримечательности)
  2. Точки, которые изначально не похожи друг на друга, будут давить друг на друга. (Отталкивание)

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

Теперь позвольте пружинам в низкоразмерном пространстве быть свободными. Это этап оптимизации TSNE. Мы прекращаем развитие системы, когда все пружины перестают двигаться. Мы убираем пружины, и конечные положения каждой точки становятся окончательным вложением.

Оптимизация TSNE

Для повышения производительности TSNE на графических процессорах используются четыре оптимизации:

  1. вычисление вероятностей более высоких измерений с меньшим объемом памяти графического процессора,
  2. аппроксимация вероятностей более высоких измерений,
  3. сокращение арифметических операций и
  4. вещание по рядам.

Оптимизация 1 - Расчет вероятностей более высоких измерений с меньшим объемом памяти графического процессора

Помните цель рассчитать вероятности каждой точки, учитывая влияние каждой другой точки? Когда влияние точки A на точку B не такое же, как влияние точки B на точку A, они не симметричны. Чтобы сделать их равными, оба вклада суммируются и делятся между собой. Это называется симметризацией вероятностей.

Первоначально этап симметризации был неэффективным из-за использования ненужных промежуточных буферов памяти. В реализации RAPIDS использование памяти было уменьшено на 30% и теперь сильно распараллеливается. В общем времени работы симметризация теперь занимает 1% или меньше общего затраченного времени по сравнению с 25% ранее.

Чтобы реализовать эту оптимизацию, мы сначала преобразовали расстояния между точками в разреженную матрицу COO (формат координат), используя быстрые примитивы cuML. Форматы разреженных матриц хороши для представления графов связанных узлов и ребер. Это особенно верно в случае графов k-ближайших соседей, которые имеют фиксированное количество связанных ребер, поскольку нужно учитывать только ближайших соседей каждой точки. Редкие форматы требуют сохранения только связанных вершин, что обеспечивает значительное ускорение и меньшие накладные расходы на хранение для таких алгоритмов, как TSNE. Формат COO представлен 3 очень простыми массивами - значениями данных (COO_Vals), индексами столбцов (COO_Cols) и отдельными индексами строк (COO_Rows ).

В качестве примера предположим, что есть заданная точка (0, 7) со значением 10. Это транспонирование (или обратное) - (7, 0), также со значением 10. Вот как сохранить это в окончательной разреженной матрице COO:

Чтобы получить его транспонирование или обратное, просто переверните указатели столбцов и строк следующим образом:

Обратите внимание, что в приведенном выше примере также есть массив с именем «RowPointer». Макет COO не включает информацию о том, где начинается или заканчивается каждая строка. Включение этой информации позволяет нам распараллеливать поиск и быстро суммировать транспонированные значения на этапе симметризации. Эта идея RowPointer исходит из макета разреженной матрицы CSR (сжатая разреженная строка). В макете CSR записи индексируются по строкам, в которых они находятся. Например, все элементы с индексом строки 1 размещаются вместе в отсортированном порядке в начале индекса RowPointer. Макет CSR отлично подходит для алгоритмов, в которых доступ к данным осуществляется построчно.

Объединение этих двух макетов позволяет нам использовать формат COO для эффективных параллельных вычислений над каждым элементом в графе, в то время как формат CSR используется для выполнения транспонирования элементов. Поскольку RowPointer содержит количество элементов, присутствующих в каждой строке, вклад каждой пары точек можно суммировать параллельно с помощью atomicAdd.

На рисунке 8 показан весь процесс. Учитывая точку (0, 7) со значением 10, проиндексируйте указатель строки, чтобы получить индекс строки для точки, и сохраните его. Затем перейдите к (7, 0), получите доступ к указателю строки и сохраните его параллельно с первым.

Оптимизация 2 - Аппроксимация вероятностей более высоких измерений

Ван дер Маатен, автор TSNE заметил, что вместо вычисления полных расстояний между всеми точками можно вычислить верхних ближайших соседей и вычислить по ним высокоразмерные вероятности. cuML последовал подходу CannyLabs, использовав библиотеку FAISS Facebook для вычисления топ-k соседей на GPU. Это сокращает вычисление вероятности от необходимости хранить N² элементов до хранения только N * k элементов (N - количество выборок данных, а k - количество соседей).

Оптимизация 3 - сокращение арифметических операций

Во многих реализациях TSNE вычисление силы притяжения (натяжение пружины) разделено, чтобы сначала вычислить точку A, а затем точку B. TSNE можно сделать значительно быстрее, если вычислить взаимодействие не отдельно, а одновременно. время. Это сокращает количество умножений и адресов с первоначальных 9 до примерно 4 и ускоряет вычисления на 50%.

Оптимизация 4. Трансляция по строкам

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

Повышение числовой стабильности TSNE

В cuML исправлены некоторые редкие проблемы с числовой стабильностью в исходной реализации CannyLab, в том числе некоторые бесконечные циклы и доступ к памяти вне пределов. Также известно, что ЦНЭ очень чувствителен к своим гиперпараметрам. В cuML предусмотрена адаптивная схема обучения, в которой параметры настраиваются на основе вводимых пользователем данных.

Иногда, если скорость обучения слишком велика, встроенные баллы могут стать выбросами. В cuML указан MAX_BOUND, который аккуратно отодвигает выброс назад и сбрасывает все переменные импульса. Это также помогает повысить точность и надежность TSNE.

Как запустить TSNE в RAPIDS?

Давайте сравним API scikit-learn с API RAPIDS cuML. В этом примере используется набор данных digits из scikit-learn.

scikit-learn API:

Теперь сравните его с cuML:

Поскольку cuML является практически незаменимой заменой scikit-learn, пакет «sklearn.manifold» можно заменить на «cuml.manifold», и все остальное будет работать.

Вот Блокнот Jupyter, демонстрирующий демонстрацию cuML TSNE на Fashion MNIST.

Дополнительные примеры TSNE и более глубокое погружение в математическую оптимизацию TSNE можно найти в более расширенном Jupyter Notebook здесь.

Заключение

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

С новой реализацией RAPIDS TSNE можно достичь ускорения до 2 000 раз при одновременном использовании на 30% меньше памяти графического процессора. Узнайте, что вы думаете, и оставьте отзыв. Попробуйте бесплатно cuML TSNE на экземпляре Google Colab здесь.

Ссылки для ЦНЭ

Дэвид М. Чан, Рошан Рао, Форрест Хуанг, Джон Ф. Кэнни: t-SNE-CUDA: t-SNE с ускорением на GPU и его приложения для современных данных https://arxiv.org/pdf/1807.11824. pdf [31 июля 2018 г.]

Джордж К. Линдерман, Манас Рах, Джереми Г. Хоскинс, Стефан Штайнербергер, Юваль Клюгер: Эффективные алгоритмы для t-распределенного встраивания стохастического окружения https://arxiv.org/abs/1712.09005 [25 декабря 2017 г.]

Лоуренс ван дер Маатен, Джеффри Хинтон: Визуализация многомерных данных с использованием t-SNE https://lvdmaaten.github.io/publications/papers/JMLR_2008.pdf [2008]