Teoria dei giochi come motore per l’analisi di dati su larga scala

'Game theory as a engine for large-scale data analysis'

EigenGame traccia un nuovo approccio per risolvere problemi fondamentali di ML

I moderni sistemi di intelligenza artificiale affrontano compiti come il riconoscimento degli oggetti nelle immagini e la previsione della struttura tridimensionale delle proteine come farebbe uno studente diligente per prepararsi a un esame. Allenandosi su molti esempi di problemi, minimizzano i loro errori nel tempo fino a raggiungere il successo. Ma questo è uno sforzo solitario e solo una delle forme conosciute di apprendimento. L’apprendimento avviene anche interagendo e giocando con gli altri. È raro che un singolo individuo possa risolvere problemi estremamente complessi da solo. Consentendo alla risoluzione dei problemi di assumere queste qualità simili a un gioco, gli sforzi precedenti di DeepMind hanno addestrato agenti di intelligenza artificiale a giocare a Capture the Flag e a raggiungere il livello di Grandmaster a Starcraft. Ciò ci ha fatto chiedere se una prospettiva basata sulla teoria dei giochi potesse aiutare a risolvere altri problemi fondamentali di machine learning.

Oggi all’ICLR 2021 (International Conference on Learning Representations), abbiamo presentato “EigenGame: PCA come un equilibrio di Nash”, che ha ricevuto un premio come Outstanding Paper. La nostra ricerca ha esplorato un nuovo approccio a un vecchio problema: abbiamo riformulato l’analisi delle componenti principali (PCA), un tipo di problema di autovalore, come un gioco competitivo multi-agente che chiamiamo EigenGame. PCA è tipicamente formulata come un problema di ottimizzazione (o problema di un singolo agente); tuttavia, abbiamo scoperto che la prospettiva multi-agente ci ha permesso di sviluppare nuove intuizioni e algoritmi che fanno uso delle più recenti risorse computazionali. Ciò ci ha permesso di scalare a set di dati enormi che in precedenza sarebbero stati troppo computazionalmente impegnativi e offre un approccio alternativo per future esplorazioni.

PCA come un equilibrio di Nash

Descritta per la prima volta all’inizio del 1900, la PCA è una tecnica consolidata per comprendere la struttura dei dati ad alta dimensione. Questo approccio è ormai ubiquo come primo passo nella pipeline di elaborazione dei dati e facilita il clustering e la visualizzazione dei dati. Può anche essere uno strumento utile per apprendere rappresentazioni a bassa dimensione per la regressione e la classificazione. A più di un secolo di distanza, ci sono ancora motivi convincenti per studiare la PCA.

Innanzitutto, i dati venivano originariamente registrati a mano su quaderni di carta, ora vengono conservati in centri di dati delle dimensioni di magazzini. Di conseguenza, questa analisi familiare è diventata un collo di bottiglia computazionale. I ricercatori hanno esplorato algoritmi randomizzati e altre direzioni per migliorare la scalabilità della PCA, ma abbiamo scoperto che questi approcci hanno difficoltà a scalare a insiemi di dati enormi perché non riescono a sfruttare appieno i recenti avanzamenti focalizzati sull’apprendimento profondo in termini di calcolo, ovvero l’accesso a molte GPU o TPU parallele.

In secondo luogo, la PCA condivide una soluzione comune con molti importanti problemi di ML e di ingegneria, ovvero la scomposizione ai valori singolari (SVD). Avvicinandoci al problema della PCA nel modo giusto, le nostre intuizioni e gli algoritmi si applicano in modo più ampio in tutti i rami dell’albero del ML.

Figura 1. Con l'SVD alle sue radici, l'albero della conoscenza comprende molte idee fondamentali nell'apprendimento automatico, inclusi PCA, Least Squares, Spectral Clustering, Proto Value Functions, Latent Semantic Indexing e Sorting.

Come per qualsiasi gioco da tavolo, per reinventare la PCA come un gioco abbiamo bisogno di un insieme di regole e obiettivi da seguire per i giocatori. Ci sono molti modi possibili per progettare un tale gioco; tuttavia, le idee importanti derivano dalla PCA stessa: la soluzione ottimale consiste in autovettori che catturano la varianza importante nei dati e sono ortogonali tra loro.

Figura 2. Ogni giocatore desidera allinearsi con una direzione di massima varianza (maggiore dispersione dei dati) ma rimanere anche perpendicolare ai giocatori sopra di lui nella gerarchia (tutti i giocatori con un numero inferiore).

In EigenGame, ogni giocatore controlla un autovettore. I giocatori aumentano il loro punteggio spiegando la varianza all’interno dei dati, ma vengono penalizzati se sono troppo allineati con gli altri giocatori. Stabiliamo anche una gerarchia: il Giocatore 1 si preoccupa solo di massimizzare la varianza, mentre gli altri giocatori devono anche preoccuparsi di minimizzare il loro allineamento con i giocatori sopra di loro nella gerarchia. Questa combinazione di ricompense e penalità definisce l’utilità di ciascun giocatore.

