Dynamisches Remarketing (Dynrem) in myTarget ist eine zielgerichtete Werbetechnologie, die Informationen zu Benutzeraktionen auf Websites und in mobilen Anwendungen von Werbetreibenden verwendet. In einem Online-Shop hat ein Benutzer beispielsweise die Warenseiten angezeigt oder in den Warenkorb gelegt, und myTarget verwendet diese Ereignisse, um Werbung für genau die Waren und Dienstleistungen anzuzeigen, für die eine Person bereits Interesse gezeigt hat. Heute werde ich detaillierter auf den Mechanismus zur Generierung nicht persönlicher, dh item2item-Empfehlungen eingehen, mit denen wir die Werbeausgabe diversifizieren und ergänzen können.

Die Kunden von dynrem myTarget sind hauptsächlich Online-Shops, die eine oder mehrere Produktlisten haben können. Bei der Erstellung von Empfehlungen sollte das Paar „Lager - Warenliste“ als separate Einheit betrachtet werden. Der Einfachheit halber werden wir als nächstes einfach den "Laden" verwenden. Wenn wir über die Dimension der Eingabeaufgabe sprechen, sollten Empfehlungen für etwa tausend Geschäfte erstellt werden, und die Anzahl der Waren kann zwischen mehreren tausend und Millionen variieren.

Das Empfehlungssystem für Dynrem muss die folgenden Anforderungen erfüllen:

1. Das Banner enthält Produkte, die die Klickrate maximieren.
2. Empfehlungen werden für eine bestimmte Zeit offline erstellt.
3. Die Systemarchitektur muss flexibel, skalierbar, stabil und in einer Kaltstartumgebung funktionieren.

Beachten Sie, dass sich aus der Anforderung, Empfehlungen für eine feste Zeit und die beschriebenen Anfangsbedingungen zu erstellen (wir gehen optimistisch davon aus, dass die Anzahl der Filialen zunimmt), natürlich eine Anforderung für den wirtschaftlichen Einsatz von Maschinenressourcen ergibt.

Abschnitt 2 enthält die theoretischen Grundlagen für den Aufbau von Empfehlungssystemen, die Abschnitte 3 und 4 erörtern die praktische Seite des Problems und Abschnitt 5 fasst das Gesamtergebnis zusammen.

Grundbegriffe

Betrachten Sie die Aufgabe, ein Empfehlungssystem für ein Geschäft aufzubauen, und listen Sie die grundlegenden mathematischen Ansätze auf.

Singular Value Decomposition (SVD)

Ein beliebter Ansatz zum Aufbau von Empfehlungssystemen ist der SVD-Ansatz (Singular Decomposition). Bewertungsmatrix $$$R = (r_ {ui})$ als Produkt zweier Matrizen darstellen $$$P$ und $$$Q$ so dass $$$R \ ca. P Q ^ T$ dann Bewertung Benutzerbewertung $$$u$ für Waren $$$i$ dargestellt als $$$\ hat {r} _ {ui} = <p_u, q_i>$ [1], wobei die Elemente des Skalarprodukts Dimensionsvektoren sind $$$k$ (Hauptparameter des Modells). Diese Formel dient als Grundlage für andere SVD-Modelle. Die Aufgabe zu finden $$$P$ und $$$Q$ Es kommt auf die Optimierung der Funktionalität an:

(2.1)

$$

$$J (P, Q) = \ sum _ {(u, i)} \ mathcal {L} (r_ {ui}, \ hat {r} _ {ui}) + \ Lambda (P, Q) \ rightarrow \ min_ {P, Q},$$

wo $$$L$ - Fehlerfunktion (zum Beispiel RMSE wie im Netflix- Wettbewerb), $$$Λ$ - Regularisierung, und die Summierung erfolgt über Paare, für die die Bewertung bekannt ist. Wir schreiben Ausdruck (2.1) in einer expliziten Form um:

(2.2)

$$

$$J (P, Q) = \ sum _ {(u, i)} (r_ {ui} - <p_u, q_i>) ^ 2 + \ lambda_1 || p_u || ^ 2 + \ lambda_2 || q_i || ^ 2 \ rightarrow \ min_ {P, Q},$$

