La maldición de las dimensiones

Tras mi desapercibida desaparición de la semana pasada, vuelvo para hablaros de más cosas de informática. Esta vez, la última durante un tiempo, de lo que toca es hablar sobre la maldición de las dimensiones, termino acuñado por Richard Bellman en 1961. Como siempre, en esta entrada se sacrificará el rigor, con el objetivo de que este problema sea comprensible.

A grandes rasgos, la maldición de las dimensiones se refiere a una serie de fenómenos que suceden cuando se trabaja con espacios vectoriales de gran dimensión. De manera rápida y poco formal, un espacio vectorial es como una caja, llena de etiquetas, donde cada una de ellas contiene información codificada en forma de listas de números. Es importante mencionar que estas etiquetas se denominan vectores y que el número de números (valga la redundancia) que están escritos en cada etiqueta viene dado por la dimensión del espacio.

Así, por ejemplo, podríamos ver el espacio tridimensional que nos rodea como una caja donde todas sus etiquetas se encuentran escritas de la forma (x,y,z). Tanto x, como y o z, pueden tomar cualquier número real, pero cada combinación de las tres debe ser única. Estas dimensiones tienen un significado físico, ya que representan el desplazamiento en cada uno de los tres ejes que empleamos como sistemas de referencia, es decir, el número de direcciones independientes que hay: arriba/abajo, izquierda/derecha y  adelante/atrás. A lo largo de esta entrada emplearemos el término vector, individuo indistintamente. Cada uno de los números de un vector los  denominaremos como atributo o componente.

Si bien nuestros sentidos sólo perciben hasta tres dimensiones espaciales, tiene sentido hablar de más dimensiones con el objetivo de codificar características sobre elementos de nuestro interés. En un espacio de cuatro dimensiones, dispondríamos, por así decirlo, de cuatro números para caracterizar lo que quisiéramos  Por ejemplo, podríamos ver a una persona como un vector cuyas cuatro componentes fueran las siguientes.

persona = (altura, peso, cociente intelectual, ingresos)

Con múltiples muestras de esta información podríamos hacer muchas cosas, como, por ejemplo, determinar si tiene estudios universitarios.  La dura realidad es que existen aplicaciones en las que cada uno de sus "individuos" no puede ser descrito con tres o cuatro dimensiones, sino que puede necesitar del orden de miles o millones de ellas.

Esto plantea un problema: el volumen de una región crece de manera desproporcionada a lo que es la dimensión del mismo. Lo que es lo mismo, el volumen de un cubo de dimensión tres, es minúsculo comparado con un cubo de dimensión, digamos, 10. Además, la distribución de este volumen también cambia, hecho que se ve reflejado en la figura que sigue a estas líneas.

Efectos del incremento en el número de dimensiones sobre el volumen de una región. Extraído de [2].

Aquí se ve el cubo unidad (aquel cubo que tiene de lado una unidad) y una pequeña región, de la misma forma, en su interior. La gráfica de la derecha, muestra en el eje x la fracción de volumen contenida a la distancia que se aprecia en el eje y.

Básicamente, los distintos trazados muestran como esta relación varía para distintas dimensiones. Conforme nos desplazamos hacia arriba en la gráfica, es como si estiráramos todos los lados del cubo a la vez, hasta llegar a uno, momento en el cual el volumen de la región alcanzaría el del cubo unidad.
Un cubo de dimensión uno, es una línea recta, por lo que su "volumen" se va llenando hasta llegar a uno, de manera lineal, es decir a cada paso que incrementamos el lado, el volumen cubierto es proporcional.

El caso de dos y tres dimensiones (un cuadrado y un cubo, respectivamente) el volumen de la vecindad no se llena proporcionalmente, pero sigue siendo aceptable la distribución respecto de la distancia al centro. Finalmente, y es aquí donde se empieza a hacer patente la maldición, para el caso de 10 dimensiones, más de la mitad del volumen (52%) se encuentra más cerca de la frontera que del centro  (recordemos que la distancia máxima es uno). Estas perspectivas empeoran conforme la dimensión aumenta, pudiendo afirmar sin miedo que casi todo el volumen de una región p-dimensional se encuentra en sus bordes.

