# Incrustació de veïns estocàstics distribuïts en t

La incrustació de veïns estocàstics distribuïts en t (t-SNE) és un mètode estadístic per visualitzar dades d'alta dimensió donant a cada punt de dades una ubicació en un mapa bidimensional o tridimensional. Es basa en Stochastic Neighbor Embedding desenvolupat originalment per Geoffrey Hinton i Sam Roweis, on Laurens van der Maaten i Hinton van proposar la variant distribuïda t. És una tècnica de reducció de dimensionalitat no lineal per incrustar dades d'alta dimensió per a la visualització en un espai de dimensions baixes de dues o tres dimensions. Concretament, modela cada objecte d'alta dimensió per un punt de dues o tres dimensions de manera que objectes similars siguin modelats per punts propers i objectes diferents siguin modelats per punts distants amb alta probabilitat.
L'algorisme t-SNE consta de dues etapes principals. En primer lloc, t-SNE construeix una distribució de probabilitat sobre parells d'objectes d'alta dimensió de tal manera que als objectes similars se'ls assigna una probabilitat més alta mentre que als punts diferents se'ls assigna una probabilitat més baixa. En segon lloc, t-SNE defineix una distribució de probabilitat similar sobre els punts del mapa de dimensions baixes i minimitza la divergència Kullback-Leibler (divergència KL) entre les dues distribucions pel que fa a les ubicacions dels punts al mapa. Tot i que l'algorisme original utilitza la distància euclidiana entre objectes com a base de la seva mètrica de similitud, aquesta es pot canviar segons correspongui. Una variant riemanniana és UMAP.
t-SNE s'ha utilitzat per a la visualització en una àmplia gamma d'aplicacions, com ara genòmica, investigació de seguretat informàtica, processament del llenguatge natural, anàlisi de música, investigació del càncer, bioinformàtica, interpretació del domini geològic, i processament de senyals biomèdics.
Per a un conjunt de dades amb n elements, t-SNE s'executa en temps O(n$^2$) i requereix espai O(n$^2$).

## Detalls

Donat un conjunt de $N$ objectes d'alta dimensió $\mathbf {x} _{1},\dots ,\mathbf {x} _{N}$, t-SNE primer calcula probabilitats $p_{ij}$ que són proporcionals a la semblança dels objectes $\mathbf {x} _{i}$ i $\mathbf {x} _{j}$, de la següent manera.
$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})}}$
i posat $p_{i\mid i}=0$. Tingueu en compte que el denominador anterior assegura $\sum _{j}p_{j\mid i}=1$ per a tot $i$.
Com van explicar van der Maaten i Hinton: "La similitud del punt de dades $x_{j}$ al punt de dades $x_{i}$ és la probabilitat condicional, $p_{j|i}$, això $x_{i}$ escolliria $x_{j}$ com el seu veí si els veïns fossin escollits en proporció a la seva densitat de probabilitat sota un gaussià centrat en $x_{i}$."
$p_{ij}={\frac {p_{j\mid i}+p_{i\mid j}}{2N}}$
Això està motivat perquè $p_{i}$ i $p_{j}$ de les N mostres s'estimen com 1/N, de manera que la probabilitat condicional es pot escriure com $p_{i\mid j}=Np_{ij}$ i $p_{j\mid i}=Np_{ji}$. Des de $p_{ij}=p_{ji}$, podeu obtenir la fórmula anterior.
També tingueu en compte que $p_{ii}=0$ i $\sum _{i,j}p_{ij}=1$.
L'ample de banda dels nuclis gaussians $\sigma _{i}$ s'estableix de tal manera que l'entropia de la distribució condicional sigui igual a una entropia predefinida utilitzant el mètode de la bisecció. Com a resultat, l'ample de banda s'adapta a la densitat de les dades: valors més petits de $\sigma _{i}$ s'utilitzen en parts més denses de l'espai de dades. L'entropia augmenta amb la perplexitat d'aquesta distribució $P_{i}$ ; aquesta relació es veu com
$Perp(P_{i})=2^{H(P_{i})}$
on $H(P_{i})$ és l'entropia de Shannon $H(P_{i})=-\sum _{j}p_{j|i}\log _{2}p_{j|i}.$
La perplexitat és un paràmetre escollit a mà del t-SNE i, com afirmen els autors, "la perplexitat es pot interpretar com una mesura suau del nombre efectiu de veïns. El rendiment de l'SNE és bastant robust als canvis en la perplexitat, i els valors típics estan entre 5 i 50".
Com que el nucli gaussià utilitza la distància euclidiana $\lVert x_{i}-x_{j}\rVert$, es veu afectat per la maledicció de la dimensionalitat, i en dades d'alta dimensió quan les distàncies perden la capacitat de discriminar, el $p_{ij}$ es tornen massa semblants (asimptòticament, convergirien a una constant). S'ha proposat ajustar les distàncies amb una transformada de potència, en funció de la dimensió intrínseca de cada punt, per pal·liar-ho.
t-SNE pretén aprendre a $d$ -Mapa dimensional $\mathbf {y} _{1},\dots ,\mathbf {y} _{N}$ (amb $\mathbf {y} _{i}\in \mathbb {R} ^{d}$ i $d$ normalment es tria com a 2 o 3) que reflecteix les similituds $p_{ij}$ tant com sigui possible. Amb aquesta finalitat, mesura les similituds $q_{ij}$ entre dos punts del mapa $\mathbf {y} _{i}$ i $\mathbf {y} _{j}$, utilitzant un enfocament molt similar. Concretament, per $i\neq j$, definir $q_{ij}$ com
$q_{ij}={\frac {(1+\lVert \mathbf {y} _{i}-\mathbf {y} _{j}\rVert ^{2})^{-1}}{\sum _{k}\sum _{l\neq k}(1+\lVert \mathbf {y} _{k}-\mathbf {y} _{l}\rVert ^{2})^{-1}}}$
i posat $q_{ii}=0$. Aquí s'utilitza una distribució t de Student de cua pesada (amb un grau de llibertat, que és la mateixa que una distribució de Cauchy) per mesurar les similituds entre punts de dimensions baixes per tal de permetre que objectes diferents siguin modelats molt entre ells al mapa.
Les ubicacions dels punts $\mathbf {y} _{i}$ al mapa es determinen minimitzant la divergència (no simètrica) de Kullback-Leibler de la distribució $P$ de la distribució $Q$, és a dir:
$\mathrm {KL} \left(P\parallel Q\right)=\sum _{i\neq j}p_{ij}\log {\frac {p_{ij}}{q_{ij}}}$
La minimització de la divergència Kullback-Leibler respecte als punts $\mathbf {y} _{i}$ es realitza mitjançant el descens de gradients. El resultat d'aquesta optimització és un mapa que reflecteix les similituds entre les entrades d'alta dimensió.

