Hallo zusammen! Ich bin Sascha, CTO & Co-Founder von LoyaltyLab. Vor zwei Jahren bin ich mit Freunden, wie alle anderen armen Studenten, abends zum nächsten Geschäft gegangen, um Bier zu kaufen. Es hat uns sehr frustriert, dass der Einzelhändler, der wusste, dass wir nach Bier kommen würden, keinen Rabatt auf Chips oder Snacks angeboten hat, obwohl das so logisch ist! Wir konnten nicht verstehen, warum das so ist, und beschlossen, unser eigenes Unternehmen zu gründen. Und als Bonus konnten wir uns jeden Freitag Rabatte auf genau diese Chips ausstellen.

Und es kam so weit, dass ich mit dem Material zur technischen Seite des Produkts auf der NVIDIA GTCspechen werde. Wir freuen uns, unsere Entwicklungen mit der Community zu teilen, deshalb veröffentliche ich meinen Vortrag als Artikel.

Einführung

Wie viele am Anfang, haben wir mit einer Übersicht darüber angefangen, wie Empfehlungssysteme erstellt werden. Und die beliebteste Architektur ist die folgende:

Sie besteht aus zwei Teilen:

1. Die Kandidatensampling für Empfehlungen erfolgt durch ein einfaches und schnelles Modell, normalerweise kollaborativ.
2. Die Rangordnung der Kandidaten erfolgt durch ein komplexeres und langsameres Inhaltsmodell unter Berücksichtigung aller möglichen Merkmale in den Daten.

Hier und in der Folge werde ich folgende Begriffe verwenden:

• candidate/Kandidat für Empfehlungen — ein Paar aus User und Produkt, das potenziell in die Empfehlungen im Produktionsbereich aufgenommen werden kann.
• candidates extraction/extractor/Methode zur Extraktion von Kandidaten — der Prozess oder die Methode zur Extraktion von "Kandidaten für Empfehlungen" aus den vorhandenen Daten.

Im ersten Schritt verwendet man normalerweise verschiedene Varianten der kollaborativen Filterung. Die beliebteste ist ALS. Es ist bemerkenswert, dass die meisten Artikel über Empfehlungssysteme nur verschiedene Verbesserungen kollaborativer Modelle im ersten Schritt behandeln, aber über andere Sampling-Methoden spricht niemand wirklich. Für uns hat der Ansatz, der nur kollaborative Modelle und verschiedene Optimierungen damit verwendet, nicht die Qualität geliefert, die wir erwartet hatten, weshalb wir uns intensiv mit der Forschung in diesem Bereich beschäftigt haben. Am Ende des Artikels zeige ich, wie sehr wir ALS verbessern konnten, das für uns die Basislinie war.

Bevor ich zu unserem Ansatz komme, ist es wichtig zu erwähnen, dass es bei Echtzeitempfehlungen, bei denen wir Daten berücksichtigen müssen, die vor 30 Minuten entstanden sind, tatsächlich nicht viele Ansätze gibt, die innerhalb der benötigten Zeit funktionieren können. In unserem Fall müssen Empfehlungen jedoch nicht häufiger als einmal pro Tag gesammelt werden, und in den meisten Fällen nur einmal pro Woche, was uns die Möglichkeit gibt, komplexe Modelle zu verwenden und die Qualität erheblich zu steigern.

Nehmen wir für die Baseline die Kennzahlen, die nur durch ALS bei der Kandidatenauswahl erzielt werden. Die wichtigsten Kennzahlen, auf die wir achten, sind die folgenden:

• Präzision — der Anteil der korrekt ausgewählten Kandidaten aus den sampelten.
• Recall — der Anteil der tatsächlichen Kandidaten aus denen, die sich tatsächlich im Zielbereich befanden.
• F1-Score — F-Maß, berechnet aus den vorherigen beiden Punkten.

Wir werden auch die Kennzahlen des finalen Modells nach dem Training des Gradientenboosting mit zusätzlichen Inhaltsmerkmalen betrachten. Auch hier gibt es 3 Hauptkennzahlen:

