Quelle est la malédiction de la dimensionnalité?

21

Plus précisément, je recherche des références (articles, livres) qui montreront et expliqueront rigoureusement la malédiction de la dimensionnalité. Cette question s'est posée après que j'ai commencé à lire ce livre blanc de Lafferty et Wasserman. Dans le troisième paragraphe, ils mentionnent une équation "bien connue" qui implique que le meilleur taux de convergence est $n^{-4/(4-d)}$ ; si quelqu'un peut en parler (et l'expliquer), ce serait très utile.

De plus, quelqu'un peut-il m'indiquer une référence qui dérive de l'équation "bien connue"?

theory khoda
la source

7

Je ne peux pas exposer, mais je crois avoir entendu ce qui ressemble à trois versions différentes de la malédiction: 1) des dimensions plus élevées signifient une quantité de travail en augmentation exponentielle, et 2) dans des dimensions plus élevées, vous obtiendrez de moins en moins d'exemples dans n'importe quelle partie de votre espace d'échantillonnage, et 3) dans des dimensions élevées, tout a tendance à être fondamentalement équidistant, ce qui rend difficile toute distinction.

Wayne

5

Vous pouvez interpréter cela géométriquement. Disons que vous avez une sphère en dimensions D avec un rayon r = 1. Vous pouvez alors vous demander quelle fraction du volume de la sphère se situe entre le rayon r = 1 et r = 1-e. Puisque nous savons que le volume d'une sphère est comme k (d) * r ^ (d), où d est le nombre de dimensions, nous pouvons déduire que la fraction est donnée par 1- (1-e) ^ d. Ainsi, pour les sphères de grande dimension, la majeure partie du volume est concentrée dans une coquille mince près de la surface. Voir plus à ce sujet dans le livre des évêques "La reconnaissance des modèles et l'apprentissage automatique".

Dr Mike

@Wayne Sure; plus 5) plus de gradations signifient généralement plus de bruit.

Dr Mike, je ne suis pas dans la logique. On dirait que vous dites que "puisque la majeure partie du volume est concentrée dans une mince coquille près de la surface de la sphère de haute dimension, alors vous êtes maudit de dimensionnalité." Pouvez-vous expliquer davantage, et peut-être me montrer explicitement comment l'analogie se rattache aux statistiques?

khoda

9

Dans le prolongement de richiemorrisroe, voici l'image pertinente des Éléments de l'apprentissage statistique , chapitre 2 (pp22-27):

ESL page 25

Comme vous pouvez le voir dans le volet supérieur droit, il y a plus de voisins à 1 unité dans 1 dimension que de voisins à 1 unité dans 2 dimensions. 3 dimensions serait encore pire!

Zach
la source

7

Cela ne répond pas directement à votre question, mais David Donoho a un bel article sur l'analyse des données à haute dimension: les malédictions et les bénédictions de la dimensionnalité (les diapositives associées sont ici ), dans lesquelles il mentionne trois malédictions:

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

raegtin
la source

6

Je sais que je continue à y faire référence, mais il y a une grande explication à cela: les éléments de l'apprentissage statistique , chapitre 2 (pp22-27). Ils notent essentiellement qu'à mesure que les dimensions augmentent, la quantité de données doit augmenter (exponentiellement) avec elle ou il n'y aura pas suffisamment de points dans le plus grand espace d'échantillonnage pour qu'une analyse utile soit effectuée.

Ils se réfèrent à un article de Bellman (1961) comme source, qui semble être son livre Adaptive Control Processes, disponible sur Amazon ici

richiemorrisroe
la source

+1. L'explication en ESL est excellente et les diagrammes associés aident beaucoup.

Zach

2

entrez la description de l'image ici

L'impact le plus notoire est peut-être capturé par la limite suivante (qui est (indirectement) illustrée dans l'image ci-dessus):

lim_{ré je m \to \infty} \frac{ré je s t_{m une X} - ré je s t_{m je n}}{ré je s t_{m je n}}

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

La distance dans l'image est la $L_2$ $k$ $L_k$

Impact de la dimensionnalité sur les données en images

Raffael
la source

Quelle est la malédiction de la dimensionnalité?

Réponses: