Von der Heuristik zum maschinellen Lernen: Suchvorschläge in Citymobil

Hallo! Mein Name ist Mikhail Dyachkov und bei Citymobil lerne ich maschinell. Heute werde ich Ihnen von unserem neuen Algorithmus zum Generieren von Suchvorschlägen für endgültige Ziele erzählen. Sie erfahren, wie aus einer scheinbar einfachen Aufgabe ein interessantes Szenario wurde, mit dessen Hilfe wir hoffentlich das Leben der Benutzer ein wenig einfacher gestalten konnten. Wir überwachen die Arbeit des neuen Algorithmus weiterhin genau und werden ihn anschließend optimieren, um die Qualität des Rankings auf einem hohen Niveau zu halten. Für alle Benutzer werden wir den Algorithmus in den nächsten Wochen starten, aber wir sind bereits bereit, über den langen Weg zu sprechen, den wir von der Heuristik zum Algorithmus für maschinelles Lernen zurückgelegt und in Betrieb genommen haben.



Ich denke, es lohnt sich, zunächst das ideale Weltbild eines Taxibestellungsszenarios aus Sicht der Benutzeroberfläche zu beschreiben. Ich möchte, dass unsere Anwendung versteht, wo / wo / wann / mit welchem ​​Auto der Benutzer abfahren möchte. In diesem Artikel sehen wir uns unsere Lösung an, um die "Wo" -Frage zu beantworten.



Eines der zentralen Elemente auf dem ersten Bildschirm (das der Benutzer nach dem Anmelden sieht) sind Suchvorschläge. Im Geo-Suchteam nennen wir sie "sajest" (nach englischem Vorschlag)). Sie bieten dem Benutzer die endgültigen Routenadressen („B“ -Punkte) aus seinem Reiseverlauf basierend auf der aktuellen Position der PIN (dh dem Ablagepunkt) und der Tageszeit, ohne eine Suchabfrage einzugeben. Wir versuchen dem Benutzer zu helfen, eine Bestellung "mit einem Klick" mit Hilfe von Sagests zu erstellen. In der aktuellen Version der iOS-Clientanwendung sehen die Sajests folgendermaßen aus: Die Geosuche







aufgrund von Algorithmen zum Generieren von Suchergebnissen kann sich auf eine der wichtigsten Produktmetriken für die Clientanwendung auswirken, z. B. auf die Zeit, die für die Bestellung eines Taxis aufgewendet wurde ( Time to Order oder T2O ) Die Anzahl der Aktionen, die der Kunde ausgeführt hat, um eine Bestellung zu erstellen ( Aktionen auf Bestellung oder A2O)). Aus diesem Grund haben wir uns entschlossen, einen Algorithmus zu entwickeln, der die wahrscheinlichsten Endpunkte der Route (Punkte "B") für einen bestimmten Ort und eine bestimmte Tageszeit vorhersagt.

Heuristik

Einer der Backend-Entwickler des Geo-Search-Teams (vasilesk, hallo!) hat eine ziemlich einfache Heuristik zum Generieren von Sajests entwickelt, die sowohl für den Startpunkt "A" als auch für den Endpunkt "B" funktioniert. Es sollte sofort angemerkt werden, dass die Heuristik nicht mit dem Reiseverlauf des Benutzers, sondern mit dem Verlauf der Klicks auf Suchergebnisse funktioniert, was einige Probleme mit sich brachte. Diese Objekte nennen wir "Peaks" (aus dem Englischen. Die Auswahl ). Die Heuristik sah folgendermaßen aus:

1. Für den aktuellen Benutzer nehmen wir alle seine historischen Spitzen.
2. Wir filtern sie und lassen diejenigen mit demselben Ziel (von / wo).
3. , , 300 ( «» — 300 «», «» — 300 «»). , GPS- .
4. , , , , , .
5. , , 3:00 14:00, , .
6. - (), , - .
7. .

