Стохастическое вложение соседей с t-распределением (англ. t-distributed Stochastic Neighbor Embedding, t-SNE) — это алгоритм машинного обучения для визуализации, разработанный Лоренсом ван дер Маатеном и Джеффри Хинтоном^[1]. Он является техникой нелинейного снижения размерности^[англ.], хорошо подходящей для вложения данных высокой размерности для визуализации в пространство низкой размерности (двух- или трехмерное). В частности, метод моделирует каждый объект высокой размерности двух- или трёхмерной точкой таким образом, что похожие объекты моделируются близко расположенными точками, а непохожие точки моделируются с большой вероятностью точками, далеко друг от друга отстоящими.

Алгоритм t-SNE состоит из двух главных шагов. Сначала t-SNE создаёт распределение вероятностей по парам объектов высокой размерности таким образом, что похожие объекты будут выбраны с большой вероятностью, в то время как вероятность выбора непохожих точек будет мала. Затем t-SNE определяет похожее распределение вероятностей по точкам в пространстве малой размерности и минимизирует расстояние Кульбака — Лейблера между двумя распределениями с учётом положения точек. Заметим, что исходный алгоритм использует евклидово расстояние между объектами как базу измерения сходства, это может быть изменено сообразно обстоятельствам.

Алгоритм t-SNE использовался для визуализации широкого ряда приложений, включая исследование компьютерной безопасности^[2], музыкальный анализ^{[англ.][3]}, исследования по раку^{[англ.][4]}, биоинформатику^[5] и обработку биомедицинских сигналов^[6]. Алгоритм часто используется для визуализации высокоуровневых представлений, полученных из искусственной нейронной сети^[7].

Поскольку t-SNE отображения часто используются для показа кластеров, а на визуализацию кластеров может оказывать значительное влияние выбранная параметризация, постольку необходимо умение работать с параметрами алгоритма t-SNE. Для выбора параметров и проверки результатов могут оказаться необходимы интерактивные^{[неизвестный термин]} исследования^[8][9]. Было продемонстрировано, что алгоритм t-SNE часто способен обнаружить хорошо отделённые друг от друга кластеры, а при специальном выборе параметров аппроксимировать простой вид спектральной кластеризации^[10].

Если дан набор из ${\displaystyle N}$ объектов высокой размерности ${\displaystyle \mathbf {x} _{1},\dots ,\mathbf {x} _{N))$, t-SNE сначала вычисляет вероятности ${\displaystyle p_{ij))$, которые пропорциональны похожести объектов ${\displaystyle \mathbf {x} _{i))$ и ${\displaystyle \mathbf {x} _{j))$ следующим образом:

${\displaystyle p_{j\mid i}={\frac {\exp(-\lVert \mathbf {x} _{i}-\mathbf {x} _{j}\rVert ^{2}/2\sigma _{i}^{2})}{\sum _{k\neq i}\exp(-\lVert \mathbf {x} _{i}-\mathbf {x} _{k}\rVert ^{2}/2\sigma _{i}^{2}))),}$

Ван дер Маатен и Хинтон объясняли: «Похожесть точки данных ${\displaystyle x_{j))$ точке ${\displaystyle x_{i))$ является условной вероятностью ${\displaystyle p_{j|i))$, что для ${\displaystyle x_{i))$ будет выбрана ${\displaystyle x_{j))$ в качестве соседней точки, если соседи выбираются пропорционально их гауссовой плотности вероятности с центром в ${\displaystyle x_{i))$»^[1].

${\displaystyle p_{ij}={\frac {p_{j\mid i}+p_{i\mid j)){2N))}$

Более того, вероятности с ${\displaystyle i=j}$ принимаются равными нулю: ${\displaystyle p_{ii}=0}$

Полоса пропускания гауссовых ядер ${\displaystyle \sigma _{i))$ устанавливается с помощью метода бисекции так, что перплексивность^[англ.] условного распределения равна предопределённой перплексивности. Как результат полоса пропускания адаптируется плотности данных — меньшие значения ${\displaystyle \sigma _{i))$ используются в более плотных частях пространства данных.

Поскольку гауссово ядро использует евклидово расстояние ${\displaystyle \lVert x_{i}-x_{j}\rVert }$, оно подвержено проклятию размерности и в данных высокой размерности, когда расстояния теряют возможность различать, ${\displaystyle p_{ij))$ становятся слишком похожи (асимптотически, они сходятся к константе). Предлагается подкорректировать расстояние с помощью экспоненциального преобразования, основываясь на внутреннем размере^[англ.] каждой точки, чтобы смягчить проблему^[11].

