Co-auteurs : Javen Xu , Hakan Baba et Adriana Deneault

Introduction

Les méthodes d'apprentissage de graphes peuvent révéler des informations intéressantes qui capturent les structures relationnelles sous-jacentes. Les méthodes d'apprentissage de graphes ont de nombreuses applications industrielles dans des domaines tels que les systèmes de recommandation de produits ou de contenu et l'analyse de réseau.

Dans cet article, nous expliquons comment nous utilisons les méthodes d'apprentissage de graphes chez Lyft pour générer des incorporations - représentation vectorielle compacte d'informations de grande dimension. Nous partagerons des informations intéressantes sur le covoiturage découvertes par les intégrations de passagers, de conducteurs, de lieux et de temps. Comme les exemples le montreront, les intégrations formées à partir de graphiques peuvent représenter des informations et des modèles difficiles à capturer avec des fonctionnalités traditionnelles et simples.

Données et intégrations Lyft

Chez Lyft, nous disposons de données semi-structurées capturant les interactions complexes entre les conducteurs, les passagers, les lieux et le temps. Nous pouvons construire des graphes représentant ces interactions (par exemple, un graphe peut être formé en reliant un cycliste à tous les lieux qu'il a visités). À partir de ces graphiques, nous pouvons générer des intégrations pour exprimer succinctement l'historique de conduite complet d'un pilote ou d'un conducteur. Ces incorporations nous permettent de résumer efficacement des informations vastes et variées dans une représentation conviviale pour les machines.

Par exemple, il existe plus de 9 000 emplacements de niveau Geohash-6 (Gh6) dans la région de la baie de San Francisco. Si nous voulions décrire l'historique de conduite d'un conducteur dans la région de la baie sans incorporations, nous aurions besoin d'un histogramme ou d'un vecteur de longueur supérieure à 9 000 pour le décrire avec précision. Le vecteur contiendrait le nombre de trajets que le conducteur a commencés dans chaque Gh6, avec beaucoup de zéros si le conducteur n'a jamais été dans certains Gh6.

Avec l'apprentissage de graphes, nous sommes en mesure de former un vecteur d'incorporations de dimension inférieure qui représente la même information. Il se peut qu'il ne capture pas les détails exacts en raison de la réduction de dimension inhérente, mais comme nous le montrerons dans Lyft Ride Insights ci-dessous, des intégrations bien formées sont capables de capturer l'image globale de l'historique de voyage d'un conducteur.

Un autre avantage est que les plongements sont des vecteurs d -dimensionnels qui décrivent des points uniques dans un espace vectoriel d -dimensionnel et ces espaces peuvent être partagés par différentes entités définies. Les entités sont les points, ou nœuds, dans le graphe d'entrée que nous voulons représenter en incorporant des vecteurs et sont regroupés par types d'entités. Par exemple, nous pouvons construire deux vecteurs d'incorporation, l'un représentant une entité de motard et l'autre représentant une entité de lieu du même graphe, où une arête connectée dans le graphe signifie que ce motard a visité cet endroit. Avec une fonction de similarité(défini dans la configuration du problème), nous pouvons comparer directement les deux vecteurs d'intégration en calculant un score de similarité entre eux. Dans ce graphique, le score de similarité décrirait la fréquence à laquelle notre passager a visité cet endroit choisi.

Bien qu'un graphique puisse incorporer de nombreux types d'entités différents (par exemple, passager, emplacement, conducteur) et relations (par exemple, pris en charge, déposé), des graphiques simples peuvent toujours être informatifs. Comme nos exemples le montreront, même avec seulement deux types d'entités et un type de relation, les incorporations basées sur des graphes peuvent toujours donner des informations précieuses.

Méthodologie

Les représentations vectorielles continues basées sur des graphes en bref

Un graphe multi-entités est construit en dessinant des entités sous forme de nœuds et en établissant des connexions (c'est-à-dire des arêtes) entre des entités où il existe une relation interprétable. L'idée des intégrations basées sur des graphes est d'encoder les nœuds de sorte que la similarité dans l'espace d'intégration (par exemple, le produit scalaire ) se rapproche de la proximité dans le graphe. Deux entités ont un score de similarité élevé avec leurs plongements si elles sont directement connectées dans le graphe d'origine (c'est-à-dire une distance de connexion de « 1 degré »), ou ont une distance très proche (c'est-à-dire une connexion de « 2 degrés »).

Il existe deux composants clés : 1) un encodeur qui mappe chaque nœud sur un vecteur de faible dimension et 2) une fonction de similarité qui spécifie comment les relations dans l'espace vectoriel correspondent aux relations dans le réseau d'origine.

