Co-Autoren: Javen Xu , Hakan Baba und Adriana Deneault

Einführung

Graph-Learning-Methoden können interessante Erkenntnisse liefern, die die zugrunde liegenden relationalen Strukturen erfassen. Graph-Learning-Methoden finden viele Branchenanwendungen in Bereichen wie Produkt- oder Inhaltsempfehlungssystemen und Netzwerkanalysen.

In diesem Beitrag diskutieren wir, wie wir bei Lyft Graph-Learning-Methoden verwenden, um Einbettungen zu generieren – eine kompakte Vektordarstellung hochdimensionaler Informationen. Wir werden interessante Einblicke in Mitfahrgelegenheiten teilen, die durch die Einbettung von Mitfahrern, Fahrern, Standorten und Zeiten gewonnen werden. Wie die Beispiele zeigen werden, können trainierte Einbettungen aus Diagrammen Informationen und Muster darstellen, die mit herkömmlichen, unkomplizierten Funktionen schwer zu erfassen sind.

Lyft-Daten und Einbettungen

Bei Lyft verfügen wir über halbstrukturierte Daten, die komplexe Interaktionen zwischen Fahrern, Fahrgästen, Standorten und Zeit erfassen. Wir können Diagramme erstellen, die diese Interaktionen darstellen (z. B. kann ein Diagramm erstellt werden, indem ein Fahrer mit allen von ihm besuchten Orten verknüpft wird). Aus diesen Diagrammen können wir Einbettungen generieren, um den gesamten Fahrverlauf eines Fahrers oder Fahrers prägnant darzustellen. Diese Einbettungen ermöglichen es uns, umfangreiche und vielfältige Informationen effizient in einer maschinenfreundlichen Darstellung zusammenzufassen.

Beispielsweise gibt es in der San Francisco Bay Area über 9.000 Geohash-6 (Gh6)-Standorte. Wenn wir den Fahrverlauf eines Fahrers in der Bay Area ohne Einbettungen beschreiben wollten, bräuchten wir ein Histogramm oder einen Vektor mit einer Länge von über 9.000, um ihn genau zu beschreiben. Der Vektor würde die Anzahl der Fahrten enthalten, die der Fahrer in jedem Gh6 begonnen hat, mit vielen Nullen, wenn der Fahrer in einigen Gh6 noch nie dabei war.

Mit Graph Learning sind wir in der Lage, einen niedrigerdimensionalen Einbettungsvektor zu trainieren, der die gleichen Informationen darstellt. Aufgrund der inhärenten Dimensionsreduzierung werden möglicherweise nicht die genauen Details erfasst, aber wie wir weiter unten in Lyft Ride Insights zeigen werden, sind gut trainierte Einbettungen in der Lage, das Gesamtbild des Reiseverlaufs eines Fahrers zu erfassen.

Ein weiterer Vorteil besteht darin, dass Einbettungen d -dimensionale Vektoren sind, die einzelne Punkte in einem d -dimensionalen Vektorraum beschreiben und diese Räume von verschiedenen definierten Entitäten gemeinsam genutzt werden können. Entitäten sind die Punkte oder Knoten im Eingabediagramm, die wir durch Einbetten von Vektoren darstellen möchten und die nach Entitätstypen gruppiert sind. Beispielsweise können wir zwei Einbettungsvektoren konstruieren, von denen einer eine Fahrerentität und einer eine Standortentität aus demselben Diagramm darstellt, wobei eine verbundene Kante im Diagramm bedeutet, dass dieser Fahrer diesen Ort besucht hat. Mit einer Ähnlichkeitsfunktion(im Problemaufbau definiert) können wir die beiden Einbettungsvektoren direkt vergleichen, indem wir einen Ähnlichkeitswert zwischen ihnen berechnen. In diesem Diagramm würde der Ähnlichkeitswert beschreiben, wie oft unser Fahrer diesen ausgewählten Ort besucht hat.

Während ein Diagramm viele verschiedene Entitätstypen (z. B. Fahrer, Standort, Fahrer) und Beziehungen (z. B. abgeholt, abgesetzt) ​​umfassen kann, können einfache Diagramme dennoch informativ sein. Wie unsere Beispiele zeigen werden, können diagrammbasierte Einbettungen auch mit nur zwei Entitätstypen und einem Beziehungstyp immer noch wertvolle Erkenntnisse liefern.

Methodik

Graphbasierte Einbettungen auf den Punkt gebracht

Ein Graph mit mehreren Entitäten wird erstellt, indem Entitäten als Knoten gezeichnet werden und Verbindungen (z. B. Kanten) zwischen Entitäten hergestellt werden, bei denen eine interpretierbare Beziehung besteht. Die Idee graphbasierter Einbettungen besteht darin, Knoten so zu kodieren, dass die Ähnlichkeit im Einbettungsraum (z. B. Skalarprodukt ) der Nähe im Diagramm nahekommt. Zwei Entitäten haben einen hohen Ähnlichkeitswert mit ihren Einbettungen, wenn sie entweder direkt im ursprünglichen Diagramm verbunden sind (d. h. „1-Grad“-Verbindungsabstand) oder einen sehr geringen Abstand haben (d. h. „2-Grad“-Verbindung).

Es gibt zwei Schlüsselkomponenten: 1) einen Encoder , der jeden Knoten einem niedrigdimensionalen Vektor zuordnet, und 2) eine Ähnlichkeitsfunktion , die angibt, wie die Beziehungen im Vektorraum den Beziehungen im ursprünglichen Netzwerk zugeordnet werden.

Wir können die Dimensionen des Einbettungsraums (dh des Ausgaberaums) im Trainingsprozess angeben. Durch die Wahl einer geeigneten Dimensionalität sind wir in der Lage, die komplexen Beziehungen zwischen Entitäten aus dem ursprünglichen Eingabediagramm in einem viel niedrigeren und kompakteren Vektorraum zu erfassen. Wir können sogar Abstandsberechnungen mit Vektorskalarprodukten im Einbettungsraum durchführen, um ein quantitatives Maß für die „Ähnlichkeit“ oder den „Abstand“ zwischen verschiedenen Entitäten zu erhalten.

Als Nächstes verwenden wir ein einfaches Lyft-Fahrdiagramm als Beispiel, um die Details des Einbettungstrainings zu veranschaulichen.

Fahrdiagramme bei Lyft und Embeddings Training

Bei Lyft sind wir daran interessiert, mehr über Fahrgäste, Fahrer und ihre Fahrpräferenzen in Bezug auf Faktoren wie Ort und Zeit zu erfahren.

Am Beispiel des Standorts können wir ein Diagramm wie in Abbildung 2 erstellen. Jeder Fahrer, Fahrer und Standort wird als separate Einheit dargestellt, und es werden Verbindungen gezogen, wenn ein Fahrer oder Fahrer eine Fahrt von einem bestimmten Standort aus begonnen hat.

Unser Trainingsalgorithmus basiert auf dem Pytorch BigGraph- Paket. Zu Beginn des Trainings geben wir die d- Dimensionen der Einbettungsvektoren an, die wir erhalten möchten, und der Algorithmus weist diesen d -dimensionalen Einbettungsvektoren Zufallswerte als Anfangsparameter zu. Als allgemeines Prinzip wählen wir eine höhere Ausgabeeinbettungsdimension, wenn der ursprüngliche Graph komplex ist und eine große Anzahl von Entitäten und kompliziert verbundene Kanten aufweist. Eine höhere Einbettungsdimension erfasst mehr Informationen aus dem Diagramm.

Das Ziel des Trainings besteht darin, d -dimensionale Einbettungsvektoren für jede Entität (dh jeden Knoten) zu lernen, sodass die berechnete Ähnlichkeit zwischen zwei beliebigen Entitäten deren Beziehung widerspiegelt. Beispielsweise hätten zwei Entitäten, die im Raum sehr nahe beieinander liegen, einen positiveren Ähnlichkeitswert als zwei weit entfernte Entitäten.

Während jedes Trainingszyklus wird für jede Entität jede mit der Entität im ursprünglichen Eingabediagramm verbundene Kante als positive (+) Instanz betrachtet, während der Algorithmus nach dem Zufallsprinzip negative (-) Instanzen aus den nicht verbundenen Entitäten abtastet. In unserem Fahrdiagramm würden die Beispiele wie in Abbildung 3 unten aussehen. Beachten Sie, dass in Abbildung 2 oben positiv beschriftete Kanten vorhanden sind, negativ beschriftete Kanten jedoch nicht.

Die Einbettungsvektoren für Entitäten werden mithilfe eines ausgewählten Komparators paarweise verglichen, um einen Ähnlichkeitswert zu generieren. Eine einfache Wahl ist die Kosinusähnlichkeit, die als Skalarprodukt zweier Vektoren berechnet wird.

