Kennen Sie UMAP? Ich kenne

Wenn Sie davon gehört haben, es aber nicht wissen, hilft Ihnen dieser Artikel, es zu verstehen.

Was ist UMAP?

** Es ist eine Methode, um Dimensionen schneller und mit höherer Leistung als t-SNE zu reduzieren und zu visualisieren **. Vergleichen wir es mit dem häufig verwendeten t-SNE. Die folgende Abbildung ist eine Visualisierung von Fashion MNIST.

(Aus [UMAP verstehen] [UMAP verstehen])

Im Vergleich zu t-SNE zeigt UMAP, dass die Cluster klar voneinander getrennt sind. Ähnliche Kategorien befinden sich auch nahe beieinander, und unterschiedliche Kategorien befinden sich weit voneinander entfernt. (In der Erläuterung von [Grundlegendes zu UMAP] und [Grundlegendes zu UMAP] finden Sie viele Beispiele für die Visualisierung. Weitere Informationen finden Sie in der obigen 3D-Abbildung.)

** UMAP hat unabhängig von der Anzahl der eingebetteten Dimensionen eine nahezu konstante Ausführungszeit **. Im Gegensatz zu t-SNE erhöht sich die Ausführungszeit nicht exponentiell, selbst wenn die eingebettete Dimension zunimmt, sodass sie nicht nur zur Visualisierung, sondern auch zur Dimensionsreduzierung verwendet werden kann. Außerdem ist in Python geschriebenes UMAP schneller als FIt-SNE, eine schnelle Implementierung von t-SNE in C ++.

Und ** unterstützt das Einbetten neuer Samples **. Im Fall von t-SNE war es schwierig, dem niedrigdimensionalen Raum neue Daten hinzuzufügen, und das Ganze musste erneut ausgeführt werden. Auf der anderen Seite müssen Sie mit UMAP nur die Differenz berechnen und können sie natürlich einbetten.

** Wenn Sie es nur als Werkzeug verwenden möchten, ist es sehr einfach. ** (Code stammt aus [Offizielles Dokument] howToUseUMAP)

!pip install umap-learn

import numpy as np
from sklearn.datasets import load_digits
import matplotlib.pyplot as plt
import umap

#Versuchen Sie es mit Ziffern
digits = load_digits()

#Mit umap auf 2 Dimensionen reduziert
reducer = umap.UMAP(random_state=42)
reducer.fit(digits.data)
embedding = reducer.transform(digits.data)

# plot
plt.scatter(embedding[:, 0], embedding[:, 1], c=digits.target, cmap='Spectral', s=5)
plt.gca().set_aspect('equal', 'datalim')
plt.colorbar(boundaries=np.arange(11)-0.5).set_ticks(np.arange(10))
plt.title('UMAP projection of the Digits dataset', fontsize=24);

Darüber hinaus kann es auch für eine sehr hochdimensionale und große Datenmenge in einer realistischen Zeit ausgeführt werden. Die folgende Abbildung zeigt 30 Millionen Ganzzahlen als Eingabe, bei denen es sich um einen primär faktorisierten Binärvektor handelt. (Ich weiß nicht, ob es eine aussagekräftige Visualisierung ist, aber es ist cool)

Wenn Sie damit zufrieden sind, ist dies das Ende. Bitte benutzen Sie es bequem als Werkzeug.

Bestehende Methode

Bevor wir uns mit der Erklärung von UMAP befassen, werfen wir einen kurzen Blick auf die vorhandenen Methoden.

Bisher wurden viele Methoden zur Dimensionsreduzierung vorgeschlagen. Es ist erforderlich, die globale Struktur und die lokale Struktur der Daten beizubehalten. Und in letzter Zeit ist auch eine gewisse Rechengeschwindigkeit erforderlich.

Lineare Methode (PCA usw.)

Funktioniert gut für künstliche Daten, hat jedoch eine schlechte Leistung für hochdimensionale reale Daten. Swiss-Roll funktioniert nicht.

Nichtlineare Methode

UMAP gehört hierher.

Isomap
LLE
Laplacian Eignmap
t-SNE
LargeVis

