Inspirados pelos resultados de uma rede neural de jogos, matemáticos têm feito avanços inesperados em um antigo problema matemático.
Os matemáticos adoram um bom quebra-cabeça. Mesmo algo tão abstrato quanto a multiplicação de matrizes (tabelas de números bidimensionais) pode parecer um jogo quando você tenta encontrar a maneira mais eficiente de fazê-lo. É um pouco como tentar resolver um Cubo de Rubik com o menor número de movimentos possível – desafiador, mas atraente. Exceto que para um cubo mágico, o número de movimentos possíveis em cada passo é 18; para multiplicação de matrizes, mesmo em casos relativamente simples, cada passo pode apresentar mais de 1012 opções.
Nos últimos 50 anos, os pesquisadores abordaram esse problema de várias maneiras, todas baseadas em pesquisas de computador auxiliadas pela intuição humana. No mês passado, uma equipe da empresa de inteligência artificial DeepMind mostrou como lidar com o problema de uma nova direção, relatando em um artigo na Nature que eles treinaram com sucesso uma rede neural para descobrir novos algoritmos rápidos para multiplicação de matrizes. Era como se a IA tivesse encontrado uma estratégia desconhecida para resolver um cubo de Rubik monstruosamente complexo.
“É um resultado muito legal”, disse Josh Alman, cientista da computação da Universidade de Columbia. Mas ele e outros especialistas em multiplicação de matrizes também enfatizaram que essa assistência de IA complementará, em vez de substituir, os métodos existentes – pelo menos no curto prazo. “É como uma prova de conceito para algo que pode se tornar um avanço”, disse Alman. O resultado simplesmente ajudará os pesquisadores em sua busca.
Como se para provar o ponto, três dias depois que o artigo da Nature foi publicado, um par de pesquisadores austríacos ilustrou como métodos novos e antigos podem se complementar. Eles usaram uma pesquisa convencional auxiliada por computador para melhorar ainda mais um dos algoritmos que a rede neural havia descoberto.
Os resultados sugerem que, como o processo de resolução de um Cubo de Rubik, o caminho para melhores algoritmos será cheio de voltas e mais voltas.
Multiplicando Matrizes
A multiplicação de matrizes é uma das operações mais fundamentais e onipresentes em toda a matemática. Para multiplicar um par de matrizes n por n, cada uma com n2 elementos, você multiplica e soma esses elementos em combinações particulares para gerar o produto, uma terceira matriz n por n. A receita padrão para multiplicar duas matrizes n por n requer n3 operações de multiplicação, então uma matriz 2 por 2, por exemplo, requer oito multiplicações.
Para matrizes maiores, com milhares de linhas e colunas, esse processo rapidamente se torna complicado. Mas em 1969, o matemático Volker Strassen descobriu um procedimento para multiplicar um par de matrizes 2 por 2 usando sete em vez de oito etapas de multiplicação, ao custo de introduzir mais etapas de adição.
O algoritmo de Strassen é desnecessariamente complicado se você quiser apenas multiplicar um par de matrizes 2 por 2. Mas ele percebeu que também funcionaria para matrizes maiores. Isso porque os elementos de uma matriz podem ser matrizes. Por exemplo, uma matriz com 20.000 linhas e 20.000 colunas pode ser reimaginada como uma matriz 2 por 2 cujos quatro elementos são matrizes de 10.000 por 10.000. Cada uma dessas matrizes pode ser subdividida em quatro blocos de 5.000 por 5.000 e assim por diante. Strassen poderia aplicar seu método para multiplicar matrizes 2 por 2 em cada nível dessa hierarquia aninhada. À medida que o tamanho da matriz aumenta, a economia de menos multiplicações aumenta.
A descoberta de Strassen levou a uma busca por algoritmos eficientes para multiplicação de matrizes, que desde então inspirou dois subcampos distintos. Um se concentra em uma questão de princípio: se você imaginar a multiplicação de duas matrizes n por n e deixar n correr em direção ao infinito, como o número de etapas de multiplicação no algoritmo mais rápido possível escala com n? O recorde atual de melhor escala, n
O segundo subcampo pensa em uma escala menor. Logo após o trabalho de Strassen, o cientista da computação israelense-americano Shmuel Winograd mostrou que Strassen havia atingido um limite teórico: não é possível multiplicar matrizes 2 por 2 com menos de sete etapas de multiplicação. Mas para todos os outros tamanhos de matrizes, o número mínimo de multiplicações necessárias permanece uma questão em aberto. E algoritmos rápidos para matrizes pequenas podem ter um impacto desproporcional, já que iterações repetidas de tal algoritmo podem superar o algoritmo de Strassen quando matrizes de tamanho razoável estão sendo multiplicadas.
Infelizmente, o grande número de possibilidades é enorme. Mesmo para matrizes 3 por 3, “o número de algoritmos possíveis excede o número de átomos no universo”, disse Alhussein Fawzi, pesquisador da DeepMind e um dos líderes do novo trabalho.
Diante desse vertiginoso menu de opções, os pesquisadores fizeram progressos ao transformar a multiplicação de matrizes no que parece ser um problema de matemática totalmente diferente – um que é mais fácil para os computadores lidarem. É possível representar a tarefa abstrata de multiplicar duas matrizes como um tipo específico de objeto matemático: uma matriz tridimensional de números chamada tensor. Os pesquisadores podem então dividir esse tensor em uma soma de componentes elementares, chamados tensores “rank-1”; cada um deles representará um passo diferente no algoritmo de multiplicação de matrizes correspondente. Isso significa que encontrar um algoritmo de multiplicação eficiente equivale a minimizar o número de termos em uma decomposição tensorial – quanto menos termos, menos etapas envolvidas.
Dessa forma, os pesquisadores descobriram novos algoritmos que multiplicam matrizes n por n usando menos etapas de multiplicação n³ padrão para muitos tamanhos de matriz pequenos. Mas os algoritmos que superam não apenas o padrão, mas também o algoritmo de Strassen para pequenas matrizes permaneceram fora de alcance – até agora.
Jogo ligado
A equipe do DeepMind abordou o problema transformando a decomposição do tensor em um jogo para um jogador. Eles começaram com um algoritmo de deep learning descendente do AlphaGo – outro DeepMind AI que em 2016 aprendeu a jogar o jogo de tabuleiro Go bem o suficiente para vencer os melhores jogadores humanos.
Todos os algoritmos de deep learning são construídos em torno de redes neurais: teias de neurônios artificiais classificados em camadas, com conexões que podem variar em força, representando o quanto cada neurônio influencia os da próxima camada. A força dessas conexões é ajustada em muitas iterações de um procedimento de treinamento, durante o qual a rede neural aprende a transformar cada entrada que recebe em uma saída que ajuda o algoritmo a atingir seu objetivo geral.
? Lex Fridman (@lexfridman) October 6, 2022
Estes são os primeiros passos na IA inventando novas ideias em matemática e física dignas de um Prêmio Nobel e uma Medalha Fields.
Vivemos em tempos excitantes!
No novo algoritmo da DeepMind, apelidado de AlphaTensor, as entradas representam etapas ao longo do caminho para um esquema válido de multiplicação de matrizes. A primeira entrada para a rede neural é o tensor de multiplicação da matriz original e sua saída é o tensor de rank 1 que o AlphaTensor escolheu para seu primeiro movimento. O algoritmo subtrai esse tensor de nível 1 da entrada inicial, produzindo um tensor atualizado que é realimentado na rede como uma nova entrada. O processo se repete até que, eventualmente, todos os elementos no tensor inicial tenham sido reduzidos a zero, o que significa que não há mais tensores de nível 1 a serem removidos.
Nesse ponto, a rede neural descobriu uma decomposição tensorial válida, pois é matematicamente garantido que a soma de todos os tensores de nível 1 é exatamente igual ao tensor inicial. E as etapas necessárias para chegar lá podem ser traduzidas de volta em etapas do algoritmo de multiplicação de matrizes correspondente.
Aqui está o jogo: AlphaTensor decompõe repetidamente um tensor em um conjunto de componentes de rank 1. A cada vez, o AlphaTensor é recompensado se encontrar uma maneira de reduzir o número de etapas. Mas os atalhos para a vitória não são nada intuitivos, assim como às vezes você deve embaralhar um rosto perfeitamente ordenado em um cubo mágico antes de poder resolver a coisa toda.
A equipe agora tinha um algoritmo que poderia, teoricamente, resolver seu problema. Eles só tinham que treiná-lo primeiro.
Novos caminhos
Como todas as redes neurais, o AlphaTensor precisa de muitos dados para treinar, mas a decomposição do tensor é um problema notoriamente difícil. Havia poucos exemplos de decomposições eficientes que os pesquisadores poderiam alimentar a rede. Em vez disso, eles ajudaram o algoritmo a começar treinando-o no problema inverso muito mais fácil: adicionar um monte de tensores de classificação 1 gerados aleatoriamente.
“Eles estão usando o problema fácil para produzir mais dados para o problema difícil”, disse Michael Littman, cientista da computação da Brown University. A combinação desse procedimento de treinamento reverso com aprendizado por reforço, em que o AlphaTensor gerava seus próprios dados de treinamento à medida que procurava decomposições eficientes, funcionou muito melhor do que qualquer método de treinamento por conta própria.
A equipe do DeepMind treinou o AlphaTensor para decompor tensores que representam a multiplicação de matrizes de até 12 por 12. Ele buscou algoritmos rápidos para multiplicar matrizes de números reais comuns e também algoritmos específicos para uma configuração mais restrita conhecida como aritmética módulo 2. (Isso é matemática baseada em apenas dois números, então os elementos da matriz só podem ser 0 ou 1, e 1 + 1 = 0.) Os pesquisadores geralmente começam com esse espaço mais restrito, mas ainda vasto, na esperança de que os algoritmos descobertos aqui possam ser adaptados para trabalhar com matrizes de números reais.
Após o treinamento, o AlphaTensor redescobriu o algoritmo de Strassen em poucos minutos. Em seguida, descobriu até milhares de novos algoritmos rápidos para cada tamanho de matriz. Estes eram diferentes dos algoritmos mais conhecidos, mas tinham o mesmo número de etapas de multiplicação.
Em alguns casos, o AlphaTensor até bateu recordes existentes. Suas descobertas mais surpreendentes aconteceram na aritmética do módulo 2, onde encontrou um novo algoritmo para multiplicar matrizes 4 por 4 em 47 etapas de multiplicação, uma melhoria em relação às 49 etapas necessárias para duas iterações do algoritmo de Strassen. Ele também superou o algoritmo mais conhecido para matrizes de módulo 2 de 5 por 5, reduzindo o número de multiplicações necessárias do recorde anterior de 98 para 96. (Mas esse novo recorde ainda fica atrás dos 91 passos que seriam necessários para vencer Algoritmo de Strassen usando matrizes 5 por 5.)
O novo resultado de alto perfil criou muita empolgação, com alguns pesquisadores elogiando a melhoria baseada em IA no status quo. Mas nem todos na comunidade de multiplicação de matrizes ficaram tão impressionados. “Eu senti que estava um pouco exagerado”, disse Vassilevska Williams. “É mais uma ferramenta. Não é como, “Oh, os computadores derrotam os humanos”, sabe?”
Os pesquisadores também enfatizaram que as aplicações imediatas do algoritmo 4 por 4 recorde seriam limitadas: não só é válido apenas na aritmética do módulo 2, mas na vida real há considerações importantes além da velocidade.
Fawzi concordou que, na verdade, isso é apenas o começo. “Há muito espaço para melhorias e pesquisas, e isso é uma coisa boa”, disse ele.
Uma reviravolta final
A maior força do AlphaTensor em relação aos métodos de pesquisa de computador bem estabelecidos também é sua maior fraqueza: ele não é limitado pela intuição humana sobre como são os bons algoritmos, portanto, não pode explicar suas escolhas. Isso torna difícil para os pesquisadores aprender com suas realizações.
Mas isso pode não ser uma desvantagem tão grande quanto parece. Poucos dias após o resultado do AlphaTensor, o matemático Manuel Kauers e seu aluno de pós-graduação Jakob Moosbauer, ambos da Johannes Kepler University Linz, na Áustria, relataram mais um passo à frente.
Quando o artigo do DeepMind foi publicado, Kauers e Moosbauer estavam em processo de busca por novos algoritmos de multiplicação usando uma pesquisa convencional auxiliada por computador. Mas, ao contrário da maioria dessas pesquisas, que começam de novo com um novo princípio orientador, seu método funciona ajustando repetidamente um algoritmo existente na esperança de extrair mais economias de multiplicação. Tomando o algoritmo do AlphaTensor para matrizes de módulo 2 de 5 por 5 como ponto de partida, eles ficaram surpresos ao descobrir que seu método reduziu o número de etapas de multiplicação de 96 para 95 após apenas alguns segundos de computação.
O AlphaTensor também os ajudou a fazer outra melhoria indiretamente. Anteriormente, Kauers e Moosbauer não se preocupavam em explorar o espaço de matrizes 4 por 4, acreditando que não seria possível vencer duas iterações do algoritmo de Strassen. O resultado do AlphaTensor os levou a reconsiderar e, após uma semana de tempo de computação começando do zero, seu método revelou outro algoritmo de 47 etapas não relacionado ao que o AlphaTensor havia descoberto. “Se alguém nos dissesse que há algo a descobrir para 4 por 4, poderíamos ter feito isso antes”, disse Kauers. “Mas tudo bem, bem, é assim que funciona.”
Littman espera mais surpresas como essa, comparando a situação com a primeira vez que um corredor terminou uma milha em menos de quatro minutos, um feito que era amplamente considerado impossível. “As pessoas diziam: “Ah, espere, podemos fazer isso”, e agora muitas pessoas podem fazer isso”, disse ele.
Olhando para o futuro, Fawzi espera generalizar o AlphaTensor para lidar com uma gama mais ampla de tarefas matemáticas e computacionais, assim como seu ancestral AlphaGo acabou se ramificando em outros jogos.
Kauers vê isso como o verdadeiro teste decisivo para a aplicação do machine learning na descoberta de novos algoritmos. Ele destaca que a busca por algoritmos de multiplicação de matrizes rápidos é um problema combinatório para o qual as buscas por computador, com ou sem assistência humana, são bem adequadas. Mas nem todos os problemas matemáticos são tão fáceis de definir. Se o machine learning puder descobrir uma ideia algorítmica qualitativamente nova, disse ele, “isso seria um divisor de águas”.
Publicado em 28/11/2022 10h23
Artigo original:
Estudo original: