Apprentissage et factorisation matricielle pour la...

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