Współautorzy: Javen Xu , Hakan Baba i Adriana Deneault

Wprowadzenie

Metody uczenia się na wykresach mogą ujawnić interesujące spostrzeżenia, które uchwycą podstawowe struktury relacyjne. Metody uczenia się na wykresach mają wiele zastosowań branżowych w takich obszarach, jak systemy rekomendacji produktów lub treści oraz analiza sieci.

W tym poście omawiamy, w jaki sposób wykorzystujemy metody uczenia się grafów w Lyft do generowania osadzania — zwartej reprezentacji wektorowej wielowymiarowych informacji. Będziemy dzielić się interesującymi spostrzeżeniami na temat wspólnych przejazdów, uzyskanymi dzięki osadzeniu pasażerów, kierowców, lokalizacji i czasu. Jak pokażą przykłady, wytrenowane osadzenie z wykresów może reprezentować informacje i wzorce, które trudno uchwycić za pomocą tradycyjnych, prostych funkcji.

Dane Lyft i osadzania

W Lyft mamy częściowo ustrukturyzowane dane rejestrujące złożone interakcje między kierowcami, pasażerami, lokalizacjami i czasem. Możemy konstruować wykresy przedstawiające te interakcje (np. wykres można utworzyć łącząc jeźdźca ze wszystkimi odwiedzonymi przez niego lokalizacjami). Na podstawie tych wykresów możemy wygenerować osadzanie, aby zwięźle przedstawić całą historię jazdy rowerzysty lub kierowcy. Te osadzenia pozwalają nam skutecznie streszczać obszerne i różnorodne informacje w postaci przyjaznej maszynie.

Na przykład w rejonie Zatoki San Francisco znajduje się ponad 9000 lokalizacji na poziomie Geohash-6 (Gh6). Gdybyśmy chcieli opisać historię jazdy kierowcy w Bay Area bez osadzania, potrzebowalibyśmy histogramu lub wektora o długości ponad 9000, aby dokładnie to opisać. Wektor zawierałby liczbę przejazdów, które kierowca rozpoczął w każdym Gh6, z dużą ilością zer, jeśli kierowca nigdy nie był w niektórych Gh6.

Dzięki uczeniu się grafów jesteśmy w stanie wytrenować wektor osadzania o niższych wymiarach, który reprezentuje te same informacje. Może nie uchwycić dokładnych szczegółów ze względu na nieodłączną redukcję wymiarów, ale jak pokażemy w Lyft Ride Insights poniżej, dobrze wyszkolone osadzanie jest w stanie uchwycić ogólny obraz historii podróży kierowcy.

Inną korzyścią jest to, że osadzania są d -wymiarowymi wektorami, które opisują pojedyncze punkty w d -wymiarowej przestrzeni wektorowej, a te przestrzenie mogą być współużytkowane przez różne zdefiniowane jednostki. Jednostki to punkty lub węzły na grafie wejściowym, które mają być reprezentowane przez osadzone wektory i są pogrupowane według typów jednostek. Na przykład, możemy skonstruować dwa wektory osadzania, jeden reprezentujący jednostkę jeźdźca, a drugi reprezentujący jednostkę lokalizacji z tego samego wykresu, gdzie połączona krawędź na wykresie oznacza, że ​​ten jeździec odwiedził to miejsce. Z funkcją podobieństwa(zdefiniowany w konfiguracji problemu), możemy bezpośrednio porównać dwa wektory osadzania, obliczając między nimi wynik podobieństwa. Na tym wykresie wynik podobieństwa opisywałby, jak często nasz jeździec odwiedzał wybraną lokalizację.

Podczas gdy wykres może zawierać wiele różnych typów jednostek (np. pasażer, lokalizacja, kierowca) i relacji (np. odebranie, odwiezienie), proste wykresy mogą nadal zawierać informacje. Jak pokażą nasze przykłady, nawet przy dwóch typach encji i jednym typie relacji osadzanie oparte na wykresach może nadal dostarczać cennych informacji.

Metodologia

Osadzenia oparte na wykresach w pigułce

