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

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

88k acessos

794 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 um progresso notável tenha sido alcançado no passado2, fazer melhorias adicionais na eficiência dessas rotinas provou ser um desafio para cientistas humanos e 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 realizar 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 aprendizado por reforço profundo, AlphaDev, para jogar este jogo. O AlphaDev descobriu pequenos algoritmos de classificação do zero que superaram os benchmarks humanos conhecidos anteriormente. Esses algoritmos foram integrados à biblioteca de classificação C++ padrão LLVM3. Essa alteração nessa parte da biblioteca de classificação representa a substituição de um componente por um algoritmo que foi descoberto automaticamente usando o aprendizado 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 para melhorar os algoritmos. No entanto, muitos algoritmos atingiram um estágio em que 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, abrangendo muitas décadas, visa gerar programas corretos e/ou otimizar programas usando proxies para latência. Isso inclui 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 aprendizado profundo na síntese de programas para gerar programas corretos11,12,13,14,15,16 . Usando o aprendizado por reforço profundo (DRL), podemos dar um passo adiante, gerando algoritmos corretos e de alto desempenho, otimizando a latência medida real no nível de instrução da CPU, pesquisando e considerando com mais eficiência 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. Isso é 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 se concentraram na descoberta e otimização de algoritmos de classificação26,27,28. Um componente-chave de soluções práticas é uma pequena classificação em uma sequência curta de elementos; esse algoritmo é chamado repetidamente ao classificar grandes matrizes que usam abordagens de divisão e conquista29. Neste trabalho, focamos em dois tipos de algoritmos de ordenação pequena: (1) a ordenação fixa e (2) a ordenação variável. Algoritmos de classificação fixa classificam sequências de comprimento fixo (por exemplo, classificação 3 pode classificar apenas 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 ordenação novos e eficientes como um jogo para um jogador que chamamos de AssemblyGame. Nesse jogo, o jogador seleciona uma série de instruções de CPU de baixo nível, às quais nos referimos como instruções de montagem30, para combinar e produzir um novo e eficiente algoritmo de classificação. Isso é desafiador, 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 dificuldade do AssemblyGame decorre não apenas do tamanho do espaço de busca, que é semelhante a jogos extremamente desafiadores como xadrez (10120 jogos)31 e Go (10700 jogos)32, mas também da natureza da função de recompensa. Uma única instrução incorreta no AssemblyGame pode potencialmente invalidar todo o algoritmo, tornando a exploração neste espaço de jogos incrivelmente desafiadora.