L'intelligenza artificiale rivela nuove possibilità nella moltiplicazione di matrici

I matematici amano un buon puzzle. Anche qualcosa di così astratto come la moltiplicazione delle matrici (tabelle di numeri bidimensionali) può sembrare un gioco quando cerchi di trovare il modo più efficiente per farlo. È un po' come cercare di risolvere un cubo di Rubik nel minor numero di mosse possibile: impegnativo, ma affascinante. Tranne che per un cubo di Rubik, il numero di mosse possibili ad ogni passo è 18; per la moltiplicazione di matrici, anche in casi relativamente semplici, ogni passaggio può presentare più di 10¹² opzioni.

Negli ultimi 50 anni, i ricercatori hanno affrontato questo problema in molti modi, tutti basati su ricerche al computer aiutate dall'intuizione umana. Il mese scorso, un team della società di intelligenza artificiale DeepMind ha mostrato come affrontare il problema da una nuova direzione, riportando in a carta in Natura che avevano addestrato con successo una rete neurale per scoprire nuovi algoritmi veloci per la moltiplicazione di matrici. Era come se l'intelligenza artificiale avesse trovato una strategia sconosciuta per risolvere un cubo di Rubik mostruosamente complesso.

"E 'un risultato molto pulito", ha detto Josh Alman, informatico alla Columbia University. Ma lui e altri specialisti della moltiplicazione di matrici hanno anche sottolineato che tale assistenza AI integrerà piuttosto che sostituire i metodi esistenti, almeno a breve termine. "È come una prova di concetto per qualcosa che potrebbe diventare una svolta", ha detto Alman. Il risultato aiuterà semplicemente i ricercatori nella loro ricerca.

Come per dimostrare il punto, tre giorni dopo il Natura è uscito un articolo, una coppia di ricercatori austriaci ha illustrato come i metodi vecchi e nuovi potrebbero completarsi a vicenda. Hanno usato una ricerca convenzionale assistita da computer per migliorare ulteriormente uno degli algoritmi che la rete neurale aveva scoperto.

I risultati suggeriscono che, come il processo di risoluzione di un cubo di Rubik, il percorso verso algoritmi migliori sarà pieno di colpi di scena.

Moltiplicare Matrici

La moltiplicazione di matrici è una delle operazioni più fondamentali e onnipresenti in tutta la matematica. Per moltiplicare una coppia di n-By-n matrici, ciascuna con n² elementi, moltiplichi e aggiungi questi elementi insieme in combinazioni particolari per generare il prodotto, un terzo n-By-n matrice. La ricetta standard per moltiplicare due n-By-n matrici richiede n³ operazioni di moltiplicazione, quindi una matrice 2 per 2, ad esempio, richiede otto moltiplicazioni.

Per matrici più grandi, con migliaia di righe e colonne, questo processo diventa rapidamente macchinoso. Ma nel 1969, il matematico Volker Strassen scoperto una procedura per moltiplicare una coppia di matrici 2 per 2 utilizzando sette passaggi di moltiplicazione anziché otto, a costo di introdurre più passaggi di addizione.

L'algoritmo di Strassen è inutilmente contorto se vuoi solo moltiplicare una coppia di matrici 2 per 2. Ma si rese conto che avrebbe funzionato anche per matrici più grandi. Questo perché gli elementi di una matrice possono essere essi stessi matrici. Ad esempio, una matrice con 20,000 righe e 20,000 colonne può essere reinventata come una matrice 2 per 2 i cui quattro elementi sono ciascuno 10,000 per 10,000 matrici. Ciascuna di queste matrici può quindi essere suddivisa in quattro blocchi da 5,000 per 5,000 e così via. Strassen potrebbe applicare il suo metodo per moltiplicare le matrici 2 per 2 a ciascun livello di questa gerarchia nidificata. All'aumentare della dimensione della matrice, aumentano i risparmi derivanti da un minor numero di moltiplicazioni.

