MOTEURS DE RECOMMANDATION
(Recommender systems)
1
INTRODUCTION
Introduction
Objectif : proposer aux utilisateurs des choix pertinents.
Applications nombreuses:
Principe intuitif : utilisation des caractéristiques de l’utilisateur et/ou des produits pour proposer des choix parmi un catalogue de choix possibles.
EXEMPLE
Exemple
Quelle méthode utiliser pour proposer à des étudiants M2 info des cours qui les intéressent?
Différents systèmes, tous pertinents mais pas forcéments dans les mêmes contextes !
Fu 98333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333
DEUX MODÈLES PRINCIPAUX
Source : paxcel.net
ALGORITHMES BASÉS SUR LE CONTENU
PRINCIPE
Donnée: Profil-utilisateur, i.e. contenus qu’il a noté (*). On évalue la note des autres contenus grâce à leur similarité aux contenus connus.
Camille | 4 | 5 | ? | 4 |
Mehdi | 1 | ? | 5 | ? |
Julien | 5 | ? | ? | 2 |
0.98
0.75
-0.3
MODÉLISATION DES CONTENUS
Modélisation des contenus
On cherche à caractériser un contenu. C’est du feature engineering!
De manière générale, un peu la même problématique que façonner une “bonne” fonction de distance!
EXEMPLE
Exemple
Un étudiant aime le cours de Fouille (normal!).
Quel autre cours lui recommander ?
FDD, comparé aux autres, a de fortes valeurs TF-IDF pour les mots : données, fouille, apprentissage, statistiques, et de faibles valeurs TF-IDF pour: algorithme, systèmes, architecture.
On mesure la similarité entre le TF-IDF du cours "Fouille" avec celui de chacun des autres cours.
On propose à l’étudiant des cours similaires, comme "Intelligence Artificielle", qui a un profil de contenu similaire.
CALCUL DE LA SIMILARITÉ
Calcul de la similarité
(Données fictives)
Par exemple, on peut mesurer une distance entre chaque couple de cours, e.g. distance euclidienne basée sur le TF-IDF.
On peut calculer d’autres similarités, que nous allons voir maintenant.
TF-IDF | algo | système | stats | données |
Fouille | 0.1 | 0.05 | 3.5 | 3 |
I.A. | 0.1 | 1.2 | 2 | 2 |
Systèmes | 0.05 | 4 | 0 | 1 |
SIMILARITE “COSINUS”
Si X et Y sont deux vecteurs (TF-IDF ou autre, tout feature vector), leur similarité cosinus est :
Où:
SIMILARITÉ COSINUS - SUITE
Similarité "cosinus", suite
Au tableau:
SIMILARITÉ DE DICE-SORENSEN
Similarité de Dice-Sorensen
Si A et B sont deux ensembles de mots-clés, la similarité de Dice entre eux est :
Exemple: ici,
Source : podcastscience.fm
MÉTHODE 0
Où:
MÉTHODE 0
Où:
Problème: Complexité
MÉTHODE 1
On veut créer un “profil utilisateur” sous forme de feature vector [pourquoi ??].
Nos données: il a "liké" quatre documents A, B, C et D. Faisons la moyenne de ce qu’il aime:
On obtient un vecteur P de ses goûts moyens.
Ce vecteur P est celui qui est comparé aux nouveaux contenus: les plus proches sont proposés (recommandés) à l’utilisateur.
MÉTHODE 1
On veut créer un “profil utilisateur” sous forme de feature vector [pourquoi ??].
Nos données: il a "liké" quatre documents A, B, C et D. Faisons la moyenne de ce qu’il aime:
On obtient un vecteur P de ses goûts moyens.
Ce vecteur P est celui qui est comparé aux nouveaux contenus: les plus proches sont proposés (recommandés) à l’utilisateur.
Problème: Si A, B, C et D sont très différents?
MÉTHODE 2
On commence par clusteriser les contenus passés. Par exemple, on trouve les clusters�{A, B} et {C, D}.
Pour chaque nouveau contenu, on regarde la similarité avec chaque cluster, en utilisant la méthode que l’on veut : distance min, max, moyenne, Ward… ou encore similarité cosinus avec la moyenne (centroïde) de chaque cluster.
→ On moyenne des contenus comparables
→ On réduit la complexité (VS méthode 0)
COMMENT CHOISIR LA SIMILARITÉ ? ET L’ENCODAGE ?
Modélisation des contenus
Comme toujours en Apprentissage : Grâce à l’évaluation sur des vraies données!
(on essaye différentes recettes, on voit ce qui marche bien et moins bien, on itère)
Ici: on peut évaluer à quel point une fonction de similarité donne de bons résultats pour la prédiction
RÉ-ALIMENTATION; COLD START
Algo: Recommandation basée sur le contenu
1. Initialisation: X = {vecteurs} représentant le profil:� TF-IDF des contenus passés aimés par l’utilisateur
2. for each visite sur le site (Netflix, Amazon, …)
3. Recommander des produits à l’utilisateur avec� la méthode 0, 1, 2, ou autre, en fonction de X.
4. Pour tous ceux que l’utilisateur a noté (*),
les ajouter à X�
Problème: Étape 1, le “Cold Start”.
RECOMMANDATION PAR CONTENU: CONCLUSION
Avantages :
Inconvénients :
ALGORITHMES BASÉS SUR LES UTILISATEURS
PRINCIPE
Les utilisateurs ayant aimé les mêmes choses que vous dans le passé continuent à aimer les mêmes choses que vous dans le futur.
Source : blog.comsysto.com
On parle de :
collaborative filtering.
PROBLÈME DE DÉPART
Problème de départ
On cherche à remplir les cases inconnues.
Camille | 4 | 5 | ? | 4 |
Mehdi | 1 | ? | 5 | ? |
Julien | 5 | ? | ? | 2 |
SIMILARITÉ DES UTILISATEURS
Si x et y sont 2 utilisateurs représentés par leur vecteur de goûts, alors la similarité entre eux est mesurée par le coefficient de corrélation :
GESTION DES DONNÉES MANQUANTES
Gestion des données manquantes
Comment mesurer la corrélation entre deux utilisateurs si certaines "cases" sont vides?
D’autres solutions existent, mais + compliquées !
Camille | 4 | 5 | ? | 4 |
Mehdi | 1 | ? | 5 | ? |
Julien | 5 | ? | ? | 2 |
Solution 1: ne prendre en compte que les "lignes" complètes pour les deux utilisateurs.�
Solution 2: remplacer les cases manquantes par la moyenne (⚠).
PROPOSITION DE CONTENUS
Proposition de contenus
On commence par calculer la corrélation entre l’utilisateur-cible et tous les autres.
Les valeurs de corrélation sont alors utilisées comme des poids pour calculer une moyenne pondérée de leurs notes (ratings) pour chaque nouveau contenu.
Cette moyenne pondérée est utilisée pour prédire une note utilisateur-cible/nouveau contenu.
PROPOSITION DE CONTENUS
Proposition de contenus
Problème de complexité ?
→ mêmes techniques qu’avant (Méthode 2,� clustering), ou sampling (on en reparlera).
EXEMPLE
Like? | Étudiant 0 | Étudiant 1 | Étudiant 2 |
Systèmes | 0 | 1 | 0 |
BDD | 1 | 1 | 1 |
Fouille | 1 | 0 | ? |
I.A. | 1 | 0 | 1 |
XML | 1 | 0 | 0 |
L’étudiant 2 va-t-il aimer le cours de Fouille ?�
import numpy as np
E = np.array([[0,1,1,1],
[1,1,0,0],[0,1,1,0]])
C = np.corrcoef(E)
rating = C[0,2]*1+C[1,2]*0
[[ 1. -0.6 0.6]
[-0.6 1. 0.]
[ 0.6 0. 1.]]�� 0.6
EXEMPLE
Like? | Étudiant 0 | Étudiant 1 | Étudiant 2 |
Systèmes | 1 | 3 | 0 |
BDD | 5 | 4 | 4 |
Fouille | 4 | 1 | ? |
I.A. | 4 | 2 | 1 |
XML | 5 | 1 | 1 |
L’étudiant 2 va-t-il aimer le cours de Fouille ?�
import numpy as np
E = np.array([[1,5,4,5],
[3,4,2,1],[0,4,1,1]])
C = np.corrcoef(E)
rating = C[0,2]*4+C[1,2]*1
[[ 1. -0.2 0.7]
[-0.2 1. 0.6]
[ 0.6 0.7 1.]]�� 3.2
PROBLEME DE COLD START
On peut:
Ici, le problème de cold-start revient à avoir un ligne entière vide (cold-start item) ou un colonne entière vide (cold-start user).
Source : bogost.com
PROBLÈMES DE CALCUL
Problèmes de calcul
Si, comme Netflix, on a 100M+ utilisateurs, le calcul en temps réel devient trop lourd:
USER-CENTRIC VS ITEM-CENTRIC
User-centric vs item-centric
L’approche qu’on vient de voir compare d’abord les utilisateurs. On l’appelle user-centric.
On peut, à l’inverse, calculer les similarités sur�les contenus (item-centric) : 2 contenus avec les mêmes ratings utilisateurs ont une similarité 1.
→ On calculera note(d, u) en fonction de� {notes(d’, u)} (au lieu de {notes(d, u’)}).�+ économe: temps réel. Popularisée par Amazon.
⚠: Cette approche est différente de la recommandation par contenu seulement qui n’utilise pas les notes des autres utilisateurs.
COLLABORATIVE FILTERING: CONCLUSION
Conclusion sur le collaborative filtering
Avantages:
�Inconvénients:
AUTRES MÉTHODES
RECOMMANDATION PERSONALISÉE
Approche basée sur le comportement passé de l’utilisateur (clics, cookies, likes...).
On va simplement lui recommander des contenus en fonction de ce qu’il a déjà cherché.
→ Approches plus ad-hoc, algorithmiquement� similaires à la recommandation par contenu� mais où l’input n’est pas des notes de� contenus existants.
Exemples : Criteo, Facebook Ads, AdSense, …
RECOMMANDATION HYBRIDE
La recommandation hybride se base sur les 3 approches précédentes, et combine donc actions passées de l’utilisateur, similarités entre contenus et collaborative filtering.
Plus performante que les autres prises seules, et a plus d’armes pour répondre aux problèmes de cold-start et de sparsity.
En pratique: par exemple pré-remplir la matrice de collaborative filtering avec un algo basé sur le contenu et l’historique de l’utilisateur.
→ Approche utilisée par Amazon, Netflix, …
EXEMPLE: YOUTUBE OU NETFLIX
Recommandation personnalisée : en fonction de l’historique et de nos caractéristiques sociales (localisation, âge, etc.)
Recommandation basée sur le contenu : les vidéos ont des tags similaires
Collaborative filtering : les utilisateurs qui ont aimé la vidéo que vous regardez ont aussi aimé ces autres vidéos.
Concrètement, on peut mettre des poids à chacun de ces types pour le ranking final.
LE PRIX NETFLIX (2007-2009)
cf [wikipedia]. Prix: 1’000’000 $ si ≥10% mieux
480K users, 18K movies, 100M ratings.
Rating: (user, movie, date, grade), grade ∈ {1..5}.
Train: 99M, Test: 1.5M. Evaluation: simple!
Vainqueurs: “Our experience is that most efforts should be concentrated in deriving substantially different approaches, rather than refining a single technique. Consequently, our solution is an ensemble of many methods.”
ÉVALUATION
ÉVALUATION
ÉVALUATION DE LISTE
Deux métriques nous intéressent:
RECALL: Parmi les contenus que user U a aimés, combien étaient dans la liste recommandée ?
PRÉCISION: Dans la liste recommandée, combien l’user U en a-t-il aimé?
L’algorithme parfait a précision=1, recall=1: non seulement la personne adore tout ce que vous lui proposez (précision maximale) mais en plus elle n’aime rien d’autre (recall maximal).
Problème: pour faire augmenter l’un, on prend le risque de baisser l’autre.
EVALUATION DE LISTE
Au seuil 0.9, recall = 2 / 14, précision = 2 / 3
Au seuil 0.7, recall = 3 / 14, précision = 3 / 5
Au seuil 0.6, recall = 4 / 14, précision = 4 / 106
Je propose: | Score: | L’utilisateur clique sur: |
- chat mignon | 0.95 | - chat au foot |
- chat possédé | 0.92 | - chat mignon |
- chat qui tombe | 0.9 | - chat et chien |
- chat qui vole | 0.8 | - chat qui tombe |
- chat au foot | 0.7 | … 10 autres vidéos |
… 100 autres … | >0.6 | hors de ma liste |
- chat et chien | 0.6 | ou de score <0.6 |
EVALUATION DE LISTE
On peut prendre le problème à l’envers:
Pour avoir une précision de 0.9, combien faut-il que je recommande d’objets?
Et est-ce possible dans l’absolu? Cela peut déterminer la taille de votre liste.
EVALUATION DE LISTE ORDONNÉE
D’autres métriques sont utilisées pour renforcer l’idée que le haut de la liste est plus important:
AP (Average Precision) = ⅓(1/1 + 2/2 + 3/5) = 0.87
NDCG (Normalized Discounted Cumulative Gain):
DCG = 1 + 1/log2(2) + 1/log2(5) = 2.43
IDCG = 1 + 1/log2(2) + 1/log2(3) = 2.63 (Ideal)
NDCG = DCG / IDCG = 2.43 / 2.63 = 0.92
Si on a des notes, remplacer “1” par notes.
1 | 2 | 3 | 4 | 5 | 6 | 7 |
EVALUATION DE LISTE - EN PRATIQUE
2 solutions, ou plutôt 2 étapes:
CONCLUSION
En fonction du problème et surtout du type de données, on choisit un algo approprié.
CLUSTERING VS RECOMMANDATION
Attention : ce ne sont pas les mêmes choses ! Il ne faut pas les confondre.
Ces deux types d’algorithmes n’ont en commun que l’utilisation de distances entre objets. (Et parfois le clustering est utilisé dans le cadre de la recommandation):