Stokastisk granninbäddning med t-distribution

t -distributed Stochastic Neighbor Embedding ( t-SNE) är en maskininlärningsalgoritm för visualisering utvecklad av Laurens van der Maaten och Geoffrey Hinton [1] . Det är en icke-linjär dimensionsreduktionsteknik väl lämpad för att bädda in högdimensionella data för visualisering i lågdimensionellt utrymme (2D eller 3D) I synnerhet modellerar metoden varje högdimensionellt objekt med en två- eller tredimensionell punkt på ett sådant sätt att liknande objekt modelleras av tätt placerade punkter, och olika punkter modelleras med hög sannolikhet av punkter som är långt ifrån varandra.

Beskrivning

t-SNE-algoritmen består av två huvudsteg. För det första skapar t-SNE en sannolikhetsfördelning över par av högdimensionella särdrag så att liknande egenskaper med stor sannolikhet kommer att väljas, medan olika punkter sannolikt inte kommer att väljas. Sedan bestämmer t-SNE en liknande sannolikhetsfördelning över punkter i ett lågdimensionellt utrymme och minimerar Kullback-Leibler-avståndet mellan de två fördelningarna, med hänsyn till punkternas position. Observera att den ursprungliga algoritmen använder det euklidiska avståndet mellan objekt som grund för att mäta likhet, detta kan ändras vid behov.

t-SNE-algoritmen har använts för att visualisera ett brett spektrum av tillämpningar, inklusive datasäkerhetsforskning [2] , musikanalys [3] , cancerforskning [4] , bioinformatik [5] och biomedicinsk signalbehandling [6] . Algoritmen används ofta för att visualisera representationer på hög nivå erhållna från ett artificiellt neuralt nätverk [7] .

Eftersom t-SNE-skärmar ofta används för att visa kluster , och valet av parametrisering avsevärt kan påverka visualiseringen av kluster, är förmågan att arbeta med parametrarna för t-SNE-algoritmen nödvändig. Interaktiva [ term okänd ] studier [8] [9] kan vara nödvändiga för att välja parametrar och validera resultat . Det har visat sig att t-SNE-algoritmen ofta kan detektera kluster som är väl separerade från varandra, och med ett speciellt val av parametrar, approximera en enkel form av spektralkluster [10] .

Detaljer

Givet en uppsättning högdimensionella egenskaper beräknar t-SNE först sannolikheter , som är proportionella mot likheten mellan funktionerna och enligt följande: $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})}{\summa _{k\neq i}\exp(-\lVert \mathbf {x} _{i}-\mathbf {x} _{k}\rVert ^{2 }/2\sigma _{i}^{2})}},

Van der Maaten och Hinton förklarade: "Likheten mellan en datapunkt och en punkt är den villkorade sannolikheten att for kommer att väljas som en grannpunkt, om grannarna väljs proportionellt mot deras Gaussisk sannolikhetstäthet centrerad vid " [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}}

Dessutom tas sannolikheterna c lika med noll: $i=j$ $p_{ii}=0$

Bandbredden för de Gaussiska kärnorna ställs in med hjälp av bisektionsmetoden så att perplexiteten för den villkorliga fördelningen är lika med den fördefinierade perplexiteten. Som ett resultat anpassas bandbredden till datatätheten - mindre värden används i de tätare delarna av datautrymmet. $\sigma_i$ $\sigma_i$

Eftersom den Gaussiska kärnan använder det euklidiska avståndet är det föremål för dimensionalitetens förbannelse och i högdimensionella data, när avstånden blir omöjliga att särskilja, blir de för lika (asymptotiskt konvergerar de till en konstant). Det föreslås att justera avståndet med hjälp av en exponentiell transformation baserad på den interna storleken varje punkt för att mildra problemet [11] . $\lVert x_{i}-x_{j}\rVert$ $p_{{ij}}$

t-SNE-algoritmen strävar efter att erhålla en mappning i dimensionella rymd(er ) som återspeglar likheter så mycket som möjligt. För att göra detta mäter algoritmen likheten mellan två punkter och använder ett mycket liknande tillvägagångssätt. Specifikt definieras det som ${\displaystyle \mathbf {y} _{1},\dots ,\mathbf {y} _{N))$ $d$ ${\displaystyle \mathbf {y} _{i}\in \mathbb {R} ^{d))$ $p_{{ij}}$ ${\displaystyle q_{ij))$ ${\displaystyle \mathbf {y} _{i))$ ${\displaystyle \mathbf {y} _{j))$ ${\displaystyle 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}}}

Här används en viktsvansad Students t-fördelning (med en frihetsgrad, vilket är samma som Cauchy-fördelningen ) för att mäta likheten mellan punkter i lågdimensionellt rum för att kunna placera olika objekt långt ifrån varandra. på kartan. Observera att vi även i det här fallet ställer in $q_{ii}=0$

