2018 nahm unser Team traditionell an der RecSys Challenge teil . Dies ist ein jährlicher Wettbewerb zu Empfehlungssystemen, der im Rahmen der RecSys-Konferenz abgehalten wird. Es ist nicht so groß wie die Wettbewerbe bei Kaggle, aber es gilt als einer der prestigeträchtigsten Wettbewerbe in Empfehlungssystemen. Diesmal war die Aufgabe musikalisch - es war notwendig, ein System für die automatische Fortsetzung von Wiedergabelisten zu erstellen. In diesem Beitrag spreche ich ausführlich über unsere Entscheidung. Ich lade dich zur Katze ein.

Über den Wettbewerb

In diesem Jahr wurden die Daten für den Wettbewerb von Spotify bereitgestellt, einem Musik-Streaming-Dienst (der in der Russischen Föderation leider nicht offiziell verfügbar ist). Empfehlungen sind einer der wichtigsten Bestandteile des Produkts in Spotify und ermöglichen es Benutzern, neue Musik zu finden, Wiedergabelisten zu erstellen oder Radio zu hören, je nach ihren Vorlieben.

Die Teilnehmer des Wettbewerbs mussten einen automatischen Algorithmus zur Fortsetzung der Wiedergabeliste erstellen. Der Million Playlist Dataset, dessen Name für sich spricht, wurde als Trainingsdaten präsentiert. Neben Informationen darüber, welche Titel in der Wiedergabeliste enthalten sind, wurden auch Metainformationen zu den Titeln bereitgestellt: Künstler, Titel, Dauer, Albumname.

Mehr über den Wettbewerb können Sie hier lesen.

Herausforderung des Wettbewerbs

Die Aufgabe des Wettbewerbs ist klassisch für Empfehlungssysteme: Generieren Sie Top-K-Empfehlungen für den Benutzer, wobei Sie den Verlauf seiner Aktionen kennen. Anstelle des üblichen Benutzerelements wird hier jedoch der Playlist-Track angezeigt. In formaleren Begriffen wurden Teile von Wiedergabelisten (im Folgenden als Startwert bezeichnet) in den Testdaten angegeben, und es gab verschiedene Möglichkeiten, sie zu erstellen. Für K = (5, 10, 25, 100) gab es Samen mit den ersten K-Spuren und K-Spuren, die zufällig ausgewählt wurden. Es gab auch Samen mit dem ersten Titel und nur mit dem Namen der Wiedergabeliste. Tracks, die nicht in den Holdouts enthalten waren, mussten vorhergesagt werden. Für jede Wiedergabeliste waren genau 500 Vorhersagen erforderlich.

Metriken

Eines der Merkmale des Wettbewerbs war, dass die Metrik nicht eine war, wie es bei den meisten Wettbewerben üblich ist, sondern mehrere. Im Folgenden werde ich über jeden von ihnen erzählen.

R-Präzision

Diese Metrik zeigt, welchen Anteil relevanter Tracks wir erraten haben.

$$$R-Genauigkeit = \ frac {| G \ cap {} R_ {1: | G |} |} {| G |}$

NDCG

Dies ist eine klassische Qualitätsmetrik für das Ranking. Sie können sie beispielsweise hier lesen

Klicks

Spotify verfügt über einen Mechanismus zum Fortsetzen der Wiedergabeliste (Sie können ihn im Screenshot am Anfang des Artikels sehen): Es bietet mehrere Titel, mit denen die Wiedergabeliste erweitert werden kann. Wenn keine angezeigt wird, können Sie auf die Schaltfläche "Aktualisieren" klicken und die nächsten Empfehlungen abrufen. Die Anzahl solcher Aktualisierungen für die erste Auswahl ist die Klickmetrik. Einfacher die Position der ersten relevanten Empfehlung (in diesem Fall geteilt durch 10).

Als nächstes wird den Teams für jede der Metriken ein Rang zugewiesen. Dann werden die Ränge gemäß dem Schema der Borda Count Election Strategy aggregiert. Wenn $$$p$Ist die Anzahl der Teilnehmer, dann bekommt ein Team mit einem Rang von 1 $$$p-1$Punkte erhält ein Team mit einem Rang von 2 $$$p-2$Punkte und so weiter.

Lösung

Validierungsschema

Um Zug- / Test-Splits zu spielen, haben wir den ursprünglichen Datensatz in drei Teile unterteilt: Der erste Teil enthielt 980.000 Wiedergabelisten, der zweite und dritte Teil enthielten jeweils 10.000. Dann wurde jede Wiedergabeliste aus dem zweiten und dritten Teil in Seed- und Holdout-Teile unterteilt, und die Größen der Seed-Teile wurden auf die gleiche Weise wie im bereitgestellten Testsatz ausgewählt, und die verbleibenden Spuren fielen in Holdout.

Auswahl der Kandidaten

Empfohlene Systeme verwenden häufig einen zweistufigen Ansatz: Zuerst werden unter Verwendung eines einfacheren Modells (z. B. Matrixfaktorisierung ) Kandidaten aus dem gesamten Satz von Elementen ausgewählt, und dann werden Kandidaten nach einem komplexeren Modell (z. B. Gradientenverstärkung ) auf einem breiteren Satz von Attributen eingestuft. Die Auswahl der Kandidaten ist vor allem aufgrund der begrenzten Rechenressourcen erforderlich: Wenn wir den gesamten Satz verfügbarer Titel als Kandidaten verwenden, müssten wir für eine Wiedergabeliste etwa eine Million Objekte durch das Modell fahren.

Auswahl der Kandidaten mittels Matrixfaktorisierung

Die Matrixfaktorisierung ist einer der häufigsten Ansätze zum Aufbau von Empfehlungssystemen. Die Hauptidee dieser Methode besteht darin, eine spärliche Matrix von Interaktionen zwischen Benutzern und Elementen in Form eines Produkts aus zwei Matrizen (U und I) kleinerer Dimension darzustellen. Dann können wir Empfehlungen für den Benutzer erhalten, indem wir den Vektor aus Matrix U mit Matrix I multiplizieren.

Für die Matrixfaktorisierung verwendeten wir die LightFM- Bibliothek mit WARP-Verlust (Weighted Approximate-Rank Pairwise) . Wir hatten auch zwei verschiedene Modelle - eines für Wiedergabelisten mit einem nicht leeren Startwert und das andere für Wiedergabelisten, die nur einen Namen haben (Kaltstart).

WARP-Verlust

Diese Verlustfunktion ist bei Ranking-Aufgaben besser als andere. Es funktioniert mit Tripeln (user, positive_item, negative_item) und hat ein sehr wichtiges Merkmal - die Auswahl negativer Beispiele erfolgt nicht zufällig, sondern so, dass die ausgewählten negativen Beispiele die aktuelle Rangfolge des Modells "brechen", d. H. waren höher als ein positives Beispiel.

Das Verfahren zum Trainieren eines Modells unter Verwendung von WARP-Verlust ist daher ungefähr wie folgt:

1. Für ein Paar $$$(Benutzer, positives \ _Element)$Wir werden ein zufälliges negatives Beispiel unter allen anderen Elementen auswählen (es ist wichtig zu verstehen, dass dies nur dann sinnvoll ist, wenn die Wahrscheinlichkeit, ein negatives Beispiel zu wählen, das tatsächlich positiv ist, recht gering ist). Berechnen Sie die Paarvorhersage $$$(Benutzer, positives \ _Element)$und $$$(Benutzer, negatives \ _Element)$und wenn es keine Störung gab (das heißt, das Modell sagte eine höhere Punktzahl für ein positives Beispiel voraus), werden wir weiterhin negative Beispiele untersuchen, bis die Verletzung auftritt.
2. Wenn wir beim ersten Versuch eine Verletzung erhalten haben, können wir einen großen Gradientenschritt machen, da dies bedeutet, dass das Modell im Moment häufig negative Beispiele über positive stellt und es notwendig ist, seine Gewichte stark zu aktualisieren. Wenn wir lange nach einem geeigneten negativen Beispiel suchen mussten, dann machen wir einen kleinen Schritt - das Modell ist bereits gut trainiert.

