Wie Yandex.Taxi die Lieferzeit von Autos mithilfe von maschinellem Lernen vorhersagt

Stellen Sie sich vor, Sie müssen ein Taxi rufen. Sie öffnen die Anwendung, sehen, dass das Auto in etwa sieben Minuten ankommt, klicken auf "Bestellen" - und ... das Auto ist, wenn überhaupt, 15 Minuten von Ihnen entfernt. Einverstanden, unangenehm?

Im Rahmen des Schnitts werden wir darüber sprechen, wie Methoden des maschinellen Lernens Yandex.Taxi dabei helfen, die ETA (geschätzte Ankunftszeit - erwartete Ankunftszeit) besser vorherzusagen.



Denken Sie zunächst daran, dass der Benutzer vor der Bestellung Folgendes in der Anwendung sieht:



Auf der Karte zeigt Blau die optimalen Punkte für das Einsteigen in ein Taxi an. Roter Stift - der Punkt, zu dem der Benutzer ein Taxi ruft. Der Stift zeigt an, wie lange das Auto ankommen wird. In einer perfekten Welt. In der realen Welt nennen sich andere Personen in der Nähe über die Yandex.Taxi-Anwendung auch ein Auto. Und wir wissen nicht, welches Auto an wen geht, weil sie erst nach Bestellung verteilt werden. Wenn das Auto bereits zugewiesen wurde, verwenden wir für die Vorhersage das Yandex.Maps-Routing und die Zeit, wenn wir uns auf dem optimalen Pfad bewegen. Dieses Mal (möglicherweise mit einem kleinen Rand) zeigen wir den Benutzer sofort nach der Bestellung. Die Frage bleibt: Wie kann man ETA vor der Bestellung vorhersagen?

Und hier erscheint maschinelles Lernen. Wir treffen eine Auswahl mit Objekten und den richtigen Antworten und bringen dem Algorithmus bei, die Antwort gemäß den Eigenschaften 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 numerische Parameter sein, die vor der Bestellung bekannt sind: die Anzahl der Fahrer und Benutzer der Anwendung neben dem Stift, die Entfernung zu den nächsten Servicefahrzeugen und andere potenziell nützliche Werte.

Warum ist das 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 oder, schlimmer noch, zum Flughafen kommt, ist es wichtig zu verstehen, ob sie rechtzeitig zum Verlassen und Erreichen ihres Ziels kommt.
Bei der Entscheidung, was bestellt werden soll, wird der zukünftige Passagier unter anderem von der Wartezeit geleitet. Es kann in verschiedenen Anwendungen für das Anrufen eines Taxis und in verschiedenen Tarifen einer Anwendung sehr unterschiedlich sein. Damit der Benutzer die Auswahl nicht bereut, ist es sehr wichtig, die genaue ETA anzuzeigen.

Alles scheint einfach zu sein. Überlegen Sie sich mehr Schilder, trainieren Sie ein Modell wie CatBoost, sagen Sie die Zeit vor der Ankunft des Autos voraus - und Sie können dort enden. Die Erfahrung zeigt jedoch, dass es besser ist, nicht zu hetzen und sorgfältig nachzudenken und es dann zu tun.

Zunächst hatten wir keinen Zweifel daran, dass es notwendig war, die Zeit vorherzusagen, in der der Fahrer tatsächlich zum Benutzer gelangen würde. Ja, wir wissen nicht genau, welches Auto vor der Bestellung zugewiesen wird. Wir können die ETA jedoch anhand von Daten vorhersagen, die sich nicht auf einen bestimmten Fahrer beziehen, sondern auf die Fahrer in der Nähe der Bestellung. Natürlich muss die Prognose ehrlich genug sein, damit der Benutzer die Zeit planen kann.

