Intuitive Erklärung der Funktionsweise von UMAP im Vergleich zu t-SNE

18

Ich habe einen Doktortitel in Molekularbiologie. Meine Studien haben vor kurzem begonnen, hochdimensionale Datenanalysen zu beinhalten. Ich hatte die Idee, wie t-SNE funktioniert (dank eines StatQuest-Videos auf YouTube ), kann mich aber nicht um UMAP kümmern (ich habe mir den Vortrag des UMAP-Erstellers online angehört, fand ihn aber nicht leicht zu verstehen). Ich ging zurück zum Originalpapier, in dem es beschrieben wurde, aber es war zu viel Mathematik für mich.

Kann jemand etwas Licht in das Thema bringen? Ich suche oder eine intuitive Erklärung, ähnlich dem oben verlinkten StatQuest-Video.

Atakan
quelle
1
Ich suche Intuition in Worten, aber auch einen einfachen Einblick in mathematische Berechnungen (ich weiß nicht, ob letzteres möglich ist). Ich würde gerne so etwas für UMAP sehen: "StatQuest tSNE klar erklärt" youtube.com/watch?v=NEaUSP4YerM Wenn ich sage, ich verstehe, wie tSNE funktioniert, beziehe ich mich auf den im Video beschriebenen umfassenden Berechnungsansatz . Es ist etwas schwierig für mich, mir das Beispiel im Video in einem höherdimensionalen Raum vorzustellen, aber insgesamt kann ich sehen, wie die Entfernungen berechnet werden. Ich möchte ein ähnliches Verständnis über UMAP
Atakan

Antworten:

13

Sie sagten, dass Ihr Verständnis von t-SNE auf https://www.youtube.com/watch?v=NEaUSP4YerM basiert und Sie nach einer Erklärung für UMAP auf einer ähnlichen Ebene suchen.

Ich habe dieses Video gesehen und es ist ziemlich genau in dem, was es sagt (ich habe ein paar kleine Nitpicks, aber insgesamt ist es in Ordnung). Komischerweise trifft es fast so auf UMAP zu, wie es ist. Hier sind Dinge, die nicht zutreffen:

  1. Ähnlichkeiten werden aus Entfernungen unter Verwendung eines anderen Kernels berechnet; es ist nicht Gaußsch, aber es fällt auch exponentiell ab und es hat auch eine adaptive Breite, wie in t-SNE.
  2. Ähnlichkeiten werden nicht auf 1 normiert, sondern am Ende auf einen konstanten Wert normiert.
  3. Ähnlichkeiten werden symmetrisiert, aber nicht nur durch Mittelung.
  4. Der Ähnlichkeitskern im Einbettungsraum ist nicht genau ein t-Verteilungskern, sondern ein sehr sehr ähnlicher Kernel.

Ich denke, all diese Unterschiede sind nicht sehr wichtig und nicht sehr folgenreich. Der eigentlich wichtige Teil ist der Teil, in dem der Erzähler im Video sagt (10m40s):

Wir möchten, dass diese Zeile wie diese Zeile aussieht [...]

Das Video erklärt nicht, wie t-SNE quantifiziert, ob sie ähnlich sind oder nicht, und wie weiterhin erreicht wird, dass sie ähnlich aussehen. Beide Teile sind in UMAP unterschiedlich. Die zitierte Aussage kann aber auch für UMAP gelten.


Die Art und Weise, wie das UMAP-Papier geschrieben ist, die rechnerischen Ähnlichkeiten mit t-SNE sind nicht sehr offensichtlich. Scrollen Sie nach unten zu Anhang C unter https://arxiv.org/pdf/1802.03426.pdf und / oder suchen Sie hier https://jlmelville.github.io/uwot/umap-for-tsne.html , wenn Sie eine sehen möchten Nebeneinander Vergleich der oben aufgeführten Berechnungen und der Verlustfunktionen von t-SNE und UMAP.