Eine formellere Beschreibung des WARP-Verlusts finden Sie im Originalartikel oder in diesem Beitrag .

Lightfm

In der ersten Version des Modells wurden nur kollaborative Informationen verwendet: das Vorhandensein des Titels track_id in der Wiedergabeliste playlist_id, dargestellt als binäre Matrix mit geringer Dichte. Eine Anzahl von Matrizen entsprach einer Wiedergabeliste, eine Spalte einem Titel.

$$$score (p, t) = b_t + b_t + <q_p, q_t>$

LightFM + Textfunktionen

Dieses Modell verwendet Einbettungen von Wörtern aus dem Namen der Wiedergabeliste anstelle von playlist_id. Eine Einbettung einer Wiedergabeliste ist die Summe der Einbettungen seiner Wörter.

$$$score (p, t) = b_p + b_t + <q_p, q_t>$
$$$b_p = \ sum_ {i \ in {f_p}} {b_i}$, $$$q_p = \ sum_ {i \ in {f_p}} {q_i}$,
wo $$$f_p$- Dies sind die Wörter aus dem Namen der Wiedergabeliste.

So lösen wir das Problem eines Kaltstarts - wir können bessere Empfehlungen für Wiedergabelisten geben, die nur einen Namen haben.

Die Organisatoren des Wettbewerbs gaben auch Auskunft darüber, wie viele Titel sich im versteckten Teil der Wiedergabeliste befanden. Wenn der versteckte Teil war $$$k$Tracks wählen wir dann $$$max (k * 15, k + 700)$Kandidaten. Die Art dieser Zahlen ist eine einfache Heuristik, die aus den folgenden Überlegungen erfunden wurde: Wir möchten (daher) genügend Kandidaten für kleine Wiedergabelisten haben $$$k + 700$), und wir möchten auch, dass der endgültige Datensatz aus Leistungsgründen in Bezug auf Zeit und Speicher ungefähr 10 Millionen Zeilen enthält (daher beispielsweise k 15, nicht k 50).

Rangliste

Nachdem wir Kandidaten ausgewählt haben, können wir die Aufgabe, Empfehlungen zu konstruieren, als binäres Klassifizierungsproblem betrachten: Für jeden der Titel in den ausgewählten Kandidaten lernen wir vorherzusagen, ob dieser Titel wirklich in der Wiedergabeliste enthalten war.

In unserem Trainingsdatensatz enthält jede Zeile Zeichen für das Paar (Wiedergabeliste, Titel), und die Bezeichnung lautet 1, wenn die Wiedergabeliste einen Titel enthält, und 0, wenn nicht.

Als Zeichen wurden mehrere verschiedene Gruppen verwendet.

Funktionen basierend auf dem LightFM-Modell

Wie oben beschrieben, haben wir im LightFM-Modell Vektoren erhalten $$$q_p, q_t$und Skalare $$$b_p, b_t$.
Als Zeichen werden wir verwenden $$$b_p, b_t$, < $$$q_p, q_t>$und der Rang des Titels t unter allen Kandidaten für die Wiedergabeliste p (der Rang wurde durch die Formel berechnet ). Diese vier Attribute wurden sowohl aus LightFM- als auch aus LightFM-Textmodellen übernommen.

Zeichen basierend auf dem gemeinsamen Auftreten der Spur

Lass $$$n_ {i, j}$Ist die Anzahl der Wiedergabelisten, die Titel enthalten $$$i$und $$$j$auch zusammen $$$n_i$- Anzahl der Wiedergabelisten, die den Titel enthalten $$$i$. Diese Werte wurden auf einem festen Satz von Wiedergabelisten berechnet, die aus allen Startteilen bestehen.

