View
5
Download
0
Category
Preview:
Citation preview
Apprentissage et factorisation matriciellepour la recommendation
Julien Delporte & Stéphane Canustephane.canu@litislab.eu
SFC’2014, 11 septembre 2014, Rabat
Recommendation Recommandation & liens
Plan de la présentation
1 Sélection de modèle pour la factorisation de matriceLe problème de la recommandationFactorisation pour la recommandationSelection de modèle
2 Recommandation avec préférences et liensLe problème TuentiNotre modèleOptimisation alternéeRésultats expérimentaux
2 / 35
Recommendation Recommandation & liens
La recommandation de tous les jours
3 / 35
Recommendation Recommandation & liens
Recommander musique, films, amis, lieux. . .
4 / 35
Recommendation Recommandation & liens
La recommandation comme un problème decomplétion de matrice
dd
1
1
1
1 1
1
1
1
1
1
1
Y
V
U
F = <U ; V >
? 1
1
〈Ui ,Vj〉 une mesure d’appétence de l’utilisateur i pour le produit j
5 / 35
Recommendation Recommandation & liens
Formalisation du problème
Modèle
Y = F + Robservation = information + bruit
avec F régulière et R une matrice de bruit.
Problème : construire F un estimateur de F
minF
L(Y , F )︸ ︷︷ ︸attache aux données
+ λ Ω(F )︸ ︷︷ ︸pénalisation
pour un λ bien choisiavec F = UV une factorisation de faible rang
6 / 35
Recommendation Recommandation & liens
Formalisation du problème
Modèle
Y = F + Robservation = information + bruit
avec F régulière et R une matrice de bruit.
Problème : construire F un estimateur de F
minF
L(Y , F )︸ ︷︷ ︸attache aux données
+ λ Ω(F )︸ ︷︷ ︸pénalisation
pour un λ bien choisiavec F = UV une factorisation de faible rang
6 / 35
Recommendation Recommandation & liens
Comment trouver U et V ?
Problème de reconstruction de la matrice Y
minF
L(Y , F ) := ‖Y − F‖2Favec rang(F ) = d
Eckart & Young 1936
Solution : faire une analyse en composante principales (ACP)
Yn = normalise(Y ) à adapterC = Y ′n ∗ Yn OUT OF MEMORYd = 200 et pas 3U = eig(C,d) creuse → pleineF = UV il faut reconstruire V
7 / 35
Recommendation Recommandation & liens
Comment trouver U et V ?
Problème de reconstruction de la matrice Y
minF
L(Y , F ) := ‖Y − F‖2Favec rang(F ) = d
Eckart & Young 1936
Solution : faire une analyse en composante principales (ACP)
Yn = normalise(Y ) à adapterC = Y ′n ∗ Yn OUT OF MEMORYd = 200 et pas 3U = eig(C,d) creuse → pleineF = UV il faut reconstruire V
7 / 35
Comment faire une ACP (pour trouver U et V ) ?Solution : décomposition en valeurs singulières (SVD)
F = UV (= U ′ΣV ′)
Méthode de résolution « exacte » sur matrices creusessvds est trop lentalgorithme : processus de Lanczos
Bidiagonalisation Y = WBZdiagonalisation de B (rotations de givens GVL 8.6.1)
logiciel : PROPACK a
a. http ://soi.stanford.edu/ rmunk/PROPACK/
>> size(Y) ans = 480189 17770>> d = 200;>> tic>> [U,D,V] = lansvd(Y,d,’L’);>> toc Elapsed time is 1030.800702 seconds.
Recommendation Recommandation & liens
Un succès de la factorisation
Netflix Challenge (2007-2009)Recommandation de filmsMoteur maison : CineMatchAméliorer les performances de 10%critère : erreur quadratique
Les données450 000 spectateurs17 000 films100 millons d’évaluations (de 1 à 5)taux de remplissage : 1,3 %test sur les 3 millions les plus récents48 000 téléchargements des donées
9 / 35
Recommendation Recommandation & liens
baseline : CineMatchfactorisation : SVD régularisée à d facteurs Ui ,Vj ∈ IRd
minU,V
∑i,j
(Yij − U>i Vj )
2 + λ(‖Ui‖2 + ‖Vi‖2)
normalisation : moyenne globale µ, pour l’utilisateur i bi
minU,V
∑i,j
(Yij − U>i Vj − µ− bi − pj )
2 + λ(‖Ui‖2 + ‖Vj‖2)
poids : implicit feedback cij : niveau de confiance
minU,V
∑i,j
cij (Yij − U>i Vj − µ− bi − pj )
2 + λ(‖Ui‖2 + ‖Vj‖2)
temps
minU,V
∑i,j
(Yij − Ui (t)>Vj )2 + λ(‖Ui‖2 + ‖Vj‖2)
Mélanges de modèles10 / 35
Recommendation Recommandation & liens
Les résultats sur Netflix
erreur initiale : 0.9514
factorisation - 4 %nombres de facteurs - .5 %améliorations - 2.5 %
normalisationpoidstemps
bagging : - 3 % = 0.8563mélange 100 méthodes
Koren, Y., Bell, R.M., Volinsky, C. : Matrix factorization techniques for recommender systems. IEEE Computer 42(8), 30–37 (2009)
11 / 35
Recommendation Recommandation & liens
Les leçons de Netflix
trop d’efforts spécifiques pour être généralisée
factorisation is the solution
poids : implicit feedback
prendre en compte les spécificités (ici l’effet temps)
une algorithmique de type gradient stochastiqueflexiblequi passe à l’échelle
12 / 35
Recommendation Recommandation & liens
Plan de la présentation
1 Sélection de modèle pour la factorisation de matriceLe problème de la recommandationFactorisation pour la recommandationSelection de modèle
2 Recommandation avec préférences et liensLe problème TuentiNotre modèleOptimisation alternéeRésultats expérimentaux
13 / 35
Recommendation Recommandation & liens
Sélection de modèle pour la factorisation
ObjectifDéterminer d le nombre de variables latentes
dd
1
1
1
1 1
1
1
1
1
1
1
Y
V
U
F = <U ; V >
? 1
1
14 / 35
Recommendation Recommandation & liens
Le choix de d c’est le choix de λ
ModèleY = F + R Rij ∼ N (0, s2)
Estimateur : F
F = argminM
‖Y −M‖2 + pen(λ,Y ,M)
Pour certaines pen⇒ Solution : SVD + shrinkage F = fλ(Y )
Y = UΣV> et F = fλ(Y ) =
p∑k=1
f (k)λ (σk )U•kV>•k
Exemple : f (k)λ (σk ) = max(0, σk − λ) (soft shrinkage)
15 / 35
Recommendation Recommandation & liens
Le Critère de choix de λ
un modèle : Y = F + R Rij ∼ N (0, s2) i.i.d.une famille d’estimateurs : F = fλ(Y )
Cout d’un estimateur : erreur de prédiction
C(Y , λ) = ‖F − fλ(Y )‖2 =∑
i∑
j (Fij − fλ(Y )ij)2
Oracle : λ? = argminλ‖F − fλ(Y )‖2
Stein Unbiased Risk Estimator (Stein, 1977, Candès, 2012)
δ0(Y , λ) = ‖Y − fλ(Y )‖2 + (2divY(fλ(Y )
)− np)s2
→ Si R est i.i.d. Gaussien, Alors, δ0(Y , λ) est un estimateursans biais de ‖F − fλ(Y )‖2 (SURE)
λ = argminλ
δ0(Y , λ)
16 / 35
Recommendation Recommandation & liens
SURE
minλδ0(Y , λ) = ‖Y − fλ(Y )‖2 + (2divY
(fλ(Y )
)− np)s2
‖Y − fλ(Y )‖2 l’erreur empiriques2 un estimateur sans biais indépendant de s2
divY(fλ(Y )
)le nombre de degrés de liberté du modèle
n nombre le lignes et p nombre de colonnes
Expression de la divergence
divY(f (Y )
)=
p∑i=1
(f ′i (σi) + (n − p)
fi(σi)
σi
)+ 2
p∑i=1
p∑j=1j 6=i
σi fi(σi)
σ2i − σ2
j
17 / 35
Recommendation Recommandation & liens
Notre point de départ
minλδ0(Y , λ) = ‖Y − fλ(Y )‖2 + (2divY
(fλ(Y )
)− np)s2
avec
divY(f (Y )
)=
p∑i=1
(f ′i (σi) + (n − p)
fi(σi)
σi
)+ 2
p∑i=1
p∑j=1j 6=i
σi fi(σi)
σ2i − σ2
j
Limitations pour le passage à l’échellea priori sur les données limité : utiliser d’autres fonctions fλ.div non calculable en grandes dimensions : estimer div .variance s2 supposée connue : proposer une estimation.
18 / 35
Recommendation Recommandation & liens
Modification de la fonction de seuillage
F = fλ(Y ) =d∑
k=1
f (k)λ (σk )U•kV>•k
f (k)λ (σk ) = max(0, σk − λ)
f (k)λ (σk ) = MCP
f (k)λ (σk ) = SCAD
-5 0 50
0.5
1
1.5
2
2.5
3
3.5
4
4.5
5SoftMcpScadAdalasso
0 1 2 3 40
0.5
1
1.5
2
2.5
3
3.5
4SoftMcpScadAdalasso
fonctions de pénalité (gauche) et fonctions de seuillage (droite)19 / 35
Recommendation Recommandation & liens
Modification de la fonction de seuillage
10-1 100
101
SoftMcpScadAda
Ris
que
estim
é
λ
Estimation du risque en fonction du paramètre λ
20 / 35
Recommendation Recommandation & liens
Estimation de la divergence
Problème
divY(f (Y )
)=
p∑i=1
(f ′i (σi) + (n − p)
fi(σi)
σi
)+ 2
p∑i=1
p∑j=1j 6=i
σi fi(σi)
σ2i − σ2
j
Solution proposéeCalculer les k premières valeurs singulières.Estimer le reste du spectre.
21 / 35
Recommendation Recommandation & liens
Estimation de la divergence
Théorème
Soit X ∈ L(p,n) une matrice aléatoire centrée. Les valeurspropres λi de la matrice 1
n X>X suivent (si on les considèrecomme variables aléatoires) une loi de Marchenko-Pastur deparamètre c > 0 dont la fonction de densité de probabilité vaut :
Pc(x) =
12πxc
√(x − a)(b − x) si a ≤ x ≤ b,
0 sinon.
où a = (1−√
c)2 et b = (1 +√
c)2.
22 / 35
Recommendation Recommandation & liens
Estimation de la divergence
5 10 15 20 25 30 350
5
10x104 snr = 0,1
dive
rgen
ceréellemarchenkolinéaire
λ
5 10 15 20 25 30 350
5
10x104 snr = 2
dive
rgen
ce
réellemarchenkolinéaire
λ
Comparaison d’estimations de divergence
23 / 35
Recommendation Recommandation & liens
Le cas corrélé (avec D. Fourdrinier)
Y = F + R R ∼ N (0,Σ)
généralisable au distributions à densité à symétrie elliptiquesSi R admet une densité, elle est de la forme
x 7→ |Σ|−n/2 g(tr(xΣ−1x t )
),
Cout invariant
‖F − F‖2Σ−1 = tr(F − F )Σ1(F − F )
δinv0 = c ‖Y − fλ(Y )‖2S−1 + 2 divY fλ(Y )− np
est un estimateur sans biais du cout invariant au sens de IE?.S un estimateur de Σc = n − k − p − 1
24 / 35
Recommendation Recommandation & liens
Conclusion
la factorisation ça marche
c’est souple d’utilisation
Encore quelques effort pour bien faire de la sélection demodèle automatique
25 / 35
Recommendation Recommandation & liens
Plan de la présentation
1 Sélection de modèle pour la factorisation de matriceLe problème de la recommandationFactorisation pour la recommandation
Factorisation et décomposition en valeurs singulièresFactorisation et Netflix
Selection de modèleLa sélection de modèle pour la factorisationPassage à l’échelle
2 Recommandation avec préférences et liensLe problème TuentiNotre modèleOptimisation alternéeRésultats expérimentaux
26 / 35
Recommendation Recommandation & liens
Le problème Tuenti
Taille des données13M d’utilisateurs100K endroits200M connexionssociales
Parcimonie4 lieux par utilisateur20 amis par utilisateur
user 1user 2user 3user 4
...
...
...
...
...
...
...
......
1
0
0 1011
0 10 1
0
27 / 35
Recommendation Recommandation & liens
Objectif
dd
1
1
1
1 1
1
1
1
1
1
1
Y
V
U
F = <U ; V >
? 1
1
28 / 35
Recommendation Recommandation & liens
Objectif
dd
1
1
1
1 1
1
1
1
1
1
1
Y
V
U
? 1
1 A
28 / 35
Recommendation Recommandation & liens
Méthodes existantes
Modification de la fonction objectif
minU,VL1(Y ,UV ) + µL2(A,UU>) + λΩ(U,V ) Yang et al. (2011)
minU,VL(Y ,UV ) + µ
n∑i=1
‖Ui −1|Fi |
∑k∈Fi
Uk‖2F + λΩ(U,V ) Ma et al. (2011)
Fi l’ensemble des amis de iAii ′ = 1 si i ′ ∈ Fi
Modification de la fonction de décision
minU,V
∑(i,j)∈Y
cij(UiVj +
∑k∈Fi
AikUkVj
|Fi |− Yij
)2+ ΩU,V ,A Ma et al. (2009)
29 / 35
Recommendation Recommandation & liens
Apprentissage de l’influence
Fonction de décision
Yij = UiVj +∑k∈Fi
AikUkVj
|Fi |Ma et al. (2009) (1)
Fonction objectif
minU,V ,A
∑(i,j)∈Y
cij(UiVj +
∑k∈Fi
AikUkVj
|Fi |− Yij
)2+ ΩU,V ,A (2)
cij un poids pour pénaliser les 1 plus que les 0.ΩU,V ,A = λ1‖U‖2Fro + λ2‖V‖2Fro + λ3‖A‖2Fro
ContributionApprendre les influences des amis
30 / 35
Recommendation Recommandation & liens
Algorithme
Moindres carrés alternés – SE CoFiInput : Y and Fintialize U,V and ARepeat
For each user i ∈ Uupdate Ui
For each item j ∈ Vupdate Vj
For each user i ∈ UFor each user k ∈ Fi
update Aik
Until convergence
31 / 35
Recommendation Recommandation & liens
Résultats sur Tuenti et Epinions
0 5 10 15 200.65
0.7
0.75
0.8
0.85
0.9
0.95
iMFSE CoFiLLARSRTrustaverage
0 5 10 15 20
0.025
0.03
0.035
0.04
0.045
0.05
iMFSECoFiLLARSRTrustAverage
Nombre de facteurs d
MA
P
Nombre de facteurs d
RA
NK
0 10 20 30 40 50 600.54
0.56
0.58
0.6
0.62
0.64
0.66
0.68
Nombre de facteurs d
MA
P
0 10 20 30 40 50 600.21
0.22
0.23
0.24
0.25
0.26
0.27
0.28
0.29
0.3
Nombre de facteurs d
RA
NK
SECoFiTrustLLARSRiMFaverage
SECoFiTrustLLARSRiMFaverage
Tuenti : 13 Mutilisateurs et 100 klieux (20 amis)
Epinion : 50 kutilisateurs et 100 karticles (5 amis)
tests réalisés sur unserveur 24 cores avec100Go RAM
32 / 35
Recommendation Recommandation & liens
Retour sur les influences des amis
−0.2 0 0.2 0.4 0.6 0.8 1 1.20
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
frequency of the histogram
−0.2 0 0.2 0.4 0.6 0.8 1 1.20
5
10
15
20
25
30
35
Distribution
values of alpha
ἀ
Le principe d’affinité (homophily) est vérifié, pas d’influence négative33 / 35
Recommendation Recommandation & liens
Conclusion
Bilanprise en compte de la matrice ET du graphegestion d’un gros volume de donnéesamélioration de la recommandationmesure de l’influence
Perspectivesutiliser la flexibilité de l’approcheprendre en compte les données contextuelles
GPS, types de lieux, . . .
vers la recommandation d’amis (apprendre tous les α)
34 / 35
Recommendation Recommandation & liens
Questions ?
dd
1
1
1
1 1
1
1
1
1
1
1
Y
V
U
F = <U ; V >
? 1
1
Factorisation Matricielle, Application à la RecommandationPersonnalisée de Préférences
Thèse de Julien DELPORTE, février 2014
35 / 35
Recommended