A nova versão da AlphaZero descobriu uma maneira mais rápida de realizar a multiplicação de matrizes, uma questão crucial no campo e que afeta milhares de tarefas computacionais diárias.
A empresa DeepMind usou sua Inteligência Artificial (IA) treinada para jogos de tabuleiro, a AlphaZero, para descobrir uma maneira mais rápida de resolver um problema matemático fundamental na ciência da computação, batendo o recorde que já perdurava por mais de 50 anos.
O problema, a multiplicação de matrizes, é um tipo crucial de cálculo, sendo o cerne de diversas aplicações, desde exibir imagens numa tela até simular sistemas complexos de física. Também é fundamental para o próprio machine learning. O aumento da velocidade desse cálculo pode causar um grande impacto em milhares de tarefas computacionais do quotidiano, reduzindo gastos e economizando energia.
“Esse é um resultado realmente incrível,” diz François Le Gall, matemático da Universidade de Nagoya, no Japão, o qual não estava envolvido nesse trabalho. “Multiplicação de matrizes é usado em tudo na engenharia,” diz. “Para qualquer questão que quiser resolver numericamente, normalmente vai usar matrizes”.
Apesar da difusão desses cálculos, ainda não são muito bem compreendidos. A matriz é simplesmente uma tabela de números, podendo representar o que você desejar. Normalmente, a multiplicação de duas matrizes implica em multiplicar as linhas de uma grade pelas colunas da outra. A técnica básica para resolver esse problema matemático é ensinada no ensino médio. “É como se fosse o ABC da computação”, diz Pushmeet Kohli, chefe da equipa de IA para Ciência da DeepMind.
No entanto, as coisas se complicam quando tenta achar um método mais rápido de fazer esses cálculos. “Ninguém sabe qual é o melhor algoritmo para resolvê-lo,” diz Le Gall. “É uma das grandes questões sem resposta da ciência da computação”.
Isso se dá pelo facto de que existem mais maneiras de multiplicar duas matrizes do que átomos no universo (10 elevado a potência de 33, em alguns dos casos estudados pelos pesquisadores). “O número de ações possíveis é quase infinita”. Diz Thomas Hubert, engenheiro da DeepMind.
O truque foi transformar o problema numa espécie de jogo de tabuleiro tridimensional, chamado TensorGame. O tabuleiro representa o problema matemático a ser resolvido, e cada movimento representa o próximo passo para solucionar esse problema. Logo, a sequência de movimentos feita no jogo representa um algoritmo.
Os investigadores treinaram uma nova versão da AlphaZero, chamada AlphaTensor, para jogar esse jogo. Ao invés de aprender a melhor sequência de movimentos a se fazer no xadrez ou no Go, a AlphaTensor aprendeu a melhor série de passos para se fazer ao multiplicar matrizes. Ganhava o jogo se resolvesse a questão com a menor quantidade possível de movimentos.
“Transformamos tudo num jogo, nosso formato favorito,” diz Hubert, um dos principais investigadores da AlphaZero.
Os cientistas descreveram o seu trabalho num artigo publicado na Nature. O principal resultado é que a AlphaTensor descobriu uma forma mais rápida de multiplicar duas matrizes 4×4 do que o método elaborado em 1969 pelo matemático alemão Volker Strassen, o qual ninguém havia sido capaz de aperfeiçoar desde então. O método básico ensinado no ensino médio tem 64 passos; o de Strassen, 49. O programa AlphaTensor achou uma maneira de fazer isso em 47 passos.
Ao todo, o AlphaTensor superou os melhores algoritmos já existentes em mais de 70 tamanhos diferentes de matrizes. Ele reduziu o número de passos necessários para multiplicar duas matrizes 9×9 de 511 para 498; e o número de etapas para multiplicar duas matrizes 11×11 de 919 para 896. Em diversos outros casos, a IA acabou por redescobrir o melhor algoritmo já existente.
Os investigadores surpreenderam-se com quantos algoritmos corretos diferentes a AlphaTensor achou para cada tamanho de matriz. “É impressionante ver que há pelo menos 14.000 maneiras de multiplicarmos matrizes 4×4,” diz Hussein Fawzi, investigador da DeepMind.
Após terem buscado pelos algoritmos teoricamente mais rápidos, a equipe da DeepMind queria saber quais desses na prática atenderiam os seus desejos. Diferentes algoritmos são executados com melhor eficácia em hardwares diferentes pois os processadores de computador são geralmente desenvolvidos para tipos específicos de computação. A equipa da DeepMind usou a AlphaTensor para procurar por algoritmos personalizados para os processadores Nvidia V100 GPU e Google TPU, dois dos chips comumente mais usados para treinamento de redes neurais. Os algoritmos achados foram de 10 a 20% mais rápidos em multiplicação de matrizes do que aqueles usados normalmente com esses chips.
Virginia Williams, cientista no Laboratório de Ciência da Computação e Inteligência Artificial do MIT, está animada com os resultados. Faz a observação de que diferentes abordagens computacionais têm sido usadas a fim de encontrar novos algoritmos para multiplicação de matrizes já há um bom tempo, e muitos dos algoritmos mais rápidos foram elaborados dessa maneira. No entanto, nenhum conseguiu melhorar os resultados duradouros como os de Strassen.
“Esse novo método realiza algo completamente diferente do que os outros estavam fazendo,” diz Williams. “Seria muito bom descobrir se esse novo método realmente substitui todos os antigos, ou se conseguimos combiná-los e obter algo ainda melhor”.
Agora, a DeepMind planeia usar a AlphaTensor para buscar por outros tipos de algoritmos. “É uma nova forma de fazer ciência da computação”, diz Kohli.
MIT Technology Review