Graf wieloobiektowy jest konstruowany przez rysowanie jednostek jako węzłów i tworzenie połączeń (tj. krawędzi) między jednostkami, w których istnieje dająca się interpretować zależność. Ideą osadzania opartego na grafach jest kodowanie węzłów w taki sposób, aby podobieństwo w przestrzeni osadzania (np. iloczyn skalarny ) było zbliżone do bliskości na grafie. Dwa obiekty mają wysoki wynik podobieństwa z ich osadzaniami, jeśli są albo bezpośrednio połączone na oryginalnym wykresie (tj. odległość połączenia „1 stopień”), albo mają bardzo bliską odległość (tj. połączenie „2 stopnie”).

Istnieją dwa kluczowe komponenty: 1) koder , który odwzorowuje każdy węzeł na niskowymiarowy wektor i 2) funkcja podobieństwa , która określa, w jaki sposób relacje w przestrzeni wektorowej odwzorowują relacje w oryginalnej sieci.

W procesie uczenia możemy określić wymiary przestrzeni osadzania (czyli wyjścia). Wybierając odpowiednią wymiarowość, jesteśmy w stanie uchwycić skomplikowane relacje między elementami z oryginalnego grafu wejściowego w znacznie niższej i zwartej wymiarowej przestrzeni wektorowej. Możemy nawet wykonać obliczenia odległości za pomocą wektorowych iloczynów skalarnych w przestrzeni osadzania, aby uzyskać ilościową miarę „podobieństwa” lub „odległości” między różnymi obiektami.

Następnie użyjemy prostego wykresu jazdy Lyft jako przykładu, aby zilustrować szczegóły treningu osadzania.

Wykresy jazdy na szkoleniu Lyft i Embeddings

W Lyft jesteśmy zainteresowani poznawaniem pasażerów, kierowców i ich preferencji dotyczących jazdy w odniesieniu do czynników takich jak lokalizacja i czas.

Biorąc jako przykład lokalizację, możemy skonstruować wykres taki jak na rysunku 2. Każdy pasażer, kierowca i lokalizacja są reprezentowane jako oddzielna jednostka, a połączenia są rysowane tam, gdzie pasażer lub kierowca rozpoczął jazdę z określonej lokalizacji.

Nasz algorytm szkoleniowy wywodzi się z pakietu Pytorch BigGraph . Na początku uczenia określamy d wymiarów wektorów osadzania, które chcemy uzyskać, a algorytm przypisuje losowe wartości tym d -wymiarowym wektorom osadzania jako parametry początkowe. Zasadniczo wybieramy wyższy wymiar osadzania danych wyjściowych, jeśli oryginalny graf jest złożony z dużą liczbą elementów i skomplikowanymi połączonymi krawędziami. Wyższy wymiar osadzania przechwytuje więcej informacji z wykresu.

Celem szkolenia jest poznanie d -wymiarowych wektorów osadzania dla każdej jednostki (tj. węzła) w taki sposób, aby obliczone podobieństwo między dowolnymi dwoma jednostkami odzwierciedlało ich związek. Na przykład dwa obiekty, które są bardzo blisko w przestrzeni, miałyby bardziej pozytywny wynik podobieństwa niż dwa oddalone obiekty.

Podczas każdego cyklu szkoleniowego, dla każdej jednostki, każda krawędź połączona z jednostką w oryginalnym grafie wejściowym jest uważana za instancję dodatnią (+), podczas gdy algorytm losowo pobiera próbki z niepowiązanych jednostek pod kątem instancji ujemnych (-). Na naszym wykresie jazdy próbki będą wyglądać jak na rysunku 3 poniżej. Zwróć uwagę, że krawędzie z etykietami dodatnimi istnieją na rysunku 2 powyżej, ale krawędzie z etykietami ujemnymi nie.

Wektory osadzania dla jednostek są porównywane parami przy użyciu wybranego komparatora w celu wygenerowania wyniku podobieństwa. Prostym wyborem jest podobieństwo cosinusowe, które jest obliczane jako iloczyn skalarny dwóch wektorów.