Aber was bedeutet "ehrlich"? Schließlich ist jeder Prognosealgorithmus schlecht oder nur statistisch gut. Es gibt sowohl erfolgreiche als auch ehrlich gesagt schlechte Ergebnisse, aber Sie müssen "durchschnittlich" sein, um nicht wesentlich von den richtigen Antworten abzuweichen. Es versteht sich, dass "im Durchschnitt" anders ist. Der Durchschnitt besteht beispielsweise aus mindestens drei statistischen Konzepten: Erwartung, Median und Mode. Das Bild aus Darrell Huffs großartigem Buch "Wie man mit Statistiken lügt" zeigt perfekt den Unterschied:



Wir möchten, dass das Modell im Durchschnitt nur wenige Fehler macht. Abhängig vom Wert des "Durchschnitts" gibt es zwei Möglichkeiten, die Qualität der Prognosen zu bewerten. Die erste Möglichkeit besteht darin, dem Benutzer die mathematische Erwartung der Zeit vor dem Eintreffen des Taxis anzuzeigen. Als Ergebnis wird ein Modell trainiert, das das mittlere Quadrat des Prognosefehlers minimiert (Mean Squared Error, MSE):

$$

$$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 zu verwechseln, hauptsächlich in eine Richtung, nach oben oder unten. In diesem Fall zeigen wir dem Benutzer den Median der Zeitverteilung vor dem Eintreffen des Taxis. Als Ergebnis wird ein Modell trainiert, das das Durchschnittsmodul des Prognosefehlers optimiert (Mean Absolute Error, MAE):

$$

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

Aber wir stellten fest, dass wir uns ein bisschen voraus waren.

Die Aussage des Problems überdenken

Nach dem Termin wissen wir, welche Art von Auto an den Benutzer geht, was bedeutet, dass wir seine Reisezeit auf Yandex.Maps schätzen können. Diese Zeit wird im Pin nach der Bestellung angezeigt. Einerseits haben wir jetzt mehr Informationen und die Prognose wird genauer sein, andererseits ist dies auch eine Schätzung mit einem Fehler.

Das war der Haken in der ETA-Pin-Aufgabe. Während der Fahrer nicht zugewiesen ist, muss genau die Zeit vorhergesagt werden , die das Yandex.Mart-Routing dann anzeigt, und nicht die tatsächliche Zeit, bevor das Auto ausgeliefert wurde.

Es scheint, was für ein Unsinn: Anstelle des genauen Wertes eine andere Prognose als Ziel nehmen? Aber das macht Sinn, und hier ist der Grund. Auf dem Weg zu Ihnen kann das angegebene Auto verweilen. Der Fahrer geriet auf der Straße, im Stau aufgrund eines Unfalls in eine gefährliche Situation 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 im Pin vorherzusagen, noch schwieriger wird.

Wie Lärm loswerden? Vorhersage der geglätteten Zielvariablen - die Zeit, die angezeigt wird, nachdem die Maschine basierend auf der Route zum Benutzer zugewiesen wurde.

Dies ist die Logik aus geschäftlicher Sicht: Sie können die Zeit auf der Straße ohnehin nicht auf den optimalen Weg von ETA bringen, aber zusätzliche Verzögerungen können durch die Arbeit mit Fahrern verringert werden.

Qualitätsmetriken, Daten, Modell und Schulung

Wir haben herausgefunden, dass für ETA im Pin nicht die tatsächliche Zeit vorhergesagt werden muss, sondern die Zeit, die empfangen wird, nachdem die Maschine entlang der Route zugewiesen wurde. Von den beiden Qualitätsmetriken MAE und MSE haben wir MAE ausgewählt. Unter dem Gesichtspunkt der Intuitivität der Prognose ist es möglicherweise logischer, die mittlere Erwartung (MSE) zu bewerten, als den Median (MAE). Aber MAE hat eine nette Eigenschaft: Das Modell ist unter Trainingsbeispielen widerstandsfähiger gegen Ausreißer.

Zeichen sind in Gruppen unterteilt:
- nach aktueller Zeit gebaut;
- Geo (Koordinaten, Entfernung zum Stadtzentrum und wichtige Objekte auf der Karte);
- Stift (wie viele und welche Autos in der Nähe sind, deren Dichte unterschiedlich berechnet wird);
- Statistiken über die Zone (wie üblich machen wir Fehler, wie viel wir vorhersagen);
- Daten über die nächstgelegenen Fahrer (wie lange sie erreichen, wie weit der erste näher als der zweite ist usw.).