• precision@5 — der durchschnittliche Anteil an Produkten aus den Top 5 nach Wahrscheinlichkeit für jeden Käufer.
• response-rate@5 — die Konversionsrate der Käufer vom Besuch im Geschäft zum Kauf eines personalisierten Angebots (in einem Angebot sind 5 Produkte).
• avg roc-auc per user — der Durchschnitt roc-auc für jeden Käufer.

Es ist wichtig zu beachten, dass alle genannten Kennzahlen auf einer Time-Series-Kreuzvalidierung, das heißt, das Training erfolgt in den ersten k Wochen, und als Testdaten wird die k+1 Woche verwendet. So spiegeln saisonale Höhen und Tiefen die Interpretation der Modellqualität minimal wider. Auf allen Grafiken wird die x-Achse die Nummer der Woche in der Kreuzvalidierung darstellen, während die y-Achse den Wert der angegebenen Kennzahl darstellt. Alle Grafiken basieren auf Transaktionsdaten eines einzelnen Kunden, um einen korrekten Vergleich untereinander zu gewährleisten.

Bevor wir damit beginnen, unseren Ansatz zu beschreiben, schauen wir uns zunächst die Baseline an, die ein trainiertes ALS-Modell darstellt.
Kennzahlen zur Auswahl von Kandidaten:

Finale Kennzahlen:

Ich betrachte alle Implementierungen von Algorithmen als eine Art Geschäftshypothese. Grob gesagt können kollaborative Modelle als die Hypothese angesehen werden, dass "Menschen dazu neigen, das zu kaufen, was andere Menschen, die ihnen ähnlich sind, kaufen." Wie bereits erwähnt, haben wir uns jedoch nicht nur auf diese Semantik beschränkt, und hier sind einige Hypothesen, die auch gut mit Daten im Offline-Einzelhandel funktionieren:

1. Was zuvor gekauft wurde.
2. Ähnliches zu dem, was zuvor gekauft wurde.
3. Zeitraum des vergangenen Kaufs.
4. Beliebtes nach Kategorien/Marken.
5. Wechselnde Käufe verschiedener Produkte von Woche zu Woche (Markov-Ketten).
6. Ähnliche Produkte zu Käufern basierend auf Eigenschaften, die von verschiedenen Modellen erstellt wurden (Word2Vec, DSSM usw.).

Was früher gekauft wurde

Die offensichtlichste Heuristik, die im Lebensmitteleinzelhandel sehr gut funktioniert. Hier nehmen wir alle Produkte, die der Inhaber der Loyalitätskarte in den letzten K Tagen (üblich 1-3 Wochen) gekauft hat, oder K Tage im Jahr davor. Bei der Anwendung nur dieses Ansatzes erhalten wir folgende Metriken:

Es ist offensichtlich, dass je länger wir den Zeitraum wählen, desto höher ist unser Recall und desto niedriger die Precision und umgekehrt. Die besten Ergebnisse im Durchschnitt für die Kunden erzielt "die letzten 2 Wochen".

Ähnliches zu dem, was zuvor gekauft wurde

Es ist nicht überraschend, dass im Lebensmitteleinzelhandel "was vorher gekauft wurde" gut funktioniert, aber nur Kandidaten aus dem zu extrahieren, was der Benutzer bereits gekauft hat, ist nicht besonders effektiv, da es schwer ist, den Käufer mit einem neuen Produkt zu überraschen. Daher schlagen wir vor, diese Heuristik mit Hilfe der gleichen kollaborativen Modelle zu verfeinern. Aus den Vektoren, die wir während des ALS-Trainings erhalten haben, können wir ähnliche Produkte zu dem finden, was der Benutzer bereits gekauft hat. Diese Idee erinnert stark an "ähnliche Videos" in Video-Streaming-Diensten, aber da wir nicht wissen, was der Benutzer gerade isst/kauft, bleibt uns nur, nach ähnlichem zu suchen, was er bereits gekauft hat, zumal wir bereits wissen, wie gut das funktioniert. Wenn wir diese Methode mit den Transaktionen der Benutzer in den letzten 2 Wochen anwenden, erhalten wir folgende Metriken:

Hier k — die Anzahl ähnlicher Produkte, die für jedes vom Käufer in den letzten 14 Tagen gekaufte Produkt abgeleitet werden.
Dieser Ansatz hat bei uns besonders gut bei einem Kunden funktioniert, dem es entscheidend war, auf keinen Fall das zu empfehlen, was bereits in der Kaufhistorie des Nutzers war.

Zeitraum vergangener Käufe

Wie wir bereits festgestellt haben, funktioniert der erste Ansatz aufgrund der hohen Kaufrate von Produkten gut in unserer speziellen Situation. Aber wie verhält es sich mit Produkten wie Waschmittel/Shampoo/usw., also solchen Artikeln, die wahrscheinlich nicht alle ein bis zwei Wochen benötigt werden und die vorherigen Methoden nicht erfassen können. Daraus ergibt sich folgende Idee – es wird vorgeschlagen, den Kaufzeitraum jedes Produkts im Durchschnitt auf Basis der Käufer zu berechnen, die das Produkt mehr als k einmal gekauft haben. Und dann extrahieren wir, was mit hoher Wahrscheinlichkeit beim Käufer bereits aufgebraucht ist. Die berechneten Zeiträume für Produkte können visuell auf Angemessenheit überprüft werden:

Dann werden wir erkennen, ob das Ende des Produktzeitraums in den Zeitraum fällt, wenn die Empfehlungen in die Produktion gehen, und das, was passt, sampeln. Der Ansatz lässt sich wie folgt veranschaulichen:

Hier haben wir zwei Hauptfälle, die wir betrachten können:

1. Sollten wir Produkte an Käufer sampeln, die das Produkt weniger als K Mal gekauft haben.
2. Sollten wir das Produkt sampeln, wenn das Ende seines Zeitraums vor Beginn des Zielintervalls liegt.

Im nächsten Diagramm sind die Ergebnisse dargestellt, die diese Methode mit verschiedenen Hyperparametern erreicht:

ft – Nur Käufer ansprechen, die das Produkt mindestens K (hier K=5) Mal gekauft haben
tm – Nur Kandidaten berücksichtigen, die in das Zielintervall fallen

Es ist nicht überraschend, dass im Zustand (0, 0) die größte Recall und die geringste Precision, da unter diesen Bedingungen am meisten Kandidaten extrahiert werden. Die besten Ergebnisse erzielt man jedoch, wenn wir keine Produkte für Käufer sampeln, die ein bestimmtes Produkt weniger als k Mal gekauft haben, und auch Produkte einbeziehen, deren Zeitraum vor das Zielintervall fällt.

Beliebt in der Kategorie

Eine weitere eher offensichtliche Idee ist, beliebte Produkte aus verschiedenen Kategorien oder Marken zu sampeln. Hier berechnen wir für jeden Käufer Top-k Wir extrahieren die „beliebtesten“ Kategorien/Marken aus dieser Kategorie/Marke. In unserem Fall definieren wir „lieblings“ und „beliebt“ anhand der Anzahl der Käufe eines Produkts. Ein zusätzliches Plus dieses Ansatzes ist die Anwendbarkeit im Fall des Cold Starts. Das heißt für Käufer, die entweder sehr wenige Käufe getätigt haben, lange nicht im Geschäft waren oder überhaupt nur eine Treuekarte beantragt haben. Für sie ist es einfacher und am besten, Produkte aus den bei Käufern mit vorhandener Historie beliebten Produkten anzubieten. Die Metriken ergeben sich wie folgt:

Hier bedeutet die Zahl nach dem Wort „category“ die Tiefe der Kategorie.

Es ist auch nicht überraschend, dass engere Kategorien die besten Ergebnisse liefern, da sie genauere „beliebte“ Produkte für Käufer extrahieren.

