Algoritmos de classificação mais rápidos descobertos usando aprendizagem por reforço profundo

Nature volume 618, páginas 257–263 (2023)Cite este artigo

355 mil acessos

1 Citações

1148 Altmétrico

Detalhes das métricas

Algoritmos fundamentais, como classificação ou hash, são usados ​​trilhões de vezes em um determinado dia1. À medida que a demanda por computação cresce, tornou-se crítico que esses algoritmos tenham o melhor desempenho possível. Embora tenham sido alcançados progressos notáveis ​​no passado2, fazer novas melhorias na eficiência destas rotinas revelou-se um desafio tanto para os cientistas humanos como para as abordagens computacionais. Aqui mostramos como a inteligência artificial pode ir além do atual estado da arte ao descobrir rotinas até então desconhecidas. Para perceber isso, formulamos a tarefa de encontrar uma rotina de classificação melhor como um jogo para um jogador. Em seguida, treinamos um novo agente de aprendizagem por reforço profundo, AlphaDev, para jogar este jogo. AlphaDev descobriu pequenos algoritmos de classificação do zero que superaram os benchmarks humanos anteriormente conhecidos. Esses algoritmos foram integrados à biblioteca de classificação C++ padrão LLVM3. Esta mudança nesta parte da biblioteca de classificação representa a substituição de um componente por um algoritmo que foi descoberto automaticamente usando aprendizagem por reforço. Também apresentamos resultados em domínios extras, mostrando a generalidade da abordagem.

A intuição e o know-how humanos têm sido cruciais na melhoria dos algoritmos. No entanto, muitos algoritmos atingiram um estágio em que os especialistas humanos não foram capazes de otimizá-los ainda mais, levando a um gargalo computacional cada vez maior. O trabalho na literatura clássica de síntese de programas, que se estende por muitas décadas, visa gerar programas corretos e/ou otimizar programas usando proxies para latência. Estas incluem técnicas de pesquisa enumerativa4,5,6,7 e pesquisa estocástica5,6,8,9,10, bem como a tendência mais recente de usar aprendizagem profunda na síntese de programas para gerar programas corretos11,12,13,14,15,16 . Usando o aprendizado de reforço profundo (DRL), podemos dar um passo adiante, gerando algoritmos corretos e de alto desempenho, otimizando a latência real medida no nível de instrução da CPU, pesquisando e considerando de forma mais eficiente o espaço de programas corretos e rápidos em comparação com o trabalho anterior .

Uma das questões fundamentais na ciência da computação é como ordenar uma sequência17,18,19,20. Isto é ensinado em aulas elementares de ciência da computação em todo o mundo21,22 e é usado de forma onipresente por uma vasta gama de aplicações23,24,25. Décadas de pesquisa em ciência da computação concentraram-se na descoberta e otimização de algoritmos de classificação26,27,28. Um componente-chave das soluções práticas é uma pequena classificação em uma sequência curta de elementos; esse algoritmo é chamado repetidamente ao classificar grandes arrays que usam abordagens de divisão e conquista29. Neste trabalho, nos concentramos em dois tipos de algoritmos de classificação pequena: (1) a classificação fixa e (2) a classificação variável. Algoritmos de classificação fixa classificam sequências de comprimento fixo (por exemplo, classificação 3 só pode classificar sequências de comprimento 3), enquanto algoritmos de classificação variável podem classificar uma sequência de tamanho variável (por exemplo, classificação variável 5 pode classificar sequências que variam de um a cinco elementos).

Formulamos o problema de descobrir algoritmos de classificação novos e eficientes como um jogo para um jogador, ao qual nos referimos como AssemblyGame. Neste jogo, o jogador seleciona uma série de instruções de CPU de baixo nível, que chamamos de instruções de montagem30, para combinar para produzir um novo e eficiente algoritmo de classificação. Isso é um desafio, pois o jogador precisa considerar o espaço combinatório das instruções de montagem para produzir um algoritmo que seja comprovadamente correto e rápido. A dureza do AssemblyGame surge não apenas do tamanho do espaço de busca, que é semelhante a jogos extremamente desafiadores como xadrez (10.120 jogos)31 e Go (10.700 jogos)32, mas também da natureza da função de recompensa. Uma única instrução incorreta no AssemblyGame pode invalidar todo o algoritmo, tornando a exploração neste espaço de jogos incrivelmente desafiadora.