Sztochasztikus szomszéd beágyazás t-elosztással

A t -distributed Stochastic Neighbor Embedding ( t-SNE) egy gépi tanulási algoritmus a vizualizációhoz , amelyet Laurens van der Maaten és Geoffrey Hinton fejlesztett ki [1] . Ez egy nemlineáris dimenziócsökkentési technika , amely kiválóan alkalmas nagy dimenziós adatok beágyazására kis dimenziós térben (2D vagy 3D) való megjelenítés céljából Konkrétan, a módszer minden nagydimenziós objektumot két- vagy háromdimenziós ponttal úgy modellez, hogy a hasonló objektumokat egymáshoz közel elhelyezkedő pontok, a különböző pontokat pedig nagy valószínűséggel az egymástól távol eső pontok modellezzék.

Leírás

A t-SNE algoritmus két fő lépésből áll. Először is, a t-SNE valószínűségi eloszlást hoz létre a nagydimenziós jellemzők párja között, így nagy valószínűséggel hasonló jellemzők kerülnek kiválasztásra, míg nem valószínű, hogy eltérő pontokat választanak ki. Ezután a t-SNE hasonló valószínűségi eloszlást határoz meg egy kis dimenziós tér pontjai között, és minimalizálja a Kullback-Leibler távolságot a két eloszlás között, figyelembe véve a pontok helyzetét. Vegye figyelembe, hogy az eredeti algoritmus az objektumok közötti euklideszi távolságot használja a hasonlóság mérésének alapjául, ez szükség szerint módosítható.

A t-SNE algoritmust számos alkalmazás vizualizálására használták, beleértve a számítógépes biztonsági kutatásokat [2] , a zeneelemzést [3] , a rákkutatást [4] , a bioinformatikát [5] és az orvosbiológiai jelfeldolgozást . [6] . Az algoritmust gyakran használják mesterséges neurális hálózatból nyert magas szintű reprezentációk megjelenítésére [7] .

Mivel a t-SNE kijelzőket gyakran használják klaszterek megjelenítésére , és a paraméterezés megválasztása jelentősen befolyásolhatja a klaszterek megjelenítését, a t-SNE algoritmus paramétereivel való munkaképesség szükséges. Interaktív [ kifejezés ismeretlen ] vizsgálatok [8] [9] szükségesek lehetnek a paraméterek kiválasztásához és az eredmények validálásához . Bebizonyosodott, hogy a t-SNE algoritmus gyakran képes az egymástól jól elkülönülő klaszterek kimutatására, és a paraméterek speciális megválasztásával közelíteni a spektrális klaszterezés egy egyszerű formáját [10] .

Részletek

Adott egy sor nagydimenziós jellemzőt, a t-SNE először kiszámítja a valószínűségeket , amelyek arányosak a jellemzők hasonlóságával, és a következők szerint: $N$ ${\displaystyle \mathbf {x} _{1},\dots ,\mathbf {x} _{N))$ $p_{{ij}}$ ${\displaystyle \mathbf {x} _{i))$ ${\displaystyle \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 és Hinton kifejtette: "Az adatpontnak egy ponthoz való hasonlósága annak a feltételes valószínűsége , hogy a -t választják szomszédos pontnak, ha a szomszédokat arányosan választják ki a Gauss-féle valószínűségi sűrűségükkel, amelynek középpontja " [1] . $x_{j}$ $x_{i}$ ${\displaystyle p_{j|i))$ $x_{i}$ $x_{j}$ $x_{i}$

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

Ezenkívül a c valószínűségeket nullával egyenlőnek tekintjük: $i=j$ $p_{ii}=0$

A Gauss-kernelek sávszélességét a felezési módszerrel úgy állítjuk be , hogy a feltételes eloszlás perplexitása egyenlő legyen az előre meghatározott perplexitással. Ennek eredményeként a sávszélesség az adatsűrűséghez igazodik - az adattér sűrűbb részein kisebb értékeket használnak. $\sigma_i$ $\sigma_i$

Mivel a Gauss-kernel az euklideszi távolságot használja , ki van téve a dimenzionalitás átkának, és a nagy dimenziós adatokban, amikor a távolságok megkülönböztethetetlenné válnak, túlságosan hasonlóvá válnak (aszimptotikusan konvergálnak egy állandóhoz). Javasoljuk, hogy a távolságot exponenciális transzformációval állítsuk be az egyes pontok belső mérete a probléma enyhítésére [11] . $\lVert x_{i}-x_{j}\rVert$ $p_{{ij}}$

A t-SNE algoritmus olyan -dimenziós térre ( s ) való leképezésre törekszik, amely a lehető legjobban tükrözi a hasonlóságokat . Ehhez az algoritmus két pont közötti hasonlóságot méri, és nagyon hasonló megközelítést alkalmaz. Konkrétan úgy van meghatározva ${\displaystyle \mathbf {y} _{1},\dots ,\mathbf {y} _{N))$ $d$ ${\displaystyle \mathbf {y} _{i}\in \mathbb {R} ^{d))$ $p_{{ij}}$ $q_{ij}$ ${\displaystyle \mathbf {y} _{i))$ ${\displaystyle \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}}}

Itt egy súlyozott farkú Student-féle t-eloszlást használunk (egy szabadságfokkal, ami megegyezik a Cauchy-eloszlással ) az alacsony dimenziós térben lévő pontok közötti hasonlóság mérésére annak érdekében, hogy a különböző objektumokat egymástól távol el lehessen helyezni. a térképen. Vegye figyelembe, hogy ebben az esetben is beállítjuk $q_{ii}=0$

