Présentation de la semaine |
 |
Le filtrage collaboratif désigne l’ensemble des méthodes utilisées pour faire des recommandations automatisées aux utilisateurs d’un système informatique, en s’appuyant sur une base de données contenant des renseignements sur les choix faits par un grand nombre d’utilisateurs. Par définition, il faut que plusieurs utilisateurs partagent leurs choix avec d’autres utilisateurs pour qu’on puisse parler de filtrage collaboratif. Le consentement des utilisateurs n’est pas nécessaire, mais souhaitable.
Tous les systèmes informatiques, capables d’offrir des recommandations automatisées à ses usagers, ne font pas nécessairement appel au filtrage collaboratif. Par exemple, on ne considère pas PageRank ou les modèles vectoriels comme des outils de filtrage collaboratif mais, néanmoins, ils permettent de faire des recommandations.
Dans cette section du cours, on distinguera trois types d’algorithmes utiles pour le filtrage collaboratif :
– les algorithmes utilisateur-utilisateur ;
– les algorithmes article-article (ou article par article) ;
– les algorithmes basés sur l’apprentissage-machine.
Cette semaine sera dédiée au filtrage collaboratif utilisateur-utilisateur, alors que la semaine prochaine nous couvrirons les algorithmes article-article. Cependant, nous ne traiterons pas des algorithmes basés sur l’apprentissage-machine.
La petite histoire du filtrage collaboratif
Le terme collaborative filtering fut proposé par David Golberg et ses collaborateurs chez Xerox en 1992 [1].
Deux ans plus tard, en 1994, Paul Resnick [2] du MIT (Massachusetts Institute of Technology) et ses collaborateurs de l’Université du Minnesota proposèrent l’architecture GroupLens [3] pour recommander des articles dans les très populaires newsgroup [4]. Le groupe de recherche GroupLens demeure à ce jour le groupe de chercheurs le plus influent en filtrage collaboratif. Ils ont notamment produit le livre Word of Mouse : The Marketing Power of Collaborative Filtering.
La librairie Amazon a popularisé le filtrage collaboratif avec « sa fonction : les utilisateurs qui ont aimé ce livre ont aussi aimé tel autre livre ». L’ingénieur responsable de ce projet, Greg Linden, a d’ailleurs un blogue très intéressant (en anglais). Fondée en 1994 à partir de rien, Amazon est devenue la librairie la plus importante aux États-Unis.
En 1998, Brin et Page publièrent leur algorithme PageRank et lancèrent Google. La même année, chez Microsoft, John S. Breese et ses collaborateurs publièrent un article charnière,
« Empirical Analysis of Predictive Algorithms for Collaborative Filtering » [5] dans lequel on faisait une comparaison détaillée des divers algorithmes de filtrage collaboratif.
Avant 2001, les algorithmes de filtrage collaboratif étaient soit basés sur l’intelligence artificielle (les réseaux bayésiens, les réseaux de neurones, etc.), soit basés sur une approche utilisateur-utilisateur. En 2001, Amazon innovait avec la publication d’un brevet [6] introduisant le filtrage collaboratif basé sur l’article ; la même année, le groupe GroupLens publiait aussi, indépendamment [7], le même type d’algorithme [8].
En 2006, la compagnie Netflix a annoncé qu’elle accorderait un prix d’un million de dollars à celui qui améliorerait de 10 % leur outil de recommandation. La Compagnie rend ainsi disponible un ensemble de données qui permettent de tester des systèmes. La compétition prendra fin en 2011. Les résidents du Québec ne peuvent y participer.
Hiérarchie du degré de distribution du filtrage collaboratif
Le filtrage collaboratif, tel que nous le connaissons, est né un peu avec le web. Il serait juste de faire un lien entre l’aspect collaboratif du filtrage et l’émergence d’un web entièrement distribué.
De plus en plus, les consommateurs veulent avoir plus de contrôle sur leurs achats et sur leurs données. On cherche donc à éviter de centraliser les données [9]. On distingue trois niveaux de distribution du filtrage collaboratif :
Niveau 1. Les biens et services ainsi que les données sont centralisés chez un seul fournisseur, comme c’est le cas avec Amazon.
Niveau 2. Seules les données (choix des utilisateurs) sont centralisées, les biens et services sont distribués. (Ce serait le cas d’un site vous offrant de l’aide pour trouver le meilleur vendeur de voiture.)
Niveau 3. Les choix des utilisateurs ainsi que les biens et services sont distribués. Les recommandations se font de poste à poste.
Bien que ce ne soit qu’une théorie, plusieurs personnes pensent qu’il y a une tendance à passer du premier niveau aux niveaux supérieurs. Cependant, les difficultés technologiques sont de taille ! Construire un site comme Amazon est déjà en soi une prouesse technique : offrir l’équivalent en qualité de service de manière distribuée est très difficile.
[1] David Goldberg, David Nichols, Brian Oki, and Douglas Terry, Using collaborative filtering to weave an
information tapestry, Communications of the ACM,
vol. 35, No. 12, 1992, p. 61-70.
[3] Paul Resnick, et al., GroupLens : an open architecture for collaborative filtering of netnews.
[4] On n’utilise guère les forums (newsgroups) de nos jours. Ils ont été remplacés par les blogues, les wiki et les babillards électroniques.
[5] J. S. Breese, D. Heckerman, and C. Kadie, Empirical analysis of predictive algorithms for collaborative filtering, In Proceedings of the 14th Conference on Uncertainty in Artificial Intelligence, Madison (WI), Morgan Kaufmann Eds., 1998, p. 43-52.
[6] G. Linden J. Jacobi, and E. Benson, « Collaborative Recommendations Using Item-to-Item Similarity Mappings », US Patent 6,266,649 (to Amazon.com), Patent and Trademark Office, Washington (D.C.), 2001.
[7] Cependant, il faut accorder à Amazon la préférence parce que le brevet fut déposé en 1998.
[8] Sarwar, B., Karypis, G., Konstan, J., and Reidl, J., « Item-based collaborative filtering recommendation algorithms », Proceedings of the tenth International Conference on World Wide Web, 2001, p. 202-208.
[9] Tomas Olsson, Bootstrapping and Decentralizing Recommender Systems, Dissertation for the degree of the Licentiate, Uppsala University, 2003, et « Resource Profiles », by Stephen Downes, 2003.
