Hallo zusammen! Mein Name ist Sasha, ich bin CTO und Mitbegründer von LoyaltyLab. Vor zwei Jahren gingen meine Freunde und ich, wie alle armen Studenten, abends zum nächsten Laden in der Nähe unseres Hauses, um Bier zu kaufen. Wir waren sehr verärgert darüber, dass der Einzelhändler, obwohl er wusste, dass wir Bier holen würden, keinen Rabatt auf Chips oder Cracker anbot, obwohl das so logisch war! Wir verstanden nicht, warum diese Situation eintrat, und beschlossen, unser eigenes Unternehmen zu gründen. Nun, als Bonus gönnen Sie sich jeden Freitag Rabatte auf dieselben Chips.

Und das alles kam zu dem Punkt, an dem ich Material zur technischen Seite des Produkts präsentiere NVIDIA AGB. Da wir unsere Arbeit gerne mit der Community teilen, veröffentliche ich meinen Bericht in Form eines Artikels.

Einführung

Wie alle anderen haben wir zu Beginn der Reise mit einem Überblick darüber begonnen, wie Empfehlungssysteme hergestellt werden. Und die beliebteste Architektur erwies sich als folgender Typ:

Es besteht aus zwei Teilen:

1. Auswahl von Kandidaten für Empfehlungen mithilfe eines einfachen und schnellen Modells, normalerweise eines kollaborativen Modells.
2. Ranking von Kandidaten mit einem komplexeren und langsameren Inhaltsmodell unter Berücksichtigung aller möglichen Merkmale in den Daten.

Im Folgenden verwende ich die folgenden Begriffe:

• Kandidat/Kandidat für Empfehlungen – ein Benutzer-Produkt-Paar, das möglicherweise in Empfehlungen in der Produktion einbezogen werden könnte.
• Kandidatenextraktion/Extraktor/Kandidatenextraktionsmethode – ein Prozess oder eine Methode zur Extraktion von „Empfehlungskandidaten“ aus verfügbaren Daten.

Der erste Schritt besteht normalerweise darin, verschiedene Varianten der kollaborativen Filterung zu verwenden. Die beliebtesten - ALS. Es ist überraschend, dass die meisten Artikel über Empfehlungssysteme nur verschiedene Verbesserungen an kollaborativen Modellen in der ersten Phase offenbaren, aber niemand spricht viel über andere Stichprobenmethoden. Für uns funktionierte der Ansatz, nur kollaborative Modelle zu verwenden und verschiedene Optimierungen damit durchzuführen, nicht mit der erwarteten Qualität, weshalb wir uns speziell auf diesen Teil der Forschung konzentrierten. Und am Ende des Artikels werde ich zeigen, wie sehr wir ALS verbessern konnten, was unser Ausgangswert war.

Bevor ich zur Beschreibung unseres Ansatzes übergehe, ist es wichtig zu beachten, dass es bei Echtzeitempfehlungen, bei denen es für uns wichtig ist, Daten zu berücksichtigen, die vor 30 Minuten aufgetreten sind, wirklich nicht viele Ansätze gibt, die in der erforderlichen Zeit funktionieren können. Aber in unserem Fall müssen wir Empfehlungen nur einmal am Tag einholen, in den meisten Fällen sogar einmal pro Woche, was uns die Möglichkeit gibt, komplexe Modelle zu verwenden und die Qualität um ein Vielfaches zu verbessern.

Nehmen wir als Grundlage, welche Metriken nur ALS für die Aufgabe der Kandidatenextraktion anzeigt. Die wichtigsten Kennzahlen, die wir überwachen, sind:

• Präzision – der Anteil richtig ausgewählter Kandidaten aus der Stichprobe.
• Der Recall ist der Anteil der Kandidaten, die tatsächlich im Zielintervall waren.
• F1-Score – F-Maß, berechnet anhand der beiden vorherigen Punkte.

Wir werden uns auch die Metriken des endgültigen Modells ansehen, nachdem wir die Gradientenverstärkung mit zusätzlichen Inhaltsfunktionen trainiert haben. Auch hier gibt es drei Hauptmetriken:

