1 Coarmnxgcnelu9hyzcvtw.jpeg

Sumérgete en el concepto de la «Maldición de la Dimensionalidad» y comprende las matemáticas detrás de todos los fenómenos sorprendentes que surgen en las altas dimensiones.

Imagen de Dall-E

En el ámbito del aprendizaje automático, el manejo de vectores de alta dimensión no sólo es común; es esencial. Esto queda ilustrado por la arquitectura de modelos populares como Transformers. Por ejemplo, BERT utiliza vectores de 768 dimensiones para codificar los tokens de las secuencias de entrada que procesa y capturar mejor patrones complejos en los datos. Dado que nuestro cerebro tiene dificultades para visualizar cualquier cosa más allá de las 3 dimensiones, ¡el uso de vectores de 768 dimensiones es bastante alucinante!

Si bien algunos modelos de aprendizaje automático y profundo sobresalen en estos escenarios de alta dimensión, también presentan muchos desafíos. En este artículo, exploraremos el concepto de «maldición de la dimensionalidad», explicaremos algunos fenómenos interesantes asociados con él, profundizaremos en las matemáticas detrás de estos fenómenos y discutiremos sus implicaciones generales para sus modelos de aprendizaje automático.

Tenga en cuenta que las pruebas matemáticas detalladas relacionadas con este artículo son disponible en mi sitio web como extensión complementaria de este artículo.

La gente suele suponer que los conceptos geométricos familiares en tres dimensiones se comportan de manera similar en espacios de dimensiones superiores. Este no es el caso. A medida que aumenta la dimensión, surgen muchos fenómenos interesantes y contrarios a la intuición. La “Maldición de la Dimensionalidad” es un término inventado por Richard Bellman (famoso matemático) que se refiere a todos estos efectos sorprendentes.

Lo que tiene de especial las grandes dimensiones es cómo crece el “volumen” del espacio (lo exploraremos con más detalle pronto). exponencialmente. Tome una línea graduada (en una dimensión) del 1 al 10. Hay 10 números enteros en esta línea. Extienda eso en 2 dimensiones: ahora es un cuadrado con 10 × 10 = 100 puntos con coordenadas enteras. Ahora considere “sólo” 80 dimensiones: ya tendría 10⁸⁰ puntos que es el número de átomos que hay en el universo.

En otras palabras, a medida que aumenta la dimensión, el volumen del espacio crece exponencialmente, lo que hace que los datos se vuelvan más cada vez más escaso.

Los espacios de alta dimensión están «vacíos»

Consideremos este otro ejemplo. Queremos calcular la distancia más lejana entre dos puntos en un hipercubo unitario (donde cada lado tiene una longitud de 1):

  • En 1 dimensión (el hipercubo es un segmento de línea de 0 a 1), la distancia máxima es simplemente 1.
  • En 2 dimensiones (el hipercubo forma un cuadrado), la distancia máxima es la distancia entre las esquinas opuestas [0,0] y [1,1]que es √2, calculado utilizando el teorema de Pitágoras.
  • Ampliando este concepto a n dimensionesla distancia entre los puntos en [0,0,…,0] y [1,1,…,1] es √n. Esta fórmula surge porque cada dimensión adicional suma un cuadrado de 1 a la suma bajo la raíz cuadrada (nuevamente por el teorema de Pitágoras).

Curiosamente, a medida que aumenta el número de dimensiones n, la distancia más grande dentro del hipercubo crece a una tasa O(√n). Este fenómeno ilustra una efecto de rendimiento decreciente, donde los aumentos en el espacio dimensional conducen a ganancias proporcionalmente menores en la distancia espacial. Se explorarán más detalles sobre este efecto y sus implicaciones en las siguientes secciones de este artículo.

Profundicemos en la noción de distancias que comenzamos a explorar en la sección anterior.

Tuvimos nuestra primera visión de cómo los espacios de alta dimensión hacen que la noción de distancia sea casi sin sentido. Pero, ¿qué significa esto realmente? ¿Podemos visualizar matemáticamente este fenómeno?