Natürlich wurde CatBoost auf diese Zeichen geschult. Das entscheidende Argument war, dass sich die in CatBoost über ausgeglichene Bäume implementierte Gradientenverstärkung seit langem als sehr leistungsfähige Methode des maschinellen Lernens etabliert hat und sich die Methode zum Codieren kategorialer Merkmale in CatBoost regelmäßig für unsere Aufgaben auszahlt. Ein weiteres nettes Feature der Bibliothek ist das schnelle Lernen auf der GPU.

Nun ein paar Worte darüber, welche Modelle verglichen wurden. Die anfängliche ETA (bevor sie durch maschinelles Lernen festgelegt wurde) wurde basierend auf der Zeit berechnet, für die die Maschine, die dem Benutzer am nächsten ist, ankommen konnte. Das aktuelle Modell (das jetzt in der Anwendung verwendet wird) hat sich als maschinelles Lernen herausgestellt und worum es in diesem Artikel geht. Darüber hinaus wird in Kürze ein neues Modell in Produktion gehen. Sie verwendet um eine Größenordnung bedeutendere Merkmale, um das Problem zu lösen. Die folgende Tabelle zeigt die Qualitätsmessungen dieser Modelle anhand historischer Daten. Übrigens haben wir noch viele Pläne - kommen Sie, um zu helfen .

Vorhersagequalität für die ETA-Validierung *



* Prozentsatz (in Klammern die Änderung gegenüber der ursprünglichen ETA angeben).

Durch maschinelles Lernen konnten wir etwa zwei Sekunden oder 3,4% der durchschnittlichen Prognoseabweichung gewinnen. Und im neuen Modell - fast eine weitere Sekunde, insgesamt 4,5%. Aus diesen Zahlen ist 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. Fehlschläge mit einer Prognose von mehr als 5 Minuten wurden 19,2% und im neuen Modell sogar 23,2% weniger! Solche Fehler treten übrigens nur in 3 und 2,8% der Fälle in Modellen mit maschinellem Lernen auf.

Zusammenfassung

Wir haben die ETA hauptsächlich im Pin angegeben, um den Benutzern eine zuverlässige Prognose zu liefern. Bei jeder Anwendung des maschinellen Lernens in der Wirtschaft ist es natürlich unerlässlich, die wirtschaftlichen Auswirkungen zu bewerten. Und verstehen Sie, ob es mit den Kosten für die Erstellung und Implementierung von Modellen vergleichbar ist. Nach dem Online-A / B-Test stellte sich heraus, dass wir mithilfe von maschinellem Lernen einen statistisch signifikanten Anstieg der Conversion von einer Bestellung zu einer Reise (schließlich kann eine Bestellung storniert werden) und einen Anstieg der Conversion von einer Benutzersitzung zu einer Bestellung erhalten haben.

In beiden Fällen handelt es sich um einen Effekt in der Größenordnung von 0,1 Prozentpunkten. Dies widerspricht übrigens nicht der statistischen Signifikanz: Bei unseren Datenmengen wird auch ein solcher Unterschied in 2–4 Wochen zuverlässig festgestellt. Und mit geschäftlicher Relevanz ist in der Tat auch nicht alles schlecht: Es stellte sich heraus, dass die Kosten für die Klärung der ETA durch die Zunahme der Umstellung in nur wenigen Monaten gedeckt werden.

Als Ergebnis haben wir einen nützlichen und anschaulichen Fall erhalten. Die Verfeinerung 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 festgestellt, dass die Benutzer sie schätzen. Wir hoffen, dass die verfeinerte ETA unseren Passagieren hilft, Meetings, Züge und Flugzeuge häufiger zu treffen.

PS Wenn Sie an anderen Yandex.Taxi-Technologien interessiert sind, empfehlen wir einen Beitrag zur dynamischen Preisgestaltung , den mein Kollege kürzlich veröffentlicht hat.