• precision@5 – der durchschnittliche Prozentsatz der Produkte aus den Top 5 in Bezug auf die Wahrscheinlichkeit für jeden Käufer.
• Response-Rate@5 – Konvertierung der Kunden von einem Ladenbesuch zum Kauf von mindestens einem persönlichen Angebot (5 Produkte in einem Angebot).
• Durchschn. Roc-AUC pro Benutzer – Durchschnitt roc-auc für jeden Käufer.

Es ist wichtig zu beachten, dass alle diese Kennzahlen gemessen werden Zeitreihen-KreuzvalidierungDas heißt, das Training findet in den ersten k Wochen statt und k+1 Woche werden als Testdaten verwendet. Daher hatten saisonale Schwankungen nur minimale Auswirkungen auf die Interpretation der Qualität der Modelle. Darüber hinaus zeigt die Abszissenachse in allen Diagrammen die Wochennummer der Kreuzvalidierung und die Ordinatenachse den Wert der angegebenen Metrik an. Alle Diagramme basieren auf Transaktionsdaten eines Kunden, sodass Vergleiche untereinander korrekt sind.

Bevor wir beginnen, unseren Ansatz zu beschreiben, werfen wir zunächst einen Blick auf die Basislinie, bei der es sich um ein ALS-trainiertes Modell handelt.
Kennzahlen zum Kandidatenabruf:

Endgültige Kennzahlen:

Ich behandle alle Implementierungen von Algorithmen als eine Art Geschäftshypothese. Grob lässt sich also jedes Kooperationsmodell als Hypothese betrachten, dass „Menschen dazu neigen, das zu kaufen, was ihnen ähnliche Leute kaufen.“ Wie ich bereits sagte, haben wir uns nicht nur auf diese Semantik beschränkt, und hier sind einige Hypothesen, die bei Daten im Offline-Einzelhandel gut funktionieren:

1. Was ich schon einmal gekauft habe.
2. Ähnlich wie das, was ich vorher gekauft habe.
3. Zeitraum eines längst vergangenen Kaufs.
4. Beliebt nach Kategorie/Marke.
5. Abwechselnder Einkauf verschiedener Waren von Woche zu Woche (Markov-Ketten).
6. Ähnliche Produkte für Käufer, je nach Eigenschaften, die von verschiedenen Modellen (Word2Vec, DSSM usw.) erstellt wurden.

Was hast du vorher gekauft?

Die offensichtlichste Heuristik, die im Lebensmitteleinzelhandel sehr gut funktioniert. Hier nehmen wir alle Waren auf, die der Kundenkarteninhaber in den letzten K Tagen (normalerweise 1–3 Wochen) oder K Tagen vor einem Jahr gekauft hat. Wenn wir nur diese Methode anwenden, erhalten wir die folgenden Metriken:

Hier ist es ziemlich offensichtlich, dass wir umso mehr Erinnerung haben und umso weniger Präzision haben, je länger wir den Zeitraum nehmen, und umgekehrt. Im Durchschnitt liefern die „letzten 2 Wochen“ bessere Ergebnisse für die Kunden.

Ähnlich wie das, was ich vorher gekauft habe

Es ist nicht verwunderlich, dass im Lebensmitteleinzelhandel „was ich vorher gekauft habe“ gut funktioniert, aber Kandidaten nur aus dem zu extrahieren, was der Benutzer bereits gekauft hat, ist nicht sehr cool, da es unwahrscheinlich ist, dass der Käufer mit einem neuen Produkt überrascht wird. Daher schlagen wir vor, diese Heuristik unter Verwendung derselben kollaborativen Modelle leicht zu verbessern. Aus den Vektoren, die wir während des ALS-Trainings erhalten haben, können wir ähnliche Produkte erhalten wie die, die der Benutzer bereits gekauft hat. Diese Idee ist den „ähnlichen Videos“ in Diensten zum Ansehen von Videoinhalten sehr ähnlich, aber da wir nicht wissen, was der Benutzer zu einem bestimmten Zeitpunkt isst/kauft, können wir nur nach ähnlichen Videos suchen, insbesondere nach denen, die er bereits gekauft hat Da wir Wir wissen bereits, wie gut es funktioniert. Wenn wir diese Methode auf Benutzertransaktionen in den letzten zwei Wochen anwenden, erhalten wir die folgenden Messwerte:

