Scoprire nuovi algoritmi con AlphaTensor

'Scoprire nuovi algoritmi con AlphaTensor.'

Prima estensione di AlphaZero alla matematica apre nuove possibilità per la ricerca

Gli algoritmi hanno aiutato i matematici a eseguire operazioni fondamentali per migliaia di anni. Gli antichi Egizi crearono un algoritmo per moltiplicare due numeri senza richiedere una tabella di moltiplicazione, e il matematico greco Euclide descrisse un algoritmo per calcolare il massimo comun divisore, che è ancora in uso oggi.

Durante l’Età dell’Oro Islamica, il matematico persiano Muhammad ibn Musa al-Khwarizmi progettò nuovi algoritmi per risolvere equazioni lineari e quadratiche. Infatti, il nome di al-Khwarizmi, tradotto in latino come Algoritmi, portò al termine algoritmo. Ma nonostante la familiarità con gli algoritmi oggi – utilizzati in tutta la società dall’algebra in classe alla ricerca scientifica all’avanguardia – il processo di scoperta di nuovi algoritmi è incredibilmente difficile ed è un esempio delle straordinarie capacità di ragionamento della mente umana.

Nel nostro articolo, pubblicato oggi su Nature, presentiamo AlphaTensor, il primo sistema di intelligenza artificiale (IA) per scoprire algoritmi nuovi, efficienti e provabilmente corretti per compiti fondamentali come la moltiplicazione di matrici. Ciò getta luce su una questione aperta da 50 anni in matematica riguardante il trovare il modo più veloce per moltiplicare due matrici.

Questo articolo è una pietra miliare nella missione di DeepMind di far avanzare la scienza e risolvere i problemi più fondamentali utilizzando l’IA. Il nostro sistema, AlphaTensor, si basa su AlphaZero, un agente che ha dimostrato prestazioni sovrumane nei giochi da tavolo, come scacchi, Go e shogi, e questo lavoro mostra il percorso di AlphaZero dall’essere un giocatore di giochi all’affrontare per la prima volta problemi matematici irrisolti.

Moltiplicazione di matrici

La moltiplicazione di matrici è una delle operazioni più semplici dell’algebra, comunemente insegnata nelle lezioni di matematica delle scuole superiori. Ma al di fuori della classe, questa umile operazione matematica ha un’enorme influenza nel mondo digitale contemporaneo ed è ubiqua nel calcolo moderno.

Esempio del processo di moltiplicazione di due matrici 3x3.

Questa operazione viene utilizzata per elaborare immagini sugli smartphone, riconoscere comandi vocali, generare grafica per videogiochi, eseguire simulazioni per prevedere il tempo, comprimere dati e video per la condivisione su Internet e molto altro ancora. Aziende di tutto il mondo spendono grandi quantità di tempo e denaro nello sviluppo di hardware informatico per moltiplicare efficientemente le matrici. Quindi, anche miglioramenti minori nell’efficienza della moltiplicazione di matrici possono avere un impatto diffuso.

Per secoli, i matematici hanno creduto che l’algoritmo standard per la moltiplicazione di matrici fosse il migliore che si potesse ottenere in termini di efficienza. Ma nel 1969, il matematico tedesco Volker Strassen ha sconvolto la comunità matematica mostrando che esistono algoritmi migliori.

Algoritmo standard confrontato con l'algoritmo di Strassen, che utilizza una moltiplicazione scalare in meno (7 invece di 8) per moltiplicare matrici 2x2. Le moltiplicazioni contano molto di più delle addizioni per l'efficienza complessiva.

Studiando matrici molto piccole (dimensione 2×2), ha scoperto un modo ingegnoso per combinare le entrate delle matrici per ottenere un algoritmo più veloce. Nonostante decenni di ricerca successivi alla scoperta di Strassen, versioni più grandi di questo problema sono rimaste irrisolte – al punto che non si sa quanto sia efficiente moltiplicare due matrici grandi quanto 3×3.

Nel nostro articolo, abbiamo esplorato come le moderne tecniche di intelligenza artificiale potessero far progredire la scoperta automatica di nuovi algoritmi per la moltiplicazione di matrici. Sulla base dei progressi dell’intuizione umana, AlphaTensor ha scoperto algoritmi più efficienti rispetto allo stato dell’arte per molte dimensioni delle matrici. I nostri algoritmi progettati dall’IA superano quelli progettati dagli esseri umani, il che rappresenta un grande passo avanti nel campo della scoperta algoritmica.

Il processo e il progresso dell’automazione della scoperta algoritmica

Prima di tutto, abbiamo convertito il problema della ricerca di algoritmi efficienti per la moltiplicazione di matrici in un gioco per giocatore singolo. In questo gioco, la scacchiera è un tensore tridimensionale (un array di numeri), che cattura quanto il metodo attuale sia distante dalla correttezza. Attraverso un insieme di mosse consentite, corrispondenti alle istruzioni dell’algoritmo, il giocatore cerca di modificare il tensore e azzerare le sue voci. Quando il giocatore riesce a farlo, si ottiene un algoritmo di moltiplicazione di matrici provabilmente corretto per qualsiasi coppia di matrici, e la sua efficienza è misurata dal numero di mosse necessarie per azzerare il tensore.

Questo gioco è incredibilmente sfidante: il numero di algoritmi possibili da considerare è molto più grande del numero di atomi nell’universo, anche per casi di moltiplicazione di matrici di piccole dimensioni. Rispetto al gioco del Go, che è rimasto una sfida per l’IA per decenni, il numero di mosse possibili ad ogni passo del nostro gioco è 30 ordini di grandezza più grande (oltre 10^33 per una delle configurazioni che consideriamo).

