Stochastic Neighbor Embedding cu t-Distribution

T -distributed Stochastic Neighbor Embedding ( t-SNE) este un algoritm de învățare automată pentru vizualizare dezvoltat de Laurens van der Maaten și Geoffrey Hinton [1] . Este o tehnică de reducere a dimensionalității neliniare , potrivită pentru încorporarea datelor cu dimensiuni mari pentru vizualizare în spațiu cu dimensiuni reduse (2D sau 3D) În special, metoda modelează fiecare obiect de dimensiuni înalte cu un punct bidimensional sau tridimensional astfel încât obiectele similare să fie modelate prin puncte strâns distanțate, iar punctele diferite sunt modelate cu o mare probabilitate prin puncte aflate la distanță unul de celălalt.

Descriere

Algoritmul t-SNE constă din doi pași principali. În primul rând, t-SNE creează o distribuție de probabilitate pe perechi de caracteristici cu dimensiuni mari, astfel încât caracteristicile similare sunt foarte probabil să fie selectate, în timp ce punctele diferite este puțin probabil să fie selectate. Apoi t-SNE determină o distribuție de probabilitate similară peste puncte dintr-un spațiu de dimensiuni reduse și minimizează distanța Kullback-Leibler dintre cele două distribuții, ținând cont de poziția punctelor. Rețineți că algoritmul original folosește distanța euclidiană dintre obiecte ca bază pentru măsurarea similarității, aceasta putând fi modificată după caz.

Algoritmul t-SNE a fost folosit pentru a vizualiza o gamă largă de aplicații, inclusiv cercetarea securității computerelor [2] , analiza muzicii [3] , cercetarea cancerului [4] , bioinformatica [5] și procesarea semnalelor biomedicale [6] . Algoritmul este adesea folosit pentru a vizualiza reprezentări de nivel înalt obținute dintr- o rețea neuronală artificială [7] .

Deoarece afișajele t-SNE sunt adesea folosite pentru a afișa clustere , iar alegerea parametrizării poate afecta în mod semnificativ vizualizarea clusterelor, este necesară capacitatea de a lucra cu parametrii algoritmului t-SNE. Studiile interactive [ termen necunoscut ] [8] [9] pot fi necesare pentru a selecta parametrii și a valida rezultatele . S-a demonstrat că algoritmul t-SNE este adesea capabil să detecteze clustere care sunt bine separate unul de celălalt și, cu o alegere specială de parametri, aproximează o formă simplă de clustering spectral [10] .

Detalii

Având în vedere un set de caracteristici dimensionale înalte, t-SNE calculează mai întâi probabilitățile , care sunt proporționale cu similaritatea caracteristicilor și după cum urmează: $N$ $\mathbf {x} _{1},\dots ,\mathbf {x} _{N)$ $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})}},

Van der Maaten și Hinton au explicat: „Asemănarea unui punct de date cu un punct este probabilitatea condiționată ca for să fie aleasă ca punct vecin, dacă vecinii sunt aleși proporțional cu densitatea lor de probabilitate Gauss centrată pe ” [1] . $x_{j}$ $x_{i}$ $p_{j|i)$ $x_{i}$ $x_{j}$ $x_{i}$

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

Mai mult, probabilitățile c sunt luate egale cu zero: $i=j$ $p_{ii}=0$

Lățimea de bandă a nucleelor gaussiene este setată folosind metoda bisecției astfel încât perplexitatea a distribuției condiționate să fie egală cu perplexitatea predefinită. Ca urmare, lățimea de bandă este adaptată la densitatea datelor - valori mai mici sunt utilizate în părțile mai dense ale spațiului de date. $\sigma_i$ $\sigma_i$

Deoarece nucleul gaussian folosește distanța euclidiană , este supus blestemului dimensionalității și în datele de dimensiuni mari, atunci când distanțele devin indistincte, ele devin prea asemănătoare (asimptotic, converg către o constantă). Se propune ajustarea distanței folosind o transformare exponențială bazată pe dimensiunea internă fiecărui punct pentru a atenua problema [11] . $\lVert x_{i}-x_{j}\rVert$ $p_{{ij}}$

Algoritmul t-SNE caută să obțină o mapare în spațiu (s ) dimensional care reflectă pe cât posibil asemănări. Pentru a face acest lucru, algoritmul măsoară similitudinea dintre două puncte și utilizând o abordare foarte similară. Mai exact, este definit ca $\mathbf {y} _{1},\dots,\mathbf {y} _{N)$ $d$ $\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}}}

Aici, o distribuție t a lui Student cu coadă ponderată (cu un grad de libertate, care este același cu distribuția Cauchy ) este utilizată pentru a măsura asemănarea dintre punctele din spațiul de dimensiuni reduse pentru a putea plasa obiecte diferite la distanță. pe hartă. Rețineți că și în acest caz am setat $q_{ii}=0$

Locația punctelor în spațiul de dimensiuni reduse este determinată prin minimizarea distanței Kullback-Leibler (asimetrice) a distribuției față de distribuție , i.e. $\mathbf {y} _{i)$ $Q$ $P$

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

Minimizarea distanței Kullback-Leibler în raport cu punctele se face utilizând coborârea în gradient . Rezultatul optimizării este o mapare care reflectă asemănarea dintre obiecte dintr-un spațiu cu dimensiuni mari. $\mathbf {y} _{i)$

