Incrustación de veïns estocàstics distribuïts en t (t-SNE)

Archiu:T-SNEvisualisation of word embeddings generated using 19th century literature.png

Visualisació T-SNE de incrustaciones de paraules (word embedding) generades a partir de lliteratura del sigle XIX

La incrustación de veïns estocàstics distribuïts en t (t-SNE) és un método estadístic per a visualisar senyes d'alta dimensió assignant a cada punt de senyes una ubicació en un mapa bidimensional o tridimensional. Es basa en l'incrustación de veïns estocàstica desenrollada originalment per Geoffrey Hinton i Sam Roweis, a on Laurens van der Maaten va propondre la variant t-distribuïda. Es tracta d'una tècnica no llineal de reducció de la dimensionalidad per a incrustar senyes d'alta dimensió per a la seua visualisació en un espai de baixa dimensió de dos o tres dimensions. Concretament, modela cada objecte d'alta dimensió per mig d'un punt bidimensional o tridimensional, de tal forma que els objectes similars es modelen per mig de punts propencs i els objectes disímiles es modelen per mig de punts distants en alta provabilitat.

Archiu:T-SNEEmbedding of MNIST.png

Incrustaciones T-SNE del conjunt de senyes MNIST

l'algoritme t-SNE consta de dos etapes principals. En primer lloc, t-SNE construïx una distribució de provabilitat sobre parells d'objectes d'alta dimensió de tal forma que als objectes similars se'ls assigna una provabilitat major, mentres que als punts disímiles se'ls assigna una provabilitat menor. En segon lloc, t-SNE definix una distribució de provabilitat similar sobre els punts del mapa de baixa dimensió i minimisa la divergència de Kullback-Leibler (divergència KL) entre les dos distribucions sobre les ubicacions dels punts en el mapa. Encara que l'algoritme original utilisa la distància euclidiana entre objectes com a base de la seua mètrica de similitut, esta pot modificar-se segons convinga. Una variant riemanniana és UMAP.

La t-SNE s'ha utilisat per a la visualisació en una àmplia gama d'aplicacions, com la genómica, l'investigació en seguritat informàtica, el processament del llenguage natural, l'anàlisis musical, l'investigació del càncer, la bioinformática, l'interpretació de dominis geològics, i el processament de senyals biomèdiques.

Encara que els gràfics t-SNE a sovint semblen mostrar clusters, els clústers o conglomerats visuals poden estar fortament influenciats per la parametrización elegida i, per lo tant, és necessari un bon coneiximent dels paràmetros per a t-SNE. Es pot demostrar que estos "conglomerats" apareixen inclús en senyes no agrupades, per lo que poden ser falses troballes. Per tant, pot ser necessària una exploració interactiva per a elegir els paràmetros i validar els resultats. S'ha demostrat que t-SNE a sovint és capaç de recuperar conglomerats ben separats i, en eleccions especials dels paràmetros, s'aproxima a una forma simple d'agrupació espectral.

Per a un conjunt de senyes en n elements, t-SNE s'eixecuta en temps O(n²) i requerix espai O(n²).

Detalls

Donat un conjunt de $N$ objectes d'alta dimensió ${𝐱}_1,\dots ,{𝐱}_N$, t-SNE calcula primer les provabilitats $p_{ij}$ que són proporcionals a la similitut dels objectes ${𝐱}_i$ i ${𝐱}_j$ com seguix:

Per a $i\ne j$ es definix:

$p_{j\mid i}=\frac{\exp (-\Vert {𝐱}_i-{𝐱}_j{\Vert }^2/2{\sigma }_i^2)}{\sum _{k\ne i}\exp (-\Vert {𝐱}_i-{𝐱}_k{\Vert }^2/2{\sigma }_i^2)}$

I s'establix $p_{i\mid i}=0$. Observe's que el denominador anterior garantisa $\sum _j{p}_{j\mid i}=1$ per a totes les $i$.

