Стохастическое вложение соседей с 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-распределение Стьюдента (с одной степенью свободы, которое является тем же, что и распределение Коши) используется для измерения похожести между точками в пространстве низкой размерности, чтобы иметь возможность непохожие объекты расположить на карте далеко друг от друга. Заметим, что в этом случае мы также устанавливаем
Расположения точек в пространстве малой размерности определяется минимизацией (несимметричной) расстояния Кульбака — Лейблера распределения от распределения , то есть
Минимизация расстояния Кульбака — Лейблера по отношению к точкам осуществляется с помощью градиентного спуска. Результатом оптимизации является отображение, которое отражает похожесть между объектами пространства высокой размерности.
Программное обеспечение
- Алгоритм Лоуренса ван дер Маатена «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 2 van der Maaten, Hinton, 2008, с. 2579–2605.
- ↑ Gashi, Stankovic, Leita, Thonnard, 2009, с. 4–11.
- ↑ Hamel, Eck, 2010, с. 339–344.
- ↑ Jamieson, Giger, Drukker, Lui, Yuan, Bhooshan, 2010, с. 339–35.
- ↑ Wallach, Liliean, 2009, с. 615–620.
- ↑ Birjandtalab, Pouyan, Nourani, 2016, с. 595–598.
- ↑ Olah’s blog, 2015.
- ↑ Pezzotti, Lelieveldt, van der Maaten и др., 2017, с. 1739–1752.
- ↑ Wattenberg, Viégas, Johnson, 2016.
- ↑ Linderman, Steinerberger, 2017.
- ↑ 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