t-SNE или t распределенное встраивание стохастических соседей — это прежде всего метод визуализации данных, родственный анализу основных компонентов (по крайней мере, его применение). Причина, по которой я использовал PCA в качестве примера, заключается в том, что их часто сравнивают и спорят о том, какая из них лучше. В то время как PCA, безусловно, находит свое применение в разработке признаков и определении важных признаков, с точки зрения визуализации данных более высокого измерения в более низких измерениях посредством уменьшения размерности, t-SNE, безусловно, является лучшим выбором (хотя он может быть очень дорогим в вычислительном отношении).

Не слишком углубляясь в математику (хотя я всегда обнаруживаю, что элементарное понимание или ощущение лежащих в основе концепций помогает моему пониманию), я хочу попытаться объяснить, почему t-SNE является таким превосходным алгоритмом для визуализации данных более низкого измерения.

t-SNE (t-Stochastic Neighbor Embedding) — это метод, используемый для уменьшения размерности. Цель, которую он пытается достичь, аналогична тому, что пытается сделать PCA, но в то же время он решает один из самых больших недостатков PCA — он может разделять нелинейно разделяемые данные в более низких измерениях.

Одно из других основных отличий заключается в том, что, хотя PCA является детерминированным и, следовательно, может быть масштабирован для большего количества точек данных, полученных из одного и того же распределения, t-SNE является недетерминированным итеративным алгоритмом, выходные данные которого будут меняться в зависимости от того, добавляются или удаляются точки данных. .
Это связано с тем, что PCA представляет собой линейную модель с решением в замкнутой форме. Мы можем напрямую применить формулу с нашими данными в качестве входных данных и получить значения наших основных компонентов (см. мою статью о PCA, чтобы узнать, как это сделать).
Однако отображения t-SNE с более низкой размерностью находятся итерационным способом. Это связано с тем, что под капотом t-SNE пытается решить проблему оптимизации, используя такие методы, как градиентный спуск (мы вернемся к этому позже в статье).

Приступая к основам, t-SNE использует Embedding, т. е. отображает/встраивает точки из более высокого измерения в более низкое измерение.

По сути, это достигается путем моделирования распределения расстояний между точками (просто возьмите любую точку данных в качестве центра, рассчитайте евклидово расстояние или любую другую форму расстояния этой точки от каждую вторую точку и построить распределение этих расстояний. Продолжайте делать это для КАЖДОЙ отдельной точки данных) в более высоких (N измерениях), а также в более низких измерениях (M измерениях, N>M). Мы знаем распределение этих расстояний в исходном высшем измерении. Чего мы изначально не знаем, так это распределения межточечных расстояний в нижнем измерении.

Подумайте об этом

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

Давайте попробуем получить базовое представление о математике, лежащей в основе формулировки задачи оптимизации.

Предположим, что для каждой точки в более высоком измерении расстояния до всех других точек распределены по гауссову закону с определенной дисперсией в зависимости от выбранной сложности (сложность — это настраиваемый параметр алгоритма t-SNE, который уравновешивает то, сколько внимания вы хотите уделить локальному измерению). против глобальных кластеров, подробнее об этом можно узнать здесь).

Предположим, что вероятность dist. функция расстояния между любыми двумя точками xi и xj в многомерном пространстве задается как P[i|j].

Точно так же функция распределения вероятностей расстояний между соответствующими точками yi и yj в пространстве меньшей размерности задается как Q[i|j].

Однако здесь есть оговорка. Помните, мы предполагали, что распределения расстояний в более высоком измерении являются гауссовыми? Логично предположить, что распределения этих расстояний в нижнем измерении также являются гауссовыми. В конце концов, мы пытаемся найти наиболее точное представление этих распределений более высокого порядка в более низком измерении. Так думали и создатели оригинального алгоритма SNE Хинтон и Ровейс. Оказывается, это предположение приводит к так называемой проблеме скученности.

Обратите внимание, что функция распределения в нижнем измерении Q[i|j] в этом случае также является нормальным распределением.

Не вдаваясь в подробности, «проблема скученности» возникает из-за того, что большинство расстояний между точками в нижнем измерении скучены вокруг среднего значения. Это связано с характером распределения Гаусса, которое имеет тенденцию назначать расстояния точкам, намного более близким к xj в более низком измерении.

Это означает, что большинство точек в нижнем измерении расположены относительно близко друг к другу, а кластеры теснятся друг вокруг друга!

Вы можете видеть, как кластеры в SNE теснятся друг вокруг друга, в то время как кластеры, сформированные с использованием t-SNE, лучше разделены. У нас уже были метки каждой точки данных, поэтому мы можем сопоставить каждому кластеру свой цвет. Однако в случае неразмеченных данных, когда наша цель состоит в том, чтобы найти и идентифицироватькластеры, в некоторых случаях (например, показанном выше) было бы очень сложно или почти невозможно использовать SNE из-за проблема скученности.

