633c2e27fd141483d83afcb0 Mm Blogheader.png

La primera extensión de AlphaZero a las matemáticas abre nuevas posibilidades de investigación

Los algoritmos han ayudado a los matemáticos a realizar operaciones fundamentales durante miles de años. Los antiguos egipcios crearon un algoritmo para multiplicar dos números sin necesidad de una tabla de multiplicar, y el matemático griego Euclides describió un algoritmo para calcular el máximo común divisor, que todavía se utiliza en la actualidad.

Durante la Edad de Oro islámica, el matemático persa Muhammad ibn Musa al-Khwarizmi Diseñó nuevos algoritmos para resolver ecuaciones lineales y cuadráticas. De hecho, el nombre de al-Khwarizmi, traducido al latín como algoritmo, condujo al término algoritmo. Pero, a pesar de la familiaridad con los algoritmos actuales (utilizados en toda la sociedad, desde el álgebra en el aula hasta la investigación científica de vanguardia), el proceso de descubrir nuevos algoritmos es increíblemente difícil y es un ejemplo de las asombrosas capacidades de razonamiento de la mente humana.

En nuestro papelpublicado hoy en Nature, les presentamos AlfaTensor, el primer sistema de inteligencia artificial (IA) para descubrir algoritmos novedosos, eficientes y demostrablemente correctos para tareas fundamentales como la multiplicación de matrices. Esto arroja luz sobre una pregunta abierta en matemáticas de hace 50 años sobre cómo encontrar la forma más rápida de multiplicar dos matrices.

Este documento es un trampolín en la misión de DeepMind de hacer avanzar la ciencia y resolver los problemas más fundamentales mediante el uso de la IA. Nuestro sistema, AlphaTensor, se basa en AlphaZero, un agente que tiene mostró un rendimiento sobrehumano en juegos de mesa, como ajedrez, go y shogiy este trabajo muestra el viaje de AlphaZero desde jugar hasta abordar problemas matemáticos sin resolver por primera vez.

Multiplicación de matrices

La multiplicación de matrices es una de las operaciones más simples de álgebra y se enseña comúnmente en las clases de matemáticas de la escuela secundaria. Pero fuera del aula, esta humilde operación matemática tiene una enorme influencia en el mundo digital contemporáneo y es omnipresente en la informática moderna.

Ejemplo del proceso de multiplicación de dos matrices de 3×3.

Esta operación se utiliza para procesar imágenes en teléfonos inteligentes, reconocer comandos de voz, generar gráficos para juegos de computadora, ejecutar simulaciones para predecir el clima, comprimir datos y videos para compartir en Internet, y mucho más. Empresas de todo el mundo invierten grandes cantidades de tiempo y dinero en desarrollar hardware informático para multiplicar matrices de forma eficiente. Por lo tanto, incluso mejoras menores en la eficiencia de la multiplicación de matrices pueden tener un impacto generalizado.

Durante siglos, los matemáticos creyeron que el algoritmo estándar de multiplicación de matrices era el mejor que se podía lograr en términos de eficiencia. Pero en 1969, el matemático alemán Volker Strassen sorprendió a la comunidad matemática mostrando que existen mejores algoritmos.

Algoritmo estándar comparado con el algoritmo de Strassen, que utiliza una multiplicación escalar menos (7 en lugar de 8) para multiplicar matrices de 2×2. Las multiplicaciones importan mucho más que las sumas para la eficiencia general.

Mediante el estudio de matrices muy pequeñas (tamaño 2×2), descubrió una forma ingeniosa de combinar las entradas de las matrices para producir un algoritmo más rápido. A pesar de décadas de investigación tras el avance de Strassen, versiones más grandes de este problema siguen sin resolverse, hasta el punto de que no se sabe con qué eficiencia es posible multiplicar dos matrices tan pequeñas como 3×3.

En nuestro artículo, exploramos cómo las técnicas modernas de IA podrían avanzar en el descubrimiento automático de nuevos algoritmos de multiplicación de matrices. Aprovechando el progreso de la intuición humana, AlphaTensor descubrió algoritmos que son más eficientes que los últimos avances para muchos tamaños de matrices. Nuestros algoritmos diseñados por IA superan a los diseñados por humanos, lo que supone un gran paso adelante en el campo del descubrimiento algorítmico.

El proceso y el progreso de la automatización del descubrimiento algorítmico.

Primero, convertimos el problema de encontrar algoritmos eficientes para la multiplicación de matrices en un juego para un solo jugador. En este juego, el tablero es un tensor tridimensional (conjunto de números), que captura qué tan lejos está de ser correcto el algoritmo actual. A través de un conjunto de movimientos permitidos, correspondientes a instrucciones del algoritmo, el jugador intenta modificar el tensor y poner a cero sus entradas. Cuando el jugador logra hacerlo, el resultado es un algoritmo de multiplicación de matrices demostrablemente correcto para cualquier par de matrices, y su eficiencia se captura por la cantidad de pasos dados para poner a cero el tensor.

Este juego es increíblemente desafiante: la cantidad de algoritmos posibles a considerar es mucho mayor que la cantidad de átomos en el universo, incluso para casos pequeños de multiplicación de matrices. En comparación con el juego de Go, que permaneció un desafío para la IA durante décadasel número de movimientos posibles en cada paso de nuestro juego es 30 órdenes de magnitud mayor (más de 1033 para una de las configuraciones que consideramos).