Nous pouvons spécifier les dimensions de l'espace d'intégration (c'est-à-dire de sortie) dans le processus d'apprentissage. En choisissant une dimensionnalité appropriée, nous sommes en mesure de capturer les relations complexes entre les entités à partir du graphique d'entrée d'origine dans un espace vectoriel dimensionnel beaucoup plus faible et compact. Nous pouvons même faire des calculs de distance avec des produits scalaires vectoriels dans l'espace des plongements pour obtenir une mesure quantitative de la « similarité » ou de la « distance » entre différentes entités.

Ensuite, nous utiliserons un simple graphique de conduite Lyft comme exemple pour illustrer les détails de la formation aux intégrations.

Graphiques de conduite à Lyft et formation aux intégrations

Chez Lyft, nous souhaitons en savoir plus sur les passagers, les chauffeurs et leurs préférences de conduite en fonction de facteurs tels que l'emplacement et l'heure.

En prenant l'emplacement comme exemple, nous pouvons construire un graphique comme la figure 2. Chaque passager, conducteur et emplacement est représenté comme une entité distincte, et des connexions sont dessinées là où un conducteur ou un conducteur a commencé un trajet à partir d'un certain emplacement.

Notre algorithme de formation s'étend du package Pytorch BigGraph . Au début de la formation, nous spécifions les dimensions d des vecteurs d'intégration que nous voulons obtenir, et l'algorithme attribue des valeurs aléatoires à ces vecteurs d'intégration d -dimensionnels comme paramètres initiaux. En règle générale, nous choisissons une dimension d'intégration de sortie plus élevée si le graphe d'origine est complexe avec un grand nombre d'entités et des arêtes connectées complexes. Une dimension d'intégration plus élevée capturera plus d'informations à partir du graphique.

Le but de la formation est d'apprendre des vecteurs d'intégration d -dimensionnels pour chaque entité (c'est-à-dire un nœud) de sorte que la similarité calculée entre deux entités quelconques reflète leur relation. Par exemple, deux entités très proches dans l'espace auraient un score de similarité plus positif que deux entités éloignées.

Au cours de chaque cycle de formation, pour chaque entité, chaque arête connectée à l'entité dans le graphique d'entrée d'origine est considérée comme une instance positive (+), tandis que l'algorithme échantillonne de manière aléatoire à partir des entités non connectées pour les instances négatives (-). Dans notre graphique de trajet, les échantillons ressembleraient à la figure 3 ci-dessous. Remarquez comment les arêtes étiquetées positives existent dans la figure 2 ci-dessus, mais pas les arêtes étiquetées négatives.

Les vecteurs d'intégration pour les entités sont comparés par paires à l'aide d'un comparateur choisi pour générer un score de similarité. Un choix simple est la similarité cosinus, qui est calculée comme le produit scalaire de deux vecteurs.

Une fois que les scores de tous les échantillons positifs et négatifs ont été déterminés, une métrique de perte agrège les scores en une seule valeur de perte par époque pour permettre l'apprentissage. Les fonctions de perte courantes sont la perte de classement, la perte logistique et la perte softmax .

Enfin, la perte est minimisée en utilisant une méthode d'optimisation Adagrad pour mettre à jour tous les paramètres du modèle.

Informations sur les trajets Lyft

Nous pouvons maintenant montrer des informations intéressantes révélées par les incorporations de graphes de conduite. Un avertissement rapide que notre analyse se concentre sur des informations anonymes ou agrégées et que nous ne visons pas à tirer des caractéristiques personnelles ou des informations sur nos passagers et conducteurs à partir des intégrations apprises.

Comparaison des habitudes de conduite des conducteurs

Le premier exemple montrera comment les plongements peuvent capturer de manière compacte des informations riches et de grande dimension. En tant qu'exercice amusant, nous construisons un graphique explorant différents modèles de localisation des conducteurs dans la région de la baie.

L'entrée est un graphe avec Driver et Gh6 comme entités, et des arêtes connectant un conducteur et le pick-up d'un trajet Gh6 pour chaque trajet demandé pendant plusieurs mois (c'est-à-dire la période de formation des incorporations). La sortie est une intégration en 32 dimensions pour chaque emplacement Gh6 et pour chaque pilote.

Avec les embeddings, nous avons calculé la similarité entre chaque paire de driver et Gh6. Dans cet exemple, la similarité indiquerait la fréquence à laquelle un conducteur a pris des courses à partir d'un emplacement Gh6. Plus le score de similarité est élevé, plus un conducteur a effectué de trajets à cet endroit.

Nous avons choisi deux pilotes - les pilotes A et B, et avons calculé le score de similarité de chaque Gh6 avec eux via le produit scalaire de leurs intégrations. La figure 4 montre les similitudes de chaque Gh6 avec le pilote A et le pilote B, respectivement avec des scores plus élevés ayant des nuances plus sombres.

À partir des tracés de similarité, nous pouvons clairement visualiser les modèles de conduite distincts des conducteurs. Nous voyons que Driver A (panneau de gauche) est un SF City Driver . Ils conduisent parfois un peu vers le sud pour des trajets dans la région de la péninsule ou un peu vers le nord pour des trajets dans la région de North Bay, mais ils se rendent rarement dans les régions d'East Bay ou de South Bay.

En revanche, le conducteur B (panneau de droite) est principalement un conducteur d'East Bay qui a effectué plus de trajets dans la région de Fremont, où se concentrent les nuances les plus sombres. Ils se rendent parfois dans la péninsule de South Bay via les ponts, mais se rendent rarement dans la ville de San Francisco.

Ces modèles de conduite intéressants pourraient nécessiter un grand histogramme des fréquences de conduite par rapport aux emplacements à décrire. Avec les incorporations, nous sommes en mesure d'obtenir une image très riche des modèles de conduite des conducteurs avec seulement un vecteur à 32 dimensions !

Modèles de conduite tout au long de la semaine

Dans l'exemple suivant, nous montrerons comment l'utilisation de fonctionnalités d'intégration temporelle peut aider à découvrir des relations et des informations cachées qui peuvent ne pas être évidentes avec des fonctionnalités temporelles simples telles que l'heure du jour ou l'heure de la semaine.

Nous avons construit un graphique avec le conducteur et l'heure de la semaine comme entités, et les arêtes reliant un conducteur et une heure de la semaine pour chaque trajet que le conducteur prend et qui commence pendant cette heure. Le résultat était une simple incorporation en quatre dimensions pour chaque heure de la semaine et pour chaque conducteur. Nous n'avons utilisé que des vecteurs d'intégration à quatre dimensions car il n'y a que 168 entités d'heure de la semaine par rapport aux milliers de Gh6 dans l'exemple précédent. Avec ce graphique, nous pouvons comparer la similarité entre chaque heure de la semaine et toutes les autres heures de la semaine et observer les habitudes de conduite tout au long de la semaine.

Nous avons choisi deux heures de référence – le samedi à 20 h et le lundi à midi, heure locale, dans toutes les régions des États-Unis et avons calculé le score de similarité de chaque heure de la semaine avec elles. Ces deux heures de référence sont choisies parce qu'elles représentent des habitudes de conduite très particulières.

Sur le graphique de gauche de la figure 5, la bosse un peu avant « x = Su » montre que samedi 20 h a le score de similarité le plus élevé avec lui-même, ce qui est attendu. Ce qui est intéressant, c'est que les prochaines heures les plus similaires au samedi 20 h semblent être le vendredi 20 h suivi de 20 h le dimanche. Les prochains plus similaires sont du lundi au jeudi à 20 heures, bien qu'ils soient distinctement à un niveau de similitude inférieur à 20 heures le vendredi.

Lorsque le lundi à 12 heures est l'heure de référence, une image différente se dessine. Le tracé de droite de la figure 5 est le plus similaire au lundi au vendredi à midi, et moins similaire au samedi ou au dimanche à midi.

Qu'est-ce que cela signifie? Sur la base de notre construction du graphique qui inclut les conducteurs et l'heure de la semaine en tant qu'entités, similaire dans ce cas peut être interprété légèrement différemment. Une interprétation pourrait être que les conducteurs qui se rapprochent davantage d'une heure de la semaine ont effectué plus de trajets à ce moment-là.

Avec un simple contraste de ces deux parcelles, nous pouvons presque sélectionner des groupes distincts de conducteurs et de trajets sur la plate-forme Lyft – les conducteurs et les trajets « fête » du week-end par rapport aux conducteurs et trajets « heure de trajet » en semaine. Ces informations sont toutes représentées dans les vecteurs à 4 dimensions pour chaque heure de la semaine qui peuvent être facilement introduites en entrée dans un modèle. Grâce aux intégrations, nous sommes en mesure de capturer et de transmettre avec élégance cette relation cachée que nous aurions manquée si nous n'avions utilisé que l'heure de la semaine comme fonctionnalité !

Et après

Après avoir vu plusieurs applications réussies d'intégrations, nous construisons une plate-forme pour permettre à de nombreux modélisateurs d'apprentissage automatique (ML) de Lyft de les utiliser. L'approche pour construire des graphiques de données et créer des incorporations est très flexible et peut être appliquée pour étudier les diverses complexités de l'activité de covoiturage Lyft. Les informations découvertes peuvent nous aider à comprendre les différents modèles de conduite, la dynamique du marché et, en fin de compte, à créer de meilleurs produits et offres de conduite pour nos passagers et chauffeurs.

Dans le cadre d'une initiative Embeddings Platform, de nombreux projets de modélisation distincts sont pris en charge pour créer des incorporations personnalisées et les utiliser comme fonctionnalités innovantes dans les modèles ML. Nous résolvons simultanément les problèmes de qualité des données et des fonctionnalités, le recyclage automatisé, la gouvernance, la conformité et l'infrastructure de formation pour nos équipes supportées.

Nous prévoyons de maintenir de nouvelles intégrations pour les entités les plus intéressantes du marché Lyft et de les rendre disponibles en tant que fonctionnalités facilement accessibles pour de nombreux cas d'utilisation courants.

[1] Figure tirée des diapositives du cours Stanford CS224W .