t-rozproszone stochastyczne osadzanie sąsiadów - t-distributed stochastic neighbor embedding

t-distributed stochastic sąsiad embedding ( t-SNE ) to statystyczna metoda wizualizacji danych wielowymiarowych poprzez nadanie każdemu punktowi danych lokalizacji na dwu- lub trójwymiarowej mapie. Opiera się na Stochastic Neighbor Embedding pierwotnie opracowanym przez Sama Roweisa i Geoffreya Hintona , gdzie Laurens van der Maaten zaproponował wariant t- distributed . Jest to technika nieliniowej redukcji wymiarowości , która dobrze nadaje się do osadzania danych wielowymiarowych w celu wizualizacji w niskowymiarowej przestrzeni dwu- lub trójwymiarowej. W szczególności modeluje każdy obiekt wysokowymiarowy za pomocą punktu dwu- lub trójwymiarowego w taki sposób, że podobne obiekty są modelowane przez pobliskie punkty, a różne obiekty są modelowane przez odległe punkty z dużym prawdopodobieństwem.

Algorytm t-SNE składa się z dwóch głównych etapów. Po pierwsze, t-SNE konstruuje rozkład prawdopodobieństwa dla par obiektów wielowymiarowych w taki sposób, że podobnym obiektom przypisuje się większe prawdopodobieństwo, podczas gdy niepodobnym punktom przypisuje się mniejsze prawdopodobieństwo. Po drugie, t-SNE definiuje podobny rozkład prawdopodobieństwa względem punktów na mapie niskowymiarowej i minimalizuje rozbieżność Kullbacka–Leiblera (dywergencję KL) między tymi dwoma rozkładami ze względu na położenie punktów na mapie. Chociaż oryginalny algorytm wykorzystuje odległość euklidesową między obiektami jako podstawę metryki podobieństwa, można to zmienić w razie potrzeby.

t-SNE został wykorzystany do wizualizacji w szerokim zakresie zastosowań, w tym genomiki , badań bezpieczeństwa komputerowego , przetwarzania języka naturalnego, analizy muzyki , badań nad rakiem , bioinformatyki , interpretacji domen geologicznych i przetwarzania sygnałów biomedycznych.

Chociaż wykresy t-SNE często wydają się przedstawiać klastry , na wizualne klastry może mieć duży wpływ wybrana parametryzacja i dlatego konieczne jest dobre zrozumienie parametrów dla t-SNE. Można wykazać, że takie „zgrupowania” pojawiają się nawet w danych niezwiązanych z klastrami, a zatem mogą być fałszywymi ustaleniami. Interaktywna eksploracja może być zatem konieczna do wyboru parametrów i walidacji wyników. Wykazano, że t-SNE jest często w stanie odtworzyć dobrze odseparowane klastery, a przy doborze specjalnych parametrów aproksymuje prostą formę klastrowania widmowego .

Detale

Mając zestaw obiektów wielowymiarowych , t-SNE najpierw oblicza prawdopodobieństwa, które są proporcjonalne do podobieństwa obiektów i , w następujący sposób. ${\ Displaystyle N}$${\ Displaystyle \ mathbf {x} _ {1} \ kropki \ mathbf {x} _ {N}}$${\displaystyle p_{ij}}$${\ Displaystyle \ mathbf {x} _ {i}}$${\ Displaystyle \ mathbf {x} _ {j}}$

Dla , zdefiniuj ${\displaystyle i\neqj}$