Dieser Algorithmus funktionierte eine Weile und war im Allgemeinen gut für MVPs (wir werden etwas später über Metriken sprechen), hatte aber eine Reihe von Nachteilen. Neben der eher primitiven Logik der Arbeit beruhte sie nicht auf Reisen, sondern auf den Empfehlungen des Benutzers. Aus diesem Grund erhielten Benutzer manchmal nicht offensichtliche Suchergebnisse. Aufgrund der "spezifischen" Art der Speicherung der Geschichte der Peaks war es auch ziemlich schwierig, schnelle Analysen durchzuführen. Auf dieser Grundlage haben wir uns entschlossen, maschinelles Lernen anzuwenden. Als nächstes werden wir die Formulierung von Ranking-Problemen betrachten und unser Problem auf eine binäre Klassifikation reduzieren.

Erklärung zum Ranking-Problem

Bevor wir über Funktionen, Metriken und ein Modell sprechen, müssen wir herausfinden, welche Art von Problem wir lösen möchten. Gehen wir iterativ vor und versuchen zunächst, eine allgemeine Formulierung des Ranking-Problems zu formulieren. Es sieht aus wie das:



$$$X$ - viele Gegenstände.



$$$X^l = \{x_1, \dots, x_l \}$ - Trainingsmuster. 



$$$i \prec j$ - paarweise richtige Reihenfolge $$$(i, j)$



Ziel: Aufbau einer Ranking-Funktion $$$a: X \rightarrow ℝ$, mit welchem 

$$

$$i \prec j ⇒  a(x_i) < a(x_j)$$

Formulieren wir nun die Aufgabe, Suchergebnisse nach Abfragen zu ordnen. Es unterscheidet sich vom allgemeinen Ranking-Problem darin, dass anstelle der allgemeinen Menge von Objekten, die sortiert werden müssen, zwei Mengen angezeigt werden$$$D$ und $$$Q$ - viele Dokumente und Anfragen.



$$$D$ - Sammlung von Dokumenten (Antworten).



$$$Q$ - viele Anfragen.



$$$D_q \subseteq D$ - die durch die Abfrage q gefundenen Dokumente.



$$$X = Q \times D$ - Objekte sind Paare "Anfrage, Dokument": $$$x \equiv (q, d), q \in Q, d \in D_q$



$$$Y$ - eine geordnete Reihe von Bewertungen (Ratings).



$$$y(q, d): X \rightarrow Y$- Relevanzwerte.



Je höher die Punktzahl$$$y(q, d)$Je relevanter das Dokument $$$d$ Anfrage $$$q$...



Die richtige Reihenfolge wird nur zwischen den Dokumenten definiert, die von derselben Abfrage gefunden wurden$$$q$:: 

$$

$$(q, d) \prec (q, d') \Leftrightarrow y(q, d) < y(q, d')$$

Bei unserer Aufgabe, Routenendpunkte zu empfehlen, sind die Bewertungen binär. Für den Benutzer kann die vorgeschlagene Adresse entweder relevant oder irrelevant sein (ausgenommen Fälle mit einer komplexen Route mit mehreren Endpunkten). Wenn wir die Aufgabe im Kontext des Benutzers betrachten, dann$$$q$- eine Anfrage an den Dienst, die die ID , die geografische Position, das Datum und die Uhrzeit des Kunden enthält ;$$$D_q$- viele historische Endpunkte "B" für die Reisen des Benutzers (wir machen nur Vorschläge basierend auf den Adressen vergangener Reisen). Und jede gültige Antwort$$$d \in D_q$ auf Anfrage $$$q$ kann entweder für den Benutzer relevant sein (ab dem aktuellen Zeitpunkt und zum aktuellen Zeitpunkt muss der Benutzer genau hierher gehen) oder irrelevant.



