AlphaDev: La IA que optimiza la implementación de los algoritmos mejor que los humanos

Ayer sábado cayó en mis manos el artículo académico publicado en la revista Nature sobre AlphaDev, la I.A. que se ha utilizado para optimizar los algoritmos básicos de programación, que ha logrado hacer mejores implementaciones que las que hemos logrado hacer los seres humanos, en problemas tan de base como los algoritmos de ordenación. Y no me he resistido a hablaros de él.

Figura 1: AlphaDev: La IA que optimiza la implementación

de los algoritmos mejor que los humanos

Y es que, para mí, la programación de algoritmos de ordenación ha sido casi un juego toda mi vida. Comienzas haciendo algoritmos de ordenación basados en la burbuja, y sigues implementando soluciones hasta que llegas a soluciones O(nLog(n)) como QuickSort. Y cuando llegas a algorítmica óptima, tienes que pasar a la siguiente fase, a la implementación en lenguaje de alto nivel más optima posible, para que esta codificación se estandarice, y sea compilado en código ensamblandor, código intermedio, o código máquina más optimizado posible. 

Figura 2: Artículo de "Faster sorting algorithms discovered using Deep Reinforcement Learning

En esta optimización, se busca la mejora de uno o de todos los parámetros de medición que sean relevantes para nosotros, como puede ser el número de instrucciones, la latencia o los ciclos de reloj que consume el programa completo en el modelo teórico, en la media de los casos o en caso más probable. La optimización es un arte de buscar el mejor resultado posible para la ejecución completa del problema.

Figura 3: AlpahDev ha descubierto mejores algoritmos Sort

Y por eso, leer en el artículo que AlphaDev ha conseguido superar en las implementaciones de los algoritmos Sort estáticos, y dinámicos para diferentes tamaños de datos de entrada, tanto en número de instrucciones como en latencia de ejecución al estado del arte de los algoritmos que hemos creado los humanos, me capturó al instante la atención.

Porque una mejora en un algoritmo como Sort para tres elementos, se utiliza tantas y tantas, y tantas veces en los programas que utilizamos constantemente, que el impacto que puede tener es brutal en temas como la eficiencia, el consumo energético o la velocidad de resolución de problemas complejos en equipos de menor capacidad de computo. 

Al final, que es el debate que tenía con uno de mis amigos, durante décadas llevamos alejándonos de la máquina para programar. Nos hemos abstraído, pasando de pensar y codificar algoritmos de forma eficiente, a utilizar objetos, luego componentes, después APIs, y por último I.A, a la que le decimos qué queremos que haga pero no nos importa mucho cómo lo haga con las estrategias de NoCode o LowCode. Lo que es casi anatema con la eficiencia algorítmica.

Figura 4: Mejoras obtenidas en algoritmos de Sort obtenidas con AlphaDev

Hemos fiado a la implementación de las capas inferiores la optimización de los pequeños detalles de lo que queríamos construir con software, y ahora usamos esa I.A. para hacer ese trabajo también. Y es como subir hacia arriba en la escala de distanciamiento del lenguaje más básico hasta crear la I.A. necesaria que permita bajar otra vez a lo más bajo nivel para hacer ese trabajo.

El problema, tal y como lo han plateado el equipo de AlphaDev ha sido similar al que hemos visto para cualquier otro juego como el Ajedrez o el Go. Un algoritmo de Deep Reinforcement Learning para que una I.A. busque el algoritmo más eficiente. Solo que en lugar de enseñarle a mover el caballo, la reina o el rey, se le enseña para qué sirve cada una de las instrucciones básicas de un microprocesador, y se le pide que gane la partida de la mejor forma.

Figura 5: La algorítmica como resolución de un juego

Es decir, imaginad el problema del Sort de tres elementos A,B,C. Las salidas posibles pueden ser ABC, ACB, BAC, BCA, CAB, CBA dependiendo si el mayor, el medio o el menor entran en un orden u otro como forma de solucionarlo. Dado esto, AlpaDev tenía que resolver ese "juego" consiguiendo que la combinación de instrucciones resolviera el problema en todos los casos, y que se optimizara primero el número de instrucciones y luego la latencia de ejecución - que es algo aún mucho más a bajo nivel donde se toman en cuenta los ciclos de ejecución -. Y por supuesto, lo hace.

Figura 6: La diferencia entre las estrategias implementadas

Los resultados han sido que para diferentes algoritmos de ordenación fija y variable ha conseguido superar, en todos los casos, al estado del arte de los algoritmos implementados por los humanos, utilizando diferentes implementaciones. Y es espectacular. En el caso del algoritmo Sort de tres elementos, consigue resolver el problema con un movimiento curioso.

Al final, pasa de resolver el problema de una forma en la que el primer elemento es el mínimo de los tres, y el último el valor máximo de los tres para que el que quede sea el del medio, a hacer una ordenación de un subconjunto de dos elementos y hacer una inserción del tercero en la lista ordenada de los dos primeros. Como hace el QuickSort a alto nivel. Y eso, implementado en código de instrucciones es una línea menos.

Figura 7: Una línea menos en la implementación de AlphaDev

Pero lo importante es que, estos códigos, una vez visto que AlphaDev es capaz de encontrar estas soluciones primando el objetivo en líneas de código o latencia, y siendo entrenado para el conjunto concreto de las instrucciones de cada uno de los microprocesadores donde vaya a ejecutarse, la eficiencia en tiempo, en recursos de computación y energía, puede ser brutal.

Figura 8: Libro de Machine Learning aplicado a Ciberseguridad de
Carmen Torrano, Fran Ramírez, Paloma Recuero, José Torres y Santiago Hernández.

Y algoritmos muy complejos, podrían ser ejecutados mucho mejor, haciendo que aquellos que son más complejos se vean beneficiados. Como los complejos algoritmos de Machine Learning e Inteligencia Artificial. Y cuando podamos utilizar estas estrategias no con solo 130 instrucciones de un microprocesador, sino con las mismas herramientas que usamos hoy en día nosotros para programar a alto nivel, se podrán optimizar soluciones de hacking y de seguridad informática de forma diferente. ¿No es maravilloso?

¡Saludos Malignos!

Autor: Chema Alonso (Contactar con Chema Alonso)