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] ) es el problema causado por el crecimiento exponencial del volumen asociado al incremento del número de dimensiones en un espacio matemático.

El término fue acuñado por Richard Bellman.

Ejemplos

Por ejemplo, 100 puntos bastan para muestrear el intervalo unidad de manera que los puntos no disten más de 0,01 entre sí. Pero en el hipercubo unidad de un espacio 10-dimensional harían falta 10²⁰ puntos.

Otra consecuencia de 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}}{d\Gamma(d/2)}.$

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}}{d2^{d-1}\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 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 distribuición posterior tenga demasiados parámetros.

Este problema ha sido parcialmente mitigado por el desarrollo de la inferencia bayesiana basada en simulaciones, especialmente usando técnicas como la de Markov chain Monte Carlo.

Véase también

• Combinatorial explosion
• Concentration of measure
• High-dimensional space
• Dimension reduction
• Fourier-related transforms
• Clustering high-dimensional data
• Dynamic programming
• Bellman equation
• Backwards induction
• Principal component analysis
• Linear least squares
• Quasi-random
• Clustering
• Wavelet
• Time series
• Singular value decomposition

Notas

1. ↑ Por favor, pon la referencia que aparece aquí.

Referencias

• 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.