Skalowalna redukcja wymiarów

Biorąc pod uwagę stałą liczbę funkcji, Barnes-Hut t-SNE ma złożoność , losowe projekcje i PCA mają złożoność co czyni je „przystępnymi” dla bardzo dużych zestawów danych. $O(n\log n)$ $O(n)$

Z drugiej strony metody oparte na skalowaniu wielowymiarowym mają złożoność . $O(n^2)$

Czy istnieją inne techniki redukcji wymiarów (poza trywialnymi, jak na przykład spojrzenie na pierwsze kolumn), których złożoność jest mniejsza niż ? $k$ $O(n\log n)$

— RUser4512
źródło

Ciekawą opcją byłoby zbadanie neuronowej redukcji wymiarowości. Najczęściej używany typ sieci do redukcji wymiarów, autoencoder, można trenować kosztem , gdzie reprezentuje iteracje treningowe (jest hiperparametrem niezależnym od danych treningowych) . Dlatego złożoność szkolenia upraszcza się do . $\mathcal{O}(i\cdot n)$ $i$ $\mathcal{O}(n)$

Możesz zacząć od przyjrzenia się pracy seminaryjnej 2006 Hinton i Salakhutdinov [1]. Od tego czasu wiele się zmieniło. Obecnie większą uwagę zwracają autoakodery wariacyjne [2], ale podstawowa idea (sieć, która rekonstruuje dane wejściowe na swojej warstwie wyjściowej z warstwą wąskiego gardła pomiędzy nimi) pozostaje taka sama. Należy zauważyć, że w przeciwieństwie do PCA i RP, autoencodery dokonują nieliniowej redukcji wymiarowości. Ponadto, w przeciwieństwie do t-SNE, autokodery mogą przekształcać niewidzialne próbki bez konieczności ponownego szkolenia całego modelu.

Z praktycznego punktu widzenia polecam zajrzeć do tego postu , który zawiera szczegółowe informacje na temat wdrażania różnych typów autoencoderów za pomocą wspaniałej biblioteki Keras.

[1] Hinton, GE i Salakhutdinov, RR (2006). Zmniejszenie wymiarów danych za pomocą sieci neuronowych. science, 313 (5786), 504-507.

[2] Kingma, DP, i Welling, M. (2013). Automatyczne kodowanie pól wariacyjnych. nadruk arXiv arXiv: 1312.6114.

— Daniel López
źródło

technicznie nie trzeba przekwalifikowywać modelu na nowe próbki z t-SNE, stosując to szczególne podejście: lvdmaaten.github.io/publications/papers/AISTATS_2009.pdf

— bibliolityczny

Pewnie. Autor zasugerował również szkolenie regresora wielowymiarowego w celu przewidywania lokalizacji danych mapy z próbek danych wejściowych jako potencjalnego podejścia. W artykule, o którym wspominasz, autor trenuje sieć neuronową, aby bezpośrednio minimalizować utratę t-SNE. Jednak w obu przypadkach musisz zdefiniować jawny model lub funkcję, aby odwzorować punkty danych na wynikową przestrzeń, więc musi być wystarczająco potężny (wystarczająca liczba warstw / neuronów), aby nauczyć się osadzania, ale nie za bardzo, aby uniknąć nadmiernego dopasowania. ... Poświęca to trochę użyteczności standardowego t-SNE.

— Daniel López

Nie ma tutaj nieporozumień, po prostu uważam, że jest to trochę niedokładne w stosunku do autoenkoderów kontrastowych i t-SNE, tak jak robisz to w swojej odpowiedzi, ponieważ t-SNE może być użyty jako strata dla zmniejszenia wymiarów

— bibliolityczny

Chociaż teraz, gdy przeczytałem ponownie, pytanie: czy możemy powiedzieć, że sieci neuronowe to , ponieważ nie gwarantuje się, że faktycznie się zbiegną? Notacja Big-O to najgorsze granice, prawda?

O (n)

$\mathcal{O}(n)$

— bibliolityczny

Nie chciałem tego uwzględniać w odpowiedzi, ponieważ obliczenie utraty t-SNE podczas szkolenia sieci zajmuje czas, gdzie jest rozmiarem mini-partii.

O (m^{2})

$\mathcal{O}(m^2)$

m

$m$

— Daniel López

Oprócz wspomnianych już autokoderów, można spróbować wykorzystać lemat Johnsona-Lindenstraussa za pomocą losowych rzutów lub losowych metod podprzestrzeni. Występy są losowe , z liczbę próbek o wymiarze i o wymiar cel CF [1]. $\mathcal{O}(k d N)$ $N$ $d$ $k$

Trochę googlingu przyniesie kilka bardzo najnowszych wyników, w szczególności dla rzadkich zestawów danych.

[1] Losowa projekcja w redukcji wymiarowości: aplikacje do danych obrazu i tekstu .

— Miguel
źródło