Consideremos un experimento, usando el mismo hipercubo unitario de n dimensiones que definimos antes. Primero, generamos un conjunto de datos muestreando aleatoriamente muchos puntos en este cubo: simulamos efectivamente una distribución uniforme multivariada. Luego, tomamos muestras de otro punto (un punto de “consulta”) de esa distribución y observamos la distancia de su vecino más cercano y más lejano en nuestro conjunto de datos.

Aquí está el código Python correspondiente.

def generate_data(dimension, num_points):
''' Generate random data points within [0, 1] for each coordinate in the given dimension '''
data = np.random.rand(num_points, dimension)
return data

def neighbors(data, query_point):
''' Returns the nearest and farthest point in data from query_point '''
nearest_distance = float('inf')
farthest_distance = 0
for point in data:
distance = np.linalg.norm(point - query_point)
if distance < nearest_distance:
nearest_distance = distance
if distance > farthest_distance:
farthest_distance = distance
return nearest_distance, farthest_distance

También podemos trazar estas distancias:

Distancias a los puntos más cercano y más lejano a medida que n aumenta (Imagen del autor)

Utilizando una escala logarítmica observamos que relativo La diferencia entre la distancia al vecino más cercano y más lejano tiende a disminuir a medida que aumenta la dimensión.

Este es un comportamiento muy poco intuitivo: como se explicó en la sección anterior, los puntos están muy separados entre sí debido al volumen exponencialmente creciente del espacio, pero al mismo tiempo, el relativo las distancias entre puntos se vuelven más pequeñas.

La noción de vecinos más cercanos desaparece

Esto significa que el concepto mismo de distancia se vuelve menos relevante y menos discriminativo a medida que aumenta la dimensión del espacio. Como puede imaginar, plantea problemas para los algoritmos de aprendizaje automático que se basan únicamente en distancias como kNN.

Ahora hablaremos de algunos otros fenómenos interesantes. Para esto necesitaremos el n-bola. Una n-bola es la generalización de una pelota en n dimensiones. La n-bola de radio R es el conjunto de puntos a una distancia máxima R del centro del espacio 0.

Consideremos un radio de 1. La bola 1 es el segmento [-1, 1]. La de 2 bolas es el disco delimitado por el círculo unitario, cuya ecuación es x² + y² ≤ 1. La de 3 bolas (lo que normalmente llamamos “bola”) tiene la ecuación x² + y² + z² ≤ 1. Como comprenderás , podemos extender esa definición a cualquier dimensión:

La pregunta ahora es: ¿cuál es el volumen de esta pelota? Esta no es una pregunta fácil y requiere bastantes cálculos, que no detallaré aquí. Sin embargo, puedes encontrar todos los detalles en mi sitio web, en mi publicación sobre el volumen del n-ball.

Después de mucha diversión (cálculo integral), puedes demostrar que el volumen de la n-bola se puede expresar de la siguiente manera, donde Γ denota el función gamma.

Por ejemplo, con R = 1 y n = 2, el volumen es πR², porque Γ(2) = 1. Este es de hecho el “volumen” de la bola 2 (también llamada “área” de un círculo en este caso ).

Sin embargo, más allá de ser un desafío matemático interesante, el volumen de la n-ball también tiene algunas propiedades muy sorprendentes.

A medida que aumenta la dimensión n, el volumen de la n-bola converge a 0.

Esto es cierto para todos los radios, pero visualicemos este fenómeno con algunos valores de R.

Volumen de la n-bola para diferentes radios a medida que aumenta la dimensión (Imagen del autor)

Como puede ver, solo converge a 0, pero comienza aumentando y luego disminuye a 0. Para R = 1, la bola con mayor volumen es la bola 5, y el valor de n que alcanza el máximo se desplaza a hacia la derecha a medida que R aumenta.

Aquí están los primeros valores del volumen de la unidad n-bola, hasta n = 10.

Volumen de la unidad n-ball para diferentes valores de n (Imagen del autor)

El volumen de una bola unitaria de grandes dimensiones se concentra cerca de su superficie.

En dimensiones pequeñas, el volumen de una bola parece bastante “homogéneo”, mientras que en dimensiones grandes no es así.

Una concha esférica

