Gibt es Versionen von t-SNE für das Streaming von Daten?

19

Mein Verständnis von t-SNE und der Barnes-Hut-Näherung ist, dass alle Datenpunkte erforderlich sind, damit alle Kraftwechselwirkungen gleichzeitig berechnet werden können und jeder Punkt in der 2d-Karte (oder der Karte mit der niedrigeren Dimension) angepasst werden kann.

Gibt es Versionen von t-sne, die effizient mit Streaming-Daten umgehen können? Wenn also meine Beobachtungen einzeln eintreffen, wird der beste Ort auf der 2D-Karte gefunden, um die neue Beobachtung zu platzieren, oder es werden kontinuierlich alle Punkte auf der 2D-Karte aktualisiert, um die neue Beobachtung zu berücksichtigen.

Wäre das überhaupt sinnvoll oder geht es gegen das Setup von t-sne.

Ger
quelle
Die Barnes-Hut-Näherung macht t-SNE hoch skalierbar (zumindest können Sie es mit 100.000 Zeilen verwenden, ich habe es ausprobiert). Sie können es von R: cran.r-project.org/web/packages/Rtsne/index.html
RUser4512,
Hey danke! Ich freue mich, für Ihre Antwort zu stimmen, wenn Sie sie in den Antwortbereich dieses Artikels aufnehmen.
Tom
3
Hier finden Sie eine parametrische Version, die mit einem neuronalen Netzwerk implementiert wurde. lvdmaaten.github.io/publications/papers/AISTATS_2009.pdf
eyaler

Antworten:

15

Ich hatte genau die gleiche Frage und habe sie auf einem YouTube-Video eines CS231n-Vortrags gepostet, den Andrej Karpathy vor einigen Wochen gehalten hat. Hier ist die Frage, die ich gepostet habe, gefolgt von Andrejs Antwort:

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

Q:

Benötigt t-SNE eine ganze Reihe von Bildern (oder allgemeiner Daten), um den niedrigdimensionalen Merkmalsraum zu erstellen? Mit PCA können Sie einen niedrigdimensionalen Merkmalsraum auf einem Datenstapel erstellen und dann neue Datenpunkte auf denselben Raum projizieren, ohne dass Sie dies "neu trainieren" müssen. Gilt das für t-SNE?

Ich frage, weil mir aufgefallen ist, dass scikit-learn t-SNE als Teil seiner vielfältigen Klasse hat, aber dieses Modul keine transform () -Methode wie PCA hat. Zumindest in sklearn scheint dies nicht möglich zu sein.

Meine Frage läuft darauf hinaus. Wie würden Sie t-SNE in einer Streaming- oder Online-Situation anwenden, in der Sie die Visualisierung kontinuierlich mit neuen Bildern aktualisieren möchten? Vermutlich möchte man den Algorithmus nicht für jedes neue Bild auf den gesamten Stapel anwenden.

EIN:

+ Evan Zamir Ja, dies ist mit t-SNE möglich, wird jedoch bei regulären t-SNE-Implementierungen möglicherweise nicht sofort unterstützt. Normalerweise ist die Position jedes Punktes ein Parameter in der Optimierung, aber Sie können genauso gut eine Zuordnung von High-D -> Low-D (z. B. neuronales Netz) und Backprop durch die Positionen erstellen. Dann haben Sie die Einbettungsfunktion und können neue Punkte projizieren. Im Prinzip steht dem also nichts im Wege, aber einige Implementierungen unterstützen es möglicherweise nicht, da es sich um einen weniger häufigen Anwendungsfall handelt.

thecity2
quelle
11

