Deep Mind AlphaTensor descubrirá nuevos algoritmos

Deep Mind ha extendido AlphaZero a las matemáticas para desbloquear nuevas posibilidades para los algoritmos de investigación.

AlphaTensor, se basa en AlphaZero, un agente que ha demostrado un rendimiento sobrehumano en juegos de mesa, como ajedrez, Go y shogi, y este trabajo muestra el viaje de AlphaZero desde jugar juegos hasta abordar problemas matemáticos sin resolver por primera vez.

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 usa 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 Algoritmi, dio lugar al término algoritmo. Pero, a pesar de la familiaridad con los algoritmos de hoy en día, que se utilizan 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 habilidades de razonamiento de la mente humana.

Publicaron en Nature. AlphaTensor es el primer sistema de inteligencia artificial (IA) para descubrir algoritmos novedosos, eficientes y comprobablemente correctos para tareas fundamentales como la multiplicación de matrices. Esto arroja luz sobre una pregunta matemática abierta de hace 50 años sobre cómo encontrar la forma más rápida de multiplicar dos matrices.

Entrenado desde cero, AlphaTensor descubre algoritmos de multiplicación de matrices que son más eficientes que los algoritmos humanos y diseñados por computadora existentes. A pesar de mejorar con respecto a los algoritmos conocidos, señalan que una limitación de AlphaTensor es la necesidad de predefinir un conjunto de posibles entradas de factores F, lo que discretiza el espacio de búsqueda, pero posiblemente puede conducir a la pérdida de algoritmos eficientes. Una dirección interesante para futuras investigaciones es adaptar AlphaTensor para buscar F. Una fortaleza importante de AlphaTensor es su flexibilidad para admitir recompensas estocásticas complejas y no diferenciables (desde el rango del tensor hasta la eficiencia práctica en hardware específico), además de encontrar algoritmos. para operaciones personalizadas en una amplia variedad de espacios (como campos finitos). Creen que esto estimulará las aplicaciones de AlphaTensor hacia el diseño de algoritmos que optimicen métricas que no consideramos aquí, como la estabilidad numérica o el uso de energía.

El descubrimiento de los algoritmos de multiplicación de matrices tiene implicaciones de gran alcance, ya que la multiplicación de matrices se encuentra en el centro de muchas tareas computacionales, como la inversión de matrices, el cálculo del determinante y la resolución de sistemas lineales.

El proceso y el progreso de la automatización del descubrimiento algorítmico
Primero, convirtieron 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 (matriz de números), que captura qué tan lejos de corregir está el algoritmo actual. A través de un conjunto de movimientos permitidos, correspondientes a las instrucciones del algoritmo, el jugador intenta modificar el tensor y poner a cero sus entradas. Cuando el jugador logra hacerlo, esto da como resultado un algoritmo de multiplicación de matrices demostrablemente correcto para cualquier par de matrices, y su eficiencia se captura por el número de pasos tomados 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 siguió siendo un desafío para la IA durante décadas, la cantidad de movimientos posibles en cada paso de su juego es 30 órdenes de magnitud mayor (más de 10^33 para una de las configuraciones que consideran).

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

Luego entrenaron a un agente de AlphaTensor utilizando el aprendizaje por refuerzo para jugar el juego, 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 de matrices rápidas como el de Strassen, superando eventualmente el reino de la intuición humana y descubriendo algoritmos más rápidos de lo que se conocía anteriormente.

Explorando el impacto en futuras investigaciones y aplicaciones
Desde un punto de vista matemático, sus 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 para ayudar 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 abarca 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 acumulen como una bola de nieve mientras funciona un algoritmo.

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

Naturaleza: descubrimiento de algoritmos de multiplicación de matrices más rápidos con aprendizaje por refuerzo

Resumen
Mejorar la eficiencia de los algoritmos para los cálculos fundamentales puede tener un impacto generalizado, ya que puede afectar la velocidad general de una gran cantidad de cálculos. La multiplicación de matrices es una de esas tareas primitivas, que ocurre en muchos sistemas, desde redes neuronales hasta rutinas informáticas científicas. El descubrimiento automático de algoritmos mediante el aprendizaje automático ofrece la posibilidad de ir más allá de la intuición humana y superar a los mejores algoritmos actuales diseñados por humanos. Sin embargo, la automatización del procedimiento de descubrimiento de algoritmos es complicada, ya que el espacio de posibles algoritmos es enorme. Aquí informamos un enfoque de aprendizaje de refuerzo profundo basado en AlphaZero1 para descubrir algoritmos eficientes y comprobablemente correctos para la multiplicación de matrices arbitrarias. Nuestro agente, AlphaTensor, está capacitado para jugar un juego de un solo jugador donde el objetivo es encontrar descomposiciones de tensores dentro de un espacio de factores finitos. AlphaTensor descubrió algoritmos que superan la complejidad de última generación para muchos tamaños de matriz. Particularmente relevante es el caso de matrices 4 × 4 en un campo finito, donde el algoritmo de AlphaTensor mejora el algoritmo de dos niveles de Strassen por primera vez, que sepamos, desde su descubrimiento hace 50 años2. Mostramos aún más la flexibilidad de AlphaTensor a través de diferentes casos de uso: algoritmos con complejidad de última generación para la multiplicación de matriz estructurada y eficiencia práctica mejorada mediante la optimización de la multiplicación de matriz para el tiempo de ejecución en hardware específico. Nuestros resultados destacan la capacidad de AlphaTensor para acelerar el proceso de descubrimiento algorítmico en una variedad de problemas y optimizar para diferentes criterios.