T-розподілене вкладення стохастичної близькості

T-розподілене вкладення стохастичної близькості (англ. t-distributed Stochastic Neighbor Embedding, t-SNE) — це метод машинного навчання візуалізації даних, розроблений Лоренсом ван дер Маатеном і Джефрі Гінтоном.^[1] Це зручний метод нелінійного зниження розмірності^[en] шляхом вкладення багатовимірних даних у дво- або тривимірний простір для подальшої візуалізації. Зокрема, він відображає кожну точку багатовимірного простору в дво- або тривимірну точку евклідового простору так, що подібні об'єкти розташовуються поруч, а несхожі об'єкти відповідають віддаленим точкам з високою ймовірністю.

Алгоритм t-SNE складається з двох основних етапів. Спочатку, t-SNE створює розподіл імовірностей по парах багатовимірних об'єктів таким чином, що подібні об'єкти мають високу ймовірність бути вибраними, у той час як несхожі точки мають надзвичайно малу ймовірність бути вибраними разом. Далі, t-SNE визначає подібний розподіл ймовірностей для точок у карті низьковимірного простору та мінімізує розбіжності за відстанню Кульбака–Лейблера між двома розподілами за місцем розташування точок на карті. Зверніть увагу, що хоч оригінальний алгоритм і використовує евклідову відстань між об'єктами, як основну метрику подібності об'єктів, проте, вона може бути змінена при необхідності.

t-SNE використовується для візуалізації в різноманітних застосунках, таких як дослідження по комп'ютерній безпеці,^[2] аналізу музики,^[3] дослідженнях раку^[en],^[4] біоінформатики,^[5] та біомедичній обробці сигналів.^[6] Він часто використовується для візуалізації високорівневих представлень, отриманих за допомогою штучної нейронної мережі.^[7]

Хоча візуалізації отримані за допомогою t-SNE часто використовуються для відображення кластерів, отримане зображення може суттєво залежати від обраної параметризації і тому потрібне глибоке розуміння параметрів, які використовуються для t-SNE. Навіть для некластеризованих даних можуть з'явитись «кластери»^[8], що може привести до помилкових висновків. Тим самим, для правильного підбору параметрів і перевірки результатів може бути потрібне інтерактивне дослідження даних.^[9]^[10] Було продемонстровано, що t-SNE часто здатний відновлювати добре розділені кластери, та зі спеціальним вибором параметрів, він наближається до простої форми спектральної кластеризації.^[11]

Деталі

Для даного набору $N$ багатовимірних об'єктів $\mathbf {x} _{1},\dots ,\mathbf {x} _{N}$ t-SNE спочатку обчислює ймовірності $p_{ij}$ пропорційні схожості $\mathbf {x} _{i}$ і $\mathbf {x} _{j}$ наступним чином:

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})}},

Ван дер Маатен та Гінтон пояснюють такий вибір відстані наступним чином: «подібність точки даних $x_{j}$ до точки даних $x_{i}$ — це умовна ймовірність, $p_{j|i}$ , що $x_{i}$ вибрав би $x_{j}$ як свого сусіда, якби сусіди були обрані пропорційно їх гаусовій густині ймовірності з центром в $x_{i}$ .»^[1]

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

Більш того, коли $i=j$ , ймовірності дорівнюють нулю: $p_{ij}=0$

Пропускна здатність Гаусового ядра $\sigma _{i}$ встановлюється за допомогою методу бісекції так, що перплексивність умовного розподілу дорівнює попередньо визначеній перплексивності. У результаті пропускна здатність адаптується до густини даних: менші значення $\sigma _{i}$ використовуються у більш густих частинах даних.

Через те що Гаусове ядро використовує евклідову відстань $\lVert x_{i}-x_{j}\rVert$ , то, у випадку дуже високої розмірності даних, слід мати на увазі ефект прокляття розмірності, коли відстані втрачають здатність до розділення і $p_{ij}$ стають дуже схожими (асимптотично, вони збігаються до константи). Для пом'якшення цього ефекту запропоновано^[12] регулювати відстані степеневим перетворенням, спираючись на внутрішню розмірність^[en] кожної точки.

