Стохастическое вложение соседей с t-распределением

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

Описание

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

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

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

Детали

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

$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})}},$

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

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

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

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

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

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

$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-распределение Стьюдента (с одной степенью свободы, которое является тем же, что и распределение Коши) используется для измерения похожести между точками в пространстве низкой размерности, чтобы иметь возможность непохожие объекты расположить на карте далеко друг от друга. Заметим, что в этом случае мы также устанавливаем $q_{ii}=0$

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

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

Минимизация расстояния Кульбака — Лейблера по отношению к точкам $\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