Dimensionalität und Mannigfaltigkeit

13

Ein häufig gehörter Satz beim unbeaufsichtigten maschinellen Lernen ist

Hochdimensionale Eingaben leben typischerweise auf oder in der Nähe eines niedrigdimensionalen Verteilers

Was ist eine Dimension? Was ist eine Mannigfaltigkeit? Was ist der Unterschied?

Können Sie ein Beispiel geben, um beide zu beschreiben?

Mannigfaltigkeit aus Wikipedia:

In der Mathematik ist eine Mannigfaltigkeit ein topologischer Raum, der dem euklidischen Raum in der Nähe jedes Punktes ähnelt. Genauer gesagt hat jeder Punkt einer n-dimensionalen Mannigfaltigkeit eine Nachbarschaft, die homöomorph zum euklidischen Raum der Dimension n ist.

Dimension aus Wikipedia:

In der Physik und Mathematik wird die Dimension eines mathematischen Raums (oder Objekts) informell als die Mindestanzahl von Koordinaten definiert, die erforderlich sind, um einen Punkt darin anzugeben.

Was bedeutet die Wikipedia überhaupt für Laien? Es klingt wie eine bizarre Definition wie die meisten Definitionen für maschinelles Lernen?

Sie sind beide Räume. Was ist also der Unterschied zwischen einem euklidischen Raum (dh einer Mannigfaltigkeit) und einem Dimensionsraum (dh merkmalsbasiert)?

Alvas
quelle
1
Haben Sie versucht, im Internet zu suchen? Das sollte genug sein.
Aleksandr Blekh
1
Ja, ich hatte Google, aber das ist sicherlich nicht genug, siehe die aktualisierte Frage.
Alvas
1
Ich bin mir nicht sicher, ob es eine so gute Idee ist, komplexe maschinelle Lernkonzepte "in Laienbegriffen" zu erklären. Außerdem sollten Sie Ihre Suche über Wikipedia hinaus erweitern.
Aleksandr Blekh

Antworten:

29

Was ist eine Dimension?

Um es einfach auszudrücken: Wenn Sie einen tabellarischen Datensatz mit m Zeilen und n Spalten haben, ist die Dimensionalität Ihrer Daten n:

Was ist eine Mannigfaltigkeit?

Das einfachste Beispiel ist unser Planet Erde. Für uns sieht es flach aus, aber es ist wirklich eine Kugel. Es ist also eine Art 2D-Mannigfaltigkeit, die in den 3D-Raum eingebettet ist.

Was ist der Unterschied?

Um diese Frage zu beantworten, betrachten Sie ein anderes Beispiel einer Mannigfaltigkeit:

Geben Sie hier die Bildbeschreibung ein

Dies ist die sogenannte "Schweizer Rolle". Die Datenpunkte befinden sich in 3d, aber sie liegen alle auf dem 2d-Verteiler, sodass die Dimensionalität des Verteilers 2 beträgt, während die Dimensionalität des Eingaberaums 3 beträgt.

Es gibt viele Techniken, um diese Verteiler "auszupacken". Eine davon heißt Local Linear Embedding , und so würde es das machen:

Geben Sie hier die Bildbeschreibung ein

Hier ist ein Scikit-Lernausschnitt dafür:

from sklearn.manifold import LocallyLinearEmbedding

lle = LocallyLinearEmbedding(n_neighbors=k, n_components=2)
X_lle = lle.fit_transform(data)
plt.scatter(X_lle[:, 0], X_lle[:, 1], c=color)
plt.show()
Alexey Grigorev
quelle
6

Die Dimensionalität eines Datensatzes ist die Anzahl der Variablen, mit denen er dargestellt wird. Wenn wir beispielsweise daran interessiert wären, Personen in Bezug auf Größe und Gewicht zu beschreiben, hätte unser Datensatz "Personen" zwei Dimensionen. Wenn wir stattdessen einen Datensatz mit Bildern hätten und jedes Bild eine Million Pixel groß wäre, wäre die Dimensionalität des Datensatzes eine Million. Tatsächlich kann in vielen modernen Anwendungen für maschinelles Lernen die Dimensionalität eines Datensatzes massiv sein.