Unter diesen wird ** t-SNE häufig als Methode ** verwendet, die sowohl die globale als auch die lokale Struktur gut beibehalten kann. Es gab jedoch ein Problem mit der Ausführungszeit, und LargeVis und andere wurden vorgeschlagen, um es zu lösen. In diesem Artikel werde ich versuchen, UMAP auf technische Weise zu erklären, aber ich denke, es ist einfacher zu verstehen, wenn Sie über Kenntnisse in Isomap und t-SNE verfügen. Die in den vorhandenen Methoden aufgeführten Artikel sind in Referenzen zusammengefasst.

Zeichendefinition

Hier sind einige Definitionen für die Zukunft.

Anzahl der Daten $ N $
$ n $ Dimension High Dimension-Datensatz $ X $
- X = \\{x_1, x_2, ..., x_N\\}, \; x_i \in \mathbb{R}^n
$ m $ Dimension Datensatz mit niedriger Dimension $ Y $ ($ m << n $)
- Y = \\{y_1, y_2, ..., y_N\\}, \; y_i \in \mathbb{R}^m

Im Folgenden werden diese Zeichen ohne vorherige Ankündigung verwendet.

Technisches Verständnis von UMAP

Lassen Sie uns zunächst den Zweck von UMAP erneut bestätigen.

** Konvertieren hochdimensionaler Daten $ X $ in niedrigdimensionale Daten $ Y $. Die lokale Struktur und die globale Struktur von $ X $ bleiben jedoch erhalten und werden konvertiert. ** ** **

UMAP-Papiere können ohne mathematische Kenntnisse nicht wirklich verstanden werden. Das Papier enthält jedoch Erklärungen für diejenigen, die keine mathematischen Kenntnisse haben. UMAP basiert auf fortgeschrittener Mathematik, aber tatsächlich kann ** UMAP als Graphenerstellung und -operation auf dem Graphen angesehen werden **. Dies liegt daran, dass UMAP auf einer sehr ähnlichen Idee basiert wie Isomap, t-SNE, Large Vis usw.

Der Ablauf der Methode besteht aus den folgenden zwei Schritten.

Erstellen Sie ein gewichtetes k-Nachbarschaftsdiagramm
Platzieren Sie das Diagramm in einer niedrigeren Dimension

Die Abbildung stammt aus [Large Vis Paper] [Large Vis Paper]

Schritt 1 konzentriert sich auf die lokale Struktur der Daten. Dann wird der auf der lokalen Struktur basierende Graph so angeordnet, dass er die globale Struktur in Schritt 2 (Bild) darstellt. Da die Stationsentfernung in einer Vielzahl lokal als euklidische Entfernung betrachtet werden kann, ist das Bild eines nahe gelegenen Bluffs unter Verwendung der euklidischen Entfernung ausreichend. (Eigentlich ist es nicht auf die Entfernung beschränkt, sondern kann auch für Dinge wie Unähnlichkeit verwendet werden.)

Schauen wir sie uns der Reihe nach an.

1. Erstellen Sie ein gewichtetes k-Nachbarschaftsdiagramm

① Machen Sie eine Grafik in der Nähe von k

Lassen Sie uns zunächst ein Nachbarschaftsdiagramm ohne Gewichtung erstellen. Definieren Sie Entfernungen (Metriken) $ d $, um die Nachbarschaft zu finden (Stellen Sie sich eine euklidische Entfernung usw. vor).

Dann werden die k Nachbarschaften in der Metrik $ d $ von $ x_i $ wie folgt geschrieben. \\{x_{i_1}, ..., x_{i_k}\\}

Die Nachbarschaftssuche kann die normale k-nahe-Methode verwenden, UMAP verwendet jedoch eine Approximationsmethode. Die normale k-Nachbarschaftsmethode kostet $ O (N ^ 2) $, aber die Approximationsmethode beschleunigt sich auf $ O (N ^ {1.14}) $. Einzelheiten finden Sie in der Referenz [Vorfront der ungefähren Suche nach dem nächsten Nachbarn] [Ungefähre knn].

Erstellen Sie nach Abschluss der Nachbarschaftssuche ein k-Nachbarschaftsdiagramm, indem Sie die Nachbarschaften miteinander zusammendrücken. Das heißt, die Seitenmenge $ E $ und die Scheitelpunktmenge $ V $ sind wie folgt definiert.

