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

Если дан набор из объектов высокой размерности , t-SNE сначала вычисляет вероятности , которые пропорциональны похожести объектов и следующим образом:

Ван дер Маатен и Хинтон объясняли: «Похожесть точки данных точке является условной вероятностью , что для будет выбрана в качестве соседней точки, если соседи выбираются пропорционально их гауссовой плотности вероятности с центром в »[1].

Более того, вероятности с принимаются равными нулю:

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

Поскольку гауссово ядро использует евклидово расстояние , оно подвержено проклятию размерности и в данных высокой размерности, когда расстояния теряют возможность различать, становятся слишком похожи (асимптотически, они сходятся к константе). Предлагается подкорректировать расстояние с помощью экспоненциального преобразования, основываясь на внутреннем размере[англ.] каждой точки, чтобы смягчить проблему[11].

Алгоритм t-SNE стремится получить отображение в -мерное пространство (с ), которое отражает похожести , насколько это возможно. Для этого алгоритм измеряет похожесть между двумя точками и с помощью очень похожего подхода. Конкретно, определяется как

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

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

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

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

[править | править код]

Примечания

[править | править код]

Литература

[править | править код]
  • 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.