¿Qué es la maldición de la dimensionalidad?

Question

En concreto, estoy buscando referencias (artículos, libros) que muestren y expliquen con rigor la maldición de la dimensionalidad. Esta pregunta me surgió después de empezar a leer esto papel blanco por Lafferty y Wasserman. En el tercer párrafo mencionan una ecuación "bien conocida" que implica que la mejor tasa de convergencia es $n^{-4/(4-d)}$ Si alguien puede exponerlo (y explicarlo), sería de gran ayuda.

Además, ¿alguien puede indicarme una referencia que derive la ecuación "conocida"?

Answer 1

Sé que sigo refiriéndome a ello, pero hay una gran explicación de esto es los elementos del aprendizaje estadístico capítulo 2 (pp. 22-27). Básicamente, señalan que, a medida que aumentan las dimensiones, la cantidad de datos tiene que aumentar (exponencialmente) con ellas o no habrá suficientes puntos en el espacio muestral más grande para que se pueda llevar a cabo ningún análisis útil.

Hacen referencia a un documento de Bellman (1961) como su fuente, que parece ser su libro Adaptive Control Processes, disponible en Amazon aquí

Answer 2

Esto no responde directamente a su pregunta, pero David Donoho tiene un buen artículo sobre Análisis de datos de alta dimensión: Las maldiciones y las bendiciones de la dimensionalidad (las diapositivas asociadas son aquí ), en el que menciona tres maldiciones:

• Optimización por búsqueda exhaustiva : "Si debemos optimizar aproximadamente una función de $D$ variables y sólo sabemos que es Lipschitz, digamos, entonces necesitamos el orden $(1/\epsilon)^D$ evaluaciones en una malla para obtener un minimizador aproximado dentro del error $\epsilon$ ."
• Integración en los dominios de los productos : "Si debemos integrar una función de $d$ variables y sólo sabemos que es Lipschitz, digamos, entonces necesitamos el orden $(1/\epsilon)^D$ evaluaciones en una malla para obtener un esquema de integración con error $\epsilon$ ."
• Aproximación en dominios de alta dimensión : "Si debemos aproximar una función de $D$ variables y sólo sabemos que es Lipschitz, digamos, entonces necesitamos el orden $(1/\epsilon)^D$ evaluaciones en una malla para obtener un esquema de aproximación con un error de aproximación uniforme $\epsilon$ ."

Answer 3

Quizá el impacto más notorio lo capte el siguiente límite (que se ilustra (indirectamente) en la imagen anterior):

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

La distancia en la imagen es la $L_2$ -distancia euclidiana. El límite expresa que la noción de distancia capta cada vez menos información sobre la similitud con el aumento de la dimensionalidad. Esto afecta a algoritmos como el k-NN. Al permitir fracciones para $k$ en $L_k$ -se puede modificar la afectación descrita .

---

Impacto de la dimensionalidad en los datos de las imágenes

Answer 4

Siguiendo con richiemorrisroe, aquí está la imagen correspondiente del Elementos de aprendizaje estadístico capítulo 2 (pp. 22-27):

Como puede ver en el panel superior derecho, hay más vecinos a 1 unidad de distancia en 1 dimensión que vecinos a 1 unidad de distancia en 2 dimensiones. En 3 dimensiones sería aún peor.