Computing with traceable tensor networks

Immagina di cercare di risolvere un puzzle dove, ogni volta che aggiungi un nuovo pezzo, il numero di modi possibili per organizzarlo esplode. Questo è l'incubo dei problemi ad "alta dimensionalità" nella scienza e nell'ingegneria. Che tu stia modellando come il calore si diffonde attraverso un materiale complesso, prevedendo il movimento delle particelle in un fluido o simulando il comportamento di un sistema quantistico, la matematica diventa rapidamente complicata. Se un problema ha solo poche variabili, puoi risolverlo su un laptop. Ma se ha dieci, venti o cento variabili, la quantità di dati che devi memorizzare cresce in modo così enorme che anche i più grandi supercomputer del mondo finirebbero per esaurire la memoria prima di aver completato il primo passaggio. È come cercare di mappare ogni possibile percorso in una città che continua ad aggiungere nuove strade più velocemente di quanto tu riesca a disegnarle.

Per affrontare questo, gli scienziati usano un trucco astuto chiamato "reti tensoriali". Pensa a un tensore come a un gigantesco foglio di calcolo multidimensionale. Invece di cercare di memorizzare l'intero foglio di calcolo, il che è impossibile, questi metodi lo scompongono in frammenti più piccoli e interconnessi, come una squadra di lavoratori che si scambiano appunti tra loro. Le squadre più popolari finora sono state organizzate in una linea retta (chiamata "Tensor Train") o in una forma ad albero (chiamata "Hierarchical Tucker"). Queste squadre sono bravissime a mantenere i dati piccoli, ma sono rigide. Possono lavorare solo in quelle specifiche forme. Se il problema che stai cercando di risolvere si adatta naturalmente a una forma diversa — come un cerchio, un anello o una rete complessa — forzarlo in una linea retta o in un albero è come cercare di inserire un perno cilindrico in un foro quadrato. Funziona, ma spreca molto spazio ed energia.

È qui che entra in gioco un nuovo studio di Sarah Ellwein e Daniele Venturi dell'Università della California, Santa Cruz. Hanno inventato un modo per lasciare che queste squadre di dati lavorino in qualsiasi forma, inclusi anelli e reti complesse, senza perdere la loro efficienza. Chiamano il loro metodo "Graph Tensor Networks" (GTN). Nel loro articolo, dimostrano che permettendo ai dati di fluire in un modello più naturale e circolare, possono risolvere difficili problemi matematici con molte meno risorse rispetto ai vecchi metodi. Hanno testato questo su alcune equazioni molto complicate, tra cui una che descrive come le particelle si muovono e si diffondono (l'equazione di Fokker–Planck), e hanno scoperto che il loro nuovo approccio a "grafo" era spesso molto più veloce e utilizzava significativamente meno memoria rispetto agli approcci tradizionali a linea retta o ad albero, mantenendo al contempo le risposte altrettanto accurate.

La storia del puzzle mutaforma

Immagina di cercare di descrivere una scultura 3D massiccia e intricata fatta di milioni di piccoli mattoncini Lego. Se provassi a elencare la posizione di ogni singolo mattoncino, l'elenco sarebbe più lungo di tutto internet. Questo è il problema dei dati ad alta dimensionalità. Per risolvere la cosa, gli scienziati usano una strategia "low-rank": invece di elencare ogni singolo mattoncino, descrivono la scultura come un insieme di blocchi più piccoli e semplici che si incastrano tra loro.

Per molto tempo, l'unico modo per incastrare questi blocchi è stato in una linea retta (come un treno) o in un albero ramificato. Queste forme sono facili da gestire, ma non sono sempre la scelta migliore. A volte, i dati vogliono formare un cerchio o una rete complessa. Forzare un problema circolare in una linea retta è come cercare di camminare in cerchio tenendo un lungo palo dritto; finisci per fare passi enormi ed inefficienti.

Ellwein e Venturi si sono posti una domanda semplice: E se potessimo far incastrare i blocchi in qualsiasi forma vogliamo, purché abbiamo una mappa di come si connettono?

Hanno sviluppato un nuovo algoritmo chiamato GTN-SVD. Pensate a questo come a un traduttore universale che può prendere un blocco di dati gigante e disordinato e scomporlo in una rete di pezzi più piccoli disposti in una forma da voi scelta — che sia una linea, un anello, una stella o un bizzarro e traballante ammasso. La chiave è una "matrice di adiacenza del rango", che è solo un modo sofisticato per disegnare una mappa di quali pezzi sono connessi a quali. Se due pezzi non sono connessi, la mappa dice "nessun collegamento" e l'algoritmo sa di dover ignorare quella connessione, risparmiando spazio.

Ma scomporre i dati è solo metà della battaglia. Per risolvere un problema che cambia nel tempo (come un fluido che scorre), bisogna continuare ad aggiungere nuove informazioni e poi "pulire" il disordine per mantenere i dati piccoli. È qui che l'articolo diventa davvero astuto.

