Czy redukcję wymiarów podczas wizualizacji należy uznać za „zamknięty” problem rozwiązany przez t-SNE?

23

Dużo czytałem o algorytmie sne do redukcji wymiarów. Jestem pod wielkim wrażeniem wydajności „klasycznych” zestawów danych, takich jak MNIST, w których osiąga wyraźne rozdzielenie cyfr ( patrz oryginalny artykuł ):t

t-SNE MNIST

Użyłem go również do wizualizacji funkcji poznanych przez sieć neuronową, którą trenuję i byłem bardzo zadowolony z wyników.

Tak więc, jak rozumiem:

t sne ma dobre wyniki w większości zestawów danych i ma dość wydajną implementację - z metodą aproksymacji Barnesa-Huta. Czy zatem moglibyśmy powiedzieć, że problem „redukcji wymiarowości”, przynajmniej w celu stworzenia dobrych wizualizacji 2D / 3D, jest teraz problemem „zamkniętym”?O(nlogn)

Wiem, że to dość odważne stwierdzenie. Interesuje mnie zrozumienie, jakie są potencjalne „pułapki” tej metody. Czy są jakieś przypadki, w których wiemy, że nie jest to przydatne? Co więcej, jakie są „otwarte” problemy w tej dziedzinie?

galoosh33
źródło

Odpowiedzi:

16

Absolutnie nie.

Zgadzam się, że t-SNE jest niesamowitym algorytmem, który działa wyjątkowo dobrze i był to prawdziwy przełom w tym czasie. Jednak:

  • ma poważne wady;
  • niektóre niedociągnięcia muszą być możliwe do rozwiązania;
  • istnieją już algorytmy, które w niektórych przypadkach działają wyraźnie lepiej;
  • wiele właściwości t-SNE jest nadal słabo poznanych.

Ktoś powiązał z tym bardzo popularnym opisem niektórych niedociągnięć t-SNE: https://distill.pub/2016/misread-tsne/ (+1), ale omawia tylko bardzo proste zestawy danych zabawek i uważam, że nie odpowiada bardzo dobrze w stosunku do problemów, które napotyka się w praktyce podczas pracy z t-SNE i powiązanymi algorytmami na rzeczywistych danych. Na przykład:

  1. t-SNE często nie zachowuje globalnej struktury zbioru danych;
  2. t-SNE cierpi z powodu „przeludnienia”, gdy rośnie powyżej ~ 100 000;N.
  3. Barnes-Hut Runtime jest zbyt powolne dla dużych .N.

Omówię krótko wszystkie trzy poniżej.


  1. t-SNE często nie zachowuje globalnej struktury zbioru danych.

    Rozważmy ten zestaw danych o pojedynczej komórce z sekwencją RNA z instytutu Allena (mysie komórki korowe): http://celltypes.brain-map.org/rnaseq/mouse . Ma ~ 23 tys. Komórek. Wiemy z góry, że ten zestaw danych ma wiele znaczących struktur hierarchicznych, co potwierdza hierarchiczne grupowanie. Istnieją neurony i komórki nieneuronowe (glej, astrocyty itp.). Wśród neuronów znajdują się neurony pobudzające i hamujące - dwie bardzo różne grupy. Wśród np. Neuronów hamujących istnieje kilka głównych grup: wyrażających Pvalb, wyrażających SSt, wyrażających VIP. W każdej z tych grup wydaje się, że istnieje wiele innych klastrów. Znajduje to odzwierciedlenie w hierarchicznym drzewie klastrów. Ale oto t-SNE, zaczerpnięte z powyższego linku:

    wprowadź opis zdjęcia tutaj

    Komórki nieneuronowe są w kolorze szarym / brązowym / czarnym. Neurony pobudzające są w kolorze niebieskim / turkusowym / zielonym. Neurony hamujące są w kolorze pomarańczowym / czerwonym / fioletowym. Chcielibyśmy, aby te główne grupy trzymały się razem, ale tak się nie dzieje: gdy t-SNE podzieli grupę na kilka klastrów, mogą ostatecznie zostać ustawione dowolnie. Struktura hierarchiczna zestawu danych została utracona.

    Myślę, że powinien to być problem do rozwiązania, ale nie jestem świadomy żadnych dobrych zasadniczych zmian, pomimo niedawnych prac w tym kierunku (w tym moich własnych).

  2. t-SNE cierpi z powodu „przeludnienia”, gdy rośnie powyżej ~ 100 000N.

    t-SNE działa bardzo dobrze na danych MNIST. Ale rozważ to (zaczerpnięte z tego artykułu ):

    wprowadź opis zdjęcia tutaj

    Z 1 milionem punktów danych wszystkie klastry są skupione razem (dokładny powód tego nie jest bardzo jasny), a jedynym znanym sposobem na zrównoważenie jest kilka brudnych hacków, jak pokazano powyżej. Wiem z doświadczenia, że ​​dzieje się tak również z innymi podobnie dużymi zbiorami danych.

    Można to dostrzec z samym MNIST (N = 70k). Spójrz:

    wprowadź opis zdjęcia tutaj

    Po prawej stronie znajduje się t-SNE. Po lewej stronie znajduje się UMAP , nowa ekscytująca metoda w trakcie aktywnego rozwoju, która jest bardzo podobna do starszej largeVis . UMAP / largeVis przyciąga klastry znacznie dalej. Dokładny powód tego jest niejasny; Powiedziałbym, że jest tu jeszcze wiele do zrozumienia i być może wiele do poprawienia.

  3. Czas działania Barnes-Hut jest zbyt wolny dla dużychN.

    Waniliowy t-SNE jest bezużyteczny dla powyżej ~ 10k. Do niedawna standardowym rozwiązaniem był Barnes-Hut t-SNE, jednak dla bliżej ~ 1 ml staje się boleśnie powolny. Jest to jeden z głównych punktów sprzedaży UMAP, ale tak naprawdę niedawny artykuł sugerował przyspieszenie FFT t-SNE (FIt-SNE), który działa znacznie szybciej niż Barnes-Hut t-SNE i jest co najmniej tak szybki jak UMAP. Odtąd polecam wszystkim korzystanie z tej implementacji .N.N.

    wprowadź opis zdjęcia tutaj

    Może to nie jest już do końca otwarty problem, ale do niedawna tak było i myślę, że jest miejsce na dalsze usprawnienia w czasie wykonywania. Dlatego prace z pewnością mogą być kontynuowane w tym kierunku.

