Algoritmi di ordinamento più rapidi scoperti utilizzando l'apprendimento per rinforzo profondo

Natura volume 618, pagine 257–263 (2023) Citare questo articolo

355k accessi

1 Citazioni

1148 Altmetrico

Dettagli sulle metriche

Algoritmi fondamentali come l'ordinamento o l'hashing vengono utilizzati trilioni di volte in un dato giorno1. Con la crescita della domanda di calcolo, è diventato fondamentale che questi algoritmi siano quanto più performanti possibile. Sebbene in passato siano stati compiuti notevoli progressi2, apportare ulteriori miglioramenti all’efficienza di queste routine si è rivelato impegnativo sia per gli scienziati umani che per gli approcci computazionali. Qui mostriamo come l’intelligenza artificiale può andare oltre l’attuale stato dell’arte scoprendo routine finora sconosciute. Per realizzare ciò, abbiamo formulato il compito di trovare una migliore routine di ordinamento come gioco per giocatore singolo. Abbiamo quindi addestrato un nuovo agente di apprendimento per rinforzo profondo, AlphaDev, a giocare a questo gioco. AlphaDev ha scoperto da zero piccoli algoritmi di ordinamento che hanno superato i parametri di riferimento umani precedentemente noti. Questi algoritmi sono stati integrati nella libreria di ordinamento C++ standard LLVM3. Questa modifica a questa parte della libreria di ordinamento rappresenta la sostituzione di un componente con un algoritmo che è stato scoperto automaticamente utilizzando l'apprendimento per rinforzo. Presentiamo anche risultati in domini aggiuntivi, mostrando la generalità dell'approccio.

L’intuizione e il know-how umani sono stati cruciali nel miglioramento degli algoritmi. Tuttavia, molti algoritmi hanno raggiunto uno stadio in cui gli esperti umani non sono più in grado di ottimizzarli ulteriormente, il che porta a un collo di bottiglia computazionale sempre crescente. Il lavoro nella letteratura classica sulla sintesi dei programmi, che abbraccia molti decenni, mira a generare programmi corretti e/o ottimizzare programmi utilizzando proxy per la latenza. Questi includono tecniche di ricerca enumerativa4,5,6,7 e ricerca stocastica5,6,8,9,10 nonché la tendenza più recente all'utilizzo del deep learning nella sintesi dei programmi per generare programmi corretti11,12,13,14,15,16 . Utilizzando l'apprendimento profondo per rinforzo (DRL), possiamo fare un ulteriore passo avanti generando algoritmi corretti ed efficienti ottimizzando la latenza misurata effettiva a livello di istruzione della CPU, cercando e considerando in modo più efficiente lo spazio dei programmi corretti e veloci rispetto al lavoro precedente .

Una delle domande fondamentali in informatica è come ordinare una sequenza17,18,19,20. Questo viene insegnato nelle classi elementari di informatica in tutto il mondo21,22 ed è utilizzato ovunque in una vasta gamma di applicazioni23,24,25. Decenni di ricerca informatica si sono concentrati sulla scoperta e sull'ottimizzazione degli algoritmi di ordinamento26,27,28. Una componente chiave delle soluzioni pratiche è un piccolo ordinamento su una breve sequenza di elementi; questo algoritmo viene chiamato ripetutamente quando si ordinano array di grandi dimensioni che utilizzano approcci divide et impera29. In questo lavoro, ci concentreremo su due tipi di algoritmi di ordinamento piccolo: (1) l'ordinamento fisso e (2) l'ordinamento variabile. Gli algoritmi di ordinamento fisso ordinano sequenze di lunghezza fissa (ad esempio, sort 3 può ordinare solo sequenze di lunghezza 3), mentre gli algoritmi di ordinamento variabile possono ordinare sequenze di dimensioni variabili (ad esempio, variable sort 5 può ordinare sequenze che vanno da uno a cinque elementi).

Formuliamo il problema di scoprire nuovi ed efficienti algoritmi di ordinamento come un gioco per giocatore singolo a cui ci riferiamo come AssemblyGame. In questo gioco, il giocatore seleziona una serie di istruzioni della CPU di basso livello, a cui ci riferiamo come istruzioni di assemblaggio30, da combinare per produrre un nuovo ed efficiente algoritmo di ordinamento. Ciò è impegnativo poiché il giocatore deve considerare lo spazio combinatorio delle istruzioni di assemblaggio per produrre un algoritmo che sia allo stesso tempo corretto e veloce. La durezza dell'AssemblyGame deriva non solo dalla dimensione dello spazio di ricerca, che è simile a giochi estremamente impegnativi come gli scacchi (10120 giochi)31 e il Go (10700 giochi)32, ma anche dalla natura della funzione di ricompensa. Una singola istruzione errata nell'AssemblyGame può potenzialmente invalidare l'intero algoritmo, rendendo l'esplorazione in questo spazio di giochi incredibilmente impegnativa.