DeepMind e il record della “moltiplicazione più veloce”

Internazionale (dietro paywall) racconta di come DeepMind abbia trovato un algoritmo per moltiplicare due matrici migliore di quelli umani: in realtà, se leggo bene l’abstract di questo articolo, due ricercatori si sono affrettati a postare un articolo dove hanno eguagliato quel record e leggermente migliorato il risultato di DeepMind rispetto a un altro record correlato. Forse è meglio però fare un passo indietro per capire di cosa si sta parlando.

matrice

struttura di una matrice [Wikipedia]

Molti tra gli algoritmi più costosi dal punto di vista computazionale richiedono di moltiplicare delle matrici molto grandi, che danno le approssimazioni dei valori di una funzione su una superficie. Se non lo sapete, le matrici sono pacchetti rettangolari o spesso quadrati di numeri: nel caso del prodotto di due matrici quadrate n×n si ottiene una nuova matrice n×n dove per ottenere l’elemento nella riga i e colonna j del prodotto bisogna prendere il primo, secondo, terzo… elemento della riga i della prima matrice, moltiplicarlo per il primo, secondo, terzo… elemento della colonna j della seconda matrice, e sommare tutti questi risultati. Come potete immaginare, un lavorone, soprattutto per matrici di migliaia di righe e colonne da moltiplicare in quantità esagerate.

I matematici si erano messi il cuore in pace, e pensavano che per moltiplicare due matrici n×n occorresse un numero di moltiplicazioni dell’ordine di n³; insomma se si voleva raddoppiare la dimensione delle matrici, cioè raddoppiare i punti sulla superficie per avere un’approssimazione migliore, occorrevano otto volte tante operazioni. Nel 1969 però il matematico tedesco Wolker Strassen se ne uscì con una notizia bomba. Prese due matrici 2×2 e fatto qualche trucchetto con i numeri, se accettavamo di eseguire un numero di addizioni molto maggiore sarebbero bastate sette moltiplicazioni anziché otto. In pratica l’algoritmo di Strassen sfrutta una struttura nascosta del prodotto; le addizioni servono per riciclare una delle moltiplicazioni in due punti diversi del prodotto delle matrici.

Negli anni seguenti ci fu un fiorire di nuovi algoritmi che per matrici molto grandi miglioravano il numero di operazioni necessarie; per un certo periodo anche il mio professore di metodi di approssimazione a Pisa detenne il record. Le sette moltiplicazioni per il prodotto di due matrici 2×2 resistono ancora, così come resisteva fino a poco fa il record di 49 moltiplicazioni per il prodotto di due matrici 4×4, ottenuto applicando ricorsivamente l’algoritmo di Strassen. Bene: DeepMind ha trovato un modo per moltiplicare due matrici (di numeri binari) 4×4 in 47 operazioni e uno per moltiplicare due matrici 5×5 in 96 operazioni anziché 98; e Kauers Moosbauer hanno trovato un modo equivalente per le 4×4 e uno con solo 95 operazioni per le 5×5. I due ricercatori hanno anche detto che ci stavano lavorando su da un po’ e si sono affrettati a pubblicare il preprint prima che qualcun altro li fregasse sul tempo :-)

In tutto questo, la cosa più inquietante, come già successo in passato per esempio con il Go, è il metodo usato da DeepMind per ottenere il suo risultato. Leggendo l’articolo di NewScientist, vediamo che il “programmatore” di DeepMind – o meglio chi ha messo su tutto il macchinario in questione – ha affermato che “essenzialmente non abbiamo idea di come mai il sistema è arrivato a questo risultato”. “In qualche modo le reti neurali hanno avuto un’intuizione di cosa sembrava buono e cosa sembrava cattivo, ma onestamente non posso spiegare esattamente come funziona”, ha continuato. Perlomeno i due ricercatori hanno spiegato qual è la loro linea di attacco (tendenzialmente fare modifiche più o meno a caso e vedendo se portavano a eliminare una moltiplicazione.

A differenza del go, in questo caso i risultati di DeepMind sono facilmente verificabili e quindi validi a tutti gli effetti. Certo però che questo è un duro colpo per la matematica: non perché un computer sia stato più bravo di noi, quanto perché contribuisce a distruggere la certezza che la matematica sia un modo “compatto” per processare le informazioni. Avete presente la dimostrazione del teorema dei quattro colori? Ecco, il concetto è quello. Sapere che ogni mappa sul piano è colorabile con solo quattro colori, ma che non c’è una vera ragione logica e bisogna per forza testare una caterva di esempi per verificare che tutti portino a una mappa a quattro colori, per noi esseri umani è una risposta a metà. Non ci basta il cosa, vogliamo anche il come.

7 comments

  1. “essenzialmente non abbiamo idea di come mai il sistema è arrivato a questo risultato”

    E’ un effetto indiretto delle GAN: sono strutture troppo complesse per essere studiate analiticamente. Ma ti dirò di più: nemmeno i metodi per costruire una GAN sono chiari, e sono lasciati a metodi tipo “funzionava lì”, “questo lo copincollo che migliora sempre”, “questo è un mix di reti fatte da persone diverse, ma se lo tolgo peggiora dell’1%”. Nel mio piccolo l’ho sperimentato pure io!

    Cmq, se la memoria non mi serve male, non è certo la prima volta che un metodo computazionale dimostra qualcosa in matematica: il duro colpo c’era stato anche molti anni fa. Forse questo è più evidente rispetto agli altri.

    • Come ho scritto, anche la dimostrazione del teorema dei quattro colori è essenzialmente computazionale. (Qualche anno fa hanno validato con Coq o simili il programma)

  2. Mah, io tutta questa ansia presso gli umani contemporanei di sapere come funzionano le cose non la vedo proprio. Del resto contrasta con l’idea che le cose complesse hanno ragioni semplici, che troppe spiegazioni sono complottismo, che le istruzioni si fanno con i disegnini, che le i/f devono essere semplificate, ecc. ecc.
    Quello che credo sia autenticamente umano è fare la mappa con 4 “diverse” gradazioni di verde scuro!

  3. Non sono un esperto, ma mi appassiona moltissimo vedere gli sviluppi (talvolta inattesi) delle reti neurali e in particolare i risultati ottenuti da DeepMind. Da giocatore di scacchi, mi aveva stupito moltissimo l’exploit di AlphaZero qualche anno fa. Adesso trova pure algoritmi nuovi!
    Nel passato moltissime scoperte scientifiche sono avvenute in maniera del tutto casuale: si cercava una cosa e, per caso, se ne scopriva un’altra. Le reti neurali hanno il vantaggio di poter andare a casaccio molto più velocemente di noi, per cui… siamo appena agli inizi… ne vedremo delle belle!

  4. Grazie, mau, molto interessante. Avevo presente Strassen, ma mi erano sfuggite queste novità.