{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Systèmes de recommandation et algorithmes de bandits\n", "\n", "### Introduction :\n", "Les **systèmes de recommandation automatiques** à très grande échelle sont aujourd'hui omniprésents sur internet : ouvrages conseillés à l'achat dans les librairies en ligne, articles recommandés sur les sites d'information, sans parler des cadres publicitaires qui financent l'essentiel de très nombreux sites aujourd'hui... \n", "\n", "Trouver la meilleure recommandation à faire à un visiteur peut être considéré comme un **\"problème de bandits\"** : il faut en même temps apprendre ses préférences, et utiliser les interactions déjà passées pour maximiser le nombre de recommandations suivies, tout en restant capable de gérer des flux de données très importants. \n", "\n", "Nous présentons ici quelques-uns des algorithmes les plus célèbres pour résoudre ce type de problèmes, et notamment l'algorithme **$\\epsilon$-greedy**, l'algorithme **UCB** (Upper Confidence Bound), et l'algorithme **EXP3** (Exponential weights for Exploration and Exploitation). Leurs mérites respectifs sont soulignés et discutés, avec la présentation des résultats théoriques les plus importants les concernant. \n", "\n", "Nous montrons en outre comment expérimenter l'efficacité de ces méthodes pour la recommandation : ceci pose une difficulté particulière, car des jeux de données statiques rendent peu aisée l'évaluation de méthodes vouées à interagir avec des utilisateurs. Nous montrons en particulier comment mettre en place des expériences sur deux jeux de données célèbres : *movielens* et *jester*." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## I. Systèmes de recommandation" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Les **systèmes de recommandation (SR)** ont pour objectif de proposer à l’utilisateur des items (documents, objets, films, musiques, informations, etc.) susceptibles de l’intéresser. Deux approches principales sont mises en œuvre dans les SR : **le filtrage basé sur le contenu** recommande à un utilisateur des items similaires à ceux qu’il a déjà aimés par le passé et **le filtrage collaboratif** (FC) recommande les items appréciés par les utilisateurs qui ont auparavant fait des choix similaires à ceux de l’utilisateur. D’autres approches existent comme, par exemple, le filtrage démographique qui se base sur ce que l’on sait de l’utilisateur (âge, données démographiques, sexe, etc.) ; le filtrage communautaire qui utilise les décisions faites par les contacts de cet utilisateur (cette méthode est notamment utilisée dans les SR sociaux).\n", "\n", "De nombreux SR recommandent à chaque instant plusieurs objets à un utilisateur simultanément; ils sont qualifiés de **SR à tirages multiples**. L’utilisateur peut choisir de sélectionner un ou plusieurs objets parmi ceux qui lui ont été recommandés. Les recommandations sélectionnées sont généralement considérées comme pertinentes. L’utilisateur peut ne pas sélectionner de recommandation dans la liste qui lui est proposée. Il s’agit d’un **abandon** qui correspond donc au cas où aucune des recommandations n’est sélectionnée par l’utilisateur. Dans le but d’optimiser les performances d’un SR, nous considérons le problème de la minimisation de l’abandon, particulièrement adapté à la recommandation à tirages multiples. Ce problème peut également être vu comme la maximisation du nombre de fois où les utilisateurs sélectionnent au moins un objet parmi ceux recommandés simultanément.\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## II. Modèles de bandits\n", "\n", "Afin d’améliorer la pertinence des recommandations pour l’utilisateur courant, un SR peut considérer l’historique des interactions passées avec les utilisateurs. Pour cela, il convient de mettre en place **une stratégie permettant d’apprendre sur la pertinence des objets tout en continuant de recommander des objets pertinents**. Lorsque toutes les\n", "données sont connues, il est possible d’estimer la pertinence des objets, c’est le cadre d’apprentissage supervisé (Hastie et al., 2009). Ce n’est pas un cadre réaliste pour un SR : de nouveaux utilisateurs et de nouveaux objets apparaissent continuellement. De plus, le choix des objets à recommander à chaque interaction est réalisé en fonction\n", "des interactions passées. \n", "\n", "Un tel environnement s’inscrit dans le cadre de ce que l’on appelle **l’apprentissage par renforcement** (Sutton et Barto, 1999). Il s’agit d’implémenter une stratégie pour obtenir de nouvelles informations (exploration), tout en assurant que le SR recommande des objets pertinents (exploitation). Ce problème est connu sous le nom de **\"dilemme exploration/exploitation\"**. \n", "\n", "\n", "Les **modèles de bandit** sont connus pour offrir une première approche formelle à ce dilemme.\n", "L'étude mathématique des problèmes de bandits remonte à l'article pionnier [1]. De nombreux travaux ont\n", "suivi, notamment dans le champ de l'apprentissage statistique, en relation avec la théorie des jeux, l'apprentissage actif, et l'agrégation d'estimateurs : on pourra par exemple se référer à l'ouvrage de référence [2]. Dans\n", "cette littérature, de nombreux problèmes tant théoriques que computationnels\n", "sont abordés, en combinant théorie des probabilités et optimisation convexe.\n", "La communauté statistique a également contribué, notamment sous la\n", "dénomination d'*inférence séquentielle* (voir [3,4] et les références citées), avec un point de vue essentiellement asymptotique.\n", "\n", "Dans la version stochastique, la plus simple du problème, \n", "\n", " - à chaque étape $t=1,2,\\dots$ **l'agent choisit un bras** $A_t\\in\\{1,\\dots,K\\}$,\n", " - et **il reçoit une récompense** $X_t$ telle que, conditionnellement au choix des bras $A_1,A_2,\\dots$, les récompenses soient indépendantes et identiquement distribuées, d'espérances $\\mu_{A_1},\\mu_{A_2},\\dots$\n", " \n", "On appelle *politique* la règle de décision (potentiellement randomisée) qui, aux observations passées $(A_1,X_1,\\dots, A_{t-1}, X_{t-1})$, associe le prochain choix $A_t$. \n", "\n", "Le meilleur choix (inconnu de l'agent) est le bras $a^*$ qui correspond à la récompense moyenne maximale $\\mu_{a^*}$. La performance d'une politique est mesurée par le **regret $R_n$**, qui est défini comme la différence moyenne entre les récompenses qu'elle permet d'accumuler jusqu'au temps $t=n$ et ce qui aurait pu être obtenu pendant la même période si le meilleur bras était connu à l'avance~:\n", "$$R_n = n \\mu_{a^*} - \\mathbb{E}\\left[\\sum_{t=1}^n X_t \\right]\\;.$$\n", "\n", "Un algorithme de bandit ne peut pas être arbritrairement bon : il existe une **borne inférieure** au regret qu'il doit encourir dès lors qu'il offre des garanties uniformes de performance. \n", "La plus célèbre de ces bornes inférieures est celle de Lai et Robbins [6] (voir [7] pour une preuve moderne et plus générale). Dans le cas de récompenses binaires, elle stipule que si une \n", "politique assure dans tout environnement un regret sous-polynômial, alors celui-ci est **toujours au moins logarithmique** : quels que soient $\\mu_1,\\dots,\\mu_K\\in ]0,1[$, \n", "$$\n", " R_n \\geq \\left(\\sum_{a: \\mu_a<\\mu_{a^*}} \\frac{\\mu_{a^*}-\\mu_a}{\\mathrm{kl}\\left( \\mu_{a}, \\mu_{a^*}\\right)}\\right)\\;\\log(n) \\;\\big(1-\\mathrm{o}(1)\\big),\n", "$$\n", "\n", "où $\\mathrm{kl}$ désigne l'entropie binaire: $\\mathrm{kl}(x,y = x\\log(x/y) + (1-x)\\log\\big((1-x)/(1-y)\\big)$." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## III. Algorithmes de bandits" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### III.1 Politique $\\epsilon$-Greedy [9]" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ " A chaque instant $t$ :\n", "