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

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

Описание

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

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

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

Детали

Если дан набор из $N$ объектов высокой размерности ${𝐱}_1,\dots ,{𝐱}_N$, t-SNE сначала вычисляет вероятности $p_{ij}$, которые пропорциональны похожести объектов ${𝐱}_i$ и ${𝐱}_j$ следующим образом:

$p_{j\mid i}=\frac{\exp (-\Vert {𝐱}_i-{𝐱}_j{\Vert }^2/2{\sigma }_i^2)}{\sum _{k\ne i}\exp (-\Vert {𝐱}_i-{𝐱}_k{\Vert }^2/2{\sigma }_i^2)},$

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

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

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

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

Поскольку гауссово ядро использует евклидово расстояние $\Vert x_i-x_j\Vert$, оно подвержено проклятию размерности и в данных высокой размерности, когда расстояния теряют возможность различать, $p_{ij}$ становятся слишком похожи (асимптотически, они сходятся к константе). Предлагается подкорректировать расстояние с помощью экспоненциального преобразования, основываясь на Шаблон:Не переведено 5 каждой точки, чтобы смягчить проблемуШаблон:Sfn.

Алгоритм t-SNE стремится получить отображение ${𝐲}_1,\dots ,{𝐲}_N$ в $d$-мерное пространство (с ${𝐲}_i\in {ℝ}^d$), которое отражает похожести $p_{ij}$, насколько это возможно. Для этого алгоритм измеряет похожесть $q_{ij}$ между двумя точками ${𝐲}_i$ и ${𝐲}_j$ с помощью очень похожего подхода. Конкретно, $q_{ij}$ определяется как

$q_{ij}=\frac{(1+\Vert {𝐲}_i-{𝐲}_j{\Vert }^2{)}^{-1}}{\sum _{k\ne l}(1+\Vert {𝐲}_k-{𝐲}_l{\Vert }^2{)}^{-1}}$

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

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

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

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

Программное обеспечение

• Алгоритм Лоуренса ван дер Маатена «t-Distributed Stochastic Neighbor Embedding» https://lvdmaaten.github.io/tsne/
• Шаблон:Не переведено 5 содержит 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