Wie Yandex.Taxi den Zeitpunkt der Ablage eines Autos durch maschinelles Lernen vorhersagt

Published on November 29, 2018

Wie Yandex.Taxi den Zeitpunkt der Ablage eines Autos durch maschinelles Lernen vorhersagt

    Stellen Sie sich vor, Sie müssen ein Taxi rufen. Sie öffnen die Anwendung, stellen fest, dass das Auto in sieben Minuten ankommt, klicken Sie auf "Bestellen" - und ... das Auto ist 15 Minuten von Ihnen entfernt, falls es überhaupt gefunden wird. Zustimmen, unangenehm?

    Sprechen wir im Folgenden darüber, wie maschinelle Lernmethoden Yandex.Taxi dabei helfen, die ETA (Voraussichtliche Ankunftszeit) besser vorherzusagen.



    Zunächst erinnern wir uns, dass der Benutzer vor der Bestellung in der Anwendung sieht:



    Auf der Karte sind die optimalen Punkte für die Landung in einem Taxi blau markiert. Rote Stecknadel - der Punkt, zu dem der Benutzer ein Taxi ruft. Der Pin zeigt an, wie lange das Auto ankommen wird. In einer idealen Welt. In der realen Welt bezeichnen sich andere Personen in der Nähe jedoch auch über die Anwendung Yandex.Taxi als Auto. Und wir wissen nicht, welches Auto zu wem fahren wird, weil sie erst nach der Bestellung verteilt werden. Wenn die Maschine bereits zugewiesen ist, verwenden wir für die Prognose das Yandex.Map-Routing und die Zeit, wenn Sie sich auf dem optimalen Pfad bewegen. Diesmal (vielleicht mit einem kleinen Vorsprung) zeigen wir den Benutzer sofort nach der Bestellung. Es bleibt die Frage: Wie kann die ETA vor der Bestellung vorhergesagt werden?

    Und hier kommt maschinelles Lernen. Wir machen eine Probe mit den Objekten und den richtigen Antworten und trainieren den Algorithmus, um die Antwort anhand der Merkmale des Objekts zu erraten. In unserem Fall sind die Objekte Benutzersitzungen, die Antworten sind die Zeit, nach der das Auto tatsächlich angekommen ist. Zeichen des Objekts können vor der Bestellung bekannte numerische Parameter sein: Anzahl der Fahrer und Benutzer der Anwendung neben dem Pin, Entfernung zu den nächstgelegenen Servicewagen und andere potenziell nützliche Werte.

    Warum ist es wichtig?



    In einer idealen Welt tun die Menschen alles im Voraus und planen ihre Zeit immer genau. Aber wir leben in der realen Welt. Wenn eine Person zu spät zur Arbeit kommt oder, noch schlimmer, am Flughafen, ist es wichtig zu wissen, ob sie Zeit hat, um zu gehen und zu ihrem Ziel zu gelangen.
    Bei der Entscheidung, was bestellt werden soll, wird der zukünftige Passagier einschließlich der Wartezeit geleitet. Es kann in verschiedenen Anwendungen zum Anrufen eines Taxis und in unterschiedlichen Raten einer Anwendung sehr unterschiedlich sein. Damit der Benutzer die Auswahl nicht bereut, ist es sehr wichtig, die genaue ETA anzuzeigen.

    Es scheint einfach zu sein. Machen Sie weitere Schilder, trainieren Sie das Modell, zum Beispiel CatBoost, und sagen Sie die Zeit bis zum Eintreffen des Autos voraus - und Sie können damit fertig werden. Die Erfahrung zeigt jedoch, dass es besser ist, sich nicht zu beeilen, sorgfältig nachzudenken und es dann zu tun.

    Zunächst hatten wir keinen Zweifel, dass es notwendig war, die Zeit vorherzusagen, nach der der Fahrer tatsächlich beim Benutzer ankommen würde. Ja, vor der Bestellung wissen wir nicht genau, welche Art von Auto zugewiesen wird. Wir können die ETA jedoch anhand von Daten vorhersagen, nicht über einen bestimmten Fahrer, sondern über Fahrer in der Nähe der Bestellung. Natürlich muss die Prognose so fair sein, dass der Benutzer die Zeit planen kann.

    Aber was heißt "ehrlich"? Schließlich ist jeder Vorhersagealgorithmus nur statistisch gut oder gut. Es gibt auch erfolgreiche und ehrlich gesagt schlechte Ergebnisse, aber es ist „im Durchschnitt“ notwendig, nicht viel von den richtigen Antworten abzuweichen. Hier müssen wir verstehen, dass "im Durchschnitt" anders ist. Der Durchschnitt besteht beispielsweise aus mindestens drei Begriffen aus Statistiken: Erwartung, Median und Mode. Das Bild aus Darella Huffs großem Buch „Wie man mit Hilfe von Statistiken lügt“ zeigt den Unterschied perfekt:



    Wir möchten, dass das Modell im Durchschnitt etwas falsch ist. Je nach Wert „im Durchschnitt“ gibt es zwei Möglichkeiten zur Beurteilung der Prognosegüte. Die erste Option besteht darin, dem Benutzer die erwartete Zeit vor der Ankunft eines Taxis anzuzeigen. Als Ergebnis wird ein Modell gelernt, das das durchschnittliche Quadrat des Vorhersagefehlers (Mean Squared Error, MSE) minimiert:

    $ MSE = \ frac {1} {n} \ sum_ {i = 1} ^ {n} (y_i - \ hat {y} _i) ^ 2 \ rightarrow min $



    Hier $ y_i $ - richtige Antworten $ \ hat {y} _i $- Modellvorhersagen.

    Eine andere Option ist nicht mit der ETA-Prognose, hauptsächlich in eine Richtung, nach oben oder unten, zu verwechseln. In diesem Fall zeigen wir dem Benutzer die mittlere Zeitverteilung vor der Ankunft eines Taxis. Als Ergebnis wird ein Modell trainiert, das den durchschnittlichen Modul des Prognosefehlers (Mean Absolute Error, MAE) optimiert:

    $ MAE = \ frac {1} {n} \ sum_ {i = 1} ^ {n} | y_i - \ hat {y} _i |  \ rightarrow min $



    Aber wir haben erkannt, dass wir ein bisschen voraus sind.

    Überdenken der Problemstellung


    Nach dem Termin wissen wir, was für ein Auto an den Benutzer geht, sodass wir die Fahrzeit mit Yandex.Maps abschätzen können. Diese Zeit wird im Pin nach der Bestellung angezeigt. Zum einen haben wir nun mehr Informationen und die Prognose wird genauer sein, zum anderen ist dies jedoch auch eine Schätzung mit einem Fehler.

    Das war der Haken beim ETA-Pin-Problem. Solange der Fahrer nicht ernannt ist, muss der Zeitpunkt genau festgelegt werden, den das Yandex.Maps-Routing später anzeigt, und nicht die tatsächliche Zeit, bevor das Fahrzeug ausgeliefert wird.

    Es scheint der Unsinn: Anstelle des genauen Werts eine andere Prognose als Ziel zu nehmen? Aber es macht Sinn, und hier ist warum. Auf dem Weg zu Ihnen kann die vorgesehene Maschine verweilen. Der Fahrer geriet in eine gefährliche Situation auf der Straße, in einen Verkehrsstau infolge eines Unfalls oder ging hinaus, um Wasser zu kaufen. Solche Verzögerungen sind schwer vorherzusagen. Sie erzeugen zusätzliches Rauschen in der Zielvariablen, wodurch die ohnehin schwierige Aufgabe, die ETA in Pin vorherzusagen, noch schwieriger wird.

    Wie kann man Lärm loswerden? Prognostizieren Sie die geglättete Zielvariable - die Zeit, die angezeigt wird, nachdem die Maschine basierend auf der Route zum Benutzer zugewiesen wurde.

    Dies ist auch aus betriebswirtschaftlicher Sicht die Logik: Sie können die Reisezeit von ETA ohnehin nicht auf die beste Weise wegwerfen, aber zusätzliche Verzögerungen können durch die Arbeit mit Treibern reduziert werden.

    Qualitätskennzahlen, Daten, Modell und Schulung


    Wir haben herausgefunden, dass für die ETA in Pina nicht die tatsächliche Zeit vorhergesagt werden muss, sondern die Zeit, die nach der Zuweisung der Maschine auf der Route erhalten wird. Unter den beiden Qualitätskennzahlen MAE und MSE haben wir uns für MAE entschieden. Aus Sicht der Intuitivität der Prognose ist es vielleicht logischer, die Erwartung (MSE) als den Median (MAE) zu bewerten. MAE hat jedoch eine schöne Eigenschaft: Das Modell ist unter den Trainingsbeispielen widerstandsfähiger gegen Emissionen (Ausreißer).

    Die Zeichen sind in Gruppen unterteilt:
    - Aufbauend auf der aktuellen Uhrzeit;
    - Geo (Koordinaten, Entfernung zum Stadtzentrum und signifikante Objekte auf der Karte);
    - pin (wie viele und welche Autos in der Nähe, ihre Dichte wird anders berechnet);
    - Statistiken über die Zone (wie üblich irren wir uns, wie viele vorhergesagt werden);
    - Daten über die nächstgelegenen Fahrer (in welcher Zeit sie ankommen, wie viel näher ist der erste näher als der zweite usw.).

    Auf diesen Schildern wurde CatBoost natürlich geschult . Das entscheidende Argument war, dass sich der in CatBoost implementierte Gradientenschub über ausgewogene Bäume längst als sehr leistungsfähige Methode des maschinellen Lernens etabliert hat, und die Kodierungsmethode kategorialer Merkmale in CatBoost rechtfertigt sich regelmäßig in unseren Aufgaben. Ein weiteres nettes Feature der Bibliothek ist das schnelle GPU-Training.

    Nun ein paar Worte darüber, welche Modelle verglichen wurden. Die ursprüngliche ETA (bis zum maschinellen Lernen) wurde auf der Grundlage der Zeit berechnet, für die die dem Benutzer am nächsten gelegene Maschine ankommen kann. Das aktuelle Modell (jetzt in der Anwendung verwendet) ist das, was mit Hilfe des maschinellen Lernens gemacht wurde und worum es in diesem Artikel geht. Außerdem wird die Produktion bald ein neues Modell einführen. Es ist um eine Größenordnung wichtiger, um das Problem der Zeichen zu lösen. Die nachstehende Tabelle zeigt die Messungen der Qualität dieser Modelle anhand historischer Daten. Übrigens, wir haben noch viel vor - komm helfen .

    ETA-Prognosegüte für die Validierung *

     
    Mittlerer absoluter Fehler
    Fehler mehr als 1 Minute
    Fehler mehr als 2 Minuten
    Fehler mehr als 5 Minuten

    Ursprüngliche ETA


    82,082


    29,95


    18,12


    3.7


    Aktuelles Modell


    79.276 (–3,4)


    29,33 (–2,1)


    16,98 (–6,3)


    3 (–19,2)


    Neues Modell


    78.414 (-4,5)


    28,95 (–3,4)


    16,62 (–8,2)


    2,8 (–23,2)




    * Prozentsatz (Änderung der Klammern im Vergleich zur Basis-ETA).

    Maschinelles Lernen erlaubte, etwa zwei Sekunden oder 3,4% der durchschnittlichen Abweichung der Prognose zu gewinnen. Und im neuen Modell - schon fast eine Sekunde, insgesamt schon 4,5%. Aufgrund dieser Zahlen ist es jedoch schwer zu verstehen, dass sich die ETA erheblich verbessert hat. Um die Vorteile des maschinellen Lernens zu spüren, sollten Sie auf die letzte Spalte achten. Mit einer Prognose von mehr als 5 Minuten betrug der Rückstand 19,2% und im neuen Modell sogar 23,2% weniger! Übrigens treten solche Fehler nur in 3% und 2,8% der Fälle bei Modellen auf, die maschinelles Lernen verwenden.

    Ergebnisse


    Wir haben die ETA in Pina hauptsächlich verfeinert, um den Benutzern eine zuverlässige Prognose zu geben. Natürlich ist es bei jeder Anwendung des maschinellen Lernens in der Wirtschaft unerlässlich, die wirtschaftlichen Auswirkungen zu bewerten. Und zu verstehen, ob es mit den Kosten für das Erstellen und Implementieren von Modellen vergleichbar ist. Nach dem Online-A / B-Test stellte sich heraus, dass wir durch maschinelles Lernen eine statistisch signifikante Erhöhung der Konvertierung von Auftrag zu Fahrt (schließlich kann eine Bestellung storniert werden können) und eine Steigerung der Konvertierung von einer Benutzersitzung in eine Bestellung erhalten.

    In beiden Fällen ist dies ein Effekt in der Größenordnung von 0,1 Prozentpunkten. Dies steht übrigens nicht im Widerspruch zur statistischen Signifikanz: Bei unseren Datenmengen wird selbst ein solcher Unterschied in zwei bis vier Wochen zuverlässig erkannt. Und mit der Wichtigkeit für das Geschäft ist in der Tat auch alles nicht schlecht: Es stellte sich heraus, dass die Kosten für die Festlegung der ETA mit einer Conversion-Erhöhung in nur wenigen Monaten abgehen.

    Als Ergebnis erhielten wir einen nützlichen und demonstrativen Fall. Die Angabe der ETA im Pin ist zu einer lehrreichen Geschichte über die sorgfältige Auswahl der Zielvariablen geworden. Auf der Produktseite ist dies ein sehr motivierendes Beispiel: Wir haben die Anwendung verbessert und gesehen, dass die Benutzer dies zu schätzen gewusst haben. Wir hoffen, die aktualisierte ETA wird unseren Fluggästen helfen, häufiger mit Meetings, Zügen und Flugzeugen Schritt zu halten.

    PS Wenn Sie sich für andere Yandex.Taxi-Technologien interessieren, empfehlen wir IhnenPost über dynamisches Pricing , das mein Kollege kürzlich veröffentlicht hat.