![](http://www.technologyreview.es/sites/default/files/mit-images/feed_mit_image_2570_MIA.jpeg)
Inteligencia Artificial
Un 70% más rápido: DeepMind desafía los límites de los algoritmos de ordenación
Millones de desarrolladores ya utilizan los algoritmos generados por la IA
Continúa la racha de descubrimientos de DeepMind en las ciencias informáticas fundamentales. En 2022, Google utilizó una versión de su inteligencia artificial AlphaZero para encontrar nuevas formas de acelerar el cálculo de una pieza matemática crucial en el corazón de diferentes códigos, batiendo un récord que llevaba vigente 50 años.
Ahora, ha vuelto a realizar el mismo truco, dos veces. La empresa, con sede en el Reino Unido, fue rebautizada como Google DeepMind tras fusionarse en abril con el laboratorio de IA de su empresa hermana. Una nueva versión de AlphaZero, llamada AlphaDev, ha descubierto una forma de ordenar los elementos de una lista hasta un 70% más rápidamente que el mejor método existente.
Además, ha encontrado la forma de acelerar en un 30% un algoritmo clave utilizado en criptografía. Estos algoritmos son uno de los componentes más comunes del software. Los pequeños aumentos de velocidad pueden suponer una gran diferencia, reducir costes y ahorrar energía.
"La Ley de Moore está llegando a su fin, los chips se acercan a sus límites físicos fundamentales", afirma Daniel Mankowitz, científico investigador de Google DeepMind. "Tenemos que encontrar formas novedosas e innovadoras de optimizar la computación".
"Es un enfoque nuevo e interesante", asegura Peter Sanders, que estudia el diseño y la implementación de algoritmos eficientes en el Instituto de Tecnología de Karlsruhe (Alemania) y que no participó en el trabajo. "La clasificación sigue siendo una de las subrutinas más utilizadas en informática".
DeepMind publicó sus resultados en Nature, este 7 de junio, pero las técnicas que descubrió AlphaDev ya están siendo utilizadas por millones de desarrolladores de software. En enero de 2022, DeepMind presentó sus nuevos algoritmos de clasificación a la organización que gestiona C++, uno de los lenguajes de programación más populares del mundo. Tras dos meses de riguroso escrutinio independiente, los algoritmos de AlphaDev se añadieron al lenguaje. Este ha sido el primer cambio en los algoritmos de clasificación de C++ en más de una década, y la primera actualización de un algoritmo descubierto mediante IA.
DeepMind ha añadido sus otros nuevos algoritmos a Abseil, una colección de código abierto de algoritmos C++ ya preescritos y que puede utilizarse por cualquiera que codifique con C++. Estos algoritmos criptográficos calculan números hashes, que pueden utilizarse como identificadores únicos para cualquier tipo de datos. DeepMind calcula que sus nuevos algoritmos se utilizan trillones de veces cada día.
AlphaDev se basa en AlphaZero, el modelo de aprendizaje por refuerzo que DeepMind entrenó para dominar juegos como Go o el ajedrez. Este avance de consistió en solucionar el problema de encontrar un algoritmo más rápido, como un juego, y hacer que su IA lo ganara. Es el mismo método que utilizó para acelerar los cálculos en la investigación de 2022.
En el caso de AlphaDev, el juego consiste en elegir instrucciones informáticas y ordenarlas, de modo que las líneas de código resultantes conformen un algoritmo. AlphaDev gana la partida si el algoritmo es tanto correcto como más rápido que los ya existentes. En principio, parece sencillo pero, para jugar bien, AlphaDev debe buscar entre un número astronómico de posibles movimientos.
DeepMind decidió trabajar con el lenguaje ensamblador, un tipo de programación que puede utilizarse para dar instrucciones específicas sobre cómo mover números en un chip para ordenador. Pocas personas escriben en este lenguaje, pues es al que se traduce el código escrito en lenguajes como C++ antes de ejecutarlo. La ventaja del ensamblador es que permite dividir los algoritmos en pasos detallados, un buen punto de partida si se buscan atajos.
Los chips de ordenador tienen diferentes ranuras donde se colocan y procesan los números. El lenguaje ensamblador incluye instrucciones básicas para manipular lo que hay en estos espacios. Como mov(A,B), que indica a un ordenador que mueva el número que hay en el espacio A a la ranura B; y cmp(A,B), que indica al ordenador que compruebe si lo que hay en el espacio A es menor, igual o mayor que lo que hay en el B. Las secuencias largas de estas instrucciones pueden ocupar toda la capacidad de los ordenadores.
AlphaDev realizó un gran movimiento al añadir una nueva instrucción en lenguaje ensamblador al algoritmo que está construyendo. Al principio, AlphaDev añadía instrucciones al azar, generando algoritmos que no se ejecutaban. Con el tiempo, igual que AlphaZero hizo con los juegos de mesa, aprendió a realizar jugadas ganadoras. Añadió instrucciones que condujeron a algoritmos que no solo funcionaban, sino que además eran correctos y rápidos.
DeepMind se centró en algoritmos para ordenar listas cortas de tres a cinco elementos. Estos algoritmos son llamados una y otra vez en programas que ordenan listas más largas. Por tanto, la aceleración de estos algoritmos cortos tendrá un efecto acumulativo.
No obstante, los algoritmos cortos también han sido estudiados y optimizados por los programadores durante décadas. Como prueba de concepto, Mankowitz y sus colegas empezaron con un algoritmo para ordenar una lista de tres elementos. La mejor versión humana de este algoritmo consta de 18 instrucciones. Y creían que no serían capaces de mejorarlo.
"No esperábamos conseguir nada mejor", afirma Mankowitz. "Pero, para nuestra sorpresa, conseguimos hacerlo más rápido. Al principio, pensamos que se trataba de un error, un fallo; pero cuando analizamos el programa nos dimos cuenta de que, en realidad, AlphaDev había descubierto algo".
AlphaDev encontró la forma de ordenar una lista de tres elementos en 17 instrucciones en lugar de 18, pues había descubierto cómo saltarse ciertos pasos. "Cuando lo analizamos después, dijimos: 'Vaya, tiene sentido", cuenta Mankowitz. "Pero para descubrir algo así [sin AlphaDev], hacen falta programadores expertos en lenguaje ensamblador".
AlphaDev no pudo superar a la mejor versión humana del algoritmo para ordenar una lista de cuatro elementos, que requiere 28 instrucciones. Pero superó a la mejor versión humana para cinco elementos, reduciendo el número de instrucciones de 46 a 42.
Esto supone un aumento significativo de la velocidad. El algoritmo C++ existente para ordenar una lista de cinco elementos tardaba unos 6,91 nanosegundos en un típico chip Intel Skylake. El de AlphaDev tardaba 2,01 nanosegundos, alrededor de un 70% más rápido.
DeepMind compara el descubrimiento de AlphaDev con uno de los extraños movimientos, pero ganadores, de AlphaGo en su partida de Go contra el gran maestro Lee Sedol en 2016. "Todos los expertos vieron este movimiento y dijeron: 'Esto no es correcto, es una mala jugada", recuerda Mankowitz. "En realidad, era la jugada correcta y AlphaGo acabó ganando la partida e influyendo en las estrategias que los jugadores profesionales de Go empezaron a utilizar".
Si bien Sanders está impresionado, no cree que haya que exagerar los resultados. "Las técnicas de aprendizaje automático cambian cada vez más las reglas del juego en la programación, y todo el mundo espera que las IA pronto sean capaces de inventar algoritmos nuevos y mejores. Pero aún no hemos llegado a ese punto".
Por un lado, Sanders señala que AlphaDev solo utiliza un subconjunto de las instrucciones disponibles en el lenguaje ensamblador. Muchos algoritmos de categorización existentes ya utilizan instrucciones que AlphaDev aún no ha probado, explica Sanders. Por eso es más difícil comparar AlphaDev con los mejores métodos de la competencia.
Es cierto que AlphaDev tiene sus límites. El algoritmo más largo que ha producido tenía 130 instrucciones, y ordenó una lista de hasta cinco elementos. En cada paso, AlphaDev elegía entre 297 posibles instrucciones de ensamblaje de entre muchas otras. "Más allá de las 297 instrucciones y los juegos de ensamblaje de más de 130 instrucciones de longitud, el aprendizaje se volvía lento", asegura Mankowitz.
Esto se debe a que, incluso con 297 instrucciones o movimientos de juego, el número de algoritmos posibles que AlphaDev podría construir es mayor que el posible número de partidas de ajedrez (10120) y que el número de átomos del universo (alrededor de 1080 ).
Para algoritmos más largos, el equipo planea adaptar AlphaDev para que funcione con instrucciones C++, en lugar del lenguaje ensamblador. Con un control menos preciso, AlphaDev podría pasar por alto algunos atajos, pero el enfoque sería aplicable a una gama más amplia de algoritmos.
A Sanders también le gustaría ver una comparación más exhaustiva con los mejores enfoques ideados por personas, en especial, para algoritmos más largos. DeepMind asegura que forma parte de su plan. Mankowitz quiere combinar AlphaDev con los mejores métodos ideados por personas, haciendo que la IA se base en la intuición humana en lugar de partir de cero.
Al fin y al cabo, puede haber mejoras en la velocidad. "Para que un ser humano haga esto, se necesita una gran experiencia y una enorme cantidad de horas -quizá días, o semanas- para examinar estos programas e identificar las mejoras", concluye Mankowitz. "Por eso, no se ha intentado antes".