Anatomie des systèmes de recommandation. Deuxième partie

Il y a une semaine, j'ai fait un aperçu des algorithmes de recommandation existants ici . Dans cet article, je poursuivrai cette revue: je parlerai de la variante par élément du filtrage collaboratif, des méthodes basées sur les décompositions matricielles, des problèmes de test, et aussi des algorithmes moins «sans torsion» (mais pas moins intéressants).

Filtrage collaboratif (option basée sur les éléments)

L'approche par éléments est une alternative naturelle à l'approche par utilisateurs classique décrite dans la première partie, et la répète presque complètement, à l'exception d'un point - elle s'applique à la matrice de préférence transposée. C'est-à-dire à la recherche de produits connexes, pas d'utilisateurs.

Permettez-moi de vous rappeler que le filtrage collaboratif basé sur l'utilisateur (CF basé sur l'utilisateur) recherche pour chaque client un groupe de clients le plus similaire (en termes d'achats précédents) et fait la moyenne de leurs préférences. Ces préférences moyennes servent de recommandations à l'utilisateur. Dans le cas du filtrage collaboratif des produits (CF par article), les voisins les plus proches sont recherchés sur l'ensemble des produits - colonnes de la matrice de préférence. Et la moyenne se produit précisément sur eux.

En effet, si les produits sont substantiellement similaires, il est très probable qu'ils soient appréciés ou non en même temps. Par conséquent, lorsque nous constatons que deux produits ont de fortes corrélations, cela peut indiquer qu'il s'agit de produits similaires.

Avantages de l'article par rapport à l'utilisateur:

• Lorsqu'il y a beaucoup d'utilisateurs (presque toujours), la tâche de trouver le voisin le plus proche devient mal calculable. Par exemple, pour 1 million d'utilisateurs, vous devez calculer et stocker $$$\ frac {1} {2} 10 ^ 6 * 10 ^ 6$~ 500 milliards de distances. Si la distance est codée avec 8 octets, cela donne 4 To pour la matrice de distance seule. Si nous faisons par article, la complexité des calculs diminue avec $$$O (N ^ 2n)$avant $$$O (n ^ 2N)$et la matrice de distance n'a plus une dimension (1 million pour 1 million), mais, par exemple (100 pour 100) par le nombre de marchandises.
  
• L'indice de proximité est beaucoup plus précis que l'indice de proximité. Ceci est une conséquence directe du fait qu'il y a généralement beaucoup plus d'utilisateurs que de biens, et donc l'erreur type dans le calcul de la corrélation des biens est beaucoup moins. Nous avons juste plus d'informations pour tirer une conclusion.
  
• Dans la version basée sur l'utilisateur, les descriptions des utilisateurs sont généralement très rares (il existe de nombreux produits, peu de notes). D'une part, cela aide à optimiser le calcul - nous multiplions uniquement les éléments où il y a une intersection. Mais d'un autre côté - combien de voisins vous ne prenez pas, la liste des produits que vous pouvez éventuellement recommander est très petite.
  
• Les préférences de l'utilisateur peuvent changer avec le temps, mais la description de l'article est beaucoup plus stable.
  

Le reste de l'algorithme répète presque complètement l'option basée sur l'utilisateur: la même distance cosinus que la mesure principale de proximité, le même besoin de normalisation des données. Le nombre de marchandises voisines N est généralement choisi dans la région de 20.

Étant donné que la corrélation des produits est prise en compte sur un plus grand nombre d'observations, il n'est pas si critique de la recalculer après chaque nouvelle évaluation, et vous pouvez le faire périodiquement en mode bataille.

Plusieurs améliorations possibles à l'algorithme:

• Une modification intéressante consiste à considérer la «similitude» des produits non pas comme des distances de cosinus typiques, mais en comparant leur contenu (similitude basée sur le contenu). Si, en même temps, les préférences des utilisateurs ne sont en aucun cas prises en compte, ce filtrage cesse d'être «collaboratif». De plus, la deuxième partie de l'algorithme - l'obtention d'estimations moyennes - ne change en rien.
• Une autre modification possible consiste à peser les utilisateurs lors du calcul de la similitude des éléments. Par exemple, plus les utilisateurs font de notes, plus ils ont de poids lorsqu'ils comparent deux produits.
• Au lieu de simplement faire la moyenne des estimations des produits voisins, les poids peuvent être sélectionnés en effectuant une régression linéaire.

Lors de l'utilisation de l'approche par éléments, les recommandations ont tendance à être plus conservatrices. En effet, la dispersion des recommandations est moindre et donc moins susceptible de montrer des produits non standard.

Si, dans la matrice des préférences, nous utilisons la vue de description du produit comme note, les produits recommandés sont le plus souvent des analogues - des produits qui sont souvent vus ensemble. Si nous calculons les notes dans la matrice des préférences en fonction des achats, alors les produits recommandés seront probablement des accessoires - des produits qui sont souvent achetés ensemble.

Évaluation de la qualité du système

Tester le système de recommandation est un processus difficile et soulève toujours de nombreuses questions, principalement en raison de l'ambiguïté du concept même de «qualité».

En général, dans les tâches d'apprentissage automatique, il existe deux principales approches de test:

• tests hors ligne du modèle sur des données historiques à l'aide de rétro-tests,
• tester le modèle fini à l'aide de tests A / B (nous lançons plusieurs options, voir laquelle donne le meilleur résultat).

Ces deux approches sont activement utilisées dans l'élaboration de systèmes de recommandation. Commençons par les tests hors ligne.

La principale limitation à laquelle vous devez faire face est d'évaluer l'exactitude des prévisions que nous pouvons uniquement sur les produits que l'utilisateur a déjà évalués.

L'approche standard est la validation croisée avec des méthodes de sortie de session et de sortie de session. La répétition répétée du test avec la moyenne des résultats permet d'obtenir une évaluation de la qualité plus stable.

• laisser de côté - le modèle est formé sur tous les objets évalués par l'utilisateur, à l'exception d'un seul, et est testé sur ce seul objet. Ceci est fait pour tous les n objets, et la moyenne est calculée parmi les n estimations de qualité obtenues.
• laisser-p-out est le même, mais p points sont exclus à chaque étape.

Toutes les mesures de qualité peuvent être divisées en trois catégories:

• Précision de la prédiction - évaluer l'exactitude de la cote prédite,
• Aide à la décision - évaluer la pertinence des recommandations,
• Classer les mesures de précision - évaluer la qualité du classement des recommandations émises.
  

Malheureusement, il n'y a pas de métrique recommandée unique pour toutes les occasions, et tous ceux qui sont impliqués dans le test du système de recommandation le sélectionnent à leurs propres fins.

Lorsque les notes sont notées sur une échelle continue (0-10), les métriques de classe de précision de prédiction sont généralement suffisantes.
Les métriques de classe d'aide à la décision fonctionnent avec des données binaires (0 et 1, oui et non). Si dans notre tâche les notes sont initialement reportées sur une échelle continue, elles peuvent être converties au format binaire en appliquant la règle décisive - disons, si la note est inférieure à 3,5, nous considérons la note «mauvaise», et si supérieure, alors «bonne».
En règle générale, les recommandations sont affichées dans une liste de plusieurs positions (d'abord en haut, puis par ordre décroissant de priorité). Les métriques de classe de précision de classement mesurent dans quelle mesure l'ordre dans lequel les recommandations sont affichées dans une liste triée est correct.
Si nous prenons des systèmes de recommandation dans les affaires en ligne, alors, en règle générale, ils ont deux objectifs (parfois contradictoires):

1. informer l'utilisateur d'un produit intéressant,
2. Encouragez-le à faire un achat (par la poste, en compilant une offre personnelle, etc.).

Comme dans tout modèle visant à motiver l'utilisateur à agir, seule l'augmentation incrémentielle de l'action cible doit être évaluée. C'est-à-dire, par exemple, lors du calcul des achats par recommandation, nous devons exclure ceux que l'utilisateur lui-même aurait fait sans notre modèle. Si cela n'est pas fait, l'effet de l'introduction du modèle sera largement surestimé.

La portance est un indicateur du nombre de fois où la précision d'un modèle dépasse un certain algorithme de base. Dans notre cas, l'algorithme de base peut simplement être le manque de recommandations. Cette mesure capture bien la part des achats incrémentiels, ce qui vous permet de comparer efficacement différents modèles.

Test utilisateur

Source

Le comportement de l'utilisateur est une chose mal formalisée et pas une seule métrique ne décrira pleinement les processus de pensée dans sa tête lors du choix d'un produit. La décision est influencée par de nombreux facteurs. Cliquer sur un lien avec un produit recommandé n'a pas encore sa cote élevée ni même son intérêt. Les tests en ligne permettent de comprendre partiellement la logique du client. Voici quelques scénarios pour de tels tests.

Le premier et le plus évident scénario est l'analyse des événements du site. Nous regardons ce que l'utilisateur fait sur le site, fait-il attention à nos recommandations, les suit-il, quelles fonctionnalités du système sont demandées, lesquelles ne le sont pas, quels produits sont mieux recommandés, quels sont les pires. Pour comprendre lequel des algorithmes dans son ensemble fonctionne mieux ou simplement essayer une nouvelle idée prometteuse, nous faisons des tests A / B et collectons le résultat.

Le deuxième scénario reçoit des commentaires des utilisateurs sous forme de sondages et de sondages. En règle générale, ce sont des questions générales pour comprendre comment les clients utilisent le service - ce qui est plus important: la pertinence ou la diversité, s'il est possible de montrer des produits en double ou est-ce trop ennuyeux. L'avantage du script est qu'il fournit une réponse directe à toutes ces questions.

De tels tests sont une chose compliquée, mais pour les grands services de recommandation, ils sont simplement nécessaires. Les questions peuvent être plus compliquées, par exemple, «laquelle des listes vous semble la plus pertinente», «à quel point la feuille semble complète», «allez-vous regarder ce film / lire un livre».

Évaluations implicites et données unaires

Au début de son développement, des systèmes de recommandation ont été utilisés dans les services où l'utilisateur évalue clairement le produit en le notant - il s'agit d'Amazon, de Netflix et d'autres sites de commerce en ligne. Cependant, avec la popularité des systèmes de recommandation, il était nécessaire de les utiliser également en l'absence de notes - il peut s'agir de banques, d'ateliers de réparation automobile, de kiosques avec shawarma et de tout autre service où, pour une raison quelconque, il est impossible d'établir un système d'évaluation. Dans ces cas, les intérêts de l'utilisateur ne peuvent être calculés que par des signes indirects - certaines actions avec le produit indiquent les préférences de l'utilisateur, par exemple, afficher la description sur le site, ajouter le produit au panier, etc. Il utilise le principe "acheté - cela signifie l'amour!". Un tel système de notation implicite est appelé notation implicite.

Les évaluations implicites fonctionnent évidemment moins bien que les évaluations explicites, car elles ajoutent un ordre de grandeur plus de bruit. Après tout, un utilisateur pouvait acheter un produit en cadeau à sa femme ou aller sur une page avec une description du produit, seulement pour y laisser un commentaire dans le style de "quel genre de méchanceté est-ce tout de même" ou pour satisfaire sa curiosité naturelle.

Si dans le cas de notations explicites, nous avons le droit de nous attendre à ce qu'au moins une note négative soit non, non et oui, nous ne prendrons aucune note négative de nulle part. Si l'utilisateur n'a pas acheté le livre «Cinquante nuances de gris», il pourrait le faire pour deux raisons:

• elle n'est vraiment pas intéressée par lui (c'est un cas négatif),
  
• elle s'intéresse à lui, mais il ne sait tout simplement pas d'elle (c'est un cas positif manqué).
  

Mais nous n'avons pas de données pour distinguer le premier cas du second. C'est mauvais, car lors de la formation d'un modèle, nous devons le renforcer sur les cas positifs et bien sur les cas négatifs, et donc nous serons presque toujours bien, et en conséquence, le modèle sera biaisé.

Le deuxième cas est la possibilité de ne laisser que des notes positives. Un exemple frappant est le bouton J'aime sur les réseaux sociaux. La note ici est déjà explicitement notée, mais comme dans l'exemple précédent, nous n'avons pas d'exemples négatifs - nous savons quels canaux l'utilisateur aime, mais nous ne savons pas lesquels il n'aime pas.

Dans les deux exemples, la tâche se transforme en tâche de classification de classe unaire .

La solution la plus évidente consiste à suivre un chemin simple et à considérer l'absence de notation comme une notation négative. Dans certains cas, cela est plus justifié, dans certains moins. Par exemple, si nous savons que l'utilisateur a très probablement vu le produit (par exemple, nous lui avons montré la liste des produits et qu'il est passé au produit qui le suit), le manque de transition peut vraiment indiquer un manque d'intérêt.

Source

Algorithmes de factorisation

Il serait intéressant de décrire les intérêts de l'utilisateur dans des «traits» plus importants. Pas au format «il aime les films X, Y et Z», mais au format «il aime les comédies russes modernes». Outre le fait que cela augmentera la généralisabilité du modèle, cela résoudra également le problème d'une grande dimensionnalité des données - car les intérêts seront décrits non pas par un vecteur de biens, mais par un vecteur de préférences nettement plus petit.

De telles approches sont également appelées décomposition spectrale ou filtrage passe-haut (car nous supprimons le bruit et laissons un signal utile). Il existe de nombreuses décompositions différentes de matrices en algèbre, et l'une des plus couramment utilisées est appelée décomposition SVD (décomposition en valeurs singulières).

La méthode SVD a été utilisée à la fin des années 80 pour sélectionner des pages de sens similaire, mais pas de contenu, puis a commencé à être utilisée dans les tâches de recommandations. La méthode est basée sur la décomposition de la matrice initiale des notations ® en un produit de 3 matrices:

$$$R = U * D * S$où les tailles des matrices $$$(k, m) = (k, r) * (r, r) * (r, m)$, et r est
rang de décomposition - paramètre caractérisant le degré de détail de décomposition.

En appliquant cette décomposition à notre matrice de préférence, nous obtenons deux matrices de facteurs (descriptions abrégées):

U - description compacte des préférences de l'utilisateur,
S est une description compacte des caractéristiques du produit.

Il est important qu'avec cette approche, nous ne sachions pas quelles caractéristiques correspondent aux facteurs dans les descriptions réduites, pour nous, elles sont codées avec certains nombres. Par conséquent, SVD est un modèle non interprété.

Pour obtenir une approximation de la matrice des préférences, il suffit de multiplier la matrice des facteurs. Cela fait, nous obtenons un score de notation pour toutes les paires client-produit.

La famille générale de ces algorithmes est appelée NMF (factorisation matricielle non négative). En règle générale, le calcul de ces extensions prend beaucoup de temps, par conséquent, dans la pratique, elles ont souvent recours à leurs variantes itératives approximatives.

La SLA (alternance des moindres carrés) est un algorithme itératif populaire pour décomposer une matrice de préférence en un produit de 2 matrices: les facteurs utilisateurs (U) et les facteurs produits (I). Il fonctionne sur le principe de la minimisation de l'erreur type des notations. L'optimisation se fait alternativement, d'abord par des facteurs utilisateurs, puis par des facteurs produits. De plus, pour contourner le recyclage, des coefficients de régularisation sont ajoutés à l'erreur standard.


Si nous complétons la matrice de préférence par une nouvelle dimension contenant des informations sur l'utilisateur ou le produit, nous pourrons développer non pas la matrice de préférence, mais le tenseur. Ainsi, nous utiliserons plus d'informations disponibles et obtiendrons éventuellement un modèle plus précis.

D'autres approches

Règles d'association

Les règles associatives sont généralement utilisées dans l'analyse des corrélations de produits (analyse du panier de consommation) et ressemblent à ceci: "s'il y a du lait dans le chèque du client, alors dans 80% des cas il y aura du pain". Autrement dit, si nous voyons que le client a déjà mis du lait dans le panier, il est temps de rappeler le pain.

Ce n'est pas la même chose que l'analyse des achats espacés dans le temps, mais si nous considérons toute l'histoire comme un grand panier, nous pouvons appliquer pleinement ce principe ici. Cela peut être justifié lorsque, par exemple, nous vendons des biens ponctuels coûteux (crédit, vol).

RBM (machines Bolzman restreintes)

Les machines Boltzmann bornées sont une approche relativement ancienne basée sur des réseaux de neurones récurrents stochastiques. C'est un modèle avec des variables latentes et en cela est similaire à la décomposition SVD. Il recherche également la description la plus compacte des préférences de l'utilisateur, qui est codée à l'aide de variables latentes. La méthode n'a pas été développée pour rechercher des recommandations, mais elle a été utilisée avec succès dans les meilleures solutions Netflix Prize et est toujours utilisée dans certaines tâches.

Codeurs automatiques

Il est basé sur le même principe de décomposition spectrale, c'est pourquoi ces réseaux sont aussi appelés auto-encodeurs débruiteurs. Le réseau réduit d'abord les données utilisateur qu'il connaît en une représentation compacte, essayant de ne laisser que des informations significatives, puis restaure les données à leur dimension d'origine. Le résultat est une sorte de modèle moyen et sans bruit grâce auquel vous pouvez évaluer l'intérêt pour n'importe quel produit.

DSSM (modèles de similitude sémantique profonde)

Une des nouvelles approches. Toujours le même principe, mais dans le rôle des variables latentes, voici les descriptions tensorielles internes des données d'entrée (plongements). Initialement, le modèle a été créé pour la correspondance des requêtes avec les documents (ainsi que les recommandations basées sur le contenu), mais il est facilement transformé en tâche de mise en correspondance des utilisateurs et des produits.


, Deep Learning .

. , .

— . — .

:

• Weighting — ,
  
• Stacking — (), ,
  

• Switching — / ,
  
• Mixing — , .
  

, content-based recommender, — .

Feature Weighted (Linear) Stacking:

$$

$$P(u,i) = w_1 P_1(u,i) + w_2 P_2(u,i) + … + w_n P_n(u,i)$$

$$$w_1,w_2 … w_n$. , .

Stacking :

$$

$$P(u,i) = f_1(u,i) P_1(u,i) + f_2(u,i) P_2(u,i) + … + f_n(u,i) P_n(u,i)$$

Netflix

Netflix Prize — , 2009 , Netflix. 1 , .

, 1 5, RMSE. .

:

• basic model — ,
  
• collaborative filtering —
  
• RBM —
  
• random forests —
  

-, , .

Résumé

La tâche de générer des recommandations est très simple - nous compilons une matrice de préférence avec les estimations des utilisateurs connues, si cela s'avère, nous complétons ces estimations avec des informations sur le client et le produit, et essayons de remplir les valeurs inconnues.

Malgré la simplicité de la déclaration, des centaines d'articles sont publiés qui décrivent des méthodes fondamentalement nouvelles pour le résoudre. Premièrement, cela est dû à une augmentation de la quantité de données collectées pouvant être utilisées dans le modèle et à une augmentation du rôle des notations implicites. Deuxièmement, avec le développement de l'apprentissage en profondeur et l'avènement de nouvelles architectures de réseaux de neurones. Tout cela multiplie la complexité des modèles.

Mais en général, toute cette diversité se résume à un très petit ensemble d'approches, que j'ai essayé de décrire dans cet article.