La teoria dei giochi come motore per l'analisi dei dati su larga scala | Intelligenza-Artificiale

Indice contenuti

EigenGame delinea un nuovo approccio per risolvere problemi fondamentali di ML

I moderni sistemi di intelligenza artificiale affrontano compiti come riconoscere gli oggetti nelle immagini E predire la struttura 3D delle proteine come uno studente diligente si preparerebbe per un esame. Addestrandosi su molti problemi di esempio, riducono al minimo i propri 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 da solo problemi estremamente complessi. Consentendo alla risoluzione dei problemi di assumere queste qualità simili a quelle di un gioco, i precedenti sforzi di DeepMind hanno addestrato gli agenti IA a giocare Cattura la bandiera e raggiungere Livello Grandmaster presso Starcraft. Ciò ci ha portato a chiederci se una tale prospettiva modellata sulla teoria dei giochi potrebbe aiutare a risolvere altri problemi fondamentali dell’apprendimento automatico.

Oggi alle ICLR 2021 (la Conferenza Internazionale sulle Rappresentazioni dell’Apprendimento), abbiamo presentato “EigenGame: PCA come equilibrio di Nash”, che ha ricevuto un Outstanding Paper Award. La nostra ricerca ha esplorato un nuovo approccio a un vecchio problema: abbiamo riformulato l’analisi delle componenti principali (PCA), un tipo di problema degli autovaloricome gioco competitivo multi-agente chiamiamo EigenGame. La PCA è tipicamente formulata come un problema di ottimizzazione (o problema ad agente singolo); tuttavia, abbiamo scoperto che la prospettiva multi-agente ci ha permesso di sviluppare nuove intuizioni e algoritmi che utilizzano le più recenti risorse computazionali. Ciò ci ha permesso di adattarci a enormi set di dati che in precedenza sarebbero stati troppo impegnativi dal punto di vista computazionale e offre un approccio alternativo per l’esplorazione futura.

PCA come equilibrio di Nash

Descritto per la prima volta agli inizi del 1900, PCA è una tecnica di lunga data per dare un senso alla struttura dei dati ad alta dimensione. Questo approccio è ormai onnipresente come primo passo nella pipeline di elaborazione dei dati e semplifica 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. Più di un secolo dopo, ci sono ancora validi motivi per studiare la PCA.

In primo luogo, i dati venivano originariamente registrati a mano su quaderni di carta, mentre ora sono archiviati in data center grandi quanto 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 adattarsi a set di dati di grandi dimensioni perché non sono in grado di sfruttare appieno i recenti progressi nel calcolo incentrati sul deep learning, ovvero l’accesso a molte GPU o TPU parallele.

In secondo luogo, PCA condivide una soluzione comune con molti importanti problemi di ML e di ingegneria, vale a dire il Scomposizione di un valore singolo (SVD). Affrontando il problema PCA nel modo giusto, le nostre intuizioni e i nostri algoritmi si applicano in modo più ampio a tutti i rami dell’albero ML.

Figura 1. Con SVD alle radici, l’albero della conoscenza comprende molte idee fondamentali nell’apprendimento automatico, tra cui PCA, minimi quadrati, clustering spettrale, funzioni di protovalore, indicizzazione semantica latente e ordinamento.

Come con qualsiasi gioco da tavolo, per reinventare PCA come gioco abbiamo bisogno di una serie di regole e obiettivi che i giocatori possano seguire. Esistono molti modi possibili per progettare un gioco del genere; tuttavia, idee importanti provengono dalla stessa PCA: la soluzione ottimale è costituita da autovettori che catturano l’importante varianza nei dati e sono ortogonali tra loro.

Figura 2. Ogni giocatore desidera allinearsi con una direzione di massima varianza (maggiore diffusione dei dati), ma rimanere anche perpendicolare ai giocatori più in alto 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 agli altri giocatori. Stabiliamo anche una gerarchia: il giocatore 1 si preoccupa solo di massimizzare la varianza, mentre gli altri giocatori devono anche preoccuparsi di ridurre al minimo il loro allineamento con i giocatori sopra di loro nella gerarchia. Questa combinazione di premi e penalità definisce l’utilità di ciascun giocatore.

