Systèmes de recommandation

Julien Romero

CSC 4538 Systèmes de recommandation 1

Limitations des moteurs de recherche
● Il faut savoir ce que l’on cherche
○ Comment découvrir de nouveau films, livres, produits ?
● Les résultats ne sont pas personnalisés
○ Le résultat “album de musique” renvoie la même chose pour quelqu’un qui écoute du métal, du
classique, ou du rap
● Les moteurs de recherches sont statiques
○ Ne prend pas en compte ce qui est actuellement populaire

CSC 4538 Systèmes de recommandation 2

Systèmes de recommandation
● Un système de recommandation est un algorithme capable de suggérer un objet
(page web, film, livre, musique, personne) pour un utilisateur et un context donné
● Plus formellement, soit U l'ensemble des utilisateurs et I l’ensemble des objets
(items), un système de recommandation prédit un score R d’utilité pour chaque
couple d’utilisateur et d’objets. Ce score peut être un entier entre 0 et 1, ou une
note sur 5.

CSC 4538 Systèmes de recommandation 3

Exemples

CSC 4538 Systèmes de recommandation 4

La personnalisation de la recommandation
● Recommandations non personnalisées
○ Souvent choisies pour plaire à une catégorie de personnes
○ Articles dans un journal
○ Vidéo Youtube “10 livres à lire pour devenir riche”
○ Top 10
○ Plus récents
● Recommandations personnalisées
○ Choisies pour un individu donné
○ Amazon, Netflix, Youtube, …
○ Ce qui nous intéresse aujourd’hui !

CSC 4538 Systèmes de recommandation 5

D’où viennent les données ?
● Pour entraîner et tester un système de recommandation, il nous faut des données
○ Ce sont des valeurs connues de notre fonction d’utilité
● Données explicites
○ On peut demander à l’utilisateur de noter (de 1 à 5, like/dislike)
○ Ne marche pas trop en pratique
● Données implicites
○ On va capturer des signaux venant des utilisateurs
○ Signaux forts : Achat d’un objet, visionnage d’un film, page web visitée
○ Signaux faibles : click sur un produit, temps passé sur une vidéo, nombre d’interactions par minute,
…

CSC 4538 Systèmes de recommandation 6

Matrice d’utilité
● Matrice contenant les valeurs connues de la fonction d’utilité
○ Matrice très creuse en général

Le seigneur Good bye

Harry Potter La chute OSS 117 Les visiteurs
des anneaux Lenin

Marie 5 ? 3 2 3 ?

Louise 4 5 4 1 2 2

Jean 1 ? ? ? ? ?

Maurice ? 3 5 4 2 ?

CSC 4538 Systèmes de recommandation 7

Recommandation basée sur le contenu

CSC 4538 Systèmes de recommandation 8

Création d’un profil d’objet et d’utilisateur
● On peut créer un vecteur de caractéristiques pour chaque objet
○ Film : Genre, réalisateur, durée, date de production, langue, titre
○ Livre : auteur, genre, nombre de pages, contenu (avec TF-IDF)
○ Offre d’emploi : type de contrat, compétences, expérience requise, formation
● Idem pour l’utilisateur
○ Moyenne (pondérée) des objets avec lesquels il a interagit
○ Sexe, age, formation, compétences, genre préféré, …

CSC 4538 Systèmes de recommandation 9

Recommander un nouvel objet
● Recommander l’objet le plus proche des objets connues de l’utilisateur
○ K plus proches voisins
○ Heuristiques/approximations quand trop d’objets
○ On peut utiliser la similarité cosinus
● Entraîner un modèle de régression/classification
○ Approche classique de machine learning

CSC 4538 Systèmes de recommandation 10

Avantages de l’approche par contenu
● Pas besoin d’avoir accès aux données des autres utilisateurs
● Marche même si l’utilisateur a des goûts particuliers
○ (Avec les bonnes caractéristiques)
● Marche avec les objets nouveaux et non populaires
● Facile de produire des explications sur la recommandation

CSC 4538 Systèmes de recommandation 11

Inconvénients de l’approche par contenu
● Il faut créer soi-même le vecteur de caractéristique
○ Souvent difficile
● Surspécialisation
○ Pas de recommandation en dehors de ce qui est connu
○ Difficile de modéliser des intérêts multiples
○ N’exploite pas le jugement des autres utilisateurs
● Ne fonctionne pas bien avec les nouveaux utilisateurs sans interactions
○ Le problème du “Cold-start”

