En 2018, notre équipe participait traditionnellement au RecSys Challenge . Il s'agit d'un concours annuel sur les systèmes de recommandation organisé dans le cadre de la conférence RecSys. Il n'est pas aussi important que les compétitions de Kaggle, mais il est considéré comme l'une des compétitions les plus prestigieuses dans les systèmes de recommandation. Cette fois, la tâche était musicale - il fallait construire un système pour continuer automatiquement les playlists. Dans cet article, je parle en détail de notre décision. Je t'invite au chat.

À propos du concours

Cette année, les données du concours ont été fournies par Spotify , un service de streaming musical (qui, malheureusement, n'est pas officiellement disponible dans la Fédération de Russie). Les recommandations sont l'une des parties les plus importantes du produit dans Spotify et permettent aux utilisateurs de trouver de la nouvelle musique, de créer des listes de lecture ou d'écouter la radio en fonction de leurs préférences.

Les participants au concours devaient créer un algorithme de continuation de liste de lecture automatique. Le Million Playlist Dataset, dont le nom parle de lui-même, a été présenté comme des données d'entraînement. En plus des informations sur les pistes contenues dans la playlist, des méta-informations sur les pistes ont également été fournies: artiste, titre, durée, nom de l'album.

Vous pouvez en savoir plus sur le concours ici .

Défi de la compétition

La tâche du concours est classique pour les systèmes de recommandation: générer des recommandations top-K pour l'utilisateur, connaissant l'historique de ses actions, mais au lieu de l'élément utilisateur habituel, la piste de playlist apparaît ici. En termes plus formels, des parties de listes de lecture (ci-après dénommées graines) ont été données dans les données de test, et il y avait plusieurs façons de les former. Pour K = (5, 10, 25, 100), il y avait des graines avec les K premières pistes et K pistes choisies au hasard. Il y avait aussi des graines avec le premier morceau et uniquement avec le nom de la playlist. Les pistes qui n'étaient pas incluses dans les récalcitrants devaient être prédites. Pour chaque playlist, exactement 500 prédictions étaient nécessaires.

Mesures

L'une des caractéristiques de la compétition était que la métrique n'en était pas une, comme c'est la coutume dans la plupart des compétitions, mais plusieurs. Ci-dessous, je vais parler de chacun d'eux.

Précision R

Cette métrique montre quelle proportion de pistes pertinentes nous avons deviné.

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

NDCG

Il s'agit d'une mesure de qualité de classement classique, vous pouvez en savoir plus, par exemple, ici

Clics

Spotify a un mécanisme pour continuer la liste de lecture (vous pouvez le voir dans la capture d'écran au début de l'article): il propose plusieurs pistes qui peuvent étendre la liste de lecture, et si aucune n'apparaît, vous pouvez cliquer sur le bouton d'actualisation et obtenir le prochain lot de recommandations. Le nombre de ces mises à jour du premier choix est la mesure des clics. Plus simplement, la position de la première recommandation pertinente (dans ce cas, divisée par 10).

Ensuite, les équipes se voient attribuer un classement pour chacune des métriques. Ensuite, les rangs sont agrégés selon le schéma de la stratégie électorale du comte de Borda. Si $$$p$ Est le nombre de participants, alors une équipe avec un rang de 1 obtient $$$p-1$ points, une équipe avec un rang de 2 reçoit $$$p-2$ points et ainsi de suite.

Solution

Schéma de validation

Pour jouer les divisions train / test, nous avons divisé le jeu de données d'origine en trois parties: la première partie contenait 980k listes de lecture, les deuxième et troisième parties contenaient 10k chacune. Ensuite, chaque liste de lecture des deuxième et troisième parties a été divisée en parties de départ et de sortie, et les tailles des parties de départ ont été sélectionnées de la même manière que dans l'ensemble de test fourni, et les pistes restantes sont tombées en attente.

Sélection des candidats

Les systèmes recommandés utilisent souvent une approche en deux étapes: tout d'abord, en utilisant un modèle plus simple (par exemple, la factorisation matricielle ), les candidats sont sélectionnés dans l'ensemble des éléments, puis les candidats sont classés par un modèle plus complexe (par exemple, l' augmentation du gradient ) sur un ensemble plus large d'attributs. La sélection des candidats est nécessaire, tout d'abord, en raison des ressources informatiques limitées: si nous utilisons l'ensemble des pistes disponibles en tant que candidats, alors pour une liste de lecture, nous aurions à conduire environ un million d'objets à travers le modèle.

Sélection des candidats par factorisation matricielle

La factorisation matricielle est l'une des approches les plus courantes pour construire des systèmes de recommandation. L'idée principale de cette méthode est de présenter une matrice clairsemée d'interactions entre les utilisateurs et les articles sous la forme d'un produit de deux matrices (U et I) de plus petite dimension. Ensuite, nous pouvons obtenir des recommandations pour l'utilisateur en multipliant le vecteur de la matrice U par la matrice I.

Pour la factorisation matricielle, nous avons utilisé la bibliothèque LightFM avec une perte WARP (Weighted Approximate-Rank Pairwise) . Nous avions également deux modèles différents - l'un pour les listes de lecture qui ont une graine non vide, et l'autre pour les listes de lecture qui n'ont qu'un nom (démarrage à froid).

Perte de WARP

Cette fonction de perte est meilleure que d'autres dans le classement des tâches. Il fonctionne avec des triplets (utilisateur, élément positif, élément négatif) et présente une caractéristique très importante - la sélection d'exemples négatifs ne se produit pas par hasard, mais de telle manière que les exemples négatifs sélectionnés «cassent» le classement actuel du modèle, c'est-à-dire étaient supérieurs à un exemple positif.

Ainsi, la procédure de formation d'un modèle utilisant la perte WARP sera approximativement la suivante:

1. Pour un couple $$$(utilisateur, positif \ _item)$ nous choisirons un exemple négatif aléatoire parmi tous les autres éléments (il est important de comprendre que cela n'est nécessaire que si la probabilité de choisir un exemple négatif, qui sera effectivement positif, est assez faible). Calculer la prédiction de paire $$$(utilisateur, positif \ _item)$ et $$$(utilisateur, négatif \ _item)$ et s'il n'y avait pas de trouble (c'est-à-dire que le modèle prédit un score plus élevé pour un exemple positif), alors nous continuons à échantillonner des exemples négatifs jusqu'à ce que la violation se produise.
2. Si nous avons reçu une violation lors de la première tentative, nous pouvons alors faire un grand pas de gradient, car cela signifie que pour le moment, le modèle place souvent des exemples négatifs au-dessus des exemples positifs et qu'il est nécessaire de mettre à jour fortement ses poids. Si nous devions chercher un exemple négatif approprié pendant longtemps, alors nous faisons un petit pas - le modèle est déjà bien formé.

Une description plus formelle de la perte de WARP peut être trouvée dans l'article d'origine ou dans cet article .

Lightfm

La première version du modèle n'utilisait que des informations collaboratives: la présence de la piste track_id dans la playlist playlist_id, présentée comme une matrice binaire clairsemée. Un certain nombre de matrices correspondaient à une playlist, une colonne à une piste.

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

Fonctionnalités de texte LightFM +

Ce modèle utilise des incorporations de mots du nom de la liste de lecture au lieu de playlist_id. Une intégration d'une playlist est la somme des intégrations de ses mots.

$$$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}$ ,
où $$$f_p$ - Ce sont les mots du nom de la playlist.

Ainsi, nous résolvons le problème d'un démarrage à froid - nous pouvons fournir de meilleures recommandations pour les listes de lecture qui n'ont qu'un nom.

Les organisateurs du concours ont également fourni des informations sur le nombre de pistes dans la partie cachée de la liste de lecture. Si la partie cachée était $$$k$ pistes alors nous choisissons $$$max (k * 15, k + 700)$ candidats. La nature de ces nombres est une simple heuristique, inventée à partir des considérations suivantes: nous voulons avoir suffisamment de candidats pour de petites listes de lecture (donc $$$k + 700$ ), et nous voulons également que l'ensemble de données final contienne environ 10 millions de lignes pour des raisons de performances en termes de temps et de mémoire (donc k 15, pas k 50 par exemple).

Classement

Après avoir sélectionné les candidats, nous pouvons considérer la tâche de construire des recommandations comme un problème de classification binaire: pour chacune des pistes des candidats sélectionnés, nous apprenons à prédire si cette piste était vraiment dans la playlist.

Dans notre jeu de données d'entraînement, chaque ligne contiendra des signes pour la paire (liste de lecture, piste), et l'étiquette sera 1 s'il y a une piste dans la liste de lecture et 0 sinon.

Comme signes, plusieurs groupes différents ont été utilisés.

Fonctionnalités basées sur le modèle LightFM

Comme décrit ci-dessus, dans le modèle LightFM, nous avons obtenu des vecteurs $$$q_p, q_t$ et scalaires $$$b_p, b_t$ .
Comme signes, nous utiliserons $$$b_p, b_t$ , < $$$q_p, q_t>$ et le rang de la piste t parmi tous les candidats pour la playlist p (le rang a été calculé par la formule ). Ces quatre attributs ont été extraits des modèles LightFM et LightFM Text.

Signes basés sur la cooccurrence de la piste

Soit $$$n_ {i, j}$ Est le nombre de listes de lecture contenant des pistes $$$i$ et $$$j$ ensemble aussi $$$n_i$ - nombre de playlists contenant la piste $$$i$ . Ces valeurs ont été calculées sur un ensemble fixe de listes de lecture comprenant toutes les parties de départ.

Laissez la playlist $$$p$ se compose de pistes $$$t_1, t_2, ..., t_n$ . Pour la piste $$$t$ calculer les valeurs $$$n_ {t, t_1}, n_ {t, t_2}, ..., n_ {t, t_n}$ et pour eux, nous calculerons diverses statistiques: minimum, maximum, moyenne et médiane. Ensuite, nous calculons les mêmes statistiques pour les quantités $$$\ frac {n_ {t, t_1}} {n_ {t_1}}, \ frac {n_ {t, t_2}} {n_ {t_2}}, ..., \ frac {n_ {t, t_n}} { n_ {t_n}}$ . Dans le premier cas, nous observons simplement la fréquence à laquelle la piste cible s'est rencontrée avec les pistes de la liste de lecture, et dans le second cas, nous normalisons également cela à la fréquence d'occurrence des autres pistes. La normalisation aide le modèle à ne pas se recycler pour les pistes populaires et à extraire plus précisément les informations sur la similitude réelle des pistes.

Autres signes

Toutes les caractéristiques sont calculées pour la paire. $$$(p, t)$ .

• Le nombre d'artistes uniques dans la playlist $$$p$ .
• Nombre d'albums uniques dans la playlist $$$p$ .
• Nombre et pourcentage de pistes dans une liste de lecture $$$p$ avec le même album / artiste que la piste $$$t$ .
• Combien de fois la piste s'est-elle rencontrée $$$t$ dans toutes les listes de lecture.
• Combien de fois l'artiste / l'album s'est-il enregistré $$$t$ dans toutes les listes de lecture.
• Le nombre de pistes dans les parties de départ et d'exclusion de la liste de lecture $$$p$ .

Modèle de recommandation

Pour construire les recommandations finales, nous avons utilisé XGBoost . Le modèle a été formé sur $$$II_ {candidats}$ , les hyperparamètres ont été sélectionnés $$$III_ {candidats}$ par métrique ROC AUC . Cette métrique a été choisie car elle est classique pour les problèmes de classification. Toutes les fonctionnalités ne sont pas également utiles, il sera donc intéressant d'examiner les valeurs d'importance des fonctionnalités du modèle.

On peut voir que le signe de co-occurrence moyenne normalisée se démarque significativement des autres. Cela signifie que les informations sur la co-occurrence de pistes donnent un signal très fort, ce qui, en général, n'est pas surprenant. En outre, cette fonctionnalité pourrait être utilisée comme sélection candidate au lieu du modèle LightFM, et cela n'a donné aucun résultat.

Autre

Le fer

Tous les modèles ont été formés sur le serveur avec Intel Xeon E5-2679 v3 (28 cœurs, 56 threads), 256 Go de RAM. L'apprentissage du pipeline final a pris environ 100 heures et a consommé 200 Go de mémoire au pic, et une partie importante (environ 90%) du temps a été consacrée à la formation du modèle de sélection des candidats. Le modèle de classement a été formé assez rapidement - environ deux heures (sans compter la sélection des hyperparamètres).

Échoue

Pas sans échec.

L'avant-dernier jour de la compétition, nous avons décidé d'organiser un mini-hackathon, à la fin nous avons collecté tout ce que nous avions: sélection des candidats en fonction de la co-occurrence, un tas de nouvelles fonctionnalités pour booster, et il semblerait que cela aurait pu se passer comme ça?
Mais la vitesse de validation a vraiment augmenté un peu, alors nous avons aveuglé la soumission et l'avons envoyée, prévoyant qu'il nous resterait un jour pour réparer les montants. Après avoir envoyé la soumission, ils ont appris que ce n'était pas l'avant-dernier jour, mais le dernier. Et la vitesse de la nouvelle soumission était bien inférieure à celle de notre meilleure soumission. Nous n'avons pas eu le temps de comprendre pourquoi cela s'est produit, nous avons donc saboté la meilleure soumission, qui est restée à la troisième place.

Le dernier jour également, nous avons appris qu'il existe deux types de graines: avec les premières pistes K et les pistes aléatoires, et dans la validation, nous avons toujours choisi des pistes aléatoires, mais il est peu probable que cela affecte considérablement le classement.
Un jour de la compétition, la valeur de la métrique R-Precision pour toutes les équipes du classement a fortement augmenté. Nous n'avons attaché aucune importance à cela, mais à la fin de la compétition, nous avons découvert que les organisateurs ont ajouté un élément de plus à la métrique - un match de l'artiste de la piste. Cela pourrait également être ajouté à la métrique de validation et, éventuellement, à une vitesse améliorée.

Code

Notre solution est conçue sous la forme d'ordinateurs portables Jupyter et elle peut être reproduite (!) En les lançant séquentiellement. Seulement pour cela, vous avez besoin d'une machine avec 200 Go + RAM et quelques jours.

Décisions des autres participants

L'équipe qui a remporté la première place participe également régulièrement au RecSys Challenge et prend des positions élevées. Leur solution est similaire à la nôtre, mais implémentée en Java .

Les seconds finalistes ont une approche assez intéressante - ils ont utilisé Denoising Autoencoder pour restaurer les listes de lecture de leurs parties .

Conclusion

Si vous regardez le classement final, notre équipe se classe sixième et quatrième dans les statistiques de classement (R-Precision et NDCG), et première dans la statistique Clicks. Comment est-ce arrivé? Et cela s'est produit à cause d'une bonne solution au problème de démarrage à froid en utilisant le modèle LightFM Text. La mesure des clics inflige des amendes plus sévères lorsque nous ne devinons pas un seul morceau d'une liste de lecture. L'utilisation du modèle LightFM Text a amélioré la mesure moyenne des clics de 2,2 à 1,78.

L'approche consistant à sélectionner des candidats à l'aide d'un modèle plus simple et à classer davantage avec un modèle plus complexe est toujours l'une des plus réussies dans les problèmes classiques de construction de recommandations top-K. Mais en même temps, il est très important de construire correctement le schéma de validation afin que les modèles de sélection candidats et les modèles de classement puissent être comparés.

De plus, ce schéma est tout à fait adapté aux systèmes de production - vous pouvez commencer à construire votre système de recommandation sur la base de la factorisation matricielle, puis l'améliorer en ajoutant une deuxième étape.

Si vous avez des questions sur l'article, n'hésitez pas à les poser dans les commentaires :)

PS Nous avons écrit un article plus détaillé à ce sujet pour l'atelier de la conférence RecSys. L'accès à son matériel sur le site est limité, donc si vous êtes intéressé à en savoir un peu plus sur notre solution, écrivez-moi en PM.