DeepMind sta sviluppando un algoritmo per domarli tutti
Gli algoritmi classici sono ciò che ha permesso al software di mangiare il mondo, ma i dati con cui lavorano non sempre riflettono il mondo reale. Il deep learning è ciò che alimenta alcune delle applicazioni AI più iconiche di oggi, ma i modelli di deep learning necessitano di una riqualificazione per essere applicati in domini per cui non sono stati originariamente progettati.
DeepMind sta cercando di combinare il deep learning e gli algoritmi, creando l’unico algoritmo per controllarli tutti: un modello di deep learning che può imparare a emulare qualsiasi algoritmo, generando un modello equivalente all’algoritmo che può funzionare con i dati del mondo reale.
DeepMind ha fatto notizia per alcune imprese iconiche nell’intelligenza artificiale. Dopo aver sviluppato AlphaGo , un programma che è diventato il campione del mondo al gioco del Go in una partita di cinque partite dopo aver battuto un giocatore professionista di Go umano, e AlphaFold , una soluzione a una grande sfida in biologia di 50 anni, DeepMind ha impostato punta su un’altra grande sfida: collegare il deep learning, una tecnica di intelligenza artificiale, con l’informatica classica.
La nascita del ragionamento algoritmico neurale
Charles Blundell e Petar Veličković ricoprono entrambi posizioni di ricerca senior presso DeepMind. Condividono un background nell’informatica classica e la passione per l’innovazione applicata. Quando Veličković ha incontrato Blundell al DeepMind, è nata una linea di ricerca nota come Neural Algorithmic Reasoning (NAR), dopo l’omonimo position paper recentemente pubblicato dal duo.
La tesi chiave è che gli algoritmi possiedono qualità fondamentalmente diverse rispetto ai metodi di deep learning, qualcosa su cui Blundell e Veličković hanno elaborato nella loro introduzione di NAR. Ciò suggerisce che se i metodi di deep learning fossero in grado di imitare meglio gli algoritmi, la generalizzazione del tipo visto con gli algoritmi diventerebbe possibile con il deep learning.
Come tutte le ricerche ben fondate, NAR ha un pedigree che risale alle radici dei campi che tocca e si ramifica in collaborazioni con altri ricercatori. A differenza di molte ricerche fantasiose, NAR ha alcuni primi risultati e applicazioni da mostrare.
Di recente ci siamo seduti per discutere i primi principi e fondamenti di NAR con Veličković e Blundell, a cui si è unito anche il ricercatore MILA Andreea Deac , che ha ampliato le specifiche, le applicazioni e le direzioni future. Le aree di interesse includono l’elaborazione di dati a forma di grafico e il pathfinding.
Pathfinding: c’è un algoritmo per questo
Deac è stato internato presso DeepMind e si è interessato all’apprendimento della rappresentazione grafica attraverso la lente della scoperta di farmaci. L’apprendimento della rappresentazione grafica è un’area in cui Veličković è uno dei maggiori esperti e ritiene che sia un ottimo strumento per l’elaborazione di dati a forma di grafico.
“Se strizzi gli occhi abbastanza forte, qualsiasi tipo di dato può essere inserito in una rappresentazione grafica. Le immagini possono essere viste come grafici di pixel collegati dalla vicinanza. Il testo può essere visto come una sequenza di oggetti collegati tra loro. Più in generale, le cose che provengono veramente dalla natura che non sono progettate per adattarsi all’interno di un fotogramma o all’interno di una sequenza come farebbero gli umani, sono in realtà rappresentate in modo abbastanza naturale come strutture grafiche”, ha affermato Veličković.
Un altro problema del mondo reale che si presta bene ai grafici – e uno standard per DeepMind , che, come Google, fa parte di Alphabet – è il pathfinding. Nel 2020, Google Maps è stata la mappa e l’app di navigazione più scaricate negli Stati Uniti ed è utilizzata da milioni di persone ogni giorno. Una delle sue caratteristiche killer, il pathfinding, è alimentata nientemeno che da DeepMind.
La popolare app ora mostra un approccio che potrebbe rivoluzionare l’intelligenza artificiale e il software come li conosce il mondo. Google Maps, dispone di una rete stradale del mondo reale che aiuta a prevedere i tempi di viaggio. Veličković ha notato che DeepMind ha anche lavorato su un’applicazione Google Maps che applica reti di grafici per prevedere i tempi di viaggio. Questo ora serve le query in Google Maps in tutto il mondo e i dettagli sono illustrati in una recente pubblicazione .
Veličković ha affermato che sebbene uno degli algoritmi grafici più iconici, l’algoritmo di Dijkstra, possa in teoria aiutare a calcolare i percorsi più brevi o persino a stimare i tempi di viaggio, ciò non è applicabile nella realtà. Per farlo, dovresti prendere tutta la complessità del mondo reale – blocchi stradali, cambiamenti meteorologici, flussi di traffico, colli di bottiglia e quant’altro – e convertirla in un grafico “astratto” di nodi e archi con alcuni pesi che corrispondono al tempo di viaggio.
Questo esemplifica alcuni dei problemi con gli algoritmi. Come ha detto Veličković, gli algoritmi sono molto felici di darti risposte perfette, indipendentemente dal fatto che gli input stessi siano perfetti o meno. Quindi ti darà il percorso più breve. Ma chi, abbiamo chiesto a Veličković, garantisce che questo grafico sia una rappresentazione accurata dello scenario del mondo reale? Egli ha detto:
“L’algoritmo potrebbe darti un’ottima soluzione, ma non c’è davvero modo di dire se questa euristica ideata dall’uomo sia effettivamente il modo migliore di guardarla, e questo è il primo punto di attacco. Storicamente, abbiamo scoperto che ogni volta che c’è molta ingegneria delle funzionalità umane e molti dati grezzi con cui dobbiamo lavorare per l’ingegneria delle funzionalità umane, è qui che brilla il deep learning. Le storie di successo iniziali del deep learning sono state esattamente la sostituzione dell’euristica artigianale per, ad esempio, il riconoscimento delle immagini con reti neurali profonde.
Questo è il punto di partenza per NAR: sostituire l’essere umano che mappa i dati grezzi del mondo reale su un input grafico con una rete neurale. La rete mapperà la complessità dei dati grezzi su alcuni input grafici “astratti” che possono quindi essere utilizzati per eseguire l’algoritmo.
Veličković ha notato che esiste una buona linea di ricerca che funziona proprio in questo contesto. Questa ricerca ha anche trovato un modo per propagare i gradienti attraverso l’algoritmo in modo da poter effettivamente ottenere una buona ottimizzazione della rete neurale nell’impostazione e applicare l’algoritmo.
Ma, ha aggiunto, ci sono alcune limitazioni con l’impostazione, anche se sei in grado di propagare i gradienti attraverso di essa. Prima di tutto, l’algoritmo potrebbe non essere tutto ciò di cui hai bisogno per calcolare la soluzione finale. Alcune parti del problema potrebbero richiedere soluzioni con il percorso più breve, ma forse a un certo punto devi anche eseguire un algoritmo di flusso e non sei sicuro di come combinare i risultati nel modo migliore, perché il problema è molto grezzo e rumoroso:
“Forzare le tue rappresentazioni a fare affidamento sull’output di questo algoritmo potrebbe essere troppo limitante. Dijkstra richiede un valore scalare per ogni bordo del grafico, il che significa che stai comprimendo tutta quella straordinaria complessità del mondo reale in un solo numero per ogni segmento di strada.
Questo è potenzialmente problematico perché, se non hai abbastanza dati per stimare correttamente quello scalare, sei condannato. L’algoritmo non ti darà ancora una volta soluzioni corrette, perché non hai visto abbastanza dati grezzi per stimare correttamente quello scalare.
Rompere il collo di bottiglia algoritmico
Questo è ciò che Veličković e Blundell chiamano il collo di bottiglia algoritmico. Succede perché stiamo piazzando tutte le nostre scommesse su questo numero per ogni vantaggio, che è una rappresentazione dimensionale molto bassa del problema. Il modo per rompere i colli di bottiglia, suggerisce il duo DeepMind, è usare i vettori, piuttosto che i numeri. In altre parole, rimanendo altamente dimensionale.
Le reti neurali profonde stanno derivando gran parte del loro successo dal rimanere altamente dimensionali e dall’applicazione di tecniche di regolarizzazione ad alta dimensionalità. Ciò significa che anche se prevedi male alcune parti del vettore interno nella rete neurale, le altre parti di quel vettore possono comunque intervenire e compensare. Il problema è che gli algoritmi sono stati progettati per funzionare su rappresentazioni a bassa dimensione, non su input ad alta dimensione.
L’idea chiave in NAR è quella di sostituire l’algoritmo con una rete neurale, tipicamente una rete neurale a grafo (GNN) . La GNN prende un input ad alta dimensione e fa un passo di ragionamento per produrre un altro input ad alta dimensione. Quindi, una volta completati i passaggi sufficienti di quella rete neurale di ragionamento, gli output finali vengono previsti in base a questo.
Naturalmente, questo esecutore neurale GNN ad alta dimensione deve effettivamente imitare l’algoritmo a portata di mano. Per questo motivo, NAR include anche una pipeline astratta in cui la rete neurale è pre-addestrata, in genere utilizzando molti dati sintetici.
Il lavoro precedente di Blundell e Veličković, come l’ esecuzione neurale di algoritmi grafici , reti di grafi puntatori e passaggio di messaggi persistenti , trattava questa parte: come ottenere reti neurali affidabili e robuste che simulano algoritmi in uno spazio astratto.
Quello che Blundell e Veličković non avevano fatto era esaminare se questo potesse essere effettivamente utilizzato in un problema del mondo reale. È qui che entra in gioco il lavoro di Deac. L’approccio si basa su una combinazione di esecuzione neurale di algoritmi grafici, reti di grafici puntatori e messaggi persistenti. Tutto questo, ha osservato Deac, è stato inserito in un framework di apprendimento per rinforzo (RL) . In RL, i problemi sono inquadrati come stati e azioni e l’obiettivo è stimare quanto sia buono ogni stato. Questo è ciò che ha guidato le applicazioni RL nei giochi, come AlphaStar o AlphaGo, ha osservato Deac:
“Definiamo un certo valore sugli stati. Se pensi a una partita di scacchi, questo valore è: quanto è buona questa mossa? E quello che vogliamo è fare piani, prendere decisioni in modo che questo valore sia massimizzato. Se conosciamo le dinamiche dell’ambiente, [allora come facciamo a sapere] come possiamo passare da uno stato all’altro e che tipo di ricompense otteniamo da uno stato per un’azione specifica?”
Il modo per farlo è tramite un cosiddetto algoritmo di iterazione del valore, che può fornire stime di quanto sia buono ogni stato. L’algoritmo itera sulle stime di valore e le migliora gradualmente, finché non convergono ai valori di verità fondamentale. Questo è l’algoritmo che il team NAR sta cercando di imitare, utilizzando dati sintetici e semplici grafici per stimare i meta-valori.
La differenza è che il team voleva passare dall’utilizzo di singoli valori numerici all’utilizzo di vettori multidimensionali ad alto valore. Inizialmente, l’output potrebbe non essere così buono, ma non hai bisogno di molti dati per decollare perché l’algoritmo può gestire stime imperfette quando non conosci le dinamiche dell’ambiente.
La chiave, come ha spiegato Deac, è l’iterazione, che porta alla convergenza. In questo caso, un algoritmo del cammino minimo era di interesse. L’algoritmo può essere appreso e quindi collegato. Ma l’idea è che il framework RL dovrebbe essere utilizzabile per qualsiasi algoritmo o combinazione di algoritmi. Questo è un passaggio importante per l’apprendimento automatico, che a volte fa fatica a essere riapplicato da un dominio all’altro
Alte prestazioni in regimi di dati bassi
L’approccio su cui hanno lavorato Deac e il duo DeepMind si chiama eXecuted Latent Value Iteration Network, o XLVIN . Innanzitutto, l’algoritmo di iterazione del valore viene appreso nello spazio astratto. Quindi viene collegato un agente RL. Il team lo ha confrontato con un’architettura quasi identica, con una differenza cruciale: invece di utilizzare il loro componente algoritmico, quell’architettura prevede i valori ed esegue l’iterazione del valore direttamente su di essi.
Veličković ha affermato che questo secondo agente è effettivamente riuscito in alcuni casi a recuperare il ritardo, quando alimentato con molte più interazioni con ambienti diversi. Ma in regimi di dati molto bassi, l’architettura RL del team funziona meglio. Questo è importante, poiché per ambienti come Atari , un classico benchmark in AI utilizzato anche in XLVIN, più dati significa più budget di simulazione, che non è sempre fattibile.
XLVIN ha convalidato empiricamente un forte legame teorico tra gli algoritmi di programmazione dinamica ei calcoli di una GNN. Ciò significa, ha detto Veličković, che la maggior parte dell’euristica temporale polinomiale può essere interpretata come programmazione dinamica, il che a sua volta significa che le reti di grafi potrebbero essere il giusto bias induttivo per questo tipo di calcolo.
Il lavoro teorico precedente ha descritto uno scenario migliore, in cui ci sono impostazioni di pesi per una GNN che lo faranno comportare bene come quell’algoritmo di programmazione dinamica. Ma non ti dice necessariamente qual è il modo migliore per arrivarci e come farlo funzionare con i dati specifici che hai o estrapola, e questi sono problemi importanti per gli algoritmi, ha osservato Veličković.
Ciò ha portato il duo ad estendere il proprio lavoro a modelli come reti di grafi puntatori e messaggi persistenti, che hanno fatto un ulteriore passo avanti. Imitano il calcolo iterativo della programmazione dinamica, ma cercano anche di includere alcune strutture di dati che sono cruciali per il funzionamento degli algoritmi al giorno d’oggi e incorporano alcuni aspetti del ragionamento persistente.
Quindi, piuttosto che essere in grado di supportare una semplice struttura di dati su un insieme esistente di nodi, è possibile creare nodi aggiuntivi di memoria aggiuntiva? Molti algoritmi si basano sull’inizializzazione di memoria aggiuntiva oltre alla memoria necessaria per memorizzare i loro input. Quindi, la ricerca di DeepMind ha sviluppato modelli che consentono un allineamento sempre maggiore con il calcolo pur seguendo lo stesso progetto GNN.
RL, ha osservato Blundell, è fondamentalmente un algoritmo grafico. È un aggiornamento di programmazione dinamico ed è strettamente correlato a un algoritmo del percorso più breve: è come un algoritmo del percorso più breve online. Non sorprende che se stai cercando di trovare il percorso più breve possibile in un grafico, e poi vuoi rappresentare il tuo problema come un grafico, forse c’è una buona relazione lì.
La programmazione dinamica è un ottimo modo per pensare alla risoluzione di qualsiasi tipo di problema, ha aggiunto Blundell. Non puoi farlo sempre, ma quando puoi, funziona davvero, molto bene. E questa è potenzialmente una delle connessioni profonde tra algoritmi grafici, apprendimento per rinforzo e reti di grafi.
Un algoritmo per domarli tutti
Nel loro lavoro più recente pubblicato, Reasoning-Modulated Representations, Blundell e Veličković mostrano di essere in grado di utilizzare i modelli di ragionamento algoritmico per supportare l’apprendimento non supervisionato e l’apprendimento auto-supervisionato. Spesso, ha detto Veličković, l’apprendimento senza supervisione è tutto: “Ehi, prendiamo una quantità enorme di dati e proviamo a estrarne le proprietà più significative”.
Ma non sono sempre tutte le informazioni che hai. Potresti avere una certa conoscenza di come sono nati i tuoi dati. Ad esempio, se stai lavorando con la stima di alcune rappresentazioni da simulazioni fisiche, come un mucchio di palline che rimbalzano o sistemi a N corpi, non vedi solo un mucchio di istantanee di quel sistema. Sai che deve obbedire a certe leggi della fisica.
Pensiamo che il modello di ragionamento algoritmico neurale sia un modo eccellente per prendere quelle leggi della fisica, impacchettarle in una rete neurale che puoi unire come parte della tua architettura non supervisionata e, di conseguenza, ottenere rappresentazioni migliori. E stiamo iniziando a vedere alcuni risultati davvero positivi su una varietà di ambienti che questo progetto è effettivamente promettente.
Per quanto riguarda il futuro di questa ricerca, il duo di DeepMind vuole estendere il lavoro di Deac e applicarlo il più ampiamente possibile nell’apprendimento per rinforzo , che è un’area di grande interesse per DeepMind e non solo. Ci sono algoritmi “sinistra, destra e centro all’interno della pipeline di apprendimento per rinforzo”, come ha detto Veličković.
Blundell da parte sua ha ribadito che non ci sono molti algoritmi là fuori. Quindi la domanda è: possiamo impararli tutti? Se puoi avere una singola rete in grado di eseguire uno qualsiasi degli algoritmi che già conosci, allora se ottieni quella rete per collegare quegli algoritmi insieme, inizi a formare pipeline di elaborazione o programmi davvero piuttosto complicati. E se è tutto fatto con i gradienti che lo attraversano, allora inizi a imparare i programmi:
“Se lo porti davvero al limite, allora inizi a imparare davvero algoritmi che apprendono. Questo diventa molto interessante perché uno dei limiti del deep learning sono gli algoritmi che dobbiamo imparare. Non ci sono stati molti cambiamenti nei migliori ottimizzatori che utilizziamo o nel modo in cui aggiorniamo i pesi in una rete neurale durante l’allenamento per un periodo piuttosto lungo.
C’è stata una piccola ricerca su diverse architetture e così via. Ma non sempre hanno trovato la svolta successiva. La domanda è: è questo un modo diverso di vederlo, da dove possiamo iniziare a trovare nuovi algoritmi di apprendimento?
Gli algoritmi di apprendimento sono solo algoritmi, e forse quello che manca a loro è tutta questa base che abbiamo per altri algoritmi che stiamo usando. Quindi abbiamo bisogno di un esecutore di algoritmi leggermente più universale da utilizzare come base per metodi migliori per il machine learning.
Deac ha anche notato che vorrebbe perseguire una rete che provi più algoritmi, tutti gli algoritmi, se possibile. Lei e alcuni dei suoi colleghi MILA hanno fatto dei passi in quella direzione. Stanno facendo un po ‘di apprendimento di trasferimento, concatenando un paio di algoritmi insieme e vedendo se possono trasferire tra un algoritmo, rendendo più facile l’apprendimento di un algoritmo correlato separato, ha detto.
O in altre parole, come Veličković ha inquadrato quello che tutti sembrano considerare il Santo Graal di questa ricerca: “Un algoritmo per domarli tutti”.