Figura 3. Riassunto dell'utilità di ciascun giocatore sopra.

Con i termini Var e Align progettati in modo appropriato, possiamo dimostrare che:

  • Se tutti i giocatori giocano in modo ottimale, insieme raggiungono l’equilibrio di Nash del gioco, che è la soluzione PCA.
  • Questo può essere ottenuto se ogni giocatore massimizza la propria utilità in modo indipendente e simultaneo utilizzando la crescita del gradiente.
Figura 4. EigenGame guida ciascun giocatore lungo la sfera unitaria dai cerchi vuoti alle frecce in parallelo. Il blu è il giocatore 1. Il rosso è il giocatore 2. Il verde è il giocatore 3.

Questa proprietà di indipendenza dell’ascesa simultanea è particolarmente importante perché consente di distribuire il calcolo su decine di Google Cloud TPU, consentendo sia la parallelizzazione dei dati che dei modelli. Ciò rende possibile per il nostro algoritmo adattarsi a dati veramente di grandi dimensioni. EigenGame trova i componenti principali in poche ore per set di dati di centinaia di terabyte che comprendono milioni di feature o miliardi di righe.

Figura 5. Ogni quadrato colorato è un dispositivo separato. (L) Ogni giocatore vive e calcola gli aggiornamenti su un singolo dispositivo. (R) Ogni giocatore viene copiato su più dispositivi e calcola gli aggiornamenti utilizzando batch di dati indipendenti; gli aggiornamenti diversi vengono quindi mediati per formare una direzione di aggiornamento più robusta.

Utilità, aggiornamenti e tutto ciò che sta nel mezzo

Pensando alla PCA da una prospettiva multi-agente, siamo stati in grado di proporre algoritmi scalabili e analisi innovative. Abbiamo anche scoperto una sorprendente connessione con l’apprendimento di Hebb – o come si adattano i neuroni durante l’apprendimento. In EigenGame, ogni giocatore che massimizza la propria utilità dà origine a equazioni di aggiornamento simili a regole di aggiornamento derivate da modelli di plasticità sinaptica nel cervello. Gli aggiornamenti di Hebb sono noti per convergere alla soluzione PCA, ma non sono derivati come il gradiente di alcuna funzione di utilità. La teoria dei giochi ci offre una prospettiva nuova per visualizzare l’apprendimento di Hebb e suggerisce anche una serie di approcci ai problemi di apprendimento automatico.

Da un lato del continuum di ML si trova il percorso ben sviluppato di proporre una funzione obiettivo che può essere ottimizzata: utilizzando la teoria dell’ottimizzazione convessa e non convessa, i ricercatori possono ragionare sulle proprietà globali della soluzione. Dall’altro lato, i metodi puramente connessionisti e le regole di aggiornamento ispirate alla neuroscienza sono specificati direttamente, ma l’analisi dell’intero sistema può essere più difficile, spesso invocando lo studio di sistemi dinamici complicati.

Gli approcci basati sulla teoria dei giochi come EigenGame si trovano da qualche parte in mezzo. Gli aggiornamenti dei giocatori non sono vincolati ad essere il gradiente di una funzione, ma solo una migliore risposta alle strategie correnti degli altri giocatori. Siamo liberi di progettare utilità e aggiornamenti con proprietà desiderabili, ad esempio specificando aggiornamenti che siano imparziali o accelerati, mentre assicuriamo che la proprietà di Nash ci permetta comunque di analizzare l’intero sistema.

Figura 6: Consentire utilità multiple colma il divario tra approcci di ottimizzazione e sistemi dinamici.

EigenGame rappresenta un esempio concreto di progettazione della soluzione a un problema di apprendimento automatico come output di un grande sistema multi-agente. In generale, progettare problemi di apprendimento automatico come giochi multi-agente è un problema di progettazione meccanica complesso; tuttavia, i ricercatori hanno già utilizzato la classe di giochi a due giocatori e somma zero per risolvere problemi di apprendimento automatico. In particolare, il successo delle reti generative avversariali (GAN) come approccio alla modellazione generativa ha suscitato interesse per la relazione tra teoria dei giochi e apprendimento automatico.

Il gioco EigenGame va oltre questo, arrivando al più complesso scenario di molti giocatori e somma generale. Ciò consente un parallelismo più evidente per una maggiore scala e velocità. Presenta anche un punto di riferimento quantitativo per la comunità per testare nuovi algoritmi multi-agente insieme a domini più ricchi, come la diplomazia e il calcio.

Speriamo che il nostro progetto per la progettazione di utilità e aggiornamenti incoraggi altri a esplorare questa direzione per la progettazione di nuovi algoritmi, agenti e sistemi. Non vediamo l’ora di vedere quali altri problemi possono essere formulati come giochi e se le intuizioni che otterremo miglioreranno ulteriormente la nostra comprensione della natura multi-agente dell’intelligenza.

Per maggiori dettagli consulta il nostro articolo EigenGame: PCA come equilibrio di Nash e il nostro lavoro di approfondimento EigenGame Unloaded: Quando giocare ai giochi è meglio dell’ottimizzazione.