Skalowalna redukcja wymiarów

9

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(nlog⁡n)O(n)

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

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ż ?kO(nlog⁡n)

pca dimensionality-reduction large-data multidimensional-scaling tsne RUser4512
źródło

Odpowiedzi:

5

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 .O(i⋅n)iO(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
1
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)
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(m2)m
Daniel López
0

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].O(kdN)Ndk

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