La scoperta di Strassen ha portato alla ricerca di algoritmi efficienti per la moltiplicazione di matrici, che da allora ha ispirato due distinti sottocampi. Uno si concentra su una questione di principio: se immagini di moltiplicare per due n-By-n matrici e let n correre verso l'infinito, come scala il numero di passaggi di moltiplicazione nell'algoritmo più veloce possibile n? Il record corrente per il miglior ridimensionamento, n^2.3728596, appartiene ad Alman e Virginia Vassilievska Williams, un informatico del Massachusetts Institute of Technology. (Un recente inedito preprint riportato un minuscolo miglioramento utilizzando una nuova tecnica.) Ma questi algoritmi sono di interesse puramente teorico, vincendo su metodi come quello di Strassen solo per matrici assurdamente grandi.

Il secondo sottocampo pensa su scala ridotta. Subito dopo il lavoro di Strassen, lo scienziato informatico israeliano americano Shmuel Winograd ha mostrato che Strassen aveva raggiunto un limite teorico: non è possibile moltiplicare matrici 2 per 2 con meno di sette passaggi di moltiplicazione. Ma per tutte le altre dimensioni di matrice, il numero minimo di moltiplicazioni richieste rimane una questione aperta. E algoritmi veloci per matrici piccole potrebbero avere un impatto enorme, poiché ripetute iterazioni di un tale algoritmo potrebbero battere l'algoritmo di Strassen quando vengono moltiplicate matrici di dimensioni ragionevoli.

Sfortunatamente, l'enorme numero di possibilità è enorme. Anche per le matrici 3 per 3, "il numero di possibili algoritmi supera il numero di atomi nell'universo", ha affermato Alhussein Fawzi, un ricercatore di DeepMind e uno dei leader del nuovo lavoro.

Di fronte a questo vertiginoso menu di opzioni, i ricercatori hanno fatto progressi trasformando la moltiplicazione di matrici in quello che sembra un problema matematico completamente diverso, più facile da gestire per i computer. È possibile rappresentare il compito astratto di moltiplicare due matrici come un tipo specifico di oggetto matematico: un array tridimensionale di numeri chiamato tensore. I ricercatori possono quindi scomporre questo tensore in una somma di componenti elementari, chiamati tensori di "rango 1"; ognuno di questi rappresenterà un passo diverso nel corrispondente algoritmo di moltiplicazione di matrici. Ciò significa che trovare un algoritmo di moltiplicazione efficiente equivale a minimizzare il numero di termini in una decomposizione tensoriale: minori sono i termini, minori sono i passaggi coinvolti.

In questo modo, i ricercatori hanno scoperto nuovi Algoritmi che si moltiplicano n-By-n matrici che utilizzano meno dello standard n³ passi di moltiplicazione per molte dimensioni di matrici piccole. Ma gli algoritmi che superano non solo lo standard ma anche l'algoritmo di Strassen per matrici piccole sono rimasti fuori portata, fino ad ora.

Game On

Il team di DeepMind ha affrontato il problema trasformando la decomposizione tensoriale in un gioco per giocatore singolo. Hanno iniziato con un algoritmo di deep learning discendente da AlphaGo, un'altra intelligenza artificiale di DeepMind che nel 2016 imparato a giocare al gioco da tavolo Go abbastanza bene da battere i migliori giocatori umani.

Tutti gli algoritmi di deep learning sono costruiti attorno a reti neurali: reti di neuroni artificiali ordinati in strati, con connessioni che possono variare in forza che rappresentano quanto ogni neurone influenza quelli nello strato successivo. La forza di queste connessioni viene ottimizzata in molte iterazioni di una procedura di addestramento, durante la quale la rete neurale impara a trasformare ogni input che riceve in un output che aiuta l'algoritmo a raggiungere il suo obiettivo generale.