Placeringen av punkter i lågdimensionellt utrymme bestäms genom att minimera det (asymmetriska) Kullback-Leibler-avståndet för fördelningen från fördelningen , d.v.s. ${\displaystyle \mathbf {y} _{i))$ $F$ $P$

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

Minimering av Kullback-Leibler-avståndet med avseende på punkter görs med hjälp av gradientnedstigning . Resultatet av optimeringen är en kartläggning som återspeglar likheten mellan objekt i ett högdimensionellt utrymme. ${\displaystyle \mathbf {y} _{i))$

Programvara

Lawrence van der Maatens "t-Distributed Stochastic Neighbor Embedding"-algoritm https://lvdmaaten.github.io/tsne/
ELKI innehåller tSNE med Barnes-Hut approximation. https://github.com/elki-project/elki/blob/master/elki/src/main/java/de/lmu/ifi/dbs/elki/algorithm/projection/TSNE.java (ej tillgänglig länk)

Anteckningar

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

Litteratur

van der Maaten LJP, Hinton GE Visualisera data med t-SNE // Journal of Machine Learning Research. - 2008. - November ( 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. Att lära sig funktioner från musikljud med 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. Utforskar icke-linjära funktionsutrymmesdimensionsreduktion och datarepresentation i bröst-CADx med Laplacian Eigenmaps och t-SNE // Medical Physics. - 2010. - T. 37 , nr. 1 . - doi : 10.1118/1.3267037 . — PMID 20175497 .
Wallach I., Liliian R. Protein-Small-Molecule Database, En icke-redundant strukturell resurs för analys av protein-ligandbindning // Bioinformatik. - 2009. - T. 25 , nr. 5 . - doi : 10.1093/bioinformatics/btp035 . — PMID 19153135 .
Birjandtalab J., Pouyan MB, Nourani M. Icke-linjär dimensionsreduktion för EEG-baserad epileptisk anfallsdetektering. — 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. Visualisera representationer: Djupt lärande och människor . — 2015.
Nicola Pezzotti, Boudewijn PF Lelieveldt, Laurens van der Maaten, Thomas Hollt, Elmar Eisemann, Anna Vilanova. Ungefärlig och användarstyrbar tSNE för progressiv visuell analys // IEEE-transaktioner på visualisering och datorgrafik. - 2017. - T. 23 , nr. 7 . — ISSN 1077-2626 . - doi : 10.1109/tvcg.2016.2570755 . — PMID 28113434 .
Martin Wattenberg, Fernanda Viegas, Ian Johnson. Hur man använder t-SNE effektivt . — Destiller, 2016.
George C. Linderman, Stefan Steinerberger. Klustring med t-SNE, bevisligen. — 2017.
Erich Schubert, Michael Gertz. Intrinsic t-Stochastic Neighbor Embedding for visualization and outlier detection // SISAP 2017 – 10:e internationella konferensen om likhetssökning och applikationer. - 2017. - doi : 10.1007/978-3-319-68474-1_13 .

Länkar

Visualisera data med t-SNE , Google Tech Tala om t-SNE

Maskininlärning och datautvinning
Uppgifter	Klassificeringsproblem Lärande utan lärare Lärarassisterat lärande Regressionsanalys AutoML Föreningens regler Särdragsextraktion Egenskapsträning Ranking utbildning Grammatisk härledning Online lärande
Att lära sig med en lärare	k-närmaste granne metod Naiv Bayes klassificerare beslutsträd Stöd vektor maskin Linjär regression Logistisk tillbakagång perceptron Ensembler av modeller Säckväv förstärkning slumpmässig skog Relevant vektormetod
klusteranalys	k-betyder metod Fuzzy klustringsmetod Hierarkisk klustring EM algoritm BJÖRK BOTA DBSCAN OPTIK Genomsnittlig förskjutning
Dimensionalitetsreduktion	Faktoranalys Huvudkomponentmetoden CCA ICA LDA Icke-negativ matrisexpansion t-SNE
Strukturell prognos	Graph probabilistisk modell Bayesiskt nätverk Dold Markov-modell CRF
Anomali upptäckt	k-närmaste granne metod Lokal utsläppsnivå
Grafisk probabilistiska modeller	Bayesiskt nätverk Markov nätverk Dold Markov-modell
Neurala nätverk	Begränsad Boltzmann-maskin självorganiserande karta Aktiveringsfunktion Sigmoid softmax Radiell basfunktion Ryggförökningsmetod Djup lärning Flerskiktsperceptron Återkommande neurala nätverk långtidsminne Kontrollerat återkommande block Konvolutionellt neuralt nätverk U-nät Autokodare
Förstärkningsinlärning	Markov process Bellmans ekvation Girig algoritm Q-lärande SARSA Temporell skillnad (TD)
Teori	Vapnik-Chervonenkis teori Bias-Dispersion Dilemma Beräkningslärandeteori Empirisk riskminimering Occam lär sig PAC-inlärning Statistisk inlärningsteori
Tidskrifter och konferenser	NeurIPS ICML ML JMLR ArXiv:cs.LG