Так как же t-SNE решает эту проблему? Давайте подумаем, какую проблему мы пытаемся решить. Стандартное гауссово распределение тесно связано со средним значением, при этом не придается большого значения точкам, находящимся дальше. Мы хотим немного расширить распределение, чтобы больше точек располагалось на расстоянии дальше от среднего, то есть мы хотим немного больше распределить распределение в более низких измерениях (более длинное хвостовое распределение). Так что, возможно, мы могли бы рассмотреть другое распределение, которое делает именно это, но при этом очень похоже на распределение Гаусса (помните, что наша основная цель по-прежнему состоит в том, чтобы найти очень точное приближение точек в пространстве меньшего измерения). , поэтому мы не можем использовать радикально другое распределение, такое как Пуассон).

Это именно то, что делает t-SNE! Он предполагает, что расстояния в пространстве меньшего измерения НЕ подчиняются распределению Гаусса, как в пространстве большего размера, а скорее распределению Стьюдента (это то, что означает «t» в t-SNE). Это помогает нам решить проблему скученности.

Теперь, когда нам ясно, как t-SNE улучшает SNE, давайте резюмируем.

Мы смоделировали гауссово распределение расстояний в высшем измерении P[i|j] и предположили, что расстояния следуют t-распределению Q[i|j] в нижнее измерение. Теперь нам нужно определить, какими должны быть соответствующие точки в нижнем измерении, чтобы эти расстояния в более высоком измерении сохранялись в нижнем измерении.

Если мы подумаем об этом интуитивно, это означает, что мы должны попытаться выбрать точки в нижнем измерении так, чтобы их t-распределения расстояний были как можно более похожи на гауссово распределение расстояний в более высоком измерении. Эта мера сходства фиксируется расхождением Кульбака-Лейблера D_KL, которое по существу измеряет, насколько похожи два распределения друг на друга (мы не будем вдаваться в математику здесь, но вот видео и блог, который интуитивно объясняет).

Все, что нам нужно знать, это то, что чем меньше значение дивергенции, тем более похожи распределения.

Идеальный! Мы можем принять это как функцию стоимости, которую нам нужно оптимизировать! Какой метод сразу же приходит на ум, который помогает нам итеративно оптимизировать функцию затрат? Хммм… *кашель* Градиентный спуск *кашель*

Вы думали о градиентном спуске? (алгоритм использует градиентный спуск с импульсом) Вот именно! Также помогает то, что вычисление градиента функции расхождения Кульбака-Лейблера чрезвычайно просто!

Давайте определим алгоритм -
1) Для некоторых итераций T мы можем инициализировать значения Yi (помните, X — это набор наших исходных точек данных в более высоком измерении, а Y – это набор точек в более низком измерении) к некоторым арбитражным значениям из t-распределения и вычислить функцию стоимости D_KL (аналогично прямому распространению).

2) Теперь найдите производную функции стоимости относительно Y(градиента) и обновите значения Yi, используя градиентный спуск (аналогично обратному распространению). По сути, мы меняем/обновляем отображения точек Yi в нижнем измерении после каждой итерации таким образом, чтобы максимально приблизить t-распределение в нижнем измерении к распределению Гаусса в высшее измерение!

После достаточного количества итераций мы получаем оптимальные значения Y (то есть точки в нижнем измерении), которые минимизируют нашу функцию стоимости, то есть расхождение Кульбака-Лейблера.

И вуаля! Мы успешно сопоставили точки из более высокого измерения в более низкое измерение, сохраняя при этом расстояния между точками (кластерами) настолько хорошо, насколько могли!

Это суть того, что делает t-SNE. Конечно, у t-SNE есть несколько недостатков.

  1. Основным недостатком является то, что это очень дорого в вычислительном отношении, особенно когда количество функций очень велико. Общепринятой практикой является использование более простого метода уменьшения размерности, такого как PCA, чтобы уменьшить количество признаков (примерно до 50 или около того), а затем применить t-SNE к этим данным с уменьшенным размером.
  2. Расстояния между кластерами не дают никакой информации. Тот факт, что два кластера могут быть близко друг к другу или далеко, не означает, что они более или менее похожи. Исходное семя рандомизации, используемое на первом этапе, может привести к очень разным визуализациям кластеров в одном и том же наборе данных.
  3. У него есть настраиваемый параметр, называемый растерянностью. Распространенной ошибкой является запуск t-SNE только с одним значением недоумения и вывод ваших выводов. Perplexity, как и любой другой гиперпараметр, необходимо настроить с несколькими значениями, прежде чем делать выводы. Эта статья предоставляет отличный интерактивный способ визуализации и понимания эффекта растерянности при t-SNE.
  4. Он не аппроксимирует общую функцию, которую можно применить к данным вне выборки. Это означает, что выходные данные этого не могут быть переданы никаким алгоритмам прогнозирования, чтобы узнать что-либо о данных (в отличие от PCA, где полученные основные компоненты могут использоваться в качестве входных данных для других моделей прогнозирования, таких как регрессия и т. д.).

Конечно, это не охватывает все плюсы и минусы t-SNE, но я надеюсь, что эта статья дала вам лучшее понимание того, что делает t-SNE!

Вы можете посмотреть оригинальную статью для t-SNE, если вам интересно дальше.
Кроме того, на странице авторов github вы можете найти реализации t-SNE на множестве языков, таких как как Python, R, Matlab и т. д., если вам интересно!

Ну вот и все, не стесняйтесь обращаться, если у вас есть какие-либо вопросы или вы хотите обсудить это подробнее.