AlphaDev es un sistema de inteligencia artificial desarrollado por Google DeepMind para descubrir algoritmos informáticos mejorados mediante aprendizaje por refuerzo . AlphaDev se basa en AlphaZero , un sistema que dominaba los juegos de ajedrez , shogi y go mediante el juego propio. AlphaDev aplica el mismo enfoque para encontrar algoritmos más rápidos para tareas fundamentales como la clasificación y el hash . [1] [2] [3]
El 7 de junio de 2023, Google DeepMind publicó un artículo en Nature en el que presentaba AlphaDev, que descubrió nuevos algoritmos que superaban a los métodos de última generación para algoritmos de ordenación pequeños. [1] Por ejemplo, AlphaDev encontró una secuencia de lenguaje ensamblador más rápida para ordenar secuencias de 5 elementos. [4] Al analizar los algoritmos en profundidad, AlphaDev descubrió dos secuencias únicas de instrucciones de ensamblaje llamadas movimientos de intercambio y copia de AlphaDev que evitan una sola instrucción de ensamblaje cada vez que se aplican. [1] [3] Para los algoritmos de ordenación variable, AlphaDev descubrió estructuras de algoritmos fundamentalmente diferentes. Por ejemplo, para VarSort4 (ordenación de hasta 4 elementos), AlphaDev descubrió un algoritmo 29 instrucciones de ensamblaje más corto que el parámetro de referencia humano. [1] AlphaDev también mejoró la velocidad de los algoritmos hash hasta en un 30% en ciertos casos. [2]
En enero de 2022, Google DeepMind presentó sus nuevos algoritmos de ordenación a la organización que administra C++ , uno de los lenguajes de programación más populares del mundo, y después de una evaluación independiente, los algoritmos de AlphaDev se agregaron a la biblioteca. [5] Este fue el primer cambio en los algoritmos de ordenación de la biblioteca estándar de C++ en más de una década y la primera actualización que involucró un algoritmo descubierto mediante IA. [5] En enero de 2023, DeepMind también agregó su algoritmo hash para entradas de 9 a 16 bytes a Abseil, una colección de código abierto de algoritmos C++ preescritos que puede usar cualquier persona que codifique con C++. [6] [5] Google estima que estos dos algoritmos se utilizan billones de veces al día. [7]
AlphaDev está construido sobre AlphaZero, el modelo de aprendizaje por refuerzo que DeepMind entrenó para dominar juegos como Go y ajedrez. [5] El gran avance de la compañía fue tratar el problema de encontrar un algoritmo más rápido como un juego y luego entrenar a su IA para ganarlo. [2] AlphaDev juega un juego para un solo jugador donde el objetivo es construir iterativamente un algoritmo en lenguaje ensamblador que sea rápido y correcto. [1] AlphaDev usa una red neuronal para guiar su búsqueda de movimientos óptimos y aprende de su propia experiencia y demostraciones sintéticas. [1]
AlphaDev muestra el potencial de la IA para hacer avanzar las bases de la informática y optimizar el código para distintos criterios. Google DeepMind espera que AlphaDev inspire más investigaciones sobre el uso de la IA para descubrir nuevos algoritmos y mejorar los existentes. [2]
El algoritmo de aprendizaje principal en AlphaDev es una extensión de AlphaZero .
Para utilizar AlphaZero en la programación en ensamblaje, los autores crearon una representación vectorial basada en Transformer de los programas en ensamblaje, diseñada para capturar su estructura subyacente. [1] Esta representación finita permite que una red neuronal juegue a la programación en ensamblaje como un juego con un número finito de movimientos posibles (como Go).
La representación utiliza los siguientes componentes:
El estado del juego es el programa de ensamblaje generado hasta un punto determinado.
El movimiento del juego es una instrucción adicional agregada al programa de ensamblaje actual.
La recompensa del juego es una función de la corrección y la latencia del programa de ensamblaje. Para reducir los costos, AlphaDev solo calcula la latencia medida real en menos del 0,002 % de los programas generados, ya que no evalúa la latencia durante el proceso de búsqueda. En cambio, utiliza dos funciones que estiman la corrección y la latencia mediante el entrenamiento a través del aprendizaje supervisado utilizando los valores reales de corrección y latencia medidos.
AlphaDev desarrolló algoritmos hash para entradas de 9 a 16 bytes para Abseil, una colección de código abierto de algoritmos C++ preescritos. [8]
AlphaDev descubrió nuevos algoritmos de ordenamiento que llevaron a mejoras de hasta un 70 % en la biblioteca de ordenamiento libc++ de LLVM para secuencias más cortas y mejoras de aproximadamente un 1,7 % para secuencias que superan los 250 000 elementos. Estas mejoras se aplican a los tipos de datos uint32, uint64 y float para arquitecturas de CPU ARMv8, Intel Skylake y AMD Zen 2. El ensamblaje condicional sin ramificaciones de AlphaDev y el nuevo movimiento de intercambio contribuyeron a estas mejoras de rendimiento. Los algoritmos descubiertos se diseñaron de manera inversa desde el ensamblaje de bajo nivel a C++ y se incluyeron oficialmente en la biblioteca de ordenamiento estándar libc++. [6]
AlphaDev aprendió una función de deserialización VarInt optimizada en protobuf [ 9], que supera el parámetro de referencia humano para entradas de un solo valor aproximadamente tres veces en términos de velocidad. AlphaDev también descubrió un nuevo movimiento de asignación VarInt, que combina dos operaciones en una sola instrucción para ahorrar latencia.
El rendimiento de AlphaDev se comparó con la superoptimización estocástica, [10] un enfoque de IA lógica. Esta última se ejecutó con al menos la misma cantidad de recursos y tiempo de reloj que AlphaDev. Los resultados mostraron que AlphaDev-S requiere una cantidad prohibitiva de tiempo para optimizar directamente la latencia, ya que la latencia debe calcularse después de cada mutación. Como tal, AlphaDev-S optimiza para un proxy de latencia, específicamente la longitud del algoritmo y, luego, al final del entrenamiento, se buscan todos los programas correctos generados por AlphaDev-S.