Wie kann man beweisen, dass die vielfältige Annahme richtig ist?

9

Beim maschinellen Lernen wird häufig angenommen, dass ein Datensatz auf einer glatten niedrigdimensionalen Mannigfaltigkeit liegt (die Mannigfaltigkeitsannahme), aber gibt es eine Möglichkeit zu beweisen, dass unter der Annahme, dass bestimmte Bedingungen erfüllt sind, der Datensatz tatsächlich (ungefähr) erzeugt wird von einem niedrigdimensionalen glatten Verteiler?

Zum Beispiel gegeben eine Datensequenz wobei X iR d (sagen wir die Sequenz von Gesichtsbildern mit unterschiedlichen Winkeln) und eine entsprechende Beschriftungssequenz { y 1Y n } wobei y 1y 2y n (sagen Sie die Winkel der Gesichtsfolge). Angenommen, wenn X i und X i + 1 sehr nahe beieinander liegen, sind ihre Bezeichnungen y i und y i + 1{X1Xn}XiRd{y1yn}y1y2ynXiXi+1yiyi+1sind auch sehr nah, wir können uns vorstellen, dass es wahrscheinlich ist, dass auf einer niedrigdimensionalen Mannigfaltigkeit liegt. Ist das wahr? Wenn ja, wie können wir das beweisen? Oder welche Bedingungen muss die Sequenz erfüllen, damit die vielfältige Annahme als wahr nachgewiesen werden kann?{X1Xn}

Denkbär
quelle

Antworten:

10

Wenn man sich viele Berichte über die "vielfältige Annahme" ansieht, wird schnell klar, dass viele Schriftsteller in Bezug auf ihre Bedeutung besonders schlampig sind. Die vorsichtigeren definieren es mit einer subtilen, aber äußerst wichtigen Einschränkung : dass die Daten auf oder in der Nähe einer niedrigdimensionalen Mannigfaltigkeit liegen.