A pontok elhelyezkedését az alacsony dimenziós térben úgy határozzuk meg, hogy minimalizáljuk az eloszlás (aszimmetrikus) Kullback-Leibler távolságát az eloszlástól , azaz. ${\displaystyle \mathbf {y} _{i))$ $K$ $P$

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

A Kullback-Leibler távolság minimálisra csökkentése a pontokhoz képest gradiens süllyedés használatával történik . Az optimalizálás eredménye egy olyan leképezés, amely tükrözi a nagydimenziós térben lévő objektumok közötti hasonlóságot. ${\displaystyle \mathbf {y} _{i))$

Szoftver

Lawrence van der Maaten "t-Distributed Stochastic Neighbor Embedding" algoritmusa https://lvdmaaten.github.io/tsne/
Az ELKI tartalmazza a tSNE-t Barnes-Hut közelítéssel. https://github.com/elki-project/elki/blob/master/elki/src/main/java/de/lmu/ifi/dbs/elki/algorithm/projection/TSNE.java (nem elérhető link)

Jegyzetek

↑ 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 és Nourani, 2016 , p. 595–598.
↑ Oláh blogja, 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.

Irodalom

van der Maaten LJP, Hinton GE Adatok megjelenítése t-SNE használatával // Journal of Machine Learning Research. - 2008. - november ( 9. köt. ).
Gashi I., Stankovic V., Leita C., Thonnard O. Kísérleti tanulmány a sokféleségről off-the-shelf víruskereső motorokkal // 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 , sz. 1 . - doi : 10,1118/1,3267037 . — PMID 20175497 .
Wallach I., Liliian R. The Protein-Small-Molecule Database, A Non-Redundant Structural Resource for the Analysis of Protein-Ligand Binding // Bioinformatika. - 2009. - T. 25 , sz. 5 . - doi : 10.1093/bioinformatika/btp035 . — PMID 19153135 .
Birjandtalab J., Pouyan MB, Nourani M. Nemlineáris dimenziócsökkentés az EEG-alapú epilepsziás rohamok detektálásához. — 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. Reprezentációk megjelenítése: mély tanulás és emberi lények . — 2015.
Nicola Pezzotti, Boudewijn PF Lelieveldt, Laurens van der Maaten, Thomas Hollt, Elmar Eisemann, Anna Vilanova. Közelítő és felhasználó által irányítható tSNE a progresszív vizuális elemzéshez // IEEE Transactions on Visualization and Computer Graphics. - 2017. - T. 23 , sz. 7 . — ISSN 1077-2626 . - doi : 10.1109/tvcg.2016.2570755 . — PMID 28113434 .
Martin Wattenberg, Fernanda Viegas, Ian Johnson. A t-SNE hatékony használata . — Párlat, 2016.
George C. Linderman, Stefan Steinerberger. Klaszterezés t-SNE-vel, bizonyíthatóan. — 2017.
Erich Schubert, Michael Gertz. Intrinsic t-Stochastic Neighbor Embedding for Visualization and Outlier Detection // SISAP 2017 – 10th International Conference on Hasonlóity Search and Applications. - 2017. - doi : 10.1007/978-3-319-68474-1_13 .

Linkek

Adatok megjelenítése a t-SNE használatával , a Google Tech Talk a t-SNE-ről

Gépi tanulás és adatbányászat
Feladatok	Osztályozási probléma Tanulás tanár nélkül Tanár által segített tanulás Regresszió analízis AutoML Egyesületi szabályzat Funkció kivonás Tulajdonságok képzése Rangsorképzés Nyelvtani levezetés Online tanulás
Tanulás tanárral	k-legközelebbi szomszéd módszer Naiv Bayes osztályozó döntési fa Támogatja a vektoros gépet Lineáris regresszió Logisztikus regresszió perceptron Modellek együttesei Zsákolás fellendítése véletlenszerű erdő Releváns vektoros módszer
klaszteranalízis	k-közép módszer Fuzzy klaszterezési módszer Hierarchikus klaszterezés EM algoritmus NYÍR GYÓGYMÓD DBSCAN OPTIKA Átlageltolás
Dimenziócsökkentés	Faktoranalízis Főkomponens módszer CCA ICA LDA Nem negatív mátrix kiterjesztése t-SNE
Strukturális előrejelzés	Grafikon valószínűségi modell Bayesi hálózat Rejtett Markov-modell CRF
Anomália észlelése	k-legközelebbi szomszéd módszer Helyi kibocsátási szint
Grafikon valószínűségi modellek	Bayesi hálózat Markov hálózat Rejtett Markov-modell
Neurális hálózatok	Limitált Boltzmann gép önszerveződő térkép Aktiválási funkció Szigma alakú softmax Radiális bázisfüggvény Hátsó szaporítási módszer Mély tanulás Többrétegű perceptron Ismétlődő neurális hálózat hosszú távú rövid távú memória Ellenőrzött visszatérő blokk Konvolúciós Neurális Hálózat U-Net Autoencoder
Megerősítő tanulás	Markov folyamat Bellman egyenlet Mohó algoritmus Q-learning SARSA Időbeli különbség (TD)
Elmélet	Vapnik-Chervonenkis elmélet Elfogultság-diszperziós dilemma Számítógépes tanuláselmélet Empirikus kockázatminimalizálás Occam tanul PAC tanulás Statisztikai tanuláselmélet
Folyóiratok és konferenciák	NeurIPS ICML ML JMLR ArXiv:cs.LG