t-SNE намагається дізнатись $d$ -вимірне відображення $\mathbf {y} _{1},\dots ,\mathbf {y} _{N}$ (де $\mathbf {y} _{i}\in \mathbb {R} ^{d}$ ), яке відображає подібність $p_{ij}$ наскільки це можливо. З цією метою він вимірює схожість $q_{ij}$ між двома точками відображення $\mathbf {y} _{i}$ та $\mathbf {y} _{j}$ за допомогою аналогічного підходу. Зокрема, $q_{ij}$ визначається як:

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-розподіл Стьюдента з обважнілим кінцем (з одним ступенем свободи, який є по суті розподілом Коші) для вимірювання подібностей між точками у низьковимірному просторі для того, щоб різнорідні об'єкти були змодельовані далеко один від одного при відображенні. Зверніть увагу, що в даному випадку ми прирівнюємо $q_{ii}=0.$

Координати точок $\mathbf {y} _{i}$ при відображенні визначаються шляхом мінімізації (несиметричної) відмінності по мірі Кульбака–Лейблера розподілу $Q$ від розподілу $P$ , тобто:

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

Мінімізація розбіжностей Кульбака–Лейблера по точкам $\mathbf {y} _{i}$ здійснюється за допомогою градієнтного спуску. Результатом такої оптимізації є відображення, яке добре зберігає подібність між входовими даними високої розмірності.

Програмне забезпечення

t-SNE від Лоренса ван дер Маатена https://lvdmaaten.github.io/tsne/ [Архівовано 28 грудня 2018 у Wayback Machine.]
ELKI^[en] містить t-SNE. Див. https://github.com/elki-project/elki/blob/master/elki/src/main/java/de/lmu/ifi/dbs/elki/algorithm/projection/TSNE.java^{[недоступне посилання з жовтня 2019]}

Примітки

↑ ^а ^б van der Maaten, L.J.P.; Hinton, G.E. (Nov 2008). Visualizing Data Using t-SNE (PDF). Journal of Machine Learning Research. 9: 2579—2605. Архів оригіналу (PDF) за 9 серпня 2017. Процитовано 27 грудня 2018.
↑ Gashi, I.; Stankovic, V.; Leita, C.; Thonnard, O. (2009). An Experimental Study of Diversity with Off-the-shelf AntiVirus Engines. Proceedings of the IEEE International Symposium on Network Computing and Applications: 4—11.
↑ Hamel, P.; Eck, D. (2010). Learning Features from Music Audio with Deep Belief Networks. Proceedings of the International Society for Music Information Retrieval Conference: 339—344.
↑ Jamieson, A.R.; Giger, M.L.; Drukker, K.; Lui, H.; Yuan, Y.; Bhooshan, N. (2010). Exploring Nonlinear Feature Space Dimension Reduction and Data Representation in Breast CADx with Laplacian Eigenmaps and t-SNE. Medical Physics. 37 (1): 339—351. doi:10.1118/1.3267037. PMC 2807447. PMID 20175497.
↑ Wallach, I.; Liliean, R. (2009). The Protein-Small-Molecule Database, A Non-Redundant Structural Resource for the Analysis of Protein-Ligand Binding. Bioinformatics. 25 (5): 615—620. doi:10.1093/bioinformatics/btp035. PMID 19153135.
↑ Birjandtalab, J.; Pouyan, M. B.; Nourani, M. (1 лютого 2016). Nonlinear dimension reduction for EEG-based epileptic seizure detection. с. 595—598. doi:10.1109/BHI.2016.7455968. ISBN 978-1-5090-2455-1. {{cite book}}: Проігноровано |journal= (довідка)
↑ Visualizing Representations: Deep Learning and Human Beings Блог Крістофера Ола, 2015. Архів оригіналу за 25 вересня 2017. Процитовано 27 грудня 2018.
↑ K-means clustering on the output of t-SNE. Cross Validated. Процитовано 16 квітня 2018.
↑ Pezzotti, Nicola; Lelieveldt, Boudewijn P. F.; Maaten, Laurens van der; Hollt, Thomas; Eisemann, Elmar; Vilanova, Anna (1 липня 2017). Approximated and User Steerable tSNE for Progressive Visual Analytics. IEEE Transactions on Visualization and Computer Graphics (амер.). 23 (7): 1739—1752. doi:10.1109/tvcg.2016.2570755. ISSN 1077-2626. PMID 28113434. Архів оригіналу за 30 листопада 2018. Процитовано 27 грудня 2018.
↑ Wattenberg, Martin; Viégas, Fernanda; Johnson, Ian (13 жовтня 2016). How to Use t-SNE Effectively (English) . Distill. Архів оригіналу за 19 грудня 2017. Процитовано 4 грудня 2017.
↑ Linderman, George C.; Steinerberger, Stefan (8 червня 2017). Clustering with t-SNE, provably. arXiv:1706.02582 [cs.LG].
↑ Schubert, Erich; Gertz, Michael (4 жовтня 2017). Intrinsic t-Stochastic Neighbor Embedding for Visualization and Outlier Detection. SISAP 2017 – 10th International Conference on Similarity Search and Applications. с. 188—203. doi:10.1007/978-3-319-68474-1_13.

