t-SNE

Что такое t-SNE?

t-SNE (tsne) является алгоритмом для сокращения размерности, которое является подходящим к визуализации высоко-размерных данных. Имя обозначает t - распределил Стохастическое Соседнее Встраивание. Идея состоит в том, чтобы встроить высоко-размерные точки в низкие размерности способом, который уважает общие черты между точками. Соседние точки в высоком мерном пространстве соответствуют поблизости встроенным низко-размерным точкам, и удаленные точки в высоком мерном пространстве соответствуют удаленным встроенным низко-размерным точкам. (Обычно невозможно совпадать с расстояниями точно между высоко-размерными и низкими мерными пространствами.)

Функция tsne создает набор низко-размерных точек от высоко-размерных данных. Как правило, вы визуализируете низко-размерные точки, чтобы видеть естественные кластеры в исходных высоко-размерных данных.

Алгоритм делает следующие общие шаги, чтобы встроить данные в низкие размерности.

Вычислите попарные расстояния между высоко-размерными точками.
Создайте стандартное отклонение _σi для каждой высоко-размерной точки i так, чтобы perplexity каждой точки был на предопределенном уровне. Для определения недоумения смотрите, Вычисляют Расстояния, Гауссовы Отклонения и Общие черты.
Вычислите similarity matrix. Это - объединенное распределение вероятностей X, заданный уравнением 1.
Создайте начальный набор низко-размерных точек.
Итеративно обновите низко-размерные точки, чтобы минимизировать расхождение Kullback-Leibler между Распределением Гаусса в высоком мерном пространстве и распределением t в низком мерном пространстве. Эта процедура оптимизации является самой длительной частью алгоритма.

Смотрите ван дер Маатена и Хинтона [1].

Алгоритм t-SNE

Основной t-SNE алгоритм выполняет следующие шаги.

Подготовка данных
Вычислите расстояния, гауссовы отклонения и общие черты
Инициализируйте встраивание и расхождение
Спуск градиента расхождения Kullback-Leibler

Подготовка данных

tsne сначала удаляет каждую строку входных данных X, который содержит любые значения NaN. Затем если парой "имя-значение" Standardize является true, tsne центрируется X путем вычитания среднего значения каждого столбца и масштабируется X путем деления его столбцов на их стандартные отклонения.

Исходные авторы ван дер Маатен и Хинтон [1] рекомендуют уменьшать исходные данные X до более низко-размерной версии с помощью Анализа главных компонентов (PCA). Можно установить пару "имя-значение" NumPCAComponents tsne на количество размерностей, которые вы любите, возможно, 50. Чтобы осуществить больше контроля над этим шагом, предварительно обработайте данные с помощью функции pca.

Вычислите расстояния, гауссовы отклонения и общие черты

После предварительной обработки tsne вычисляет расстояние d (_xi, _xj) между каждой парой точек _xi и _xj в X. Можно выбрать различные метрики расстояния с помощью пары "имя-значение" Distance. По умолчанию tsne использует стандартную Евклидову метрику. tsne использует квадрат метрики расстояния в ее последующих вычислениях.

Затем для каждой строки i X, tsne вычисляет стандартное отклонение _σi так, чтобы perplexity строки i был равен паре "имя-значение" Perplexity. Недоумение задано с точки зрения образцового Распределения Гаусса можно следующим образом. Как ван дер Маатен и Хинтон [1] описывают, “Подобие точки данных _xj к точке данных _xi является условной вероятностью, $p_{j | i}$ , тот _xi выбрал бы _xj как своего соседа, если бы соседи были выбраны в пропорции к их плотности вероятности под Гауссовым, сосредоточенным в _xi. Для соседних точек данных, $p_{j | i}$ относительно высоко, тогда как для широко разделенных точек данных, $p_{j | i}$ будет почти бесконечно малая величина (для рыночной стоимости отклонения Гауссова, _σi)”.

Задайте условную вероятность j, данного i как

$\begin{array}{l} p_{j | i} = \frac{\exp (- d {(x_{i}, x_{j})}^{2} / (2 σ_{i}^{2}))}{\sum_{k \neq i} \exp (- d {(x_{i}, x_{k})}^{2} / (2 σ_{i}^{2}))} \\ p_{i | i} = 0. \end{array}$

