t-verteilte stochastische Nachbareinbettung – Wikipedia

Technik zur Dimensionsreduktion

t-verteilte stochastische Nachbareinbettung ((t-SNE) ist ein Algorithmus für maschinelles Lernen zur Visualisierung basierend auf Stochastic Neighbor Embedding, der ursprünglich von Sam Roweis und Geoffrey Hinton entwickelt wurde.^[1] wo Laurens van der Maaten das vorschlug t-verteilte Variante.^[2] Es handelt sich um eine nichtlineare Technik zur Reduzierung der Dimensionalität, die sich gut zum Einbetten hochdimensionaler Daten zur Visualisierung in einen niedrigdimensionalen Raum mit zwei oder drei Dimensionen eignet. Insbesondere wird jedes hochdimensionale Objekt durch einen zwei- oder dreidimensionalen Punkt so modelliert, dass ähnliche Objekte durch nahegelegene Punkte und unterschiedliche Objekte mit hoher Wahrscheinlichkeit durch entfernte Punkte modelliert werden.

Der t-SNE-Algorithmus umfasst zwei Hauptstufen. Zunächst konstruiert t-SNE eine Wahrscheinlichkeitsverteilung über Paare hochdimensionaler Objekte, so dass ähnlichen Objekten eine höhere Wahrscheinlichkeit zugewiesen wird, während unterschiedlichen Punkten eine niedrigere Wahrscheinlichkeit zugewiesen wird. Zweitens definiert t-SNE eine ähnliche Wahrscheinlichkeitsverteilung über die Punkte in der niedrigdimensionalen Karte und minimiert die Kullback-Leibler-Divergenz (KL-Divergenz) zwischen den beiden Verteilungen in Bezug auf die Positionen der Punkte in der Karte. Während der ursprüngliche Algorithmus den euklidischen Abstand zwischen Objekten als Grundlage für seine Ähnlichkeitsmetrik verwendet, kann dieser entsprechend geändert werden.

t-SNE wurde zur Visualisierung in einer Vielzahl von Anwendungen verwendet, einschließlich der Computersicherheitsforschung.^[3]Musikanalyse,^[4]Krebsforschung,^[5]Bioinformatik,^[6] und biomedizinische Signalverarbeitung.^[7] Es wird häufig verwendet, um Darstellungen auf hoher Ebene zu visualisieren, die von einem künstlichen neuronalen Netzwerk gelernt wurden.^[8]

Während t-SNE-Diagramme häufig Cluster anzuzeigen scheinen, können die visuellen Cluster stark durch die gewählte Parametrisierung beeinflusst werden. Daher ist ein gutes Verständnis der Parameter für t-SNE erforderlich. Es kann gezeigt werden, dass solche “Cluster” sogar in nicht geclusterten Daten erscheinen.^[9] und kann daher falsche Befunde sein. Eine interaktive Exploration kann daher erforderlich sein, um Parameter auszuwählen und Ergebnisse zu validieren.^[10][11] Es wurde gezeigt, dass t-SNE häufig gut getrennte Cluster wiederherstellen kann und mit speziellen Parameteroptionen eine einfache Form der spektralen Clusterbildung annähert.^[12]

Einzelheiten[edit]

Gegeben eine Reihe von

${ displaystyle N}$

hochdimensionale Objekte

${ displaystyle mathbf {x} _ {1}, dots, mathbf {x} _ {N}}$

, t-SNE berechnet zuerst Wahrscheinlichkeiten

${ displaystyle p_ {ij}}$

das ist proportional zur Ähnlichkeit von Objekten

${ displaystyle mathbf {x} _ {i}}$

und

${ displaystyle mathbf {x} _ {j}}$

, wie folgt.

Zum

${ displaystyle i neq j}$

, definieren

${ displaystyle p_ {j mid i} = { frac { exp (- lVert mathbf {x} _ {i} – mathbf {x} _ {j} rVert ^ {2} / 2 sigma _ {i} ^ {2})} { sum _ {k neq i} exp (- lVert mathbf {x} _ {i} – mathbf {x} _ {k} rVert ^ {2 } / 2 sigma _ {i} ^ {2})}}}$

und setzen

${ displaystyle p_ {i mid i} = 0}$

. Beachten Sie, dass

${ displaystyle sum _ {j} p_ {j mid i} = 1}$

für alle

${ displaystyle i}$

.

Wie Van der Maaten und Hinton erklärten: “Die Ähnlichkeit des Datenpunkts

${ displaystyle x_ {j}}$

zum Datenpunkt

${ displaystyle x_ {i}}$

ist die bedingte Wahrscheinlichkeit,

${ displaystyle p_ {j | i}}$

, Das

${ displaystyle x_ {i}}$

würde wählen

${ displaystyle x_ {j}}$

als sein Nachbar, wenn Nachbarn proportional zu ihrer Wahrscheinlichkeitsdichte unter einem Gaußschen zentriert bei ausgewählt wurden

${ displaystyle x_ {i}}$

. “^[2]

Nun definieren

${ displaystyle p_ {ij} = { frac {p_ {j mid i} + p_ {i mid j}} {2N}}}$

und beachte das

${ displaystyle p_ {ij} = p_ {ji}}$

,

${ displaystyle p_ {ii} = 0}$

, und

${ displaystyle sum _ {i, j} p_ {ij} = 1}$

.

Die Bandbreite der Gaußschen Kernel

${ displaystyle sigma _ {i}}$

wird so eingestellt, dass die Ratlosigkeit der bedingten Verteilung einer vordefinierten Ratlosigkeit unter Verwendung der Halbierungsmethode entspricht. Infolgedessen wird die Bandbreite an die Dichte der Daten angepasst: kleinere Werte von

${ displaystyle sigma _ {i}}$

werden in dichteren Teilen des Datenraums verwendet.

Da der Gaußsche Kern den euklidischen Abstand verwendet

${ displaystyle lVert x_ {i} -x_ {j} rVert}$

wird es durch den Fluch der Dimensionalität beeinflusst, und in hochdimensionalen Daten, wenn Entfernungen die Fähigkeit zur Unterscheidung verlieren, die

${ displaystyle p_ {ij}}$

zu ähnlich werden (asymptotisch würden sie zu einer Konstanten konvergieren). Es wurde vorgeschlagen, die Abstände mit einer Leistungstransformation basierend auf der intrinsischen Dimension jedes Punkts anzupassen, um dies zu mildern.^[13]

t-SNE zielt darauf ab, a zu lernen

${ displaystyle d}$

-dimensionale Karte

${ displaystyle mathbf {y} _ {1}, dots, mathbf {y} _ {N}}$

(mit

${ displaystyle mathbf {y} _ {i} in mathbb {R} ^ {d}}$

), die die Ähnlichkeiten widerspiegeln

${ displaystyle p_ {ij}}$

so gut wie möglich. Zu diesem Zweck werden Ähnlichkeiten gemessen

${ displaystyle q_ {ij}}$

zwischen zwei Punkten in der Karte

${ displaystyle mathbf {y} _ {i}}$

und

${ displaystyle mathbf {y} _ {j}}$

mit einem sehr ähnlichen Ansatz. Speziell für

${ displaystyle i neq j}$

, definieren

${ displaystyle q_ {ij}}$

wie

${ displaystyle q_ {ij} = { frac {(1+ lVert mathbf {y} _ {i} – mathbf {y} _ {j} rVert ^ {2}) ^ {- 1}} { sum _ {k} sum _ {l neq k} (1+ lVert mathbf {y} _ {k} – mathbf {y} _ {l} rVert ^ {2}) ^ {- 1 }}}}$

und setzen

${ displaystyle q_ {ii} = 0}$

. Hier wird eine schwerfällige Student-T-Verteilung (mit einem Freiheitsgrad, der einer Cauchy-Verteilung entspricht) verwendet, um Ähnlichkeiten zwischen niedrigdimensionalen Punkten zu messen, damit unterschiedliche Objekte in der Karte weit auseinander modelliert werden können .

Die Positionen der Punkte

${ displaystyle mathbf {y} _ {i}}$

in der Karte werden durch Minimierung der (nicht symmetrischen) Kullback-Leibler-Divergenz der Verteilung bestimmt

${ displaystyle P}$

aus der Verteilung

${ displaystyle Q}$

, das ist:

${ displaystyle mathrm {KL} left (P parallel Q right) = sum _ {i neq j} p_ {ij} log { frac {p_ {ij}} {q_ {ij}}} }}$

Die Minimierung der Kullback-Leibler-Divergenz in Bezug auf die Punkte

${ displaystyle mathbf {y} _ {i}}$

wird mit Gradientenabstieg durchgeführt. Das Ergebnis dieser Optimierung ist eine Karte, die die Ähnlichkeiten zwischen den hochdimensionalen Eingaben widerspiegelt.

Software[edit]

• ELKI enthält tSNE, ebenfalls mit Barnes-Hut-Näherung
• Scikit-learn, ein beliebtes Toolkit für maschinelles Lernen in Python, implementiert t-SNE sowohl mit exakten Lösungen als auch mit der Barnes-Hut-Näherung.

Verweise[edit]

Externe Links[edit]