Po określeniu wyników wszystkich próbek pozytywnych i negatywnych, metryka strat agreguje wyniki w jedną wartość straty na epokę, aby umożliwić uczenie się. Typową funkcją strat jest strata rankingowa, strata logistyczna i strata softmax .

Wreszcie, strata jest minimalizowana przy użyciu metody optymalizacji Adagrad w celu aktualizacji wszystkich parametrów modelu.

Informacje o jeździe Lyft

Teraz możemy pokazać interesujące spostrzeżenia, które wynikają z ujawnionych osadzeń wykresów. Krótkie zastrzeżenie, że nasza analiza koncentruje się na anonimowych lub zagregowanych informacjach i nie naszym celem jest czerpanie jakichkolwiek cech osobistych ani spostrzeżeń na temat naszych jeźdźców i kierowców na podstawie wyuczonych osadzeń.

Porównanie wzorców jazdy kierowcy

Pierwszy przykład pokaże, w jaki sposób osadzanie może w zwarty sposób uchwycić bogate, wielowymiarowe informacje. W ramach zabawy tworzymy wykres przedstawiający różne wzorce lokalizacji kierowców w rejonie zatoki.

Dane wejściowe to wykres z Driver i Gh6 jako jednostkami oraz krawędziami łączącymi kierowcę i pickupa Gh6 dla każdego żądanego przejazdu w czasie kilku miesięcy (tj. okresu szkolenia osadzania). Dane wyjściowe to 32-wymiarowe osadzanie dla każdej lokalizacji Gh6 i dla każdego sterownika.

Dzięki osadzeniom obliczyliśmy podobieństwo między każdą parą sterowników a Gh6. W tym przykładzie podobieństwo oznaczałoby, jak często kierowca odbierał przejazdy z lokalizacji Gh6. Im wyższy wynik podobieństwa, tym więcej przejazdów odebrał kierowca z tej lokalizacji.

Wybraliśmy dwóch kierowców — kierowcę A i B, i obliczyliśmy wynik podobieństwa każdego Gh6 z nimi za pomocą iloczynu skalarnego ich osadzania. Rysunek 4 pokazuje podobieństwa każdego Gh6 odpowiednio do Kierowcy A i Kierowcy B, z wyższymi wynikami mającymi ciemniejsze odcienie.

Z wykresów podobieństwa możemy wyraźnie zwizualizować różne wzorce jazdy kierowców. Widzimy, że kierowca A (lewy panel) jest kierowcą SF City . Czasami jeżdżą trochę na południe, aby przejechać się w rejonie Półwyspu lub trochę na północ, aby przejechać się w rejonie North Bay, ale rzadko jeżdżą do obszarów East Bay lub South Bay.

Natomiast kierowca B (prawy panel) to przede wszystkim kierowca z East Bay , który odbył więcej przejażdżek w rejonie Fremont, gdzie koncentrują się najciemniejsze odcienie. Czasami jeżdżą mostami do obszaru półwyspu South Bay, ale rzadko jadą do obszaru miasta San Francisco.

Te interesujące wzorce jazdy mogą wymagać dużego histogramu częstotliwości jazdy w odniesieniu do lokalizacji do opisania. Dzięki osadzeniom jesteśmy w stanie uzyskać bardzo bogaty obraz wzorców jazdy kierowców za pomocą zaledwie 32-wymiarowego wektora!

Wzorce jazdy przez cały tydzień

W następnym przykładzie pokażemy, jak użycie funkcji osadzania czasowego może pomóc w odkryciu ukrytych relacji i spostrzeżeń, które mogą nie być oczywiste w przypadku prostych funkcji czasowych, takich jak godzina dnia lub godzina tygodnia.

