Barnes-Hut t-SNE

Das habe ich nicht selbst entwickelt!

Nur damit das klar ist. Aber ich habe eine Java-basierte t-SNE-Implementierung etwas aufgeräumt und benutzbarer gemacht, und die liegt jetzt hier:

Und in der Maven Central:

<dependency>
    <groupId>de.javagl</groupId>
    <artifactId>bh-tsne</artifactId>
    <version>0.0.1</version>
</dependency>

Dabei ist auch eine Demo:

Natürlich, mit dem MNIST-Datensatz :roll_eyes:

Sieht spannend aus, was machen diese Algorithmen genau?

Man kann sich da lange damit beschäftigen, auf unterschiedlichsten technischen Ebenen.

Auf der obersten Ebene ist das „irgendein Dimensionsreduktionsverfahren“ (etwas ungenau: eine Projektion). Das heißt man hat im einfachsten Fall nur das, was eben durch double[][] run(double input[][]) angeboten wird: Man schmeißt einen Array mit „hochdimensionalen“ Punkten rein (z.B. 100-dimensionale Punkte), und bekommt einen Array mit „niedrig(er)dimensionalen“ Punkten (meistens 2D-Punkte, weil man die schön darstellen kann).

Das gleiche gibt’s an sich auch mit PCA, MDS, oder anderen DimRed-Verfahren. Aber t-SNE hat vergleichsweise viel Aufmerksamkeit bekommen, weil es Ausgaben liefert, die in mancher Hinsicht „gut“ sind. Für „gut“ gibt es beliebig ausgefeilte Metriken, da wurden schon etliche Dissertationen drüber erarbeitet, aber stark vereinfacht gesagt: t-SNE bewirkt, dass Punkte, die im hochdimensionalen Raum „nah beieinander“ liegen, auch im niedrigdimensionalen Raum „nah beieinander“ liegen. (Das Verfahren ist in anderer Hinsicht „schlecht“, weil große Abstände nicht notwendigerweise groß bleiben, und es ist hochgradig nichtlinear, aber … das sind die Trade-Offs, die man da halt machen muss…)

Das ganze ist intern etwas stochastisch (dafür steht das S :wink: ) und nicht-deterministisch. Aber am oben gezeigten Screenshot sieht man vielleicht schon, was das bedeutet: Die Eingaben sind 784-dimensionale Punkte - nämlich Bildchen von handschriftlichen Ziffern (oben rechts, bei der Maus, sieht man eine 6). Und diese „Blobs“ die man da sieht sind die 2D-Ergebnisse, eingefärbt nach den Ziffern. Und man sieht, dass die Ziffern von 0 bis 9 recht klar abgegrenzte Grüppchen bilden (quasi „Cluster“ - nicht ganz der richtige Begriff, aber sinngemäß).

Wie das ganze genau intern funktioniert hatte ich mir nur vergleichsweise oberflächlich angesehen. Wie gesagt, da wird viel „random“ initialisiert, und dann läuft in vielen Iterationen etwas, was man sich im weitesten Sinne wie ein „Energieminimierungsverfahren“ oder eine Art „Simulated Annealing“ vorstellen kann: Wenn die Punkte in bezug auf ihre 2D-Neighbors (da haben wir das N) eine Einbettung (E) finden, in der sie sich „wohl“ fühlen, weil die nD-Abstände auch klein sind, ist das gut. Wenn nicht, versuchen sie eine Position zu finden, die besser zu den nD-Abständen passt.

Das scheint mir ein nasser Traum von Big Data und ANN zu sein.

Danke für die Erläuterung! Was ich mir nun unter Bildchen von Ziffern im 784-dimensionalen Raum vorstellen soll, weiß ich nicht, aber ich habe nun eine bessere Vorstellung davon, was hier grob passiert.

Wollte schon fragen, ob ich auch mehr als zwei Dimensionen eingeben kann. :partying_face:

@Marco13 Kann ich auch eine zweidimensionale Eingabe verwenden und eine eindimensionale Ausgabe erlangen? (Also, zum Beispiel einen Buchstaben erkennen)

Und näher betrachtet, fallen mir mehr als drei Dimensionen auch schwer.

Die Bilder sind der MNIST Datensatz, der oft für verschiedene MachineLearning/Classification-Verfahren verwendet wird. Das sind 70000 Bilder von handschriftlichen Ziffern. Grob gesagt geht es beim MNIST meistens darum, irgendwas mit 60000 Bildern zu trainieren, und zwar so, dass bei den übrigen 10000 Bildern die Ziffern möglichst richtig erkannt werden

Die Ziffern sind quasi Bilder mit einer Größe von 28x28 Pixeln, als weiße Schrift auf schwarzen Hintergrund. Jedes Bild sind also 784 Pixel mit Helligkeitswerten zwischen 0 und 255. Man hat also 784 Werte (die man bei sowas meistens auf 0.0…1.0 normalisiert), die das Bild beschreiben - also ein Punkt in einem 784-dimensionalen Raum.

Und wie gesagt: Die t-SNE ist eine allgemeine Dimensionsreduktion. Man könnte eine 40D-Eingabe auf eine 20D-Ausgabe runterrechnen, oder eine 2D-Eingabe auf eine 1D-Ausgabe (auch wenn das nicht viel Sinn ergeben würde). Bei „hohen“ Eingabedimensionen wird vor der eigentlichen t-SNE auch noch eine PCA gemacht, damit die t-SNE dann nicht mit viel mehr als 50 Dimensionen rechnen muss.

EDIT: Der MNIST-Datensatz ist so bekannt, dass ich schon vor einer ganzen Weile das hier erstellt hatte:

Der wird hier aber nicht verwendet: Für Demo habe ich kleinere Teilmengen des Datensatzes erstellt, und als gezippte ARFF-Datei dazugelegt, die mit Weka gelesen wird. Aber das nur nebenbei.

(Edit2: Wobei mir gerade auffällt, dass die README dort noch behauptet, man bräuchte eine APache dependency - die braucht man aber gar nicht … muss ich bei Gelegenheit mal updaten…)

1 Like

Ist run gleichzeitig auch das Training?

Die t-SNE selbst ist nur die „Projektion“/Dimensionsreduktion. Hochdimensional rein. Niedrigdimensional raus. Nix mit Training.

1 Like

Danke für die Erklärungen. Ist auf jeden Fall spannend!