Amöbe
quelle
Das ist sehr hilfreich, danke! Ich habe eine Frage zu diesem bestimmten Segment des Videos. Wenn er links die "ungeordnete Heatmap" anzeigt, sind die Anmerkungspunkte (farbige Datenpunkte) in Ordnung und die Farbintensität am Zeilen-Spalten-Schnittpunkt stimmt nicht mit dem Diagramm auf der rechten Seite überein. Das ist eine falsche Darstellung, oder? Ich würde erwarten, dass die Grafik links ungeordnet ist, wenn es um Datenpunkte geht, die dann von UMAP sortiert werden. Bin ich hier auf dem falschen Weg?
Atakan
@ Atakan Ich bin nicht ganz sicher, was du sagst. Ich sehe keine falsche Darstellung. Ich schaue mir den Videorahmen um 10:40 an. Die linke Ähnlichkeitsmatrix ist "ein Durcheinander". Die "Anmerkungspunkte" links markieren einfach die Gruppe jedes Punktes. Stellen Sie sich vor, die Punkte sind von 1 bis 12 nummeriert. Die 12 Zeilen / Spalten der Matrix entsprechen diesen Punkten. Die ersten 4 Zeilen entsprechen den "blauen" Punkten, die nächsten 4 entsprechen den "roten" Punkten usw. Da die eindimensionale Einbettung (im unteren Bereich des Rahmens) "ein Durcheinander" ist, sind die Ähnlichkeiten in der Matrix sind auch "ein Chaos".
Amöbe
8

Der Hauptunterschied zwischen t-SNE und UMAP ist die Interpretation des Abstands zwischen Objekten oder "Clustern". Ich benutze die Anführungszeichen, da beide Algorithmen nicht für das Clustering gedacht sind - sie sind hauptsächlich für die Visualisierung gedacht.

t-SNE behält die lokale Struktur in den Daten bei.

UMAP behauptet, sowohl die lokale als auch den größten Teil der globalen Struktur in den Daten beizubehalten.

Dies bedeutet, dass Sie mit t-SNE den Abstand zwischen den Clustern A und B an verschiedenen Enden Ihres Diagramms nicht interpretieren können. Sie können nicht schließen, dass diese Cluster unterschiedlicher sind als A und C, wobei C im Diagramm näher an A liegt. Innerhalb von Cluster A können Sie jedoch sagen, dass nahe beieinander liegende Punkte ähnlichere Objekte sind als Punkte an verschiedenen Enden des Clusterbilds.

Mit UMAP sollten Sie in der Lage sein, sowohl die Abstände zwischen / Positionen von Punkten als auch von Clustern zu interpretieren.

Beide Algorithmen sind sehr stochastisch und hängen stark von der Wahl der Hyperparameter ab (t-SNE sogar mehr als UMAP) und können in verschiedenen Läufen sehr unterschiedliche Ergebnisse liefern, sodass Ihr Diagramm möglicherweise Informationen in den Daten verschleiert, die ein nachfolgender Lauf möglicherweise enthüllt.

Gute alte PCA hingegen ist deterministisch und mit Grundkenntnissen der linearen Algebra (Matrixmultiplikation und Eigenprobleme) leicht verständlich, aber nur eine lineare Reduktion im Gegensatz zu den nichtlinearen Reduktionen von t-SNE und UMAP.

Edgar
quelle
10
Ich stimme dieser Einschätzung überhaupt nicht zu: "t-SNE behält die lokale Struktur bei und ignoriert die globale Struktur. UMAP erkennt sowohl die lokale als auch die globale Struktur an." UMAP arbeitet mit dem Diagramm der k-nächsten Nachbarn (für einen kleinen Wert von k) genau wie t-SNE.
Amöbe
Dies ist eigentlich das, was die Autoren des UMAP behaupten, siehe zB hier oder hier . Kennen Sie einen Vergleich (theoretisch oder praktisch), der zeigt, dass ihre Behauptung nicht wahr ist? Bitte teilen!
Edgar
6
Ich weiß, dass sie das sagen ...: - / Aber sie sind es, die diese Aussage machen, also liegt es an ihnen, das zu beweisen (nicht an mir, es zu widerlegen). Ich war nicht überzeugt von dem, was ich bisher gesehen habe.
Amöbe
2
Es stimmt, es ist immer noch eine neue Methode. Hoffen wir, dass eine genauere Bewertung von umap vs t-sne vorgenommen wird. Ich habe meine Antwort geändert, um Ihren Standpunkt widerzuspiegeln.
Edgar