Le remarketing dynamique (dynrem) dans myTarget est une technologie de publicité ciblée qui utilise des informations sur les actions des utilisateurs sur les sites Web et dans les applications mobiles des annonceurs. Par exemple, dans une boutique en ligne, un utilisateur a regardé les pages de produits ou les a ajoutés au panier, et myTarget utilise ces événements pour afficher des publicités pour les produits et services pour lesquels une personne a précédemment manifesté son intérêt. Aujourd'hui, je vais parler plus en détail du mécanisme de génération de recommandations non personnelles, c'est-à-dire les recommandations item2item, qui nous permettent de diversifier et de compléter la production publicitaire.

Les clients de dynrem myTarget sont principalement des boutiques en ligne, qui peuvent avoir une ou plusieurs listes de produits. Lors de l'élaboration des recommandations, la paire «magasin - liste de marchandises» doit être considérée comme une unité distincte. Mais pour plus de simplicité, nous utiliserons simplement le "store" ensuite. Si nous parlons de la dimension de la tâche d'entrée, des recommandations doivent être élaborées pour environ un millier de magasins, et le nombre de marchandises peut varier de plusieurs milliers à des millions.

Le système de recommandation pour dynrem doit répondre aux exigences suivantes:

1. La bannière contient des produits qui maximisent son CTR.
2. Les recommandations sont construites hors ligne pendant un temps donné.
3. L'architecture du système doit être flexible, évolutive, stable et fonctionner dans un environnement de démarrage à froid.

Notez que de l'exigence de construire des recommandations pour un temps fixe et des conditions initiales décrites (nous supposerons avec optimisme que le nombre de magasins augmente), une exigence se pose naturellement pour l'utilisation économique des ressources de la machine.

La section 2 contient les fondements théoriques de la construction de systèmes de recommandation, les sections 3 et 4 discutent du côté pratique de la question et la section 5 résume le résultat global.

Concepts de base

Considérez la tâche de créer un système de recommandations pour un magasin et énumérez les approches mathématiques de base.

Décomposition en valeurs singulières (SVD)

Une approche populaire pour construire des systèmes de recommandation est l'approche de la décomposition singulière (SVD). Matrice de notation $$$R = (r_ {ui})$ représenter comme un produit de deux matrices $$$P$ et $$$Q$ pour que $$$R \ environ P Q ^ T$ puis note de l'utilisateur $$$u$ pour les marchandises $$$i$ représenté comme $$$\ hat {r} _ {ui} = <p_u, q_i>$ [1], où les éléments du produit scalaire sont des vecteurs dimensionnels $$$k$ (paramètre principal du modèle). Cette formule sert de base à d'autres modèles SVD. La tâche de trouver $$$P$ et $$$Q$ Cela se résume à l'optimisation des fonctionnalités:

(2.1)

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

où $$$L$ - fonction d'erreur (par exemple, RMSE comme dans la compétition Netflix ), $$$Λ$ - régularisation, et la sommation se fait sur des paires dont la cote est connue. Nous réécrivons l'expression (2.1) sous une forme explicite:

(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},$$

Ici $$$λ1$ , $$$λ2$ - Coefficients de régularisation L2 pour les représentations des utilisateurs $$$p_ {u}$ et marchandises $$$q_ {i}$ en conséquence. Le modèle de base du concours Netflix était:

(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},$$

où $$$µ$ , $$$b_ {u}$ et $$$b_ {i}$ - biais pour la notation, l'utilisateur et le produit, respectivement. Le modèle (2.3) - (2.4) peut être amélioré en y ajoutant une préférence utilisateur implicite. Dans l'exemple de la compétition Netflix, la réponse explicite est le score défini par l'utilisateur pour le film «à notre demande», et d'autres informations sur «l'interaction de l'utilisateur avec le produit» (visualisation du film, sa description, commentaires sur celui-ci; autrement dit, la réponse implicite ne donne pas de réponse implicite) informations directes sur la notation du film, mais en même temps indique un intérêt). La comptabilité des réponses implicites est implémentée dans le modèle SVD ++:

(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>,$$

où $$$S (u)$ - un ensemble d'objets avec lesquels l'utilisateur a implicitement interagi, $$$σ_ {u} = | S (u) |, y_ {j}$ - représentation dimensionnelle $$$k$ pour un objet de $$$S (u)$ .

Machines de factorisation (FM)

Comme on peut le voir dans les exemples avec différents modèles SVD, un modèle diffère d'un autre par l'ensemble des termes inclus dans la formule d'évaluation. De plus, l'expansion du modèle à chaque fois représente une nouvelle tâche. Nous voulons que ces changements (par exemple, l'ajout d'un nouveau type de réponse implicite, en tenant compte des paramètres de temps) soient facilement mis en œuvre sans changer le code de mise en œuvre du modèle. Les modèles (2.1) - (2.5) peuvent être représentés sous une forme universelle pratique en utilisant le paramétrage suivant. Nous représentons l'utilisateur et le produit comme un ensemble de fonctionnalités:

(2.6)

$$ $$\ overline {x} ^ U = (x_1 ^ U, x_2 ^ U, \ dots, 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.$$

Fig. 1: Un exemple de matrice de caractéristiques dans le cas de CF.

Par exemple, dans le cas du filtrage collaboratif (CF), lorsque seules des données sur l'interaction des utilisateurs et des produits sont utilisées, les vecteurs de caractéristiques ressemblent à un code unique (Fig.1). Introduire le vecteur $$$\ overline {x} = (\ overline {x} ^ U, \ overline {x} ^ I)$ , la tâche de recommandation est réduite à des problèmes de régression avec la variable cible $$$r_ {ui}$ :

1. Modèle linéaire:
   (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>$$

où $$$w_ {j}$ - paramètres du modèle, $$$v_ {i}$ Sont des vecteurs de dimension $$$k$ représentant le signe $$$i$ dans l'espace latent $$$l$ et $$$m$ - le nombre de signes de l'utilisateur et du produit, respectivement. En plus des codes uniques, les fonctionnalités basées sur le contenu (basées sur le contenu, CB) peuvent servir de signes (Fig.2), par exemple, des descriptions vectorisées de produits et de profils d'utilisateurs.


Fig. 2: Un exemple d'une matrice d'entités étendue.

Le modèle FM introduit dans [2] est une généralisation pour (2.1) - (2.5), (2.8), (2.10). L'essence de la FM est qu'elle prend en compte l'interaction par paires des fonctionnalités à l'aide d'un produit scalaire $$$<\ overline {v} _i, \ overline {v} _j>$ , n'utilisant pas le paramètre $$$w_ {ij}$ . L'avantage de FM sur Poly2 est une réduction significative du nombre de paramètres: pour les vecteurs $$$v_ {i}$ nous aurons besoin $$$(l + m) · k$ paramètres et $$$w_ {ij}$ sera nécessaire $$$lm m$ paramètres. À $$$l$ et $$$m$ pour les commandes importantes, la première approche utilise beaucoup moins de paramètres.

Remarque: s'il n'y a pas de paire spécifique dans l'ensemble d'entraînement $$$(i, j)$ , puis le terme correspondant avec $$$w_ {ij}$ dans Poly2, cela n'affecte pas la formation du modèle, et l'évaluation de la notation est formée uniquement sur la partie linéaire. Cependant, l'approche (2.10) nous permet d'établir des relations à travers d'autres fonctionnalités. En d'autres termes, les données sur une interaction aident à évaluer les paramètres des attributs qui ne sont pas inclus dans cet exemple.

Sur la base de la FM, un modèle dit hybride est implémenté dans lequel les attributs CB sont ajoutés aux attributs CF. Il vous permet de résoudre le problème d'un démarrage à froid, prend également en compte les préférences de l'utilisateur et vous permet de faire des recommandations personnalisées.

Lightfm

Dans la mise en œuvre populaire de la FM , l'accent est mis sur la séparation entre les caractéristiques de l'utilisateur et du produit. Les matrices agissent comme des paramètres de modèle $$$E ^ U$ et $$$E ^ I$ Soumission des fonctionnalités personnalisées et du produit:

(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$$

ainsi que les compensations $$$\ overline {b} ^ U, \ overline {b} ^ I \ in \ mathbb {R} ^ k$ . Utilisation des vues utilisateur et produit:

(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,$$

obtenir la note de la paire $$$(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>.$$

Fonction de perte

Dans notre cas, il est nécessaire de classer les produits pour un utilisateur spécifique afin qu'un produit plus pertinent ait une note plus élevée qu'un produit moins pertinent. LightFM a plusieurs fonctions de perte:

1. La logistique est une implémentation qui nécessite un négatif qui n'est pas explicitement présenté dans la plupart des tâches.
2. BPR [3] est de maximiser la différence de notes entre les exemples positifs et négatifs pour un utilisateur particulier. Le résultat négatif est obtenu par échantillonnage bootstrap. La fonctionnalité de qualité utilisée dans l'algorithme est similaire à ROC-AUC.
3. WARP [4] diffère de BPR par la méthode d'échantillonnage des exemples négatifs et la fonction de perte, qui est également classée, mais optimise en même temps les meilleures recommandations pour l'utilisateur.

Mise en œuvre pratique

Pour construire des recommandations pour un temps donné, une implémentation parallèle sur Spark est utilisée. Une tâche indépendante est lancée pour chaque magasin, dont l'exécution est contrôlée par luigi.

Prétraitement des données

Le prétraitement des données est effectué par des outils Spark SQL évolutifs automatiquement. Les fonctionnalités sélectionnées dans le modèle final sont des descriptions textuelles de produits et des catalogues avec des conversions standard.

Ce qui nous a aidés lors de l'interaction avec Spark:

1. Partitionnement des données préparées (matrice des interactions utilisateurs et produits, signes pour celles-ci) par magasins. Cela vous permet de gagner du temps pendant la phase de formation sur la lecture des données de HDFS. Sinon, chaque tâche doit lire les données dans la mémoire Spark et les filtrer par ID de magasin.
2. L'enregistrement / la réception de données vers / depuis Spark se fait en plusieurs parties. Cela est dû au fait que pendant l'une de ces actions, les données sont chargées dans la mémoire JVM. Pourquoi ne pas simplement augmenter la mémoire de la JVM? Premièrement, la mémoire disponible pour l'apprentissage du modèle diminue, et deuxièmement, il n'est pas nécessaire de stocker quoi que ce soit dans la JVM, il s'agit dans ce cas d'un stockage temporaire.

Formation modèle

Le modèle de chaque magasin est formé dans son propre conteneur Spark, de sorte que vous pouvez exécuter simultanément un nombre arbitraire de tâches pour les magasins, limité uniquement par les ressources du cluster.

LightFM manque de mécanismes d'arrêt précoce, par conséquent, nous dépensons des ressources supplémentaires pour des itérations supplémentaires de formation lorsqu'il n'y a pas d'augmentation de la métrique cible. Nous avons choisi l'ASC comme métrique, dont la relation avec le CTR est confirmée expérimentalement.

Dénote:

$$$S$ - toutes les interactions connues entre les utilisateurs et les produits, c'est-à-dire les paires $$$(u, i)$ ,
$$$I$ - beaucoup de tous les produits $$$i$ ,
$$$U$ - beaucoup de tous les utilisateurs $$$u$ .
Pour un utilisateur spécifique $$$u$ présenter également $$$I_ {u} = {i ∈ I: (u, i) ∈ S}$ - Beaucoup de produits avec lesquels l'utilisateur a interagi. L'AUC peut être calculée comme suit [réf]:

(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).$$

Dans la formule (3.1), nous devons calculer la note pour toutes les paires possibles $$$(u, i)$ ( $$$u$ fixe), ainsi que de comparer les notes des articles de $$$\ mathcal {I} _u$ avec des notes de $$$\ mathcal {I} \ setminus \ mathcal {I} _u$ . Étant donné que l'utilisateur interagit avec la partie limitée de l'assortiment, la complexité du calcul est $$$O (| \ mathcal {U} || \ mathcal {I} |)$ . En même temps, une ère de formation FM nous coûte $$$O (| \ mathcal {U} |)$ .

Par conséquent, nous avons modifié le calcul de l'ASC. Tout d'abord, vous devez diviser l'échantillon en une formation $$$\ mathcal {S} ^ {train} \ sous-ensemble \ mathcal {S}$ et validation $$$\ mathcal {S} ^ {val} \ sous-ensemble \ mathcal {S}$ et $$$\ mathcal {S} ^ {val} = \ mathcal {S} \ setminus \ mathcal {S} ^ {train}$ . Ensuite, nous utilisons l'échantillonnage pour créer de nombreux utilisateurs pour la validation $$$\ mathcal {U} ^ {val} \ sous-ensemble \ {u \ in \ mathcal {U}: (u, i) \ in \ mathcal {S} ^ {val} \}$. Pour l'utilisateur $$$u$de $$$\ mathcal {U} ^ {val}$les éléments de la classe positive seront considérés comme nombreux $$$\ mathcal {I} _u ^ {+} = \ {i \ in \ mathcal {I}: (u, i) \ in \ mathcal {S} ^ {val} \}$similaire $$$\ mathcal {I} _u$. En tant qu'éléments d'une classe négative, nous prenons un sous-échantillon $$$\ mathcal {I} _u ^ {-} \ sous-ensemble \ mathcal {I}$de sorte qu'aucun élément de $$$\ mathcal {I} _u$. La taille du sous-échantillon peut être prise proportionnellement à la taille. $$$\ mathcal {I} _u ^ {+}$c'est $$$| \ mathcal {I} _u ^ {-} | = c \ cdot | \ mathcal {I} _u ^ {+} |$. Ensuite, les formules (3.1), (3.2) pour calculer l'ASC changeront:

(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 (\ chapeau {r} _ {ui}> \ chapeau {r} _ {uj}),$$

(3.4)

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

En conséquence, nous obtenons un temps constant pour le calcul de l'ASC, car nous ne prenons qu'une partie fixe des utilisateurs, et les ensembles $$$\ mathcal {I} _u ^ {+}$et $$$\ mathcal {I} _u ^ {-}$avoir une petite taille. Le processus d'apprentissage pour le magasin s'arrête après que l'AUC (3.4) cesse de s'améliorer.

Rechercher des objets similaires

Dans le cadre de la tâche item2item, vous devez sélectionner pour chaque élément $$$n$(ou des produits aussi similaires que possible) à ceux qui maximisent la cliquabilité de la bannière. Notre hypothèse: les candidats à la bannière doivent être considérés $$$k$le plus proche dans les plongements spatiaux. Nous avons testé les méthodes suivantes pour calculer les «voisins les plus proches»: Scala + Spark, ANNOY, SCANNs, HNSW.


Pour Scala + Spark pour un magasin de 500 000 objets, il a fallu 15 minutes pour calculer une métrique cosinus honnête et une quantité importante de ressources de cluster, nous avons donc testé des méthodes approximatives pour trouver les voisins les plus proches. Lors de la recherche de la méthode SCANNs, les paramètres suivants variaient: bucketLimit , shouldSampleBuckets , NumHashes et setSignatureLength , mais les résultats se sont révélés insatisfaisants par rapport à d'autres méthodes (des objets très différents sont tombés dans le compartiment). Les algorithmes ANNOY et HNSW ont montré des résultats comparables à un cosinus honnête, mais ont fonctionné beaucoup plus rapidement.

	200k produits		500k marchandises		2,2 millions de produits
Algorithme	ANNOY	Hnsw	ANNOY	Hnsw	ANNOY	Hnsw
temps de construction index (sec)	59,45	8.64	258.02	25,44	1190.81	90,45
temps total (sec)	141,23	14/01	527,76	43,38	2081,57	150,92

Étant donné que HNSW fonctionnait plus rapidement que tous les algorithmes, nous avons décidé de nous y arrêter.
Nous recherchons également les voisins les plus proches dans le conteneur Spark et écrivons le résultat dans Hive avec le partitionnement approprié.

Conclusion

Rappel: nous utilisons WARP pour former le modèle, l'AUC pour l'arrêt précoce, et l'évaluation finale de la qualité est effectuée à l'aide du test A / B sur le trafic en direct.

Nous pensons qu'à cet endroit - en organisant l'expérience et en sélectionnant la composition optimale de la bannière - les données se terminent et la science commence. Ici, nous apprenons à déterminer s'il est logique d'afficher des recommandations pour les produits pour lesquels le reciblage a fonctionné; exactement combien de recommandations montrer; combien de produits consultés, etc. Nous en parlerons dans les articles suivants.

D'autres améliorations de l'algorithme - la recherche de plongements universels qui permettront de placer les produits de tous les magasins dans un seul espace - sont effectuées dans le cadre du paradigme décrit au début de l'article.

Merci de votre attention!

Littérature

[1] Ricci F., Rokach L., Shapira B. Introduction au manuel des systèmes de recommandation
// Manuel des systèmes de recommandation. - Springer, Boston, MA, 2011 .-- S. 147160.

[2] Machines de factorisation Rendle S. // Conférence internationale 2010 de l'IEEE sur l'exploration de données. - IEEE, 2010 .-- S. 995-1000.

[3] Rendle S. et al. BPR: classement personnalisé bayésien à partir de retours implicites
// Actes de la vingt-cinquième conférence sur l'incertitude dans l'intelligence artificielle.
- AUAI Press, 2009 .-- S. 452-461.

[4] Weston J., Bengio S., Usunier N. Wsabie: passage à l'échelle des annotations d'images de vocabulaire // Vingt-deuxième Conférence conjointe internationale sur l'intelligence artificielle. - 2011.