E = \\{(x_i, x_{i_j}) \; | \; 0\leq i \leq N, \, 0\leq j \leq k \\} $ V $ entspricht jedem Punkt der Daten.

Auf diese Weise wurde ein gerichteter k-Nachbargraph $ G_1 $ ohne Gewichte erstellt. $ G_1 = (V, E) $

Um es ein wenig zusammenzufassen ** In "(1) Erstellen eines k-Nachbarschaftsgraphen" wurden k Nachbarschaften nach jedem $ x_i $ hochdimensionaler Daten $ X $ durchsucht und ein ungewichteter gerichteter k-Nachbarschaftsgraph $ G_1 $ erstellt. ** ** **

➁ Erstellen Sie ein gewichtetes k-Nachbarschaftsdiagramm

Um Gewicht hinzuzufügen, definieren Sie zuerst die Gewichtungsfunktion $ w $. Die rechte Seite wird durch $ \ rho_i $ und $ \ sigma_i $ normalisiert.

w((x_i, x_{i_j})) = \exp(\dfrac{-\max(0, \, d(x_i, x_{i_j})-\rho_i)}{\sigma_i})

Wobei $ \ rho_i $ die Entfernung zum nächsten Nachbarn ist. \rho_i = \min\\{d(x_i, x_{i_j}) \; |\; 1\leq j \leq k \\}

Außerdem wird $ \ sigma_i $ durch eine zweiteilige Suche erhalten, um die folgende Gleichung zu erfüllen. \Sigma_j w((x_i, x_{i_j})) = \log_2 (k) $ \ Log_2 (k) $ auf der rechten Seite wird empirisch erhalten.

(Dieses $ log_2 {k} $ ist etwas, das ich nicht weiß, aber ich denke, es hat eine ratlose Bedeutung von t-SNE, da die Verteilung durch eine zweiteilige Suche berechnet wird.)

Erstellen Sie mit der obigen Gewichtungsfunktion einen gerichteten gewichteten Graphen $ G_2 $. G_2 = (V, E, w)

Dieses $ G_2 $ wird jedoch nicht so verwendet, wie es ist. Erstellen Sie mit der folgenden Konvertierung ein ungerichtetes Diagramm $ G $. $ A $: Benachbarte Matrix von $ G_2 $ $ B = A + A ^ T-A \ circ A ^ T, \ circ: Adamar-Produkt $

Wenn Sie sich die Elemente von $ B $ ansehen, können Sie sehen, dass sie zielgerichtet sind. B_{i,l} = w((x_i, x_l)) + w((x_l, x_i)) - w((x_i, x_l))*w((x_l, x_i)) \\ = B_{l. i}

(Ich denke, dies funktioniert genauso wie t-SNE, das die bedingte Wahrscheinlichkeit von SNE symmetrisiert. Die Kostenfunktion wird einfacher zu handhaben.)

Der Graph $ G $ wird unter Verwendung des auf diese Weise erstellten $ B $ als benachbarte Matrix erstellt. Platzieren Sie dieses Diagramm $ G $ in Schritt ➂ in einer niedrigeren Dimension.

Um es ein wenig zusammenzufassen ** In "➁ Erstellen eines gewichteten k-Nachbarschaftsgraphen" wurde ein gewichteter und ungerichteter k-Nachbarschaftsgraph $ G $ erstellt **.

2. In eine niedrigere Dimension legen

Nachdem wir nun eine benachbarte Matrix haben, möchten wir sie in einem niedrigdimensionalen Raum platzieren. Das Verfahren zum Zeichnen eines Graphen aus einer benachbarten Matrix ist jedoch nicht eindeutig. Schauen Sie sich die beiden folgenden Abbildungen an.

Beide sind Visualisierungen desselben Graphen (Bilder stammen von [hier] [Erklärung des mechanischen Modells]). Verwenden Sie ** Dynamikmodell ** für eine saubere Platzierung. Da die Erklärung lang sein wird, habe ich die Erklärung des dynamischen Modells in [Qiita separater Artikel (Graph Drawing Algorithmus und die Rückseite von Networkx)] [Qiita Dynamic Model] geschrieben. Im dynamischen Modell werden die Eckpunkte mit dem folgenden Algorithmus gut angeordnet.