ameba mówi Przywróć Monikę
źródło
7

Oto doskonała analiza tego, jak zmienianie parametrów podczas uruchamiania t-SNE wpływa na niektóre bardzo proste zestawy danych: http://distill.pub/2016/misread-tsne/ . Ogólnie rzecz biorąc, t-SNE wydaje się dobrze radzić sobie z rozpoznawaniem struktur wielowymiarowych (w tym relacji bardziej złożonych niż klastry), choć podlega to dostrajaniu parametrów, zwłaszcza wartościom zakłopotania.

Liangjy
źródło
7

Nadal chciałbym usłyszeć inne komentarze, ale na razie opublikuję własną odpowiedź. Podczas gdy szukałem bardziej „praktycznej” odpowiedzi, są dwie teoretyczne „wady” do t-sne, o których warto wspomnieć; pierwszy jest mniej problematyczny, a drugi zdecydowanie należy wziąć pod uwagę:

  1. Funkcja kosztu t-sne nie jest wypukła, więc nie gwarantujemy osiągnięcia globalnego optimum : inne techniki redukcji wymiarów (Isomap, LLE) mają funkcję wypukłego kosztu. W przypadku t-sne tak nie jest, dlatego istnieją pewne parametry optymalizacyjne, które należy skutecznie dostroić, aby uzyskać „dobre” rozwiązanie. Jednakże, choć potencjalnie teoretyczny pułapek, warto wspomnieć, że w praktyce nie jest to upadek, ponieważ wydaje się, że nawet „lokalne minimum” algorytmu t-sne przewyższa (tworzy lepsze wizualizacje) niż globalne minimum innych metod .

  2. przekleństwo międzyinstytucjonalnej wymiarowości : Jedną z ważnych rzeczy, o których należy pamiętać podczas używania t-sne jest to, że jest to zasadniczo różnorodna naukaalgorytm. Zasadniczo oznacza to, że t-sne (i inne tego typu metody) są zaprojektowane do pracy w sytuacjach, w których pierwotny wysoki wymiar jest tylko sztucznie wysoki: dane są wewnętrznie niższe. tzn. dane „siedzą” na kolektorze o niższych wymiarach. Dobrym przykładem, który należy mieć na uwadze, są kolejne zdjęcia tej samej osoby: chociaż mogę reprezentować każdy obraz w liczbie pikseli (wysoki wymiar), wewnątrzwymiarowa wymiarowość danych jest faktycznie ograniczona przez fizyczną transformację punktów (w w tym przypadku obrót głowy 3D). W takich przypadkach t-sne działa dobrze. Ale w przypadkach, gdy istotna wymiarowość jest wysoka lub punkty danych znajdują się na bardzo zróżnicowanym rozmaitości, oczekuje się, że t-sne będzie działać źle, ponieważ jego najbardziej podstawowe założenie - lokalna liniowość na rozmaitości - jest naruszone.

Dla praktycznego użytkownika myślę, że oznacza to dwie przydatne sugestie, o których należy pamiętać:

  1. Przed wykonaniem redukcji wymiarowości dla metod wizualizacji zawsze spróbuj najpierw dowiedzieć się, czy rzeczywiście istnieje mniejszy wewnętrzny wymiar danych, z którymi masz do czynienia.

  2. Jeśli nie masz pewności co do 1 (a także ogólnie), może być przydatne, jak sugeruje oryginalny artykuł, „wykonać t-sne na reprezentacji danych uzyskanej z modelu, który skutecznie reprezentuje bardzo różnorodne rozmaitości danych w wielu warstw nieliniowych, takich jak automatyczny koder ”. Tak więc kombinacja auto-enkodera + t-sne może być dobrym rozwiązaniem w takich przypadkach.

galoosh33
źródło
Cześć @ galoosh33! Zastanawiam się, czy miałeś już okazję rzucić okiem na moją odpowiedź. Czy to było pomocne? Nie mam pojęcia, czy nadal jesteś zainteresowany tym 1,5 roku po zadaniu tego pytania, więc doceniłbym trochę opinii ... W swojej zaakceptowanej odpowiedzi mówisz, że nadal chciałbyś usłyszeć dalsze myśli, ale to także było trochę czas temu :)
ameba mówi Przywróć Monikę
1
dzięki za świetną odpowiedź @amoeba! Przejrzę to w ten weekend.
galoosh33