In sostanza, per giocare bene a questo gioco, bisogna identificare gli aghi più piccoli in un’enorme massa di possibilità. Per affrontare le sfide di questo dominio, che si discosta significativamente dai giochi tradizionali, abbiamo sviluppato diversi componenti cruciali, tra cui un’architettura di rete neurale innovativa che incorpora bias induttivi specifici del problema, una procedura per generare dati sintetici utili e una ricetta per sfruttare le simmetrie del problema.

In seguito abbiamo addestrato un agente AlphaTensor utilizzando l’apprendimento per rinforzo per giocare al gioco, partendo senza alcuna conoscenza sugli algoritmi di moltiplicazione di matrici esistenti. Attraverso l’apprendimento, AlphaTensor migliora gradualmente nel tempo, riscoprendo gradualmente algoritmi storici di moltiplicazione di matrici veloci come quello di Strassen, superando infine il regno dell’intuizione umana e scoprendo algoritmi più veloci di quelli precedentemente conosciuti.

Gioco per giocatore singolo giocato da AlphaTensor, in cui l'obiettivo è trovare un algoritmo corretto di moltiplicazione di matrici. Lo stato del gioco è un array cubico di numeri (mostrato come grigio per 0, blu per 1 e verde per -1), che rappresenta il lavoro rimanente da fare.

Ad esempio, se l’algoritmo tradizionale insegnato a scuola moltiplica una matrice 4×5 per una matrice 5×5 usando 100 moltiplicazioni, e questo numero viene ridotto a 80 con l’ingegno umano, AlphaTensor ha trovato algoritmi che eseguono la stessa operazione usando solo 76 moltiplicazioni.

Algoritmo scoperto da AlphaTensor utilizzando 76 moltiplicazioni, un miglioramento rispetto agli algoritmi all'avanguardia.

Oltre a questo esempio, l’algoritmo di AlphaTensor migliora l’algoritmo a due livelli di Strassen in un campo finito per la prima volta dai suoi 50 anni di scoperta. Questi algoritmi per la moltiplicazione di matrici di piccole dimensioni possono essere utilizzati come primitive per moltiplicare matrici molto più grandi di dimensioni arbitrarie.

Inoltre, AlphaTensor scopre anche un insieme diversificato di algoritmi con complessità all’avanguardia, fino a migliaia di algoritmi di moltiplicazione di matrici per ogni dimensione, dimostrando che lo spazio degli algoritmi di moltiplicazione di matrici è più ricco di quanto si pensasse in precedenza.

Gli algoritmi in questo spazio ricco hanno proprietà matematiche e pratiche diverse. Sfruttando questa diversità, abbiamo adattato AlphaTensor per trovare specificamente algoritmi che sono veloci su un hardware specifico, come Nvidia V100 GPU e Google TPU v2. Questi algoritmi moltiplicano matrici grandi dal 10% al 20% più velocemente rispetto agli algoritmi comunemente utilizzati sull’hardware stesso, dimostrando la flessibilità di AlphaTensor nell’ottimizzare obiettivi arbitrari.

AlphaTensor con un obiettivo corrispondente al tempo di esecuzione dell'algoritmo. Quando viene scoperto un algoritmo corretto di moltiplicazione di matrici, viene testato sul hardware di destinazione, che viene quindi restituito ad AlphaTensor, al fine di apprendere algoritmi più efficienti sull'hardware di destinazione.

Esplorando l’impatto sulla ricerca futura e sulle applicazioni

Dal punto di vista matematico, i nostri risultati possono orientare ulteriori ricerche sulla teoria della complessità, che mira a determinare gli algoritmi più veloci per risolvere problemi computazionali. Esplorando lo spazio degli algoritmi possibili in modo più efficace rispetto ai precedenti approcci, AlphaTensor contribuisce a far progredire la nostra comprensione sulla ricchezza degli algoritmi di moltiplicazione di matrici. Comprendere questo spazio potrebbe aprirsi a nuovi risultati che aiutino a determinare la complessità asintotica della moltiplicazione di matrici, uno dei problemi aperti più fondamentali in informatica.

Poiché la moltiplicazione delle matrici è un componente fondamentale in molti compiti computazionali, che spaziano dalla grafica computerizzata alle comunicazioni digitali, all’addestramento delle reti neurali e al calcolo scientifico, gli algoritmi scoperti da AlphaTensor potrebbero rendere i calcoli in questi campi significativamente più efficienti. La flessibilità di AlphaTensor nel considerare qualsiasi tipo di obiettivo potrebbe anche stimolare nuove applicazioni per la progettazione di algoritmi che ottimizzano metriche come l’utilizzo dell’energia e la stabilità numerica, contribuendo a evitare che piccoli errori di arrotondamento si accumulino durante l’esecuzione di un algoritmo.

Mentre ci siamo concentrati qui sul problema specifico della moltiplicazione delle matrici, speriamo che il nostro articolo ispiri altri a utilizzare l’IA per guidare la scoperta algoritmica per altri compiti computazionali fondamentali. La nostra ricerca mostra anche che AlphaZero è un potente algoritmo che può essere esteso ben oltre il dominio dei giochi tradizionali per aiutare a risolvere problemi aperti in matematica. Sulla base della nostra ricerca, speriamo di stimolare un maggior numero di lavori che applicano l’IA per aiutare la società a risolvere alcune delle sfide più importanti in matematica e nelle scienze in generale.

Puoi trovare ulteriori informazioni nel repository GitHub di AlphaTensor.