Was ist der Fluch der Dimensionalität?

21

Konkret suche ich Referenzen (Papiere, Bücher), die den Fluch der Dimensionalität konsequent aufzeigen und erklären. Diese Frage stellte sich, nachdem ich dieses Whitepaper von Lafferty und Wasserman gelesen hatte . Im dritten Absatz erwähnen sie eine "bekannte" Gleichung, die impliziert, dass die beste Konvergenzrate ; Wenn jemand darauf eingehen kann (und es erklären kann), wäre das sehr hilfreich. $n^{-4/(4-d)}$

Kann mich auch jemand auf eine Referenz hinweisen, die die "bekannte" Gleichung herleitet?

theory khoda
quelle

7

Ich kann es nicht erklären, aber ich glaube, ich habe gehört, wie drei verschiedene Versionen des Fluchs klingen: 1) Höhere Dimensionen bedeuten eine exponentiell zunehmende Menge an Arbeit, und 2) in höheren Dimensionen werden Sie in jedem Teil immer weniger Beispiele erhalten 3) In großen Dimensionen ist alles in der Regel gleich weit voneinander entfernt, sodass es schwierig ist, Unterschiede zu machen.

Wayne

5

Sie könnten dies geometrisch interpretieren. Angenommen, Sie haben eine Kugel in D-Dimensionen mit dem Radius r = 1. Sie können dann die Frage stellen, welcher Anteil des Kugelvolumens zwischen dem Radius r = 1 und r = 1-e liegt. Da wir wissen, dass das Volumen einer Kugel wie k (d) · r ^ (d) skaliert, wobei d die Anzahl der Dimensionen ist, können wir ableiten, dass der Bruch durch 1- (1-e) ^ d gegeben ist. Daher ist bei hochdimensionalen Kugeln der größte Teil des Volumens in einer dünnen Schale nahe der Oberfläche konzentriert. Weitere Informationen hierzu finden Sie im Bischofsbuch "Mustererkennung und maschinelles Lernen".

Dr. Mike

@ Wayne Sure; plus 5) mehr Dimmen bedeuten normalerweise mehr Lärm.

Dr. Mike, ich folge nicht der Logik. Es hört sich so an, als würden Sie sagen: "Da der größte Teil des Volumens in einer dünnen Schale nahe der Oberfläche einer hochdimensionalen Kugel konzentriert ist, sind Sie mit Dimensionalität verflucht." Können Sie mir näher erläutern und mir vielleicht explizit zeigen, wie die Analogie mit der Statistik zusammenhängt?

Khoda

9

Im Anschluss an Richiemorrisroe ist hier das relevante Bild aus den Elementen des statistischen Lernens , Kapitel 2 (S. 22-27):

ESL Seite 25

Wie Sie im oberen rechten Bereich sehen können, gibt es in einer Dimension mehr Nachbarn, die 1 Einheit entfernt sind, als in zwei Dimensionen Nachbarn, die 1 Einheit entfernt sind. 3 Dimensionen wären noch schlimmer!

Zach
quelle

7

Dies beantwortet Ihre Frage nicht direkt, aber David Donoho hat einen schönen Artikel über hochdimensionale Datenanalyse: Die Flüche und Segnungen der Dimensionalität (die dazugehörigen Folien sind hier ), in dem er drei Flüche erwähnt:

$D$ $(1/\epsilon)^D$ $\epsilon$
$d$ $(1/\epsilon)^D$ $\epsilon$
$D$ $(1/\epsilon)^D$ $\epsilon$

raegtin
quelle

6

Ich weiß, dass ich mich immer wieder darauf beziehe, aber es gibt eine großartige Erklärung dafür: Die Elemente des statistischen Lernens , Kapitel 2 (S. 22-27). Sie stellen im Grunde fest, dass mit zunehmenden Dimensionen die Datenmenge (exponentiell) zunehmen muss, da sonst im größeren Probenraum nicht genügend Punkte vorhanden sind, um eine sinnvolle Analyse durchzuführen.

Sie beziehen sich auf eine Veröffentlichung von Bellman (1961) als Quelle, die sein Buch Adaptive Control Processes zu sein scheint, das hier bei Amazon erhältlich ist

richiemorrisroe
quelle

+1. Die Erklärung in ESL ist großartig und die zugehörigen Diagramme helfen sehr.

Zach

2

Bildbeschreibung hier eingeben

Die vielleicht berüchtigtste Auswirkung wird durch die folgende Grenze erfasst (die (indirekt) im obigen Bild dargestellt ist):

lim_{d ich m \to \infty} \frac{d ich s t_{m ein x} - d ich s t_{m ich n}}{d ich s t_{m ich n}}

$\lim_{dim\rightarrow\infty}\frac{dist_{max}-dist_{min}}{dist_{min}}$

$L_2$ $k$ $L_k$

Einfluss der Dimensionalität auf Daten in Bildern

Raffael
quelle

Was ist der Fluch der Dimensionalität?

Antworten: