algorithmes de recommandation.
L’objectif de cet article est de présenter brièvement le principe de fonctionnement de ces algorithmes et de montrer comment de simples notions d’algèbre linéaire peuvent transformer un ordinateur en véritable oracle. Dans la suite de l’article, on prendra YouTube comme exemple d’illustration, mais le principe reste évidemment valable pour de nombreuses autres plates-formes (Facebook, Netflix, Spotify, etc).
Pour comprendre les préférences de chacun, rien de tel qu’un tableau
Le problème à résoudre s’énonce comme suit : considérons nvidéos et m internautes (m et n étant potentiellement très grands). Supposons qu’une des personnes ait déjà visionné quelques-unes des vidéos disponibles. Alors, quelle(s) autre(s) vidéo(s) sera-t-elle susceptible d’aimer le plus ?
Deux idées sont alors possibles : soit elle aimera des vidéos semblables à ce qu’elle a déjà aimé dans le passé – on développe alors la technique du filtrage par contenu. Soit elle aimera ce qui a déjà plu à d’autres personnes qui lui ressemblent – et on optera pour le filtrage collaboratif.
La première idée requiert la définition a priori de nombreux critères. Elle n’est en pratique utilisée que dans des cas très particuliers. Nous allons donc nous concentrer sur la seconde idée.
Représentons notre problème avec une matrice D (de taille n x m) où chaque colonne représente une personne et chaque ligne une vidéo. Dans chaque case, on met un nombre compris entre 0 et 4 (comme un système de notation avec 5 étoiles). La valeur 0 indique que la personne a détesté la vidéo et la valeur 4 indique qu’elle lui a plu. Cette note varie selon le temps passé sur la vidéo, le fait d’avoir mis une mention « j’aime » ou non, le fait d’avoir commenté ou pas, etc. Elle est en pratique calculée grâce à une recette confidentielle de YouTube. Une case correspondant à une vidéo qui n’a pas encore été visionnée par la personne reste vide. L’objectif de l’algorithme est alors de deviner les valeurs à mettre dans ces cases vides afin d’estimer quelle vidéo plaira le plus à l’utilisateur.
L’idée du filtrage collaboratif est de considérer que la préférence d’une personne pour une vidéo sera donnée par un « produit scalaire » de deux vecteurs u et v représentant respectivement les caractéristiques de la personne et celles de la vidéo. S’il y a une absence totale de caractéristiques communes entre la personne et la vidéo, on dit que u est « orthogonal » à v et le produit scalaire uv est nul. Inversement, si la personne et la vidéo ont des caractéristiques communes, les vecteurs u et v sont dits « quasi colinéaires » et leur produit scalaire donne une note élevée.
En déterminant les caractéristiques communes entre les vidéos et les internautes, on peut ainsi attribuer une note potentielle à chaque vidéo : la note que mettrait (peut-être) l’utilisateur à cette vidéo s’il la visionnait.
Utiliser un outil de base de l’algèbre linéaire
L’idée mathématique sous-jacente est de décomposer la matrice des données D en produit de deux petites matrices U et V. Une telle décomposition permet de caractériser les personnes (à travers la matrice U) et les vidéos (à travers la matrice V) par un petit nombre k de vecteurs.
Ainsi, pour chaque case remplie (par exemple la case verte sur la Figure), on va chercher les vecteurs u (indiqué en bleu) et v(indiqué en rouge) des matrices U et V tels que le produit u x vsoit le plus proche possible de la valeur de la case verte. Pour les plus curieux, cela revient à résoudre un problème d’optimisation.
Il suffit en fait de multiplier les lignes de U par les colonnes de V pour retrouver les valeurs de toutes les cases vides et estimer ainsi la préférence future de chaque personne pour chaque vidéo.
En raison du nombre gigantesque de personnes et de vidéos, la résolution de ce problème requiert l’utilisation d’algorithmes d’apprentissage comme les réseaux de neurones qui sont bien plus rapides que les techniques d’optimisation classiques.
Est-ce vraiment aussi simple ?
On peut se demander si c’est cela que fait YouTube réellement – la réponse est affirmative sur le principe, mais avec énormément d’améliorations bien entendu. Le véritable système de recommandation de YouTube combine en fait deux réseaux de neurones profonds, comme expliqué dans cet L’article. Le premier sert à identifier quelques centaines de candidats parmi les millions de vidéos disponibles et le second attribue un score à chaque candidat grâce à la décomposition matricielle expliquée dans cet article. ,
