Maldición de la dimensión

En matemáticas y estadística, la maldición de la dimensión (también conocida como efecto Hughes^[1]) se refiere a los diversos fenómenos que surgen al analizar y organizar datos de espacios de múltiples dimensiones (cientos y miles de dimensiones) que no suceden en el espacio físico descrito generalmente con solo tres dimensiones.

Hay múltiples fenómenos referidos con este nombre en campos tales como el análisis numérico, el muestreo, la combinatoria, el aprendizaje automático, la minería de datos y bases de datos. La causa común de estos problemas es que cuando aumenta la dimensionalidad, el volumen del espacio aumenta exponencialmente haciendo que los datos disponibles se vuelven dispersos. Esta dispersión es problemática para cualquier método que requiera significación estadística. Con el fin de obtener un resultado estadísticamente sólido y fiable, la cantidad de datos necesarios para mantener el resultado a menudo debe crecer también exponencialmente con la dimensionalidad. Además la organización y búsqueda de datos a menudo se basa en la detección de las áreas donde los objetos forman grupos con propiedades similares, y en datos de alta dimensión, sin embargo todos los objetos parecen ser escasos y diferentes en muchos aspectos, lo que impide que las estrategias de organización de datos comunes sean eficientes.

El término fue acuñado por Richard Bellman cuando estaba considerando los problemas de la programación dinámica.^[2]^[3]

Ejemplo en distintos campos

Muestreo

Por ejemplo: bastan 100 puntos (10²=100) para muestrear un intervalo unidad (un cubo unidimensional) de manera que los puntos no disten más de 10^-2=0,01 entre sí. Pero un muestreo equivalente en un hipercubo unidad de un espacio de dimensión diez harían falta 10²⁰ puntos. En general con una distancia especial de 10^-n en el hipercubo de diez dimensiones aparece ser 10^n(10-1) más grande que en el hipercubo de una dimensión. En el anterior ejemplo n=2; cuando se usa una distancia de muestra de 0,01 el hipercubo de 10 dimensiones parece ser 10¹⁸ más grande que el intervalo unidad.

Funciones distancia

Este fenómeno se aprecia al comparar la proporción de una esfera de radio $r$ con el cubo de arista $2r$ que la contiene al incrementar el número $d$ de dimensiones del espacio. El volumen del cubo es $(2r)^{d}$ y el de la esfera,

${\frac {2r^{d}\pi ^{d/2}}{\Gamma (d/2)d}}.$

Por tanto, conforme $d$ tiende a infinito, el volumen relativo de la esfera con respecto al del cubo se vuelve insignificante:

${\frac {\pi ^{d/2}}{2^{d-1}d\Gamma (d/2)}}\rightarrow 0.$

Así, en cierto sentido, los puntos de un hipercubo de dimensión elevada están alejados del centro.

Impacto

En optimización y aprendizaje automático

La maldición de la dimensión representa un obstáculo importante a la hora de resolver los problemas de optimización que se plantean en el contexto del aprendizaje automático. También afecta a métodos como el de los k vecinos más próximos porque al aumentar la dimensión, la distancia al vecino más próximo crece.

En estadística bayesiana

La maldición de la dimensión también ha dificultado la aplicación de la estadística bayesiana: obliga a que la distribución posterior tenga demasiados parámetros.

Este problema ha sido parcialmente mitigado por algunas técnicas como los Métodos de Montecarlo basados en cadenas de Markov (MCMC), basados en simulaciones. En particular, el método Monte Carlo Hamiltoniano, inspirado en la mecánica Hamiltoniana, muestra un excelente comportamiento en grandes dimensiones.

Véase también

Referencias

↑ Oommen, T.; Misra, D.; Twarakavi, N.K.C.; Prakash, A.; Sahoo, B.; Bandopadhyay, S. (2008). «An Objective Analysis of Support Vector Machine Based Classification for Remote Sensing». Mathematical Geosciences 40 (4): 409. doi:10.1007/s11004-008-9156-6.
↑ Richard Ernest Bellman; Rand Corporation (1957). Dynamic programming. Princeton University Press. ISBN 978-0-691-07951-6. ,
Republished: Richard Ernest Bellman (2003). Dynamic Programming. Courier Dover Publications. ISBN 978-0-486-42809-3.
↑ Richard Ernest Bellman (1961). Adaptive control processes: a guided tour. Princeton University Press.

Bibliografía

Bellman, R.E. 1957. Dynamic Programming. Princeton University Press, Princeton, NJ.
- Republished 2003: Dover, ISBN 0486428095.
Bellman, R.E. 1961. Adaptive Control Processes. Princeton University Press, Princeton, NJ.
Powell, Warren B. 2007. Approximate Dynamic Programming: Solving the Curses of Dimensionality. Wiley, ISBN 0470171553.
Samet, H. 2006. Foundations of Multidimensional and Metric Data Structures. Morgan Kaufman. ISBN 0123694469
Beyer, K. 1999. When Is "Nearest Neighbor" Meaningful? Int. Conf. on Database Theory.

Datos: Q1430460

[1] Oommen, T.; Misra, D.; Twarakavi, N.K.C.; Prakash, A.; Sahoo, B.; Bandopadhyay, S. (2008). «An Objective Analysis of Support Vector Machine Based Classification for Remote Sensing». Mathematical Geosciences 40 (4): 409. doi:10.1007/s11004-008-9156-6.

[2] Richard Ernest Bellman; Rand Corporation (1957). Dynamic programming. Princeton University Press. ISBN 978-0-691-07951-6. ,
Republished: Richard Ernest Bellman (2003). Dynamic Programming. Courier Dover Publications. ISBN 978-0-486-42809-3.

[3] Richard Ernest Bellman (1961). Adaptive control processes: a guided tour. Princeton University Press.

[1]

[2]

[3]