Hier k — die Anzahl ähnlicher Produkte, die für jedes vom Käufer in den letzten 14 Tagen gekaufte Produkt abgerufen werden.
Dieser Ansatz funktionierte besonders gut für unseren Kunden, für den es wichtig war, nichts zu empfehlen, was sich bereits in der Kaufhistorie des Benutzers befand.

Späte Kauffrist

Wie wir bereits herausgefunden haben, eignet sich der erste Ansatz aufgrund der hohen Kauffrequenz für unsere spezifischen Bedürfnisse gut. Aber was ist mit Waren wie Waschpulver/Shampoo/etc. Das heißt, mit Produkten, die wahrscheinlich nicht alle ein bis zwei Wochen benötigt werden und die mit bisherigen Methoden nicht extrahiert werden können. Dies führt zu folgender Idee: Es wird vorgeschlagen, die durchschnittliche Kaufdauer jedes Produkts für Kunden zu berechnen, die das Produkt häufiger gekauft haben k einmal. Und dann extrahieren Sie, was dem Käufer höchstwahrscheinlich bereits ausgegangen ist. Die berechneten Warenfristen können Sie mit Ihren Augen auf Angemessenheit überprüfen:

Und dann schauen wir uns an, ob das Ende des Produktzeitraums in den Zeitraum fällt, in dem die Empfehlungen in Produktion gehen und probieren, was passiert. Der Ansatz lässt sich wie folgt veranschaulichen:

Hier haben wir zwei Hauptfälle, die berücksichtigt werden können:

1. Ist es notwendig, Produkte von Kunden zu testen, die das Produkt weniger als K-mal gekauft haben?
2. Ist es notwendig, ein Produkt zu bemustern, wenn das Ende seines Zeitraums vor dem Beginn des Zielintervalls liegt?

Die folgende Grafik zeigt, welche Ergebnisse diese Methode mit verschiedenen Hyperparametern erzielt:

ft — Nehmen Sie nur Kunden, die das Produkt mindestens K-mal (hier K=5) gekauft haben
tm — Nehmen Sie nur Kandidaten auf, die innerhalb des Zielintervalls liegen

Es ist nicht überraschend, dass er dazu in der Lage ist (0, 0) größte erinnern und der Kleinste Präzision, da unter dieser Bedingung die meisten Kandidaten gefunden werden. Die besten Ergebnisse werden jedoch erzielt, wenn wir keine Produktproben für Kunden durchführen, die ein bestimmtes Produkt weniger als gekauft haben k Zeiten und Extrakt, einschließlich Waren, deren Ende vor dem Zielintervall liegt.

Beliebt nach Kategorie

Eine weitere ziemlich naheliegende Idee besteht darin, beliebte Produkte verschiedener Kategorien oder Marken auszuprobieren. Hier berechnen wir für jeden Käufer top-k „Lieblings“-Kategorien/Marken und extrahieren Sie „beliebt“ aus dieser Kategorie/Marke. In unserem Fall ermitteln wir „Favorit“ und „Beliebt“ anhand der Anzahl der Käufe des Produkts. Ein zusätzlicher Vorteil dieses Ansatzes ist seine Anwendbarkeit im Kaltstartfall. Das heißt für Kunden, die entweder nur sehr wenig eingekauft haben, längere Zeit nicht im Geschäft waren oder gerade eine Kundenkarte ausgestellt haben. Für sie ist es einfacher und besser, Artikel auf Lager zu haben, die bei den Kunden beliebt sind und eine Geschichte haben. Die resultierenden Kennzahlen sind:

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

Insgesamt ist es auch nicht verwunderlich, dass engere Kategorien bessere Ergebnisse erzielen, da sie genauere „Lieblings“-Produkte für Käufer extrahieren.

Abwechselnder Einkauf verschiedener Waren von Woche zu Woche