## Sortida

Tot i que els diagrames t-SNE sovint semblen mostrar clústers, els clústers visuals es poden veure fortament influenciats per la parametrització escollida (especialment la perplexitat) i, per tant, cal una bona comprensió dels paràmetres per a t-SNE. Es pot demostrar que aquests "clusters" fins i tot apareixen en dades estructurades sense agrupacions clares, i per tant poden ser troballes falses. De la mateixa manera, la mida dels clústers produïts per t-SNE no és informativa, ni tampoc la distància entre clústers. Per tant, pot ser necessària una exploració interactiva per triar paràmetres i validar els resultats. S'ha demostrat que t-SNE sovint pot recuperar cúmuls ben separats i, amb opcions de paràmetres especials, s'aproxima a una forma simple d'agrupament espectral.

## Referències

* ↑ van der Maaten, L.J.P.; Hinton, G.E. Journal of Machine Learning Research, 9, 11-2008, pàg. 2579–2605.
* ↑ Gashi, I.; Stankovic, V.; Leita, C.; Thonnard, O. Proceedings of the IEEE International Symposium on Network Computing and Applications, 2009, pàg. 4–11.
* ↑ Hamel, P.; Eck, D. Proceedings of the International Society for Music Information Retrieval Conference, 2010, pàg. 339–344.
* ↑ Jamieson, A.R.; Giger, M.L.; Drukker, K.; Lui, H.; Yuan, Y. Medical Physics, 37, 1, 2010, pàg. 339–351. DOI: 10.1118/1.3267037. PMC: 2807447. PMID: 20175497.
* ↑ Wallach, I.; Liliean, R. Bioinformatics, 25, 5, 2009, pàg. 615–620. DOI: 10.1093/bioinformatics/btp035. PMID: 19153135 [Consulta: free].
* ↑ Balamurali, Mehala; Silversides, Katherine L.; Melkumyan, Arman (en anglès) Computers & Geosciences, 125, 01-04-2019, pàg. 78–89. Bibcode: 2019CG....125...78B. DOI: 10.1016/j.cageo.2019.01.011. ISSN: 0098-3004.
* ↑ Balamurali, Mehala. «t-SNE Based Visualisation and Clustering of Geological Domain». A: Hirose. Neural Information Processing (en anglès). 9950. Cham: Springer International Publishing, 2016, p. 565–572 (Lecture Notes in Computer Science). DOI 10.1007/978-3-319-46681-1_67. ISBN 978-3-319-46681-1.
* ↑ Leung, Raymond; Balamurali, Mehala; Melkumyan, Arman (en anglès) Mathematical Geosciences, 53, 1, 01-01-2021, pàg. 105–130. Bibcode: 2021MatGe..53..105L. DOI: 10.1007/s11004-019-09839-z. ISSN: 1874-8953.
* ↑ Birjandtalab, J. «Nonlinear dimension reduction for EEG-based epileptic seizure detection». A: 2016 IEEE-EMBS International Conference on Biomedical and Health Informatics (BHI) (en anglès), 2016-02-01, p. 595–598. DOI 10.1109/BHI.2016.7455968. ISBN 978-1-5090-2455-1.
* ↑ van der Maaten, L.J.P.; Hinton, G.E. Journal of Machine Learning Research, 9, 11-2008, pàg. 2579–2605.
* ↑ «K-means clustering on the output of t-SNE» (en anglès). Cross Validated. [Consulta: 16 abril 2018].
* ↑ Wattenberg, Martin; Viégas, Fernanda; Johnson, Ian (en anglès) Distill, 1, 10, 13-10-2016, pàg. e2. DOI: 10.23915/distill.00002. ISSN: 2476-0757 [Consulta: free].
* ↑ Pezzotti, Nicola; Lelieveldt, Boudewijn P. F.; Maaten, Laurens van der; Hollt, Thomas; Eisemann, Elmar (en anglès) IEEE Transactions on Visualization and Computer Graphics, 23, 7, 01-07-2017, pàg. 1739–1752. arXiv: 1512.01655. DOI: 10.1109/tvcg.2016.2570755. ISSN: 1077-2626. PMID: 28113434.
* ↑ Wattenberg, Martin; Viégas, Fernanda; Johnson, Ian (en anglès) Distill, 1, 10, 13-10-2016. DOI: 10.23915/distill.00002 [Consulta: 4 desembre 2017].