Hier $$$λ1$ , $$$λ2$ - L2-Regularisierungskoeffizienten für Benutzerdarstellungen $$$p_ {u}$ und Waren $$$q_ {i}$ entsprechend. Das Grundmodell für den Netflix-Wettbewerb war:

(2.3)

$$

$$\ hat {r} _ {ui} = \ mu + b_u + b_i + <p_u, q_i>,$$

(2.4)

$$

$$J (P, Q) = \ sum _ {(u, i)} (r_ {ui} - \ mu - b_u - b_i - <p_u, q_i>) ^ 2 + \ lambda_1 || p_u || ^ 2 + \ lambda_2 || q_i || ^ 2 + \ lambda_3 b_u ^ 2 + \ lambda_4 b_i ^ 2 \ rightarrow \ min_ {P, Q},$$

wo $$$µ$ , $$$b_ {u}$ und $$$b_ {i}$ - Vorurteile für Bewertung, Benutzer bzw. Produkt. Das Modell (2.3) - (2.4) kann durch Hinzufügen einer impliziten Benutzerpräferenz verbessert werden. Im Netflix-Wettbewerbsbeispiel ist die explizite Antwort die vom Benutzer auf den Film „auf unsere Anfrage“ festgelegte Punktzahl und andere Informationen zur „Benutzerinteraktion mit dem Produkt“ (Anzeigen des Films, seiner Beschreibung, Bewertungen darauf; dh die implizite Antwort gibt keine implizite Antwort). direkte Informationen über die Bewertung des Films, zeigt aber gleichzeitig Interesse). Die implizite Antwortabrechnung ist im SVD ++ - Modell implementiert:

(2.5)

$$

$$\ hat {r} _ {ui} = \ mu + b_u + b_i + <p_u + \ frac {1} {\ sqrt {\ sigma_u}} \ sum_ {j \ in S (u)} y_j, \, \ , q_i>,$$

wo $$$S (u)$ - eine Reihe von Objekten, mit denen der Benutzer implizit interagiert hat, $$$σ_ {u} = | S (u) |, y_ {j}$ - Dimensionsdarstellung $$$k$ für ein Objekt aus $$$S (u)$ .

Faktorisierungsmaschinen (FM)

Wie in den Beispielen mit verschiedenen SVD-Modellen zu sehen ist, unterscheidet sich ein Modell vom anderen in der Menge der in der Bewertungsformel enthaltenen Begriffe. Darüber hinaus stellt die Erweiterung des Modells jedes Mal eine neue Aufgabe dar. Wir möchten, dass solche Änderungen (z. B. Hinzufügen einer neuen Art impliziter Antwort unter Berücksichtigung von Zeitparametern) einfach implementiert werden können, ohne den Modellimplementierungscode zu ändern. Die Modelle (2.1) - (2.5) können mit der folgenden Parametrisierung in einer praktischen universellen Form dargestellt werden. Wir repräsentieren den Benutzer und das Produkt als eine Reihe von Funktionen:

(2.6)

$$

$$\ overline {x} ^ U = (x_1 ^ U, x_2 ^ U, \ Punkte, x_l ^ U) \ in \ mathbb {R} ^ l,$$

(2.7)

$$

$$\ overline {x} ^ I = (x_1 ^ I, x_2 ^ I, \ dots, x_m ^ I) \ in \ mathbb {R} ^ m.$$

Abb. 1: Ein Beispiel für eine Merkmalsmatrix im Fall von CF.

Wenn beispielsweise bei der kollaborativen Filterung (CF) nur Daten zur Interaktion von Benutzern und Produkten verwendet werden, sehen die Merkmalsvektoren wie ein One-Hot-Code aus (Abb. 1). Vektor einführen $$$\ overline {x} = (\ overline {x} ^ U, \ overline {x} ^ I)$ Dann wird die Empfehlungsaufgabe auf Regressionsprobleme mit der Zielvariablen reduziert $$$r_ {ui}$ ::

1. Lineares Modell:
   (2.8)
   

   $$

   $$h_ {lin} (\ overline {x}) = w_0 + \ sum_ {j = 1} ^ {l + m} w_jx_j$$
