La prima estensione di AlphaZero alla matematica apre nuove possibilità di ricerca
Gli algoritmi aiutano i matematici a eseguire operazioni fondamentali da migliaia di anni. 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, matematico persiano Muhammad ibn Musa al-Khwarizmi progettato nuovi algoritmi per risolvere equazioni lineari e quadratiche. Infatti, il nome di al-Khwarizmi, tradotto in latino come Algoritmiha 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.
Nel nostro cartapubblicato oggi su Nature, presentiamo Alpha Tensoreil primo sistema di intelligenza artificiale (AI) per scoprire 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.
Questo articolo è un trampolino di lancio nella missione di DeepMind di far progredire la scienza e risolvere i problemi più fondamentali utilizzando l’intelligenza artificiale. Il nostro sistema, AlphaTensor, si basa su AlphaZero, un agente che ha ha mostrato prestazioni sovrumane nei giochi da tavolo, come gli scacchi, il Go e lo shogie questo lavoro mostra il viaggio di AlphaZero dal gioco 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 fuori dall’aula, questa umile operazione matematica ha un’enorme influenza nel mondo digitale contemporaneo ed è onnipresente nell’informatica moderna.
Questa operazione viene utilizzata per elaborare immagini su smartphone, riconoscere comandi vocali, generare grafica per giochi per computer, eseguire simulazioni per prevedere il tempo, comprimere dati e video per condividerli su Internet e molto altro ancora. Le aziende di tutto il mondo investono grandi quantità di tempo e denaro nello sviluppo di hardware informatico per moltiplicare in modo efficiente le matrici. Pertanto, anche miglioramenti minori nell’efficienza della moltiplicazione delle matrici possono avere un impatto diffuso.
Per secoli, i matematici hanno creduto che l’algoritmo standard di moltiplicazione di matrici fosse il migliore che si potesse ottenere in termini di efficienza. Ma nel 1969, il matematico tedesco Volker Strassen sconvolse la comunità matematica dimostrando che esistono algoritmi migliori.
Studiando matrici molto piccole (dimensione 2×2), ha scoperto un modo ingegnoso di combinare le voci delle matrici per ottenere un algoritmo più veloce. Nonostante decenni di ricerca seguiti alla scoperta di Strassen, versioni più ampie di questo problema sono rimaste irrisolte, al punto che non si sa con quanta efficienza sia possibile moltiplicare due matrici piccole quanto 3×3.
Nel nostro articolo abbiamo esplorato come le moderne tecniche di intelligenza artificiale potrebbero far avanzare la scoperta automatica di nuovi algoritmi di moltiplicazione di matrici. Basandosi sul progresso dell’intuizione umana, AlphaTensor ha scoperto algoritmi più efficienti rispetto allo stato dell’arte per matrici di molte dimensioni. I nostri algoritmi progettati dall’intelligenza artificiale superano quelli progettati dall’uomo, il che rappresenta un importante passo avanti nel campo della scoperta algoritmica.
Il processo e il progresso dell’automazione della scoperta algoritmica
Innanzitutto, abbiamo 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 da decenniil numero di mosse possibili in ogni fase del nostro gioco è maggiore di 30 ordini di grandezza (oltre 1033 per una delle impostazioni che consideriamo).
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 significativamente 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 dei giochi tradizionali. problema.
Abbiamo 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 storici algoritmi 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.
Ad esempio, se l’algoritmo tradizionale insegnato a scuola moltiplica una matrice 4×5 per 5×5 utilizzando 100 moltiplicazioni, e questo numero è stato ridotto a 80 con l’ingegno umano, AlphaTensor ha trovato algoritmi che eseguono la stessa operazione utilizzando solo 76 moltiplicazioni.
Al di là di questo esempio, l’algoritmo di AlphaTensor migliora per la prima volta l’algoritmo a due livelli di Strassen in un campo finito dalla sua scoperta 50 anni fa. Questi algoritmi per moltiplicare matrici piccole possono essere utilizzati come primitivi per moltiplicare matrici molto più grandi di dimensione arbitraria.
Inoltre, AlphaTensor scopre anche un insieme diversificato di algoritmi con complessità all’avanguardia – fino a migliaia di algoritmi di moltiplicazione di matrici per ciascuna dimensione, dimostrando che lo spazio degli algoritmi di moltiplicazione di matrici è più ricco di quanto si pensasse in precedenza.
Gli algoritmi in questo ricco spazio hanno diverse proprietà matematiche e pratiche. Sfruttando questa diversità, abbiamo adattato AlphaTensor per trovare specificamente algoritmi veloci su un determinato hardware, come GPU Nvidia V100 e Google TPU v2. Questi algoritmi moltiplicano matrici di grandi dimensioni il 10-20% più velocemente rispetto agli algoritmi comunemente utilizzati sullo stesso hardware, il che dimostra la flessibilità di AlphaTensor nell’ottimizzazione di obiettivi arbitrari.
Esplorare l’impatto sulla ricerca e sulle applicazioni future
Da un punto di vista matematico, i nostri 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 modo più efficace rispetto agli approcci precedenti, AlphaTensor aiuta a far avanzare 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 dell’informatica.
Poiché la moltiplicazione delle matrici è una componente fondamentale in molte attività computazionali, che spaziano 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 ottimizzino parametri come l’utilizzo di energia e la stabilità numerica, aiutando a prevenire che piccoli errori di arrotondamento si diffondano durante il funzionamento dell’algoritmo.
Anche se qui ci siamo 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 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. Basandosi sulla nostra ricerca, speriamo 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.
Puoi trovare maggiori informazioni in Repository GitHub di AlphaTensor.