Wenn die Dimensionalität sehr groß ist (größer als die Anzahl der Proben im Datensatz), können schwerwiegende Probleme auftreten. Stellen Sie sich einen einfachen Klassifizierungsalgorithmus vor, der versucht, einen Satz von Gewichten w zu finden, der, wenn er mit einer Stichprobe x gepunktet wird, eine negative Zahl für eine Klasse und eine positive Zahl für eine andere ergibt. w hat eine Länge, die der Dimensionalität der Daten entspricht, sodass mehr Parameter vorhanden sind, als Stichproben im gesamten Datensatz vorhanden sind. Dies bedeutet, dass ein Lernender in der Lage ist, die Daten zu überarbeiten, und sich daher nicht gut auf andere Proben verallgemeinern lässt, die während des Trainings nicht gesehen wurden.

Eine Mannigfaltigkeit ist ein Objekt der Dimensionalität d, das in einen höherdimensionalen Raum eingebettet ist. Stellen Sie sich eine Reihe von Punkten auf einem Blatt Papier vor. Wenn wir das Papier zerknittern, sind die Punkte jetzt dreidimensional. Viele vielfältige Lernalgorithmen versuchen, das Blatt Papier zu "zerknittern", um die Daten wieder in zwei Dimensionen zu bringen. Selbst wenn wir uns nicht mit der Überanpassung unseres Modells befassen, kann ein nichtlinearer Mannigfaltiger Lernender einen Raum erzeugen, der Klassifizierungs- und Regressionsprobleme erleichtert.

Jordan A.
quelle
Gibt es Fälle, in denen sich eine hohe Dimensionalität nicht zu einer Mannigfaltigkeit löst?
Alvas
Bestimmt! Manchmal liegen Daten bereits in ihrem inneren Raum. In diesem Fall ist der Versuch, die Dimensionalität zu verringern, wahrscheinlich schädlich für die Klassifizierungsleistung. In diesen Fällen sollten Sie feststellen, dass die Funktionen in dem von Ihnen verwendeten Datensatz statistisch weitgehend unabhängig voneinander sind.
Jordanien A
1

Eine Möglichkeit zur Dimensionsreduktion ist das Feature-Hashing. Dies war in den 1960er Jahren bekannt. Wenn Ihre Daten beispielsweise eine spärliche Menge von Punkten in drei Dimensionen (x, y, z) sind, erstellen Sie eine (gute) Hash-Funktion h (x, y, z). Sie können dies natürlich für eine Hash-Tabelle oder eine Bloom-Filter-Suche verwenden. Dies ist eine gute Form der Datenkomprimierung. Ich weiß nicht, warum die KI-Community es nicht benutzt. Es ist viel mehr auf den Punkt als ein neuronales Netz.

SeanOCVN
quelle
1
Wie hängt die Dimensionsreduktion mit der Mannigfaltigkeit zusammen?
Alvas
Es ist eine Möglichkeit, alles auf dem Verteiler herauszusuchen und alles andere auszuschließen.
SeanOCVN
Ich denke, @alvas hat hier einen Punkt. Es ist nicht sofort klar, wie dies mit der ursprünglichen Frage nach einer Erklärung von Mannigfaltigkeiten und Dimensionen zusammenhängt.
Ryan J. Smith
Um das fehlende Glied von SeanOCVNs Antwort und Alvas-Kommentar zu beheben: Eine Mannigfaltigkeit (in einem topologischen Raum) ist die Ausgabe der Ausführung des (oder eines) lokal linearen Einbettungsalgorithmus mit Eingabedaten in einem eingebetteten Raum. Das Ergebnis ist, dass die Eingangsdaten-Dimensionsmenge höher ist als die Ausgangsdaten-Dimensionsmenge. Das Extrahieren einer neuen Datendarstellung (die der ursprünglichen Datendarstellung zugeordnet werden kann) wird als "Merkmalsextraktion" bezeichnet. Dies ist ein Subtyp der "Dimensionsreduktion".
pds
0

