Maldición de la dimensionalidad

En algunos problemas, cada variable puede tomar uno de varios valores discretos, o el rango de valores posibles se divide para dar un número finito de posibilidades. Tomando las variables en conjunto, se debe considerar una enorme cantidad de combinaciones de valores. Este efecto también se conoce como explosión combinatoria . Incluso en el caso más simple de${\displaystyle d}$variables binarias , el número de combinaciones posibles ya es${\displaystyle 2^{d}}$, exponencial en la dimensionalidad. Ingenuamente, cada dimensión adicional duplica el esfuerzo necesario para probar todas las combinaciones.

Hay un aumento exponencial en el volumen asociado con agregar dimensiones adicionales a un espacio matemático . Por ejemplo, 10² ⁼  100 puntos de muestra espaciados uniformemente son suficientes para muestrear un intervalo unitario (intente visualizar un cubo "unidimensional", es decir, una línea) con no más de 10⁻² ⁼ 0,01 de distancia entre puntos; un muestreo equivalente de un hipercubo unitario de 10 dimensiones con una red que tiene un espaciado de 10⁻² ⁼ 0,01 entre puntos adyacentes requeriría ^10²⁰ = [(10² ⁾ ¹⁰ ^] puntos de muestra. En general, con una distancia de espaciado de 10⁻ⁿ ^{, el} hipercubo de 10 dimensiones parece ser un factor de 10ⁿ ^{( 10⁻¹)} = [( ^10ⁿ ) ^¹⁰ / ( ^10ⁿ )] "más grande" que el hipercubo unidimensional, que es el intervalo unitario. En el ejemplo anterior, n = 2: al usar una distancia de muestreo de 0,01, el hipercubo de 10 dimensiones parece ser 10¹⁸ ^" más grande" que el intervalo unitario. Este efecto es una combinación de los problemas combinatorios mencionados anteriormente y los problemas de la función de distancia que se explican a continuación.

Al resolver problemas de optimización dinámica mediante inducción numérica hacia atrás , la función objetivo debe evaluarse para cada combinación de valores en un espacio de estados discretizado. Esto representa un obstáculo significativo cuando la dimensión de la "variable de estado" es grande. ^{[ 3 ]}

En los problemas de aprendizaje automático que implican aprender un "estado de la naturaleza" a partir de un número finito de muestras de datos en un espacio de características de alta dimensión , donde cada característica tiene un rango de valores posibles, normalmente se requiere una enorme cantidad de datos de entrenamiento para asegurar que existan varias muestras con cada combinación de valores. En un sentido abstracto, a medida que aumenta el número de características o dimensiones, la cantidad de datos que necesitamos para generalizar con precisión crece exponencialmente. ^{[ 4 ]}

Una regla general típica es que debe haber al menos 5 ejemplos de entrenamiento para cada dimensión en la representación. ^{[ 5 ]} En el aprendizaje automático y en lo que respecta al rendimiento predictivo, la maldición de la dimensionalidad se usa indistintamente con el fenómeno de pico , ^{[ 5 ]} que también se conoce como fenómeno de Hughes . ^{[ 6 ]} Este fenómeno establece que con un número fijo de muestras de entrenamiento, el poder predictivo promedio (esperado) de un clasificador o regresor primero aumenta a medida que aumenta el número de dimensiones o características utilizadas, pero más allá de cierta dimensionalidad comienza a deteriorarse en lugar de mejorar constantemente. ^{[ 7 ] [ 8 ] [ 9 ]}

No obstante, en el contexto de un clasificador simple (por ejemplo, análisis discriminante lineal en el modelo gaussiano multivariado bajo el supuesto de una matriz de covarianza común conocida), Zollanvari et al. demostraron, tanto analítica como empíricamente, que siempre que la eficacia acumulativa relativa de un conjunto de características adicionales (con respecto a las características que ya forman parte del clasificador) sea mayor (o menor) que el tamaño de dicho conjunto, el error esperado del clasificador construido con estas características adicionales será menor (o mayor) que el error esperado del clasificador construido sin ellas. En otras palabras, tanto el tamaño de las características adicionales como su efecto discriminatorio acumulativo (relativo) son importantes para observar una disminución o un aumento en el poder predictivo promedio. ^{[ 10 ]}

En el aprendizaje métrico , las dimensiones más altas a veces permiten que un modelo logre un mejor rendimiento. Después de normalizar las incrustaciones a la superficie de una hiperesfera, FaceNet logra el mejor rendimiento usando 128 dimensiones en comparación con 64, 256 o 512 dimensiones en un estudio de ablación. ^{[ 11 ]} Se encontró que una función de pérdida para la disimilitud invariante unitaria entre incrustaciones de palabras se minimiza en dimensiones altas. ^{[ 12 ]}

En minería de datos , la maldición de la dimensionalidad se refiere a un conjunto de datos con demasiadas características. ^{[ 13 ] [ 14 ]}

Consideremos la primera tabla, que muestra 200 individuos y 2000 genes (características), donde un 1 o un 0 indica si presentan o no una mutación genética en dicho gen. Una aplicación de minería de datos a este conjunto de datos podría consistir en encontrar la correlación entre mutaciones genéticas específicas y crear un algoritmo de clasificación, como un árbol de decisión , para determinar si un individuo padece cáncer o no.

Una práctica común de minería de datos en este ámbito sería crear reglas de asociación entre mutaciones genéticas que conducen al desarrollo de cánceres. Para ello, habría que recorrer cada mutación genética de cada individuo y encontrar otras mutaciones genéticas que superen un umbral determinado, creando pares. Se comenzaría con pares de dos, luego de tres, luego de cuatro, hasta obtener un conjunto vacío de pares. La complejidad de este algoritmo puede llevar al cálculo de todas las permutaciones de pares de genes para cada individuo o fila. La fórmula para calcular las permutaciones de n elementos con un tamaño de grupo r es:${\displaystyle {\frac {n!}{(nr)!}}}$, calcular el número de permutaciones de tres pares de cualquier individuo dado seríaSe evaluarán 7 988 004 000 pares de genes diferentes para cada individuo. El número de pares creados aumentará exponencialmente a medida que aumente el tamaño de los pares. Este crecimiento se muestra en la tabla de permutaciones (véase a la derecha).

Como se puede observar en la tabla de permutaciones anterior, uno de los principales problemas que enfrentan los analistas de datos con respecto a la maldición de la dimensionalidad es que el espacio de posibles valores de parámetros crece exponencial o factorialmente a medida que aumenta el número de características en el conjunto de datos. Este problema afecta de manera crítica tanto el tiempo como el espacio computacional al buscar asociaciones o características óptimas a considerar.

Otro problema al que pueden enfrentarse los analistas de datos al trabajar con demasiadas características es que el número de predicciones o clasificaciones erróneas tiende a aumentar a medida que crece el número de características en el conjunto de datos. En cuanto al problema de clasificación mencionado anteriormente, conservar todos los puntos de datos podría generar un mayor número de falsos positivos y falsos negativos en el modelo.

Esto puede parecer contraintuitivo, pero consideremos la tabla de mutaciones genéticas anterior, que muestra todas las mutaciones genéticas de cada individuo. Cada mutación genética, independientemente de si se correlaciona con el cáncer o no, tendrá algún peso o influencia en el modelo que guía el proceso de toma de decisiones del algoritmo. Puede haber mutaciones atípicas o que dominen la distribución general de mutaciones genéticas cuando, en realidad, no se correlacionan con el cáncer. Estas características pueden perjudicar el modelo, dificultando la obtención de resultados óptimos.

Este problema es responsabilidad del analista de datos, y no existe una solución universal. El primer paso que debe dar cualquier analista de datos es explorar los datos para comprender cómo utilizarlos para resolver el problema. Es fundamental comprender el significado de los datos y qué se busca descubrir antes de decidir si es necesario eliminar algún elemento del conjunto de datos. Posteriormente, se puede crear o utilizar un algoritmo de selección de características o de reducción de dimensionalidad para eliminar muestras o características del conjunto de datos si se considera necesario. Un ejemplo de estos métodos es el rango intercuartil , que se utiliza para eliminar valores atípicos en un conjunto de datos calculando la desviación estándar de una característica o ocurrencia.

Cuando una medida como la distancia euclidiana se define utilizando muchas coordenadas, hay poca diferencia en las distancias entre diferentes pares de puntos.

Una forma de ilustrar la "inmensidad" del espacio euclidiano de alta dimensión es comparar la proporción de una hiperesfera inscrita con radio${\displaystyle r}$y dimensión${\displaystyle d}$, al de un hipercubo con aristas de longitud${\displaystyle 2r.}$ El volumen de dicha esfera es${\displaystyle {\frac {2r^{d}\pi ^{d/2}}{d\;\Gamma (d/2)}}}$, dónde${\displaystyle \Gamma }$es la función gamma , mientras que el volumen del cubo es${\displaystyle (2r)^{d}}$. Como la dimensión${\displaystyle d}$del espacio aumenta, la hiperesfera se convierte en un volumen insignificante en relación con el del hipercubo. Esto se puede ver claramente al comparar las proporciones a medida que la dimensión${\displaystyle d}$va hasta el infinito:

${\displaystyle {\frac {V_{\mathrm {hiperesfera} }}{V_{\mathrm {hipercubo} }}}={\frac {\pi ^{d/2}}{d2^{d-1}\Gamma (d/2)}}\rightarrow 0}$como${\displaystyle d\rightarrow \infty }$.

Además, la distancia entre el centro y las esquinas es${\displaystyle r{\sqrt {d}}}$, que aumenta sin límite para un r fijo.

En este sentido, cuando los puntos se generan uniformemente en un hipercubo de alta dimensión, casi todos los puntos están mucho más lejos que${\displaystyle r}$unidades lejos del centro. En dimensiones altas, el volumen del hipercubo unitario d -dimensional (con coordenadas de los vértices${\displaystyle \pm 1}$) se concentra cerca de una esfera con el radio${\displaystyle {\sqrt {d}}/{\sqrt {3}}}$para una dimensión grande d . De hecho, para cada coordenada${\displaystyle x_{i}}$el valor promedio de ${\displaystyle x_{i}^{2}}$en el cubo es ^{[ 15 ]}

${\displaystyle \left\langle x_{i}^{2}\right\rangle ={\frac {1}{2}}\int _{-1}^{1}x^{2}dx={\frac {1}{3}}}$.

La varianza de ${\displaystyle x_{i}^{2}}$para distribución uniforme en el cubo es

${\displaystyle {\frac {1}{2}}\int _{-1}^{1}x^{4}dx-\left\langle x_{i}^{2}\right\rangle ^{2}={\frac {4}{45}}}$

Por lo tanto, la distancia al cuadrado desde el origen,${\textstyle r^{2}=\sum _{i}x_{i}^{2}}$tiene un valor promedio d /3 y una varianza de 4 d /45. Para d grande , la distribución de${\displaystyle r^{2}/d}$se aproxima a la distribución normal con una media de 1/3 y una desviación estándar${\displaystyle 2/{\sqrt {45d}}}$Según el teorema del límite central , al generar puntos uniformemente en dimensiones altas, tanto el "centro" del hipercubo como las esquinas están vacíos, y todo el volumen se concentra cerca de la superficie de una esfera de radio "intermedio".${\textstyle {\sqrt {d/3}}}$.

Esto también ayuda a comprender la distribución chi-cuadrado . De hecho, la distribución chi-cuadrado (no central) asociada a un punto aleatorio en el intervalo [-1, 1] es la misma que la distribución del cuadrado de la longitud de un punto aleatorio en el d -cubo. Por la ley de los grandes números, esta distribución se concentra en una banda estrecha alrededor de d veces la desviación estándar al cuadrado (σ² ⁾ de la derivación original. Esto ilumina la distribución chi-cuadrado y también ilustra que la mayor parte del volumen del d -cubo se concentra cerca del límite de una esfera de radio${\displaystyle \sigma {\sqrt {d}}}$.

Un desarrollo posterior de este fenómeno es el siguiente. Cualquier distribución fija en los números reales induce una distribución de producto en puntos en${\displaystyle \mathbb {R} ^{d}}$. Para cualquier n fijo , resulta que la diferencia entre la distancia mínima y máxima entre un punto de referencia aleatorio Q y una lista de n puntos de datos aleatorios P _​​1 ,..., P _n se vuelve indiscernible en comparación con la distancia mínima: ^{[ 16 ]}

${\displaystyle \lim _{d\to \infty }E\left({\frac {\operatorname {dist} _{\max }(d)-\operatorname {dist} _{\min }(d)}{\operatorname {dist} _{\min }(d)}}\right)\to 0}$.

Esto se cita a menudo como la pérdida de utilidad de las funciones de distancia (para el criterio del vecino más cercano en algoritmos de comparación de características, por ejemplo) en dimensiones altas. Sin embargo, investigaciones recientes han demostrado que esto solo se cumple en el escenario artificial cuando las distribuciones unidimensionales${\displaystyle \mathbb {R} }$son independientes e idénticamente distribuidos . ^{[ 13 ]} Cuando los atributos están correlacionados, los datos pueden ser más fáciles y proporcionar un mayor contraste de distancia y se encontró que la relación señal-ruido juega un papel importante, por lo que se debe utilizar la selección de características . ^{[ 13 ]}

Más recientemente, se ha sugerido que podría existir una falla conceptual en el argumento de que la pérdida de contraste crea una maldición en dimensiones altas. El aprendizaje automático puede entenderse como el problema de asignar instancias a su respectivo proceso generativo de origen, donde las etiquetas de clase actúan como representaciones simbólicas de los procesos generativos individuales. La derivación de la maldición asume que todas las instancias son resultados independientes e idénticos de un único proceso generativo de alta dimensión. Si solo existe un proceso generativo, solo existiría una clase (de origen natural) y el aprendizaje automático estaría conceptualmente mal definido tanto en dimensiones altas como bajas. Por lo tanto, el argumento tradicional de que la pérdida de contraste crea una maldición podría ser fundamentalmente inapropiado. Además, se ha demostrado que cuando el modelo generativo se modifica para acomodar múltiples procesos generativos, la pérdida de contraste puede transformarse de una maldición a una bendición, ya que garantiza que el vecino más cercano de una instancia sea casi con seguridad su instancia más estrechamente relacionada. Desde esta perspectiva, la pérdida de contraste hace que las distancias de alta dimensión sean especialmente significativas y no especialmente carentes de significado, como se suele argumentar. ^{[ 17 ]}

El efecto complica la búsqueda del vecino más cercano en espacios de alta dimensión. No es posible rechazar rápidamente a los candidatos utilizando la diferencia en una coordenada como límite inferior para una distancia basada en todas las dimensiones. ^{[ 18 ] [ 19 ]}

Sin embargo, recientemente se ha observado que el mero número de dimensiones no necesariamente genera dificultades, ^{[ 14 ]} ya que las dimensiones adicionales relevantes también pueden aumentar el contraste. Además, para la clasificación resultante, sigue siendo útil distinguir entre vecinos cercanos y lejanos. Sin embargo, las dimensiones irrelevantes ("ruido") reducen el contraste de la manera descrita anteriormente. En el análisis de series temporales , donde los datos son inherentemente de alta dimensión, las funciones de distancia también funcionan de manera confiable siempre que la relación señal-ruido sea suficientemente alta. ^{[ 20 ]}

En una encuesta de 2012, Zimek et al. identificaron los siguientes problemas al buscar anomalías en datos de alta dimensión: ^{[ 13 ]}

1. Concentración de puntuaciones y distancias: los valores derivados, como las distancias, se vuelven numéricamente similares.
2. Atributos irrelevantes: en datos de alta dimensión, un número significativo de atributos puede ser irrelevante.
3. Definición de conjuntos de referencia: para los métodos locales, los conjuntos de referencia suelen basarse en el vecino más cercano.
4. Puntuaciones incomparables para diferentes dimensionalidades: diferentes subespacios producen puntuaciones incomparables
5. Interpretabilidad de las puntuaciones: las puntuaciones a menudo ya no transmiten un significado semántico.
6. Espacio de búsqueda exponencial: el espacio de búsqueda ya no se puede explorar sistemáticamente.
7. Sesgo de búsqueda de datos : dado el gran espacio de búsqueda, para cada significancia deseada se puede encontrar una hipótesis.
8. Centralidad: ciertos objetos aparecen con mayor frecuencia en las listas de vecinos que otros.

Muchos de los métodos especializados analizados abordan uno u otro de estos problemas, pero aún quedan muchas preguntas de investigación abiertas.

A pesar de las dificultades esperadas de la "maldición de la dimensionalidad", las heurísticas de sentido común basadas en los métodos más directos "pueden producir resultados que son casi con seguridad óptimos" para problemas de alta dimensión. ^{[ 24 ]} El término "bendición de la dimensionalidad" se introdujo a finales de la década de 1990. ^{[ 24 ]} Donoho en su "Manifiesto del Milenio" explicó por qué cree que la "bendición de la dimensionalidad" formará una base de la minería de datos futura. ^{[ 25 ]} Los efectos de la bendición de la dimensionalidad se descubrieron en muchas aplicaciones y encontraron su fundamento en los fenómenos de concentración de medidas . ^{[ 26 ]} Un ejemplo del fenómeno de la bendición de la dimensionalidad es la separabilidad lineal de un punto aleatorio de un gran conjunto aleatorio finito con alta probabilidad incluso si este conjunto es exponencialmente grande: el número de elementos en este conjunto aleatorio puede crecer exponencialmente con la dimensión. Además, este funcional lineal puede seleccionarse en la forma del discriminante de Fisher lineal más simple . Este teorema de separabilidad se demostró para una amplia clase de distribuciones de probabilidad: distribuciones generales uniformemente log-cóncavas, distribuciones de producto en un cubo y muchas otras familias (revisadas recientemente en ^{[ 26 ]} ).

«La bendición de la dimensionalidad y la maldición de la dimensionalidad son dos caras de la misma moneda». ^{[ 27 ]} Por ejemplo, la propiedad típica de las distribuciones de probabilidad esencialmente de alta dimensión en un espacio de alta dimensión es: la distancia al cuadrado de puntos aleatorios a un punto seleccionado es, con alta probabilidad, cercana a la distancia al cuadrado promedio (o mediana). Esta propiedad simplifica significativamente la geometría esperada de los datos y la indexación de datos de alta dimensión (bendición), ^{[ 28 ]} pero, al mismo tiempo, hace que la búsqueda de similitud en altas dimensiones sea difícil e incluso inútil (maldición). ^{[ 29 ]}

Zimek et al. ^{[ 13 ]} observaron que, si bien las formalizaciones típicas de la maldición de la dimensionalidad afectan a los datos i.i.d. , resulta más sencillo separar los datos en cada atributo, incluso en dimensiones elevadas. Argumentaron que la relación señal-ruido es importante: los datos se procesan con mayor facilidad con cada atributo que aporta señal, y con mayor dificultad con los atributos que solo añaden ruido (error irrelevante). En particular, para el análisis de datos no supervisado, este efecto se conoce como saturación.