Una red de neuronas artificiales diseña un algoritmo de ordenación que parece más rápido que el quicksort de Hoare

Por Francisco R. Villatoro, el 11 julio, 2020. Categoría(s): Ciencia • Informática • Noticias • Redes de Neuronas • Science ✎ 17

El aprendizaje automático con redes de neuronas artificiales se puede usar para optimizar algoritmos, la llamada inducción neuronal de programas. Se publica en arXiv un algoritmo de ordenación diseñado mediante aprendizaje con refuerzo que parece ser más eficiente que el algoritmo quicksort de C. A. R. Hoare; por supuesto, su complejidad computacional es la misma, O(n log n) operaciones, pero en los experimentos realizados con 100 secuencias aleatorias de 100 000 números el nuevo algoritmo requiere ~ 92 % del tiempo de ejecución de quicksort (el experimento exigió más de 3 días de tiempo computacional). Siendo más rápido en la práctica, el nuevo algoritmo parece un gran éxito en la generación automática de algoritmos.

Sin embargo, hay un pero. Por desgracia, no se puede demostrar matemáticamente que el nuevo algoritmo funcione de forma correcta (los autores prometen intentarlo en el futuro). La opción obvia para demostrarlo, enumerar todos los posibles casos por fuerza bruta, es inviable. Así, el algoritmo quicksort sigue reinando entre los algoritmos de ordenación. La red de neuronas artificiales fue entrenada para imitar los pasos del algoritmo quicksort (también los algoritmos de burbuja y por inserción) usando 100 conjuntos de entre 5 y 1000 números; luego se usó dicho algoritmo para ordenador 100 conjuntos de 10 000 y otros 100 de 100 000 números. Que los resultados sean correctos en estos experimentos computacionales no garantiza que el nuevo algoritmo funcione siempre de forma correcta. Se requiere una demostración independiente, labor que no es nada fácil, aunque tampoco parece imposible.

El nuevo artículo es Yujia Li, Felix Gimeno, …, Oriol Vinyals, «Strong Generalization and Efficiency in Neural Programs,» arXiv:2007.03629 [cs.LG] (07 Jul 2020); el artículo incluye animaciones donde se compara la ejecución del nuevo algoritmo con los algoritmos clásicos que se imitan. Me he enterado gracias a un tuit de @fan_real_madrid.

El primer autor del artículo ha publicado un tuit con esta animación del algoritmo (los vídeos que promete el artículo como información suplementaria no se incluyen en arXiv; habrá que esperar a su publicación en una revista para disfrutarlos).

Para aprender a diseñar algoritmos hay que usar una representación de las instrucciones válidas, llamada interface view en el artículo; operaciones como comparar dos índices i y j con operadores como <, =, y >, comparar dos números del vector a ordenador A[i] y A[j] con dichos operadores, o comparar A[i] con A[i−1] y A[i+1], entre otras. Los algoritmos a imitar por la red de neuronas (en este artículo bubble sort, insertion sort y quick sort) se codifican a mano usando dichas operaciones válidas. Usando un algoritmo de aprendizaje con refuerzo la red de neuronas aprende a diseñar un algoritmo que realice la misma operación que el algoritmo a imitar. Con un entrenamiento adecuado la red diseña un algoritmo que generaliza el imitado, así como el conjunto de datos de entrenamiento, resultando un algoritmo capaz de ordenador conjuntos hasta 100 veces más grandes de forma (un poco) más eficiente en la práctica. No quiero entrar en los detalles técnicos, pero debo destacar que en el artículo se presenta un ejemplo de entrenamiento inadecuado que conlleva que la red no sea capaz de generalizar más allá del conjunto de entrenamiento, obteniendo algoritmos que solo funcionan para vectores con un tamaño similar a los de entrenamiento.

Los resultados para el aprendizaje con refuerzo con imitación (RL + imitation) de algoritmos de coste computacional O(n²), como los algoritmos de burbuja y por inserción, son similares a los obtenidos en la imitación del algoritmo quicksort de coste computacional O(n log n); solo se obtiene una pequeña mejora el tiempo final de cómputo. Así la red de neuronas artificiales es incapaz de descubrir un algoritmo como quicksort al tratar de imitar un algoritmo por inserción, por ejemplo. Más aún, si en el aprendizaje con refuerzo se realiza desde cero (RL from scratch), sin el profesor al que imitar, el algoritmo obtenido es bastante pobre, con un coste O(n²) y un tiempo de cómputo comparable al del algoritmo por inserción. El profesor al que imitar (y mejorar) parece imprescindible.