Básicamente, para jugar bien a este juego, es necesario identificar la más pequeña de las agujas en un gigantesco pajar de posibilidades. Para abordar los desafíos de este dominio, que se aleja significativamente de los juegos tradicionales, desarrollamos múltiples componentes cruciales, incluida una novedosa arquitectura de red neuronal que incorpora sesgos inductivos específicos del problema, un procedimiento para generar datos sintéticos útiles y una receta para aprovechar las simetrías de los juegos. problema.

Luego entrenamos a un agente AlphaTensor utilizando el aprendizaje por refuerzo para jugar, comenzando sin ningún conocimiento sobre los algoritmos de multiplicación de matrices existentes. A través del aprendizaje, AlphaTensor mejora gradualmente con el tiempo, redescubriendo algoritmos históricos de multiplicación rápida de matrices como el de Strassen, superando finalmente el ámbito de la intuición humana y descubriendo algoritmos más rápidos de lo que se conocía anteriormente.

Juego para un jugador jugado por AlphaTensor, donde el objetivo es encontrar un algoritmo de multiplicación de matrices correcto. El estado del juego es una matriz cúbica de números (que se muestran en gris para 0, azul para 1 y verde para -1), que representan el trabajo restante por hacer.

Por ejemplo, si el algoritmo tradicional que se enseña en la escuela multiplica una matriz de 4×5 por 5×5 usando 100 multiplicaciones, y este número se redujo a 80 con ingenio humano, AlphaTensor ha encontrado algoritmos que hacen la misma operación usando solo 76 multiplicaciones.

Algoritmo descubierto por AlphaTensor que utiliza 76 multiplicaciones, una mejora con respecto a los algoritmos de última generación.

Más allá de este ejemplo, el algoritmo de AlphaTensor mejora el algoritmo de dos niveles de Strassen en un campo finito por primera vez desde su descubrimiento hace 50 años. Estos algoritmos para multiplicar matrices pequeñas se pueden utilizar como primitivos para multiplicar matrices mucho más grandes de tamaño arbitrario.

Además, AlphaTensor también descubre un conjunto diverso de algoritmos con una complejidad de vanguardia: hasta miles de algoritmos de multiplicación de matrices para cada tamaño, lo que demuestra que el espacio de los algoritmos de multiplicación de matrices es más rico de lo que se pensaba anteriormente.

Los algoritmos en este rico espacio tienen diferentes propiedades matemáticas y prácticas. Aprovechando esta diversidad, adaptamos AlphaTensor para encontrar específicamente algoritmos que sean rápidos en un hardware determinado, como la GPU Nvidia V100 y Google TPU v2. Estos algoritmos multiplican matrices grandes entre un 10% y un 20% más rápido que los algoritmos comúnmente utilizados en el mismo hardware, lo que muestra la flexibilidad de AlphaTensor para optimizar objetivos arbitrarios.

AlphaTensor con un objetivo correspondiente al tiempo de ejecución del algoritmo. Cuando se descubre un algoritmo de multiplicación de matrices correcto, se compara con el hardware de destino, que luego se retroalimenta a AlphaTensor, para aprender algoritmos más eficientes en el hardware de destino.

Explorando el impacto en futuras investigaciones y aplicaciones.

Desde un punto de vista matemático, nuestros resultados pueden guiar futuras investigaciones en teoría de la complejidad, cuyo objetivo es determinar los algoritmos más rápidos para resolver problemas computacionales. Al explorar el espacio de posibles algoritmos de una manera más efectiva que los enfoques anteriores, AlphaTensor ayuda a avanzar en nuestra comprensión de la riqueza de los algoritmos de multiplicación de matrices. Comprender este espacio puede desbloquear nuevos resultados que ayuden a determinar la complejidad asintótica de la multiplicación de matrices. Uno de los problemas abiertos más fundamentales en informática..

Debido a que la multiplicación de matrices es un componente central en muchas tareas computacionales, que abarcan gráficos por computadora, comunicaciones digitales, entrenamiento de redes neuronales y computación científica, los algoritmos descubiertos por AlphaTensor podrían hacer que los cálculos en estos campos sean significativamente más eficientes. La flexibilidad de AlphaTensor para considerar cualquier tipo de objetivo también podría impulsar nuevas aplicaciones para diseñar algoritmos que optimicen métricas como el uso de energía y la estabilidad numérica, ayudando a evitar que pequeños errores de redondeo se multipliquen mientras funciona un algoritmo.

Si bien nos centramos aquí en el problema particular de la multiplicación de matrices, esperamos que nuestro artículo inspire a otros a utilizar la IA para guiar el descubrimiento algorítmico para otras tareas computacionales fundamentales. Nuestra investigación también muestra que AlphaZero es un poderoso algoritmo que puede extenderse mucho más allá del dominio de los juegos tradicionales para ayudar a resolver problemas abiertos en matemáticas. A partir de nuestra investigación, esperamos impulsar un mayor volumen de trabajo: aplicar la IA para ayudar a la sociedad a resolver algunos de los desafíos más importantes en matemáticas y en todas las ciencias.

Puedes encontrar más información en Repositorio GitHub de AlphaTensor.