Figura 3. Riepilogo dell’utilità di ciascun giocatore sopra.

Con opportunamente progettato Era E Allineare termini, possiamo dimostrare che:

Se tutti i giocatori giocano in modo ottimale, insieme raggiungono il risultato equilibrio di Nash del gioco, che è la soluzione PCA.
Ciò può essere ottenuto se ciascun giocatore massimizza la propria utilità in modo indipendente e simultaneamente utilizzando l’ascesa gradiente.

Figura 4. EigenGame guida ogni 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 dozzine di Google Cloud TPU, consentendo il parallelismo sia dei dati che del modello. Ciò consente al nostro algoritmo di adattarsi a dati veramente su larga scala. EigenGame trova i componenti principali in poche ore per set di dati da cento terabyte comprendenti milioni di funzionalità 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 lettore viene copiato su più dispositivi e calcola gli aggiornamenti utilizzando batch di dati indipendenti; viene quindi calcolata la media dei diversi aggiornamenti per formare una direzione di aggiornamento più solida.

Utilità, aggiornamenti e tutto il resto

Pensando alla PCA da una prospettiva multi-agente, siamo stati in grado di proporre algoritmi scalabili e nuove analisi. Abbiamo anche scoperto una connessione sorprendente con Apprendimento hebbiano – o come i neuroni si adattano durante l’apprendimento. In EigenGame, ogni giocatore che massimizza le proprie utilità dà origine ad equazioni di aggiornamento simili a aggiornare le regole derivato da modelli hebbiani di plasticità sinaptica nel cervello. È noto che gli aggiornamenti Hebbiani convergono alla soluzione PCA ma non sono derivati come gradiente di alcuna funzione di utilità. La teoria dei giochi ci offre una nuova prospettiva per visualizzare l’apprendimento hebbiano e suggerisce anche un continuum di approcci ai problemi dell’apprendimento automatico.

A un’estremità del continuum ML c’è 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. D’altro canto, puro connessionista metodi e regole di aggiornamento ispirate alle neuroscienze vengono specificati direttamente, ma l’analisi dell’intero sistema può essere più difficile, richiedendo spesso lo studio di complicati sistemi dinamici.

Gli approcci teorici dei giochi come EigenGame si collocano da qualche parte nel mezzo. Gli aggiornamenti dei giocatori non sono vincolati ad essere il gradiente di una funzione, ma solo la migliore risposta alle strategie attuali degli altri giocatori. Siamo liberi di progettare utilità e aggiornamenti con proprietà desiderabili, ad esempio specificando aggiornamenti imparziali o accelerati, garantendo al tempo stesso che la proprietà di Nash ci consenta comunque di analizzare il sistema nel suo complesso.

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

EigenGame rappresenta un esempio concreto di progettazione della soluzione a un problema di machine learning come risultato di un grande sistema multi-agente. Più in generale, progettare problemi di machine learning come giochi multi-agente è una sfida progettazione del meccanismo problema; tuttavia, i ricercatori hanno già utilizzato la classe a due giocatori, a somma zero giochi per risolvere problemi di machine learning. In particolare, il successo di reti avversarie generative (GAN) come approccio alla modellazione generativa ha stimolato l’interesse per la relazione tra teoria dei giochi e apprendimento automatico.

EigenGame va oltre questo, verso l’impostazione più complessa a molti giocatori e con somma generale. Ciò consente un parallelismo più evidente per una maggiore scala e velocità. Presenta inoltre un punto di riferimento quantitativo per la comunità per testare nuovi algoritmi multi-agente insieme a domini più ricchi, come Diplomazia E Calcio.

Ci auguriamo 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. Siamo ansiosi di vedere quali altri problemi potranno essere formulati come giochi e se le intuizioni che raccoglieremo 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 successivo EigenGame Unloaded: quando giocare è meglio che ottimizzare.