Wenn Sie mit Streaming-Daten arbeiten, möchten / müssen Sie möglicherweise nicht alle Punkte im Verlauf in eine einzelne t-SNE-Karte einbetten. Alternativ können Sie eine Online-Einbettung durchführen, indem Sie die folgenden einfachen Schritte ausführen :

  1. Wählen Sie ein Zeitfenster der Dauer T, das lang genug ist, damit jedes interessierende Muster mindestens ein paar Mal in der Fensterdauer erscheint.

  2. Scrollen Sie durch das Fenster, während die Datenströme einlaufen, mit einem Zeitschritt dt, der viel kleiner als T ist. Berechnen Sie für jede Position des Fensters eine t-SNE-Einbettung der Datenpunkte im Zeitfenster.

  3. Setzen Sie jede Einbettung mit dem Ergebnis der vorherigen ein. In t-SNE muss man die Anfangskoordinaten der Datenpunkte im niedrigdimensionalen Raum wählen. In unserem Fall teilen zwei aufeinanderfolgende Einbettungen die meisten ihrer Datenpunkte, da wir dt viel kleiner als T wählen. Ordnen Sie für alle gemeinsam genutzten Datenpunkte ihre Anfangskoordinaten in der aktuellen Einbettung ihren Endkoordinaten in der vorherigen Einbettung zu . Dieser Schritt stellt sicher, dass ähnliche Muster über aufeinanderfolgende Einbettungen hinweg konsistent dargestellt werden. (In der sklearn-Implementierung in Python ist der seed-Parameter "init". Standardmäßig legt die sklearn-Implementierung die Anfangsposition der Punkte nach dem Zufallsprinzip fest.)

Hinweis 1: Es ist wichtig, dass die Muster von Interesse in einem bestimmten Zeitfenster mindestens einmal auftreten, damit der Speicher der Darstellung nicht verloren geht, wenn das Fenster durch den Datensatz gleitet. Tatsächlich konvergiert t-SNE typischerweise nicht zu einer eindeutigen Lösung, sondern nur zu einem lokalen Minimum. Wenn der Speicher verloren geht, kann ein ähnliches Muster in zwei Instanzen einer Einbettung auf sehr unterschiedliche Weise dargestellt werden.

Anmerkung 2: Diese Methode ist besonders relevant, wenn es um instationäre Zeitreihen geht, bei denen Muster verfolgt werden sollen, die sich langsam im Laufe der Zeit entwickeln. In der Tat wird jede Einbettung speziell auf das kleine Zeitfenster zugeschnitten, in dem sie berechnet wird, um sicherzustellen, dass die zeitlich lokale Struktur optimal erfasst wird (im Gegensatz zu einer vollständigen Einbettung des gesamten nicht stationären Datensatzes).

Anmerkung 3: Bei dieser Methode können die aufeinanderfolgenden Einbettungen nicht parallelisiert werden, da das Ergebnis der vorherigen Einbettung benötigt wird, um die nächste Einbettung zu erhalten. Da jedoch der Startwert (dh die Anfangskoordinaten der Punkte) für die meisten Punkte (alle gemeinsamen Punkte zwischen aufeinanderfolgenden Einbettungen) gut ausgewählt ist, konvergiert eine Einbettung normalerweise sehr schnell, und zwar nur in wenigen Iterationen.

Ein Beispiel für die Anwendung dieser Methode auf instationäre Zeitreihen finden Sie in diesem Artikel ( ICLR 2016, Lernen stabiler Darstellungen in einer sich verändernden Welt mit online t-SNE: Proof of Concept im Singvogel ), in dem sie erfolgreich angewendet wurde die Entstehung von Silben über die Entwicklung im Singvogel zu verfolgen.

Stéphane Deny
quelle
2
Willkommen in der Community. Selbstplagiat ist uncool. Ich beziehe mich auf Ihr erster Beitrag hier . Sicher, wir können dieselbe Begründung für mehrere Antworten verwenden, möglicherweise einen oder zwei Sätze kopieren und einfügen oder einfach direkt auf vorherige Antworten verweisen. Dies bedeutet jedoch nicht, dass Ihre Posts auf eine wörtliche Kopie der vorherigen Antworten mit geändertem ersten Satz reduziert werden. Es verringert die Qualität des Lebenslaufs und zeigt schlechte schulische Sportlichkeit von Ihnen.
usεr11852 sagt Reinstate Monic
5
@ usεr11852 Das Problem wurde verursacht, weil der andere Thread ein Duplikat dieses Threads ist. Ich habe daher die andere geschlossen, mit dieser zusammengeführt und die überflüssige Antwort gestrichen. Im Allgemeinen, Stéphane, wenn Sie sich inspiriert fühlen, genau dieselbe Antwort in zwei Threads zu posten, markieren Sie bitte einen von ihnen als Duplikat, damit wir sie kombinieren können.
whuber
2
@ usεr11852 OK, entschuldigen Sie die doppelte Antwort. Ich bin ein neuer Mitwirkender, daher kenne ich die Best Practices noch nicht.
Stéphane Deny
1
@whuber Danke für das Zusammenführen der Fragen und für die Heads-up!
Stéphane Deny
1
Sie haben anscheinend 2 Upvotes verloren. Das ist bedauerlich. +1 :) Willkommen zum Lebenslauf.
Amöbe sagt Reinstate Monica
7

