Systèmes de recommandation et algorithmes de bandits¶
Introduction :¶
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...
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.
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.
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.
I. Systèmes de recommandation¶
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).
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.
II. Modèles de bandits¶
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 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 des interactions passées.
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".
Les modèles de bandit sont connus pour offrir une première approche formelle à ce dilemme. L'étude mathématique des problèmes de bandits remonte à l'article pionnier [1]. De nombreux travaux ont 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 cette littérature, de nombreux problèmes tant théoriques que computationnels sont abordés, en combinant théorie des probabilités et optimisation convexe. La communauté statistique a également contribué, notamment sous la dénomination d'inférence séquentielle (voir [3,4] et les références citées), avec un point de vue essentiellement asymptotique.
Dans la version stochastique, la plus simple du problème,
- à chaque étape $t=1,2,\dots$ l'agent choisit un bras $A_t\in\{1,\dots,K\}$,
- 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$
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$.
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~: $$R_n = n \mu_{a^*} - \mathbb{E}\left[\sum_{t=1}^n X_t \right]\;.$$
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. 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 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[$, $$ Rn \geq \left(\sum{a: \mua<\mu{a^}} \frac{\mu_{a^}-\mua}{\mathrm{kl}\left( \mu{a}, \mu_{a^*}\right)}\right)\;\log(n) \;\big(1-\mathrm{o}(1)\big), $$
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)$.
III. Algorithmes de bandits¶
III.1 Politique $\epsilon$-Greedy [9]¶
A chaque instant $t$ :
- Avec une probabilité de $1 - \epsilon_t$, recommander le document ayant le plus fort taux de clics estimé (Exploitation);
- Avec une probabilité de $\epsilon_t$, recommander un document tiré selon une loi uniforme (Exploration).
# Exemple epsilon-greedy algorithm
%matplotlib inline
from pylab import *
import matplotlib.pyplot as pyplot
import re
import math
import random
import numpy
class EpsilonGreedy():
def __init__(self, epsilon = 0.05, counts = [], values = [], n_arms = 0):
"""Récupère les paramètres spécifiés lors de la création d'un objet de cette classe"""
self.epsilon = epsilon
self.counts = [0 for col in range(n_arms)]
self.values = [0.0 for col in range(n_arms)]
def select_arm(self):
""" Selectionne le bras avec la valeur la plus haute si random.random() > Epsilon, sinon choisi au hasard un bras"""
if sum(self.values) == 0:
return int(random.random() * len(self.values))
else:
return self.values.index(max(self.values)) if random.random() > self.epsilon else int(random.random() * len(self.values))
def update(self, chosen_arm, reward):
""" Met à jour la liste self.values en fonction des rewards obtenus """
self.counts[chosen_arm] += 1
new_value = ((self.counts[chosen_arm] - 1) /float(self.counts[chosen_arm])) * self.values[chosen_arm] + (1 / float(self.counts[chosen_arm])) * reward
self.values[chosen_arm] = new_value
#Simulation part
def simulate_arm_bernoulli(proba):
return 1 if random.random() < proba else 0
def bernoulli_epsilongreedy(nb_try, epsilon, proba_arm_1, proba_arm_2):
print "Epsilon-greedy : cas 2 bras suivant une loi de bernoulli, arm1 : %s, arm2: %s" % (proba_arm_1, proba_arm_2)
algo = EpsilonGreedy(epsilon,[],[], 2)
i = 0
vector_arms_chosen = []
reward_vect = []
reward_cum = 0
while i < nb_try :
chosen_arm = algo.select_arm()
vector_arms_chosen.append(chosen_arm)
reward = simulate_arm_bernoulli(proba_arm_1) if chosen_arm == 0 else simulate_arm_bernoulli(proba_arm_2)
algo.update(chosen_arm, reward)
reward_cum = reward_cum + reward
if i != 0:
reward_vect.append(reward_cum / float(i))
else:
reward_vect.append(0)
i += 1
return reward_vect, algo.values, algo.counts, vector_arms_chosen
#features
iteration_nb = 1000
arm_1_probability = 0.4
arm_2_probability = 0.3
epsilon = 0.1
#Simulation
rewards_vect, values, count, arms_chosen = bernoulli_epsilongreedy(iteration_nb, epsilon, arm_1_probability, arm_2_probability)
offline_solution = [max(arm_1_probability, arm_2_probability) for x in range(iteration_nb)]
#PLOTTING
cum_sum_arm_2 = cumsum(arms_chosen) #arm_chosen = 1 if arm2 selected, else arm_chosen = 0
cum_sum_arm_1 = [ x - cum_sum_arm_2[x] for x in range(iteration_nb)]
plot(range(iteration_nb),cum_sum_arm_1, range(iteration_nb), cum_sum_arm_2);
title("Nombre de tirages de chaque bras");
legend(["arm1 Proba %s" % arm_1_probability, "arm2 p= %s" % arm_2_probability], loc="upper left");
figure();
#plot
plot(range(iteration_nb), offline_solution, 'k-', range(iteration_nb), rewards_vect, 'r--');
axis([0,iteration_nb,0.25,0.45]);
title("Gain moyen par tour");
legend(["Offline",r"$\epsilon$-greedy $\epsilon$ = %s" % epsilon], loc="lower right");
Dans les expérimentations appliquées, il n'est pas rare de voir un choix $\epsilon_t=\epsilon$ constant. Il n'est cependant pas difficile de rendre le regret négligeable devant $n$, en choisissant une suite $(\epsilon_t)$ décroissant (pas trop vite) vers $0$. Cependant, il n'est pas possible d'atteindre le regret asymptotiquement optimal suggéré par la borne de Lai et Robbins : cette politique paye donc sa grande simplicité par une performance moindre que ses concurrentes.
III.2 Politique UCB: Upper-Confidence Bound [10]¶
- Recommander une fois chaque document
- A chaque instant $t > m$ :
- Calculer la borne supérieure de confiance associée à chaque document
$$ \hat{x_i} + \sqrt{\frac{2\ln t}{t_i}} $$
- où $\hat{x_i}$ est la proportion de clics observée pour le document $i$
- et $t_i$ est le nombre de fois où le document $i$ a été recommandé
- Recommander le document avec la borne supérieure de confiance associ\'ee la plus forte
- Calculer la borne supérieure de confiance associée à chaque document
# Exemple UCB1 algorithm
class UCB1():
def __init__(self, counts = [], values = [], n_arms = 0):
self.counts = [0 for col in range(n_arms)]
self.values = [0.0 for col in range(n_arms)]
self.n_arms = n_arms
def select_arm(self):
""" Selectionne le bras avec la valeur de l'estimateur la plus haute"""
for arm in range(self.n_arms):
if self.counts[arm] == 0:
return arm
ucb_values = [0.0 for arm in range(self.n_arms)]
total_counts = sum(self.counts)
for arm in range(self.n_arms):
bonus = math.sqrt((2 * math.log(total_counts)) / float(self.counts[arm]))
ucb_values[arm] = self.values[arm] + bonus
value_max = max(ucb_values)
return ucb_values.index(value_max)
def update(self, chosen_arm, reward):
self.counts[chosen_arm] += 1
n = self.counts[chosen_arm]
value = self.values[chosen_arm]
new_value = ((n - 1) /float(n)) * value + (1 / float(n)) * reward
self.values[chosen_arm] = new_value
#Simulation part
def bernoulli_UCB1(nb_try, proba_arm_1, proba_arm_2):
print "UCB1 : cas 2 arms, suivant une loi de bernoulli, arm1 : %s, arm2: %s" % (proba_arm_1, proba_arm_2)
vector_arms_chosen = []
reward_vect = []
reward_cum = 0
algo = UCB1([],[], 2)
i = 0
while i < nb_try :
chosen_arm = algo.select_arm()
vector_arms_chosen.append(chosen_arm)
if chosen_arm == 0 :
reward = 1 if random.random() < proba_arm_1 else 0
else:
reward = 1 if random.random() < proba_arm_2 else 0
algo.update(chosen_arm, reward)
reward_cum = reward_cum + reward
i += 1
reward_vect.append(reward_cum / float(i))
return reward_vect, algo.values, algo.counts, vector_arms_chosen
#features
iteration_nb = 100
arm_1_probability = 0.5
arm_2_probability = 0.2
#bandit algorithm
rewards_vect, values, count, arms_chosen = bernoulli_UCB1(iteration_nb, arm_1_probability, arm_2_probability)
offline_solution = [max(arm_1_probability, arm_2_probability) for x in range(iteration_nb)]
cum_sum_arm_2 = cumsum(arms_chosen) #arm_chosen = 1 if arm2 selected, else arm_chosen = 0
cum_sum_arm_1 = [x - cum_sum_arm_2[x] for x in range(iteration_nb)]
plot(range(iteration_nb),cum_sum_arm_1, range(iteration_nb), cum_sum_arm_2);
title("Nombre de tirages de chaque bras");
legend(["arm1 Proba %s" % arm_1_probability, "arm2 Proba %s" % arm_2_probability], loc="upper left");
figure();
#plot
plot(range(iteration_nb), offline_solution, 'k-', range(iteration_nb), rewards_vect, 'r--');
title("Gain moyen par tour");
legend(["Offline","UCB1"], loc="lower right");
Il est prouvé dans [10] une borne de regret logarithmique (non-asymptotique). Toutefois, l'algorithme ci-dessus a un comportement sous-optimal qui peut s'avérer assez décevant dans le cas (fréquent en recommandation) où les récompenses moyennes sont toutes très faibles (cela se conçoit bien : la borne de Hoeffding est alors très pessimiste).
Heureusement, l'analyse peut être significativement renforcée, et [11] présente une variante pour laquelle une borne non-asymptotique de regret est montrée d'où peut être déduite l'optimalité au sens de la borne de Lai et Robbins. Le calcul de la borne supérieure de confiance est un peu plus complexe, mais le gain de performance n'est pas seulement théorique.
Les méthodes de type UCB présentent donc de grandes qualités ; elles posent toutefois des difficultés dans les modèles plus complexes (par exemple, dans le cas où les récompenses dépendent de façon non triviale de covariables) où il devient difficile de construire des intervalles de confiance précis avec les bonnes garanties non asymptotiques.
III.3 Politique EXP3: Exponential Weightsfor Exploration and Exploitation [2,5]¶
Plusieurs variantes ont été envisagées, la plus simple consiste à
- donner un poids initial $w^t_a=1$ à chaque action $a\in\{1,\dots,K\}$;
- tirer, au temps $t$, l'action $A_t=a$ avec une probabilité $p_t(a)$ proportionnelle à son poids $w_a^t$;
- une fois obervée la récompense $X_t$, mettre à jour le poids de l'action $A_t$ en le multipliant par $\exp(-\eta_t X_t/p_t(a))$, où $\eta_t$ est un paramètre de l'algorithme.
# Exemple Exp3 algorithm
class Exp3():
def __init__(self, counts = [], values = [], n_arms = 0):
self.n_arms = n_arms
self.counts = [0 for col in range(n_arms)]
self.G = [0 for col in range(n_arms)]
init_proba = float(1/float(n_arms))
self.weights = [1 for col in range(n_arms)]
self.values = values
self.t = 0
def select_arm(self, eta):
def tirage_aleatoire_avec_proba(proba_vect):
valeur_test = random.uniform(0, 1)
arm_chosen = -1
i = 0
sum_partiel = 0
while i <= len(proba_vect) and arm_chosen == -1 :
sum_partiel += (proba_vect[i])
if sum_partiel > valeur_test :
arm_chosen = i
i += 1
return arm_chosen
self.recalcul_proba = False
self.proba_vect = [0 for col in range(self.n_arms)]
#####################################
#ALGO CALCUL DU Pi
max_G = max(self.G)
sum_exp_eta_x_Gjt_max_G = 0
self.t += 1
for i in range(len(self.G)):
sum_exp_eta_x_Gjt_max_G += math.exp(eta*(self.G[i] - max_G))
for i in range(len(self.proba_vect)):
self.proba_vect[i] = math.exp(eta*(self.G[i] - max_G)) / float(sum_exp_eta_x_Gjt_max_G)
######################################
arm_chosen = tirage_aleatoire_avec_proba(self.proba_vect)
return arm_chosen
def update(self, chosen_arm, reward):
self.counts[chosen_arm] += 1
if not (self.recalcul_proba):
if self.counts[chosen_arm] != 1:
if self.proba_vect[chosen_arm] != 0:
if self.proba_vect[chosen_arm] < 0.01: #Pour eviter les problemes de limite de calcul
self.G[chosen_arm] = float(self.G[chosen_arm]) + (float(reward)/0.01)
else :
self.G[chosen_arm] = float(self.G[chosen_arm]) + (float(reward)/float(self.proba_vect[chosen_arm]))
else:
self.G[chosen_arm] = reward
else :
if self.counts[chosen_arm] != 1:
if self.proba_vect[chosen_arm] != 0:
if self.proba_vect[chosen_arm] < 0.01:
self.G[chosen_arm] = float(self.G[chosen_arm]) + (float(reward)/0.01)
else :
self.G[chosen_arm] = float(self.G[chosen_arm]) + (float(reward)/float(self.proba_vect_2[chosen_arm]))
else:
self.G[chosen_arm] = reward
#Simulation part
def simulate_arm_bernoulli(proba):
return 1 if random.random() < proba else 0
def bernoulli_exp3(nb_try, proba_arm_1, proba_arm_2, eta):
print "exp3 : cas 2 bras suivant une loi de bernoulli, arm1 : %s, arm2: %s" % (proba_arm_1, proba_arm_2)
algo = Exp3([],[], 2)
i = 0
vector_arms_chosen = []
reward_vect = []
reward_cum = 0
while i < nb_try :
chosen_arm = algo.select_arm(eta)
vector_arms_chosen.append(chosen_arm)
if chosen_arm == 0 :
reward = simulate_arm_bernoulli(proba_arm_1)
else:
reward = simulate_arm_bernoulli(proba_arm_2)
algo.update(chosen_arm, reward)
reward_cum = reward_cum + reward
i += 1
reward_vect.append(reward_cum / float(i))
return reward_vect, algo.values, algo.counts, vector_arms_chosen
#features
iteration_nb = 1000
arm_1_probability = 0.4
arm_2_probability = 0.3
eta= 0.05
#bandit algorithm
rewards_vect, values, count, arms_chosen = bernoulli_exp3(iteration_nb, arm_1_probability, arm_2_probability, eta)
#Offline solution
best_arm = [max(arm_1_probability, arm_2_probability) for x in range(iteration_nb)]
cum_sum_arm_2 = cumsum(arms_chosen) #arm_chosen = 1 if arm2 selected, else arm_chosen = 0
cum_sum_arm_1 = [ x - cum_sum_arm_2[x] for x in range(iteration_nb)]
plot(range(iteration_nb),cum_sum_arm_1, range(iteration_nb), cum_sum_arm_2);
title("Nombre de tirages de chaque bras");
legend(["arm1 Proba %s" % arm_1_probability, "arm2 Proba %s" % arm_2_probability], loc="upper left");
figure();
#plot
plot(range(iteration_nb), best_arm, 'k-', range(iteration_nb), rewards_vect, 'r--');
title("Gain moyen par tour");
legend(["Offline","UCB1"], loc="lower right");
Dans le cas des bandits bornés entre $0$ et $1$, un choix adéquat pour le paramètre est $\eta_t = \sqrt{\log(K)/(Kt)}$. Pour ce choix, on arrive à contrôler \emph{uniformément} le regret~: $R_n \leq 2\sqrt{nK\log(K)}$ (voir [2]).
Cette borne de regret peut sembler décevante en regard des taux logarithmiques obtenus pour UCB, mais il convient de noter qu'il s'agit de bornes uniformes qui ne font pas intervenir les récompenses moyennes du problème considéré (et on peut prouver que, pour de telles bornes uniformes, on ne peut pas faire mieux). En outre, cette borne est en fait vraie au sens des séquences individuelles, ce qui est beaucoup plus fort (en particulier, elle ne nécessite pas de supposer que les récompenses sont i.i.d. conditionnellement aux actions).
On pourra retenir que les algorithmes softmax sont moins performants mais plus robustes. Noter qu'il est en partie possible de combiner le "meilleur des deux mondes" (cf. par exemple [11]).
IV. Evaluation d'un système de recommandation : données Jester et MovieLens¶
Nous utilisons le cadre expérimental défini par Kohli et al. [12]. Les expérimentations font appel aux jeux de données MovieLens-100 et Jester.
IV.1 Jeu de données MovieLens¶
MovieLens-100 contient 943 utilisateurs qui ont noté 100 films. Les notes sont comprises entre 1 (mauvais) et 5 (bon) (si un film n’est pas noté par un utilisateur, la note minimale lui est affectée). Pour traduire les notes en actions utilisateurs, Kohli et al. (2013) ont choisi de fixer un seuil de pertinence. Dans leurs expérimentations, deux valeurs ont été utilisées : 2 et 4. Lorsque le seuil est 4, tous les films qui ont une note strictement supérieure à 4 sont considérés comme pertinents, c’est-à-dire que l’utilisateur les a apprécié. La même logique est suivie pour le seuil de valeur 2.
def get_first_100_docs():
"""Récupère les 100 premiers films du jeu u.data"""
first_100_docs = []
with open(r"Datasets/ml_100K/u.data") as f:
for line in f:
line = re.sub("\n", "", line)
line_tab = re.split("\t", line)
if line_tab[1] not in first_100_docs and len(first_100_docs) < 100 :
first_100_docs.append(line_tab[1])
return first_100_docs
def replace_empty_cells_by_worst_rate():
first_100_docs = get_first_100_docs()
list_users = []
hashtable_docs_corresponding = {}
nb_docs = len(first_100_docs)
for i, doc in enumerate(first_100_docs):
hashtable_docs_corresponding[doc] = i
rates_hashtable = {}
with open(r"lib/movielens100.data") as f:
for line in f:
line = re.sub("\n", "", line)
current_user, current_doc, rate, timestamp = re.split("\t", line)
if current_user not in rates_hashtable.keys(): #si pas de données sur cet utilisateur, initialisation d'un tableau de hachage contenant les notes par documents
rates_hashtable[current_user] = {}
for doc in first_100_docs:
rates_hashtable[current_user][hashtable_docs_corresponding[doc]] = 0.0
rates_hashtable[current_user][hashtable_docs_corresponding[current_doc]] = float(rate)
list_users.append(current_user)
else:
rates_hashtable[current_user][hashtable_docs_corresponding[current_doc]] = float(rate)
return rates_hashtable, list_users, nb_docs
rates_hashtable, list_users, nb_docs = replace_empty_cells_by_worst_rate()
print nb_docs
IV.2 Jeu de données Jester¶
Jester contient 25000 utilisateurs qui ont noté 100 blagues. Les notes sont comprises entre -10 (pas drôle) et 10 (très drôle). Kohli et al. (2013) ont choisi de fixer le seuil de pertinence à 7 comme seuil à partir duquel les blagues recommandées sont considérées comme pertinentes.
import re
def import_jester_collection():
user_id = 0
list_users = []
nb_docs = 100
rates_hashtable = {}
with open(r"Datasets/Jester/jester-data-1.csv") as f:
for line in f:
list_users.append(user_id)
rates_hashtable[user_id] = {}
line = re.sub("\n","",line)
line = re.split(",", line)
line = line[1:101] # Conserve uniquement les 100 blagues les plus notées
for i in range(100):
if line[i] == "99.00":
line[i] = "-10.00"
rates_hashtable[user_id][i] = float(line[i])
user_id += 1
return rates_hashtable, list_users, nb_docs
rates_hashtable, list_users, nb_docs = import_jester_collection()
print nb_docs
V. Bandits à actions multiples : approche RBA¶
L’approche RBA (Algorithme 1) a été développée par Radlinski et al. [13] et nécessite l’utilisation en parallèle d'autant d'instances d’un algorithme de bandit à tirages simples qu'il y a de recommandations à faire à chaque instant. À chaque instant t, les m objets choisis par les m instances d’algorithme de bandit sont recommandés à l’utilisateur. L’information de chaque instance est mise à jour de la manière suivante : l’instance correspondant au premier objet cliqué obtient une récompense de 1, tandis que tous les autres obtiennent une récompense de 0. De cette manière, la première instance tend à recommander l’objet avec le taux de clics le plus haut. La deuxième instance peut recevoir une récompense de 1 uniquement si le premier objet n’est pas cliqué. Elle tend ainsi à recommander l’objet avec le taux de clics le plus haut quand l’objet avec le taux de clics le plus haut n’est pas cliqué. Et ainsi de suite pour les instances suivantes.
Algorithme 1 : Ranked Bandits Algorithm
BTS(i): instance d’un algorithme de bandit à tirages simples pour la recommandation en position i
Pour t = 1, . . . , T faire
Pour i = 1, . . . , nb_documents_a_recommander faire
document(i) ← SélectionnerObjet(BTS(i), K)
si document(i) ∈ {document(1), . . . , document(i−1)} alors
document(i) ← choix arbitraire parmi les documents non sélectionnés
fin
fin
A(t) ← ∪ a(i)
Recommander A(t) à l’utilisateur, récupérer le retour utilisateur X(t)
Pour i = 1, . . . , m faire
Retour utilisateur : z(i) = 1 si le document(i) est le premier cliqué, 0 sinon
Mise à jour de l'estimateur de la pertinence du document(i) pour BTS(i) en fonction du retour z(i)
fin
fin import math
import random
import time
# some elements of the code
class RBA():
def __init__(self, nb_ranks,algorithm):
self.nb_ranks = nb_ranks
list_algorithms = ["UCB1","EpsilonGreedy","Exp3"]
if algorithm not in list_algorithms:
print 'Les algorithmes disponibles pour le IBA sont : %s' % list_algorithms
quit()
self.algorithm = algorithm
def initialize(self, nb_arms):
self.nb_arms = nb_arms
self.MBA_ranks = []
for i in range(self.nb_ranks):
if self.algorithm == "UCB1":
self.MBA_ranks.append(UCB1([], [], self.nb_arms))
if self.algorithm == "EpsilonGreedy":
self.MBA_ranks.append(EpsilonGreedy(0.05, [], [], self.nb_arms))
if self.algorithm == "Exp3":
self.MBA_ranks.append(Exp3([], [], self.nb_arms))
def select_arms(self, eta = 0):
arms_chosen = []
if self.algorithm == "Exp3":
for i in range(self.nb_ranks):
arm_chosen = self.MBA_ranks[i].select_arm(eta)
arms_chosen.append(arm_chosen)
else:
for i in range(self.nb_ranks):
arm_chosen = self.MBA_ranks[i].select_arm()
arms_chosen.append(arm_chosen)
return arms_chosen
def update_arms(self, arms_chosen, rewards):
#print arms_chosen
#print rewards
for i in range(len(arms_chosen)) :
#print "1 : %s" % self.MBA_ranks[i].values
#print "%s, %s"% (arms_chosen[i], rewards[i])
self.MBA_ranks[i].update(arms_chosen[i], rewards[i])
#print "2 : %s" % self.MBA_ranks[i].values
#Méthode responsable de l'allocation des rcompenses
def get_rewards(arms_chosen, hashtable_users_data, user_chosen, threshold):
hashtable_pertinence = hashtable_users_data[user_chosen]
rewards = []
first_clic_found = False
for arm in arms_chosen :
if hashtable_pertinence[arm] > threshold and not first_clic_found :
rewards.append(1)
first_clic_found = True
else :
rewards.append(0)
return rewards
# Utilisation de l'algorithme RBA sur nos collections
def use_RBA(threshold, hashtable_users_data, list_users, bandit_algorithm, nb_docs):
RBA_item = RBA(5, bandit_algorithm)
RBA_item.initialize(nb_docs)
cum_rewards = []
rewards_vect = [0 for i in range(100)]
for i in range(100000):
user_chosen = list_users[int(random.random()*len(list_users))]
arms_chosen = RBA_item.select_arms(eta)
rewards = get_rewards(arms_chosen, hashtable_users_data, user_chosen, threshold)
RBA_item.update_arms(arms_chosen, rewards)
if 1 in rewards : #non abandonment
cum_rewards.append(1)
else:
cum_rewards.append(0)
if i % 1000 == 0 and i != 0 :
rewards_vect[i/1000] = (sum(cum_rewards) / float(1000))
cum_rewards = []
return rewards_vect
# Permet de représenter l'évolution de l'abandon en fonction du temps passé
def tracer_graphique(threshold, rewards_tab, legend_list):
"Graphique"
fig = pyplot.figure()
ax = fig.add_subplot(1,1,1)
style = ['k', 'c', 'b', 'b-.', 'b--', 'r', 'r-.', 'r--', 'g', 'g-.', 'g--', 'y', 'y-.', 'y--', 'm', "m-.", "m--"]
for i, rewards in enumerate(rewards_tab) :
ax.plot(range(0, 100000, 1000), rewards, style[i])
ax.set_xscale('log')
ax.xaxis.set_tick_params(size=5)
ax.xaxis.set_ticks_position('bottom')
ax.yaxis.set_ticks_position('left')
ax.set_xticks([1000, 5000, 10000, 50000, 100000])
ax.set_xticklabels(['1000', '5000', '10000', '50000', '100000'])
ax.legend(legend_list, loc="lower right")
xlabel("Time Steps")
ylabel("Fraction of Relevant Sets (1 - Abandonment)")
show()
##################
#### FEATURES ####
##################
threshold = 4 #2 ou 4 pour MovieLens, 7 pour Jester
nb_try = 1
collection = "MovieLens"
bandit_subroutine = "EpsilonGreedy"
rewards_type = "1 - abandon"
eta= 0.05
#Importation des données
if collection == "MovieLens":
hashtable_users_data, list_users, nb_docs = replace_empty_cells_by_worst_rate()
elif collection == "Jester":
hashtable_users_data, list_users, nb_docs = import_jester_collection()
else:
print "Unknown collection\n"
error_message()
# Utilisation de l'algorithme RBA
rewards_vect = use_RBA(threshold, hashtable_users_data, list_users, bandit_subroutine, nb_docs)
#Solutions optimales (en fonction du seuil et de la collection)
if threshold == 4 :
rewards_vect_max = [529/float(len(list_users)) for col in range(100)]
rewards_vect_max_no_diversity = [524/float(len(list_users)) for col in range(100)]
elif threshold == 2 :
rewards_vect_max = [866/float(len(list_users)) for col in range(100)]
rewards_vect_max_no_diversity = [825/float(len(list_users)) for col in range(100)]
else :
rewards_vect_max = [12981/float(len(list_users)) for col in range(100)]
rewards_vect_max_no_diversity = [12672/float(len(list_users)) for col in range(100)]
#Graphiques
try:
tracer_graphique(threshold, [rewards_vect_max, rewards_vect_max_no_diversity, rewards_vect], [" offline diversity", "offline no diversity", "RBA E-greedy", "IBA E-greedy"])
except:
print "impossible de tracer le graphique"
print [round(x,2) for x in rewards_vect]
Quelques références¶
[1] Thompson, W. (1933), On the likelihood that one unknown probability exceeds another in view of the evidence of two sample {Bulletin of the {A}merican mathematics society}, 25:285--294.
[2] Bubeck, S. and Cesa-Bianchi, N. (2012), Regret analysis of stochastic and nonstochastic multi-armed bandit problems, {Foundations and trends in machine learning}, 5(1):1--122.
[3] Hu, F. and Rosenberger, W.~F. (2006), {The theory of response-adaptive randomization in clinical trials}, Wiley Series in Probability and Statistics. Wiley-Interscience [John Wiley & Sons], Hoboken, NJ.
[4] Jennison, C. and Turnbull, B.~W. (2000), {Group sequential methods with applications to clinical trials}, Chapman & Hall/CRC, Boca Raton, FL.
[5] Cesa-Bianchi, N. and Lugosi, G. (2006), {Prediction, Learning, and Games}, Cambridge University Press.
[6] Lai, T. and Robbins, H. (1985), Asymptotically efficient adaptive allocation rules, {Advances in Applied Mathematics}, 6(1):4--22.
[7] Kaufmann, E. and Cappé, O. and Garivier, A. (2015), Complexity of Best-Arm Identification in Multi-Armed Bandits, {Journal of Machine Learning Research}.
[8] Kaufmann, E. and Korda, N. and Munos, R. (2012), Thompson Sampling : an Asymptotically Optimal Finite-Time Analysis, { Algorithmic Learning Theory (ALT)}.
[9] Sutton, R.S. and Barto, A.G. (1998), {Reinforcement learning: An introduction}, The MIT press.
[10] Auer, P. and Cesa-Bianchi, N. and Fischer, P. (2002), Finite-time analysis of the multiarmed bandit problem, {Machine Learning}, 47(2):235--256.
[11] Bubeck, S. and Slivkins, A. (2012), The best of both worlds: stochastic and adversarial bandits, {Conference On Learning Theory (COLT)}.
[12] Kohli, P. and Salek, M. and Stoddard, G. (2013), A Fast Bandit Algorithm for Recommendation to Users With Heterogeneous Tastes, 27th AAAI Conference on Artificial Intellignece, 1135--1141.
[13] Radlinski, F. and Kleinberg, R. and Joachims, T. (2008) Learning Diverse Rankings with Multi-Armed Bandits, {25th International Conference on Machine Learning}, 784--791.