Berechnen Sie die Anziehungs- / Abstoßungskraft, die zwischen den einzelnen Spitzen wirkt
Verschieben Sie die Eckpunkte basierend auf der in 1 berechneten Kraft. Die Größe der Bewegungsverschiebung ist kleiner oder gleich dem Temperaturparameter $ t $
Verringern Sie den Temperaturparameter
Wiederholen Sie die Schritte 1 bis 3 einige Male

Da es notwendig ist, Anziehungskraft und Abstoßungskraft im mechanischen Modell zu definieren, wird es wie folgt definiert. Ich werde erklären, warum diese Formel etwas später ist, also werde ich sie akzeptieren und weitermachen.

f_a(y_i, y_j) = \dfrac{-2ab\|y_i - y_j\|^{2(b-1)}} {1+\|y_i - y_j\|^2} w((x_i, x_j))(y_i - y_j)

f_r(y_i, y_j) = \dfrac{b} {(\epsilon + \|y_i - y_j\|^2)(1 + \|y_i - y_j\|^2)} (1 - w((x_i, x_j))) (y_i - y_j)

$ a, b $: Hyperparameter $ \ Epsilon $: Kleiner Wert, um eine Nullteilung zu vermeiden

UMAP hat jedoch die Berechnung der Abstoßungskraft optimiert. Betrachtet man einen Scheitelpunkt $ x_i $

Die Anziehungskraft wirkt auf k in der Nähe
Die Abstoßungskraft wirkt auf andere N-k-Teile als die Umgebung

Im Allgemeinen ist $ k << N $, sodass die Berechnung der Abstoßungskraft zu einem Engpass wird. UMAP verwendet ** negative Stichprobe **, um den Rechenaufwand zu reduzieren. Scheitelpunkte, die nicht durch Seiten verbunden sind, gelten als durch eine negative Flanke verbunden.

Probieren Sie diese negative Flanke dann gut aus und aktualisieren Sie sie vorläufig. UMAP verwendet die folgende Vertex-Stichprobenverteilung $ P $. Dies kann einer gleichmäßigen Verteilung in einem ausreichend großen Datensatz angenähert werden. (Ich weiß nichts darüber, also sag es mir bitte.)

P(x_i) = \dfrac{ \sum_{\{a \in A | d_0(a) = x_i\}}{1 - \mu(a)} }{ \sum_{\{b\in A | d_0(b) \neq x_i \}}{1 - \mu(b)} }

$ \ mu $: Mitgliedschaftsfunktion (Zugehörigkeitsgrad zu $ \ mu: A \ rightarrow [0, 1] $, $ A $) $ A $: Fuzzy topologischer Ausdruck (wahrscheinlich)

Wenn Sie die Platzierung aktualisieren, anstatt alle negativen Flanken zu verwenden, probieren Sie einige aus und aktualisieren Sie sie. Mit anderen Worten ist der Algorithmus wie folgt.

Berechnen Sie die Anziehungskraft, die zwischen jedem Scheitelpunkt wirkt. ** Die Abstoßungskraft wird durch Abtasten mit der Verteilung $ P $ ** berechnet.
Verschieben Sie die Eckpunkte basierend auf der in 1 berechneten Kraft. Die Größe der Bewegungsverschiebung ist kleiner oder gleich dem Temperaturparameter $ t $
Verringern Sie den Temperaturparameter
Wiederholen Sie die Schritte 1 bis 3 einige Male

Ich weiß nicht, ob Konvergenz garantiert ist, aber empirisch scheint sie richtig zu konvergieren.

Unterscheidet sich dieses Verständnis völlig vom ursprünglichen Ablauf? ??

"UMAPs Artikel ist ursprünglich wahnsinnig mathematisch, aber gibt es jetzt eine Erklärung?"

"In welcher Beziehung stehen Sie zur Fuzzy-Topologie und zur Lehman-Sorte?"

Schreiben Sie für diejenigen, die denken, die Relevanz für den ursprünglichen Ablauf. Dazu müssen wir zuerst den ursprünglichen mathematischen Ablauf kennen ...

Ursprünglicher UMAP-Fluss

Diejenigen, die Kenntnisse der Mathematik haben, sollten diesen Fluss verstehen.

