Ein guter Taxidienst sollte sicher, zuverlässig und schnell sein. Auf Details wird der Nutzer nicht eingehen: Für ihn ist es wichtig, dass er auf den Button „Bestellen“ klickt und so schnell wie möglich ein Auto erhält, das ihn von Punkt A nach Punkt B bringt. Wenn keine Autos in der Nähe sind, sollte der Service dies tun Informieren Sie uns unverzüglich darüber, damit beim Kunden keine falschen Erwartungen entstehen. Wenn das „Autoverbot“-Schild jedoch zu oft erscheint, ist es logisch, dass jemand diesen Service einfach nicht mehr nutzt und zu einem Mitbewerber wechselt.
In diesem Artikel möchte ich darüber sprechen, wie wir mithilfe von maschinellem Lernen das Problem der Suche nach Autos in Gebieten mit geringer Bevölkerungsdichte (d. h. dort, wo es auf den ersten Blick keine Autos gibt) gelöst haben. Und was dabei herausgekommen ist.
Vorgeschichte
Um ein Taxi zu rufen, führt der Benutzer ein paar einfache Schritte aus, aber was passiert innerhalb des Dienstes?
| Benutzer | Bühne | Backend Yandex.Taxi |
|---|---|---|
| Wählt den Startpunkt aus | Pin | Wir starten eine vereinfachte Kandidatensuche – die Pin-Suche. Basierend auf den gefundenen Fahrern wird die Ankunftszeit vorhergesagt – ETA im Pin. Der zunehmende Koeffizient an einem bestimmten Punkt wird berechnet. |
| Wählt Ziel, Tarif und Anforderungen aus | Angebot | Wir erstellen eine Route und berechnen die Preise für alle Tarife unter Berücksichtigung des steigenden Koeffizienten. |
| Drückt die Schaltfläche „Taxi rufen“. | Заказ | Wir starten eine vollständige Suche nach dem Auto. Wir wählen den am besten geeigneten Fahrer aus und bieten ihm einen Auftrag an. |
Про , и wir haben schon geschrieben. Und dies ist eine Geschichte über die Suche nach Fahrern. Wenn eine Bestellung erstellt wird, erfolgt die Suche zweimal: auf dem Pin und auf der Bestellung. Die Suche nach einem Auftrag erfolgt in zwei Schritten: Rekrutierung von Kandidaten und Ranking. Zunächst werden verfügbare Fahrerkandidaten gefunden, die im Straßendiagramm am nächsten liegen. Dann werden Boni und Filter angewendet. Die verbleibenden Kandidaten werden gereiht und der Gewinner erhält ein Bestellangebot. Stimmt er zu, wird er der Bestellung zugewiesen und begibt sich zur Lieferstelle. Wenn er ablehnt, kommt das Angebot zum nächsten. Wenn keine Kandidaten mehr vorhanden sind, beginnt die Suche erneut. Dies dauert nicht länger als drei Minuten. Danach wird die Bestellung storniert und verbrannt.
Die Suche nach einem Pin ähnelt der Suche nach einer Bestellung, nur dass die Bestellung nicht erstellt wird und die Suche selbst nur einmal durchgeführt wird. Vereinfachte Einstellungen zur Anzahl der Kandidaten und zum Suchradius kommen ebenfalls zum Einsatz. Solche Vereinfachungen sind notwendig, da es um eine Größenordnung mehr Pins als Bestellungen gibt und die Suche ein ziemlich schwieriger Vorgang ist. Der Kernpunkt unserer Story: Sollten bei der Vorabsuche keine passenden Kandidaten auf dem Pin gefunden werden, erlauben wir Ihnen keine Bestellung. Zumindest war das früher so.
Dies ist, was der Benutzer in der Anwendung gesehen hat:
Suche nach Autos ohne Autos
Eines Tages kamen wir auf eine Hypothese: Vielleicht kann der Auftrag in manchen Fällen noch ausgeführt werden, auch wenn keine Autos auf dem Pin wären. Schließlich vergeht zwischen dem Pin und der Bestellung einige Zeit, und die Suche nach der Bestellung ist vollständiger und wird manchmal mehrmals wiederholt: In dieser Zeit können verfügbare Treiber erscheinen. Wir wussten auch das Gegenteil: Wenn Treiber auf dem Pin gefunden wurden, war es keine Tatsache, dass sie bei der Bestellung gefunden wurden. Manchmal verschwinden sie oder jeder lehnt die Bestellung ab.
Um diese Hypothese zu testen, haben wir ein Experiment gestartet: Wir haben für eine Testgruppe von Benutzern aufgehört, das Vorhandensein von Autos während einer Suche auf einem Pin zu überprüfen, d. h. sie hatten die Möglichkeit, eine „Bestellung ohne Autos“ aufzugeben. Das Ergebnis war ziemlich unerwartet: Wenn das Auto nicht auf dem Pin stand, wurde es in 29 % der Fälle später gefunden – bei der Suche auf der Bestellung! Darüber hinaus unterschieden sich Bestellungen ohne Autos in Bezug auf Stornierungsraten, Bewertungen und andere Qualitätsindikatoren nicht wesentlich von regulären Bestellungen. Buchungen ohne Auto machten 5 % aller Buchungen aus, aber etwas mehr als 1 % aller erfolgreichen Reisen.
Um zu verstehen, woher die Ausführer dieser Befehle kommen, schauen wir uns ihren Status während einer Suche nach einem Pin an:
- Verfügbar: war verfügbar, wurde aber aus irgendeinem Grund nicht in die Kandidatenliste aufgenommen, zum Beispiel weil er zu weit weg war;
- Auf Bestellung: war beschäftigt, schaffte es aber, sich zu befreien oder verfügbar zu werden ;
- Beschäftigt: die Möglichkeit, Bestellungen anzunehmen, wurde deaktiviert, aber dann kehrte der Fahrer an die Schlange zurück;
- Nicht verfügbar: Der Fahrer war nicht online, erschien aber.
Fügen wir Zuverlässigkeit hinzu
Zusätzliche Bestellungen sind großartig, aber 29 % der erfolgreichen Suchanfragen bedeuten, dass der Benutzer in 71 % der Fälle lange gewartet hat und am Ende nichts erreicht hat. Obwohl dies aus Sicht der Systemeffizienz keine schlechte Sache ist, weckt es beim Benutzer tatsächlich falsche Hoffnungen und verschwendet Zeit, woraufhin er verärgert ist und (möglicherweise) die Nutzung des Dienstes einstellt. Um dieses Problem zu lösen, haben wir gelernt, die Wahrscheinlichkeit vorherzusagen, mit der ein bestelltes Auto gefunden wird.
Das Schema sieht so aus:
- Der Benutzer setzt einen Pin.
- Es wird eine Suche auf dem Pin durchgeführt.
- Wenn es keine Autos gibt, sagen wir voraus: Vielleicht werden sie auftauchen.
- Und abhängig von der Wahrscheinlichkeit gestatten wir Ihnen, eine Bestellung aufzugeben oder nicht, weisen Sie jedoch darauf hin, dass die Dichte an Autos in dieser Gegend derzeit gering ist.
Im Antrag sah es so aus:
Durch die Verwendung des Modells können Sie neue Aufträge präziser erstellen und die Leute nicht umsonst beruhigen. Das heißt, das Verhältnis von Zuverlässigkeit und Anzahl der Bestellungen ohne Maschinen mithilfe des Precision-Recall-Modells zu regulieren. Die Zuverlässigkeit des Dienstes beeinflusst den Wunsch, das Produkt weiterhin zu nutzen, d. h. letztendlich kommt es auf die Anzahl der Fahrten an.
Ein wenig über PräzisionsrückrufEine der Grundaufgaben beim maschinellen Lernen ist die Klassifizierungsaufgabe: die Zuweisung eines Objekts zu einer von zwei Klassen. In diesem Fall wird das Ergebnis des maschinellen Lernalgorithmus häufig zu einer numerischen Bewertung der Zugehörigkeit zu einer der Klassen, beispielsweise einer Wahrscheinlichkeitsbewertung. Die durchgeführten Aktionen sind jedoch in der Regel binär: Wenn das Auto verfügbar ist, lassen wir es Sie bestellen, wenn nicht, dann nicht. Genauer gesagt nennen wir einen Algorithmus, der eine numerische Schätzung erstellt, ein Modell und einen Klassifikator eine Regel, die ihn einer von zwei Klassen (1 oder –1) zuordnet. Um einen Klassifikator basierend auf der Modellbewertung zu erstellen, müssen Sie einen Bewertungsschwellenwert auswählen. Wie genau, hängt stark von der Aufgabenstellung ab.
Angenommen, wir führen einen Test (Klassifikator) für eine seltene und gefährliche Krankheit durch. Basierend auf den Testergebnissen schicken wir den Patienten entweder zu einer genaueren Untersuchung oder sagen: „Gut, gehen Sie nach Hause.“ Für uns ist es viel schlimmer, einen Kranken nach Hause zu schicken, als einen Gesunden unnötig zu untersuchen. Das heißt, wir wollen, dass der Test bei möglichst vielen wirklich kranken Menschen funktioniert. Dieser Wert wird Recall = genannt. Ein idealer Klassifikator hat einen Rückruf von 100 %. Eine degenerierte Situation ist es, alle zur Untersuchung zu schicken, dann erfolgt auch der Rückruf zu 100 %.
Es passiert auch umgekehrt. Wir entwickeln zum Beispiel ein Testsystem für Studenten, das über einen Betrugsdetektor verfügt. Wenn bei einigen Betrugsfällen plötzlich die Prüfung nicht funktioniert, ist das zwar unangenehm, aber nicht kritisch. Andererseits ist es äußerst schlimm, Schülern zu Unrecht etwas vorzuwerfen, was sie nicht getan haben. Das heißt, es ist uns wichtig, dass unter den positiven Antworten des Klassifikators möglichst viele richtige Antworten sind, vielleicht zu Lasten ihrer Zahl. Das bedeutet, dass Sie die Präzision maximieren müssen = . Wenn die Auslösung bei allen Objekten erfolgt, entspricht die Genauigkeit der Häufigkeit der definierten Klasse im Beispiel.
Wenn der Algorithmus einen numerischen Wahrscheinlichkeitswert erzeugt, können Sie durch Auswahl verschiedener Schwellenwerte unterschiedliche Präzisionsrückrufwerte erzielen.
In unserem Problem ist die Situation wie folgt. Rückruf ist die Anzahl der Aufträge, die wir anbieten können, Präzision ist die Zuverlässigkeit dieser Aufträge. So sieht die Precision-Recall-Kurve unseres Modells aus:
Es gibt zwei Extremfälle: niemandem erlauben, zu bestellen, und jedem erlauben, zu bestellen. Wenn Sie niemanden zulassen, ist der Rückruf 0: Wir erstellen keine Aufträge, aber keiner von ihnen wird fehlschlagen. Wenn wir alle zulassen, beträgt die Rückrufquote 100 % (wir erhalten alle möglichen Bestellungen) und die Genauigkeit 29 %, d. h. 71 % der Bestellungen sind fehlerhaft.
Als Zeichen haben wir verschiedene Parameter des Startpunkts verwendet:
- Uhrzeit Ort.
- Systemzustand (Anzahl der belegten Automaten aller Tarife und Pins in der Nähe).
- Suchparameter (Radius, Anzahl der Kandidaten, Einschränkungen).
Mehr zu den Schildern
Konzeptionell wollen wir zwischen zwei Situationen unterscheiden:
- „Tiefer Wald“ – zur Zeit fahren hier keine Autos.
- „Pech gehabt“ – es gibt Autos, aber bei der Suche gab es keine passenden.
Ein Beispiel für „Pech“ ist, wenn am Freitagabend eine große Nachfrage im Center herrscht. Es gibt viele Bestellungen, viele Leute, die bereit sind, und nicht genug Fahrer für alle. Es kann so kommen: Es sind keine passenden Treiber im Pin vorhanden. Aber buchstäblich innerhalb von Sekunden erscheinen sie, denn zu diesem Zeitpunkt gibt es an diesem Ort viele Fahrer und ihr Status ändert sich ständig.
Daher erwiesen sich verschiedene Systemindikatoren in der Nähe von Punkt A als gute Merkmale:
- Gesamtzahl der Autos.
- Anzahl der bestellten Autos.
- Die Anzahl der Autos, die im Status „Beschäftigt“ nicht zur Bestellung verfügbar sind.
- Anzahl der Nutzer.
Denn je mehr Autos es gibt, desto wahrscheinlicher ist es, dass eines davon verfügbar wird.
Tatsächlich ist es uns wichtig, dass nicht nur Autos geortet werden, sondern auch erfolgreiche Fahrten durchgeführt werden. Daher war es möglich, die Wahrscheinlichkeit einer erfolgreichen Reise vorherzusagen. Wir haben uns jedoch dagegen entschieden, da dieser Wert stark vom Benutzer und Fahrer abhängt.
Der Modelltrainingsalgorithmus war . Die aus dem Experiment gewonnenen Daten wurden für das Training verwendet. Nach der Implementierung mussten Trainingsdaten gesammelt werden, was es manchmal einer kleinen Anzahl von Benutzern ermöglichte, gegen die Entscheidung des Modells zu bestellen.
Ergebnisse
Die Ergebnisse des Experiments waren wie erwartet: Durch die Verwendung des Modells können Sie die Anzahl erfolgreicher Fahrten aufgrund von Bestellungen ohne Autos erheblich steigern, ohne jedoch die Zuverlässigkeit zu beeinträchtigen.
Derzeit ist der Mechanismus in allen Städten und Ländern eingeführt und mit seiner Hilfe werden etwa 1 % der erfolgreichen Reisen durchgeführt. Darüber hinaus erreicht der Anteil solcher Fahrten in einigen Städten mit geringer Autodichte 15 %.
Weitere Beiträge zum Thema Taxitechnologien
Source: habr.com