Deep Mind AlphaTensor scoprirà nuovi algoritmi

Deep Mind ha esteso AlphaZero alla matematica per sbloccare nuove possibilità di ricerca sugli algoritmi.

AlphaTensor, si basa su AlphaZero, un agente che ha mostrato prestazioni sovrumane nei giochi da tavolo, come gli scacchi, il Go e lo shogi, e questo lavoro mostra il viaggio di AlphaZero dal gioco all'affrontare per la prima volta problemi matematici irrisolti.

Gli antichi egizi crearono un algoritmo per moltiplicare due numeri senza richiedere una tavola pitagorica 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, ha portato al termine algoritmo. Ma, nonostante la familiarità con gli algoritmi di oggi – utilizzati in tutta la società, dall’algebra scolastica 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.

Hanno pubblicato su Nature. AlphaTensor è il primo sistema di intelligenza artificiale (AI) per la scoperta di algoritmi nuovi, efficienti e dimostrabilmente corretti per compiti fondamentali come la moltiplicazione di matrici. Ciò fa luce su una questione aperta da 50 anni in matematica su come trovare il modo più veloce per moltiplicare due matrici.

Addestrato da zero, AlphaTensor scopre algoritmi di moltiplicazione di matrici che sono più efficienti degli algoritmi esistenti progettati dall'uomo e dal computer. Nonostante i miglioramenti rispetto agli algoritmi conosciuti, notano che una limitazione di AlphaTensor è la necessità di predefinire una serie di potenziali voci di fattori F, che discretizzano lo spazio di ricerca ma possono eventualmente portare a perdere algoritmi efficienti. Una direzione interessante per la ricerca futura è quella di adattare AlphaTensor alla ricerca di F. Un importante punto di forza di AlphaTensor è la sua flessibilità nel supportare complesse ricompense stocastiche e non differenziabili (dal rango tensore all'efficienza pratica su hardware specifico), oltre a trovare algoritmi per operazioni personalizzate in un'ampia varietà di spazi (come campi finiti). Ritengono che ciò stimolerà le applicazioni di AlphaTensor verso la progettazione di algoritmi che ottimizzano le metriche che non abbiamo considerato qui, come la stabilità numerica o il consumo di energia.

La scoperta degli algoritmi di moltiplicazione di matrici ha implicazioni di vasta portata, poiché la moltiplicazione di matrici è al centro di molti compiti computazionali, come l’inversione di matrici, il calcolo del determinante e la risoluzione di sistemi lineari.

Il processo e il progresso dell'automazione della scoperta algoritmica
Innanzitutto, hanno convertito il problema di trovare algoritmi efficienti per la moltiplicazione di matrici in un gioco per giocatore singolo. In questo gioco, il tabellone è un tensore tridimensionale (una matrice di numeri), che cattura quanto sia lontano dall'essere corretto l'algoritmo attuale. Attraverso una serie di mosse consentite, corrispondenti alle istruzioni dell'algoritmo, il giocatore tenta di modificare il tensore e azzerarne le voci. Quando il giocatore riesce a farlo, ciò si traduce in un algoritmo di moltiplicazione di matrici dimostrabilmente corretto per qualsiasi coppia di matrici e la sua efficienza viene catturata dal numero di passaggi necessari per azzerare il tensore.

Questo gioco è incredibilmente impegnativo: il numero di possibili algoritmi da considerare è molto maggiore del numero di atomi nell’universo, anche per piccoli casi di moltiplicazione di matrici. Rispetto al gioco del Go, che è rimasto una sfida per l’intelligenza artificiale per decenni, il numero di mosse possibili in ogni fase del gioco è maggiore di 30 ordini di grandezza (oltre 10^33 per una delle impostazioni considerate).

In sostanza, per giocare bene a questo gioco, è necessario identificare il più piccolo degli aghi in un gigantesco pagliaio di possibilità. Per affrontare le sfide di questo dominio, che si discosta in modo significativo dai giochi tradizionali, abbiamo sviluppato molteplici componenti cruciali tra cui una nuova architettura di rete neurale che incorpora pregiudizi induttivi specifici del problema, una procedura per generare dati sintetici utili e una ricetta per sfruttare le simmetrie del problema.