Skonstruowaliśmy wykres z kierowcą i godziną tygodnia jako jednostkami oraz krawędziami łączącymi kierowcę i godzinę w tygodniu dla każdego przejazdu, który kierowca odbiera i który rozpoczyna się w tej godzinie. Dane wyjściowe były prostym czterowymiarowym osadzeniem dla każdej godziny tygodnia i dla każdego kierowcy. Użyliśmy tylko czterowymiarowych wektorów osadzania, ponieważ w poprzednim przykładzie jest tylko 168 jednostek godzinowych w tygodniu w porównaniu z tysiącami Gh6. Za pomocą tego wykresu możemy porównać podobieństwo między każdą godziną tygodnia a każdą inną godziną tygodnia i obserwować wzorce jazdy w ciągu tygodnia.

Wybraliśmy dwie godziny referencyjne — sobotę o 20:00 i poniedziałek w południe czasu lokalnego we wszystkich regionach w USA i obliczyliśmy z nimi wynik podobieństwa każdej godziny w tygodniu. Te dwie godziny referencyjne zostały wybrane, ponieważ reprezentują bardzo charakterystyczne wzorce jazdy.

Na lewym wykresie ryciny 5 garb nieco przed „x = Su” pokazuje, że sobota o godzinie 20:00 ma najwyższy wynik podobieństwa do siebie, czego można się spodziewać. Co ciekawe, najbliższe najbardziej zbliżone godziny do soboty 20:00 to piątek 20:00, a następnie 20:00 w niedzielę. Kolejne najbardziej podobne są od poniedziałku do czwartku o 20:00, chociaż wyraźnie mają niższy poziom podobieństwa niż 20:00 w piątek.

Gdy poniedziałek o godzinie 12:00 jest czasem odniesienia, wyłania się inny obraz. Prawy wykres na rycinie 5 jest najbardziej podobny do południa od poniedziałku do piątku, a mniej do soboty lub niedzieli w południe.

Co to znaczy? Opierając się na naszej konstrukcji wykresu, który obejmuje kierowców i godziny tygodnia jako jednostki, podobne w tym przypadku mogą być interpretowane nieco inaczej. Interpretacją może być to, że kierowcy, którzy są bardziej podobni do godziny w tygodniu, wykonali w tym czasie więcej przejazdów.

Dzięki prostemu kontrastowi tych dwóch wykresów możemy prawie wybrać charakterystyczne grupy kierowców i kierowców na platformie Lyft — weekendowi kierowcy i przejażdżki „w godzinach imprezowych” vs. kierowcy i przejażdżki w dni powszednie „w godzinach dojazdów”. Wszystkie te informacje są reprezentowane w 4-wymiarowych wektorach dla każdej godziny tygodnia, które można łatwo wprowadzić jako dane wejściowe do modelu. Dzięki osadzeniom jesteśmy w stanie elegancko uchwycić i przekazać tę ukrytą relację, którą przegapilibyśmy, gdybyśmy wykorzystali tylko godzinę tygodnia jako funkcję!

Co dalej

Po obejrzeniu kilku udanych zastosowań osadzania budujemy platformę, która umożliwi wielu modelarzom uczenia maszynowego (ML) w Lyft ich wykorzystanie. Podejście do konstruowania wykresów danych i budowania osadzania jest bardzo elastyczne i można je zastosować do badania różnych zawiłości działalności związanej z przejazdami Lyft. Odkryte spostrzeżenia mogą pomóc nam zrozumieć różne wzorce jazdy, dynamikę rynku, a ostatecznie stworzyć lepsze produkty i oferty przejazdów dla naszych pasażerów i kierowców.

W ramach inicjatywy Embeddings Platform obsługiwanych jest wiele różnych projektów modelowania w celu tworzenia niestandardowych osadzeń i wykorzystywania ich jako innowacyjnych funkcji w modelach ML. Równolegle rozwiązujemy problemy z jakością danych i funkcji, automatycznym przekwalifikowaniem, zarządzaniem, zgodnością i infrastrukturą służącą do szkolenia dla naszych obsługiwanych zespołów.

Planujemy utrzymać świeże osadzenie najciekawszych podmiotów na rynku Lyft i udostępnić je jako łatwo dostępne funkcje dla wielu typowych przypadków użycia.

[1] Rysunek ze slajdów z wykładów z kursu Stanford CS224W .