Software

Algoritmul de „încorporare stochastică a vecinilor t-distribuit” al lui Lawrence van der Maaten https://lvdmaaten.github.io/tsne/
ELKI conține tSNE cu aproximarea Barnes-Hut. https://github.com/elki-project/elki/blob/master/elki/src/main/java/de/lmu/ifi/dbs/elki/algorithm/projection/TSNE.java (link indisponibil)

Note

↑ 12 van der Maaten , Hinton, 2008 , p. 2579–2605.
↑ Gashi, Stankovic, Leita, Thonnard, 2009 , p. 4–11.
↑ Hamel, Eck, 2010 , p. 339–344.
↑ Jamieson, Giger, Drukker, Lui, Yuan, Bhooshan, 2010 , p. 339–35.
↑ Wallach, Liliian, 2009 , p. 615–620.
↑ Birjandtalab, Pouyan și Nourani, 2016 , p. 595–598.
↑ Blogul lui Olah, 2015 .
↑ Pezzotti, Lelieveldt, van der Maaten et al., 2017 , p. 1739–1752
^ Wattenberg , Viégas, Johnson, 2016 .
↑ Linderman, Steinerberger, 2017 .
↑ Schubert, Gertz, 2017 , p. 188–203.

Literatură

van der Maaten LJP, Hinton GE Vizualizarea datelor folosind t-SNE // Journal of Machine Learning Research. - 2008. - Noiembrie ( vol. 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 AR, Giger ML, 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. - T. 37 , nr. 1 . - doi : 10.1118/1.3267037 . — PMID 20175497 .
Wallach I., Liliian R. Baza de date Protein-Small-Molecule, O resursă structurală non-redundantă pentru analiza legării proteinelor-ligand // Bioinformatică. - 2009. - T. 25 , nr. 5 . - doi : 10.1093/bioinformatics/btp035 . — PMID 19153135 .
Birjandtalab J., Pouyan MB, Nourani M. Reducerea dimensiunii neliniare pentru detectarea crizelor epileptice pe bază de EEG. — 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. Vizualizarea reprezentărilor: Învățare profundă și ființe umane . — 2015.
Nicola Pezzotti, Boudewijn PF Lelieveldt, Laurens van der Maaten, Thomas Hollt, Elmar Eisemann, Anna Vilanova. TSNE aproximat și orientabil de utilizator pentru analiză vizuală progresivă // Tranzacții IEEE privind vizualizarea și grafica pe computer. - 2017. - T. 23 , nr. 7 . — ISSN 1077-2626 . - doi : 10.1109/tvcg.2016.2570755 . — PMID 28113434 .
Martin Wattenberg, Fernanda Viegas, Ian Johnson. Cum să utilizați t-SNE în mod eficient . — Distil, 2016.
George C. Linderman, Stefan Steinerberger. Clustering cu t-SNE, probabil. — 2017.
Erich Schubert, Michael Gertz. Încorporarea intrinsecă a vecinilor t-stochastice pentru vizualizare și detectarea valorii aberante // SISAP 2017 – a 10-a Conferință internațională privind căutarea și aplicațiile similare. - 2017. - doi : 10.1007/978-3-319-68474-1_13 .

Link -uri

Vizualizarea datelor folosind t-SNE , Google Tech Talk despre t-SNE

Învățare automată și extragerea datelor
Sarcini	Problema de clasificare Învățați fără profesor Învățare asistată de profesor Analiza regresiei AutoML Regulile de asociere Extragerea caracteristicilor Antrenamentul trăsăturilor Antrenament de clasare Derivarea gramaticală Învățare online
Învățarea cu un profesor	metoda k-cel mai apropiat vecin Clasificator naiv Bayes arborele de decizie Suport mașină vectorială Regresie liniara Regresie logistică perceptron Ansambluri de modele Bagare stimularea pădure la întâmplare Metoda vectorială relevantă
analiza grupului	metoda k-means Metoda de grupare fuzzy Gruparea ierarhică algoritmul EM MESTEACĂN VINDECA DBSCAN OPTICA Schimbarea medie
Reducerea dimensionalității	Analiza factorilor Metoda componentei principale CCA ICA LDA Expansiunea nenegativă a matricei t-SNE
Prognoza structurală	Modelul probabilistic grafic Rețeaua bayesiană Modelul Markov ascuns CRF
Detectarea anomaliilor	metoda k-cel mai apropiat vecin Nivelul de emisie local
Modele grafice probabilistice	Rețeaua bayesiană Rețeaua Markov Modelul Markov ascuns
Rețele neuronale	Mașină Boltzmann limitată hartă de auto-organizare Funcția de activare Sigmoid softmax Funcția de bază radială Metoda de propagare înapoi Invatare profunda Perceptron multistrat Rețea neuronală recurentă memorie pe termen lung și scurt Bloc recurent controlat Rețeaua neuronală convoluțională U-Net Autoencoder
Consolidarea învățării	procesul Markov Ecuația Bellman Algoritmul lacom Q-learning SARSA Diferența temporală (TD)
Teorie	Teoria Vapnik-Chervonenkis Dilema părtinire-dispersie Teoria învățării computaționale Minimizarea riscului empiric Occam învață Învățarea PAC Teoria învăţării statistice
Reviste și conferințe	NeurIPS ICML ML JMLR ArXiv:cs.LG