Стохастическое вложение соседей с 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 (недоступная+ссылка)

Примечания

1. van der Maaten, Hinton, 2008, с. 2579–2605.
2. Gashi, Stankovic, Leita, Thonnard, 2009, с. 4–11.
3. Hamel, Eck, 2010, с. 339–344.
4. Jamieson, Giger, Drukker, Lui, Yuan, Bhooshan, 2010, с. 339–35.
5. Wallach, Liliean, 2009, с. 615–620.
6. Birjandtalab, Pouyan, Nourani, 2016, с. 595–598.
7. Olah’s blog, 2015.
8. Pezzotti, Lelieveldt, van der Maaten и др., 2017, с. 1739–1752.
9. Wattenberg, Viégas, Johnson, 2016.
10. Linderman, Steinerberger, 2017.
11. Schubert, Gertz, 2017, с. 188–203.

Литература

• van der Maaten L.J.P., Hinton G.E. Visualizing Data Using t-SNE // Journal of Machine Learning Research. — 2008. — Ноябрь (т. 9).
• Gashi I., Stankovic V., Leita C., Thonnard O. An Experimental Study of Diversity with Off-the-shelf AntiVirus Engines // Proceedings of the IEEE International Symposium on Network Computing and Applications. — 2009.
• Hamel P., Eck D. Learning Features from Music Audio with Deep Belief Networks // Proceedings of the International Society for Music Information Retrieval Conference. — 2010.
• Jamieson A.R., Giger M.L., Drukker K., Lui H., Yuan Y., Bhooshan N. Exploring Nonlinear Feature Space Dimension Reduction and Data Representation in Breast CADx with Laplacian Eigenmaps and t-SNE // Medical Physics. — 2010. — Т. 37, вып. 1. — doi:10.1118/1.3267037. — PMID 20175497. — PMC 2807447.
• Wallach I., Liliean R. The Protein-Small-Molecule Database, A Non-Redundant Structural Resource for the Analysis of Protein-Ligand Binding // Bioinformatics. — 2009. — Т. 25, вып. 5. — doi:10.1093/bioinformatics/btp035. — PMID 19153135.
• Birjandtalab J., Pouyan M. B., Nourani M. Nonlinear dimension reduction for EEG-based epileptic seizure detection. — 2016 IEEE-EMBS International Conference on Biomedical and Health Informatics (BHI). — 2016. — ISBN 978-1-5090-2455-1. — doi:10.1109/BHI.2016.7455968.
• Christopher Olah. Visualizing Representations: Deep Learning and Human Beings. — 2015.
• Nicola Pezzotti, Boudewijn P. F. Lelieveldt, Laurens van der Maaten, Thomas Hollt, Elmar Eisemann, Anna Vilanova. Approximated and User Steerable tSNE for Progressive Visual Analytics // IEEE Transactions on Visualization and Computer Graphics. — 2017. — Т. 23, вып. 7. — ISSN 1077-2626. — doi:10.1109/tvcg.2016.2570755. — PMID 28113434.
• Martin Wattenberg, Fernanda Viégas, Ian Johnson. How to Use t-SNE Effectively. — Distill, 2016.
• George C. Linderman, Stefan Steinerberger. Clustering with t-SNE, provably. — 2017.
• Erich Schubert, Michael Gertz. Intrinsic t-Stochastic Neighbor Embedding for Visualization and Outlier Detection // SISAP 2017 – 10th International Conference on Similarity Search and Applications. — 2017. — doi:10.1007/978-3-319-68474-1_13.

Ссылки

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