Previsione del traffico con avanzati Graph Neural Networks

'Previsione traffico con Graph Neural Networks avanzate'

Collaborando con Google, DeepMind è in grado di portare i benefici dell’AI a miliardi di persone in tutto il mondo. Dalla riunione di un utente con problemi di linguaggio con la sua voce originale, all’aiuto agli utenti nel trovare app personalizzate, possiamo applicare ricerche innovative a problemi reali immediati su scala Google. Oggi siamo lieti di condividere i risultati della nostra ultima collaborazione, che ha un impatto globale per oltre un miliardo di persone che utilizzano Google Maps.

La nostra collaborazione con Google Maps

Le persone si affidano a Google Maps per previsioni accurate sul traffico e tempi di arrivo stimati (ETAs). Sono strumenti fondamentali che sono particolarmente utili quando è necessario evitare un ingorgo stradale, se è necessario avvisare amici e familiari che si è in ritardo o se è necessario partire in tempo per partecipare a una riunione importante. Queste funzioni sono anche utili per le aziende come le compagnie di ride-sharing, che utilizzano Google Maps Platform per alimentare i loro servizi con informazioni sui tempi di prelievo e rilascio, insieme a prezzi stimati basati sulla durata del viaggio.

I ricercatori di DeepMind hanno collaborato con il team di Google Maps per migliorare l’accuratezza degli ETAs in tempo reale fino al 50% in luoghi come Berlino, Jakarta, São Paulo, Sydney, Tokyo e Washington D.C. utilizzando tecniche avanzate di apprendimento automatico, tra cui le reti neurali grafiche, come mostra il grafico qui sotto:

• Apprendimento automatico rapido tramite la composizione di comportamenti
• FermiNet Fisica Quantistica e Chimica dalle Prime Principî
• Abbattere le barriere globali di accesso

Come Google Maps prevede gli ETAs

Per calcolare gli ETAs, Google Maps analizza i dati sul traffico in tempo reale per i segmenti stradali di tutto il mondo. Sebbene questi dati forniscano a Google Maps un’immagine accurata del traffico attuale, non tengono conto del traffico che un guidatore può aspettarsi di vedere dopo 10, 20 o anche 50 minuti di viaggio. Per prevedere accuratamente il traffico futuro, Google Maps utilizza l’apprendimento automatico per combinare le condizioni di traffico in tempo reale con i modelli di traffico storici per le strade di tutto il mondo. Questo processo è complesso per diverse ragioni. Ad esempio, anche se l’ora di punta si verifica inevitabilmente ogni mattina e sera, l’orario esatto dell’ora di punta può variare significativamente da giorno a giorno e da mese a mese. Fattori aggiuntivi come la qualità delle strade, i limiti di velocità, gli incidenti e le chiusure possono anche aggiungere complessità al modello di previsione.

DeepMind ha collaborato con Google Maps per migliorare l’accuratezza degli ETAs in tutto il mondo. Sebbene gli ETAs predittivi di Google Maps siano stati costantemente accurati per oltre il 97% dei viaggi, abbiamo lavorato con il team per ridurre al minimo le imprecisioni residue ancora di più, a volte anche oltre il 50% in città come Taichung. Per farlo su scala globale, abbiamo utilizzato un’architettura di apprendimento automatico generalizzata chiamata Graph Neural Networks che ci consente di condurre un ragionamento spaziotemporale incorporando i bias di apprendimento relazionali per modellare la struttura di connettività delle reti stradali reali. Ecco come funziona:

Dividere le strade del mondo in Supersegmenti

Abbiamo diviso le reti stradali in “Supersegmenti” costituiti da più segmenti stradali adiacenti che condividono un volume significativo di traffico. Attualmente, il sistema di previsione del traffico di Google Maps è composto dai seguenti componenti: (1) un analizzatore di percorsi che elabora terabyte di informazioni sul traffico per costruire i Supersegmenti e (2) un nuovo modello di rete neurale grafica, ottimizzato con obiettivi multipli, che prevede il tempo di percorrenza per ciascun Supersegmento.

Sulla strada verso nuove architetture di apprendimento automatico per la previsione del traffico

La sfida più grande da risolvere nella creazione di un sistema di apprendimento automatico per stimare i tempi di percorrenza utilizzando Supersegmenti è di natura architetturale. Come rappresentare esempi di segmenti connessi di dimensioni dinamiche con precisione arbitraria in modo che un singolo modello possa avere successo?