2. Poly2:
   (2.9)
   

   $$

   $$h_ {poly2} (\ overline {x}) = w_0 + \ sum_ {j = 1} ^ {l + m} w_jx_j + \ sum_ {i = 1} ^ {l + m} \ sum_ {j = i + 1 } ^ {l + m} w_ {ij} x_i x_j$$
3. FM:
   (2.10)
   

   $$

   $$h_ {FM} (\ overline {x}) = w_0 + \ sum_ {j = 1} ^ {l + m} w_jx_j + \ sum_ {i = 1} ^ {l + m} \ sum_ {j = i + 1 } ^ {l + m} x_i x_j <\ overline {v} _i, \ overline {v} _j>$$

wo $$$w_ {j}$ - Modellparameter, $$$v_ {i}$ Sind Dimensionsvektoren $$$k$ das Zeichen darstellen $$$i$ im latenten Raum $$$l$ und $$$m$ - die Anzahl der Zeichen des Benutzers bzw. des Produkts. Neben One-Hot-Codes können inhaltsbasierte Funktionen (Content-based, CB) als Zeichen dienen (Abb. 2), beispielsweise vektorisierte Beschreibungen von Produkten und Benutzerprofilen.


Abb. 2: Ein Beispiel für eine erweiterte Feature-Matrix.

Das in [2] eingeführte FM-Modell ist eine Verallgemeinerung für (2.1) - (2.5), (2.8), (2.10). Das Wesentliche von FM ist, dass es die paarweise Interaktion von Merkmalen unter Verwendung eines skalaren Produkts berücksichtigt $$$<\ overline {v} _i, \ overline {v} _j>$ , ohne den Parameter $$$w_ {ij}$ . Der Vorteil von FM gegenüber Poly2 ist eine signifikante Reduzierung der Anzahl der Parameter: für Vektoren $$$v_ {i}$ wir werden brauchen $$$(l + m) · k$ Parameter und für $$$w_ {ij}$ wird benötigt $$$lm m$ Parameter. Bei $$$l$ und $$$m$ Bei großen Aufträgen werden beim ersten Ansatz deutlich weniger Parameter verwendet.

Bitte beachten Sie: Wenn das Trainingsset kein bestimmtes Paar enthält $$$(i, j)$ , dann der entsprechende Begriff mit $$$w_ {ij}$ In Poly2 hat dies keinen Einfluss auf das Training des Modells, und die Bewertung erfolgt nur für den linearen Teil. Der Ansatz (2.10) ermöglicht es uns jedoch, Beziehungen durch andere Merkmale herzustellen. Mit anderen Worten, die Daten zu einer Interaktion helfen bei der Bewertung der Parameter von Attributen, die in diesem Beispiel nicht enthalten sind.

Auf Basis von FM wird ein sogenanntes Hybridmodell implementiert, bei dem CB-Attribute zu CF-Attributen hinzugefügt werden. Sie können damit das Problem eines Kaltstarts lösen, Benutzerpräferenzen berücksichtigen und personalisierte Empfehlungen abgeben.

Lightfm

Bei der populären Implementierung von FM liegt der Schwerpunkt auf der Trennung zwischen den Eigenschaften des Benutzers und des Produkts. Matrizen dienen als Modellparameter $$$E ^ U$ und $$$E ^ I$ Einreichung von benutzerdefinierten und Produktmerkmalen:

(2.11)

$$

$$E ^ U = \ begin {pmatrix} \ overline {e} _1 ^ U \\ \ vdots \\ \ overline {e} _l ^ U \ end {pmatrix}, \, \, E ^ I = \ begin {pmatrix } \ overline {e} _1 ^ I \\ \ vdots \\ \ overline {e} _m ^ I \ end {pmatrix}, \ overline {e} _i ^ U \ in \ mathbb {R} ^ k, \ overline { e} _i ^ I \ in \ mathbb {R} ^ k$$

sowie Offsets $$$\ overline {b} ^ U, \ overline {b} ^ I \ in \ mathbb {R} ^ k$ . Benutzer- und Produktansichten verwenden:

