Deep Mind AlphaTensor descobrirá novos algoritmos

A Deep Mind estendeu o AlphaZero à matemática para desbloquear novas possibilidades de algoritmos de pesquisa.

AlphaTensor, baseia-se no AlphaZero, um agente que mostrou desempenho sobre-humano em jogos de tabuleiro, como xadrez, Go e shogi, e este trabalho mostra a jornada do AlphaZero de jogar até resolver problemas matemáticos não resolvidos pela primeira vez.

Os antigos egípcios criaram um algoritmo para multiplicar dois números sem a necessidade de uma tabela de multiplicação, e o matemático grego Euclides descreveu um algoritmo para calcular o máximo divisor comum, que ainda está em uso hoje.

Durante a Idade de Ouro Islâmica, o matemático persa Muhammad ibn Musa al-Khwarizmi projetou novos algoritmos para resolver equações lineares e quadráticas. De fato, o nome de al-Khwarizmi, traduzido para o latim como Algoritmi, levou ao termo algoritmo. Mas, apesar da familiaridade com os algoritmos hoje – usados ​​em toda a sociedade, desde a álgebra em sala de aula até a pesquisa científica de ponta – o processo de descoberta de novos algoritmos é incrivelmente difícil e um exemplo das incríveis habilidades de raciocínio da mente humana.

Eles publicaram na Nature. AlphaTensor é o primeiro sistema de inteligência artificial (IA) para descobrir algoritmos novos, eficientes e comprovadamente corretos para tarefas fundamentais, como multiplicação de matrizes. Isso lança luz sobre uma questão aberta de 50 anos em matemática sobre encontrar a maneira mais rápida de multiplicar duas matrizes.

Treinado do zero, o AlphaTensor descobre algoritmos de multiplicação de matrizes que são mais eficientes do que os algoritmos humanos e projetados por computador existentes. Apesar de melhorar os algoritmos conhecidos, eles observam que uma limitação do AlphaTensor é a necessidade de pré-definir um conjunto de entradas de fatores potenciais F, que discretiza o espaço de busca, mas pode levar à perda de algoritmos eficientes. Uma direção interessante para pesquisas futuras é adaptar o AlphaTensor para procurar F. Um ponto forte importante do AlphaTensor é sua flexibilidade para suportar recompensas estocásticas complexas e não diferenciáveis ​​(da classificação do tensor à eficiência prática em hardware específico), além de encontrar algoritmos para operações personalizadas em uma ampla variedade de espaços (como campos finitos). Eles acreditam que isso estimulará as aplicações do AlphaTensor para projetar algoritmos que otimizem métricas que não consideramos aqui, como estabilidade numérica ou uso de energia.

A descoberta de algoritmos de multiplicação de matrizes tem implicações de longo alcance, pois a multiplicação de matrizes está no centro de muitas tarefas computacionais, como inversão de matrizes, cálculo do determinante e resolução de sistemas lineares.

O processo e o progresso da automatização da descoberta algorítmica
Primeiro, eles converteram o problema de encontrar algoritmos eficientes para multiplicação de matrizes em um jogo para um jogador. Neste jogo, o tabuleiro é um tensor tridimensional (matriz de números), capturando o quão longe de correto está o algoritmo atual. Através de um conjunto de movimentos permitidos, correspondentes às instruções do algoritmo, o jogador tenta modificar o tensor e zerar suas entradas. Quando o jogador consegue fazer isso, isso resulta em um algoritmo de multiplicação de matriz comprovadamente correto para qualquer par de matrizes, e sua eficiência é capturada pelo número de passos dados para zerar o tensor.

Este jogo é incrivelmente desafiador – o número de algoritmos possíveis a serem considerados é muito maior do que o número de átomos no universo, mesmo para pequenos casos de multiplicação de matrizes. Comparado ao jogo Go, que permaneceu um desafio para a IA por décadas, o número de movimentos possíveis em cada etapa do jogo é 30 ordens de magnitude maior (acima de 10^33 para uma das configurações que eles consideram).

Essencialmente, para jogar bem este jogo, é preciso identificar a menor das agulhas em um gigantesco palheiro de possibilidades. Para enfrentar os desafios deste domínio, que se afasta significativamente dos jogos tradicionais, desenvolvemos vários componentes cruciais, incluindo uma nova arquitetura de rede neural que incorpora vieses indutivos específicos do problema, um procedimento para gerar dados sintéticos úteis e uma receita para alavancar simetrias do problema.

