Un nuevo algoritmo reduce el tiempo de cálculo en órdenes de magnitud

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

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

El patrón de funcionamiento básico de estos algoritmos no ha sido alterado (mejorado) desde que se establecieron por primera vez a principios de los años 1970. Resuelven cualquier problema particular de forma secuencial 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 provocar 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 algunos 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 algoritmos ampliamente utilizados en la actualidad funcionaran exponencialmente más rápido? Hablamos 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, lo que llaman "Breakthrough", que acelera exponencialmente el cálculo al disminuir drásticamente el número de iteraciones necesarias para resolver un problema.

Acelera la computación 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álculos en varios segundos que antes habrían llevado días o semanas. Esto podría abrir las puertas a nuevos enfoques de paralelización a gran escala, permitiendo construir procesos de resumen prácticos a una escala excepcional.

¿Cómo funciona?

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

Algoritmo innovador utiliza muestreo adaptativo | Cortesía de 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 la 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 en cada paso una película que tenga atributos similares (acción, aventura, fantasía) a los de Star Wars.

El algoritmo recientemente desarrollado, por otro lado, toma muestras aleatorias de un conjunto de películas, eliminando aquellas que no coinciden en absoluto con Star Wars. Esto ofrece 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 radica en el proceso de muestreo adaptativo.

Número de pasos que sigue un algoritmo secuencial (negro) y revolucionario (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 en 4.000 películas de 6.000 usuarios. Recomendó con éxito películas personalizadas y variadas para una persona 20 veces más rápido que los algoritmos convencionales.

También aplicaron este algoritmo a un problema de despacho de taxis:elegir las mejores ubicaciones para atender al máximo número de clientes con taxis limitados. Durante 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 agrupación de datos genéticos.  Aparte de esto, el algoritmo podría aplicarse para desarrollar ensayos clínicos para múltiples enfermedades, conjuntos de sensores para imágenes médicas y detectar interacciones entre medicamentos.

Leer:Buscar Nuevo algoritmo para vehículos autónomos que puede cambiar de carril de forma agresiva

Hoy en día, encontrar un subconjunto eficaz de datos a partir de millones de imágenes/vídeos 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 los problemas de resumen de datos a gran escala.