(2.12)

$$

$$\ overline {p} ^ U = \ overline {x} ^ U \ cdot E ^ U = \ sum_ {j = 1} ^ l x_j ^ U \ cdot \ overline {e} _j ^ U,$$

(2.13)

$$

$$\ overline {q} ^ I = \ overline {x} ^ I \ cdot E ^ I = \ sum_ {j = 1} ^ m x_j ^ I \ cdot \ overline {e} _j ^ I,$$

Holen Sie sich die Paarbewertung $$$(u, i)$ ::

(2.14)

$$

$$\ hat {r} _ {ui} = <\ overline {p} ^ U, \ overline {q} ^ I> + <\ overline {x} ^ U, \ overline {b} ^ U> + <\ overline {x} ^ I, \ overline {b} ^ I>.$$

Verlustfunktionen

In unserem Fall ist es erforderlich, Produkte für einen bestimmten Benutzer zu bewerten, damit ein relevanteres Produkt eine höhere Bewertung als ein weniger relevantes hat. LightFM hat mehrere Verlustfunktionen:

1. Logistik ist eine Implementierung, die ein Negativ erfordert, das in den meisten Aufgaben nicht explizit dargestellt wird.
2. BPR [3] soll den Unterschied in den Bewertungen zwischen positiven und negativen Beispielen für einen bestimmten Benutzer maximieren. Negativ wird durch Bootstrap-Abtastung erhalten. Die im Algorithmus verwendete Qualitätsfunktion ähnelt der ROC-AUC.
3. WARP [4] unterscheidet sich von BPR in der Methode der Stichprobe negativer Beispiele und der Verlustfunktion, die ebenfalls in der Rangfolge aufgeführt ist, optimiert jedoch gleichzeitig die Top-Empfehlungen für den Benutzer.

Praktische Umsetzung

Um Empfehlungen für eine bestimmte Zeit zu erstellen, wird eine parallele Implementierung auf Spark verwendet. Für jedes Geschäft wird eine unabhängige Aufgabe gestartet, deren Ausführung von luigi gesteuert wird.

Datenvorverarbeitung

Die Datenvorverarbeitung wird von automatisch skalierbaren Spark SQL-Tools durchgeführt. Die im endgültigen Modell ausgewählten Funktionen sind Textbeschreibungen von Waren und Katalogen mit Standardkonvertierungen.

Was hat uns bei der Interaktion mit Spark geholfen:

1. Partitionierung vorbereiteter Daten (Matrix der Benutzer- und Produktinteraktionen, Zeichen dafür) nach Filialen. Auf diese Weise können Sie während der Trainingsphase beim Lesen von Daten aus HDFS Zeit sparen. Andernfalls muss jede Aufgabe Daten in den Spark-Speicher lesen und nach Speicher-ID filtern.
2. Das Speichern / Empfangen von Daten zu / von Spark erfolgt in Teilen. Dies liegt an der Tatsache, dass während einer dieser Aktionen die Daten in den JVM-Speicher geladen werden. Warum nicht einfach den Speicher für die JVM erhöhen? Erstens verringert sich dann der für das Training des Modells verfügbare Speicher, und zweitens muss nichts in der JVM gespeichert werden. In diesem Fall fungiert es als temporärer Speicher.

Modelltraining

Das Modell für jedes Geschäft wird in einem eigenen Spark-Container trainiert, sodass Sie gleichzeitig eine beliebige Anzahl von Aufgaben für Geschäfte ausführen können, die nur durch Clusterressourcen begrenzt sind.

In LightFM fehlen Frühstoppmechanismen. Daher geben wir zusätzliche Ressourcen für zusätzliche Trainingsiterationen aus, wenn die Zielmetrik nicht erhöht wird. Wir haben AUC als Metrik gewählt, deren Beziehung zur Klickrate experimentell bestätigt wird.

Bezeichnen:

$$$S$ - alle bekannten Interaktionen zwischen Benutzern und Produkten, dh Paare $$$(u, i)$ ,
$$$I$ - viele aller Waren $$$i$ ,
$$$U$ - viele aller Benutzer $$$u$ .
Für einen bestimmten Benutzer $$$u$ auch vorstellen $$$I_ {u} = {i ∈ I: (u, i) ∈ S}$ - Viele Produkte, mit denen der Benutzer interagiert hat. Die AUC kann wie folgt berechnet werden [ref]:

(3.1)

$$

$$AUC (u) = \ frac {1} {| \ mathcal {I} _u || \ mathcal {I} \ setminus \ mathcal {I} _u |} \ sum_ {i \ in \ mathcal {I} _u} \ sum_ {j \ in \ mathcal {I} \ setminus \ mathcal {I} _u} \ delta (\ hat {r} _ {ui}> \ hat {r} _ {uj}),$$

(3.2)

$$

$$AUC = \ frac {1} {| \ mathcal {U} |} \ sum_ {u \ in \ mathcal {U}} AUC (u).$$

In Formel (3.1) müssen wir die Bewertung für alle möglichen Paare berechnen $$$(u, i)$ ( $$$u$ behoben) sowie Bewertungen für Artikel aus vergleichen $$$\ mathcal {I} _u$ mit Bewertungen von $$$\ mathcal {I} \ setminus \ mathcal {I} _u$ . Angesichts der Tatsache, dass der Benutzer mit dem spärlichen Teil des Sortiments interagiert, ist die Komplexität der Berechnung $$$O (| \ mathcal {U} || \ mathcal {I} |)$ . Gleichzeitig kostet uns eine Ära des FM-Trainings $$$O (| \ mathcal {U} |)$ .

Daher haben wir die Berechnung der AUC geändert. Zunächst sollten Sie die Probe in ein Training aufteilen $$$\ mathcal {S} ^ {train} \ subset \ mathcal {S}$ und Validierung $$$\ mathcal {S} ^ {val} \ subset \ mathcal {S}$ und $$$\ mathcal {S} ^ {val} = \ mathcal {S} \ setminus \ mathcal {S} ^ {train}$ . Als Nächstes verwenden wir Stichproben, um viele Benutzer für die Validierung zu erstellen $$$\ mathcal {U} ^ {val} \ subset \ {u \ in \ mathcal {U}: (u, i) \ in \ mathcal {S} ^ {val} \}$ . Für Benutzer $$$u$ von $$$\ mathcal {U} ^ {val}$ Die Elemente der positiven Klasse werden als viele betrachtet $$$\ mathcal {I} _u ^ {+} = \ {i \ in \ mathcal {I}: (u, i) \ in \ mathcal {S} ^ {val} \}$ ähnlich $$$\ mathcal {I} _u$ . Als Elemente einer negativen Klasse nehmen wir eine Teilstichprobe $$$\ mathcal {I} _u ^ {-} \ subset \ mathcal {I}$ damit keine elemente aus $$$\ mathcal {I} _u$ . Die Teilstichprobengröße kann proportional zur Größe genommen werden. $$$\ mathcal {I} _u ^ {+}$ , also $$$| \ mathcal {I} _u ^ {-} | = c \ cdot | \ mathcal {I} _u ^ {+} |$ . Dann ändern sich die Formeln (3.1), (3.2) zur Berechnung der AUC:

(3.3)

$$

$$AUC (u) = \ frac {1} {| \ mathcal {I} _u ^ {+} || \ mathcal {I} _u ^ {-} |} \ sum_ {i \ in \ mathcal {I} _u ^ {+}} \ sum_ {j \ in \ mathcal {I} _u ^ {-}} \ delta (\ hat {r} _ {ui}> \ hat {r} _ {uj}),$$

(3.4)

$$

$$AUC = \ frac {1} {| \ mathcal {U} ^ {val} |} \ sum_ {u \ in \ mathcal {U} ^ {val}} AUC (u).$$

Als Ergebnis erhalten wir eine konstante Zeit für die Berechnung der AUC, da wir nur einen festen Teil der Benutzer und der Mengen verwenden $$$\ mathcal {I} _u ^ {+}$ und $$$\ mathcal {I} _u ^ {-}$ habe eine kleine Größe. Der Lernprozess für das Geschäft stoppt, nachdem sich die AUC (3.4) nicht mehr verbessert hat.

