Como puede atestiguar cualquiera que haya usado alguna vez una hoja de cálculo, a menudo resulta conveniente organizar los datos en tablas. Pero en la era de los macrodatos, esas tablas pueden ser enormes, con millones o incluso cientos de millones de filas.
Una forma de hacer que el análisis de macrodatos sea computacionalmente viable consiste en reducir el tamaño de las tablas de datos —o matrices, para usar el término matemático— eliminando un montón de filas. El truco está en que, en cierto sentido, las filas restantes deben ser representativas de las omitidas, para que los cálculos realizados con ellas arrojen resultados aproximadamente correctos.
En junio, durante el Simposio ACM sobre Teoría de la Computación, investigadores del MIT presentarán un nuevo algoritmo que encuentra la aproximación más pequeña posible de la matriz original y garantiza cálculos fiables. Para una clase de problemas importantes en ingeniería y aprendizaje automático, esto supone una mejora significativa respecto de las técnicas anteriores. Y para todas las clases de problemas, el algoritmo encuentra la aproximación con la mayor rapidez posible.
Para determinar hasta qué punto una fila determinada de la matriz condensada representa una fila de la matriz original, el algoritmo debe medir la «distancia» entre ellas. Pero hay distintas formas de definir la «distancia».
Una forma común es la llamada «distancia euclídea». En la distancia euclídea, se elevan al cuadrado las diferencias entre los elementos situados en posiciones correspondientes de las dos filas y se suman; la distancia entre las filas es la raíz cuadrada de esa suma. La intuición se basa en el teorema de Pitágoras: la raíz cuadrada de la suma de los cuadrados de las longitudes de los catetos de un triángulo rectángulo da la longitud de la hipotenusa.
Otra medida de distancia es menos común, pero resulta especialmente útil para resolver problemas de aprendizaje automático y otros problemas de optimización. Se llama «distancia de Manhattan» y consiste simplemente en la suma de las diferencias absolutas entre los elementos correspondientes de las dos filas.
Dentro de la norma
De hecho, tanto la distancia de Manhattan como la distancia euclídea son casos de lo que los estadísticos llaman «normas». La distancia de Manhattan, o norma 1, es la raíz primera de la suma de las diferencias elevadas a la primera potencia, y la distancia euclídea, o norma 2, es la raíz cuadrada de la suma de las diferencias elevadas a la segunda potencia. La norma 3 es la raíz cúbica de la suma de las diferencias elevadas a la tercera potencia, y así sucesivamente hasta el infinito.
En su artículo, los investigadores del MIT —Richard Peng, investigador posdoctoral en matemáticas aplicadas, y Michael Cohen, estudiante de posgrado en ingeniería eléctrica e informática— demuestran que su algoritmo es óptimo para condensar matrices bajo cualquier norma. Pero, según Peng, «la que realmente nos importaba era la norma 1».
En la condensación de matrices —bajo cualquier norma—, el primer paso consiste en asignar un «peso» a cada fila de la matriz original. El peso de una fila representa el número de otras filas a las que se parece y determina la probabilidad de que se incluya en la matriz condensada. Si se incluye, sus valores se multiplicarán según su peso. Así, por ejemplo, si 10 filas son buenos sustitutos unas de otras, pero no de ninguna otra fila de la matriz, cada una tendrá un 10 % de probabilidad de entrar en la matriz condensada. Si una de ellas entra, todos sus elementos se multiplicarán por 10, de modo que refleje la contribución de las otras nueve filas a las que representa.
Aunque la distancia de Manhattan es, en cierto sentido, más sencilla que la distancia euclídea, dificulta el cálculo de los pesos de las filas. Hasta ahora, el mejor algoritmo para condensar matrices bajo la norma 1 producía una matriz cuyo número de filas era proporcional al número de columnas de la matriz original elevado a 2,5. En cambio, el mejor algoritmo para condensar matrices bajo la norma 2 producía una matriz cuyo número de filas era proporcional al número de columnas de la matriz original multiplicado por su propio logaritmo.
Eso significa que, si la matriz tuviera 100 columnas, bajo la norma 1 la mejor condensación posible antes del trabajo de Peng y Cohen era una matriz con cientos de miles de filas. Bajo la norma 2, era una matriz con un par de cientos de filas. Esa discrepancia aumenta a medida que crece el número de columnas.
Domar la recursividad
El algoritmo de Peng y Cohen condensa matrices bajo la norma 1 tan bien como bajo la norma 2; bajo la norma 2, condensa matrices tan bien como sus predecesores. Esto se debe a que, para la norma 2, simplemente utiliza el mejor algoritmo existente. Para la norma 1, utiliza el mismo algoritmo, pero lo aplica cinco o seis veces.
La verdadera aportación del artículo consiste en demostrar matemáticamente que el algoritmo de la norma 2 producirá resultados fiables bajo la norma 1. Como explica Peng, hace tiempo que se conoce una ecuación para calcular los pesos de la norma 1. Pero «lo curioso de esa definición es que es recursiva», afirma. «Así que el conjunto correcto de pesos aparece tanto en el lado izquierdo como en el lado derecho». Es decir, el peso de una fila determinada de la matriz —llamémoslo w — se iguala a una expresión matemática que a su vez incluye w.
«Se sabía que esta definición existía, pero la gente de estadística no sabía qué hacer con ella», dice Peng. «La miran y piensan: “¿Cómo voy a calcular algo con esto?”»
Lo que demuestran Peng y Cohen es que, si se empieza asignando a la w del lado derecho de la ecuación el valor 1, luego se evalúa la expresión y se introduce la respuesta en la w del lado derecho, y después se repite lo mismo una y otra vez, se llegará rápidamente a una buena aproximación del valor correcto de w.
«Es una matemática sumamente elegante y supone un avance significativo respecto de los resultados anteriores», afirma Richard Karp, profesor de informática en la Universidad de California en Berkeley y ganador de la Medalla Nacional de Ciencia y del Premio Turing, el máximo honor en informática. «Reduce el problema original a uno muy fácil de entender. Admiro el desarrollo matemático que lo hizo posible».
Este artículo se publica en colaboración con MIT News. La publicación no implica que el Foro Económico Mundial respalde las opiniones expresadas.
Para mantenerse al día con la Agenda, suscríbase a nuestro boletín semanal.
Autor: Larry Hardesty es colaborador de MIT News.
Imagen: Una ilustración muestra la proyección de un código binario sobre un hombre que sostiene una computadora portátil. REUTERS/Kacper Pempel.
