• Home
  • Química
  • Astronomía
  • Energía
  • Naturaleza
  • Biología
  • Física
  • Electrónica
  • Un algoritmo revolucionario exponencialmente más rápido que cualquier otro anterior

    Crédito:CC0 Public Domain

    ¿Qué pasaría si una gran clase de algoritmos utilizados en la actualidad, desde los que nos ayudan a evitar el tráfico hasta los algoritmos que identifican nuevas moléculas de fármacos, funcionaran exponencialmente más rápido?

    Los informáticos de la Escuela de Ingeniería y Ciencias Aplicadas (SEAS) de Harvard John A. Paulson han desarrollado un tipo de algoritmo completamente nuevo, uno que acelera exponencialmente el cálculo al reducir drásticamente el número de pasos paralelos necesarios para llegar a una solución.

    Los investigadores presentarán su enfoque novedoso en dos próximas conferencias:el Simposio ACM sobre Teoría de la Computación (STOC), 25-29 de junio y Conferencia Internacional sobre Aprendizaje Automático (ICML), 10 al 15 de julio.

    Muchos de los llamados problemas de optimización, problemas que encuentran la mejor solución entre todas las soluciones posibles, como mapear la ruta más rápida desde el punto A al punto B, dependen de algoritmos secuenciales que no han cambiado desde que se describieron por primera vez en la 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, resultando en líneas de preguntas y áreas de investigación que son demasiado costosas desde el punto de vista computacional 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:¿y si, en lugar de dar cientos o miles de pequeños pasos para llegar a una solución, ¿Un algoritmo podría dar solo unos pocos saltos?

    "Este algoritmo y enfoque general nos permite acelerar drásticamente la computación para una clase enorme de problemas en muchos campos diferentes, incluida la visión por computadora, recuperación de información, análisis de red, Biología Computacional, diseño de subasta, y muchos otros, ", dijo Singer." Ahora podemos realizar cálculos en solo unos segundos que antes hubieran 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 aceleraciones mucho mayores de lo que ha sido posible antes, "dijo Jeff Bilmes, Profesor del Departamento de Ingeniería Eléctrica de la Universidad de Washington, que no participó en la investigación. "Estas habilidades por ejemplo, permitir que los procesos de resumen del mundo real se desarrollen a una escala sin precedentes ".

    Tradicionalmente, Los algoritmos para problemas de optimización reducen paso a paso el espacio de búsqueda de la mejor solución. A diferencia de, este nuevo algoritmo muestrea una variedad de direcciones en paralelo. Basado en esa muestra, el algoritmo descarta las direcciones de bajo valor de su 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 Los Vengadores. Un algoritmo de recomendación tradicional agregaría secuencialmente una sola película en cada paso que tiene atributos similares a los de Los Vengadores. A diferencia de, el nuevo algoritmo muestrea un grupo de películas al azar, descartando aquellos que son demasiado diferentes a Los Vengadores. Lo que queda es un lote de películas que son diversas (después de todo, no quieres diez películas de Batman) pero similar a Los Vengadores. El algoritmo continúa agregando lotes en cada paso hasta que tiene 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 problemas agregan datos con avidez a la solución mientras consideran el conjunto de datos completo en cada paso, "dijo Eric Balkanski, estudiante de posgrado en SEAS y coautor de la investigación. "La fortaleza de nuestro algoritmo es que, además de agregar datos, también elimina de forma selectiva los datos que se ignorarán en pasos futuros ".

    En experimentos, Singer y Balkanski demostraron que su algoritmo podía examinar un conjunto de datos que contenía 1 millón de calificaciones de 6, 000 usuarios en 4, 000 películas y recomiende una colección personalizada y diversa de películas para un usuario individual 20 veces más rápido que el estado de la técnica.

    Los investigadores también probaron el algoritmo en un problema de despacho de taxis, donde hay un cierto número 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 de la comisión de taxis y limusinas de la ciudad de Nueva York, el algoritmo de muestreo adaptativo encontró soluciones 6 veces más rápido.

    "Esta brecha aumentaría aún más significativamente en aplicaciones de mayor escala, como agrupar 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 envío de taxis. Podría aplicarse a:

    • diseñar ensayos clínicos de fármacos para tratar la enfermedad de Alzheimer, esclerosis múltiple, obesidad, diabetes, hepatitis C, VIH y más
    • biología evolutiva para encontrar buenos subconjuntos representativos de diferentes colecciones de genes a partir de grandes conjuntos de datos de genes de diferentes especies
    • diseño de matrices de sensores para imágenes médicas
    • Identificar la detección de interacciones medicamentosas en foros de salud en línea.

    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 gran 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 del aprendizaje automático es encontrar buenos 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 caja negra a la función de precisión del modelo que requiere mucho tiempo para calcular, "dijo Mirrokni." Al mismo tiempo, La precisión del modelo de cálculo para muchas configuraciones de características se puede realizar 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 impacto profundo en esta importante área de la investigación del aprendizaje automático ".

    Singer y Balkanski continúan trabajando con los profesionales en la implementación del algoritmo.


    © Ciencia http://es.scienceaq.com