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

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

Accessi 88k

952 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.

) to the current algorithm generated thus far. A reward rtis received that comprises both a measure of algorithm correctness and latency. Algorithm correctness (Fig. 2b) involves inputting a set of N test sequences into the current algorithm Pt to generate N outputs. These outputs are then compared to the expected outputs and a correctness reward rt is computed. Latency rewards can be generated by either (1) penalizing the agent for increasing the length of the algorithm (when length and latency are highly correlated) that we refer to as the algorithm length reward, or (2) measuring the actual latency of the algorithm. The game is executed for a limited number of steps, after which the game is terminated. Winning the game corresponds to generating a correct, low-latency algorithm using assembly instructions. Losing the game corresponds to generating an incorrect algorithm or a correct but inefficient algorithm./p> assembly instruction, which is appended to the current algorithm. The agent receives a reward that is a function of the algorithm's correctness, discussed in b, as well as the algorithm's latency. The game is won by the player discovering a low latency, correct algorithm. b, The program correctness and latency computations are used to compute the reward rt. In this example, test sequences are input to the algorithm; for example, in the case of sorting three elements, test inputs comprise all sequences of unsorted elements of length 3. For each sequence, the algorithm output is compared to the expected output (in the case of sorting, the expected output is the sorted elements). In this example, the output \({\bf{D}}{\boldsymbol{{\prime} }}\) does not match the expected output \({\bf{B}}{\boldsymbol{{\prime} }}\) and the algorithm is therefore incorrect./p>