Nel nuovo algoritmo di DeepMind, denominato AlphaTensor, gli input rappresentano i passaggi lungo il percorso verso uno schema di moltiplicazione di matrici valido. Il primo input alla rete neurale è il tensore di moltiplicazione della matrice originale e il suo output è il tensore di rango 1 che AlphaTensor ha scelto per la sua prima mossa. L'algoritmo sottrae questo tensore di rango 1 dall'input iniziale, producendo un tensore aggiornato che viene reimmesso nella rete come nuovo input. Il processo si ripete finché alla fine ogni elemento nel tensore iniziale non è stato ridotto a zero, il che significa che non ci sono più tensori di rango 1 da eliminare.

A quel punto, la rete neurale ha scoperto una decomposizione tensoriale valida, poiché è matematicamente garantito che la somma di tutti i tensori di rango 1 sia esattamente uguale al tensore iniziale. E i passaggi necessari per arrivarci possono essere tradotti in passaggi del corrispondente algoritmo di moltiplicazione di matrici.

Ecco il gioco: AlphaTensor decompone ripetutamente un tensore in un insieme di componenti di rango 1. Ogni volta, AlphaTensor viene ricompensato se trova un modo per ridurre il numero di passaggi. Ma le scorciatoie per la vittoria non sono affatto intuitive, proprio come a volte devi rimescolare una faccia perfettamente ordinata su un cubo di Rubik prima di poter risolvere l'intera faccenda.

Il team ora disponeva di un algoritmo che, in teoria, poteva risolvere il problema. Dovevano solo addestrarlo prima.

Nuovi percorsi

Come tutte le reti neurali, AlphaTensor ha bisogno di molti dati su cui allenarsi, ma la decomposizione del tensore è un problema notoriamente difficile. C'erano pochi esempi di decomposizioni efficienti che i ricercatori potevano alimentare la rete. Invece, hanno aiutato l'algoritmo a iniziare addestrandolo sul problema inverso molto più semplice: sommando un gruppo di tensori di rango 1 generati casualmente.

"Stanno usando il problema facile per produrre più dati per il problema difficile", ha detto Michael Littmann, un informatico della Brown University. La combinazione di questa procedura di addestramento all'indietro con l'apprendimento per rinforzo, in cui AlphaTensor ha generato i propri dati di addestramento mentre si aggirava alla ricerca di scomposizioni efficienti, ha funzionato molto meglio di entrambi i metodi di addestramento da soli.

Il team di DeepMind ha addestrato AlphaTensor a scomporre tensori che rappresentano la moltiplicazione di matrici fino a 12 per 12. Ha cercato algoritmi veloci per moltiplicare matrici di numeri reali ordinari e anche algoritmi specifici per un'impostazione più vincolata nota come aritmetica modulo 2. (Questa è matematica basata solo su due numeri, quindi gli elementi della matrice possono essere solo 0 o 1 e 1 + 1 = 0.) I ricercatori spesso iniziano con questo spazio più ristretto ma ancora vasto, nella speranza che gli algoritmi scoperti qui possano essere adattati a lavorare su matrici di numeri reali.

Dopo l'allenamento, AlphaTensor ha riscoperto l'algoritmo di Strassen in pochi minuti. Ha quindi scoperto fino a migliaia di nuovi algoritmi veloci per ogni dimensione di matrice. Questi erano diversi dagli algoritmi più noti ma avevano lo stesso numero di passaggi di moltiplicazione.

In alcuni casi, AlphaTensor ha persino battuto record esistenti. Le sue scoperte più sorprendenti sono avvenute nell'aritmetica modulo 2, dove ha trovato un nuovo algoritmo per moltiplicare matrici 4 per 4 in 47 passaggi di moltiplicazione, un miglioramento rispetto ai 49 passaggi richiesti per due iterazioni dell'algoritmo di Strassen. Ha anche battuto il più noto algoritmo per matrici 5 per 5 modulo 2, riducendo il numero di moltiplicazioni richieste dal record precedente di 98 a 96. (Ma questo nuovo record è ancora in ritardo rispetto ai 91 passaggi che sarebbero necessari per battere Algoritmo di Strassen utilizzando matrici 5 per 5.)