Hanno quindi addestrato un agente AlphaTensor utilizzando l'apprendimento per rinforzo per giocare, iniziando senza alcuna conoscenza degli algoritmi di moltiplicazione di matrici esistenti. Attraverso l’apprendimento, AlphaTensor migliora gradualmente nel tempo, riscoprendo algoritmi storici di moltiplicazione di matrici veloci come quello di Strassen, superando infine il regno dell’intuizione umana e scoprendo algoritmi più velocemente di quanto precedentemente noto.

Esplorare l'impatto sulla ricerca e le applicazioni future
Da un punto di vista matematico, i loro risultati possono guidare ulteriori ricerche nella teoria della complessità, che mira a determinare gli algoritmi più veloci per risolvere problemi computazionali. Esplorando lo spazio dei possibili algoritmi in un modo più efficace rispetto agli approcci precedenti, AlphaTensor aiuta a far progredire la nostra comprensione della ricchezza degli algoritmi di moltiplicazione di matrici. Comprendere questo spazio può sbloccare nuovi risultati per aiutare a determinare la complessità asintotica della moltiplicazione di matrici, uno dei problemi aperti più fondamentali nell’informatica.

Poiché la moltiplicazione di matrici è una componente fondamentale in molte attività di calcolo, che vanno dalla computer grafica, 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 di energia e la stabilità numerica, aiutando a prevenire piccoli errori di arrotondamento che si verificano durante il funzionamento di un algoritmo.

Anche se qui si sono concentrati sul particolare problema della moltiplicazione delle matrici, speriamo che il nostro articolo possa ispirare altri nell’uso dell’intelligenza artificiale per guidare la scoperta algoritmica per altri compiti computazionali fondamentali. La loro 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. Basandosi sulla nostra ricerca, sperano di stimolare un lavoro più ampio, applicando l’intelligenza artificiale per aiutare la società a risolvere alcune delle sfide più importanti in matematica e in tutte le scienze.

Natura: scoperta di algoritmi di moltiplicazione di matrici più veloci con l'apprendimento per rinforzo

Astratto
Migliorare l’efficienza degli algoritmi per i calcoli fondamentali può avere un impatto diffuso, poiché può influenzare la velocità complessiva di una grande quantità di calcoli. La moltiplicazione delle matrici è uno di questi compiti primitivi, che si verifica in molti sistemi, dalle reti neurali alle routine di calcolo scientifico. La scoperta automatica di algoritmi che utilizzano l’apprendimento automatico offre la prospettiva di andare oltre l’intuizione umana e di sovraperformare gli attuali migliori algoritmi progettati dall’uomo. Tuttavia, automatizzare la procedura di scoperta degli algoritmi è complicato, poiché lo spazio dei possibili algoritmi è enorme. Qui riportiamo un approccio di apprendimento per rinforzo profondo basato su AlphaZero1 per scoprire algoritmi efficienti e dimostrabilmente corretti per la moltiplicazione di matrici arbitrarie. Il nostro agente, AlphaTensor, è addestrato a giocare a un gioco per giocatore singolo in cui l'obiettivo è trovare decomposizioni tensoriali all'interno di uno spazio a fattori finiti. AlphaTensor ha scoperto algoritmi che superano la complessità dello stato dell'arte per matrici di molte dimensioni. Particolarmente rilevante è il caso delle matrici 4 × 4 in un campo finito, dove l’algoritmo di AlphaTensor migliora per la prima volta, a nostra conoscenza, l’algoritmo a due livelli di Strassen dalla sua scoperta 50 anni fa2. Mostriamo ulteriormente la flessibilità di AlphaTensor attraverso diversi casi d'uso: algoritmi con complessità all'avanguardia per la moltiplicazione di matrici strutturate e migliore efficienza pratica ottimizzando la moltiplicazione di matrici per il runtime su hardware specifico. I nostri risultati evidenziano la capacità di AlphaTensor di accelerare il processo di scoperta algoritmica su una serie di problemi e di ottimizzare per diversi criteri.