Para entender esto hay que desligarse de la concepción que tenemos del volumen. Cuando pensamos en un cubo, pensamos que el volumen está contenido cerca del centro (¡y así es!), porque el volumen cercano al borde es muy fino. Esta afirmación sigue cumpliéndose para cubos de dimensión superior, sólo que en este caso el borde pese a seguir siendo fino, también es enorme. Pese a que sea fino, es tan vasto que acapara todo el volumen de la región.

Si los individuos de nuestro problema se encuentran en un espacio con muchas dimensiones, surgen los dos problemas elementales siguientes:

• ¿Como es posible disponer de medidas estadísticas significativas? Si tenemos un número moderado de muestras, pero muchísimas dimensiones, cada una de ellas cubrirá una porción pequeña del espacio. Esto plantea el problema de que es necesario incrementar el número de muestras para poder sacar conclusiones. Esto es un problema porque, por lo general, las muestras o ejemplos son difíciles de conseguir en el mundo real.
• ¿Como medimos la similitud entre individuos? Esto se relaciona directamente con la figura anterior. Por lo general, existen métodos que predicen el resultado calculando la distancia (puede verse la distancia entre dos puntos como lo similares que son) de un nuevo ejemplo respecto de los ejemplos que se conocen. Para esto se basa en encontrar qué vecino se encuentra más cerca de este nuevo ejemplo. Esto se realiza construyendo una vecindad similar a la de la figura anterior, sólo que de forma esférica, en el centro de este nuevo ejemplo. Si la dimensión es muy grande no habrá nada realmente cerca, sino que se encontrará todo en el borde de ésta, lo cual empeora bastante los resultados.

Para terminar y dar un poco de esperanza, os planteo una pregunta: ¿y si realmente no hicieran falta todas estas dimensiones?. Es decir, si de esas miles de dimensiones, pudiéramos quedarnos con las importantes. Y más aún ¿y si pudiéramos eliminar de golpe algunas? 

Anteriormente, veíamos en nuestro ejemplo, que una persona podía describirse como un punto en un espacio de cuatro dimensiones. La idea era, a partir de muchas muestras con  cuatro atributos cada una, determinar el nivel de estudios de una persona, es decir, si tenía estudios superiores o no.  Antes de ponerse manos a la obra y resolver el problema, sería interesante averiguar si ciertos atributos pueden ser eliminados. Por ejemplo, es muy probable que el peso y la altura no sean independientes, es decir, que para valores similares de peso, encontraremos en general valores similares de altura. Estos dos atributos pueden verse combinados en una sola, a la que podríamos llamar, por ejemplo, complexión.

Si damos un paso más, tal vez el nivel de ingresos tenga menos importancia de la que creemos a la hora de determinar si una persona tiene estudios universitarios, por lo que puede ser eliminado directamente. Nuestra persona pasaría a tener ahora dos dimensiones en lugar de cuatro.

persona' = (complexión, ingresos)

La misión de las técnicas de reducción de dimensiones es esa: obtener una representación más compacta, intentando mitigar los efectos de la maldición que asola a los espacios de alta dimensión. En concreto, cuando hablábamos de combinar atributos, las técnicas se denominan como extracción de características. Si por el contrario se desea encontrar un grupo de características de entre las originales, se trata de técnicas de selección de características. En cualquier caso, existirá un error, ya sea porque a la hora de representar los datos en una dimensión inferior se pierda información, o por la degradación de las técnicas si se mantiene la dimensionalidad inicial.

Y esto es todo por hoy. La semana que viene, volveré, con algo mucho más light y amigable.

Pepe "Puertas de Acero" Pérez

[1]http://en.wikipedia.org/wiki/Curse_of_dimensionality

[2]Hastie, Tibshirani, Friedman. The Elements Of Statistical Learning
[3]http://en.wikipedia.org/wiki/Dimension_reduction