Il nuovo risultato di alto profilo ha creato molta eccitazione, con alcuni ricercatori accumulando elogi per il miglioramento basato sull'intelligenza artificiale sullo status quo. Ma non tutti nella comunità della moltiplicazione di matrici sono rimasti così colpiti. "Mi sembrava che fosse un po' sopravvalutato", ha detto Vassilevska Williams. “È un altro strumento. Non è come, 'Oh, i computer hanno battuto gli umani', sai?"

I ricercatori hanno anche sottolineato che le applicazioni immediate dell'algoritmo 4 per 4 da record sarebbero limitate: non solo è valido solo nell'aritmetica modulo 2, ma nella vita reale ci sono considerazioni importanti oltre alla velocità.

Fawzi ha convenuto che in realtà questo è solo l'inizio. "C'è molto spazio per il miglioramento e la ricerca, e questa è una buona cosa", ha detto.

Una svolta finale

La più grande forza di AlphaTensor rispetto ai metodi di ricerca computerizzati consolidati è anche la sua più grande debolezza: non è vincolata dall'intuizione umana su come siano i buoni algoritmi, quindi non può spiegare le sue scelte. Ciò rende difficile per i ricercatori imparare dai suoi risultati.

Ma questo potrebbe non essere uno svantaggio così grande come sembra. Pochi giorni dopo il risultato di AlphaTensor, il matematico Manuel Kauers e il suo studente laureato Jakob Moosbauer, entrambi della Johannes Kepler University Linz in Austria, hanno riportato un altro passo avanti.

Quando è uscito il documento di DeepMind, Kauers e Moosbauer stavano cercando nuovi algoritmi di moltiplicazione utilizzando una ricerca assistita da computer convenzionale. Ma a differenza della maggior parte di tali ricerche, che ricominciano da capo con un nuovo principio guida, il loro metodo funziona modificando ripetutamente un algoritmo esistente nella speranza di spremere maggiori risparmi sulla moltiplicazione. Prendendo come punto di partenza l'algoritmo di AlphaTensor per matrici 5 per 5 modulo 2, sono rimasti sorpresi nello scoprire che il loro metodo ha ridotto il numero di passaggi di moltiplicazione da 96 a 95 dopo solo pochi secondi di calcolo.

AlphaTensor li ha anche aiutati indirettamente a fare un altro miglioramento. In precedenza, Kauers e Moosbauer non si erano preoccupati di esplorare lo spazio delle matrici 4 per 4, ritenendo che non sarebbe stato possibile battere due iterazioni dell'algoritmo di Strassen. Il risultato di AlphaTensor li ha spinti a riconsiderare e, dopo una settimana di tempo di calcolo a partire da zero, il loro metodo ha rivelato un altro algoritmo a 47 passaggi non correlato a quello scoperto da AlphaTensor. "Se qualcuno ci avesse detto che c'è qualcosa da scoprire per 4-by-4, avremmo potuto farlo prima", ha detto Kauers. "Ma OK, beh, è ​​così che funziona."

Littman si aspetta altre sorprese del genere, paragonando la situazione alla prima volta che un corridore ha terminato un miglio in meno di quattro minuti, un'impresa che era stata ampiamente considerata impossibile. "La gente diceva, 'Oh, aspetta, possiamo farlo', e ora molte persone possono farlo", ha detto.

Guardando al futuro, Fawzi spera di generalizzare AlphaTensor per affrontare una gamma più ampia di attività matematiche e computazionali, proprio come il suo antenato AlphaGo alla fine si è esteso ad altri giochi.

Kauers vede questo come la vera cartina di tornasole per l'applicazione dell'apprendimento automatico alla scoperta di nuovi algoritmi. Sottolinea che la ricerca di algoritmi di moltiplicazione di matrici veloci è un problema combinatorio per il quale le ricerche al computer, con o senza assistenza umana, sono adatte. Ma non tutti i problemi matematici sono così facili da definire. Se l'apprendimento automatico può scoprire un'idea algoritmica qualitativamente nuova, ha detto, "questo sarebbe quindi un punto di svolta".