Затем задайте объединенную вероятность _pij путем симметрирования условных вероятностей:

p_{i j} = \frac{p_{j | i} + p_{i | j}}{2 N},

(1)

где N является количеством строк X.

Дистрибутивам все еще не задали их стандартные отклонения _σi с точки зрения пары "имя-значение" Perplexity. Позволенный _Pi представляет распределение условной вероятности по всем другим точкам данных, данным точку данных _xi. Недоумение распределения

$недоумение (P_{i}) = 2^{H (P_{i})},$

где H (_Pi) является шенноновской энтропией _Pi:

$H (P_{i}) = - \sum_{j} p_{j | i} {журнал}_{2} (p_{j | i}) .$

Недоумение измеряет эффективное количество соседей точки i. tsne выполняет двоичный поиск по _σi, чтобы достигнуть фиксированного недоумения для каждой точки i.

Инициализируйте встраивание и расхождение

Чтобы встроить точки в X в низкое мерное пространство, tsne выполняет оптимизацию. tsne пытается минимизировать расхождение Kullback-Leibler между образцовым Распределением Гаусса точек в X и Студентом распределение t точек Y в низком мерном пространстве.

Процедура минимизации начинается с начального набора точек Y. tsne создает точки по умолчанию как случайные Распределенные гауссовым образом точки. Можно также создать эти точки сами и включать их в пару "имя-значение" 'InitialY' для tsne. tsne затем вычисляет общие черты между каждой парой точек в Y.

Вероятностная модель _qij распределения расстояний между точками _yi и _yj

$\begin{array}{l} q_{i j} = \frac{{(1 + {‖ y_{i} - y_{j} ‖}^{2})}^{- 1}}{\sum_{k} \sum_{l \neq k} {(1 + {‖ y_{k} - y_{l} ‖}^{2})}^{- 1}} \\ q_{i i} = 0. \end{array}$

Используя это определение и модель расстояний в X данный уравнением 1, расхождение Kullback-Liebler между совместным распределением P и Q

$K L (P | | Q) = \sum_{j} \sum_{i \neq j} p_{i j} журнал \frac{p_{i j}}{q_{i j}} .$

Для последствий этого определения смотрите Полезное Нелинейное Искажение.

Спуск градиента расхождения Kullback-Leibler

Чтобы минимизировать расхождение Kullback-Leibler, алгоритм 'exact' использует измененную процедуру спуска градиента. Градиент относительно точек в Y расхождения

$\frac{\partial K L (P | | Q)}{\partial y_{i}} = 4 \sum_{j \neq i} Z (p_{i j} - q_{i j}) q_{i j} (y_{i} - y_{j}),$

где термин нормализации

$Z = \sum_{k} \sum_{l \neq k} {(1 + {‖ y_{k} - y_{l} ‖}^{2})}^{- 1} .$

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

'Exaggeration' — Во время первых 99 шагов спуска градиента tsne умножает вероятности _pij от уравнения 1 значением преувеличения. Этот шаг имеет тенденцию создавать больше пространства между кластерами в выводе Y.
'LearnRate' — tsne использует адаптивное обучение улучшить сходимость итераций спуска градиента. Алгоритм спуска имеет итеративные шаги, которые являются линейной комбинацией предыдущего шага в спуске и текущем градиенте. 'LearnRate' является множителем текущего градиента для линейной комбинации. Для получения дополнительной информации смотрите Джейкобса [3].

Изменение Barnes-хижины t-SNE

Чтобы ускорить t-SNE алгоритм и сократить его использование памяти, tsne предлагает аппроксимированную схему оптимизации. Алгоритм Barnes-хижины собирает в группу соседние точки, чтобы понизить сложность и использование памяти t-SNE шага оптимизации. Алгоритм Barnes-хижины является аппроксимированным оптимизатором, не точным оптимизатором. Существует неотрицательный настраивающий параметр Theta, который производит компромисс между скоростью и точностью. Большие значения 'Theta' дают более быстрые но менее точные результаты оптимизации. Алгоритм относительно нечувствителен к значениям 'Theta' в области значений (0.2 0.8).