CSC 4538 Systèmes de recommandation 12

Le problème du “cold-start”
● Comment traiter le cas particulier du “démarrage” du système ?
○ À la création d’un objet ou utilisateur, nous n’avons pas d’interaction le concernant
● La recommandation suivra souvent une stratégie simple et générique
○ Top 10, Tendance en ce moment, …
● Problème récurrent

CSC 4538 Systèmes de recommandation 13

 Le filtrage collaboratif

CSC 4538 Systèmes de recommandation 14

Le filtrage collaboratif
● Idée principale : On base la recommandation d’un objet pour un utilisateur sur
l’ensemble des interactions entre les objets et les utilisateurs.
● Le vecteur de caractéristique va être obtenu à partir de la matrice d’utilité
○ Les colonnes nous donnent les vecteurs des objets
○ Les lignes nous donnent les vecteurs des utilisateurs
● Deux variantes :
○ Filtrage collaboratif basé sur les utilisateurs
○ Filtrage collaboratif basé sur les objets

CSC 4538 Systèmes de recommandation 15

Filtrage collaboratif basé sur les utilisateurs
● Pour un u utilisateur donné :
○ Trouver les N plus proches utilisateurs (selon la matrice d’utilité)
○ Estimer le vecteur de u à partir des N autres utilisateurs
● Mesures de similarité
○ Similarité de Jaccard
■ Mais en ignorant les valeurs des notes
○ Similarité cosinus
■ Mais en traitant les valeurs manquantes comme négatives
○ Coefficient de corrélation de Pearson (S(xy) est l’ensemble des interactions communes)

CSC 4538 Systèmes de recommandation 16

Prédire le vecteur de caractéristique
● Si r(x) est le vecteur de caractéristique d’un utilisateur x, et N est le set des plus
proches utilisateurs ayant prédit un objet i, alors on pourrait définir plusieurs
métriques pour construire le score final

CSC 4538 Systèmes de recommandation 17

Filtrage collaboratif basé sur les objets
On peut appliquer les mêmes principes sur les objets.

CSC 4538 Systèmes de recommandation 18

Exemple - Basé sur l’utilisateur

Le
Harry seigneur Good bye Les
La chute OSS 117 Similarité
Potter des Lenin visiteurs
anneaux

Marie 5 ? 3 2 3 ?

Louise 4 4 4 1 3 2

Jean 1 ? ? 5 ? ?

Maurice ? 3 5 4 2 ?

CSC 4538 Systèmes de recommandation 19

Exemple - Basé sur l’utilisateur - Calcul de la similarité

Le
Harry seigneur Good bye Les
La chute OSS 117 Similarité
Potter des Lenin visiteurs
anneaux

Marie 5 ? 3 2 3 ? 1

Louise 4 4 4 1 3 2 0.75

Jean 1 ? ? 5 ? ? -0.99

Maurice ? 3 5 4 2 ? -0.22

CSC 4538 Systèmes de recommandation 20

Exemple - Basé sur l’utilisateur - Sélection des K (=2) plus proches

Le
Harry seigneur Good bye Les
La chute OSS 117 Similarité
Potter des Lenin visiteurs
anneaux

Marie 5 ? 3 2 3 ? 1

Louise 4 4 4 1 3 2 0.75

Jean 1 ? ? 5 ? ? -0.99

Maurice ? 3 5 4 2 ? -0.22

CSC 4538 Systèmes de recommandation 21

Exemple - Basé sur l’utilisateur - Moyenne pondérée

Le
Harry seigneur Good bye Les
La chute OSS 117 Similarité
Potter des Lenin visiteurs
anneaux

Marie 5 4.41 3 2 3 ? 1

Louise 4 4 4 1 3 2 0.75

Jean 1 ? ? 5 ? ? -0.99

Maurice ? 3 5 4 2 ? -0.22

CSC 4538 Systèmes de recommandation 22

Exemple - Basé sur l’objet
Le
Harry seigneur Good bye Les
La chute OSS 117
Potter des Lenin visiteurs
anneaux

Marie 5 ? 3 2 3 ?

Louise 4 4 4 1 3 2

Jean 1 ? ? 5 ? ?

Maurice ? 3 5 4 2 ?

Similarité

CSC 4538 Systèmes de recommandation 23

