t-SNE

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

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

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

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

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

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

Алгоритм t-SNE

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

Подготовка данных
Вычисление расстояний, Гауссовых отклонений и сходств
Инициализируйте встраивание и расхождение
Градиентный спуск расхождения Кулбэка-Лейблера

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

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

Оригинальные авторы van der Maaten и Hinton [1] рекомендуют уменьшить исходные данные X до более низкой размерности с помощью Principal Component Analysis (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 пытается минимизировать расхождение Куллбэка-Лейблера между модельным Гауссовым распределением точек в 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, расхождение Кулбака и Лейблера между P распределения соединений и Q,

$K L (P | | Q) = \sum_{j} \sum_{i \neq j} p_{i j} \log \frac{p_{i j}}{q_{i j}} .$

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

Градиентный спуск расхождения Кулбэка-Лейблера

Чтобы минимизировать расхождение Куллбэка-Лейблера, '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' является умножителем градиента тока для линейной комбинации. Для получения дополнительной информации смотрите Jacobs [3].

Барнс-Хат Изменение t-SNE

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

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

См. Ван дер Маатен [2].

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

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

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

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

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

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

Точные t-SNE берут порядок D * N² операции.
Barnes-Hut t-SNE принимает заказ D * N log (N) * exp (dimension (Y)) операции.

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

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

Открыть Live Script

T-SNE отображает высокомерные расстояния на искаженные маломерные аналоги. Из-за более толстого хвоста распределения Student 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

Figure contains an axes. The axes with title Density of Gaussian(0,1) and Student t (df = 1) contains 10 objects of type line, text. These objects represent Gaussian(0,1), Student t (df = 1).

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

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

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

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

Ссылки

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

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

[3] Jacobs, Robert A. «Увеличение темпов сходимости посредством адаптации скорости обучения». Нейронные сети 1.4, 1988, с. 295-307.

[4] Ваттенберг, Мартин, Фернанда Виегас и Ян Джонсон. «Эффективное использование t-SNE». Дистилль, 2016. Доступно в How to Use t-SNE Effectively.

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