Ein interessanter Ansatz, den ich in Artikeln über Empfehlungssysteme noch nicht gesehen habe, ist eine recht einfache und gleichzeitig funktionierende statistische Methode von Markov-Ketten. Hier nehmen wir uns 2 verschiedene Wochen Zeit, dann bauen wir für jeden Kunden Produktpaare [gekauft in Woche i]-[gekauft in Woche j], wobei j > i, und von hier aus berechnen wir für jedes Produkt die Wahrscheinlichkeit, nächste Woche auf ein anderes Produkt umzusteigen. Das heißt, für jedes Warenpaar Produkti-Produktj Wir zählen ihre Anzahl in den gefundenen Paaren und dividieren durch die Anzahl der Paare, wo Produkti war in der ersten Woche. Um Kandidaten zu extrahieren, nehmen wir die letzte Quittung des Käufers und extrahieren sie top-k die wahrscheinlichsten nächsten Produkte aus der Übergangsmatrix, die wir erhalten haben. Der Prozess zum Erstellen einer Übergangsmatrix sieht folgendermaßen aus:

Anhand realer Beispiele in der Übergangswahrscheinlichkeitsmatrix sehen wir die folgenden interessanten Phänomene:

Hier lassen sich interessante Abhängigkeiten erkennen, die sich im Konsumentenverhalten offenbaren: etwa Liebhaber von Zitrusfrüchten oder einer Milchmarke, von der sie mit großer Wahrscheinlichkeit auf eine andere umsteigen. Es ist auch nicht verwunderlich, dass auch Produkte mit hoher Wiederkaufsfrequenz, wie zum Beispiel Butter, hier landen.

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

k — die Anzahl der Produkte, die für jedes gekaufte Produkt aus der letzten Transaktion des Käufers abgerufen wurden.
Wie wir sehen, zeigt die Konfiguration mit k=4 das beste Ergebnis. Der Anstieg in Woche 4 kann durch saisonales Verhalten rund um die Feiertage erklärt werden. 

Ähnliche Produkte für Käufer, je nach Eigenschaften, die von verschiedenen Modellen gebaut wurden

Jetzt sind wir beim schwierigsten und interessantesten Teil angelangt – der Suche nach nächsten Nachbarn auf der Grundlage von Kunden- und Produktvektoren, die nach verschiedenen Modellen erstellt wurden. In unserer Arbeit verwenden wir 3 solcher Modelle:

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

Wir haben uns bereits mit ALS beschäftigt, Sie können nachlesen, wie es lernt hier. Im Fall von Word2Vec verwenden wir die bekannte Implementierung des Modells von Gensim. Analog zu den Texten verstehen wir das Angebot als Kaufbeleg. Bei der Konstruktion eines Produktvektors lernt das Modell also, für das Produkt im Beleg seinen „Kontext“ (die übrigen Produkte im Beleg) vorherzusagen. Bei E-Commerce-Daten ist es besser, die Sitzung des Käufers anstelle einer Quittung zu verwenden; die Jungs von Ozon. Und DSSM ist interessanter zu analysieren. Ursprünglich wurde es von den Jungs von Microsoft als Modell für die Suche geschrieben, Den Original-Forschungsbericht können Sie hier lesen. Die Architektur des Modells sieht folgendermaßen aus:

Hier Q — Abfrage, Benutzersuchanfrage, D[i] — Dokument, Internetseite. Die Eingabe in das Modell sind die Attribute der Anfrage bzw. der Seiten. Nach jeder Eingabeschicht gibt es eine Reihe vollständig verbundener Schichten (mehrschichtiges Perzeptron). Als nächstes lernt das Modell, den Kosinus zwischen den in den letzten Schichten des Modells erhaltenen Vektoren zu minimieren.
Empfehlungsaufgaben verwenden genau die gleiche Architektur, nur gibt es anstelle einer Anfrage einen Benutzer und anstelle von Seiten Produkte. Und in unserem Fall wird diese Architektur wie folgt umgewandelt:

Um nun die Ergebnisse zu überprüfen, muss noch der letzte Punkt behandelt werden: Wenn wir im Fall von ALS und DSSM explizit Benutzervektoren definiert haben, dann haben wir im Fall von Word2Vec nur Produktvektoren. Um den Benutzervektor zu erstellen, haben wir hier drei Hauptansätze definiert:

1. Fügen Sie einfach die Vektoren hinzu, dann stellt sich für den Kosinusabstand heraus, dass wir einfach den Durchschnitt der Produkte in der Einkaufshistorie gebildet haben.
2. Vektorsummierung mit etwas Zeitgewichtung.
3. Wiegen von Gütern mit TF-IDF-Koeffizient.

Bei der linearen Gewichtung des Käufervektors gehen wir von der Hypothese aus, dass das Produkt, das der Nutzer gestern gekauft hat, einen größeren Einfluss auf sein Verhalten hat als das Produkt, das er vor sechs Monaten gekauft hat. Wir betrachten also die Vorwoche des Käufers mit einer Quote von 1 und das, was als Nächstes geschah, mit einer Quote von ½, ⅓ usw.:

Bei den TF-IDF-Koeffizienten machen wir genau das Gleiche wie bei TF-IDF für Texte, nur betrachten wir den Käufer als Dokument und den Scheck als Angebot bzw. das Wort als Produkt. Auf diese Weise verschiebt sich der Fokus des Nutzers stärker auf seltene Güter, während häufige und vertraute Güter für den Käufer daran kaum etwas ändern. Der Ansatz lässt sich wie folgt veranschaulichen:

Schauen wir uns nun die Kennzahlen an. So sehen die ALS-Ergebnisse aus:

Metriken für Item2Vec mit verschiedenen Variationen der Konstruktion des Käufervektors:

In diesem Fall wird genau das gleiche Modell wie in unserer Basislinie verwendet. Der einzige Unterschied besteht darin, welches k wir verwenden werden. Um nur kollaborative Modelle zu nutzen, müssen Sie für jeden Kunden etwa 50-70 nächstliegende Produkte nehmen.

Und Kennzahlen laut DSSM:

Wie kombiniere ich alle Methoden?

Cool, sagen Sie, aber was tun mit einem so großen Satz an Tools zur Kandidatenextraktion? Wie wählen Sie die optimale Konfiguration für Ihre Daten? Hier haben wir mehrere Probleme:

1. Es ist notwendig, den Suchraum für Hyperparameter in jeder Methode irgendwie einzuschränken. Es ist natürlich überall diskret, aber die Anzahl der möglichen Punkte ist sehr groß.
2. Wie können Sie anhand einer kleinen, begrenzten Stichprobe spezifischer Methoden mit spezifischen Hyperparametern die beste Konfiguration für Ihre Metrik auswählen?

Auf die erste Frage haben wir noch keine definitiv richtige Antwort gefunden, daher gehen wir wie folgt vor: Für jede Methode wird ein Hyperparameter-Suchraumbegrenzer geschrieben, abhängig von einigen Statistiken zu den uns vorliegenden Daten. Wenn wir also den durchschnittlichen Zeitraum zwischen Käufen von Personen kennen, können wir erraten, mit welchem ​​Zeitraum die Methode „was bereits gekauft wurde“ und „Zeitraum eines längst zurückliegenden Kaufs“ verwendet werden soll.

Und nachdem wir eine bestimmte ausreichende Anzahl von Variationen verschiedener Methoden durchlaufen haben, stellen wir Folgendes fest: Jede Implementierung extrahiert eine bestimmte Anzahl von Kandidaten und hat für uns einen bestimmten Wert der Schlüsselmetrik (Rückruf). Wir möchten insgesamt eine bestimmte Anzahl an Kandidaten, abhängig von unserer zulässigen Rechenleistung, mit einer möglichst hohen Metrik erhalten. Hier lässt sich das Problem wunderbar in das Rucksackproblem integrieren.

Hier ist die Anzahl der Kandidaten das Gewicht des Barrens und die Rückrufmethode sein Wert. Es gibt jedoch noch zwei weitere Punkte, die bei der Implementierung des Algorithmus berücksichtigt werden sollten:

• Die Methoden können sich bei den von ihnen abgerufenen Kandidaten überschneiden.
• In einigen Fällen ist es richtig, eine Methode zweimal mit unterschiedlichen Parametern zu verwenden, und die Kandidatenausgabe der ersten Methode ist keine Teilmenge der zweiten.

