Ads-728

Ads-728

Psicología

Astrofísica

Genética

Neurociencia

» » Un algoritmo corto de grandes consecuencias

Referencia: Science.Daily.com, 1 de marzo 2013

En la última década, la informática teórica ha desarrollado un progreso notable respecto al problema de resolver los gráficos laplacianos, un nombre esotérico para un tipo de cálculo con hordas de aplicaciones conocidas en programación, procesamiento de imágenes, recomendación de productos en línea, análisis de redes y la computación científica, por nombrar sólo algunas.

Ya en 2004, los primeros investigadores propusieron un algoritmo que resolvía los gráficos laplacianos en un "tiempo casi lineal", lo que significa que el tiempo de ejecución del algoritmo no aumentaba exponencialmente con el tamaño del problema.

Este año, en el Simposio ACM sobre la Teoría de Computación, los investigadores del MIT presentarán un nuevo algoritmo para resolver los gráficos laplacianos, no sólo más rápido que sus predecesores, sino drásticamente más sencillo. "El artículo de 2004 requiere innovaciones fundamentales en múltiples ramas de las matemáticas y de las ciencias de computación, pero acabó siendo dividido en tres artículos que creo que tenían unas 130 páginas en total," apunta Jonathan Kelner, profesor asociado de matemáticas aplicadas en el MIT que dirigió la nueva investigación. "Hemos podido sustituirlo con algo que encaja en una pizarra."

Los investigadores del MIT, Kelner, Lorenzo Orecchia, un instructor de matemáticas aplicadas, y los estudiantes Kelner, Aaron Sidford y Zhu Zeyuan, creen que la simplicidad de su algoritmo podrá hacer que la implementación en software sea más rápida y fácil que sus predecesores. Pero igual de importante que su sencillez es su análisis conceptual que, según los investigadores, resultarán mucho más fácil de generalizar a otros contextos.

Superando la resistencia

Un gráfico laplaciano es una matriz (una rejilla grande de números) que describe un gráfico, una abstracción matemática bastante común en informática. Un gráfico es cualquier colección de nodos, generalmente representados como círculos y aristas, y presentados con líneas que conectan los nodos. En un problema logístico, los nodos pueden representar las tareas a realizar, mientras que en un motor de recomendaciones en línea, pueden representar títulos de películas.

En muchos gráficos, las aristas son "ponderadas", que quiere decir que tienen diferentes números asociados con ellas. Estos números podrían representar el coste (en tiempo, dinero o energía) de pasar de una etapa a otra en una operación logística compleja, o podrían representar las fuertes correlaciones entre las preferencias por unas películas de los usuarios de un servicio de video en línea.

Un gráfico laplaciano describe la ponderación entre todas las aristas, pero también puede ser interpretado como una serie de ecuaciones lineales. Resolver estas ecuaciones es crucial para muchas técnicas de análisis de gráficos.

Una forma intuitiva de pensar acerca de estos gráficos laplacianos es imaginar el gráfico como un gran circuito eléctrico cuyas aristas son como las resistencias. Las ponderaciones de las aristas describen la resistencia de las resistores, la solución laplaciana nos indica la cantidad de corriente que fluye entre dos puntos cualesquiera de la gráfica.

Los enfoques anteriores para su resolución se consideraba una serie de aproximaciones cada vez más simples de la gráfica de interés. La solución es la más sencilla que proporcione una buena aproximación, y la siguiente que proporcione la más simple y buena aproximación, y así sucesivamente. Pero las reglas para construir la secuencia de gráficos podía llegar ser muy compleja, y demuestra que este tipo de soluciones aproximadas a los más complejos requieren de un ingenio matemático considerable.

Retroalimentación