Formulierung
Ableitung der Kostenfunktion
Minimieren Sie die Kostenfunktion und binden Sie sie in eine niedrigere Dimension ein

Werfen wir einen kurzen Blick auf jeden einzelnen.

1. Formulierung

Um einen Überblick zu erhalten, zitiere ich einen Teil aus [Qiita liest UMAP-Papiere] und [Qiita liest UMAP-Papiere].

Die folgenden Konzepte werden in UMAP eingeführt. (Hallo)

fuzzy set --Fuzzy-Set

simplicial set --Verbindung

fuzzy simplicial set

Kombination von 1 und 2

FinReal

Konvertieren Sie eine einzelne Einheit in EPMet

FinSing

Konvertieren Sie EPMet in einen unscharfen einfachen Satz

Definieren Sie die Operation zum Transformieren der Punktsequenz in einen topologischen Fuzzy-Ausdruck.

Zunächst wurde in Kapitel 1 beschrieben, wie die Lehman-Sorte aus einer Folge von Datenpunkten geschätzt wird. Ich habe jedoch nicht wirklich die Form der Diversität selbst geschätzt, sondern den Abstand über den endlichen Raum (FinEPMet).

In Kapitel 3 haben wir eine Fuzzy-Simplicial-Menge definiert, die wie eine Fuzzy-Verbindung aussieht, und eine Operation namens FinSing definiert, um ein FinEPMet in eine Fuzzy-Simplicial-Menge zu konvertieren.

Ich weiß nicht, ob ich es nur zitiere, aber ich denke, es liegt wahrscheinlich daran, dass der Mathematiker es sagt (aufgegebenes Verständnis). Wenn Sie mehr über diesen Bereich erfahren möchten, ist der folgende Artikel hilfreich. Wenn Sie mit Englisch vertraut sind, ist das Lesen der Zeitung korrekt.

[Lesen von UMAP-Papieren Qiita] [Lesen von UMAP-Papieren Qiita]
[UMAP-Kommentarartikel] Artikel nach UMAP-Formel

2. Ableitung der Kostenfunktion

Die Kreuzentropie der beiden topologischen Fuzzy-Ausdrücke ist wie folgt definiert.

C((A, \mu), (A, \nu)) \rightarrow \sum_{a \in A}{( \mu(a)\log(\nu(a)) + (1 - \mu(a)) \log(1-\nu(a)) )}

$ \ mu, \ nu $: Mitgliedschaftsfunktion (Zugehörigkeitsgrad zu $ \ mu: A \ rightarrow [0, 1] $, $ A $) A：Fuzzy topological expression

Der Grund, warum es nicht gleich ist, ist, dass die rechte Seite die Formel ist, nachdem der Teil weggelassen wurde, der nicht mit der Minimierung zusammenhängt. (Einzelheiten finden Sie im Papier.)

3. Minimieren Sie die Kostenfunktion und binden Sie sie in eine niedrigere Dimension ein

Konvertieren Sie hochdimensionale Daten in den unscharfen topologischen Ausdruck $ X $
Konvertieren Sie niedrigdimensionale Daten (Einbettungsziel) ebenfalls in den unscharfen topologischen Ausdruck $ Y $

Die niedrigdimensionalen Daten $ Y $ werden gemäß der Gradientenmethode geändert, so dass die Kreuzentropie zwischen den topologischen Fuzzy-Ausdrücken minimiert wird. Das auf diese Weise erstellte $ Y $ ist das Visualisierungsergebnis oder das Ergebnis der Dimensionsreduzierung.

Um es so grob zusammenzufassen:

** Es gibt eine Kostenfunktion, die von einem Mathematiker abgeleitet wurde. ** ** ** ** Minimieren Sie dies für mathematisch fundierte niedrigdimensionale Einbettungen. ** ** **

Verbindung mit dem bisherigen technischen Verständnis

"Was war die Erklärung des k-Nachbarschaftsgraphen und des dynamischen Modells früher !?" Tut mir leid, dass ich dich habe warten lassen. ** Die Definition der Anziehungs- / Abstoßungskraft im dynamischen Modell ist mit der Kostenfunktion verknüpft **.

Die Kostenfunktion könnte wie folgt geschrieben werden.

C((A, \mu), (A, \nu)) \rightarrow \sum_{a \in A}{( \mu(a)\log(\nu(a)) + (1 - \mu(a)) \log(1-\nu(a)) )}