Группы алгоритма Barnes-хижины поблизости указывают в низком мерном пространстве и выполняют аппроксимированный спуск градиента на основе этих групп. Идея, первоначально используемая в астрофизике, состоит в том, что градиент подобен для соседних точек, таким образом, вычисления могут быть упрощены.

Смотрите ван дер Маатена [2].

Характеристики t-SNE

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

Не может использовать встраивание, чтобы классифицировать новые данные

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

Производительность зависит от размеров данных и алгоритма

t-SNE может занять много времени, чтобы обработать данные. Если у вас есть точки данных N в размерностях D, которые вы хотите сопоставить с размерностями Y, то

Точные t-SNE взятия операций D *N2 порядка.
Barnes-хижина t-SNE взятия порядка D *Nlog (N) *exp (размерность (Y)) операции.

Таким образом для больших наборов данных, где N больше, чем приблизительно 1000, и где размерность встраивания Y равняется 2 или 3, алгоритм Barnes-хижины может быть быстрее, чем точный алгоритм.

Полезное нелинейное искажение

T-SNE сопоставляет высоко-размерные расстояния до искаженных низко-размерных аналогов. Из-за более толстого хвоста Студента распределение t в низком мерном пространстве tsne часто двигает близкие точки поближе вместе и перемещает далекие точки дальше независимо, чем в высоком мерном пространстве, как проиллюстрировано в следующей фигуре. Данные показывают и Гауссов и Студент дистрибутивы t в точках, где плотность в 0,25 и 0.025. Гауссова плотность относится к высоко-размерным расстояниям, и плотность t относится к низко-размерным расстояниям. Плотность t соответствует близким точкам, являющимся ближе, и далеко указывает быть более далеким, по сравнению с Гауссовой плотностью.

t = linspace(0,5);
y1 = normpdf(t,0,1);
y2 = tpdf(t,1);
plot(t,y1,'k',t,y2,'r')
hold on
x1 = fzero(@(x)normpdf(x,0,1)-0.25,[0,2]);
x2 = fzero(@(x)tpdf(x,1)-0.25,[0,2]);
z1 = fzero(@(x)normpdf(x,0,1)-0.025,[0,5]);
z2 = fzero(@(x)tpdf(x,1)-0.025,[0,5]);
plot([0,x1],[0.25,0.25],'k-.')
plot([0,z2],[0.025,0.025],'k-.')
plot([x1,x1],[0,0.25],'g-',[x2,x2],[0,0.25],'g-')
plot([z1,z1],[0,0.025],'g-',[z2,z2],[0,0.025],'g-')
text(1.1,.25,'Close points are closer in low-D')
text(2.4,.05,'Far points are farther in low-D')
legend('Gaussian(0,1)','Student t (df = 1)')
xlabel('x')
ylabel('Density')
title('Density of Gaussian(0,1) and Student t (df = 1)')
hold off

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

Установите пару "имя-значение" 'Verbose' на 2.
Настройте пару "имя-значение" 'Perplexity', таким образом, область значений, о которой сообщают, отклонений не слишком далека от 1, и среднее отклонение около 1.

Если можно достигнуть этой области значений отклонений, то схема применяется, и искажение tsne полезно.

Для эффективных способов настроить tsne, смотрите Wattenberg, Виегаса и Джонсона [4].

Ссылки

[1] ван дер Маатен, Лоренс и Джеффри Хинтон. Визуализация Данных с помощью t-SNE. J. Исследование Машинного обучения 9, 2008, стр 2579–2605.

[2] ван дер Маатен, Laurens. Барнс-Хут-СН. arXiv:1301.3342 [cs. LG], 2013.

[3] Джейкобс, Роберт А. Увеличенные уровни сходимости посредством адаптации темпа обучения. Нейронные сети 1.4, 1988, стр 295–307.

[4] Wattenberg, Мартин, Фернанда Виегас и Иэн Джонсон. Как Использовать t-SNE Эффективно. Дистиллируйте, 2016. Доступный в How to Use t-SNE Effectively.

Документация