Wechselnde Käufe verschiedener Produkte von Woche zu Woche

Ein interessanter Ansatz, den ich in Artikeln über Empfehlungssysteme nicht gesehen habe — eine ziemlich einfache und gleichzeitig funktionierende statistische Methode der Markov-Ketten. Hier nehmen wir 2 verschiedene Wochen und bauen für jeden Käufer Produktpaare auf. [gekauft in Woche i]-[gekauft in Woche j], wobei j > i, und von hier aus berechnen wir für jedes Produkt die Wahrscheinlichkeit, dass in der nächsten Woche zu einem anderen Produkt gewechselt wird. Das heißt für jedes Paar von Produkten producti-productj wir zählen deren Anzahl in den gefundenen Paaren und teilen durch die Anzahl der Paare, in denen producti in der ersten Woche war. Um die Kandidaten zu extrahieren, nehmen wir den letzten Beleg des Käufers und ziehen die wahrscheinlichsten folgenden Produkte aus der Übergangsmatrix, die wir erhalten haben. Der Prozess zum Aufbau der Übergangsmatrix sieht folgendermaßen aus: Top-k Aus realen Beispielen in der Übergangswahrscheinlichkeitsmatrix sehen wir folgende interessante Phänomene:

Hier kann man interessante Abhängigkeiten bemerken, die im Konsumverhalten auftauchen: zum Beispiel Liebhaber von Zitrusfrüchten oder eine Milchmarke, von der man mit hoher Wahrscheinlichkeit zu einer anderen wechselt. Es ist auch nicht überraschend, dass Produkte mit hoher Wiederkaufrate, wie Öl, ebenfalls hier auftauchen.

Die Metriken in der Methode mit Markov-Ketten ergeben sich wie folgt:

— die Anzahl der Produkte, die für jedes gekaufte Produkt aus der letzten Transaktion des Käufers extrahiert werden.

k — die Anzahl der Artikel, die für jeden gekauften Artikel aus der letzten Transaktion des Käufers abgezogen werden.
Wie wir sehen, zeigt die Konfiguration mit k=4 das beste Ergebnis. Der Anstieg in Woche 4 kann durch saisonale Verhaltensweisen während der Feiertage erklärt werden. 

Ähnliche Produkte für Käufer, basierend auf Merkmalen, die von verschiedenen Modellen erstellt wurden

Hier sind wir am schwierigsten und interessantesten Teil angekommen – der Suche nach den nächsten Nachbarn anhand von Käufern- und Produktvektoren, die mit verschiedenen Modellen erstellt wurden. In unserer Arbeit verwenden wir dafür 3 Modelle:

• ALS
• Word2Vec (Item2Vec für solche Aufgaben)
• DSSM

Mit ALS haben wir uns bereits befasst, wer mehr über das Training erfahren möchte, kann lesen hier. Im Fall von Word2Vec verwenden wir die allgemein bekannte Implementierung des Modells aus gensim. Analog zu Texten definieren wir eine Transaktion als einen Einkaufsbeleg. Auf diese Weise lernt das Modell beim Erstellen des Produktvektors, den "Kontext" des Produkts (die anderen Produkte im Einkaufsbeleg) vorherzusagen. Bei E-Commerce-Daten ist es besser, anstelle des Belegs die Sitzung des Käufers zu verwenden, hierzu haben die Jungs von Ozontoll geschrieben. DSSM zu zerlegen, ist interessanter. Ursprünglich wurde es von den Jungs von Microsoft als Modell für die Suche entwickelt, hier kann man das ursprüngliche Forschungspapier lesen. Die Architektur des Modells sieht so aus:

Hier Q — query, die Benutzerabfrage, D[i] — document, die Internetseite. Bei der Eingabe des Modells werden die Merkmale der Anfrage und der Seiten verwendet. Nach jeder Eingangsschicht geht eine gewisse Anzahl von vollständig verbundenen Schichten (multilayer perceptron) einher. Danach lernt das Modell, den Kosinus zwischen den Vektoren, die in den letzten Schichten des Modells entstehen, zu minimieren.
In Empfehlungsaufgaben wird genau die gleiche Architektur verwendet, nur dass anstelle der Anfrage der Benutzer und anstelle der Seiten die Produkte kommen. In unserem Fall wird diese Architektur in Folgendes transformiert:

Jetzt bleibt für die Überprüfung der Ergebnisse nur noch ein letzter Punkt zu klären – während bei ALS und DSSM die Benutzervektoren klar definiert sind, haben wir bei Word2Vec nur die Produktvektoren. Hier haben wir für den Aufbau des Benutzervektors 3 Hauptansätze definiert:

1. Einfach die Vektoren addieren, dann ergibt sich für den kosinus-ähnlichen Abstand, dass wir die Produkte in der Einkaufsgeschichte einfach gemittelt haben.
2. Die Vektoren mit einer gewissen zeitlichen Gewichtung summieren.
3. Gewichtung der Produkte mit dem TF-IDF-Koeffizienten.

Im Falle der linearen Gewichtung des Käufervektors gehen wir davon aus, dass das Produkt, das der Nutzer gestern gekauft hat, stärker sein Verhalten beeinflusst, als das Produkt, das er vor einem halben Jahr gekauft hat. Daher betrachten wir die letzte Woche des Käufers mit einem Koeffizienten von 1 und was davor war mit Koeffizienten von ½, ⅓ usw.:

Für die TF-IDF-Koeffizienten machen wir genau dasselbe wie bei TF-IDF für Texte, nur dass wir den Käufer als Dokument betrachten und den Kassenbon als Angebot, entsprechend ist das Wort das Produkt. So wird der Vektor des Nutzers stärker in Richtung seltener Produkte verschoben, während häufige und für den Käufer vertraute Produkte ihn nicht besonders verändern werden. Dieser Ansatz lässt sich folgendermaßen veranschaulichen:

Schauen wir uns nun die Metriken an. So sehen die Ergebnisse von ALS aus:

Metriken für Item2Vec mit verschiedenen Varianten der Erstellung des Käufervektors:

In diesem Fall wird genau dasselbe Modell verwendet, das auch in unserem Baseline verwendet wird. Der einzige Unterschied besteht darin, welches k wir verwenden werden. Um nur kollaborative Modelle zu verwenden, müssen wir etwa 50-70 nächstgelegene Produkte für jeden Käufer nehmen.

Und die Metriken für DSSM:

Wie kombiniert man all diese Methoden?

Toll, werden Sie sagen, aber was machen wir mit einem so großen Set an Werkzeugen zur Kandidatenauswahl? Wie findet man die optimale Konfiguration für seine Daten? Hier ergeben sich mehrere Aufgaben:

1. Wir müssen den Suchraum der Hyperparameter in jeder Methode irgendwie einschränken. Es ist natürlich überall diskret, aber die Anzahl möglicher Punkte ist sehr groß.
2. Wie kann man aus einer kleinen, begrenzten Stichprobe spezifischer Methoden mit spezifischen Hyperparametern die beste Konfiguration für seine Metrik auswählen?

Auf die erste Frage haben wir bisher keine eindeutig richtige Antwort gefunden, daher gehen wir von Folgendem aus: Für jede Methode wurde ein Begrenzung des Suchraums der Hyperparameter in Abhängigkeit von bestimmten Statistiken der uns vorliegenden Daten erstellt. So können wir, wenn wir den durchschnittlichen Zeitraum zwischen Käufen der Menschen kennen, annehmen, mit welchem Zeitraum wir die Methode 'was bereits gekauft wurde' und 'Zeitraum seit einem langen vergangenen Kauf' verwenden sollten.

Nachdem wir eine angemessene Anzahl an Variationen verschiedener Methoden durchgesehen haben, stellen wir Folgendes fest: Jede Implementierung extrahiert eine bestimmte Anzahl an Kandidaten und hat einen bestimmten Wert für unsere wichtige Kennzahl (Recall). Wir möchten insgesamt eine bestimmte Anzahl an Kandidaten erhalten, abhängig von unseren verfügbaren Rechenressourcen, mit der höchstmöglichen Kennzahl. Hier wird die Aufgabe elegant zu einem Rucksackproblem.

