Czy są jakieś wersje T-SNE do przesyłania strumieniowego danych?

19

Rozumiem t-SNE i aproksymację Barnesa-Huta, że ​​wszystkie punkty danych są wymagane, aby wszystkie oddziaływania sił mogły być obliczone w tym samym czasie, a każdy punkt można dostosować na mapie 2d (lub niższych wymiarach).

Czy są jakieś wersje T-sne, które mogą skutecznie radzić sobie z przesyłaniem danych? Więc jeśli moje obserwacje docierają pojedynczo, znajdzie najlepszą lokalizację na mapie 2d, aby umieścić nową obserwację, lub ciągle aktualizuję wszystkie punkty na mapie 2d, aby uwzględnić nową obserwację.

Czy to w ogóle miałoby sens, czy też byłoby sprzeczne z konfiguracją t-sne.

Ger
źródło
Przybliżenie Barnesa-Huta sprawia, że ​​t-SNE jest wysoce skalowalny (przynajmniej możesz go użyć z 100 000 linii, próbowałem). Możesz to nazwać z R: cran.r-project.org/web/packages/Rtsne/index.html
RUser4512
Hej dzięki! Z przyjemnością głosuję na twoją odpowiedź, jeśli umieścisz ją w sekcji odpowiedzi tego.
Tom
3
Zobacz tutaj, aby zobaczyć wersję parametryczną zaimplementowaną w sieci neuronowej. lvdmaaten.github.io/publications/papers/AISTATS_2009.pdf
eyaler

Odpowiedzi:

15

Mam dokładnie to samo pytanie i zamieściłem je na wideo na YouTube z wykładu CS231n wygłoszonego przez Andreja Karpathy'ego kilka tygodni temu. Oto pytanie, które opublikowałem, a następnie odpowiedź Andreja:

https://www.youtube.com/watch?v=ta5fdaqDT3M&lc=z12ji3arguzwgxdm422gxnf54xaluzhcx

P:

Czy t-SNE potrzebuje całej partii obrazów (lub bardziej ogólnie danych) do stworzenia przestrzeni cech w małych wymiarach? Za pomocą PCA możesz utworzyć niskopoziomową przestrzeń funkcji na partii danych, a następnie rzutować nowe punkty danych na tę samą przestrzeń bez konieczności „ponownego szkolenia”. Czy to prawda dla t-SNE?

Pytam, ponieważ zauważyłem, że scikit-learn ma t-SNE jako część swojej różnorodnej klasy, ale ten moduł nie ma metody transform () jak PCA. Przynajmniej w skrócie wydaje się, że nie jest to możliwe.

Moje pytanie sprowadza się do tego. Jak zastosowałbyś t-SNE w sytuacji transmisji strumieniowej lub online, w której chcesz ciągle aktualizować wizualizację o nowe obrazy? Przypuszczalnie nie należy stosować algorytmu dla całej partii dla każdego nowego obrazu.

ZA:

+ Evan Zamir tak, jest to możliwe w przypadku t-SNE, ale może nie jest obsługiwany po wyjęciu z pudełka ze zwykłymi implementacjami t-SNE. Zwykle lokalizacja każdego punktu jest parametrem optymalizacji, ale równie dobrze możesz utworzyć mapowanie z wysokiej D -> niskiej D (np. Sieci neuronowej) i backprop przez lokalizacje. Następnie kończysz z funkcją osadzania i możesz rzutować nowe punkty. W zasadzie nic nie stoi na przeszkodzie, ale niektóre implementacje mogą go nie obsługiwać, ponieważ jest to rzadszy przypadek użycia.

thecity2
źródło
11