Exemple - Basé sur l’objet - Calcul de la similarité
Le
Harry seigneur Good bye Les
La chute OSS 117
Potter des Lenin visiteurs
anneaux

Marie 5 ? 3 2 3 ?

Louise 4 4 4 1 2 2

Jean 1 ? ? ? ? ?

Maurice ? 3 5 4 2 ?

Similarité 1.0 1.0 -0.71 -0.95 0.95 -1

CSC 4538 Systèmes de recommandation 24

Exemple - Basé sur l’objet - Sélection des K (=2) plus proches
Le
Harry seigneur Good bye Les
La chute OSS 117
Potter des Lenin visiteurs
anneaux

Marie 5 ? 3 2 3 ?

Louise 4 4 4 1 2 2

Jean 1 ? ? ? ? ?

Maurice ? 3 5 4 2 ?

Similarité 1.0 1.0 -0.71 -0.95 0.95 0

CSC 4538 Systèmes de recommandation 25

Exemple - Basé sur l’objet - Moyenne pondérée
Le
Harry seigneur Good bye Les
La chute OSS 117
Potter des Lenin visiteurs
anneaux

Marie 5 4.03 3 2 3 ?

Louise 4 4 4 1 2 2

Jean 1 ? ? ? ? ?

Maurice ? 3 5 4 2 ?

Similarité 1.0 1.0 -0.71 -0.95 0.95 0

CSC 4538 Systèmes de recommandation 26

Filtrage collaboratif basé sur les objets ou les utilisateurs ?
● En général, le filtrage collaboratif basé sur les objets donne de meilleurs résultats
○ Pourquoi ? Le objets sont généralement plus simples
○ Les utilisateurs ont de nombreux intérêts, qui changent avec le temps

CSC 4538 Systèmes de recommandation 27

Avantages et inconvénients du filtrage collaboratif
+ Marche avec tous les types d’objets
+ Pas besoin de passer beaucoup de temps à créer des caractéristiques
- Cold start
- Il faut beaucoup d’utilisateurs et un minimum d’interaction pour chaque utilisateur et objet
- Difficile pour les nouveaux objets ou les objets qui sortent de l’ordinaire
- Matrice d’utilité sparse
- Difficile de trouver des utilisateurs ayant noté les mêmes objets
- Biais de popularité
- Tendance à recommander les objets que tout le monde aime

CSC 4538 Systèmes de recommandation 28

Méthodes hybrides
● Souvent, il faut implémenter plusieurs modèles différent et combiner les résultats
● On prendra l’approche basée sur le contenu pour les utilisateurs et objets avec peu
d’interaction
● On bascule vers du filtrage collaboratif par la suite

CSC 4538 Systèmes de recommandation 29

 Évaluation

CSC 4538 Systèmes de recommandation 30

Évaluer un système de recommandation
● Comme pour toutes les tâches de machine learning, on divise notre dataset en un
jeu d'entraînement et un jeu de test (et un jeu de validation si possible)
● On a ensuite le choix entre plusieurs métriques
○ Racine de l'erreur quadratique moyenne (Root Mean Square Error)
■ Utile quand on a des scores

CSC 4538 Systèmes de recommandation 31

Évaluer un système de recommandation
● Comme pour toutes les tâches de machine learning, on divise notre dataset en un
jeu d'entraînement et un jeu de test (et un jeu de validation si possible)
● On a ensuite le choix entre plusieurs métriques
○ Racine de l'erreur quadratique moyenne (Root Mean Square Error)
■ Utile quand on a des scores
○ Métriques basées sur le rang
■ Pour un utilisateur donné, on prédit le score pour tous les objets et on les classe
■ On associe à chaque objet s’il est pertinent ou pas
■ On calcule des métriques basées sur le rang des objets pertinents

CSC 4538 Systèmes de recommandation 32