Der Vollständigkeit halber muss nur der Prozess der Erstellung einer Stichprobe von Anforderungs-Antwort-Paaren mit einem Ziel beschrieben werden. Betrachten Sie der Einfachheit halber einen Kunden, der 5 Reisen hatte. Lassen Sie uns diese Reisen vom ersten bis zum letzten Rang einordnen. Für die erste Reise wissen wir nichts über die Reisen des Benutzers, daher können wir ihm mit dem beschriebenen Algorithmus für maschinelles Lernen keinen Sagest anbieten (die Heuristik für neue Benutzer funktioniert hier). Für die zweite Reise kennen wir das endgültige Ziel von der ersten Reise und können dem Benutzer diese Adresse anbieten, wenn er das Nachbearbeitungsverfahren erfolgreich bestanden hat (mehr als 1 km vom aktuellen Standort entfernt, in derselben Region usw.). Für die dritte Reise haben wir möglicherweise bereits ein bis zwei mögliche Sadgets.wenn die Endadresse der zweiten Reise mit der Endadresse der ersten identisch war und wenn die Endadressen unterschiedlich waren. Wenn das Sajest mit dem Endpunkt "B" zusammenfiel (das heißt, es fiel in dasselbe Hex einer festen Größe), setzen wir 1 als Ziel, andernfalls - 0. Nach diesem Algorithmus bilden wir alle Arten von Paaren der Form "Anfrage - (mögliche) Antwort "Für jeden Kunden.



Daher haben wir das Ranking-Problem auf ein binäres Klassifizierungsproblem reduziert. Jetzt können wir über Qualitätsbewertungsmetriken sprechen.

Metriken

Bei Ranking-Problemen eine Metrik, die den Anteil der richtigen Antworten aus Dokumenten anzeigt $$$D_q$ nach oben $$$n$ Rangliste auf Anfrage $$$q$heißen Precision @ n . Wir sind an Precision @ 1/2/3 interessiert , da die gesamte Klickrate für die ersten drei Positionen etwa 95% beträgt. Gleichzeitig gibt es nur eine korrekte Endadresse (natürlich, wenn der Benutzer eine Adresse aus seinem Verlauf abrufen möchte). Daher zeigt diese Metrik nur den Anteil der Fälle an, in denen der korrekte Endpunkt "B" in die oberen 1/2/3 Adressen fällt, die schlug unseren Algorithmus vor.



Denken Sie daran, dass in unserem Problem$$$Y = \{0, 1\},\; y(q, d)$ - Relevanz, $$$a(q, d)$Ist die erforderliche Ranking-Funktion. Dann kann Precision @ n wie folgt geschrieben werden:

$$

$$P_n(q) = \frac{1}{n}\sum_{i=1}^{n} y(q, d_q^{(i)})$$

Schilder und Modell

Die Funktionen für das Modell in unserem Problem können in mehrere Blöcke unterteilt werden:

• Nur für Dokumente $$$d \in D_q$ (Endadresse, Punkt "B").
• Nur auf Anfrage $$$q$ (Startadresse, Punkt "A").
• Gemeinsam anzufordern und zu dokumentieren $$$(q, d)$ (Route von "A" nach "B").
• Allgemein für den Benutzer.

Hier sind einige Beispiele für jeden von ihnen.



Beispiele für Zeichen nur für das Dokument (Punkt "B"):

1. Anzahl der Fahrten zum Punkt "B" in den letzten K Tagen.
2. Die Anzahl der Fahrten zum Punkt "B" nach Wochentag und Tageszeit.
3. Wann war die vorherige Reise zu Punkt "B".
4. Markieren Sie, dass die vorherige Reise zum Punkt "B" gemacht wurde.
5. Ist Punkt "B" eine gewählte Adresse / Zuhause / Arbeit.

Beispiele für Merkmale nur auf Anfrage $$$q$ ( «» + /):

1. , .
2. «».
3. «» K .
4. «» .
5. «» //.
6. / $$$q$.
7. «».

, $$$(q, d)$ ( «» “”):

1. , .
2. .
3. .

:

1. K .
2. .
3. Historische Reisestatistiken (Mittelwert, Quantile, mittlere Reisestrecke usw.).