El enfoque de los investigadores del MIT es mucho más sencillo. Lo primero que hacen es encontrar un "árbol de expansión" de la gráfica. Un árbol es un tipo particular de gráfico que no tiene bucles cerrados. Un árbol genealógico puede ser un ejemplo; ahí, el bucle podría significar que alguien tenía padre y hermano de la misma persona. El árbol de expansión de un gráfico es un árbol que toca todos los nodos de la gráfica, pero prescinde de las aristas que crean los bucles. Los algoritmos eficientes para la construcción de árboles de expansión están bien establecidos.

Con el árbol de expansión a mano, el algoritmo del MIT añade tan sólo una de las aristas que faltan, creando un bucle. Un bucle significa que dos nodos están conectados por dos rutas distintas; en la analogía con un circuito, el voltaje tendría que ser el mismo que cruza ambas rutas. Así que los algoritmos marcan los valores del flujo de corriente que balancea el bucle. Entonces se vuelve a agregar otra arista perdida y se reequilibra.

Incluso en una gráfica simple, los valores que balancean un bucle pueden desequilibrar otro. No obstante, los investigadores del MIT han demostrado que, sorprendentemente, este proceso tan simple y repetitivo de añadir aristas y reequilibrar puede converger en una solución del gráfico laplaciano. La demostración de esta convergencia tampoco requiere matemáticas sofisticadas: "Una vez que encuentre la manera correcta de pensar sobre el problema, todo lo demás cae por su propio peso" explica Kelner.

Cambio de paradigma

Daniel Spielman, profesor de matemáticas aplicadas y ciencias de computación en la Universidad de Yale, fue el asesor de la tesis de Kelner y uno de los dos autores del artículo de 2004. Según Spielman, su algoritmo resuelve los laplacianos casi en tiempo lineal "sobre problemas del tamaño astronómico que nunca se encontrarían a menos que el universo sea mucho más grande de lo que conocemos. El algoritmo de Jon y sus colegas es realmente práctico."

Spielman señala que en 2010, los investigadores de la Carnegie Mellon University también presentaron un práctico algoritmo para resolver los laplacianos. El análisis teórico mostraba que el algoritmo del MIT debería ser un poco más rápido, pero, "la extraña realidad de todo esto es el tener que hacer un montón de análisis para asegurarse de que todo funciona, cuando a veces consigues implementarlos con más o menos fortuna. Así pues, tendremos que esperar a ver cuál es realmente el caso."

El valor real del artículo del MIT, subraya Spielman, está en su innovador enfoque teórico. "Mi trabajo y el trabajo de la gente en Carnegie Mellon, trata de resolver un problema de álgebra lineal numérica con técnicas del mismo campo" dice. "Y el artículo de Jon está ignorando por completo todas estas técnicas, y está resolviendo este problema usando ideas del diseño de las estructuras de datos y del algoritmo. Está sustituyendo un conjunto de ideas por otro conjunto de ideas, y creo que viene a ser un poco como un cambio de juego en el campo. Ya que la gente va a poder ver que hay un conjunto de ideas por ahí que puede tener aplicación donde nadie había imaginado."


- Imagen: Estas dos imágenes muestran dos “árboles de expansión” distintos para un gráfico sencillo, con una rejilla similar a la usada en la mayoría de cálculos científicos. Las aceleración que promete el nuevo algoritmo MIT requiere una "baja extensión" de los árboles de expansión (verde), en los cuales las rutas entre nodos vecinos no llegan a ser excesivamente largas (rojo). Crédito, cortesía de los investigadores.
- Fuente: Massachusetts Institute of Technology. Artículo original escrito por Larry Hardesty.
- Publicación: Jonathan A. Kelner, Lorenzo Orecchia, Aaron Sidford, Zeyuan Allen Zhu. A Simple, Combinatorial Algorithm for Solving SDD Systems in Nearly-Linear Time. Submitted to ArXiv, 2013 [enlace].
.

«
Next
Entrada más reciente
»
Previous
Entrada antigua
Editor del blog Pedro Donaire

Filosofía

Educación

Deporte

Tecnología

Materiales