Principe général de la décomposition en valeurs singulières sur grandes matrices creuses 

Les approches contextuelles

Il existe différents types d’approche suivant la nature des informations contextuelles dont nous disposons (en plus de la matrice utilisateur/article). On peut citer notamment, les approches dites démographiques qui basent la personnalisation de la recommandation sur le profil de l’utilisateur, comme son âge, son sexe, sa nationalité, sa localisation géographique (Zheng et al. 2011). . .
Les approches orientées communauté utilisent les informations sociales de l’utilisateur pour effectuer la prédiction. Les goûts supposés d’un utilisateur seront directement influencés par ceux de ses amis. Nous reviendrons d’ailleurs en détail sur ces approches dans le chapitre 4.
Les approches que l’on peut appeler temporelles se basent sur la non constance des préférences d’un utilisateur dans le temps, ainsi la recommandation pourra être fortement dépendante du moment où est faite cette recommandation.
Ces informations contextuelles peuvent être utilisées à différents niveaux dans le processus de recommandation. Elles peuvent être utilisées en prétraitement afin de ne sélectionner que les informations qui nous intéressent pour construire le modèle. Elles peuvent être utilisées en post traitement afin de ne sélectionner, parmi les articles recommandés, que ceux qui correspondent au contexte.
Enfin, ces données contextuelles peuvent être utilisées directement au cours de la construction du modèle.
Le chapitre 3 de ce manuscrit se concentre sur ces aspects contextuels de la recommandation.
Nous reviendrons dessus plus en détail dans cette partie.

Les obstacles rencontrés par les systèmes de recommandation

En plus de la nature particulière des données dans les systèmes de recommandation, d’autres difficultés se posent. C’est également le cas de l’évaluation. Il est en effet difficile d’évaluer la pertinence d’un système de recommandation. [Ricci et al. 2011, Pu et al. 2012, Pradel 2013] se sont intéressés à ce problème.

Les types de données : des volumes massifs

La nature même des données dont nous disposons peut soulever des difficultés pour la mise en place d’un système de recommandation. Commençons par présenter ces données avant de préciser les obstacles que l’on peut rencontrer.
Les données utilisées dans les systèmes de recommandation ont des caractéristiques particulières comme leur volume car la taille des matrices d’achats/préférences est souvent très grande. Les données de Netflix contenaient environ 500 000 utilisateurs et 17 000 articles et Amazon rapportait en 2003 devoir gérer 29 millions d’utilisateurs et un catalogue de plusieurs millions d’articles. Notons par ailleurs que la nature de ces données va jouer un rôle primordial dans la formalisation du problème et dans sa résolution. En effet, une matrice de transactions, contenant donc uniquement les valeurs 1 ou 0 (1 signifiant qu’une action a été effectuée par un utilisateur donné pour un article donné), ne sera pas traitée de la même façon qu’une matrice de vote (rating ) qui, elle, ne contient typiquement que des valeurs comprises en 0 et 5, où une valeur entre 1 et 5 indique l’appréciation explicite d’un utilisateur pour un article, et où 0 indique l’absence d’appréciation. Ainsi dans le cas des matrices de vote, 0 signifie simplement que la valeur n’est pas renseignée alors que dans le cas des matrices de transactions, la signification exacte du 0 est inconnue. Cela peut signifier que l’utilisateur n’aime pas l’article, qu’il ignore l’existence de l’article ou qu’il en a connaissance mais n’a encore effectué aucune action (on pourra choisir dans certains cas de considérer ces 0 effectivement comme une appréciation négative de l’utilisateur avec une pénalisation moindre que les 1 dans la fonction coût, ou du moins un certain nombre de ces 0). On appelle généralement ces données de transaction, des données d’appréciations implicites (implicit feedback). Les sens très différents des 0 dans ces deux types de matrices imposent des modèles et des manipulations différentes. De plus, ces matrices sont creuses (souvent moins de 1% de valeurs non nulles).

L’éthique et les systèmes de recommandation

