El filósofo alemán Fredrich Nietzsche dijo una vez que “los hilos invisibles son los lazos más fuertes”. Se podría pensar que los “hilos invisibles” unen objetos relacionados, como las casas en la ruta de un repartidor, o entidades más nebulosas, como transacciones en una red financiera o usuarios en una red social.
El informático Julian Shun estudia estos tipos de conexiones multifacéticas pero a menudo invisibles mediante gráficos, donde los objetos se representan como puntos o vértices, y las relaciones entre ellos se modelan mediante segmentos de línea o aristas.
Shun, un profesor asociado recientemente titular en el Departamento de Ingeniería Eléctrica e Informática, diseña algoritmos gráficos que podrían usarse para encontrar el camino más corto entre hogares en la ruta del conductor de entrega o detectar transacciones fraudulentas realizadas por actores maliciosos en una red financiera.
Pero con el creciente volumen de datos, dichas redes han crecido hasta incluir miles de millones o incluso billones de objetos y conexiones. Para encontrar soluciones eficientes, Shun crea algoritmos de alto rendimiento que aprovechan la computación paralela para analizar rápidamente incluso los gráficos más enormes. Como la programación paralela es notoriamente difícil, también desarrolla marcos de programación fáciles de usar que facilitan a otros escribir sus propios algoritmos gráficos eficientes.
“Si estás buscando algo en un motor de búsqueda o en una red social, querrás obtener resultados muy rápidamente. Si intenta identificar transacciones financieras fraudulentas en un banco, debe hacerlo en tiempo real para minimizar los daños. Los algoritmos paralelos pueden acelerar las cosas mediante el uso de más recursos informáticos”, explica Shun, quien también es investigador principal en el Laboratorio de Ciencias de la Computación e Inteligencia Artificial (CSAIL).
Estos algoritmos se utilizan con frecuencia en los sistemas de recomendación en línea. Busque un producto en un sitio web de comercio electrónico y lo más probable es que vea rápidamente una lista de artículos relacionados que también puede agregar a su carrito. Esa lista se genera con la ayuda de algoritmos gráficos que aprovechan el paralelismo para encontrar rápidamente elementos relacionados en una red masiva de usuarios y productos disponibles.
Conexiones del campus
Cuando era adolescente, la única experiencia de Shun con las computadoras fue una clase de secundaria sobre creación de sitios web. Más interesado en las matemáticas y las ciencias naturales que en la tecnología, tenía la intención de especializarse en una de esas materias cuando se matriculó en la Universidad de California en Berkeley.
Pero durante su primer año, un amigo le recomendó tomar una clase de introducción a la informática. Si bien no estaba seguro de qué esperar, decidió inscribirse.
“Me enamoré de la programación y el diseño de algoritmos. Me cambié a la informática y nunca miré atrás”, recuerda.
Ese curso inicial de informática fue a su propio ritmo, por lo que Shun aprendió por sí mismo la mayor parte del material. Disfrutaba de los aspectos lógicos del desarrollo de algoritmos y del breve circuito de retroalimentación de los problemas informáticos. Shun podía introducir sus soluciones en la computadora y ver inmediatamente si tenía razón o no. Y los errores en las soluciones equivocadas lo guiarían hacia la respuesta correcta.
“Siempre pensé que era divertido crear cosas y, en programación, estás creando soluciones que hacen algo útil. Eso me atrajo”, añade.
Después de graduarse, Shun pasó algún tiempo en la industria pero pronto se dio cuenta de que quería seguir una carrera académica. En la universidad sabía que tendría la libertad de estudiar los problemas que le interesaran.
Entrar en gráficos
Se matriculó como estudiante de posgrado en la Universidad Carnegie Mellon, donde centró su investigación en algoritmos aplicados y computación paralela.
Como estudiante universitario, Shun había tomado clases de algoritmos teóricos y cursos prácticos de programación, pero los dos mundos no conectaban. Quería realizar una investigación que combinara teoría y aplicación. Los algoritmos paralelos encajaban perfectamente.
“En la computación paralela, hay que preocuparse por las aplicaciones prácticas. El objetivo de la computación paralela es acelerar las cosas en la vida real, por lo que si sus algoritmos no son rápidos en la práctica, entonces no son tan útiles”, afirma.
En Carnegie Mellon, conoció los conjuntos de datos gráficos, donde los objetos de una red se modelan como vértices conectados por aristas. Se sintió atraído por las numerosas aplicaciones de este tipo de conjuntos de datos y por el difícil problema de desarrollar algoritmos eficientes para manejarlos.
Después de completar una beca postdoctoral en Berkeley, Shun buscó un puesto docente y decidió unirse al MIT. Había estado colaborando con varios profesores del MIT en investigaciones sobre computación paralela y estaba entusiasmado de unirse a un instituto con tanta experiencia.
En uno de sus primeros proyectos después de unirse al MIT, Shun unió fuerzas con el profesor del Departamento de Ingeniería Eléctrica y Ciencias de la Computación y miembro de CSAIL Saman Amarasinghe, un experto en lenguajes de programación y compiladores, para desarrollar un marco de programación para el procesamiento de gráficos conocido como GraphIt. El marco fácil de usar, que genera código eficiente a partir de especificaciones de alto nivel, funcionó aproximadamente cinco veces más rápido que el siguiente mejor enfoque.
“Esa fue una colaboración muy fructífera. No podría haber creado una solución tan potente si hubiera trabajado solo”, afirma.
Shun también amplió su enfoque de investigación para incluir algoritmos de agrupamiento, que buscan agrupar puntos de datos relacionados. Él y sus estudiantes construyen algoritmos y marcos paralelos para resolver rápidamente problemas complejos de agrupación en clústeres, que pueden usarse para aplicaciones como la detección de anomalías y la detección de comunidades.
Problemas dinámicos
Recientemente, él y sus colaboradores se han centrado en problemas dinámicos en los que los datos de una red de gráficos cambian con el tiempo.
Cuando un conjunto de datos tiene miles de millones o billones de puntos de datos, ejecutar un algoritmo desde cero para realizar un pequeño cambio podría resultar extremadamente costoso desde el punto de vista computacional. Él y sus estudiantes diseñan algoritmos paralelos que procesan muchas actualizaciones al mismo tiempo, mejorando la eficiencia y preservando la precisión.
Pero estos problemas dinámicos también plantean uno de los mayores desafíos que Shun y su equipo deben superar. Debido a que no hay muchos conjuntos de datos dinámicos disponibles para probar algoritmos, el equipo a menudo debe generar datos sintéticos que pueden no ser realistas y podrían obstaculizar el rendimiento de sus algoritmos en el mundo real.
Al final, su objetivo es desarrollar algoritmos de gráficos dinámicos que funcionen de manera eficiente en la práctica y que al mismo tiempo cumplan con las garantías teóricas. Eso garantiza que serán aplicables en una amplia gama de entornos, afirma.
Shun espera que los algoritmos paralelos dinámicos tengan un enfoque de investigación aún mayor en el futuro. A medida que los conjuntos de datos continúan haciéndose más grandes, más complejos y cambian más rápidamente, los investigadores necesitarán crear algoritmos más eficientes para mantenerse al día.
También espera que surjan nuevos desafíos a partir de los avances en la tecnología informática, ya que los investigadores necesitarán diseñar nuevos algoritmos para aprovechar las propiedades del nuevo hardware.
«Esa es la belleza de la investigación: puedo intentar resolver problemas que otras personas no han resuelto antes y contribuir con algo útil a la sociedad», afirma.