DeepMind convirtió la multiplicación de matrices en un juego para un jugador y superó un récord de 50 años

Ars Technica informó en octubre de 2022 que DeepMind había encontrado una forma más eficiente de multiplicar matrices, superando un récord de 50 años. En 1969, Volker Strassen encontró un algoritmo que multiplica dos matrices de 4x4 en 49 multiplicaciones en lugar de 64 mediante el método escolar. Usando una red neuronal llamada AlphaTensor, DeepMind encontró una forma de hacerlo en 47, y lo publicó en Nature.

DeepMind planteó el problema como un juego para un jugador. El «tablero» es un tensor tridimensional que captura cuánto se aleja el algoritmo actual de ser correcto; los movimientos permitidos corresponden a instrucciones del algoritmo, y el jugador intenta anular las entradas del tensor. Hacerlo produce un algoritmo demostrablemente correcto para cualquier par de matrices, con la eficiencia capturada por el número de pasos. Entrenado mediante aprendizaje por refuerzo, como AlphaGo, AlphaTensor primero redescubrió el trabajo de Strassen y el de otros matemáticos, y luego los superó, según DeepMind.

Para matrices de 5x5, AlphaTensor encontró un método de 96 pasos frente a 98 del anterior. Una semana después, Manuel Kauers y Jakob Moosbauer, de la Universidad Johannes Kepler de Linz, informaron de 95, y escribieron que su solución se obtuvo a partir del esquema de DeepMind mediante una secuencia de transformaciones que eliminó una multiplicación. Ars señala que la multiplicación de matrices está en la base del reconocimiento de voz e imágenes y de los gráficos, y que cada día se ejecutan billones de esos cálculos en GPU, por lo que pequeños ahorros pueden acumularse.

Reformular la búsqueda de algoritmos de matrices más rápidos como un juego para un jugador sobre un tensor, de modo que una IA que juega pueda descubrir algoritmos demostrablemente correctos.

Un algoritmo correcto es un tensor reducido a cero, así que la corrección está incorporada en las reglas del juego.

El número de pasos utilizados es una puntuación limpia, así que la IA puede aprender qué movimientos conducen a algoritmos más cortos.

La multiplicación de matrices se usa tanto que incluso pasar de 49 a 47 pasos importa a escala de GPU.

Publicar el esquema descubierto permitió a investigadores humanos construir sobre él en una semana.

Si un problema de investigación puede enmarcarse como un juego con una puntuación clara, una IA que juega puede buscarlo, y sus resultados pueden servir de base para mejoras humanas posteriores.

Una semana después del anuncio de DeepMind, los dos investigadores austriacos reclamaron un esquema de 95 multiplicaciones para matrices de 5x5, basándose en el de DeepMind. Ars especuló que, con la IA buscando ahora nuevos algoritmos, otros récords matemáticos de larga data podrían caer pronto.