$ \ mu, \ nu $: Mitgliedschaftsfunktion (Zugehörigkeitsgrad zu $ \ mu: A \ rightarrow [0, 1] $, $ A $) A：Fuzzy topological expression

Wenn Sie sich die Gleichung genau ansehen, können Sie die Beziehung zum dynamischen Modell erkennen. Da $ \ mu $ eine Zugehörigkeitsfunktion für höherdimensionale Daten ist, gehört $ \ mu (a) $ zu $ A $ und $ (1- \ mu (a)) $ zu $ A $. Abschluss nicht. Das heißt, der erste Term von $ \ sum $ kann als ein Term angesehen werden, der auf die Nachbarschaft wirkt, und der zweite Term kann als ein Term angesehen werden, der auf andere als die Nachbarschaft wirkt.

Die ** Anziehungskraft und die Abstoßungskraft, die zuvor erwähnt wurden, werden aus der Kostenfunktion ** zurückgerechnet (obwohl in der Veröffentlichung nicht angegeben, wird der der Abstoßungskraft entsprechende Begriff nach Ableitung der Kostenfunktion auch mit der bestehenden Methode LargeVis durch negative Abtastung effizient abgetastet. Ist berechnet).

Schließlich sind mathematische Kenntnisse erforderlich, um der Definition von Anziehung / Abstoßung auf den Grund zu gehen. Ich bin jedoch der Meinung, dass das Verständnis von "Erstellen eines Diagramms und Einbetten gemäß der Kraft" dem Verständnis von "Minimieren der Kostenfunktion, die nicht gut verstanden wird" einen Schritt voraus ist.

Schließlich

Es ist interessant, dass das mathematisch schwierige UMAP mit einem einfachen (wenn auch etwas technischen) mechanischen Modell formuliert werden kann. Dies ist das maximale Verständnis für jemanden (I), der keinen mathematischen Hintergrund hat. Es gibt einige Teile, die ich nicht verstehe, daher wäre es hilfreich, wenn Sie auf die Fehler hinweisen könnten, indem Sie auf das Papier schlagen, ohne diesen Artikel als selbstverständlich zu betrachten.

Verweise

[UMAP: UniformManifold ApproximationandProjectionfor DimensionReduction, arXiv] [UMAP Paper] : Hier ist alles

[Lesen von UMAP-Papieren Qiita] [Lesen von UMAP-Papieren Qiita]
[UMAP-Kommentarartikel] Artikel nach UMAP-Formel : Diese beiden Artikel versuchen, mathematische Formeln zu verstehen

Understanding UMAP : Es gibt reichlich Zahlen und es ist leicht zu verstehen. Es ist interessant, es sich nur anzusehen, also schauen Sie es sich bitte an.

[UMAP-Dokument] [UMAP-Dokument]
HowToUseUMAP : Wenn Sie es als Werkzeug verwenden möchten, klicken Sie hier

[Dimensionsreduzierung mit t-SNE (Rtsne) und UMAP (uwot) unter Verwendung von R-Paketen.] Von tSNE zu UMAP (erprobtes System) : Verschaffen Sie sich einen Überblick über t-SNE und UMAP. Praktisch> Theorie

[Algorithmus zum Zeichnen von Grafiken und hinter den Kulissen von Networkx] Dynamisches Qiita-Modell : Erklärung typischer dynamischer Modellalgorithmen. (Mein Artikel)

[Vorne der ungefähren Suche nach dem nächsten Nachbarn] [Ungefähre knn] : Räumliche Aufteilung nach Baum, Hashing, wobei die Hypothese, dass "in der Nähe auch in der Nähe ist", interessant ist

Sie können Ihr Verständnis vertiefen, indem Sie die folgenden Artikel lesen.

[Barns-Hut-SNE] [Barns-Hut-SNE-Papier]
[(t-SNE) Visualisierung von Daten mit t-SNE] t-SNE-Papier
[(LargeVis) Visualisierung großer und hochdimensionaler Daten] LargeVis Paper
(fruchterman-reingold algorithm) Graph drawing by force‐directed placement

[PYTHON] Ich möchte UMAP (Engineering) stärker verstehen als t-SNE