La nostra prova di concetto iniziale è iniziata con un approccio diretto che utilizzava il sistema di traffico esistente per quanto possibile, in particolare la segmentazione esistente delle reti stradali e il relativo flusso di dati in tempo reale. Ciò significava che un Supersegmento copriva un insieme di segmenti stradali, dove ogni segmento aveva una lunghezza specifica e caratteristiche di velocità corrispondenti. All’inizio abbiamo addestrato un singolo modello di rete neurale completamente connessa per ogni Supersegmento. Questi risultati iniziali sono stati promettenti e hanno dimostrato il potenziale nell’utilizzo delle reti neurali per la previsione del tempo di percorrenza. Tuttavia, dati i formati dinamici dei Supersegmenti, avremmo avuto bisogno di un modello di rete neurale separato per ognuno. Per implementare ciò su larga scala, avremmo dovuto addestrare milioni di questi modelli, il che avrebbe rappresentato una considerevole sfida infrastrutturale. Questo ci ha spinto a cercare modelli in grado di gestire sequenze di lunghezza variabile, come le reti neurali ricorrenti (RNN). Tuttavia, incorporare ulteriori strutture dalla rete stradale si è dimostrato difficile. Invece, abbiamo deciso di utilizzare le reti neurali grafiche. Nella modellazione del traffico, ci interessa come le auto si muovono attraverso una rete di strade e le reti neurali grafiche possono modellare le dinamiche di rete e la propagazione delle informazioni.

Il nostro modello considera la rete stradale locale come un grafo, in cui ogni segmento di percorso corrisponde a un nodo e gli archi esistono tra segmenti che sono consecutivi sulla stessa strada o collegati attraverso un’intersezione. In una Graph Neural Network, viene eseguito un algoritmo di passaggio di messaggi in cui i messaggi e il loro effetto sugli stati degli archi e dei nodi vengono appresi dalle reti neurali. Da questa prospettiva, i nostri Supersegmenti sono sottografi stradali, che sono stati campionati casualmente in proporzione alla densità del traffico. Un singolo modello può quindi essere addestrato utilizzando questi sottografi campionati e può essere implementato su larga scala.

Le Graph Neural Networks estendono il bias di apprendimento imposto dalle Convolutional Neural Networks e dalle Recurrent Neural Networks generalizzando il concetto di “vicinanza”, consentendoci di avere connessioni arbitrariamente complesse per gestire non solo il traffico avanti o dietro di noi, ma anche lungo strade adiacenti e intersecanti. In una Graph Neural Network, i nodi adiacenti si scambiano messaggi tra loro. Mantenendo questa struttura, imponiamo un bias di località in cui i nodi troveranno più facile fare affidamento sui nodi adiacenti (questo richiede solo un passaggio di messaggi). Questi meccanismi consentono alle Graph Neural Networks di sfruttare in modo più efficace la struttura di connettività della rete stradale. I nostri esperimenti hanno dimostrato guadagni di potenza predittiva dall’inclusione di strade adiacenti che non fanno parte della strada principale. Ad esempio, pensa a come un ingorgo in una strada secondaria può riversarsi sul traffico di una strada più grande. Attraversando più intersezioni, il modello acquisisce la capacità di prevedere nativamente ritardi nei cambi di direzione, ritardi dovuti all’incorporazione e il tempo complessivo di percorrenza nel traffico a scatti. Questa capacità delle Graph Neural Networks di generalizzare su spazi combinatori è ciò che conferisce potenza alla nostra tecnica di modellazione. Ogni Supersegmento, che può avere lunghezza e complessità variabili – da semplici percorsi di due segmenti a percorsi più lunghi contenenti centinaia di nodi – può comunque essere elaborato dallo stesso modello di Graph Neural Network.

Dalla ricerca di base ai modelli di apprendimento automatico pronti per la produzione