Lass die Playlist $$$p$besteht aus Spuren $$$t_1, t_2, ..., t_n$. Für die Strecke $$$t$Berechnen Sie die Werte $$$n_ {t, t_1}, n_ {t, t_2}, ..., n_ {t, t_n}$und für sie werden wir verschiedene Statistiken berechnen: Minimum, Maximum, Durchschnitt und Median. Dann berechnen wir die gleichen Statistiken für die Mengen $$$\ frac {n_ {t, t_1}} {n_ {t_1}}, \ frac {n_ {t, t_2}} {n_ {t_2}}, ..., \ frac {n_ {t, t_n}} { n_ {t_n}}$. Im ersten Fall beobachten wir nur, wie oft sich der Ziel-Track zusammen mit den Tracks aus der Wiedergabeliste getroffen hat, und im zweiten Fall normalisieren wir dies auch auf die Häufigkeit des Auftretens anderer Tracks. Die Normalisierung hilft dem Modell, sich nicht auf gängige Tracks umzuschulen und Informationen darüber, wie sehr sich die Tracks wirklich ähneln, genauer zu extrahieren.

Andere Anzeichen

Alle Eigenschaften werden für das Paar berechnet. $$$(p, t)$.

• Die Anzahl der eindeutigen Künstler in der Wiedergabeliste $$$p$.
• Anzahl der eindeutigen Alben in der Wiedergabeliste $$$p$.
• Anzahl und Prozentsatz der Titel in einer Wiedergabeliste $$$p$mit dem gleichen Album / Künstler wie der Titel $$$t$.
• Wie oft hat sich die Strecke getroffen? $$$t$in allen Wiedergabelisten.
• Wie oft hat der Künstler / Album-Track $$$t$in allen Wiedergabelisten.
• Die Anzahl der Titel in den Seed- und Holdout-Teilen der Wiedergabeliste $$$p$.

Empfehlungsmodell

Um die endgültigen Empfehlungen zu erstellen, haben wir XGBoost verwendet . Das Modell wurde trainiert $$$II_ {Kandidaten}$wurden Hyperparameter ausgewählt $$$III_ {Kandidaten}$nach ROC AUC- Metrik. Diese Metrik wurde gewählt, weil sie für Klassifizierungsprobleme klassisch ist. Nicht alle Features sind gleichermaßen nützlich, daher ist es interessant, die Werte der Feature-Wichtigkeit des Modells zu betrachten.

Es ist ersichtlich, dass sich das Zeichen des normalisierten Mittelwerts des gleichzeitigen Auftretens signifikant von den anderen unterscheidet. Dies bedeutet, dass Informationen über das gleichzeitige Auftreten von Spuren ein sehr starkes Signal liefern, was im Allgemeinen nicht überraschend ist. Diese Funktion könnte auch als Kandidatenauswahl anstelle des LightFM-Modells verwendet werden, was zu keinen schlechteren Ergebnissen führte.

Andere

Eisen

Alle Modelle wurden auf dem Server mit Intel Xeon E5-2679 v3 (28 Kerne, 56 Threads) und 256 GB RAM trainiert. Das Erlernen der endgültigen Pipeline dauerte ungefähr 100 Stunden und verbrauchte zu Spitzenzeiten 200 GB Speicher. Ein erheblicher Teil (ungefähr 90%) der Zeit wurde für das Training des Kandidatenauswahlmodells aufgewendet. Das Ranking-Modell wurde ziemlich schnell trainiert - ungefähr zwei Stunden (ohne die Auswahl der Hyperparameter).

Schlägt fehl

Nicht ohne Fehler.

