Nuevo Algoritmo Reduce el Tiempo de Cómputo en Órdenes de Magnitud

• Un nuevo algoritmo acelera exponencialmente el cómputo reduciendo drásticamente el número de iteraciones requeridas para resolver un problema.
• Funciona mucho mejor que los algoritmos convencionales (secuenciales) en conjuntos de datos a gran escala, como análisis de redes sociales y agrupamiento de datos genéticos.

Miles de problemas de optimización (problema de encontrar la mejor solución de todas las soluciones factibles) como asignar fondos a acciones para minimizar el riesgo en los rendimientos, o asignar empleados a oficinas disponibles para maximizar el flujo de trabajo y el estadístico de empleados, dependen fuertemente de algoritmos secuenciales.

El patrón de funcionamiento básico de estos algoritmos no se ha alterado (mejorado) desde que se establecieron por primera vez a principios de la década de 1970. Resuelven cualquier problema particular secuencialmente en "n" número de pasos.

El número de pasos depende del tamaño del problema (que proporciona ciertos valores al algoritmo como entrada). Este tipo de método suele resultar en un cuello de botella computacional. La ganancia relativa de cada iteración se vuelve cada vez más pequeña a medida que avanza el algoritmo.

¿Qué pasaría si un algoritmo pudiera dar unos pocos saltos, en lugar de dar miles de pequeños pasos para resolver el problema? ¿Qué pasaría si pudiéramos hacer que un gran conjunto de los algoritmos ampliamente utilizados hoy en día funcionen exponencialmente más rápido? Estamos hablando de los algoritmos que nos ayudan a descubrir nuevos fármacos y evitar el tráfico.

Para hacer esto posible, investigadores de la Universidad de Harvard han ideado un nuevo tipo de algoritmo, al que llaman "Breakthrough", que acelera exponencialmente el cómputo reduciendo drásticamente el número de iteraciones requeridas para resolver un problema.

Acelera el cómputo para una amplia gama de problemas en varias áreas diferentes, como extracción de información, diseño de subastas, visión artificial, biología computacional, análisis de redes y más.

Según los desarrolladores, es capaz de realizar grandes cómputos en varios segundos que anteriormente habrían tomado días o semanas. Esto podría abrir las puertas a nuevos enfoques de paralelización a gran escala, permitiendo construir procesos de resumición prácticos a escala excepcional.

¿Cómo Funciona?

Los algoritmos secuenciales funcionan reduciendo el número de soluciones factibles un paso a la vez. Mientras que, el nuevo algoritmo muestrea paralelamente diferentes direcciones, y luego elimina las direcciones menos relevantes y selecciona las más favorables (de alto valor) para llegar a la solución. Descarta selectivamente valores que serán ignorados en futuras iteraciones.

El algoritmo Breakthrough usa muestreo adaptativo | Cortesía de los investigadores

Más específicamente, el algoritmo requiere O(log n) pasos secuenciales y alcanza una aproximación arbitrariamente cercana a 1/3. Al habilitar la paralelización, los algoritmos alcanzan una aproximación de factor constante exponencialmente más rápido que cualquier método existente para maximización submodular.

Referencia: Harvard SEAS | Publicaciones de Harvard

Por ejemplo, si la tarea es recomendar películas similares a Star Wars, un algoritmo convencional agregaría una película en cada paso que tenga atributos similares (acción, aventura, fantasía) a los de Star Wars.

El algoritmo recién desarrollado, por otro lado, muestrea aleatoriamente un conjunto de películas, podando aquellas que no coinciden en absoluto con Star Wars. Esto da una colección diversa de películas (obviamente, no quieres 10 películas de Superman en tu recomendación) que son similares a Star Wars.

El algoritmo continuará agregando variedad de películas en cada paso hasta que tenga suficientes elementos para recomendar. La clave para tomar decisiones valiosas en cada paso reside en el proceso de muestreo adaptativo.

Número de pasos tomados por un algoritmo secuencial (negro) y breakthrough (rojo) para resolver un problema

Pruebas y Aplicaciones

Los investigadores probaron su algoritmo de muestreo adaptativo en un gran conjunto de datos que contenía 1 millón de calificaciones sobre 4.000 películas de 6.000 usuarios. Recomendó exitosamente películas personalizadas y variadas para una persona 20 veces más rápido que los algoritmos convencionales.

También aplicaron este algoritmo en un problema de despacho de taxis – elegir las mejores ubicaciones para atender el máximo número de clientes con taxis limitados. Para 2 millones de viajes en taxi, el algoritmo funcionó 6 veces más rápido que el estado del arte.

Puede producir resultados mucho mejores en conjuntos de datos a gran escala, como análisis de redes sociales o agrupamiento de datos genéticos. Además, el algoritmo podría aplicarse para desarrollar ensayos clínicos para múltiples enfermedades, arrays de sensores para imágenes médicas y detección de interacciones entre fármacos.

Leer: Buscar Nuevo Algoritmo de Vehículo Autónomo Puede Cambiar de Carril Agresivamente

Hoy en día, encontrar un subconjunto efectivo de datos de millones de imágenes/videos para entrenar redes de aprendizaje profundo se ha convertido en una tarea desafiante. Este estudio podría ayudar a extraer subconjuntos valiosos rápidamente y tener un impacto significativo en problemas de resumición de datos a gran escala.