Una grande sfida per un sistema di apprendimento automatico di produzione che spesso viene trascurata nell’ambiente accademico riguarda la grande variabilità che può esistere tra diverse esecuzioni di addestramento dello stesso modello. Mentre piccole differenze di qualità possono essere semplicemente scartate come cattive inizializzazioni in contesti più accademici, queste piccole incongruenze possono avere un grande impatto quando vengono sommate su milioni di utenti. Pertanto, rendere la nostra Graph Neural Network robusta a questa variabilità nell’addestramento è diventato il punto focale quando abbiamo spinto il modello in produzione. Abbiamo scoperto che le Graph Neural Networks sono particolarmente sensibili ai cambiamenti nel curriculum di addestramento, la causa principale di questa instabilità è la grande variabilità nelle strutture di grafi utilizzate durante l’addestramento. Un singolo batch di grafi poteva contenere da piccoli grafi con due nodi a grandi grafi con oltre 100 nodi.

Dopo molti tentativi ed errori, tuttavia, abbiamo sviluppato un approccio per risolvere questo problema adattando una nuova tecnica di apprendimento per rinforzo per l’utilizzo in un contesto supervisionato.

Nell’addestramento di un sistema di apprendimento automatico, il tasso di apprendimento di un sistema specifica quanto “plastico” – o suscettibile a nuove informazioni – sia. I ricercatori spesso riducono il tasso di apprendimento dei loro modelli nel tempo, poiché c’è un compromesso tra l’apprendimento di nuove cose e l’oblio delle caratteristiche importanti già apprese, non molto diverso dalla progressione dall’infanzia all’età adulta. Inizialmente abbiamo utilizzato un programma di riduzione esponenziale del tasso di apprendimento per stabilizzare i nostri parametri dopo un periodo predefinito di addestramento. Abbiamo anche esplorato e analizzato tecniche di insiemistica del modello che si sono dimostrate efficaci in lavori precedenti per vedere se potevamo ridurre la varianza del modello tra le esecuzioni di addestramento.

In definitiva, l’approccio più efficace a questo problema è stato utilizzare i MetaGradients per adattare dinamicamente il tasso di apprendimento durante l’addestramento, consentendo di fatto al sistema di apprendere il proprio programma di apprendimento ottimale. Adattando automaticamente il tasso di apprendimento durante l’addestramento, il nostro modello non solo ha raggiunto una qualità superiore rispetto al passato, ma ha anche imparato a diminuire automaticamente il tasso di apprendimento. Ciò ha portato a risultati più stabili, consentendoci di utilizzare la nostra nuova architettura in produzione.

Rendere i modelli generalizzabili attraverso funzioni di perdita personalizzate

Mentre l’obiettivo ultimo del nostro sistema di modellazione è ridurre gli errori nelle stime di viaggio, abbiamo scoperto che l’utilizzo di una combinazione lineare di più funzioni di perdita (pesate appropriatamente) ha notevolmente aumentato la capacità del modello di generalizzare. In particolare, abbiamo formulato un obiettivo di multi-perdita utilizzando un fattore di regolarizzazione sui pesi del modello, perdite L_2 e L_1 sui tempi di attraversamento globali, così come perdite individuali di Huber e negative-log likelihood (NLL) per ogni nodo nel grafo. Combinando queste perdite siamo stati in grado di guidare il nostro modello e evitare l’overfitting sul dataset di addestramento. Mentre le nostre misurazioni di qualità in addestramento non sono cambiate, i miglioramenti osservati durante l’addestramento si sono tradotti in modo più diretto negli insiemi di test e nei nostri esperimenti end-to-end.

Attualmente stiamo esplorando se la tecnica MetaGradient può essere utilizzata anche per variare la composizione della funzione di perdita multi-componente durante l’allenamento, utilizzando la riduzione degli errori nella stima del percorso come metrica guida. Questo lavoro è ispirato agli sforzi di MetaGradient che hanno ottenuto successo nell’apprendimento per rinforzo e i primi esperimenti mostrano risultati promettenti.

Collaborazione

Grazie alla nostra stretta e fruttuosa collaborazione con il team di Google Maps, siamo stati in grado di applicare queste nuove e innovative tecniche su larga scala. Insieme, siamo riusciti a superare sia le sfide di ricerca che i problemi di produzione e scalabilità. Alla fine, il modello finale e le tecniche hanno portato a un lancio di successo, migliorando l’accuratezza degli ETA su Google Maps e sulle API di Google Maps Platform in tutto il mondo.

Lavorare a scala Google con ricerche all’avanguardia rappresenta un insieme unico di sfide. Se sei interessato a utilizzare tecniche all’avanguardia come le Graph Neural Networks per affrontare problemi del mondo reale, scopri di più sul team che lavora su questi problemi qui .