La Maldición de la Dimensión en Machine Learning

¿Sabías que a medida que aumenta el número de dimensiones, la distancias se vuelven menos discriminativas? A este efecto se le conoce con el nombre de la Maldición de la Dimensión (Curse of Dimensionality) y tiene un gran impacto en técnicas de aprendizaje automático basadas en distancias tales como K-Means y KNN (los k vecinos más cercanos).

La Maldición de la Dimensión

En Machine Learning, el número de dimensiones se puede equiparar al número de variables o características (features) que estemos utilizando.

La maldición de la dimensión se «manifiesta» de dos maneras:

• La distancia media entre los datos aumenta con el número de dimensiones
• La variabilidad de la distancia disminuye exponencialmente con el número de dimensiones (éste es el verdadero problema)

Vamos a verlo en detalle. Para darte una intuición gráfica he generado puntos aleatorios en varias dimensiones siempre en el rango [0, 1].

La distancia media aumenta con el número de dimensiones

A medida que el número de dimensiones aumenta, la distancia media entre ellos también aumenta. Esto en sí mismo no es muy problemático para el aprendizaje automático. El siguiente gráfico muestra este efecto (hasta 1000 dimensiones).

La variabilidad disminuye exponencialmente

Lo verdaderamente importante es que a medida que el número de dimensiones aumenta … ¡la variabilidad de las distancias entre los datos disminuye exponencialmente!

El siguiente gráfico muestra el coeficiente de variación para varias dimensiones (hasta 1000). El coeficiente de variación se utiliza para medir la variabilidad.

Esto es terrible para los métodos de aprendizaje automático basados en distancias tales como clustering o los vecinos más cercanos. El problema es que cuando hay un gran número de atributos (features), los datos están todos a casi la misma distancia. Es decir, no hay variabilidad entre sus distancias.

Distribución de distancias a medida que aumenta la dimensión

La maldición de la dimensión es un concepto un tanto abstracto. Por eso, creo que una intuición gráfica que nos explique qué está pasando cuando cuando aumenta el número de variables puede resultar esclarecedora.

La siguiente figura muestra la distribución de distancias euclídeas entre 10000 puntos aleatorios en el rango [0, 1] en varias dimensiones: 1, 2, 3, 10, 50, 100, 250, 500 y 1000.

Como puedes apreciar, conforme van aumentando las dimensiones la variabilidad va desapareciendo. Esto hace que los algoritmos de machine learning basados en distancias tengan muy difícil el saber qué puntos están más cerca que otros.

Intuición Gráfica de la Maldición de la Dimensión

¿Por qué aumenta la distancia media con el número de dimensiones? ¿y por qué se reduce la variabilidad entre las distancias? Vamos a tratar de verlo con un ejemplo.

En la siguiente figura podemos ver 100 puntos elegidos aleatoriamente en el rango [0,1] para 1 dimensión. Como ves, es bastante fácil encontrar puntos que estén muy cerca (por ejemplo: 0.21 y 0.25) y puntos que estén lejos (0.21 y 0.99). Para cualquier punto, en 1 dimensión, es fácil encontrar muchos puntos que estén cerca y bastantes puntos que estén lejos.

Sin embargo, encontrar muchos puntos que estén cerca de uno dado ya no es tan fácil cuando los 100 puntos los ponemos aleatoriamente en 2 dimensiones. En 2 dimensiones, la mayoría de los puntos están a una distancia media de otros … mientras que para 1 dimensión, la mayoría de los puntos están cerca de otros puntos.

Este efecto se acentúa a medida que el número de dimensiones va subiendo.

Impacto de la Maldición de la Dimensión en Machine Learning

En una representación de datos de alta dimensionalidad, cada dato está aproximadamente a la misma distancia de cualquier otro. Es decir, la distancia discrimina menos conforme aumenta el número de dimensiones.

Esto no siempre es un problema, ya que la maldición de la dimensión sólo afecta a las técnicas basadas en distancias.

Estas son algunas de las técnicas de aprendizaje automático afectadas por la maldición de la dimensión:

• Agrupamiento (clustering): para encontrar automáticamente grupos en los datos
• K vecinos más cercanos (KNN): ofrece una predicción combinando los resultados de instancias similares.
• Técnicas de detección de anomalías basadas en distancias tales como Local Outlier Factor.

Mitigando el efecto de la Maldición de la Dimensión

Para mitigar el efecto de la maldición de la dimensión tenemos dos opciones:

• reducir el número de dimensiones
• aumentar la cantidad de datos

Técnicas de reducción de la dimensionalidad

Hay varias técnicas para reducir la dimensión de nuestro problema. La más conocida es el Análisis de Componentes Principales (PCA por sus siglas en inglés, Principal Component Analysis). Otras técnicas incluyen el uso de auto-encoders, variedades (manifold), etc.

Las técnicas de reducción de dimensionalidad asumen que pueden capturar bastante variabilidad de los datos en menos dimensiones. Así crean un conjunto nuevo de dimensiones que representa nuestros mismos datos con menor dimensionalidad.

Esto permite utilizar técnicas de machine learning en una dimensionalidad menor. Para técnicas sensibles a la maldición de la dimensión, los resultados serán probablemente mucho mejores. En cualquier caso, al tener menos atributos, hay una mejora de rendimiento, tanto en el uso de memoria como en el uso de la CPU.

El problema … es que no resulta muy interpretable lo que significan el conjunto nuevo de dimensiones. Sin embargo, si no nos preocupa la interpretabilidad para algún modelo, es un enfoque aconsejable.

Aumentar (exponencialmente) la cantidad de datos

A más dimensiones, más datos se necesitan para llenar el espacio. Cuando el número de dimensiones es muy alto, el espacio está casi vacío. Por eso es tan difícil encontrar puntos que estén cerca.

Por esta razón, también podemos mitigar el efecto de la maldición de la dimensión aumentando la cantidad de datos. Este aumento debe ser exponencial con el número de dimensiones, para contrarrestar el efecto exponencial de la pérdida de variabilidad de las distancias.

Normalmente es mucho más difícil (y más caro) aumentar exponencialmente la cantidad de datos. Así que las técnicas de reducción de la dimensionalidad se usan con frecuencia en estos casos. Por otra parte, si para un problema en particular, es fácil (y barato) conseguir muchos más datos, puede ser una buena opción.

Resumen

La maldición de la dimensión nos enseña que la variabilidad de las distancias entre nuestros datos disminuye exponencialmente con el número de dimensiones (features).

Esta maldición afecta a las técnicas que estén basadas en distancias tales como agrupamiento (clustering), los vecinos más cercanos (k-NN), algunas técnicas de detección de outliers, etc.

Para mitigar los efectos de esta «maldición» podemos utilizar técnicas de reducción de la dimensionalidad y / o aumentar (exponencialmente) la cantidad de datos.

Fuente imagen del espejo: pixbay