Am vorletzten Tag des Wettbewerbs haben wir beschlossen, einen Mini-Hackathon zu veranstalten. Am Ende haben wir alles gesammelt, was wir hatten: Auswahl der Kandidaten basierend auf dem gemeinsamen Auftreten, eine Reihe neuer Funktionen zur Steigerung, und es scheint, dass es so laufen könnte?
Aber die Validierungsgeschwindigkeit ist wirklich ein bisschen gestiegen, also haben wir die Einreichung geblendet und gesendet und geplant, dass wir noch einen Tag Zeit haben, um die Pfosten zu reparieren. Nachdem sie die Vorlage gesendet hatten, erfuhren sie, dass es nicht der vorletzte Tag war, sondern der letzte. Und die Geschwindigkeit der neuen Einreichung war viel geringer als unsere beste Einreichung. Es war keine Zeit herauszufinden, warum dies geschah, also sabotierten wir die beste Einreichung, die auf dem dritten Platz blieb.

Auch am letzten Tag haben wir erfahren, dass es zwei verschiedene Arten von Seeds gibt: mit den ersten K-Tracks und zufälligen, und bei der Validierung haben wir immer zufällige ausgewählt, aber es ist unwahrscheinlich, dass dies die Bestenliste stark beeinflusst.
An einem Tag des Wettbewerbs stieg der Wert der R-Precision-Metrik für alle Teams in der Rangliste stark an. Wir haben dem keine Bedeutung beigemessen, aber am Ende des Wettbewerbs haben wir festgestellt, dass die Organisatoren der Metrik eine weitere Komponente hinzugefügt haben - ein Match des Track-Künstlers. Dies könnte auch zur Validierungsmetrik hinzugefügt und möglicherweise die Geschwindigkeit verbessert werden.

Code

Unsere Lösung ist in Form von Jupyter-Laptops konzipiert und kann durch sequentielles Starten (!) Reproduziert werden. Nur dafür benötigen Sie eine Maschine mit 200 GB + RAM und ein paar Tagen Zeit.

Entscheidungen anderer Teilnehmer

Das Team, das den ersten Platz gewonnen hat, nimmt auch regelmäßig an der RecSys Challenge teil und nimmt hohe Plätze ein. Ihre Lösung ähnelt unserer, ist jedoch in Java implementiert .

Die zweiten Finalisten haben einen ziemlich interessanten Ansatz - sie haben Denoising Autoencoder verwendet, um Wiedergabelisten aus ihren Teilen wiederherzustellen .

Fazit

Wenn Sie sich die endgültige Rangliste ansehen, belegt unser Team in den Ranglisten (R-Precision und NDCG) den sechsten und vierten Platz und in der Klick-Metrik den ersten Platz. Wie ist es passiert? Dies geschah aufgrund einer guten Lösung für das Kaltstartproblem mit dem LightFM-Textmodell. Die Clicks-Metrik wird strenger, wenn wir keinen einzelnen Titel aus einer Wiedergabeliste erraten. Durch Verwendung des LightFM-Textmodells wurde die durchschnittliche Metrik für Klicks von 2,2 auf 1,78 verbessert.

Der Ansatz, Kandidaten anhand eines einfacheren Modells auszuwählen und mit einem komplexeren Modell weiter zu bewerten, ist immer noch einer der erfolgreichsten bei den klassischen Problemen der Erstellung von Top-K-Empfehlungen. Gleichzeitig ist es sehr wichtig, das Validierungsschema korrekt zu erstellen, damit sowohl Kandidatenauswahlmodelle als auch Rankingmodelle verglichen werden können.

Dieses Schema eignet sich auch gut für Produktionssysteme. Sie können Ihr Empfehlungssystem auf der Grundlage der Matrixfaktorisierung erstellen und es dann durch Hinzufügen einer zweiten Stufe verbessern.

Wenn Sie Fragen zu dem Artikel haben, können Sie diese gerne in den Kommentaren stellen :)

PS Wir haben einen ausführlicheren Artikel dazu für den Workshop auf der RecSys-Konferenz geschrieben. Der Zugriff auf ihre Materialien auf der Website ist begrenzt. Wenn Sie also mehr über unsere Lösung erfahren möchten, schreiben Sie mir in PM.