@Alexey Grigorev gab bereits eine sehr gute Antwort, aber ich denke, dass es hilfreich sein könnte, zwei Dinge hinzuzufügen:

  • Ich möchte Ihnen ein Beispiel geben, das mir geholfen hat, die Bedeutung der Mannigfaltigkeit intuitiv zu verstehen.
  • Ich möchte darauf näher eingehen und die "Ähnlichkeit mit dem euklidischen Raum" ein wenig erläutern.

Intuitives Beispiel

Stellen Sie sich vor, wir würden an einer Sammlung von (Schwarzweiß-) HDready-Bildern (1280 * 720 Pixel) arbeiten. Diese Bilder leben in einer 921.600 dimensionalen Welt; Jedes Bild wird durch einzelne Pixelwerte definiert.

Stellen Sie sich nun vor, wir würden diese Bilder konstruieren, indem wir jedes Pixel nacheinander ausfüllen, indem wir einen 256-seitigen Würfel rollen.

Das resultierende Bild würde wahrscheinlich ungefähr so ​​aussehen:

Geben Sie hier die Bildbeschreibung ein

Nicht sehr interessant, aber wir könnten das so lange tun, bis wir etwas treffen, das wir behalten möchten. Sehr anstrengend, aber wir könnten dies in ein paar Zeilen Python automatisieren.

Wenn der Raum für aussagekräftige (geschweige denn realistische) Bilder auch nur annähernd so groß wäre wie der gesamte Funktionsraum, würden wir bald etwas Interessantes sehen. Vielleicht würden wir ein Babybild von Ihnen oder einen Nachrichtenartikel aus einer alternativen Zeitleiste sehen. Hey, wie wäre es, wenn wir eine Zeitkomponente hinzufügen, und wir könnten sogar Glück haben und Back to the Future mit einem alternativen Ende generieren

Tatsächlich hatten wir Maschinen, die genau das taten: Alte Fernseher, die nicht richtig eingestellt waren. Jetzt erinnere ich mich, diese gesehen zu haben und habe noch nie etwas gesehen, das überhaupt eine Struktur hatte.

Warum passiert das? Nun: Bilder, die wir interessant finden, sind in der Tat hochauflösende Projektionen von Phänomenen und werden von Dingen gesteuert, die viel weniger hochdimensional sind. Zum Beispiel: Die Helligkeit der Szene, die einem eindimensionalen Phänomen nahe kommt, dominiert in diesem Fall fast eine Million Dimensionen.

Dies bedeutet, dass es einen Unterraum (die Mannigfaltigkeit) gibt, in diesem Fall (aber nicht per Definition), der von versteckten Variablen gesteuert wird und die für uns interessanten Instanzen enthält

Lokales euklidisches Verhalten

Euklidisches Verhalten bedeutet, dass Verhalten geometrische Eigenschaften hat. Bei der Helligkeit ist das sehr offensichtlich: Wenn Sie sie entlang der "Achse" erhöhen, werden die resultierenden Bilder kontinuierlich heller.

Aber hier wird es interessant: Dieses euklidische Verhalten wirkt sich auch auf abstraktere Dimensionen in unserem Mannigfaltigkeitsraum aus. Betrachten Sie dieses Beispiel aus Deep Learning von Goodfellow, Bengio und Courville

Links: Die 2D-Karte der Frey-Gesichter ist vielfältig.  Eine entdeckte Dimension (horizontal) entspricht meist einer Rotation des Gesichts, während die andere (vertikal) dem emotionalen Ausdruck entspricht.  Rechts: Die 2D-Karte des MNIST-Verteilers

Links: Die 2D-Karte der Frey-Gesichter ist vielfältig. Eine entdeckte Dimension (horizontal) entspricht meist einer Rotation des Gesichts, während die andere (vertikal) dem emotionalen Ausdruck entspricht. Rechts: Die 2D-Karte des MNIST-Verteilers

Ein Grund, warum Deep Learning bei der Anwendung mit Bildern so erfolgreich ist, liegt darin, dass es eine sehr effiziente Form des vielfältigen Lernens beinhaltet. Dies ist einer der Gründe, warum es für die Bilderkennung und -komprimierung sowie für die Bildmanipulation anwendbar ist.

S van Balen
quelle