Es gibt eine kürzlich veröffentlichte Variante namens A-tSNE, die das dynamische Hinzufügen neuer Daten und das Verfeinern von Clustern unterstützt, entweder basierend auf Interessensgebieten oder durch Benutzereingaben. Das unten verlinkte Papier enthält einige hübsche Beispiele dafür:

Zitierweise: arXiv: 1512.01655

Ungefähre und benutzergesteuerte tSNE für progressive visuelle Analytik Nicola Pezzotti, Boudewijn PF Lelieveldt, Laurens van der Maaten, Thomas Höllt, Elmar Eisemann, Anna Vilanova

Zusammenfassung:

Progressive Visual Analytics zielt darauf ab, die Interaktivität in vorhandenen Analysetechniken durch Visualisierung sowie Interaktion mit Zwischenergebnissen zu verbessern. Eine Schlüsselmethode für die Datenanalyse ist die Dimensionsreduzierung, um beispielsweise 2D-Einbettungen zu erstellen, die effizient visualisiert und analysiert werden können. Das t-Distributed Stochastic Neighbor Embedding (tSNE) ist eine geeignete Technik zur Visualisierung mehrerer hochdimensionaler Daten. tSNE kann aussagekräftige Zwischenergebnisse erzeugen, leidet jedoch unter einer langsamen Initialisierung, die seine Anwendung in Progressive Visual Analytics einschränkt. Wir führen eine steuerbare tSNE-Näherung (A-tSNE) ein, bei der Geschwindigkeit und Genauigkeit gegeneinander abgewogen werden, um eine interaktive Datenexploration zu ermöglichen. Wir bieten Visualisierungstechniken in Echtzeit an, einschließlich einer dichtebasierten Lösung und einer magischen Linse zur Überprüfung des Approximationsgrades. Mit diesem Feedback kann der Benutzer lokale Verfeinerungen festlegen und das Approximationsniveau während der Analyse steuern. Wir demonstrieren unsere Technik anhand mehrerer Datensätze in einem realen Forschungsszenario und für die Echtzeitanalyse von hochdimensionalen Datenströmen, um ihre Wirksamkeit für die interaktive Datenanalyse zu veranschaulichen.

cvlad
quelle
Willkommen auf der Seite. Wir versuchen, ein permanentes Repository mit hochwertigen statistischen Informationen in Form von Fragen und Antworten aufzubauen. Aus diesem Grund sind wir aufgrund von Linkrot vorsichtig, wenn nur Links beantwortet werden. Kannst du ein vollständiges Zitat und eine Zusammenfassung der Informationen unter dem Link posten, falls sie tot sind?
gung - Wiedereinsetzung von Monica
6

Die Barnes-Hut-Näherung macht t-SNE hoch skalierbar (zumindest können Sie es mit 100.000 Zeilen verwenden, ich habe es ausprobiert). Sie können es von R: Rtsne aufrufen

O(nLog(n))O(n2)

RUser4512
quelle
1
Ich habe es mit 250K dichten 1K-Linien verwendet - war eigentlich ziemlich gut, aber es ist an den Speicher gebunden.
Vladimir Chupakhin
2

Die Barnes-Hut-Approximation ist jetzt die Standardmethode in scikit-learn ab Version 0.17.0:

Standardmäßig verwendet der Algorithmus zur Gradientenberechnung die Barnes-Hut-Näherung in O-Zeit (NlogN). method = 'exact' wird auf dem langsameren, aber genauen Algorithmus in O (N ^ 2) ausgeführt. Der genaue Algorithmus sollte verwendet werden, wenn der Fehler bei der nächsten Nachbarschaft besser als 3% sein muss. Die genaue Methode kann jedoch nicht auf Millionen von Beispielen skaliert werden. Neu in Version 0.17: Ungefähre Optimierungsmethode über die Barnes-Hut.

thecity2
quelle
Dies spricht die Frage nicht an. BH ist zwar schneller, unterstützt aber kein Streaming. Vielleicht meintest du damit einen Kommentar zu dieser Antwort .
13.