Podczas przesyłania danych strumieniowych może nie być konieczne / konieczne osadzenie wszystkich punktów w historii na jednej mapie t-SNE. Alternatywnie możesz wykonać osadzanie online, wykonując następujące proste kroki:

  1. wybierz przedział czasu trwania T, wystarczająco długi, aby każdy interesujący wzór pojawiał się co najmniej kilka razy w czasie trwania okna.

  2. przewijaj okno w miarę przesyłania danych, z krokiem czasowym dt znacznie mniejszym niż T. Dla każdej pozycji okna, oblicz osadzenie punktów danych w oknie czasowym przez t-SNE.

  3. zaszczepiaj każde osadzenie wynikiem poprzedniego. W t-SNE należy wybrać początkowe współrzędne punktów danych w przestrzeni niskiego wymiaru. W naszym przypadku, ponieważ wybraliśmy dt znacznie mniejszy niż T, dwa kolejne osadzenia współdzielą większość swoich punktów danych. Dla wszystkich współdzielonych punktów danych dopasuj ich początkowe współrzędne w bieżącym osadzeniu do ich ostatecznych współrzędnych w poprzednim osadzeniu . Ten krok zapewni spójną reprezentację podobnych wzorców w kolejnych osadzeniach. (w implementacji sklearn w pythonie parametr początkowy to „init”. Domyślnie implementacja sklearn określa losową pozycję punktów)

Uwaga 1: Ważne jest, aby interesujące wzorce pojawiały się co najmniej raz w dowolnym oknie czasowym, aby pamięć reprezentacji nie została utracona, gdy okno przesuwa się przez zestaw danych. Rzeczywiście, t-SNE zwykle nie jest zbieżny z unikalnym rozwiązaniem, ale tylko z lokalnym minimum, więc jeśli pamięć zostanie utracona, podobny wzorzec może być reprezentowany na bardzo różne sposoby w dwóch przypadkach osadzania.

Uwaga 2: Ta metoda jest szczególnie istotna w przypadku niestacjonarnych szeregów czasowych, w których chce się śledzić wzorce, które ewoluują powoli w czasie. Rzeczywiście, każde osadzanie jest tutaj specjalnie dostosowane do małego okna czasowego, w którym jest obliczane, zapewniając, że najlepiej przechwytuje lokalną strukturę czasową (w przeciwieństwie do pełnego osadzania całego niestacjonarnego zestawu danych).

Uwaga 3: W tej metodzie kolejne osadzanie nie może być zrównoleglone, ponieważ potrzeba wyniku poprzedniego osadzania, aby zaszczepić następne. Ponieważ jednak ziarno (tj. Początkowe współrzędne punktów) jest dobrze wybrane dla większości punktów (wszystkich wspólnych punktów między kolejnymi osadzeniami), osadzanie zazwyczaj zbiega się bardzo szybko, tylko w kilku iteracjach.

Przykład zastosowania tej metody do niestacjonarnych szeregów czasowych znajduje się w tym artykule ( ICLR 2016, Uczenie się stabilnych reprezentacji w zmieniającym się świecie za pomocą on-line t-SNE: dowód koncepcji w śpiewie ptaków ), gdzie została z powodzeniem zastosowana aby śledzić pojawianie się sylab w całym rozwoju ptaka śpiewającego.

Stéphane Deny
źródło
2
Witamy w społeczności. Self-plagiat jest nudna. Odnoszę się tutaj do twojego pierwszego postu . Jasne, możemy użyć tego samego uzasadnienia dla wielu odpowiedzi, potencjalnie skopiować lub wkleić frazę lub dwa lub po prostu bezpośrednio połączyć się z poprzednimi odpowiedziami. Mając to na uwadze, nie obniżaj swoich postów do pełnych kopii poprzednich odpowiedzi ze zmienionym pierwszym zdaniem. Obniża jakość treści CV i pokazuje słabą scholastyczną sportowość.
usεr11852 mówi Przywróć Monic
5
@ usεr11852 Problem został utworzony, ponieważ drugi wątek jest duplikatem tego. Dlatego zamknąłem drugą, połączyłem ją z tą i usunąłem zbędną odpowiedź. Ogólnie rzecz biorąc, Stéphane, za każdym razem, gdy masz ochotę opublikować dokładnie tę samą odpowiedź w dwóch wątkach, po prostu oznacz jeden z nich jako duplikat, abyśmy mogli je połączyć.
whuber
2
@ usεr11852 OK, przepraszam za duplikat odpowiedzi, jestem nowym współpracownikiem, więc nie znam jeszcze najlepszych praktyk.
Stéphane Deny
1
@whuber Dziękujemy za połączenie pytań i zgłoszenie się!
Stéphane Deny
1
Wygląda na to, że straciłeś 2 głosy poparcia. To niefortunne. +1 :) Witamy w CV.
ameba mówi Przywróć Monikę
7

