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 em uma tela até simular sistemas complexos de física. Ele 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 cotidiano, 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 ele. “Para qualquer questão que você quiser resolver numericamente, você vai normalmente usar matrizes”.
Apesar da difusão desses cálculos, eles 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 equipe de IA para Ciência da DeepMind.
No entanto, as coisas se complicam quando você 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 fato 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 em uma 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 pesquisadores 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. Ela ganhava o jogo se resolvesse a questão com a menor quantidade possível de movimentos.
“Transformamos tudo em um jogo, nosso formato favorito,” diz Hubert, um dos principais pesquisadores da AlphaZero.
Os cientistas descreveram seu trabalho em um 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 pesquisadores se surpreenderam 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, pesquisador 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 equipe da DeepMind usou a AlphaTensor para buscar 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. Ela 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 planeja 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