${\ Displaystyle p_ {j \ mid ja} = {\ 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 ustaw . Zauważ, że dla wszystkich . ${\ Displaystyle p_ {i \ średni ja} = 0}$${\ Displaystyle \ suma _ {j} p_ {j \ średni i} = 1}$${\displaystyle i}$

Jak Van der Maaten i Hinton wyjaśnił: „Podobieństwo Datapoint do Datapoint jest prawdopodobieństwo warunkowe , które byłoby wybrać jako swojego sąsiada, jeśli sąsiedzi zebrano w proporcji do ich gęstości prawdopodobieństwa Gaussa pod skupione w .” ${\displaystyle x_{j}}$${\displaystyle x_{i}}$${\displaystyle p_{j|i}}$${\displaystyle x_{i}}$${\displaystyle x_{j}}$${\displaystyle x_{i}}$

Teraz zdefiniuj

${\ Displaystyle p_ {ij} = {\ Frac {p_ {j \ średni ja} + p_ {i \ średni j}} {2 N}}}$

i pamiętać, że , i . ${\displaystyle p_{ij}=p_{ji}}$${\ Displaystyle p_ {ii} = 0}$${\ Displaystyle \ suma _ {i, j} p_ {ij} = 1}$

Szerokość pasma jąder Gaussa jest ustawiona w taki sposób, że zakłopotanie rozkładu warunkowego jest równe z góry określonemu zakłopotaniu przy użyciu metody bisekcji . W rezultacie przepustowość jest dostosowywana do gęstości danych: mniejsze wartości są wykorzystywane w gęstszych częściach przestrzeni danych. ${\ Displaystyle \ sigma _ {i}}$${\ Displaystyle \ sigma _ {i}}$

Ponieważ jądro Gaussa korzysta z odległości euklidesowej , jest dotknięte przekleństwem wymiarowości , a w przypadku danych wielowymiarowych, gdy odległości tracą zdolność rozróżniania, stają się zbyt podobne (asymptotycznie zbiegają się do stałej). Zaproponowano dostosowanie odległości za pomocą transformacji mocy, w oparciu o wewnętrzny wymiar każdego punktu, aby to złagodzić. ${\ Displaystyle \ lVert x_ {i} -x_ {j} \ r Vert}$${\displaystyle p_{ij}}$

t-SNE ma na celu nauczenie się dwuwymiarowej mapy (z ), która jak najlepiej odzwierciedla podobieństwa . W tym celu mierzy podobieństwa między dwoma punktami na mapie i , stosując bardzo podobne podejście. W szczególności dla , zdefiniuj jako ${\displaystyle d}$${\ Displaystyle \ mathbf {y} _ {1}, \ kropki, \ mathbf {y} _ {N}}$${\ Displaystyle \ mathbf {y} _ {i} \ w \ mathbb {R} ^ {d}}$${\displaystyle p_{ij}}$${\displaystyle q_{ij}}$${\ Displaystyle \ mathbf {y} _ {i}}$${\ Displaystyle \ mathbf {y} _ {j}}$${\displaystyle i\neqj}$${\displaystyle q_{ij}}$

${\ Displaystyle q_ {ij} = {\ Frac {(1 + \ l Vert \ mathbf {y} _ {i} - \ mathbf {y} _ {j} \ r Vert ^ {2}) ^ {-1}} \sum _{k}\sum _{l\neq k}(1+\lVert \mathbf {y} _{k}-\mathbf {y} _{l}\rVert ^{2})^{-1 }}}}$

i ustaw . W tym przypadku rozkład t-Studenta z grubym ogonem (z jednym stopniem swobody, który jest taki sam jak rozkład Cauchy'ego ) jest używany do pomiaru podobieństw między punktami niskowymiarowymi, aby umożliwić modelowanie odmiennych obiektów daleko od siebie na mapie . ${\displaystyle q_{ii}=0}$

Lokalizację punktów na mapie wyznacza się minimalizując (niesymetryczną) rozbieżność rozkładu Kullbacka–Leiblera z rozkładem , czyli: ${\ Displaystyle \ mathbf {y} _ {i}}$${\displaystyle P}$${\displaystyle Q}$

${\ Displaystyle \ operatorname {KL} \ lewo (P \ równoległy Q \ po prawej) = \ suma _ {i \ neq j} p_ {ij} \ log {\ Frac {p_ {ij}} {q_ {ij}}} }$

Minimalizacja rozbieżności Kullbacka-Leiblera w odniesieniu do punktów jest wykonywana za pomocą opadania gradientu . Wynikiem tej optymalizacji jest mapa, która odzwierciedla podobieństwa między wejściami wielowymiarowymi. ${\ Displaystyle \ mathbf {y} _ {i}}$

Oprogramowanie

• Pakiet R Rtsne implementuje t-SNE w R .
• ELKI zawiera tSNE, również z przybliżeniem Barnesa-Huta
• Scikit-learn , popularny zestaw narzędzi do uczenia maszynowego w Pythonie implementuje t-SNE zarówno z dokładnymi rozwiązaniami, jak i przybliżeniem Barnesa-Huta.
• Tensorboard, zestaw wizualizacji powiązany z TensorFlow , również implementuje t-SNE ( wersja online )

Bibliografia

Zewnętrzne linki

• Wizualizacja danych za pomocą t-SNE , Google Tech Talk o t-SNE
• Implementacje t-SNE w różnych językach , Kolekcja linków utrzymywana przez Laurensa van der Maatena