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

{{Машинне навчання|Знижування розмірності}}
{{Унаочнення даних}}
'''T-розподілене вкладення стохастичної близькості''' ({{lang-en|t-distributed Stochastic Neighbor Embedding}}, t-SNE)&nbsp;— це метод [[Машинне навчання|машинного навчання]] візуалізації даних, розроблений Лоренсом ван дер Маатеном і [[Джефрі Гінтон]]ом.<ref name=MaatenHinton>{{cite journal|last=van der Maaten|first=L.J.P.|author2=Hinton, G.E.|title=Visualizing Data Using t-SNE|journal=Journal of Machine Learning Research|volume=9|date=Nov 2008|pages=2579–2605|url=http://jmlr.org/papers/volume9/vandermaaten08a/vandermaaten08a.pdf|accessdate=27 грудня 2018|archive-date=9 серпня 2017|archive-url=https://web.archive.org/web/20170809055554/http://jmlr.org/papers/volume9/vandermaaten08a/vandermaaten08a.pdf}}</ref> Це зручний {{Нп|метод нелінійного зниження розмірності|||nonlinear dimensionality reduction}} шляхом [[вкладення]] багатовимірних даних у дво- або тривимірний простір для подальшої візуалізації. Зокрема, він відображає кожну точку багатовимірного простору в дво- або тривимірну точку евклідового простору так, що подібні об'єкти розташовуються поруч, а несхожі об'єкти відповідають віддаленим точкам з високою ймовірністю.

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

t-SNE використовується для візуалізації в різноманітних застосунках, таких як дослідження по [[Комп'ютерна безпека|комп'ютерній безпеці]],<ref>{{cite journal|last=Gashi|first=I.|author2=Stankovic, V. |author3=Leita, C. |author4=Thonnard, O. |title=An Experimental Study of Diversity with Off-the-shelf AntiVirus Engines|journal=Proceedings of the IEEE International Symposium on Network Computing and Applications|year=2009|pages=4–11}}</ref> [[Музичний аналіз|аналізу музики]],<ref>{{cite journal|last=Hamel|first=P.|author2=Eck, D. |title=Learning Features from Music Audio with Deep Belief Networks|journal=Proceedings of the International Society for Music Information Retrieval Conference|year=2010|pages=339–344}}</ref> {{Нп|Дослідження раку|дослідженнях раку||Cancer research}},<ref>{{cite journal|last=Jamieson|first=A.R.|author2=Giger, M.L. |author3=Drukker,  K. |author4=Lui, H. |author5=Yuan, Y. |author6=Bhooshan, N. |title=Exploring Nonlinear Feature Space Dimension Reduction and Data Representation in Breast CADx with Laplacian Eigenmaps and t-SNE|journal=Medical Physics  |issue=1|year=2010|pages=339–351|doi=10.1118/1.3267037|pmid=20175497|volume=37|pmc=2807447}}</ref> [[Біоінформатика|біоінформатики]],<ref>{{cite journal|last=Wallach|first=I.|author2=Liliean, R. |title=The Protein-Small-Molecule Database, A Non-Redundant Structural Resource for the Analysis of Protein-Ligand Binding|journal=Bioinformatics |year=2009|pages=615–620|doi=10.1093/bioinformatics/btp035|volume=25|issue=5|pmid=19153135}}</ref> та біомедичній обробці сигналів.<ref>{{Cite book|last=Birjandtalab|first=J.|last2=Pouyan|first2=M. B.|last3=Nourani|first3=M.|date=2016-02-01|title=Nonlinear dimension reduction for EEG-based epileptic seizure detection|url=http://ieeexplore.ieee.org/lpdocs/epic03/wrapper.htm?arnumber=7455968|journal=2016 IEEE-EMBS International Conference on Biomedical and Health Informatics (BHI)|pages=595–598|doi=10.1109/BHI.2016.7455968|isbn=978-1-5090-2455-1}}</ref> Він часто використовується для візуалізації високорівневих представлень, отриманих за допомогою [[Штучна нейронна мережа|штучної нейронної мережі]].<ref>{{Cite web |url=https://colah.github.io/posts/2015-01-Visualizing-Representations/ |title=''Visualizing Representations: Deep Learning and Human Beings'' Блог Крістофера Ола, 2015 |accessdate=27 грудня 2018 |archive-date=25 вересня 2017 |archive-url=https://web.archive.org/web/20170925022513/http://colah.github.io/posts/2015-01-Visualizing-Representations/ }}</ref>

Хоча візуалізації отримані за допомогою t-SNE часто використовуються для відображення [[Кластерний аналіз|кластерів]], отримане зображення може суттєво залежати від обраної параметризації і тому потрібне глибоке розуміння параметрів, які використовуються для t-SNE. Навіть для некластеризованих даних можуть з'явитись «кластери»<ref>{{Cite web|url=https://stats.stackexchange.com/a/264647|title=K-means clustering on the output of t-SNE|last=|first=|date=|website=Cross Validated|archiveurl=|archivedate=|deadurl=|accessdate=2018-04-16}}</ref>, що може привести до помилкових висновків. Тим самим, для правильного підбору параметрів і перевірки результатів може бути потрібне інтерактивне дослідження даних.<ref>{{Cite journal|last=Pezzotti|first=Nicola|last2=Lelieveldt|first2=Boudewijn P. F.|last3=Maaten|first3=Laurens van der|last4=Hollt|first4=Thomas|last5=Eisemann|first5=Elmar|last6=Vilanova|first6=Anna|date=2017-07-01|title=Approximated and User Steerable tSNE for Progressive Visual Analytics|url=http://ieeexplore.ieee.org/document/7473883/|journal=IEEE Transactions on Visualization and Computer Graphics|language=en-US|volume=23|issue=7|pages=1739–1752|doi=10.1109/tvcg.2016.2570755|pmid=28113434|issn=1077-2626|accessdate=27 грудня 2018|archive-date=30 листопада 2018|archive-url=https://web.archive.org/web/20181130220626/https://ieeexplore.ieee.org/document/7473883/}}</ref><ref>{{cite web|url=https://distill.pub/2016/misread-tsne/|title=How to Use t-SNE Effectively|last=Wattenberg|first=Martin|last2=Viégas|first2=Fernanda|date=2016-10-13|publisher=Distill|language=English|accessdate=4 грудня 2017|last3=Johnson|first3=Ian|archive-date=19 грудня 2017|archive-url=https://web.archive.org/web/20171219083719/https://distill.pub/2016/misread-tsne/}}</ref> Було продемонстровано, що t-SNE часто здатний відновлювати добре розділені кластери, та зі спеціальним вибором параметрів, він наближається до простої форми [[Спектральна кластеризація|спектральної кластеризації]].<ref>{{cite arxiv|last=Linderman|first=George C.|last2=Steinerberger|first2=Stefan|date=2017-06-08|title=Clustering with t-SNE, provably|eprint=1706.02582|class=cs.LG}}</ref>

== Деталі ==
Для даного набору <math>N</math> багатовимірних об'єктів <math>\mathbf{x}_1, \dots, \mathbf{x}_N</math> t-SNE спочатку обчислює ймовірності <math>p_{ij}</math> пропорційні схожості <math>\mathbf{x}_i</math> і <math>\mathbf{x}_j</math> наступним чином:

: <math>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)},</math>

Ван дер Маатен та [[Джефрі Гінтон|Гінтон]] пояснюють такий вибір відстані наступним чином: «подібність точки даних <math>x_j</math> до точки даних <math>x_i</math>&nbsp;— це умовна ймовірність, <math>p_{j|i}</math>, що <math>x_i</math> вибрав би <math>x_j</math> як свого сусіда, якби сусіди були обрані пропорційно їх гаусовій [[Густина імовірності|густині ймовірності]] з центром в <math>x_i</math>.»<ref name=MaatenHinton/>

: <math>p_{ij} = \frac{p_{j\mid i} + p_{i\mid j}}{2N}</math>

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

Пропускна здатність [[Функція Гауса|Гаусового ядра]] <math>\sigma_i</math>встановлюється за допомогою [[метод бісекції|методу бісекції]] так, що [[перплексивність]] умовного розподілу дорівнює попередньо визначеній перплексивності. У результаті пропускна здатність адаптується до [[Густина|густини]] даних: менші значення <math>\sigma_i</math> використовуються у більш густих частинах даних.

Через те що [[Функція Гауса|Гаусове ядро]] використовує евклідову відстань <math>\lVert x_i-x_j \rVert</math>, то, у випадку дуже високої розмірності даних, слід мати на увазі ефект [[прокляття розмірності]], коли відстані втрачають здатність до розділення і <math>p_{ij}</math> стають дуже схожими (асимптотично, вони збігаються до константи).
Для пом'якшення цього ефекту запропоновано<ref>{{Cite conference|last=Schubert|first=Erich|last2=Gertz|first2=Michael|date=2017-10-04|title=Intrinsic t-Stochastic Neighbor Embedding for Visualization and Outlier Detection|conference=SISAP 2017 – 10th International Conference on Similarity Search and Applications|pages=188–203|doi=10.1007/978-3-319-68474-1_13}}</ref> регулювати відстані степеневим перетворенням, спираючись на {{Нп|Внутрішня розмірність|внутрішню розмірність||Intrinsic dimension}} кожної точки.

t-SNE намагається дізнатись <math>d</math>-вимірне відображення <math>\mathbf{y}_1, \dots, \mathbf{y}_N</math> (де <math>\mathbf{y}_i \in \mathbb{R}^d</math>), яке відображає подібність <math>p_{ij}</math> наскільки це можливо. З цією метою він вимірює схожість <math>q_{ij}</math> між двома точками відображення <math>\mathbf{y}_i</math> та <math>\mathbf{y}_j</math> за допомогою аналогічного підходу. Зокрема, <math>q_{ij}</math> визначається як:

: <math>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}}</math>

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