Hierbei entspricht die Anzahl der Kandidaten dem Gewicht des Goldbarrens, und der Recall der Methode entspricht seinem Wert. Es gibt jedoch noch zwei weitere Aspekte, die bei der Implementierung des Algorithmus berücksichtigt werden sollten:

• Bei den Methoden kann es zu Überschneidungen bei den Kandidaten kommen, die sie extrahieren.
• In einigen Fällen kann es sinnvoll sein, eine Methode zweimal mit unterschiedlichen Parametern anzuwenden, und die Kandidaten aus der ersten Methode sind kein Untermenge der zweiten.

Wenn man zum Beispiel die Implementierung der Methode "Was bereits gekauft wurde" mit unterschiedlichen Intervallen zur Extraktion verwendet, werden ihre Mengen an Kandidaten ineinander verschachtelt sein. Gleichzeitig liefern unterschiedliche Parameter bei "periodischen Käufen" jedoch kein vollständiges Überlappen. Daher teilen wir die Sampling-Methoden mit unterschiedlichen Parametern in Blöcke auf, sodass wir aus jedem Block nicht mehr als einen Extraktionsansatz mit bestimmten Hyperparametern übernehmen möchten. Dazu muss man bei der Implementierung des Rucksackproblems etwas tricksen, aber die Asymptotik und das Ergebnis bleiben davon unberührt.

Diese geschickte Kombination ermöglicht es uns, die folgenden Kennzahlen im Vergleich zu einfachen kollaborativen Modellen zu erhalten:

Bei den finalen Kennzahlen sehen wir folgendes Bild:

Hierbei ist jedoch zu beachten, dass ein Punkt für Empfehlungen, die für Unternehmen nützlich sind, noch nicht abgedeckt ist. Derzeit haben wir einfach gelernt, genau vorherzusagen, was der Benutzer beispielsweise in der nächsten Woche kaufen wird. Doch einfach Rabatt auf das zu geben, was er sowieso kaufen wird, ist nicht besonders spannend. Viel spannender ist es, das Erwartungswert zu maximieren, beispielsweise der folgenden Kennzahlen:

1. Die Marge/Umsatz durch personalisierte Empfehlungen.
2. Der durchschnittliche Einkaufswert der Kunden.
3. Die Besuchshäufigkeit.

So, we multiply the obtained probabilities by different coefficients and rearrange them so that products influencing the metrics more are at the top. There is no ready-made solution for which approach is better to use. Even we experiment with such coefficients directly in production. But here are some interesting techniques that most often yield the best results for us:

1. Multiply by the price/margin of the product.
2. Multiply by the average check in which the product appears. This way, products that are usually bought together with something else will rise to the top.
3. Multiply by the average visit frequency of customers for this product, based on the hypothesis that this product encourages them to return more often.

After experimenting with the coefficients, we obtained the following metrics in production:

Hier overall products conversion — the share of purchased products from all products in the recommendations that we generated.

The attentive reader will notice a significant difference between offline and online metrics. This behavior can be explained by the fact that not all dynamic filters for products recommended can be taken into account when training the model. It is normal for us that half of the extracted candidates can be filtered out; this specificity is characteristic of our industry.

In terms of revenue, the following story emerges; it is clear that after launching the recommendations, the revenue for the test group significantly increases, and currently, the average increase in revenue with our recommendations is 3-4%.

In conclusion, I want to say that if you need non-realtime recommendations, there is a significant increase in quality when experimenting with candidate extraction for recommendations. A lot of time spent on their generation allows for the combination of many good methods, which together produce great results for the business.

I would be happy to discuss in the comments with anyone who finds the material interesting. Questions can be directed to me personally at Telegram. I also share my thoughts on AI/startups in my Telegram-Kanal — welcome 🙂

Quelle: habr.com