Sobald die Bewertungen aller positiven und negativen Stichproben ermittelt wurden, aggregiert eine Verlustmetrik die Bewertungen zu einem einzigen Verlustwert pro Epoche, um das Lernen zu ermöglichen. Übliche Verlustfunktionen sind Ranking-Verlust, Logistikverlust und Softmax-Verlust .

Schließlich wird der Verlust mithilfe einer Adagrad- Optimierungsmethode minimiert, um alle Modellparameter zu aktualisieren.

Einblicke in Lyft Ride

Jetzt können wir interessante Erkenntnisse zeigen, die durch die Einbettung von Fahrdiagrammen gewonnen wurden. Ein kurzer Haftungsausschluss: Unsere Analyse konzentriert sich auf anonyme oder aggregierte Informationen und wir beabsichtigen nicht, aus den gelernten Einbettungen persönliche Merkmale oder Erkenntnisse über unsere Fahrer und Fahrer abzuleiten.

Vergleich des Fahrverhaltens der Fahrer

Das erste Beispiel zeigt, wie Einbettungen umfangreiche hochdimensionale Informationen kompakt erfassen können. Als unterhaltsame Übung erstellen wir eine Grafik, die verschiedene Standortmuster von Autofahrern in der Bay Area untersucht.

Die Eingabe ist ein Diagramm mit Fahrer und Gh6 als Entitäten und Kanten, die einen Fahrer und den Abholer Gh6 einer Fahrt für jede angeforderte Fahrt über einen Zeitraum von mehreren Monaten (d. h. der Einbettungstrainingszeit) verbinden. Die Ausgabe ist eine 32-dimensionale Einbettung für jeden Gh6-Standort und für jeden Treiber.

Mit den Einbettungen haben wir die Ähnlichkeit zwischen jedem Treiberpaar und Gh6 berechnet. In diesem Beispiel würde die Ähnlichkeit darauf hinweisen, wie häufig ein Fahrer Fahrten von einem Gh6-Standort übernommen hat. Je höher der Ähnlichkeitswert ist, desto mehr Fahrten hat ein Fahrer an diesem Ort übernommen.

Wir haben zwei Treiber ausgewählt – Treiber A und B – und den Ähnlichkeitswert jedes Gh6 mit ihnen anhand des Skalarprodukts ihrer Einbettungen berechnet. Abbildung 4 zeigt die Ähnlichkeiten jedes Gh6 mit Fahrer A und Fahrer B, wobei höhere Werte dunklere Farbtöne aufweisen.

Anhand der Ähnlichkeitsdiagramme können wir die unterschiedlichen Fahrmuster der Fahrer klar visualisieren. Wir sehen, dass Fahrer A (linkes Feld) ein SF City Driver ist . Manchmal fahren sie für Fahrten in der Gegend um die Halbinsel etwas weiter nach Süden oder für Fahrten in die Gegend um die North Bay etwas nach Norden, aber sie fahren selten in die Gebiete East Bay oder South Bay.

Im Gegensatz dazu ist Fahrer B (rechtes Feld) in erster Linie ein East Bay-Fahrer , der mehr Fahrten in der Gegend von Fremont unternommen hat, wo sich die dunkelsten Farbtöne konzentrieren. Manchmal fahren sie über die Brücken in das Halbinselgebiet von South Bay, selten jedoch in das Stadtgebiet von San Francisco.

Diese interessanten Fahrmuster könnten ein großes Histogramm der Fahrhäufigkeiten in Bezug auf die zu beschreibenden Orte erfordern. Mit Einbettungen sind wir in der Lage, mit nur einem 32-dimensionalen Vektor ein sehr detailliertes Bild des Fahrverhaltens der Fahrer zu erhalten!

Fahrmuster während der Woche

Im nächsten Beispiel zeigen wir, wie die Verwendung zeitlicher Einbettungsfunktionen dazu beitragen kann, verborgene Zusammenhänge und Erkenntnisse aufzudecken, die bei einfachen Zeitfunktionen wie Tageszeit oder Wochenstunde möglicherweise nicht offensichtlich sind.

