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). Можно установить tsne NumPCAComponents пара "имя-значение" к количеству размерностей вам нравится, возможно, 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. Недоумение распределения

$perplexity (P_{i}) = 2^{H (P_{i})},$

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

$H (P_{i}) = - \sum_{j} p_{j | i} \log_{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} \log \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.

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