Upload
others
View
6
Download
0
Embed Size (px)
Citation preview
Mineure « Data Science » Frédéric Pennerath
SYSTÈMES DE RECOMMANDATION
Chapitre 6
Mineure « Data Science » Frédéric Pennerath
Marketing personnalisé et
système de recommandation
Données : matrice creuse 𝑅 de notes des acheteurs pour des articles
Problème : quels articles recommander à un utilisateur ?
Articles
Utilisateurs
A1 A2 A3 … Acible
U1
U2
U3
Ucible ?
…
Articles
Nbr.
de v
ente
s
Remarques / difficultés :
• Cas dégénéré : notes unaires (1 = achat, pas de 0)
• Très grande matrice creuse
• Nbr. de recommandations par articles très variable (distrib. à longue traîne)
• Asymétrie : seule la prédiction des notes élevées présente un intérêt
• Problème du « cold start » : ligne / colonne vierge pour un nouvel utilisateur / article
Deux approches : basées sur le contenu ou « model based » / filtrage collaboratif ou « model free »
Loi de Zipf :
𝑃 𝐴𝑖 ∝1
𝑖
Mineure « Data Science » Frédéric Pennerath
Un problème d’apprentissage supervisé :
exemple du challenge Netflix
Données : 500K abonnés, 20K de films, 100M notes matrice à 99% vide
Challenge : minimiser l’erreur quadratique de prédiction
Films
AbonnésFilms apprentissage Films test
Abonnés
apprentissage
Abonnés
test
𝐸𝑅𝑀𝑆𝐸 =1
𝑅
𝑟𝑎,𝑓∈𝑅
𝑟𝑎,𝑓 − 𝑟𝑎,𝑓2
Mineure « Data Science » Frédéric Pennerath
RECOMMANDATIONS BASÉES SUR LE
CONTENU
Mineure « Data Science » Frédéric Pennerath
Recommandations fondées sur le contenu
Données : matrice articles / caractéristiques + matrice creuse des notes utilisateurs
Principe :
1. Construire un profil utilisateur à partir des profils d’articles consommés
2. Chercher les k profils d’articles les plus similaires au profil d’utilisateur
Films
Utilisateurs
F1 F2 F3 F4 F5 F6
U1 0 5 1 4 5
U2 4 2 5 5
U3 5 1 5 1
Caractéristiques
Films
Réalisateur Acteurs Genres
Rambo IV S. Stallone S. Stallone action,
thriller
Full Metal Jacket S. Kubrick M. Modine drame,
guerre
Rocky II S. Stallone S. Stallone drame,
action
Top Gun T. Scott T. Cruise action,
guerre
Docteur
Folamour
S. Kubrick P. Sellers comédie,
guerre
Eyes Wide Shut S. Kubrick T. Cruise, N.
Kidman
drame
Mineure « Data Science » Frédéric Pennerath
Construction des profils utilisateurs
Caractéristiques
Films
Réalisateur Acteurs Genres
Rambo IV S. Stallone S. Stallone action,
thriller
Full Metal Jacket S. Kubrick M. Modine drame,
guerre
Rocky II S. Stallone S. Stallone drame,
action
Top Gun T. Scott T. Cruise action,
guerre
Docteur
Folamour
S. Kubrick P. Sellers comédie,
guerre
Eyes Wide Shut S. Kubrick T. Cruise,
N. Kidman
drame
Films
Utilisateurs
F1 F2 F3 F4 F5 F6
U1 0 5 1 4 5
U2 4 2 5 5
U3 5 1 5 1
Calcul des coordonnées pour chaque caractéristique :
𝑈1 = −3 𝐹1 + 2 𝐹2 − 2 𝐹3 + 𝐹5 + 2 𝐹6
= −3 𝑆𝑡𝑎𝑙𝑙𝑜𝑛𝑒 𝑟é𝑎𝑙. + 𝑆𝑡𝑎𝑙𝑙𝑜𝑛𝑒 𝑎𝑐𝑡. + 𝑎𝑐𝑡𝑖𝑜𝑛 + 𝑡ℎ𝑟𝑖𝑙𝑙𝑒𝑟 + ⋯
= −3 − 2 𝑆𝑡𝑎𝑙𝑙𝑜𝑛𝑒 𝑟é𝑎𝑙. + 2 + 1 + 2 𝐾𝑢𝑏𝑟𝑖𝑐𝑘 + −3 − 2 𝑆𝑡𝑎𝑙𝑙𝑜𝑛𝑒 𝑎𝑐𝑡. + 2 𝐶𝑟𝑢𝑖𝑠𝑒 +⋯
= 5 𝐾𝑢𝑏𝑟𝑖𝑐𝑘 + 3 𝑔𝑢𝑒𝑟𝑟𝑒 + 2 𝑑𝑟𝑎𝑚𝑒 + 2 𝐶𝑟𝑢𝑖𝑠𝑒 + ⋯− 5 𝑎𝑐𝑡𝑖𝑜𝑛 − 5 𝑆𝑡𝑎𝑙𝑙𝑜𝑛𝑒 𝑟é𝑎𝑙.
Films
Utilisateurs
F1 F2 F3 F4 F5 F6
U1 -3 2 -2 1 2
U2 0 -2 1 1
U3 2 -2 2 -2
Centrage
Mineure « Data Science » Frédéric Pennerath
Recherche des profils d’articles similaires
K films les plus
similaires
Requête = profil
utilisateur
Moteur de
recherche
d’information
Index inversé
des films
Principe :
1. Indexer chaque article par ses caractéristiques :
Exemple : 𝑇𝑜𝑝 𝐺𝑢𝑛 = 𝑆𝑐𝑜𝑡𝑡 + 𝐶𝑟𝑢𝑖𝑠𝑒 + 𝑔𝑢𝑒𝑟𝑟𝑒 + 𝑎𝑐𝑡𝑖𝑜𝑛
2. Chercher les k profils d’articles les plus similaires au profil d’utilisateur en utilisant le modèle
vectoriel (𝑠𝑖𝑚 = 𝑐𝑜𝑠) :
Requête:
5 𝐾𝑢𝑏𝑟𝑖𝑐𝑘 + 3 𝑔𝑢𝑒𝑟𝑟𝑒 + 2 𝑑𝑟𝑎𝑚𝑒
+ 2 𝐶𝑟𝑢𝑖𝑠𝑒 +⋯− 5 𝑎𝑐𝑡𝑖𝑜𝑛
− 5 𝑆𝑡𝑎𝑙𝑙𝑜𝑛𝑒 (𝑟é𝑎𝑙. )
Réponses :
• Les sentiers de la Gloire (Kubrick, drame, guerre)
• Lolita (Kubrick, drame, Sellers)
• Des hommes d’honneur (guerre, drame, Cruise)
Avantages : fonctionne pour les nouveaux articles pas encore évalués
Inconvénient : nécessite un modèle d’articles et d’extraire une liste de caractéristiques
(pertinence, partialité)
→ Filtrage collaboratif
Mineure « Data Science » Frédéric Pennerath
FILTRAGE COLLABORATIF
Mineure « Data Science » Frédéric Pennerath
Principe général (version naïve)
Algorithme semblable aux k plus proches voisins :
1. Sélection des utilisateurs 𝑈𝑖 ayant évalués Acible
2. Détermination des k utilisateurs 𝑈𝑖 1≤𝑖≤𝑘 les plus similaires à Ucible selon une fonction de similarité
𝑠𝑖𝑚 𝑈𝑖 , 𝑈𝑐𝑖𝑏𝑙𝑒 ≥ 0.
Utilisation d’un index inversé des 𝑈𝑖 indexés selon les 𝐴𝑗
3. Prédiction barycentrique du score :
𝑠 𝑈𝑐𝑖𝑏𝑙𝑒 , 𝐴𝑐𝑖𝑏𝑙𝑒 = 𝑖=1𝑘 𝑠𝑖𝑚 𝑈𝑖 , 𝑈𝑐𝑖𝑏𝑙𝑒 ⋅ 𝑠 𝑈𝑖 , 𝐴𝑐𝑖𝑏𝑙𝑒 𝑖=1𝑘 𝑠𝑖𝑚 𝑈𝑖 , 𝑈𝑐𝑖𝑏𝑙𝑒
Articles
Utilisateurs
A1 A2 A3 Acible
U1 5 4
U2 4 3 1
U3 4
Ucible 4 0 2 ?
Données : uniquement la matrice de recommandation (model free)
Mineure « Data Science » Frédéric Pennerath
Choix de la fonction de similarité
Exemple du modèle vectoriel :
𝑠𝑖𝑚 𝑈𝑖 , 𝑈𝑐𝑖𝑏𝑙𝑒 = cos 𝑈𝑖 , 𝑈𝑐𝑖𝑏𝑙𝑒 = 𝑗 𝑠 𝑈𝑖 , 𝐴𝑗 ⋅ 𝑠 𝑈𝑐𝑖𝑏𝑙𝑒 , 𝐴𝑗
𝑗 𝑠 𝑈𝑖 , 𝐴𝑗2 𝑗 𝑠 𝑈𝑐𝑖𝑏𝑙𝑒 , 𝐴𝑗
2
Exemple :
𝑠𝑖𝑚 𝑈1, 𝑈𝑐𝑖𝑏𝑙𝑒 =5 × 4 + 0 × 0 + 0 × 2
52 42 + 22= 0,89
Articles
Utilisateurs
A1 A2 A3
U1 5
U2 4 3
Ucible 4 0 2
𝑠𝑖𝑚 𝑈𝑖 , 𝑈𝑐𝑖𝑏𝑙𝑒
0,89
0,26
1
Acible
4
1
Problèmes :
Ne tient pas compte du caractère creux (case vide⟺ score nul )
Les utilisateurs ne notent pas tous selon la même échelle.
3,3
⇒ 𝑠 𝑈𝑐𝑖𝑏𝑙𝑒 , 𝐴𝑐𝑖𝑏𝑙𝑒 =0,89 ⋅ 𝟒 + 0,26 ⋅ 𝟏
0,89 + 0,26≈ 𝟑, 𝟑
Mineure « Data Science » Frédéric Pennerath
Choix de la fonction de similarité
Articles
Utilisateurs
A1 A2 A3 Acible
U1 5 4
U2 4 3 1
Ucible 4 0 2
Articles
Utilisateurs
A1 A2 A3 Acible
U1 0,5 0 0 -0,5
U2 0 1,33 0,33 -1,66
Ucible 2 -2 0 0
Problèmes :
Sur-apprentissage (peu de profils fortement similaires) + « cold start » → Recours à un prédicteur de base
Profils utilisateurs complexes (goûts multiples) → Problème dual : similarité entre articles (profil plus singulier)
𝑠 𝑈𝑖 ,∗
4,5
2,66
2
𝑠𝑖𝑚 𝑈𝑖 , 𝑈𝑐𝑖𝑏𝑙𝑒
0,75
0,28
1
Acible
4
1
3,18
Solution : centrage des notes sur 0 + remplissage (implicite) des cases vides par 0
𝑠𝑖𝑚 𝑈𝑖 , 𝑈𝑐𝑖𝑏𝑙𝑒 =1
21 +
𝑗 𝑠 𝑈𝑖 , 𝐴𝑗 − 𝑠 𝑈𝑖 ,∗ ⋅ 𝑠 𝑈𝑐𝑖𝑏𝑙𝑒 , 𝐴𝑗 − 𝑠 𝑈𝑐𝑖𝑏𝑙𝑒 ,∗
𝑗 𝑠 𝑈𝑖 , 𝐴𝑗 − 𝑠 𝑈𝑖 ,∗2 𝑗 𝑠 𝑈𝑐𝑖𝑏𝑙𝑒 , 𝐴𝑗 − 𝑠 𝑈𝑐𝑖𝑏𝑙𝑒 ,∗
2
=1
21 + 𝑐𝑜𝑟𝑟 𝑠 𝑈𝑖 ,∗ , 𝑠 𝑈𝑐𝑖𝑏𝑙𝑒 ,∗
Calcul
des biais
Centrage +
complétion
Calcul des
similarités
(corrélation)
Prédiction
barycentrique
Mineure « Data Science » Frédéric Pennerath
Prédicteur de « base » (baseline)
Articles
Utilisateurs
A1 A2 A3 A4
U1 5 4
U2 4 3 1
U3 4 0 2
𝑠 ∗,∗
𝑠𝑏 𝑈3, 𝐴4 = 2,875 + 2 − 2,875 + 2,5 − 2,875
Articles
Utilisateurs
A1 A2 A3 A4 𝑠 𝑈𝑖 ,∗
U1 5 4 4,5
U2 4 3 1 2,66
U3 4 0 2 2
𝑠 ∗, 𝐴𝑗 4,5 2 2,5 2,5 2,875
Articles
Utilisateurs
A1 A2 A3 A4
U1 6,13 3,63 4,13 4,13
U2 4,29 1,79 2,29 2,29
U3 3,63 1,13 1,63 1,63
𝑠𝑏 𝑈𝑖 , 𝐴𝑗 = 𝑠 ∗,∗ + 𝑠 𝑈𝑖 ,∗ − 𝑠 ∗,∗ + 𝑠 ∗, 𝐴𝑗 − 𝑠 ∗,∗
Note
moyenneBiais utilisateur Biais article
But : prédiction systématique sans sur apprentissage
Prédiction
baseline
Calcul
des
biais
Calcul des prédictions de base
Mineure « Data Science » Frédéric Pennerath
Correction par filtrage collaboratif
Articles
Utilisateurs
A1 A2 A3 A4
U1 5 4
U2 4 3 1
U3 4 0 2
Articles
Utilisateurs
A1 A2 A3 A4
U1 -1,125 0 0 -0,125
U2 0 2,208 0,708 -1,292
U3 0,375 -1,125 0,375 0
Articles
Articles
A1 A2 A3 A4
A1 1 0,47 0,87 0,40
A2 0,47 1 0,81 0,016
A3 0,87 0,81 1 0,10
A4 0,40 0,016 0,10 1
𝑠𝑐 = 𝑠 − 𝑠𝑏
𝑠𝑖𝑚 𝐴𝑖 , 𝐴𝑗 =1 + 𝑐𝑜𝑟𝑟 𝑠𝑐 ∗, 𝐴𝑖 , 𝑠𝑐 ∗, 𝐴𝑗
2
𝑠𝑓 𝑈𝑖 , 𝐴𝑗 = 𝑗′=1𝑘 𝑠𝑖𝑚 𝐴𝑗 , 𝐴𝑗′ ⋅ 𝑠𝑐 𝑈𝑖 , 𝐴𝑗′
𝑗′=1𝑘 𝑠𝑖𝑚 𝐴𝑗, 𝐴𝑗′
Articles
Utilisateurs
A1 A2 A3 A4
U1 -1,18 -0,53 -0,99 -0,58
U2 1,14 2,76 2,37 -1,19
U3 0,17 -0,64 -0,21 0,17
Calcul des
écarts avec la
baseline
+ complétion
par des zéros Calcul des coefs. de
corrélation entre
articles
Prédiction de
l’écart avec la
baseline
Mineure « Data Science » Frédéric Pennerath
Fusion des prédictions
Articles
Utilisateurs
A1 A2 A3 A4
U1 -1,18 -0,53 -0,99 -0,58
U2 1,14 2,76 2,37 -1,19
U3 0,17 -0,64 -0,21 0,17
Articles
Utilisateurs
A1 A2 A3 A4
U1 6,13 3,63 4,13 4,13
U2 4,29 1,79 2,29 2,29
U3 3,63 1,13 1,63 1,63
Articles
Utilisateurs
A1 A2 A3 A4
U1 4,95 3,09 3,13 3,55
U2 5,43 4,55 4,66 1,11
U3 3,80 0,48 1,4 1,79
Articles
Utilisateurs
A1 A2 A3 A4
U1 -0,05 -0,45
U2 0,55 1,66 0,11
U3 -0,20 0,48 -0,59
𝑠 = 𝑠𝑏 + 𝑠𝑓
𝜀 = 𝑠 − 𝑠
Prédiction de base 𝑠𝑏 Prédiction par filtrage collaboratif 𝑠𝑓Fusion baseline + écart
Estimation de l’erreur
Mineure « Data Science » Frédéric Pennerath
AMÉLIORATION PAR
ANALYSE SÉMANTIQUE LATENTE :
TECHNIQUES DE RÉDUCTION DE
DIMENSION
Mineure « Data Science » Frédéric Pennerath
Coclustering
Donnée : relation binaire entre deux familles d’objets et de sujets.
Problème de coclustering : regroupement simultané des objets et des sujets
• Deux objets sont similaires si ils ont une affinité pour les mêmes sujets.
• Deux sujets sont similaires s’ils ont une affinité pour les mêmes objets.
Applications :
• Analyse sémantique latente : objets : termes, sujets : documents.
• Système de recommandation : objets : produits, sujets : acheteurs.
sujet1 sujet2 sujet3 sujet4
objet1 4 5 0 1
objet2 3 2 4 3
objet3 2 1 5 4
Mineure « Data Science » Frédéric Pennerath
Problème : similarité entre 2 articles presque nulle (peu de notes communes)
malédiction de la dimension risque de mesurer du bruit (sur-apprentissage)
Solution : généraliser les goûts et les styles par l’analogie sémantique
Si René aime les films d’action et Rambo IV est un film d’action alors René aime Rambo IV
Projection des données dans un espace « sémantique » latent de dimension réduite
Calcul de 𝑠𝑖𝑚 𝐴𝑖 , 𝐴𝑗 = cos 𝐴𝑖 , 𝐴𝑗 dans cet espace
Analyse sémantique latente (LSA)
projection
Espace abonnés
ℝ|𝑓𝑖𝑙𝑚𝑠|Espace « sémantique »
latent ℝ𝑘 avec𝑘 ≪ min 𝑓𝑖𝑙𝑚𝑠 , 𝑎𝑏𝑜𝑛𝑛é𝑠
Espace films
ℝ|𝑎𝑏𝑜𝑛𝑛é𝑠|
𝑅𝑎𝑚𝑏𝑜 𝐼𝑉 = −3 𝐽𝑒𝑎𝑛 + 4 𝑅𝑒𝑛é + 4 𝑃𝑎𝑢𝑙
projection
𝑅𝑒𝑛é
= 4 𝑅𝑎𝑚𝑏𝑜 𝐼𝑉 + 5 𝑅𝑎𝑚𝑏𝑜 𝐼 − 3 𝑇𝑖𝑡𝑎𝑛𝑖𝑐𝑅𝑒𝑛é = 4 𝐴𝑐𝑡𝑖𝑜𝑛 − 3 𝐷𝑟𝑎𝑚𝑒
𝑅𝑎𝑚𝑏𝑜 𝐼𝑉 = 5 𝐴𝑐𝑡𝑖𝑜𝑛 − 2 𝐷𝑟𝑎𝑚𝑒
⇒ 𝑠𝑖𝑚 𝑅𝑒𝑛é , 𝑅𝑎𝑚𝑏𝑜 𝐼𝑉 ≃ 1
Vecteurs
lignes de
𝑅
Vecteurs
colonnes de
𝑅
Mineure « Data Science » Frédéric Pennerath
Théorème :
Toute matrice réelle 𝑀 de taille m x n peut se décomposer en un produit matriciel :
𝑀 = 𝑈 × Σ × 𝑉𝑇 où Σ =
𝜎1⋱ 0𝜎𝑟
0 0⋱
avec 𝜎1 ≥ ⋯ ≥ 𝜎𝑟 > 0
Où :
• r est le rang de 𝑀
• est de taille m x n diagonale semi-définie positive
• 𝑈 est de taille m x m orthogonale : 𝑈TU = Im.
• 𝑉 est de taille n x n orthogonale : 𝑉TV = In
Définition :
• Les scalaires 𝜎𝑖 sont les valeurs singulières.
• La 𝑖è𝑚𝑒 colonne de 𝑈 (resp. de 𝑉) est le vecteur singulier à gauche (resp. à droite) de 𝜎𝑖
Décomposition en valeurs singulières (SVD)
valeurs singulières
Mineure « Data Science » Frédéric Pennerath
Approximation SVD
Soit la norme matricielle 𝐴 2 = 𝑖,𝑗 𝑎𝑖,𝑗2 (norme de Frobenius).
Théorème :
La matrice 𝑀𝑘 de rang 𝑘 ≤ 𝑟 la plus proche (au sens de ∙ 2) d’une matrice 𝑀 de
dimension 𝑚 × 𝑛 s’obtient par décomposition SVD de 𝑀, en supprimant de Σ les 𝑟 − 𝑘 plus
petites valeurs singulières (complexité en Θ min 𝑚 × 𝑛2, 𝑛2 ×𝑚 ) :
minA 𝑡𝑞
𝑟𝑎𝑛𝑔 𝐴 =𝑘
𝐴 −𝑀 2 = 𝑀𝑘 −𝑀 2 =
𝑖=𝑘+1
𝑟
𝜎𝑖2
𝑎𝑣𝑒𝑐 𝑀𝑘 = 𝑈 × Σ𝑘 × 𝑉𝑇 𝑒𝑡 Σ𝑘 =
𝜎1⋱𝜎𝑘0
0 0
Mineure « Data Science » Frédéric Pennerath
Interprétation géométrique de LSA
𝑉𝑇 × 𝑅𝑇
(« PCA » sur les abonnés)
𝑈𝑇 × 𝑅(« PCA » sur les films)
projection
Espace abonnés
ℝ|𝑓𝑖𝑙𝑚𝑠|Espace « sémantique »
latent ℝ𝑘Espace films
ℝ|𝑎𝑏𝑜𝑛𝑛é𝑠|
projection
Décomposition SVD d’ordre k : 𝑅 ≃ 𝑈 × Σk × 𝑉𝑇
Alignements
Colonnes
de 𝑅𝑇Colonnes
de 𝑅
Abonnés : colonnes de Σk × 𝑈𝑇 Films : colonnes de Σk × 𝑉
𝑇
Mineure « Data Science » Frédéric Pennerath
Interprétation des dimensions latentes
1 2,637 Trailer Park Boys: Season 3
3 2,391 Lost: Season 1
5 2,383 Trailer Park Boys: Season 4
6 2,368 Veronica Mars: Season 1
8 2,341 Battlestar Galactica: Season 1
9 2,333 Arrested Development: Season 2
10 2,323 As Time Goes By: Series 9
... … ...
... … ...
10 -0,044 The Bogus Witch Project
9 -0,047 Underground Comedy Movie
8 -0,071 Rise of the Undead
7 -0,084 The Horror Within
6 -0,105 Vampire Assassins
5 -0,121 Absolution
4 -0,135 The Worst Horror Movie Ever Made
3 -0,155 Alone in a Haunted House
2 -0,159 Zodiac Killer
1 -0,220 Avia Vampire Hunter
Les dimensions de l’espace latent (pour k faible) ont un sens interprétable
Exemple de colonne de V × Σk exprimé dans l’espace abonnés
𝑉 𝑈
Transf.Trans.
Mineure « Data Science » Frédéric Pennerath
Systèmes de recommandation fondés LSA
Problème 1 : en pratique 𝑅 est creux. Comment adapter SVD ?
Solution :
Remplacer minU,V 𝑡𝑞𝑈∈𝑀𝑛,𝑘(ℝ)
𝑉∈𝑀𝑚,𝑘(ℝ)
𝑖,𝑗 𝑟𝑖𝑗 − 𝑈𝑖 𝑉𝑗𝑇 2 par min
U,V 𝑡𝑞𝑈∈𝑀𝑛,𝑘(ℝ)
𝑉∈𝑀𝑚,𝑘(ℝ)
𝑛𝑜𝑡𝑒 𝑟𝑖𝑗 𝑟𝑖𝑗 − 𝑈𝑖 𝑉𝑗𝑇 2
Résoudre par descente de gradient (variables : coefs. de 𝑈 et 𝑉)
Problème 2 : les coefs. de 𝑈 et 𝑉 sont nombreux par rapport au nombre de notes disponibles
Solution :
Inclure un terme de régularisation L2 :
minU,V 𝑡𝑞𝑈∈𝑀𝑛,𝑘(ℝ)
𝑉∈𝑀𝑚,𝑘(ℝ)
𝑛𝑜𝑡𝑒 𝑟𝑖𝑗
𝑟𝑖𝑗 − 𝑈𝑖 𝑉𝑗𝑇 2 + 𝜆
𝑖,𝑗
𝑢𝑖,𝑗2 +
𝑖,𝑗
𝑣𝑖,𝑗2
Résoudre par descente de gradient (variables : coefs. de 𝑈 et 𝑉)