Istnieje niedawno opublikowany wariant o nazwie A-tSNE, który obsługuje dynamiczne dodawanie nowych danych i udoskonalanie klastrów na podstawie obszarów zainteresowań lub na podstawie danych wprowadzonych przez użytkownika. Poniższy artykuł zawiera kilka całkiem dobrych przykładów:

Cytowanie: arXiv: 1512.01655

Przybliżone i sterowane przez użytkownika tSNE dla Progressive Visual Analytics Nicola Pezzotti, Boudewijn PF Lelieveldt, Laurens van der Maaten, Thomas Höllt, Elmar Eisemann, Anna Vilanova

Streszczenie:

Progresywna analiza wizualna ma na celu poprawę interaktywności istniejących technik analitycznych poprzez wizualizację, a także interakcję z wynikami pośrednimi. Jedną z kluczowych metod analizy danych jest redukcja wymiarowości, na przykład w celu tworzenia osadzeń 2D, które można wizualizować i skutecznie analizować. t-Distributed Stochastic Neighbor Embedding (tSNE) to dobrze dopasowana technika do wizualizacji kilku danych wielowymiarowych. tSNE może tworzyć znaczące wyniki pośrednie, ale cierpi na powolną inicjalizację, która ogranicza jego zastosowanie w Progressive Visual Analytics. Wprowadzamy kontrolowane przybliżenie tSNE (A-tSNE), które zamienia prędkość i dokładność, aby umożliwić interaktywną eksplorację danych. Oferujemy techniki wizualizacji w czasie rzeczywistym, w tym rozwiązanie oparte na gęstości i Magic Lens do sprawdzania stopnia przybliżenia. Dzięki tej informacji zwrotnej użytkownik może decydować o lokalnych udoskonaleniach i sterować poziomem przybliżenia podczas analizy. Pokazujemy naszą technikę za pomocą kilku zestawów danych, w scenariuszu badawczym w świecie rzeczywistym oraz do analizy strumieni wielowymiarowych w czasie rzeczywistym, aby zilustrować ich skuteczność w interaktywnej analizie danych.

cvlad
źródło
Witamy na stronie. Staramy się zbudować stałe repozytorium wysokiej jakości informacji statystycznych w formie pytań i odpowiedzi. Dlatego też obawiamy się odpowiedzi typu „tylko link” z powodu linkrot. Czy możesz zamieścić pełny cytat i streszczenie informacji pod linkiem, na wypadek gdyby nie działał?
gung - Przywróć Monikę
6

Przybliżenie Barnesa-Huta sprawia, że ​​t-SNE jest wysoce skalowalny (przynajmniej możesz go użyć z 100 000 linii, próbowałem). Możesz to nazwać z R: Rtsne

O(nlog(n))O(n2))

RUser4512
źródło
1
Użyłem go z gęstymi liniami 1K o gęstości 250 000 - było całkiem niezłe, ale jest ograniczone pamięcią.
Vladimir Chupakhin
2

Przybliżenie Barnesa-Huta jest teraz domyślną metodą w scikit-learn od wersji 0.17.0:

Domyślnie algorytm obliczania gradientu używa aproksymacji Barnesa-Huta działającej w czasie O (NlogN). method = 'exact' będzie działał na wolniejszym, ale dokładnym algorytmie w czasie O (N ^ 2). Dokładny algorytm należy zastosować, gdy błędy najbliższego sąsiada muszą być lepsze niż 3%. Jednak dokładna metoda nie może być skalowana do milionów przykładów. Nowości w wersji 0.17: Przybliżona metoda optymalizacji za pomocą Barnes-Hut.

thecity2
źródło
To nie dotyczy pytania. BH, chociaż szybszy, nie obsługuje przesyłania strumieniowego. Może miałeś na myśli komentarz do tej odpowiedzi .
merv