Suche nach ähnlichen Objekten

Im Rahmen der Aufgabe item2item müssen Sie für jedes Element auswählen $$$n$ (oder Produkte, die so ähnlich wie möglich sind) zu denen, die die Klickbarkeit des Banners maximieren. Unsere Annahme: Kandidaten für das Banner müssen von oben betrachtet werden. $$$k$ am nächsten im Raum Einbettungen. Wir haben die folgenden Methoden zur Berechnung der „nächsten Nachbarn“ getestet: Scala + Spark, ANNOY, SCANNs, HNSW.


Für Scala + Spark für ein Geschäft mit 500.000 Objekten dauerte die Berechnung einer ehrlichen Kosinusmetrik 15 Minuten und eine erhebliche Menge an Clusterressourcen. In diesem Zusammenhang haben wir ungefähre Methoden zum Auffinden der nächsten Nachbarn getestet. Bei der Untersuchung der SCANNs-Methode variierten die folgenden Parameter: bucketLimit , shouldSampleBuckets , NumHashes und setSignatureLength . Die Ergebnisse erwiesen sich jedoch im Vergleich zu anderen Methoden als unbefriedigend (sehr unterschiedliche Objekte fielen in den Bucket). Die ANNOY- und HNSW-Algorithmen zeigten Ergebnisse, die mit einem ehrlichen Cosinus vergleichbar waren, arbeiteten jedoch viel schneller.

	200k Produkte		500k Waren		2,2 Mio. Produkte
Algorithmus	ANNOY	Hnsw	ANNOY	Hnsw	ANNOY	Hnsw
Bauzeit Index (Sek.)	59,45	8.64	258.02	25.44	1190,81	90,45
Gesamtzeit (Sek.)	141,23	01/14	527,76	43,38	2081,57	150,92

Aufgrund der Tatsache, dass HNSW schneller als alle Algorithmen arbeitete, haben wir beschlossen, damit aufzuhören.
Wir suchen auch nach den nächsten Nachbarn im Spark-Container und schreiben das Ergebnis mit der entsprechenden Partitionierung in Hive.

Fazit

Rückruf: Wir verwenden WARP, um das Modell AUC für den frühen Stopp zu trainieren, und die endgültige Qualitätsbewertung wird mithilfe des A / B-Tests für den Live-Verkehr durchgeführt.

Wir glauben, dass an diesem Ort - bei der Organisation des Experiments und der Auswahl der optimalen Zusammensetzung des Banners - die Daten enden und die Wissenschaft beginnt. Hier lernen wir festzustellen, ob es sinnvoll ist, Empfehlungen für Produkte anzuzeigen, für die Retargeting funktioniert hat. genau wie viele Empfehlungen zu zeigen sind; wie viele Produkte angesehen usw. Wir werden in den folgenden Artikeln darüber sprechen.

Weitere Verbesserungen des Algorithmus - die Suche nach universellen Einbettungen, mit denen die Produkte aller Geschäfte in einem Raum platziert werden können - werden im Rahmen des am Anfang des Artikels beschriebenen Paradigmas durchgeführt.

Vielen Dank für Ihre Aufmerksamkeit!

Literatur

[1] Ricci F., Rokach L., Shapira B. Einführung in das Handbuch für Empfehlungssysteme
// Handbuch für Empfehlungssysteme. - Springer, Boston, MA, 2011 - S. 147160.

[2] Rendle S. Faktorisierungsmaschinen // 2010 IEEE International Conference on Data Mining. - IEEE, 2010 - S. 995-1000.

[3] Rendle S. et al. BPR: Bayesianisches personalisiertes Ranking aus implizitem Feedback
// Vorträge der fünfundzwanzigsten Konferenz über Unsicherheit in der künstlichen Intelligenz.
- AUAI Press, 2009 - S. 452-461.

[4] Weston J., Bengio S., Usunier N. Wsabie: Skalierung auf große Vokabeln Bildanmerkung // Zweiundzwanzigste internationale gemeinsame Konferenz über künstliche Intelligenz. - 2011.