Métrique sur les rangs
● Precision@K : Pourcentage d’objets pertinents
Pertinent ?
dans les K premiers
Objet 1 Oui ○ Precision@3 = 1 / 3
Objet 2 Non ● Recall@K : Nombre d’objets pertinents dans les K
premiers, divisé par le nombre d’objets pertinents
Objet 3 Non
○ Recall@3 = 1 / 2
Objet 4 Oui ● Mean Reciprocal Rank (MRR) : Moyenne des
Objet 5 Non inverses des rangs du premier objet pertinent
○ MRR = (1/1 + RR autres utilisateurs) / (# utilisateurs)
Objet 6 Non

CSC 4538 Systèmes de recommandation 33

Métrique sur les rangs
● Average Precision (AP) @ K :
Pertinent ?
○ AP@3 = 1/2 * (1 * 1 + 1/2*0 + 1/3*0) = 1/2
Objet 1 Oui ○ N = Nombre d’objets pertinents pour u
○ rel(k) = pertinence de l’objet au rang k
Objet 2 Non

Objet 3 Non

Objet 4 Oui ● Mean Average Precision (MAP) @ K : Moyenne

des AP@K sur tous les utilisateurs
Objet 5 Non

Objet 6 Non

CSC 4538 Systèmes de recommandation 34

Métrique sur les rangs
● Discounted Cumulative Gain (DCG) @ K :
Pertinent ?
○ DCG@3 = 1 / log(2) = 1
Objet 1 Oui

Objet 2 Non

Objet 3 Non

Objet 4 Oui ● Normalized DCG (NDCG) @ K :

○ NDCG@K = 1 / (1/log2(2) + 1/log2(3)) = 0.61
Objet 5 Non ○ IDCG@K = Meilleur DCG@K possible
Objet 6 Non

CSC 4538 Systèmes de recommandation 35

Filtrage collaboratif basé sur un modèle

CSC 4538 Systèmes de recommandation 36

Filtrage collaboratif basé sur un modèle
● Jusqu’à présent, nous avons utilisé la matrice d’utilité brute et une approche
statistique
○ Communément appelé “basé sur la mémoire” (memory-based)
● Cependant, nous avons une matrice très creuse à manipuler
● L’autre approche consiste à compresser la matrice d’utilité pour la rendre plus
dense
○ C’est l’approche basée sur un modèle (model-based)

CSC 4538 Systèmes de recommandation 37

Factorisation de matrice
● La factorisation de matrice consiste à décomposer une matrice en une
multiplication de plusieurs matrices (plus petites)
○ Dans notre cas, nous allons avoir au moins une matrice correspondant aux utilisateurs, et une
matrice correspondant aux objets
○ Si nous avons une matrice de taille U (nombre d’utilisateurs) par I (nombre d’objet), nous voulons
factoriser la matrice d’utilité de taille U*I en deux matrices de taille U*k et I*k (avec k petit)
○ Les vecteurs associés aux utilisateurs et objets sont appelés des vecteurs latents
○ Pour notre matrice d’utilité M, nous cherchons deux matrices telles que

CSC 4538 Systèmes de recommandation 38

Exemple I

2.5

2 -1 4
U

CSC 4538 Systèmes de recommandation 39

Prédire la valeur d’une interaction
● Si p(x) est le vecteur latent d’un utilisateur et q(i) le vecteur latent d’un objet, la
valeur de l’interaction sera donnée par :

CSC 4538 Systèmes de recommandation 40

Singular Value Decomposition (SVD)
● SVD est un algorithme qui factorise une matrice M de taille m*n en trois matrices
U matrice unitaire de taille m*k, Σ matrice diagonale de taille k*l et V matrice
unitaire de taille n*l telles que :

● Pour obtenir les vecteurs latents des utilisateurs et objets, on posera

CSC 4538 Systèmes de recommandation 41

Propriété de SVD
● SVD nous donne l’erreur de reconstruction minimale

● Cependant, notre matrice est creuse ! Il faut donc résoudre le problème sur les
interactions connues (jeu d’entrainement):

● On peut rajouter de la régularisation (conseillé)

CSC 4538 Systèmes de recommandation 42

Résolution
● Problème résolu avec une descente de gradient (stochastique)

CSC 4538 Systèmes de recommandation 43

Autres algorithmes
● Analyse en composantes principales, ACP (Principal component analysis, PCA)
● Alternating Least Square (ALS)

CSC 4538 Systèmes de recommandation 44

Pour aller plus loin…
● Il est possible d’inclure dans la modélisation le score moyen et les déviations de
l’utilisateur ou de l’objet
○ Certains utilisateurs sont plus gentils, d’autres plus sévères
○ Certains objets sont globalement meilleurs ou pires

Biais de l’objet
Score moyen Biais de l’utilisateur Interactions

● Ajouter un aspect temporel (sur les biais par exemple)

CSC 4538 Systèmes de recommandation 45

 En route pour le TP

CSC 4538 Systèmes de recommandation 46