Als Ergebnis haben wir mehr als 100 Funktionen erhalten, die ein Paar von "Anforderungsdokument" -Objekten beschreiben. Da wir Precision @ 1/2/3 maximieren möchten , ist es logisch, dass wir die Wahrscheinlichkeit einer Benutzerreise zu einem bestimmten Ziel vorhersagen und mögliche Kandidaten gemäß der erhaltenen Wahrscheinlichkeit bewerten müssen. Wir haben verschiedene Algorithmen und verschiedene Verlustfunktionen ausprobiert und uns für die Erhöhung des Gradienten auf Bäumen und den Logloss entschieden . Die Ergebnisse, die zum Zeitpunkt der Verwendung der Heuristik erhalten wurden:

Produktion

Bevor Sie einige komplexe Algorithmen, Funktionen und Trainingsmodelle entwickeln, müssen Sie sich natürlich überlegen, wie dies alles im Kampf unter Last funktioniert, ohne die Skalierung zu vergessen. Nachdem wir uns mit dem Backend-Entwicklungsteam getroffen hatten, skizzierten wir einen groben Überblick darüber, wie unser Service aussehen sollte. Wir haben uns entschlossen, das trainierte Modell für maschinelles Lernen in das asynchrone Webframework Sanic zu integrieren, an die der Suchdienst Anfragen sendet. Zusätzlich zur vertikalen Skalierung haben wir die Möglichkeit implementiert, auf mehreren Computern bereitzustellen. Anforderungen an den Dienst werden an die URL des Load Balancers gesendet, und anschließend erfolgt ein Proxy an diesen oder jenen Computer mithilfe des Round-Robin-Algorithmus. Nach der Implementierung des ersten Prototyps des Dienstes haben wir festgestellt, dass wir das Abfragevolumen in MySQL erheblich reduzieren können. Da jede Verschiebung des Pins mit der Wahl des Einspeisepunkts eine neue Suchanforderung darstellt und daher für unseren Service, dachten wir, wir könnten ab dem Moment der Anforderung an Redis einen Cache mit dem Reiseverlauf des Benutzers für N Minuten speichern . Dank dessen haben wir die Belastung der Basis um das Dreifache reduziert. Infolgedessen kann das Dienstschema wie folgt dargestellt werden:







Wir speichern Anfragen an den Service und seine Antworten in ElasticSearch und übertragen und überwachen Metriken, die für die Stabilität der Arbeit in NewRelic verantwortlich sind.



Der allgemeine Arbeitsablauf unseres Service:

1. Der Suchdienst sendet eine Anfrage an den Suchhinweisdienst.
2. Der Balancer wählt eine der Maschinen aus und sendet diese Anfrage an diese.
3. Innerhalb des Computers wird die Anforderung an einen der offenen Mitarbeiter gesendet oder in die Warteschlange gestellt.
4. Im Inneren des Arbeiters:
   1. Wir validieren die eingehende Anfrage.
   2. Wir stellen in Redis eine Anfrage. Wenn für den Benutzer keine Bestellhistorie vorhanden ist, gehen wir zu MySQL und schreiben die empfangenen Daten in Redis.
   3. Wir führen eine grundlegende Datenvorverarbeitung durch und sammeln Funktionen für das Modell.
   4. Wir machen es predict_proba()nach allen generierten Sadges und sortieren sie nach "Wahrscheinlichkeit".
   5. Wir führen eine zusätzliche Nachbearbeitung der Daten durch und bilden die Antwort.
   6. Wir senden die Antwort an den Suchdienst zurück.

Was weiter?

Jetzt testen wir unser Modell aktiv mithilfe von Switchback-Tests, um anschließend Schlussfolgerungen zu ziehen und zusätzliche Add-Ons in den Algorithmus zu implementieren, um die Ranking-Qualität zu verbessern. In Zukunft werden wir versuchen, dem Modell zusätzliche Funktionen hinzuzufügen und gemeinsam mit den Produktdesignern eine neue Lösung für die "Anzeige" von Sagests vorzubereiten. Natürlich wäre es großartig, wenn unsere Anwendung selbst verstehen würde, wo / wann / wo / mit welchem ​​Auto der Benutzer abfahren möchte. Wir arbeiten in alle Richtungen, damit eine Taxibestellung wirklich mit einem Klick erfolgt.