Il nous semble important d’évoquer les problèmes éthiques soulevés dans le monde de la recommandation. De nombreuses polémiques ont eu lieu quant à la façon dont étaient recueillies, stockées ou utilisées certaines données sur les utilisateurs ; en effet, la personnalisation des recommandations est d’autant plus précise qu’elle utilise des données pertinentes sur l’utilisateur, ses goûts et ses comportements. Or l’acquisition et le stockage de données personnelles peut s’avérer intrusive et constituer une violation de la vie privée, notamment lorsque les informations sont collectées de manière implicite à l’insu de l’utilisateur (sans parler des risques de divulgation inopportune de ce type d’information). De plus l’absence de transparence des entreprises quant à l’utilisation de ces données ou à la façon dont sont réalisées les recommandations n’est en rien rassurante pour les utilisateurs. On peut notamment citer Google qui est poursuivi en juin 2013 par la CNIL pour la façon jugée illégale de collecte d’informations des utilisateurs et pour l’absence de transparence de l’utilisation qui est faite de ces informations. Netflix a également fait l’objet d’une plainte en décembre 2009 pour avoir libéré les données du challenge bien qu’aucune information personnelle n’y figurait.
De plus, la connaissance de l’utilisateur par le système de recommandation pourrait aller jusqu’à la personnalisation d’une véritable stratégie d’influence (Kaptein & Eckles 2010). Un système de recommandation se doit, en plus de respecter la législation, d’être transparent sur sa façon d’effectuer les recommandations pour éviter son rejet par les utilisateurs. Ainsi il devient fréquent de se voir justifier la suggestion d’un article par des phrases du type « les utilisateurs qui ont acheté ce produit, ont également acheté tel produit » rassurantes pour l’utilisateur, qui voit ainsi comment sont utilisés les informations dont disposent les entreprises.
Il reste cependant beaucoup à faire, principalement sur le manque de transparence au niveau de la collecte des données et sur leur utilisation.

L’avenir des systèmes de recommandation

Bien que la recherche dans le domaine des systèmes de recommandation n’en est qu’à ses débuts, l’engouement des chercheurs au cours de ces vingt dernières années a fait grandement avancer les choses. Le livre Recommender Systems Handbook, qui présente un bilan exhaustif des systèmes de recommandation, montre déjà une certaine maturité du domaine de recherche.
Des workshops et des thèmes de recherche consacrés aux systèmes de recommandation ont fait leur apparition dans les principalement conférences internationales en apprentissage artificiel et en fouille de données ou dans des conférences spécialisées dans le domain . De nouvelles tendances de recherche apparaissent régulièrement, comme par exemple le crowdsourcing (externalisation ouverte) appliqué aux systèmes de recommandation qui fait l’objet d’un workshop dans la conférence ACM RecSys . Le développement constant de sociétés sur Internet ayant de réels besoins en terme de recommandation assure un avenir florissant à ce domaine de recherche, où de nouvelles problèmatiques naissent régulièrement et où les contraintes techniques (temps de calcul, stockage des données. . .) nécessitent un réel apport de la communauté scientifique.

Les types de données contextuelles

Les données contextuelles par nature sont très variées. Les données les plus couramment rencontrées (et utilisées) dans les systèmes de recommandation sont les variables « utilisateurs » et lesvariables « produits » 1 . Il existe également d’autres informations, aussi bien explicites qu’implicites qui peuvent être utilisées pour améliorer la recommandation (données temporelles, graphe social. . .).
Nous allons maintenant détailler les données utilisées pour la contextualisation.

Les variables utilisateurs et produits

Lorsque l’on parle de variables utilisateurs, il s’agit généralement de données telles que l’âge, le sexe, l’adresse. Il est aussi possible d’utiliser d’autres données propres à l’utilisateur, comme par exemple la position géographique ou l’adresse IP.
Les variables produits diffèrent suivant la nature du produit. Par exemple lorsque les produits à recommander sont des films, il peut s’agir du réalisateur, du genre filmographique ou de la durée.
L’intérêt d’utiliser ces variables pour améliorer la recommandation peut être illustré avec l’exemple suivant : les films « Dora l’exploratrice » auront sûrement plus de succès pour un public en bas âge, tandis que « Derrick » intéressera plus un public d’un certain âge. De la même façon, un cliché répandu suggère qu’un public féminin aura peut être plus de plaisir à regarder une comédie romantique qu’un public masculin, qui lui préfèrera des films d’actions. Ainsi en utilisant le genre cinématographique des films, l’âge et le sexe des utilisateurs comme information de contextualisation, il est très certainement possible d’améliorer la qualité de prédiction d’un système de recommmandation de film.
En revanche, si l’on souhaite recommander des restaurants, on s’intéressera plutôt au type de nourriture proposé, au prix, à l’adresse ou encore à l’appréciation donnée par des guides culinaires.
On pourra également utiliser la position actuelle de l’utilisateur.
La recommandation de publicité ciblée sur Internet peut être, quant à elle, améliorée en prenant en compte l’adresse IP de l’utilisateur par exemple.
La définition de variable utilisateur ou variable produit est à prendre au sens large, n’importe quelle information sur l’utilisateur ou sur le produit peut être utilisée comme information contextuelle, dés lors qu’elle est susceptible de permettre une meilleure identification du comportement, des goûts de l’utilisateur ou une meilleure catégorisation des produits.

