IA revela novas possibilidades na multiplicação de matrizes

Os matemáticos adoram um bom quebra-cabeça. Mesmo algo tão abstrato quanto a multiplicação de matrizes (tabelas bidimensionais de números) 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 etapa é 18; para multiplicação de matrizes, mesmo em casos relativamente simples, cada passo pode apresentar mais de 10¹² 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 enfrentar o problema de uma nova direção, relatando em um papel in Natureza 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 mágico monstruosamente complexo.

“É um resultado muito bom”, disse Josh Alman, um 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 que para provar o ponto, três dias após o Natureza Após a publicação do artigo, uma dupla de pesquisadores austríacos ilustrou como métodos novos e antigos podem se complementar. Eles usaram uma busca convencional auxiliada por computador para melhoramento futuro um dos algoritmos que a rede neural havia descoberto.

Os resultados sugerem que, assim como o processo de resolução de um cubo de Rubik, o caminho para melhores algoritmos será cheio de voltas e reviravoltas.

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 n-A-n matrizes, cada uma com n² elementos, você multiplica e soma esses elementos em combinações particulares para gerar o produto, um terceiro n-A-n matriz. A receita padrão para multiplicar dois n-A-n matrizes requer n³ operações de multiplicação, portanto, 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. Cada uma dessas matrizes pode então 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 dois n-A-n matrizes e deixe 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 Registro atual para a melhor escala, n^2.3728596, pertence a Alman e Virgínia Vassilevska Williams, cientista da computação do Instituto de Tecnologia de Massachusetts. (Recentemente não publicado pré-impressão relataram uma pequena melhoria usando uma nova técnica.) Mas esses algoritmos são de interesse puramente teórico, vencendo métodos como o de Strassen apenas para matrizes absurdamente grandes.

O segundo subcampo pensa em menor escala. 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 matriz, 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 descomunal, já que repetidas iterações 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 menu estonteante de opções, os pesquisadores fizeram progressos ao transformar a multiplicação de matrizes no que parece ser um problema matemático totalmente diferente – um problema 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 de “classe 1”; cada um deles representará uma etapa 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 de tensor — quanto menos termos, menos etapas envolvidas.

Desta forma, os pesquisadores descobriram novos algoritmos que se multiplicam n-A-n matrizes usando menos do que o padrão n³ etapas de multiplicaçã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.

Game On

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 aprendizado profundo 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 aprendizado profundo 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 ao longo de 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.

No novo algoritmo do 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 classificação 1 que o AlphaTensor escolheu para seu primeiro movimento. O algoritmo subtrai esse tensor de classificação 1 da entrada inicial, produzindo um tensor atualizado que é realimentado na rede como uma nova entrada. O processo se repete até que todos os elementos no tensor inicial tenham sido reduzidos a zero, o que significa que não há mais tensores de nível 1 para remover.

Nesse ponto, a rede neural descobriu uma decomposição de tensor válida, pois é matematicamente garantido que a soma de todos os tensores de classificação 1 é exatamente igual ao tensor inicial. E as etapas necessárias para chegar lá podem ser convertidas 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 nível 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 uma face perfeitamente ordenada em um cubo de Rubik antes de resolver tudo.

A equipe agora tinha um algoritmo que poderia, teoricamente, resolver o problema. Eles apenas tiveram 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. Foram poucos os exemplos de decomposições eficientes que os pesquisadores puderam 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 nível 1 gerados aleatoriamente.

“Eles estão usando o problema fácil para produzir mais dados para o problema difícil”, disse Michael Littman, um cientista da computação da Brown University. A combinação desse procedimento de treinamento reverso com o aprendizado por reforço, em que o AlphaTensor gerou seus próprios dados de treinamento enquanto procurava decomposições eficientes, funcionou muito melhor do que qualquer um dos métodos de treinamento por conta própria.

A equipe do DeepMind treinou o AlphaTensor para decompor tensores que representam a multiplicação de matrizes 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 de módulo 2. (Esta é matemática baseada em apenas dois números, então os elementos da matriz podem ser apenas 0 ou 1 e 1 + 1 = 0.) Os pesquisadores geralmente começam com esse espaço mais restrito, mas ainda assim 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 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 passos de multiplicação.

Em alguns casos, o AlphaTensor até bateu os 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 5 5 por 2, reduzindo o número de multiplicações necessárias do recorde anterior de 98 para 96. (Mas esse novo recorde ainda está atrás dos 91 passos que seriam necessários para bater Algoritmo de Strassen usando matrizes 5 por 5.)

O novo resultado de alto perfil criou muita emoçã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. “Achei que foi um pouco exagerado”, disse Vassilevska Williams. “É outra ferramenta. Não é como, 'Oh, os computadores vencem os humanos', sabe?”

Os pesquisadores também enfatizaram que as aplicações imediatas do algoritmo recorde de 4 por 4 seriam limitadas: não apenas é 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 realmente, este é apenas o começo. “Há muito espaço para melhorias e pesquisas, e isso é bom”, 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 a aparência de bons algoritmos, por isso não pode explicar suas escolhas. Isso torna difícil para os pesquisadores aprenderem com suas realizações.

Mas isso pode não ser uma desvantagem tão grande quanto parece. Alguns 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 saiu, Kauers e Moosbauer estavam no processo de busca de 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 economia de multiplicação dele. Tomando o algoritmo do AlphaTensor para matrizes de módulo 5 5 por 2 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 haviam se preocupado 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 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, é assim que funciona.”

Littman espera mais surpresas desse tipo, 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, 'Oh, espere, nós 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 eventualmente se ramificou em outros jogos.

Kauers vê isso como o verdadeiro teste decisivo para a aplicação do aprendizado de máquina para descobrir novos algoritmos. Ele aponta que a busca por algoritmos de multiplicação rápida de matrizes é um problema combinatório para o qual pesquisas de 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 aprendizado de máquina puder descobrir uma ideia algorítmica qualitativamente nova, disse ele, “isso mudaria o jogo”.