Skalierbare Dimensionsreduzierung

9

In Anbetracht der konstanten Anzahl von Merkmalen hat Barnes-Hut t-SNE eine Komplexität von , zufällige Projektionen und PCA eine Komplexität von was sie für sehr große Datenmengen "erschwinglich" macht.O ( n )O(nlogn)O(n)

Andererseits weisen Verfahren, die auf mehrdimensionaler Skalierung beruhen , eine -Komplexität auf.O(n2)

Gibt es andere Techniken zur Dimensionsreduktion (abgesehen von trivialen, wie natürlich das Betrachten der ersten Spalten), deren Komplexität geringer ist als ?kO(nlogn)

RUser4512
quelle

Antworten:

5

Eine interessante Option wäre die Untersuchung der neuronalen Dimensionsreduktion. Der am häufigsten verwendete Netzwerktyp zur Dimensionsreduzierung, der Autoencoder, kann auf Kosten von trainiert werden , wobei die Trainingsiterationen darstellt (ist ein von Trainingsdaten unabhängiger Hyperparameter). . Daher vereinfacht sich die Trainingskomplexität zu .i O ( n )O(in)iO(n)

Sie können zunächst einen Blick auf die Seminararbeit von Hinton und Salakhutdinov 2006 werfen [1]. Seitdem haben sich die Dinge sehr weiterentwickelt. Jetzt wird der größte Teil der Aufmerksamkeit von Variational Autoencodern [2] erreicht, aber die Grundidee (ein Netzwerk, das die Eingabe auf seiner Ausgabeschicht mit einer dazwischen liegenden Engpassschicht rekonstruiert) bleibt dieselbe. Beachten Sie, dass Autoencoder im Gegensatz zu PCA und RP eine nichtlineare Dimensionsreduktion durchführen. Im Gegensatz zu t-SNE können Autoencoder auch unsichtbare Samples transformieren, ohne das gesamte Modell neu trainieren zu müssen.

Auf der praktischen Seite empfehle ich, einen Blick auf diesen Beitrag zu werfen , der Details zur Implementierung verschiedener Arten von Autoencodern mit der wunderbaren Bibliothek Keras enthält.

[1] Hinton, GE & Salakhutdinov, RR (2006). Reduzierung der Dimensionalität von Daten mit neuronalen Netzen. science, 313 (5786), 504 & ndash; 507.

[2] Kingma, DP & Welling, M. (2013). Automatische Codierung von Variationsfeldern. arXiv-Vorabdruck arXiv: 1312.6114.

Daniel López
quelle
1
technisch haben Sie nicht haben das Modell für neue Proben mit t-SNE mit diesem besonderen Ansatz umschulen: lvdmaaten.github.io/publications/papers/AISTATS_2009.pdf
bibliolytic
Sicher. Der Autor schlug außerdem vor, einen multivariaten Regressor zu schulen, um den Kartenstandort aus Eingabedatenproben als möglichen Ansatz vorherzusagen. In dem Artikel erwähnen Sie, dass der Autor ein neuronales Netzwerk trainiert, um den t-SNE-Verlust direkt zu minimieren. In beiden Fällen müssen Sie jedoch ein explizites Modell oder eine explizite Funktion definieren, um Datenpunkte auf den resultierenden Raum abzubilden. Daher muss es leistungsfähig genug sein (genügend Schichten / Neuronen), um die Einbettung zu lernen, aber nicht zu viel, um eine Überanpassung zu vermeiden ... Es opfert einen Teil der Benutzerfreundlichkeit von Standard-t-SNE.
Daniel López
Keine Meinungsverschiedenheit, ich denke nur, dass es ein bisschen ungenau ist, Autoencoder und t-SNE so zu kontrastieren, wie Sie es in Ihrer Antwort tun, da t-SNE als Verlust für die Dimensionsreduktion verwendet werden kann
bibliolytisch
Obwohl jetzt, wo ich wieder lese, eine Frage: Können wir tatsächlich sagen, dass neuronale Netze sind, da nicht garantiert ist, dass sie tatsächlich konvergieren? Big-O-Notation ist Worst-Case-Grenzen, oder? O(n)
Bibliolytic
Ich wollte das nicht in die Antwort aufnehmen, da die Berechnung des t-SNE-Verlusts beim Training eines Netzwerks Zeit benötigt, wobei die Mini-Batch-Größe ist. mO(m2)m
Daniel López
0

Neben den bereits erwähnten Autoencodern kann man versuchen, das Lemma von Johnson-Lindenstrauss mit zufälligen Projektionen oder zufälligen Subraummethoden auszunutzen . Zufällige Projektionen sind , wobei die Anzahl der Stichproben der Dimension und die Zieldimension ist, vgl. [1].N d kO(kdN)Ndk

Ein bisschen googeln bringt Ihnen einige sehr aktuelle Ergebnisse, insbesondere für spärliche Datensätze.

[1] Zufällige Projektion bei der Reduzierung der Dimensionalität: Anwendungen auf Bild- und Textdaten .

Miguel
quelle