Selbst diejenigen, die die "oder nahe" -Klausel nicht enthalten, nehmen die Mannigfaltigkeitsannahme eindeutig als ungefähre Fiktion an, die für die Durchführung mathematischer Analysen geeignet ist , da ihre Anwendungen Abweichungen zwischen den Daten und der geschätzten Mannigfaltigkeit berücksichtigen müssen . In der Tat führen viele Autoren später einen expliziten Mechanismus für Abweichungen ein, beispielsweise die Betrachtung der Regression von gegen x, wobei x gezwungen ist, auf einer Mannigfaltigkeit M kR d zu liegen , das y jedoch zufällige Abweichungen enthalten kann. Dies entspricht der Annahme, dass die Tupel ( x i ,yxxMkRd y nahean einer eingetauchten k- dimensionalen Mannigfaltigkeit der Formliegen, aber nicht unbedingt darauf(xi,yi)k

(x,f(x))Mk×RRd×RRd+1

für einige glatt (Regression) Funktion . Da wir sehen können alle gestörten Punkte ( x , y ) = ( x , f ( x ) + ε ) , die lediglich sind nahe an dem Graphen von f (a k dimensionalen Mannigfaltigkeit) als liegend auf dem k + 1 -dimensionalen Verteiler M k × R.f:RdR(x,y)=(x,f(x)+ε)fkk+1Mk×RDies erklärt, warum eine solche Schlamperei bei der Unterscheidung zwischen "Ein" und "Nah" theoretisch unwichtig sein kann.

Der Unterschied zwischen "Ein" und "Nah an" ist für Anwendungen von enormer Bedeutung. "Nah an" ermöglicht, dass die Daten vom Verteiler abweichen können. Wenn Sie diesen Verteiler schätzen, kann der typische Betrag der Abweichung zwischen den Daten und dem Verteiler quantifiziert werden. Ein angepasster Verteiler ist besser als ein anderer, wenn die typische Abweichung geringer ist, ceteris paribus.

Zahl

Die Abbildung zeigt zwei Versionen der Verteilerannahme für die Daten (große blaue Punkte): Der schwarze Verteiler ist relativ einfach (zur Beschreibung sind nur vier Parameter erforderlich), kommt jedoch den Daten nur "nahe", während der rot gepunktete Verteiler zu den Daten passt perfekt, aber kompliziert (17 Parameter werden benötigt).

Rd

Dies führt zu einer einfachen und praktischen Methode zur Bewertung der Mannigfaltigkeitsannahme: Wenn das aus der Mannigfaltigkeitsannahme entwickelte Modell / Prädiktor / Klassifikator akzeptabel gut funktioniert, war die Annahme gerechtfertigt. Die in der Frage angestrebten geeigneten Bedingungen werden daher sein, dass ein relevantes Maß für die Anpassungsgüte akzeptabel klein ist. (Welche Maßnahme? Sie hängt vom Problem ab und ist gleichbedeutend mit der Auswahl einer Verlustfunktion.)

Es ist möglich, dass Verteiler unterschiedlicher Dimension (mit unterschiedlichen Einschränkungen ihrer Krümmung) gleichermaßen gut zu den Daten passen - und durchgehaltene Daten vorhersagen. Über "die zugrunde liegende" Mannigfaltigkeit kann im Allgemeinen nichts "bewiesen" werden , insbesondere wenn mit großen, unordentlichen menschlichen Datensätzen gearbeitet wird. Wir können normalerweise nur hoffen, dass der eingebaute Verteiler ein gutes Modell ist.

Wenn Sie kein gutes Modell / Prädiktor / Klassifikator finden, ist entweder die Mannigfaltigkeitsannahme ungültig, Sie nehmen Mannigfaltigkeiten mit einer zu kleinen Dimension an oder Sie haben nicht genau genug oder nicht gut genug ausgesehen.

whuber
quelle
1
+1 Sehr schön. Lassen Sie mich hinzufügen (ohne zu implizieren, dass Sie meine Ansicht teilen), dass dies noch einmal zeigt, warum die prinzipielle, aber skeptische und oft vorläufige Denkweise, die über viele Jahre in der Statistik gepflegt wurde, für die oft vagen, schnellen, glänzenden Neuheiten sehr wichtig ist. Spielzeugwelt des maschinellen Lernens und der Datenwissenschaft.
Momo
5

Jede endliche Menge von Punkten kann auf jede Mannigfaltigkeit passen (Satzreferenz benötigt, ich kann mich nicht erinnern, was der Satz ist, ich erinnere mich nur an diese Tatsache von uni).

Wenn nicht alle Punkte identifiziert werden sollen, ist die niedrigstmögliche Dimension 1.

Nehmen wir als einfaches Beispiel, wenn N 2d Punkte gegeben sind, gibt es ein Polynom N - 1 Ordnung, bei dem alle N Punkte auf diesem Polynom liegen. Daher haben wir einen 1d-Verteiler für jeden 2d-Datensatz. Ich denke, die Logik für beliebige Dimensionen ist ähnlich.

Das ist also nicht das Problem, die wirklichen Annahmen beziehen sich auf die Struktur / Einfachheit der Mannigfaltigkeit, insbesondere wenn verbundene Riemannsche Mannigfaltigkeiten als metrische Räume behandelt werden. Ich habe Artikel über diesen vielfältigen Hokuspokus gelesen und festgestellt, dass beim sorgfältigen Lesen einige ziemlich große Annahmen auftauchen!

Die getroffenen Annahmen sind, wenn angenommen wird, dass die induzierte Definition von "Nähe" "die Informationen in unserem Datensatz bewahrt", aber da dies in informationstheoretischen Begriffen nicht formal definiert ist, ist die resultierende Definition ziemlich ad hoc und in der Tat eine ziemlich große Annahme. Insbesondere scheint das Problem zu sein, dass "Nähe" erhalten bleibt, dh zwei nahe Punkte, bleiben nahe, aber "Ferne" nicht, und so bleiben zwei "ferne" Punkte nicht weit.

Zusammenfassend wäre ich sehr vorsichtig mit solchen Tricks beim maschinellen Lernen, es sei denn, es ist bekannt, dass der Datensatz tatsächlich von Natur aus euklidisch ist, z. B. visuelle Mustererkennung. Ich würde diese Ansätze für allgemeinere Probleme nicht für angemessen halten.

samthebest
quelle
Vielen Dank! Ihre Antwort hat mir geholfen, das Problem besser zu verstehen. Könnten Sie einige der Papiere bezüglich der vielfältigen Annahme empfehlen, die Sie hier erwähnt haben?
Thinkbear
Entschuldigung, ich kann mich nicht erinnern, Google sollte helfen können :)
Samthebest