En resumen, un artículo curioso e interesante que apunta a que las técnicas automáticas de optimización de algoritmos basadas en aprendizaje automático con refuerzo son muy prometedoras. Su aplicación a algoritmos para problemas NP-completos y NP-duros podría ofrecer sorpresas interesantes. Hay mucho camino por recorrer en el campo de la inducción automática de programas. Por ello habrá que estar al tanto de sus futuros progresos.



17 Comentarios

  1. Como ingeniero informático, este artículo me deja alucinado…Y aún más las aparentes puertas que se abren en el futuro! Un saludo!

  2. Solo notar que QuickSort es O(n^2) en el peor de los casos, aunque su complejidad amortizada (por su naturaleza aleatoria) si seria de O(n log n). Merge sort en todo caso siempre es O(n log n), aunque tiene una constante superior, con lo que es menos eficiente que el QuickSort en promedio.

  3. Tan familiar nos es hoy en día el quicksort que había olvidado que es el más eficiente…me pregunto qué pequeñas mejoras tendrá el nuevo….

  4. Quicksort no es el algoritmo genérico de ordenación más eficiente. Binsort o PostalSort ordenan en O(n), por ejemplo y de hecho, en algoritmos como bwt que tienen un paso de ordenacion, usan éstos o similares, pero no quicksort.
    Si que es el más eficiente, junto con merge sort, de los algoritmos de ordenación por comparación.

    1. Gowen:

      Una pregunta de lego: ¿Es «Postman’s sort» es un algortimo de ordenación genérico más eficiente que Quicksort? Mi pregunta va sobre todo por el adjetivo «genérico». Tenía entendido que este tipo de algoritmos «Bucket Sort» hacen uso de ciertas hipótesis en el conjunto de objetos a ser ordenado (por ejemplo, que están normalmente distribuidos), no me queda claro que en el caso genérico sean más eficientes que Quicksort.¿Tenéis alguna referencia?

      Es muy interesante leer: Why is quicksort better than other sorting algorithms in practice? https://cs.stackexchange.com/questions/3/why-is-quicksort-better-than-other-sorting-algorithms-in-practice?newreg=8e8c3e6a679944bbb229e8ab025fb268 . Aunque este es un tema diferente (eficiencia práctica contra eficiencia teórica).

      Saludos.

  5. Hola Francis,
    Como dices, es un campo muy interesante, que se aplica ya a problemas clásicos de la informática como el scheduling, partición de grafos, o modelado de comunicaciones, con resultados prometedores. Aunque como bien explicas, los algoritmos generados tienen difícil demostración y análisis.
    En la UEx estamos tratando de explorar estos temas aplicados a la computación de altas prestaciones.
    Saludos,
    Juan Antonio.

  6. Hola Francis

    Gracias por la entrada, es súper interesante.

    ¿Qué ocurriría si tras ejecutar este algoritmo se hace una pasada sobre el array resultante para comprobar que efectivamente esté bien ordenado (complejidad O(n))?

    Entiendo que la complejidad seguiría siendo O(n * log n) porque O(n) + O(n * log n) = O(n * log n)
    ¿Puede que para ciertos n la ejecución siga siendo más rápida que quicksort? ¿O habría que determinarlo experimentalmente para saberlo?

  7. Hola Francis,

    recomiendas algún libro a nivel divulgativo para aprender sobre estas cosas?: tipos de algoritmos comunes, complejidad computacional, computación, etc.

    Soy ingeniero pero de rama industrial y me interesaría aprender más sobre estas cosas.

    Gracias

    1. a) Genéricos, sin tocar ningún lenguaje concreto : El de Brassard y Bratley «Fundamentos de algorítmica», Prentice-Hall, es un clásico al respecto. También, aunque más matemático, de los mismos autores » Algorítmica. Concepción y análisis» de los mismos autores, Ed. Masson; y Comen, Leiserson, Rivest «Introduction to algorithms» MIT press.
      b) Orientados a lenguajes de programación, cualquiera de los de Joyanes.
      Hay muchos más, aunque en esto, como en todo también va en gustos y manías de cada uno.
      Saludos.

      1. Pues el que tenía en mente es el algoritmo de aproximación de corte máximo de Goemans-Williamson, pero no parece que compartan la IA tan fácilmente al parecer y no tengo el conocimiento para realizar una parecida…

        1. Andrés, no entiendo bien, ¿quieres usar una red neuronal para optimizar el algoritmo max-cut de optimización convexa? ¿O quieres implementar dicho algoritmo con redes neuronales? ¿O solo quieres implementar dicho algoritmo? No entiendo qué quieres hacer.

Deja un comentario