Координати точок <math>\mathbf{y}_i</math> при відображенні визначаються шляхом мінімізації (несиметричної) відмінності по [[Розходження Кульбака — Лейблера|мірі Кульбака–Лейблера]] розподілу <math>Q</math> від розподілу <math>P</math>, тобто:

: <math>KL(P||Q) = \sum_{i \neq j} p_{ij} \log \frac{p_{ij}}{q_{ij}}</math>

Мінімізація розбіжностей Кульбака–Лейблера по точкам <math>\mathbf{y}_i</math> здійснюється за допомогою [[Градієнтний спуск|градієнтного спуску]]. Результатом такої оптимізації є відображення, яке добре зберігає подібність між входовими даними високої розмірності.

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

* t-SNE від Лоренса ван дер Маатена https://lvdmaaten.github.io/tsne/ {{Webarchive|url=https://web.archive.org/web/20181228160132/http://lvdmaaten.github.io/tsne/ |date=28 грудня 2018 }}
* {{Нп|ELKI|||}} містить t-SNE. Див. https://github.com/elki-project/elki/blob/master/elki/src/main/java/de/lmu/ifi/dbs/elki/algorithm/projection/TSNE.java{{Недоступне посилання|date=жовтня 2019 |bot=InternetArchiveBot }}

== Примітки ==
{{reflist}}

== Посилання ==

* [https://www.youtube.com/watch?v=RJVL80Gg3lA Візуалізація даних за допомогою t-SNE] {{Webarchive|url=https://web.archive.org/web/20180724043508/https://www.youtube.com/watch?v=RJVL80Gg3lA |date=24 липня 2018 }}, Google Tech Talk про t-SNE
* [https://lvdmaaten.github.io/tsne/ Реалізація t-SNE різними мовами програмування] {{Webarchive|url=https://web.archive.org/web/20181228160132/http://lvdmaaten.github.io/tsne/ |date=28 грудня 2018 }}, список посилань підтримує Лоренс ван дер Маатен
* {{Cite news|title=How to Use t-SNE Effectively|issue=10|first3=Ian|last2=Viégas|first2=Fernanda|last=Wattenberg|first=Martin|language=en|volume=1|url=http://distill.pub/2016/misread-tsne|pages=e2|doi=10.23915/distill.00002|issn=2476-0757|accessdate=2021-01-04|date=2016-10-13|work=Distill|last3=Johnson|archive-date=3 січня 2021|archive-url=https://web.archive.org/web/20210103203243/https://distill.pub/2016/misread-tsne/}}

[[Категорія:Алгоритми машинного навчання]]