Com varen explicar van der Maaten i Hinton: "La similitut dels punts de senyes $x_j$ als punts de senyes $x_i$ és la provabilitat condicional $p_{j|i}$ de que $x_i$ trie a $x_j$ com el seu veí si els veïns s'elegiren en proporció a la seua densitat de provabilitat baix una gaussiana centrada en $x_i$.

Després es definix:

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

Açò és motivat degut a que $p_i$ i $p_j$ de les N mostres s'estimen com 1/N, per lo que la provabilitat condicional pot escriure's com $p_{i\mid j}=N{p}_{ij}$ i $p_{j\mid i}=N{p}_{ji}$. Tenint en conte que $p_{ij}=p_{ji}$ es pot obtindre la fòrmula anterior.

També es deu tindre en conte que $p_{ii}=0$ i $\sum _{i,j}{p}_{ij}=1$.

L'ample de banda dels núcleus gaussianos ${\sigma }_i$ es fixa de manera que l'entropía de la distribució condicional siga igual a una entropía predefinida per mig del método de bisecció. Com a resultat, l'ample de banda s'adapta a la densitat de les senyes: els valors més menuts de ${\sigma }_i$ s'utilisen en les parts més denses de l'espai de senyes.

Ya que el kernel gaussiano utilisa la distància euclidiana $\Vert x_i-x_j\Vert$, es veu afectada per la maldicció de la dimensionalidad, i en senyes d'alta dimensionalidad quan les distàncies perden la capacitat de discriminar, llavors $p_{ij}$ es tornen massa similars (asintóticament, convergirien a una constant). Per a paliar-ho, s'ha propost ajustar les distàncies en una transformada de potència, basada en la dimensió intrínseca de cada punt.

t-SNE pretén deprendre un mapa dimensional $d$, que és ${𝐲}_1,\dots ,{𝐲}_N$ (en ${𝐲}_i\in {ℝ}^d$ i $d$ normalment elegit com 2 o 3) que reflectixca les similituts $p_{ij}$ lo millor possible. Per a això, medix les similituts $q_{ij}$ entre dos punts del mapa ${𝐲}_i$ i ${𝐲}_j$ utilisant un enfocament molt similar. Específicament, per a $i\ne j$, $q_{ij}$ es definix com:

$q_{ij}=\frac{(1+\Vert {𝐲}_i-{𝐲}_j{\Vert }^2{)}^{-1}}{\sum _k\sum _{l\ne k}(1+\Vert {𝐲}_k-{𝐲}_l{\Vert }^2{)}^{-1}}$

I s'establix $q_{ii}=0$. En este cas s'utilisa una distribució t de Student de coes grosses (en un grau de llibertat, que és lo mateix que una distribució de Cauchy) per a medir les similituts entre punts de baixa dimensió, en la finalitat de permetre que els objectes disímiles es modelen molt separats en el mapa.

L'ubicació del punt ${𝐲}_i$ en el mapa es determina minimisant la divergència (no simètrica) de Kullback-Leibler de la distribució $P$ de la distribució $Q$, és dir:

$\mathrm{K}\mathrm{L}(P\parallel Q)=\sum _{i\ne j}{p}_{ij}\log \frac{p_{ij}}{q_{ij}}$

La minimisació de la divergència de Kullback-Leibler sobre el punt ${𝐲}_i$ es realisa per mig del descens de gradient. El resultat d'esta optimisació és un mapa que reflectix les similituts entre les entrades d'alta dimensió.

Software

• El paquet R Rtsne implementa t-SNE en R.
• ELKI conté tSNE, també en aproximació Barnes-Hut
• scikit-learn, una popular biblioteca d'aprenentage automàtic en Python, implementa t-SNE tant en solucions exactes com en l'aproximació de Barnes-Hut.
• Tensorboard, el kit de visualisació associat a TensorFlow, també implementa t-SNE