Dicembre 4, 2022

NbaRevolution

Covid crisi politica in Italia

Il raddoppio della matrice sta guadagnando velocità con l’IA

Dove si fermerà DeepMind, una sussidiaria di Google con sede a Londra specializzata in intelligenza artificiale? Nel 2016, il loro programma AlphaGo ha sconfitto Lee Sedol, uno dei migliori giocatori di Go al mondo. Nel 2020, AlphaFold ha affrontato con successo una sfida nota ai genetisti, determinando la struttura 3D di una proteina dalla sua sequenza di amminoacidi. Il team di DeepMind ha recentemente affrontato un problema matematico: la moltiplicazione di matrici. Ho scoperto algoritmi più efficienti di quelli noti, alcuni dei quali non vengono superati da cinquant’anni. Questo tipo di moltiplicazione si trova in un’ampia gamma di applicazioni e questi risultati saranno sicuramente utilizzati per migliorare molti programmi per computer.

Le matrici sono una generalizzazione del concetto di numero. Questi oggetti sono un tipo di matrice le cui righe e colonne sono riempite con numeri. Come con i numeri tradizionali, è possibile aggiungere, sottrarre o anche moltiplicare due matrici. Tuttavia, le regole di moltiplicazione sono un po’ più complicate. Per moltiplicare la matrice A per la matrice B, è necessario combinare i termini delle righe di A con quelli delle colonne di B. Ogni voce della matrice C, risultato della moltiplicazione, è la somma del prodotto dei termini A e B.

Poiché le moltiplicazioni richiedono più risorse di calcolo rispetto alle addizioni, le prestazioni dell’algoritmo vengono stimate in base al numero di moltiplicazioni necessarie. Per un prodotto di matrici quadrate bidimensionali Non (insieme a Non linee e Non colonne), la definizione standard di questo processo porta a un totale Non3 battere. quando Non Il numero di operazioni aumenta molto rapidamente. Possiamo fare di meglio?

READ  La commissione elettorale incontra il ministro federale della sanità prima del voto UP, sollevando preoccupazione per Omicron

Nel 1969, il matematico Volker Strassen ha mostrato che è possibile moltiplicare matrici bidimensionali con solo sette invece di otto seguendo direttamente la definizione. Per questo, ha abilmente combinato i termini delle matrici iniziali. Pertanto, la definizione standard di moltiplicazione non è un algoritmo perfetto. Questa scoperta ha portato i matematici a cercare algoritmi più efficienti per il prodotto di matrici quadrate (e anche non quadrate).

Per rivelare un tale algoritmo, l’approccio utilizzato dai ricercatori di DeepMind consiste nel costruire un tensore tridimensionale che rappresenta il processo di moltiplicazione di matrici con determinate dimensioni, quindi selezionare e sottrarre insiemi di termini per queste matrici. al tenditore. Il processo viene ripetuto fino a quando il tensore non viene annullato (tutte le sue condizioni saranno zero). Questa procedura introduce quindi un algoritmo per moltiplicare nel tensore qualsiasi matrice di dimensioni scelte.

La difficoltà sta nella selezione dei gruppi di termini. Il numero di possibilità è enorme (supera di parecchi ordini di grandezza il numero di azioni possibili negli scacchi o nel go). Quindi è impossibile testare tutte le possibilità. I matematici facevano affidamento sulla loro intuizione e sui test back-to-back. Ma questo approccio diventa rapidamente limitato.

Per aggirare queste limitazioni, Al-Hussein Fawzi e colleghi di DeepMind si sono affidati a un algoritmo di deep learning che utilizza una rete neurale per scegliere i costrutti che sembrano più efficienti. Per questo, i ricercatori hanno adattato AlphaGo a questo problema e lo hanno chiamato AlphaTensor. Quest’ultimo contiene un albero decisionale, cioè una struttura che deve scegliere combinazioni di termini tra tutte le possibilità. La rete neurale cerca quindi di determinare quale ramo dell’albero avrà più senso. In base al risultato ottenuto, l’algoritmo regola i parametri della rete neurale per migliorarne la selezione.

READ  Virus delle notizie false (9/9) | Italia post-Berlusconi: non dire addio alla verità

Il risultato è stato sorprendente. Molto rapidamente, AlphaTensor ha trovato tutti gli algoritmi precedentemente identificati dagli esseri umani. Ma in alcuni casi si è rivelato più efficace! Ad esempio, per moltiplicare due matrici 4×4, l’algoritmo di Strassen, risalente al 1969, richiedeva 49 moltiplicazioni. AlphaTensor ha ottenuto solo 47 risultati (nel caso di campi finiti Z2). Per il prodotto di una matrice 4×5 con una matrice 5×5, il numero minimo di multipli è stato aumentato da 80 a 76.

Il team ha controllato tutti i prodotti delle matrici fino a dimensioni 5 x 5. Hanno anche esplorato matrici più grandi scomponendole in elementi più piccoli. Utilizzando il loro metodo, i ricercatori hanno ridotto, ad esempio, il numero dei multipli da 1022 a 990 nel caso del prodotto delle matrici 11 × 12 e 12 × 12.

Un altro modo per affrontare il problema dell’ottimizzazione, il team ha anche chiesto ad AlphaTensor di trovare un algoritmo che riduca i tempi di calcolo su processori specifici. In alcuni casi, le prestazioni sono migliorate del 10-20%.

Molte applicazioni trarranno vantaggio da queste nuove scoperte. AlphaTensor apre anche la strada all’utilizzo dell’intelligenza artificiale per migliorare altri tipi di algoritmi. Ma anche nel caso degli array, la domanda rimane: le soluzioni trovate da AlphaTensor sono le più efficienti o no?

Il raddoppio della matrice sta guadagnando velocità con l'IA