Les données sociales

Dans le cadre de la recommandation dans les réseaux sociaux, l’utilisation des données sociales telles que le graphe d’amitié ou graphe de confiance est très commune. On effectue généralement la prédiction des préférences d’un utilisateur en s’intéressant aux préférences des personnes avec qui il est ami ou en qui il a confiance.
Nous reviendrons en détail sur la recommandation dans les réseaux sociaux dans le chapitre 4 car l’utilisation de ce type d’approche contextuelle en est l’objet principal.

Informations contextuelles implicites

Les données présentées précédemment peuvent permettre d’extraire des informations contextuelles de façon explicite. Ces données peuvent ne pas suffire à définir des contextes. Dans certains cas, le contexte doit être déduit à partir des données connues (et grâce éventuellement à une connaissance experte du domaine). On parlera alors d’information contextuelle implicite. Le cas d’étude présenté en section 3.3 de ce chapitre fait justement l’objet d’une contextualisation implicite qui a nécessité une connaissance a priori sur les produits. En effet si, un client achète une baignoire et du carrelage, on peut déduire que ce client s’est lancé dans un chantier de construction (ou de rénovation) de salle de bain, cette information implicite peut être utilisée pour une contextualisation éventuelle.

Les différents paradigmes de contextualisation

La contextualisation peut intervenir à différents endroits dans un système de recommandation.
Trois grands types d’approche de contextualisation sont généralement définis suivant la place (dans le processus de construction du modèle) où cette contextualisation intervient. Ces approches sont les suivantes :
– la contextualisation par prétraitement (contextual pre-filtering ),
– la contextualisation par post-traitement (contextual post-filtering ),
– la modélisation contextuelle (contextual modeling ).
La première approche consiste à ne sélectionner qu’un certain sous-ensemble des données pour la construction du modèle, ou à partitionner les données pour construire un ensemble de modèles. La deuxième, quant à elle, consiste à ne garder en sortie du modèle qu’un sous-ensemble des données.
Enfin la troisième approche consiste à utiliser au cours de la construction du modèle les données contextuelles dont nous disposons.
Nous allons présenter brièvement ces trois paradigmes. Pour des informations complémentaires, nous invitons le lecteur à consulter la section 3 de [Adomavicius & Tuzhilin 2011].

La contextualisation par post-traitement

Dans une approche de contextualisation par post-traitement (contextual post-filtering ), le système de recommandation ne prend pas en compte les données contextuelles lors de l’apprentissage du modèle. Ce n’est qu’après l’évaluation du modèle pour un utilisateur donné que le contexte entre en jeu. Il peut intervenir de deux façons différentes. À partir de la liste des recommandations sortant de l’évaluation, le système peut filtrer en retirant de la liste un certain nombre de produits recommandés selon le contexte, ou le système peut pondérer chacun des produits de la liste suivant le contexte et réordonner la liste des produits en fonction des nouveaux scores obtenus. Notons que cette approche est généralement utilisée dans des problèmes d’ordonnancement.
Un exemple simple et régulièrement utilisé de ce type de procédure consiste à retirer de la liste de recommandation l’ensemble des produits déjà achetés par l’utilisateur. Les informations contextuelles utilisées sont les données de transactions elles mêmes et l’on fait la supposition que l’utilisateur ne sera pas intéressé par un produit qu’il a déjà acheté. Cette hypothèse est valide dans la plupart des cas. De plus, même si ce produit peut à nouveau intéresser l’utilisateur, il connaît son existence (puisqu’il l’a acheté) et il devient inutile de le recommander. Un autre exemple de recommandation dans un paradigme de contextualisation par post-traitement pourrait être, lorsque l’on cherche à recommander des lieux (bars, restaurants, musées. . .), de ne suggérer parmi les lieux sélectionnés, que les lieux géographiquement proches de la position actuelle de l’utilisateur.
Cette approche ne souffre pas de la faiblesse de l’approche prétraitement étant donné qu’il n’y a qu’un modèle à construire. La difficulté de cette approche réside dans le choix (arbitraire) ou dans l’apprentissage des coefficients de pondération.