Nei vecchi metodi a "linea retta", aggiungere nuove informazioni era facile: bastava aggiungere i nuovi blocchi accanto ai vecchi. Ma in una rete circolare o a rete, aggiungere nuovi blocchi può causare grovigli e rendere le connessioni enormi, facendo esplodere nuovamente l'intero sistema in termini di dimensioni. Gli autori si sono resi conto che se la rete possiede un "percorso tracciabile" — un percorso che visita ogni singolo blocco esattamente una volta senza incastrarsi in un ciclo — potevano trattare la rete come un treno solo ai fini della pulizia.

Hanno inventato una nuova procedura di "arrotondamento" (rounding). Immaginate di avere una rete disordinata di corde. Se tirate le corde in un ordine specifico (seguendo quel percorso tracciabile), potete stringere i nodi e tagliare le estremità libere senza rompere la rete. Il loro metodo fa esattamente questo: setaccia la rete, stringendo le connessioni e tagliando i dati non necessari, mantenendo la dimensione piccola e l'accuratezza elevata.

I risultati: Più intelligenti, più veloci e più snelli

Per vedere se la loro idea funzionasse davvero, gli autori hanno eseguito alcuni test. Non hanno solo tirato a indovinare; hanno simulato scenari del mondo reale.

Per prima cosa, hanno cercato di approssimare alcune funzioni matematiche molto complesse e irregolari. Hanno confrontato la loro nuova forma "Barbell" (un grafo che sembra due anelli collegati da un ponte) contro i vecchi metodi a linea retta e ad albero. I risultati sono stati sorprendenti. Per ottenere lo stesso livello di accuratezza, il nuovo metodo a grafo aveva bisogno di 382 volte meno "gradi di libertà" (che è solo un modo elegante per dire "pezzi di dati") rispetto al metodo a linea retta a un certo livello di precisione, e 498 volte meno a un livello di precisione superiore. In parole povere: il nuovo metodo era centinaia di volte più efficiente nello memorizzare la stessa quantità di informazioni.

In seguito, hanno affrontato un famoso problema di fisica: l'equazione di Fokker–Planck. Questa equazione descrive come una nuvola di particelle si muove e si diffonde nel tempo, come l'inchiostro che cade nell'acqua. Hanno simulato questo processo in uno spazio a 4 dimensioni (che è difficile da visualizzare, ma pensatelo come una versione iper-complessa di una stanza).

Hanno eseguito la simulazione per un lungo periodo, passo dopo passo.

• Nello scenario "senza vento" (dove le particelle si diffondono casualmente), il nuovo metodo a grafo ha utilizzato 166 volte meno memoria rispetto al metodo a linea retta all'inizio. Mentre la simulazione procedeva, il metodo a grafo rimaneva efficiente, mentre il vecchio metodo faticava. Il metodo a grafo ha completato l'intera simulazione in 1.460 secondi, mentre il metodo a linea retta ne ha impiegati 2.737. È quasi il doppio della velocità.
• Nello scenario "ventoso" (dove le particelle sono spinte da un flusso complesso), il metodo a grafo ha comunque utilizzato più di 10 volte meno memoria rispetto al metodo a linea retta. La differenza di tempo è stata ancora maggiore: il metodo a grafo ha impiegato circa 1,16 secondi per passaggio, mentre il metodo a linea retta ne ha impiegati 13,6.

Gli autori hanno sottolineato con cura che il loro metodo non è una bacchetta magica che risolve tutto perfettamente. Nello scenario "ventoso", il metodo a linea retta era leggermente più accurato alla fine, sebbene fosse molto più lento e utilizzasse molta più memoria. Gli autori suggeriscono che per alcuni problemi i vecchi metodi potrebbero essere ancora migliori, ma per molti altri, il nuovo approccio a grafo è una grande vittoria.

Perché questo è importante

Il punto fondamentale è che non dobbiamo più forzare i nostri dati in una linea retta. Lasciando che i dati fluiscano in forme che corrispondono al problema — come anelli o reti — possiamo risolvere enigmi ad alta dimensionalità che prima erano troppo costosi o troppo lenti da gestire.

Gli autori dimostrano che, utilizzando queste forme di grafi flessibili, possiamo ottenere risposte altrettanto buone di quelle dei vecchi metodi, ma con una frazione della potenza di calcolo del computer. È come rendersi conto che non è necessario costruire una strada lunga e tortuosa per andare dal punto A al punto B; a volte, un ponte diretto o un percorso circolare è molto più veloce e utilizza meno asfalto. Questo apre la porta alla simulazione di sistemi più complessi in fisica, chimica e ingegneria, aiutandoci potenzialmente a comprendere tutto, dal modo in cui i farmaci si muovono nel corpo a come nascono le stelle, senza aver bisogno di un supercomputer grande quanto una città.