Coautori: Javen Xu , Hakan Baba e Adriana Deneault

Introduzione

I metodi di apprendimento grafico possono rivelare intuizioni interessanti che catturano le strutture relazionali sottostanti. I metodi di apprendimento grafico hanno molte applicazioni industriali in aree come i sistemi di raccomandazione di prodotti o contenuti e l'analisi di rete.

In questo post, discutiamo di come utilizziamo i metodi di apprendimento dei grafici in Lyft per generare incorporamenti, una rappresentazione vettoriale compatta di informazioni ad alta dimensione. Condivideremo interessanti approfondimenti sul rideshare scoperti dall'incorporamento di motociclisti, conducenti, luoghi e orari. Come mostreranno gli esempi, gli incorporamenti addestrati dai grafici possono rappresentare informazioni e modelli che sono difficili da acquisire con funzionalità tradizionali e dirette.

Dati e incorporamenti di Lyft

In Lyft disponiamo di dati semi-strutturati che catturano interazioni complesse tra conducenti, motociclisti, luoghi e tempo. Possiamo costruire grafici che rappresentano queste interazioni (ad esempio, un grafico può essere formato collegando un ciclista con tutti i luoghi che ha visitato). Da questi grafici possiamo generare incorporamenti per esprimere sinteticamente l'intera cronologia di guida di un ciclista o di un pilota. Questi incorporamenti ci consentono di riassumere in modo efficiente informazioni vaste e varie in una rappresentazione adatta alla macchina.

Ad esempio, ci sono oltre 9.000 località di livello Geohash-6 (Gh6) nella San Francisco Bay Area. Se volessimo descrivere la storia del viaggio di un guidatore nella Bay Area senza incorporamenti, avremmo bisogno di un istogramma o di un vettore di lunghezza superiore a 9.000 per descriverlo con precisione. Il vettore conterrebbe il numero di corse che il conducente ha iniziato in ogni Gh6, con molti zeri se il conducente non è mai stato in alcuni Gh6.

Con l'apprendimento grafico siamo in grado di addestrare un vettore di incorporamento di dimensioni inferiori che rappresenta le stesse informazioni. Potrebbe non catturare i dettagli esatti a causa della riduzione delle dimensioni intrinseche, ma come mostreremo in Lyft Ride Insights di seguito, gli incorporamenti ben addestrati sono in grado di catturare il quadro generale della cronologia di viaggio di un conducente.

Un altro vantaggio è che gli incorporamenti sono vettori d -dimensionali che descrivono singoli punti in uno spazio vettoriale d -dimensionale e quegli spazi possono essere condivisi da diverse entità definite. Le entità sono i punti, o nodi, nel grafico di input che vogliamo rappresentare mediante vettori di incorporamento e sono raggruppati per tipi di entità. Ad esempio, possiamo costruire due vettori di incorporamento, uno che rappresenta un'entità ciclista e uno che rappresenta un'entità posizione dallo stesso grafico, dove un bordo connesso nel grafico significa che questo ciclista ha visitato questa posizione. Con una funzione di somiglianza(definito nella configurazione del problema), possiamo confrontare direttamente i due vettori di incorporamento calcolando un punteggio di somiglianza tra di loro. In questo grafico, il punteggio di somiglianza descrive la frequenza con cui il nostro ciclista ha visitato la località scelta.

Sebbene un grafico possa incorporare molti tipi di entità differenti (ad es. ciclista, posizione, conducente) e relazioni (ad es. prelevato, lasciato), i grafici semplici possono comunque essere informativi. Come mostreranno i nostri esempi, anche con solo due tipi di entità e un tipo di relazione, gli incorporamenti basati su grafi possono comunque fornire preziose informazioni.

Metodologia

Incorporamenti basati su grafici in poche parole

Un grafo multi-entità viene costruito disegnando entità come nodi e creando connessioni (cioè spigoli) tra entità in cui esiste una relazione interpretabile. L'idea degli incorporamenti basati su grafi è di codificare i nodi in modo che la somiglianza nello spazio di incorporamento (ad es. prodotto scalare ) approssimi la vicinanza nel grafo. Due entità hanno un alto punteggio di somiglianza con i loro incorporamenti se sono collegate direttamente nel grafico originale (ad es. distanza di connessione di “1 grado”) o hanno una distanza molto ravvicinata (ad es. connessione di “2 gradi”).

Ci sono due componenti chiave: 1) un codificatore che associa ciascun nodo a un vettore a bassa dimensione e 2) una funzione di somiglianza che specifica come le relazioni nello spazio vettoriale si mappano alle relazioni nella rete originale.