Eles então treinaram um agente AlphaTensor usando aprendizado por reforço para jogar o jogo, começando sem nenhum conhecimento sobre os algoritmos de multiplicação de matrizes existentes. Através do aprendizado, o AlphaTensor melhora gradualmente ao longo do tempo, redescobrindo algoritmos históricos de multiplicação de matriz rápida, como o de Strassen, eventualmente ultrapassando o reino da intuição humana e descobrindo algoritmos mais rápido do que o conhecido anteriormente.

Explorando o impacto em futuras pesquisas e aplicações
Do ponto de vista matemático, seus resultados podem orientar novas pesquisas em teoria da complexidade, que visa determinar os algoritmos mais rápidos para resolver problemas computacionais. Ao explorar o espaço de possíveis algoritmos de maneira mais eficaz do que as abordagens anteriores, o AlphaTensor ajuda a avançar nossa compreensão da riqueza dos algoritmos de multiplicação de matrizes. Compreender este espaço pode desbloquear novos resultados para ajudar a determinar a complexidade assintótica da multiplicação de matrizes, um dos problemas abertos mais fundamentais em ciência da computação.

Como a multiplicação de matrizes é um componente central em muitas tarefas computacionais, abrangendo computação gráfica, comunicações digitais, treinamento de rede neural e computação científica, os algoritmos descobertos pelo AlphaTensor podem tornar os cálculos nesses campos significativamente mais eficientes. A flexibilidade do AlphaTensor para considerar qualquer tipo de objetivo também pode estimular novas aplicações para projetar algoritmos que otimizem métricas como uso de energia e estabilidade numérica, ajudando a evitar que pequenos erros de arredondamento se transformem em bola de neve à medida que um algoritmo funciona.

Enquanto eles se concentraram aqui no problema específico da multiplicação de matrizes, esperamos que nosso artigo inspire outros a usar a IA para orientar a descoberta algorítmica para outras tarefas computacionais fundamentais. Sua pesquisa também mostra que o AlphaZero é um algoritmo poderoso que pode ser estendido muito além do domínio dos jogos tradicionais para ajudar a resolver problemas abertos em matemática. Com base em nossa pesquisa, eles esperam estimular um trabalho maior – aplicando a IA para ajudar a sociedade a resolver alguns dos desafios mais importantes da matemática e das ciências.

Natureza – Descobrindo algoritmos de multiplicação de matrizes mais rápidos com aprendizado por reforço

Sumário
Melhorar a eficiência dos algoritmos para cálculos fundamentais pode ter um impacto generalizado, pois pode afetar a velocidade geral de uma grande quantidade de cálculos. A multiplicação de matrizes é uma dessas tarefas primitivas, ocorrendo em muitos sistemas – de redes neurais a rotinas de computação científica. A descoberta automática de algoritmos usando aprendizado de máquina oferece a perspectiva de ir além da intuição humana e superar os atuais melhores algoritmos projetados por humanos. No entanto, automatizar o procedimento de descoberta de algoritmos é intrincado, pois o espaço de algoritmos possíveis é enorme. Aqui relatamos uma abordagem de aprendizado por reforço profundo baseada no AlphaZero1 para descobrir algoritmos eficientes e comprovadamente corretos para a multiplicação de matrizes arbitrárias. Nosso agente, AlphaTensor, é treinado para jogar um jogo single-player onde o objetivo é encontrar decomposições de tensores dentro de um espaço de fator finito. O AlphaTensor descobriu algoritmos que superam a complexidade de última geração para muitos tamanhos de matriz. Particularmente relevante é o caso de matrizes 4 × 4 em um corpo finito, onde o algoritmo de AlphaTensor melhora o algoritmo de dois níveis de Strassen pela primeira vez, até onde sabemos, desde sua descoberta há 50 anos2. Mostramos ainda a flexibilidade do AlphaTensor por meio de diferentes casos de uso: algoritmos com complexidade de última geração para multiplicação de matriz estruturada e eficiência prática aprimorada, otimizando a multiplicação de matriz para tempo de execução em hardware específico. Nossos resultados destacam a capacidade do AlphaTensor de acelerar o processo de descoberta algorítmica em uma variedade de problemas e otimizar para diferentes critérios.