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

Стохастическое вложение соседей с 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