Consideremos una n-bola de radio R y otra de radio R-dR donde dR es muy pequeña. La porción de la n-bola entre estas 2 bolas se llama «cáscara» y corresponde a la porción de la bola cerca de su superficie (ver la visualización de arriba en 3D). Podemos calcular la relación entre el volumen de toda la bola y el volumen de esta delgada capa únicamente.

Relación (volumen total/volumen de cáscara delgada) a medida que n aumenta (Imagen del autor)

Como podemos ver, converge muy rápidamente a 0: casi todo el volumen está cerca de la superficie en espacios de alta dimensión. Por ejemplo, para R = 1, dR = 0,05 y n = 50, aproximadamente el 92,3% del volumen se concentra en la capa delgada. Esto muestra que en dimensiones superiores, el volumen está en “esquinas”. Esto está nuevamente relacionado con la distorsión del concepto de distancia que hemos visto antes.

Tenga en cuenta que el volumen del hipercubo unitario es 2ⁿ. La esfera unitaria está básicamente “vacía” en dimensiones muy altas, mientras que el hipercubo unitario, por el contrario, obtiene exponencialmente más puntos. Nuevamente, esto muestra cómo la idea de un “vecino más cercano” de un punto pierde su efectividad porque casi no hay ningún punto dentro de una distancia R de un punto de consulta q cuando n es grande.

La maldición de la dimensionalidad está estrechamente relacionada con el principio de sobreajuste. Debido al crecimiento exponencial del volumen del espacio con la dimensión, necesitamos conjuntos de datos muy grandes para capturar y modelar adecuadamente patrones de alta dimensión. Peor aún: necesitamos un número de muestras que crezca exponencialmente con la dimensión de superar esta limitación. Este escenario, caracterizado por muchas características pero relativamente pocos datos, es particularmente propenso al sobreajuste.

La navaja de Occam sugiere que Los modelos más simples son generalmente mejores que los complejos. porque es menos probable que se sobreadapten. Este principio es particularmente relevante en contextos de alta dimensión (donde la maldición de la dimensionalidad juega un papel) porque fomenta la reducción de la complejidad del modelo.

Aplicar el principio de la Navaja de Occam en escenarios de alta dimensión puede significar reducir la dimensionalidad del problema en sí (mediante métodos como PCA, selección de características, etc.), con lo que mitigar algunos efectos de la maldición de la dimensionalidad. Simplificar la estructura del modelo o el espacio de características ayuda a gestionar la escasa distribución de datos y a hacer que las métricas de distancia vuelvan a ser más significativas. Por ejemplo, la reducción de dimensionalidad es una práctica muy común. paso preliminar antes de aplicar el algoritmo kNN. Métodos más recientes, como RNA (Vecinos más cercanos aproximados) también surgen como una forma de abordar escenarios de alta dimensión.

Imagen de Dall-E

Si bien hemos descrito los desafíos de las configuraciones de alta dimensión en el aprendizaje automático, también existen algunas ventajas!

  • Las dimensiones altas pueden mejorar separabilidad linealhaciendo que técnicas como los métodos del kernel sean más efectivas.
  • Además, las arquitecturas de aprendizaje profundo son particularmente experto para navegar y extraer patrones complejos de espacios de alta dimensión.

Como siempre con el aprendizaje automático, esto es una compensación: aprovechar estas ventajas implica equilibrar las mayores demandas computacionales con ganancias potenciales en el rendimiento del modelo.

Con suerte, esto le dará una idea de cuán “extraña” puede ser la geometría en alta dimensión y los muchos desafíos que plantea para el desarrollo de modelos de aprendizaje automático. Vimos cómo, en espacios de alta dimensión, los datos son muy escasos pero también tienden a concentrarse en las esquinas y las distancias pierden su utilidad. Para profundizar más en el n-ball y las pruebas matemáticas, te invito a visitar la ampliada de este artículo en mi sitio web.

Si bien la “maldición de la dimensionalidad” describe limitaciones significativas en espacios de alta dimensión, es emocionante ver cómo los modelos modernos de aprendizaje profundo son cada vez más hábiles para sortear estas complejidades. Considere los modelos de incrustación o los últimos LLM, por ejemplo, que utilizan vectores de muy altas dimensiones para discernir y modelar patrones textuales de manera más efectiva.