Possiamo specificare le dimensioni dello spazio di incorporamento (ovvero l'output) nel processo di addestramento. Scegliendo una dimensionalità appropriata, siamo in grado di catturare le intricate relazioni tra entità dal grafico di input originale in uno spazio vettoriale dimensionale molto più basso e compatto. Possiamo persino eseguire calcoli di distanza con prodotti scalari vettoriali nello spazio degli incorporamenti per ottenere una misura quantitativa della "somiglianza" o "distanza" tra entità diverse.

Successivamente, utilizzeremo un semplice grafico di corsa Lyft come esempio per illustrare i dettagli dell'addestramento degli incorporamenti.

Ride Graphs al Lyft and Embeddings Training

In Lyft, siamo interessati a conoscere i motociclisti, i conducenti e le loro preferenze di guida rispetto a fattori come la posizione e l'ora.

Prendendo la posizione come esempio, possiamo costruire un grafico come la Figura 2. Ogni ciclista, conducente e posizione è rappresentato come un'entità separata e vengono tracciate le connessioni in cui un ciclista o conducente ha iniziato una corsa da una determinata posizione.

Il nostro algoritmo di addestramento si estende dal pacchetto Pytorch BigGraph . All'inizio dell'addestramento, specifichiamo le dimensioni d dei vettori di incorporamento che vogliamo ottenere e l'algoritmo assegna valori casuali a questi vettori di incorporamento d -dimensionali come parametri iniziali. Come principio generale, scegliamo una dimensione di incorporamento dell'output più alta se il grafo originale è complesso con un gran numero di entità e intricati bordi connessi. Una dimensione di incorporamento più alta catturerà più informazioni dal grafico.

L'obiettivo dell'addestramento è apprendere i vettori di incorporamento d -dimensionali per ciascuna entità (cioè nodo) in modo tale che la somiglianza calcolata tra due entità qualsiasi rifletta la loro relazione. Ad esempio, due entità molto vicine nello spazio avrebbero un punteggio di somiglianza più positivo rispetto a due entità distanti.

Durante ogni ciclo di addestramento, per ogni entità, ogni spigolo connesso all'entità nel grafico di input originale è considerato un'istanza positiva (+), mentre l'algoritmo campiona casualmente dalle entità non connesse per le istanze negative (-). Nel nostro grafico di corsa, i campioni apparirebbero come nella Figura 3 di seguito. Si noti come i bordi con etichetta positiva esistano nella Figura 2 sopra, ma i bordi con etichetta negativa no.

I vettori di incorporamento per le entità vengono confrontati a coppie utilizzando un comparatore scelto per generare un punteggio di somiglianza. Una scelta semplice è la somiglianza del coseno, che viene calcolata come prodotto scalare di due vettori.

Una volta determinati i punteggi di tutti i campioni positivi e negativi, una metrica di perdita aggrega i punteggi in un unico valore di perdita per epoca per consentire l'apprendimento. Le funzioni di perdita comuni sono la perdita di classifica, la perdita logistica e la perdita di softmax .

Infine, la perdita viene minimizzata utilizzando un metodo di ottimizzazione Adagrad per aggiornare tutti i parametri del modello.

Lyft Ride Approfondimenti

Ora possiamo mostrare intuizioni interessanti che cavalcano gli incorporamenti di grafici rivelati. Una rapida dichiarazione di non responsabilità che la nostra analisi si concentra su informazioni anonime o aggregate e non miriamo a ricavare alcuna caratteristica personale o intuizione sui nostri motociclisti e conducenti dagli incorporamenti appresi.

Confronto del modello di guida del conducente

Il primo esempio mostrerà come gli incorporamenti possono catturare in modo compatto informazioni ricche di dimensioni elevate. Come esercizio divertente, costruiamo un grafico che esplora i diversi modelli di posizione dei conducenti nella Bay Area.

L'input è un grafico con Driver e Gh6 come entità, e gli archi che collegano un driver e il pick-up di una corsa Gh6 per ogni corsa richiesta durante diversi mesi (cioè il periodo di addestramento degli incorporamenti). L'output è un incorporamento a 32 dimensioni per ogni posizione Gh6 e per ogni driver.

Con gli incorporamenti, abbiamo calcolato la somiglianza tra ogni coppia di driver e Gh6. In questo esempio, la somiglianza indicherebbe la frequenza con cui un conducente ha raccolto corse da una posizione Gh6. Più alto è il punteggio di somiglianza, più corse ha raccolto un conducente da quella posizione.

Abbiamo scelto due driver, driver A e B, e abbiamo calcolato il punteggio di somiglianza di ogni Gh6 con loro attraverso il prodotto scalare dei loro incorporamenti. La Figura 4 mostra le somiglianze di ogni Gh6 con Driver A e Driver B, rispettivamente con punteggi più alti con sfumature più scure.

Dai grafici di somiglianza, possiamo visualizzare chiaramente i distinti modelli di guida dei conducenti. Vediamo che il pilota A (pannello di sinistra) è un pilota di SF City . A volte guidano un po 'a sud per le corse nella zona della penisola o un po' a nord per le corse nella zona di North Bay, ma raramente vanno nelle aree di East Bay o South Bay.

Al contrario, Driver B (pannello destro) è principalmente un East Bay Driver che ha raccolto più corse nell'area di Fremont, dove si concentrano le sfumature più scure. A volte guidano verso l'area della penisola di South Bay attraverso i ponti, ma raramente vanno nell'area della città di San Francisco.

Questi interessanti schemi di corsa potrebbero richiedere un ampio istogramma di frequenze di corsa rispetto ai luoghi da descrivere. Con gli incorporamenti, siamo in grado di ottenere un'immagine molto ricca degli schemi di guida dei conducenti con solo un vettore a 32 dimensioni!

Modelli di corsa per tutta la settimana

Nel prossimo esempio, mostreremo come l'utilizzo delle funzionalità di incorporamento temporale può aiutare a scoprire relazioni e intuizioni nascoste che potrebbero non essere ovvie con semplici funzionalità temporali come l'ora del giorno o l'ora della settimana.

Abbiamo costruito un grafico con Driver e ora della settimana come entità e bordi che collegano un driver e un'ora della settimana per ogni corsa che il conducente prende che inizia durante quell'ora. L'output è stato un semplice incorporamento quadridimensionale per ogni ora della settimana e per ogni conducente. Abbiamo utilizzato solo vettori di incorporamento quadridimensionali poiché ci sono solo 168 entità dell'ora della settimana rispetto alle migliaia di Gh6 nell'esempio precedente. Con questo grafico, possiamo confrontare la somiglianza tra ogni ora della settimana e ogni altra ora della settimana e osservare i modelli di corsa durante la settimana.

Abbiamo scelto due orari di riferimento: sabato alle 20:00 e lunedì a mezzogiorno ora locale in tutte le regioni degli Stati Uniti e abbiamo calcolato il punteggio di somiglianza di ogni ora della settimana con loro. Queste due ore di riferimento sono state scelte perché rappresentano modelli di corsa molto distintivi.

Sul grafico a sinistra della Figura 5, la gobba poco prima di "x = Su" mostra che sabato 20:00 ha il punteggio di somiglianza più alto con se stesso, come previsto. Ciò che è interessante è che il prossimo orario più simile a sabato alle 20 sembra essere il venerdì alle 20, seguito dalle 20 di domenica. I prossimi più simili sono dal lunedì al giovedì alle 20:00, sebbene siano distintamente a un livello di somiglianza inferiore rispetto alle 20:00 di venerdì.

Quando il lunedì alle 12 è l'orario di riferimento emerge un quadro diverso. Il grafico a destra della Figura 5 è più simile al mezzogiorno dal lunedì al venerdì e meno simile al mezzogiorno del sabato o della domenica.

Cosa significa questo? Sulla base della nostra costruzione del grafico che include i conducenti e l'ora della settimana come entità, simili in questo caso possono essere interpretati in modo leggermente diverso. Un'interpretazione potrebbe essere che i conducenti che sono più simili a un'ora della settimana hanno dato più corse in quel momento.

Con un semplice contrasto di queste due trame, possiamo quasi individuare conducenti e gruppi di corse distintivi sulla piattaforma Lyft: i conducenti e le corse "dell'ora di festa" del fine settimana rispetto ai conducenti e le corse dell'"ora del pendolarismo" nei giorni feriali. Queste informazioni sono tutte rappresentate nei vettori a 4 dimensioni per ogni ora della settimana che possono essere facilmente inserite come input in un modello. Attraverso gli incorporamenti siamo in grado di catturare e trasmettere con eleganza questa relazione nascosta che ci saremmo persi se avessimo usato solo l'ora della settimana come caratteristica!

Qual è il prossimo

Dopo aver visto diverse applicazioni di incorporamento di successo, stiamo costruendo una piattaforma per consentire a molti modellatori di machine learning (ML) di Lyft di utilizzarli. L'approccio per costruire grafici di dati e incorporamenti è molto flessibile e può essere applicato per studiare le varie complessità del business del rideshare di Lyft. Le intuizioni scoperte possono aiutarci a comprendere i diversi modelli di guida, le dinamiche del mercato e, in ultima analisi, a creare prodotti e offerte di guida migliori per i nostri motociclisti e conducenti.

Nell'ambito di un'iniziativa della piattaforma Embeddings, sono supportati molti progetti di modellazione distinti per creare incorporamenti personalizzati e utilizzarli come funzionalità innovative nei modelli ML. Stiamo risolvendo contemporaneamente problemi con la qualità dei dati e delle funzionalità, la riqualificazione automatizzata, la governance, la conformità e l'infrastruttura di formazione per i nostri team supportati.

Abbiamo in programma di mantenere nuovi incorporamenti per le entità più interessanti nel mercato Lyft e renderli disponibili come funzionalità facilmente accessibili per molti casi d'uso comuni.

[1] Figura dalle diapositive delle lezioni del corso Stanford CS224W .