Nehmen wir beispielsweise die Implementierung der Methode „Was ich bereits gekauft habe“ mit unterschiedlichen Abrufintervallen, dann werden ihre Kandidatensätze ineinander verschachtelt. Gleichzeitig bieten unterschiedliche Parameter bei „periodischen Käufen“ am Ausgang keinen vollständigen Schnittpunkt. Daher unterteilen wir die Sampling-Ansätze mit unterschiedlichen Parametern in Blöcke, so dass wir aus jedem Block höchstens einen Extraktionsansatz mit spezifischen Hyperparametern nehmen wollen. Um dies zu erreichen, müssen Sie bei der Umsetzung des Rucksackproblems ein wenig geschickt vorgehen, aber die Asymptotik und das Ergebnis werden sich nicht ändern.

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

In den endgültigen Metriken sehen wir das folgende Bild:

Allerdings fällt hier auf, dass es einen ungedeckten Punkt für Empfehlungen gibt, die für das Unternehmen nützlich sind. Jetzt haben wir gerade gelernt, wie man hervorragend vorhersagen kann, was der Benutzer beispielsweise nächste Woche kaufen wird. Aber einfach einen Rabatt auf etwas zu gewähren, das er bereits kaufen wird, ist nicht sehr cool. Aber es ist cool, die Erwartungen beispielsweise an die folgenden Kennzahlen zu maximieren:

1. Marge/Umsatz basierend auf persönlichen Empfehlungen.
2. Durchschnittlicher Kundenscheck.
3. Häufigkeit der Besuche.

Also multiplizieren wir die erhaltenen Wahrscheinlichkeiten mit verschiedenen Koeffizienten und ordnen sie neu, sodass die Produkte, die die oben genannten Metriken beeinflussen, ganz oben stehen. Es gibt keine vorgefertigte Lösung, welcher Ansatz am besten geeignet ist. Mit solchen Koeffizienten experimentieren wir sogar direkt in der Produktion. Aber hier sind interessante Techniken, die uns am häufigsten die besten Ergebnisse liefern:

1. Mit dem Preis/der Marge des Produkts multiplizieren.
2. Mit dem durchschnittlichen Beleg multiplizieren, in dem das Produkt erscheint. Es werden also Waren entstehen, mit denen sie normalerweise etwas anderes nehmen.
3. Multiplizieren Sie dies mit der durchschnittlichen Besuchshäufigkeit von Käufern dieses Produkts, basierend auf der Hypothese, dass dieses Produkt Menschen dazu verleitet, öfter zurückzukommen, um es zu kaufen.

Nach der Durchführung von Experimenten mit Koeffizienten haben wir in der Produktion die folgenden Metriken erhalten:

Hier Gesamtproduktumwandlung — der Anteil der gekauften Produkte an allen Produkten in den von uns generierten Empfehlungen.

Ein aufmerksamer Leser wird einen erheblichen Unterschied zwischen Offline- und Online-Metriken bemerken. Dieses Verhalten erklärt sich dadurch, dass nicht alle dynamischen Filter für empfehlenswerte Produkte beim Training des Modells berücksichtigt werden können. Für uns ist es normal, dass die Hälfte der gefundenen Kandidaten herausgefiltert werden kann; diese Besonderheit ist typisch für unsere Branche.

In Bezug auf den Umsatz ergibt sich die folgende Geschichte, es ist klar, dass nach der Einführung der Empfehlungen der Umsatz der Testgruppe stark wächst, jetzt beträgt die durchschnittliche Umsatzsteigerung mit unseren Empfehlungen 3-4 %:

Abschließend möchte ich sagen, dass, wenn Sie Empfehlungen benötigen, die nicht in Echtzeit erfolgen, eine sehr große Qualitätssteigerung durch Experimente mit der Extraktion von Kandidaten für Empfehlungen erzielt werden kann. Ein großer Zeitaufwand für ihre Entwicklung ermöglicht die Kombination vieler guter Methoden, die in der Summe zu großartigen Ergebnissen für das Unternehmen führen.

Ich freue mich, in den Kommentaren mit jedem zu chatten, der das Material interessant findet. Fragen können Sie mir persönlich unter stellen Telegram mit. Ich teile auch meine Gedanken über KI/Startups in meinem Telegrammkanal - Willkommen :)

Source: habr.com