Посилання

Візуалізація даних за допомогою t-SNE [Архівовано 24 липня 2018 у Wayback Machine.], Google Tech Talk про t-SNE
Реалізація t-SNE різними мовами програмування [Архівовано 28 грудня 2018 у Wayback Machine.], список посилань підтримує Лоренс ван дер Маатен
Wattenberg, Martin; Viégas, Fernanda; Johnson, Ian (13 жовтня 2016). How to Use t-SNE Effectively. Distill (англ.). Т. 1, № 10. с. e2. doi:10.23915/distill.00002. ISSN 2476-0757. Архів оригіналу за 3 січня 2021. Процитовано 4 січня 2021.

[MaatenHinton-1] а ^б van der Maaten, L.J.P.; Hinton, G.E. (Nov 2008). Visualizing Data Using t-SNE (PDF). Journal of Machine Learning Research. 9: 2579—2605. Архів оригіналу (PDF) за 9 серпня 2017. Процитовано 27 грудня 2018.

[2] Gashi, I.; Stankovic, V.; Leita, C.; Thonnard, O. (2009). An Experimental Study of Diversity with Off-the-shelf AntiVirus Engines. Proceedings of the IEEE International Symposium on Network Computing and Applications: 4—11.

[3] Hamel, P.; Eck, D. (2010). Learning Features from Music Audio with Deep Belief Networks. Proceedings of the International Society for Music Information Retrieval Conference: 339—344.

[4] Jamieson, A.R.; Giger, M.L.; Drukker, K.; Lui, H.; Yuan, Y.; Bhooshan, N. (2010). Exploring Nonlinear Feature Space Dimension Reduction and Data Representation in Breast CADx with Laplacian Eigenmaps and t-SNE. Medical Physics. 37 (1): 339—351. doi:10.1118/1.3267037. PMC 2807447. PMID 20175497.

[5] Wallach, I.; Liliean, R. (2009). The Protein-Small-Molecule Database, A Non-Redundant Structural Resource for the Analysis of Protein-Ligand Binding. Bioinformatics. 25 (5): 615—620. doi:10.1093/bioinformatics/btp035. PMID 19153135.

[6] Birjandtalab, J.; Pouyan, M. B.; Nourani, M. (1 лютого 2016). Nonlinear dimension reduction for EEG-based epileptic seizure detection. с. 595—598. doi:10.1109/BHI.2016.7455968. ISBN 978-1-5090-2455-1. {{cite book}}: Проігноровано |journal= (довідка)

[7] Visualizing Representations: Deep Learning and Human Beings Блог Крістофера Ола, 2015. Архів оригіналу за 25 вересня 2017. Процитовано 27 грудня 2018.

[8] K-means clustering on the output of t-SNE. Cross Validated. Процитовано 16 квітня 2018.

[9] Pezzotti, Nicola; Lelieveldt, Boudewijn P. F.; Maaten, Laurens van der; Hollt, Thomas; Eisemann, Elmar; Vilanova, Anna (1 липня 2017). Approximated and User Steerable tSNE for Progressive Visual Analytics. IEEE Transactions on Visualization and Computer Graphics (амер.). 23 (7): 1739—1752. doi:10.1109/tvcg.2016.2570755. ISSN 1077-2626. PMID 28113434. Архів оригіналу за 30 листопада 2018. Процитовано 27 грудня 2018.

[10] Wattenberg, Martin; Viégas, Fernanda; Johnson, Ian (13 жовтня 2016). How to Use t-SNE Effectively (English) . Distill. Архів оригіналу за 19 грудня 2017. Процитовано 4 грудня 2017.

[11] Linderman, George C.; Steinerberger, Stefan (8 червня 2017). Clustering with t-SNE, provably. arXiv:1706.02582 [cs.LG].

[12] Schubert, Erich; Gertz, Michael (4 жовтня 2017). Intrinsic t-Stochastic Neighbor Embedding for Visualization and Outlier Detection. SISAP 2017 – 10th International Conference on Similarity Search and Applications. с. 188—203. doi:10.1007/978-3-319-68474-1_13.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]