Wir haben ein Diagramm mit dem Fahrer und der Stunde der Woche als Entitäten erstellt und Kanten, die einen Fahrer und eine Stunde der Woche für jede Fahrt verbinden, die der Fahrer in dieser Stunde in Angriff nimmt. Die Ausgabe war eine einfache vierdimensionale Einbettung für jede Stunde der Woche und für jeden Fahrer. Wir haben nur vierdimensionale Einbettungsvektoren verwendet, da es im Vergleich zu Tausenden von Gh6s im vorherigen Beispiel nur 168 Stunden-der-Woche-Entitäten gibt. Mit diesem Diagramm können wir die Ähnlichkeit zwischen jeder Stunde der Woche und jeder zweiten Stunde der Woche vergleichen und die Fahrmuster im Laufe der Woche beobachten.

Wir haben zwei Referenzstunden ausgewählt – Samstag um 20 Uhr und Montag um 12 Uhr Ortszeit in allen Regionen der USA – und mit ihnen den Ähnlichkeitswert jeder Stunde der Woche berechnet. Diese beiden Referenzstunden wurden ausgewählt, weil sie sehr unterschiedliche Fahrmuster darstellen.

Im linken Diagramm von Abbildung 5 zeigt der Buckel kurz vor „x = Su“, dass Samstag 20 Uhr den höchsten Ähnlichkeitswert mit sich selbst aufweist, was erwartet wird. Interessant ist, dass die Stunden, die dem Samstag um 20 Uhr am nächsten kommen, anscheinend Freitag um 20 Uhr sind, gefolgt von 20 Uhr am Sonntag. Die nächstähnlichsten sind Montag bis Donnerstag um 20:00 Uhr, obwohl sie deutlich weniger ähnlich sind als freitags um 20:00 Uhr.

Wenn Montag um 12 Uhr als Referenzzeit gilt, ergibt sich ein anderes Bild. Das rechte Diagramm in Abbildung 5 ähnelt am meisten Montag bis Freitag um 12 Uhr und weniger Samstag oder Sonntag um 12 Uhr.

Was bedeutet das? Basierend auf unserer Konstruktion des Diagramms, das Fahrer und Wochenstunden als Einheiten umfasst, kann Ähnliches in diesem Fall etwas anders interpretiert werden. Eine Interpretation könnte sein, dass Fahrer, die einer Wochenstunde ähnlicher sind, zu diesem Zeitpunkt mehr Fahrten unternommen haben.

Mit einer einfachen Gegenüberstellung dieser beiden Darstellungen können wir fast unterschiedliche Fahrer- und Fahrgruppen auf der Lyft-Plattform erkennen – die „Party-Hour“-Fahrer und -Fahrten am Wochenende im Vergleich zu den „Pendelstunden“-Fahrern und -Fahrten an Wochentagen. Diese Informationen werden alle in den 4-dimensionalen Vektoren für jede Stunde der Woche dargestellt, die problemlos als Eingabe in ein Modell eingespeist werden können. Durch Einbettungen sind wir in der Lage, diese verborgene Beziehung, die uns entgangen wäre, wenn wir nur die Stunde der Woche als Feature verwendet hätten, auf elegante Weise einzufangen und zu vermitteln!

Was kommt als nächstes

Nachdem wir mehrere erfolgreiche Anwendungen von Einbettungen gesehen haben, bauen wir eine Plattform auf, um vielen Modellierern für maschinelles Lernen (ML) bei Lyft die Möglichkeit zu geben, diese zu nutzen. Der Ansatz zum Erstellen von Datendiagrammen und zum Erstellen von Einbettungen ist sehr flexibel und kann zur Untersuchung der verschiedenen Feinheiten des Mitfahrgeschäfts von Lyft angewendet werden. Die gewonnenen Erkenntnisse können uns helfen, unterschiedliche Fahrmuster und Marktdynamiken zu verstehen und letztendlich bessere Produkte und Fahrangebote für unsere Fahrer und Fahrer zu entwickeln.

Im Rahmen einer Embeddings-Plattform-Initiative werden viele verschiedene Modellierungsprojekte unterstützt, um benutzerdefinierte Einbettungen zu erstellen und diese als innovative Funktionen in ML-Modellen zu verwenden. Gleichzeitig lösen wir Probleme mit der Daten- und Funktionsqualität, der automatisierten Umschulung, der Governance, der Compliance und der Schulungsinfrastruktur für unsere unterstützten Teams.

Wir planen, neue Einbettungen für die interessantesten Entitäten auf dem Lyft-Marktplatz beizubehalten und sie als leicht zugängliche Funktionen für viele gängige Anwendungsfälle verfügbar zu machen.

[1] Abbildung aus den Vorlesungsfolien des Stanford CS224W- Kurses.