¿Qué pasaría si una gran clase de algoritmos utilizados hoy en día, desde los algoritmos que nos ayudan a evitar el tráfico hasta los algoritmos que identifican nuevas moléculas de medicamentos, funcionaran exponencialmente más rápido?
Los científicos informáticos de la Escuela de Ingeniería y Ciencias Aplicadas John A. Paulson de Harvard SEAS han desarrollado un tipo de algoritmo completamente nuevo, uno que acelera exponencialmente la computación al reducir drásticamente la cantidad de pasos paralelos necesarios para llegar a una solución.
Los investigadores presentarán su enfoque novedoso en dos próximas conferencias: el Simposio de ACM sobre Teoría de la Computación STOC, del 25 al 29 de junio y la Conferencia Internacional sobre Aprendizaje Automático ICML, del 10 al 15 de julio.
Muchos de los llamados problemas de optimización, problemas que encuentran la mejor solución de todas las soluciones posibles, como el mapeo de la ruta más rápida del punto A al punto B, se basan en algoritmos secuenciales que no han cambiado desde que se describieron por primera vez enla década de 1970. Estos algoritmos resuelven un problema siguiendo un proceso secuencial paso a paso. El número de pasos es proporcional al tamaño de los datos. Pero esto ha llevado a un cuello de botella computacional, lo que resulta en líneas de preguntas y áreas de investigación.que son demasiado computacionalmente caras para explorar.
"Estos problemas de optimización tienen una propiedad de rendimiento decreciente", dijo Yaron Singer, Profesor Asistente de Ciencias de la Computación en SEAS y autor principal de la investigación. "A medida que avanza un algoritmo, su ganancia relativa de cada paso se hace cada vez más pequeña".
Singer y su colega preguntaron: ¿qué pasaría si, en lugar de dar cientos o miles de pequeños pasos para llegar a una solución, un algoritmo podría dar unos pocos saltos?
"Este algoritmo y enfoque general nos permite acelerar drásticamente la computación para una clase enormemente grande de problemas en muchos campos diferentes, incluyendo visión por computadora, recuperación de información, análisis de redes, biología computacional, diseño de subastas y muchos otros", dijo Singer"Ahora podemos realizar cálculos en solo unos segundos que anteriormente habrían tomado semanas o meses".
"Este nuevo trabajo algorítmico, y el análisis correspondiente, abre las puertas a nuevas estrategias de paralelización a gran escala que tienen velocidades mucho más grandes que lo que ha sido posible antes", dijo Jeff Bilmes, profesor del Departamento de Ingeniería Eléctrica delUniversidad de Washington, que no participó en la investigación: "Estas habilidades permitirán, por ejemplo, desarrollar procesos de resumen del mundo real a una escala sin precedentes".
Tradicionalmente, los algoritmos para problemas de optimización reducen el espacio de búsqueda para la mejor solución paso a paso. Por el contrario, este nuevo algoritmo muestrea una variedad de direcciones en paralelo. Basado en esa muestra, el algoritmo descarta direcciones de bajo valor desu espacio de búsqueda y elige las direcciones más valiosas para avanzar hacia una solución.
Tome este ejemplo de juguete :
Estás de humor para ver una película similar a The Avengers. Un algoritmo de recomendación tradicional agregaría secuencialmente una sola película en cada paso que tenga atributos similares a los de The Avengers. Por el contrario, el nuevo algoritmo muestra un grupo depelículas al azar, descartando aquellas que son muy diferentes a The Avengers. Lo que queda es un lote de películas que son diversas después de todo, no quieres diez películas de Batman pero similares a The Avengers. El algoritmo continúa agregando lotes encada paso hasta que tenga suficientes películas para recomendar.
Este proceso de muestreo adaptativo es clave para la capacidad del algoritmo de tomar la decisión correcta en cada paso.
"Los algoritmos tradicionales para esta clase de problema agregan datos con avidez a la solución mientras consideran todo el conjunto de datos en cada paso", dijo Eric Balkanski, estudiante graduado de SEAS y coautor de la investigación. "La fortaleza de nuestro algoritmo es queademás de agregar datos, también elimina selectivamente datos que se ignorarán en pasos futuros ".
En experimentos, Singer y Balkanski demostraron que su algoritmo podía filtrar un conjunto de datos que contenía 1 millón de calificaciones de 6,000 usuarios en 4,000 películas y recomendar una colección personalizada y diversa de películas para un usuario individual 20 veces más rápido que el estado de-el arte.
Los investigadores también probaron el algoritmo en un problema de despacho de taxis, donde hay una cierta cantidad de taxis y el objetivo es elegir las mejores ubicaciones para cubrir el número máximo de clientes potenciales. Utilizando un conjunto de datos de dos millones de viajes en taxi dela comisión de taxis y limusinas de la ciudad de Nueva York, el algoritmo de muestreo adaptativo encontró soluciones 6 veces más rápidas.
"Esta brecha aumentaría aún más significativamente en aplicaciones de mayor escala, como la agrupación de datos biológicos, subastas de búsqueda patrocinadas o análisis de redes sociales", dijo Balkanski.
Por supuesto, el potencial del algoritmo se extiende mucho más allá de las recomendaciones de películas y las optimizaciones de despacho de taxis. Podría aplicarse a :
Este proceso de aprendizaje activo es clave para la capacidad del algoritmo de tomar la decisión correcta en cada paso y resuelve el problema de los rendimientos decrecientes.
"Esta investigación es un verdadero avance para la optimización discreta a gran escala", dijo Andreas Krause, profesor de Ciencias de la Computación en ETH Zurich, que no participó en la investigación. "Uno de los mayores desafíos en el aprendizaje automático es encontrar buenos resultados,subconjuntos representativos de datos de grandes colecciones de imágenes o videos para entrenar modelos de aprendizaje automático. Esta investigación podría identificar esos subconjuntos rápidamente y tener un impacto práctico sustancial en estos problemas de resumen de datos a gran escala ".
El modelo de Singer-Balkanski y las variantes del algoritmo desarrollado en el documento también podrían usarse para evaluar más rápidamente la precisión de un modelo de aprendizaje automático, dijo Vahab Mirrokni, científico principal de Google Research, que no participó en la investigación.
"En algunos casos, tenemos un acceso de recuadro negro a la función de precisión del modelo que lleva mucho tiempo calcular", dijo Mirrokni. "Al mismo tiempo, la precisión del modelo informático para muchas configuraciones de funciones se puede hacer en paralelo.Este marco de optimización adaptativa es un gran modelo para estas configuraciones importantes y los conocimientos de las técnicas algorítmicas desarrolladas en este marco pueden tener un profundo impacto en esta importante área de investigación de aprendizaje automático ".
Singer y Balkanski continúan trabajando con los profesionales para implementar el algoritmo.
Fuente de la historia :
Materiales proporcionados por Harvard John A. Paulson School of Engineering and Applied Sciences . Nota: El contenido puede ser editado por estilo y longitud.
Cite esta página :