Table des matières
Introduction 
1 Présentation des systèmes de recommandation 
1.1 Contexte
1.1.1 Une histoire de la recommandation
1.1.2 Le challenge Netflix
1.2 Les problématiques usuelles
1.3 Les différentes approches
1.3.1 Les approches classiques
1.3.2 Les approches contextuelles
1.4 Les obstacles rencontrés par les systèmes de recommandation
1.4.1 Les types de données : des volumes massifs
1.4.2 L’éthique et les systèmes de recommandation
1.5 L’avenir des systèmes de recommandation
2 Factorisation et Recommandation, un état de l’art 
2.1 Formalisation du problème de Factorisation
2.1.1 Notation et Formulation générale
2.1.2 Les différentes approches
2.1.3 Les problèmes sous-jacents à ces approches
2.1.4 Le choix du critère d’attache aux données
2.1.5 Le terme régularisant
2.1.6 La nature des problèmes
2.1.7 La matrice de bruit
2.2 La factorisation dans la recommandation
2.2.1 Méthode de résolution exacte sur grandes matrices creuses
2.2.1.1 Principe général de la décomposition en valeurs singulières sur grandes matrices creuses
2.2.1.2 Bi-diagonalisation
2.2.1.3 Diagonalisation d’une matrice bi-diagonale
2.2.2 Descente de gradient stochastique (SGD)
2.2.3 Optimisation alternée
2.2.4 Algorithme Multiplicatif
2.2.5 Approches non linéaires
2.2.6 Factorisation Tensorielle
2.3 Les méthodes d’évaluation
2.3.1 Le choix des modèles
2.3.2 La méthode d’évaluation
2.3.3 La métrique d’évaluation
2.4 Conclusion
3 Tout est une histoire de contexte 
3.1 Les types de données contextuelles
3.1.1 Les variables utilisateurs et produits
3.1.2 Les données temporelles
3.1.3 Les données sociales
3.1.4 Informations contextuelles implicites
3.2 Les différents paradigmes de contextualisation
3.2.1 La contextualisation par prétraitement
3.2.2 La contextualisation par post-traitement
3.2.3 La modélisation contextuelle
3.3 Un cas d’étude précis : la vente d’outils
3.3.1 Présentation du problème
3.3.2 Présentation des approches contextuelles
3.3.2.1 Un contexte temporel
3.3.2.2 Un contexte de chantier
3.3.3 Protocole expérimental
3.3.3.1 Méthodes de factorisation choisies
3.3.3.2 Évaluation
3.3.3.3 Protocole de contextualisation temporelle
3.3.3.4 Protocole de contextualisation par chantier préliminaire
3.3.3.5 Protocole de contextualisation par chantier évolué
3.4 Discussion
4 Recommandation dans les réseaux sociaux 
4.1 Les Concepts
4.2 État de l’art sur la recommandation dans les réseaux sociaux
4.2.1 Notations
4.2.2 Ajout de contraintes au problème
4.2.3 Modification de la fonction de décision
4.3 D’une pierre deux coups : recommandation et apprentissage d’influence
4.3.1 L’influence des amis
4.3.2 Optimisation
4.3.2.1 Mise à jour de U
4.3.2.2 Mise à jour de V
4.3.2.3 Mise à jour de A
4.3.2.4 Algorithme
4.3.2.5 Prédiction
4.3.3 Expérimentations
4.3.3.1 Les Problèmes
4.3.3.2 Les données
4.3.3.3 Protocole d’évaluation
4.3.3.4 Méthodes en comparaison
4.3.3.5 Résultats d’expériences
4.4 Discussion
5 Sélection de modèle pour la factorisation 
5.1 La sélection de modèle
5.1.1 Un cadre de sélection de modèle
5.1.2 Estimation du risque
5.1.3 Choix du critère, de la pénalité et du coût
5.2 Sélection de modèle dans la factorisation
5.2.1 État de l’art
5.2.2 Formalisation du problème
5.2.3 Pénalité et estimateur du risque
5.2.4 Estimateur sans biais du risque
5.2.5 Calcul de la divergence
5.2.6 Limites du modèle actuel
5.3 Adaptation et élargissement de la méthode
5.3.1 Amélioration relative à la fonction de seuillage
5.3.1.1 Fonctions de seuillage proposées
5.3.1.2 Protocole expérimental
5.3.1.3 Quelques résultats expérimentaux
5.3.2 Passage à l’échelle
5.3.2.1 Approximation de la divergence
5.3.2.2 Protocole expérimental
5.3.2.3 Résultats expérimentaux
5.3.3 Estimation de la variance
5.3.3.1 Protocole expérimental
5.3.3.2 Quelques résultats
5.4 Discussion
Conclusion 
A Article sur la recommandation contextuelle
B Annexes diverses
B.1 Calcul de la divergence
B.2 Introduction à la notion de différentielle pour les matrices
B.3 Calcul de la fonction de répartition de la loi de Marchenko-Pastur
Références 

Lire le rapport complet