DeepMind transformou a multiplicação de matrizes em um jogo para um jogador e superou um recorde de 50 anos

O Ars Technica relatou em outubro de 2022 que o DeepMind havia encontrado uma maneira mais eficiente de multiplicar matrizes, superando um recorde de 50 anos. Em 1969, Volker Strassen encontrou um algoritmo que multiplica duas matrizes 4x4 em 49 multiplicações em vez das 64 do método escolar. Usando uma rede neural chamada AlphaTensor, o DeepMind encontrou uma maneira de fazê-lo em 47, e publicou na Nature.

O DeepMind configurou o problema como um jogo para um jogador. O "tabuleiro" é um tensor tridimensional que captura o quão longe o algoritmo atual está de estar correto; os movimentos permitidos correspondem a instruções do algoritmo, e o jogador tenta zerar as entradas do tensor. Fazer isso produz um algoritmo comprovadamente correto para qualquer par de matrizes, com a eficiência capturada pelo número de passos. Treinado por aprendizado por reforço, como o AlphaGo, o AlphaTensor primeiro redescobriu o trabalho de Strassen e o de outros matemáticos, depois os superou, segundo o DeepMind.

Para matrizes 5x5, o AlphaTensor encontrou um método de 96 passos contra 98 do mais antigo. Uma semana depois, Manuel Kauers e Jakob Moosbauer, da Universidade Johannes Kepler de Linz, relataram 95, escrevendo que sua solução foi obtida a partir do esquema do DeepMind por uma sequência de transformações que eliminou uma multiplicação. O Ars observa que a multiplicação de matrizes está por trás do reconhecimento de fala e de imagem e dos gráficos, e que trilhões desses cálculos rodam em GPUs todos os dias, de modo que pequenas economias podem se acumular.

Reformular a busca por algoritmos de matrizes mais rápidos como um jogo para um jogador sobre um tensor, para que uma IA que joga jogos possa descobrir algoritmos comprovadamente corretos.

Um algoritmo correto é um tensor reduzido a zero, então a correção está embutida nas regras do jogo.

O número de passos usados é uma pontuação clara, então a IA pode aprender quais movimentos levam a algoritmos mais curtos.

A multiplicação de matrizes é tão amplamente usada que até passar de 49 para 47 passos importa na escala das GPUs.

Publicar o esquema descoberto permitiu que pesquisadores humanos construíssem sobre ele em uma semana.

Se um problema de pesquisa pode ser enquadrado como um jogo com uma pontuação clara, uma IA que joga jogos pode explorá-lo, e seus resultados podem servir de base para melhorias humanas posteriores.

Uma semana após o anúncio do DeepMind, os dois pesquisadores austríacos reivindicaram um esquema de 95 multiplicações para matrizes 5x5, construindo sobre o do DeepMind. O Ars especulou que, com a IA agora buscando novos algoritmos, outros recordes matemáticos de longa data poderiam cair em breve.