Алгоритм t-SNE стремится получить отображение ${\displaystyle \mathbf {y} _{1},\dots ,\mathbf {y} _{N))$ в ${\displaystyle d}$-мерное пространство (с ${\displaystyle \mathbf {y} _{i}\in \mathbb {R} ^{d))$), которое отражает похожести ${\displaystyle p_{ij))$, насколько это возможно. Для этого алгоритм измеряет похожесть ${\displaystyle q_{ij))$ между двумя точками ${\displaystyle \mathbf {y} _{i))$ и ${\displaystyle \mathbf {y} _{j))$ с помощью очень похожего подхода. Конкретно, ${\displaystyle q_{ij))$ определяется как

${\displaystyle q_{ij}={\frac {(1+\lVert \mathbf {y} _{i}-\mathbf {y} _{j}\rVert ^{2})^{-1)){\sum _{k\neq l}(1+\lVert \mathbf {y} _{k}-\mathbf {y} _{l}\rVert ^{2})^{-1))))$

Здесь имеющее утяжелённый хвост t-распределение Стьюдента (с одной степенью свободы, которое является тем же, что и распределение Коши) используется для измерения похожести между точками в пространстве низкой размерности, чтобы иметь возможность непохожие объекты расположить на карте далеко друг от друга. Заметим, что в этом случае мы также устанавливаем ${\displaystyle q_{ii}=0}$

Расположения точек ${\displaystyle \mathbf {y} _{i))$ в пространстве малой размерности определяется минимизацией (несимметричной) расстояния Кульбака — Лейблера распределения ${\displaystyle Q}$ от распределения ${\displaystyle P}$, то есть

${\displaystyle KL(P||Q)=\sum _{i\neq j}p_{ij}\log {\frac {p_{ij)){q_{ij))))$

Минимизация расстояния Кульбака — Лейблера по отношению к точкам ${\displaystyle \mathbf {y} _{i))$ осуществляется с помощью градиентного спуска. Результатом оптимизации является отображение, которое отражает похожесть между объектами пространства высокой размерности.

• Алгоритм Лоуренса ван дер Маатена «t-Distributed Stochastic Neighbor Embedding» https://lvdmaaten.github.io/tsne/
• ELKI^[англ.] содержит tSNE с аппроксимацией Барнеса-Хата. https://github.com/elki-project/elki/blob/master/elki/src/main/java/de/lmu/ifi/dbs/elki/algorithm/projection/TSNE.java (недоступная ссылка)

• Visualizing Data Using t-SNE, Google Tech Talk about t-SNE

Машинное обучение и data mining
Задачи	Задача классификации Обучение без учителя Обучение с частичным привлечением учителя Регрессионный анализ AutoML Ассоциативные правила Выделение признаков Обучение признакам Обучение ранжированию Грамматический вывод Онлайновое обучение
Обучение с учителем	Метод k ближайших соседей Наивный байесовский классификатор Дерево решений Метод опорных векторов Линейная регрессия Логистическая регрессия Перцептрон Ансамблевое обучение Бэггинг Бустинг Метод случайного леса Метод релевантных векторов
Кластерный анализ	Метод k-средних Метод нечёткой кластеризации Иерархическая кластеризация EM-алгоритм BIRCH CURE DBSCAN OPTICS Mean-shift
Снижение размерности	Факторный анализ Метод главных компонент CCA ICA LDA Неотрицательное матричное разложение t-SNE
Структурное прогнозирование	Графовая вероятностная модель Байесовская сеть Скрытая марковская модель CRF
Выявление аномалий	Метод k ближайших соседей Локальный уровень выброса
Графовые вероятностные модели	Байесовская сеть Марковская сеть Скрытая марковская модель
Нейронные сети	Ограниченная машина Больцмана Самоорганизующаяся карта Функция активации Сигмоида Softmax Радиально-базисная функция Метод обратного распространения ошибки Глубокое обучение Многослойный перцептрон Рекуррентная нейронная сеть Долгая краткосрочная память Управляемый рекуррентный блок Свёрточная нейронная сеть U-Net Автокодировщик
Обучение с подкреплением	Марковский процесс Уравнение Беллмана Жадный алгоритм Q-обучение SARSA Temporal difference (TD)
Теория	Размерность Вапника — Червоненкиса Дилемма смещения–дисперсии Теория вычислительного обучения Минимизация эмпирического риска Оккамово обучение PAC learning Статистическая теория обучения
Журналы и конференции	NeurIPS ICML ML JMLR ArXiv:cs.LG