Février 2018
Volume 33, numéro 2
Cet article a fait l'objet d'une traduction automatique.
Série de tests - Échantillonnage Thompson utilisant C#
Par James McCaffrey
.jpg "James McCaffrey")
Thompson l’échantillonnage est un algorithme qui peut être utilisé pour trouver une solution à un problème bandit armées multiples, un terme dérivant du fait que les machines à sous jeux sont couramment appelées « bandits one-armed. »
Supposons que vous êtes debout devant les trois ordinateurs de l’emplacement. Lorsque vous retirez l’arm sur l’un des ordinateurs, il sera vous payez zéro dollars ou un dollar en fonction d’une distribution de probabilité d’inconnu. Par exemple, l’ordinateur peut payer avec une probabilité moyenne de 0,5, donc si vous avez extrait le handle sur cet ordinateur 100 fois, vous attendez à payer de dollars environ 50 fois zéro et un dollar environ 50 fois.
Votre objectif est d’identifier l’ordinateur meilleures, aussi efficacement que possible. Le problème vient d’être décrit est un exemple d’un problème de bandit Bernoulli, car le résultat est 0 ou 1. Il existe des autres types de problèmes de bandit. Par exemple, si une valeur, généralement entre zéro et un dollar (par exemple, 55.0 cents), en fonction d’une distribution gaussienne en forme de cloche, chaque ordinateur payées vous aurait un problème bandit gaussienne. Cet article traite uniquement le problème bandit de Bernoulli.
Il existe plusieurs algorithmes qui peuvent être utilisés pour tenter de trouver le meilleur ordinateur. Supposons que vous êtes limité à un total de 100 extrait sur trois ordinateurs. Vous pouvez essayer 10 extrait sur chaque ordinateur, le suivi de chaque ordinateur degré. Vous pouvez ensuite utiliser votre extrait de 70 restantes sur l’un ordinateur payée le plus d’argent au moment de 30-extraction Explorer. Le danger avec cette approche est que vous pouvez identifier de manière incorrecte le meilleur ordinateur. Et si vous utilisez plusieurs extractions pendant la phase d’Explorer, vous n’avez pas de gauche pendant la phase d’exploitation.
Thompson l’échantillonnage est un algorithme intelligent qui s’ajuste en permanence les probabilités estimées de paiement de chaque ordinateur. Comme vous le verrez bientôt, la clé à Thompson d’échantillonnage pour un problème de bandit Bernoulli est la distribution bêta mathématique.
Il est improbable que vous êtes invité par votre direction pour analyser les ordinateurs de l’emplacement, mais bandit armées plusieurs problèmes apparaissent dans de nombreux scénarios importants, la pratiques. Par exemple, supposons que vous travaillez pour un fabricant médicament. Vous venez de créer quatre stupéfiants expérimentales nouvelle pour cancer et que vous souhaitez établir lequel des quatre stupéfiants est plus efficace, avec un minimum de tests sur des sujets dynamiques. Ou peut-être que vous travaillez pour une société de commerce électronique et vous souhaitez déterminer parmi plusieurs nouvelles campagnes de publicité est le plus de succès.
Une bonne solution pour voir où cet article est menée consiste à examiner le programme de démonstration dans Figure 1. La démonstration définit trois ordinateurs Bernoulli avec des probabilités de paiement de (0,3, 0,5, 0,7), respectivement. Dans un scénario non-demo, les probabilités sont inconnues, bien sûr. Vous êtes autorisé un total de 10 extrait. L’objectif est de déterminer le meilleur ordinateur (#3) et tirez sur sa poignée la plupart du temps.
.png "Démonstration d’échantillonnage Thompson")
Figure 1 Thompson d’échantillonnage démonstration
Dans la première version d’évaluation, vous supposez que les trois ordinateurs ont une probabilité de paiement de 0,5. La démonstration utilise la distribution bêta pour générer des trois probabilités en conséquence. Ces probabilités aléatoires sont (0.7711, 0.1660, 0.1090). Étant donné que la probabilité associée à la machine #1 est la plus élevée, son arm est extraite. Dans ce cas, l’ordinateur #1 ne payez pas.
Dans la deuxième version d’évaluation, en arrière-plan, la démonstration estime que le premier ordinateur a maintenant une probabilité de paiement est inférieure à 0,5. Échantillonnage de la version bêta est utilisé et cette fois les probabilités sont (0.6696, 0.2250, 0.7654), afin de l’ordinateur #3 est sélectionné et lu, et sa probabilité estimée de paiement est ajustée si l’ordinateur paie ou non.
Au fil du temps, car l’ordinateur #3 a la probabilité la plus élevée de paiement, elle gagne le plus souvent que les deux ordinateurs et chaque ordinateur temps #3 paie, la probabilité qu’il sera sélectionné augmente.
Après les essais de 10, #1 a été lu trois fois, payée qu’une seule fois pour la simulation devine sa probabilité true de paiement est d’environ 1/3 = 0,33. #2 a été lu trois fois, payée deux fois (estimé p = 2/3 =.6667. #3 a été lu quatre fois, payée à trois reprises (estimé p = 3/4 = 0,7500). Par conséquent, dans cet exemple, au moins, le meilleur ordinateur a été identifié et a été lu le plus souvent.
Cet article suppose que vous avez intermédiaires ou meilleures compétences de programmation, mais ne suppose pas que vous connaissez un peu Thompson d’échantillonnage ou les distributions bêta. Le programme de démonstration est codé à l’aide de c#, mais ne doit pas avoir trop de difficultés refactorisation du code à un autre langage, tels que Visual Basic ou Python, si vous le souhaitez. Le code du programme de démonstration est présenté dans son intégralité dans cet article et est également disponible dans le téléchargement de fichier associé.
Présentation de la Distribution bêta
Thompson d’échantillonnage pour un problème de bandit Bernoulli dépend de la distribution bêta. Pour comprendre la distribution bêta vous devez comprendre les distributions de probabilité en général. Il existe de nombreux types de distributions de probabilités, chacun d'entre eux ayant des variations qui dépendent d’un ou deux paramètres.
Vous pouvez être familiarisé avec la distribution uniforme, qui possède deux paramètres, appelée min et max, ou parfois simplement un et b. Une distribution uniforme avec min = 0,0 et max = 1.0 retourne une valeur de p entre 0,0 et 1,0 où chaque valeur est également probable. Par conséquent, si vous échantillonné 1 000 fois à partir de la distribution uniforme, tout relatifs à 100 p-valeurs comprises entre 0.00 et 0,10, sur 100 p-valeurs comprises entre 0,10 et 0,20 et ainsi de suite, sur les valeurs de 100 p entre 0,90 et 1.00. Si vous graphiquement les résultats, vous voyez un graphique à barres avec des barres de 10, sur la même hauteur.
Vous pourrez également être familiarisé avec la distribution normale (également appelée gaussienne). La distribution normale est aussi caractérisée par deux paramètres, la moyenne et l’écart type. Si vous échantillonné 1 000 fois à partir de la distribution normale par la moyenne = 0,0 et écart = 1.0, vous souhaitez obtenir sur les valeurs z 380 entre -0,5 et + 0,5 ; à propos des valeurs z 240 entre + 0,5 et plus de 1,5 (et également entre -0,5 et-1.5) ; à propos des valeurs z 60 entre plus de 1,5 et +2.5 (et également entre-1.5 et -2,5) ; et 10 valeurs z supérieures à +2.5 (et 10 -2,5 inférieure). Si vous graphiquement les résultats que vous verriez un graphique à barres en forme de cloche.
La distribution bêta est caractérisée par deux paramètres, généralement appelé alpha et bêta, ou parfois simplement un et b. Notez le risque de confusion entre « bêta » représentant la distribution tout entière et « bêta », représentant les secondes des paramètres de distribution de deux.
Si vous échantillonnez une distribution bêta avec une = 1 et b = 1, vous obtenez le même que la distribution uniforme avec moyenne = 0,5 des résultats. Si un et b ont des valeurs différentes, lorsque vous échantillonnez à partir de la distribution bêta vous p-valeurs moyenne pour obtenez une / (a + b). Par exemple, si un = 3 et b = 1 et vous exemple à plusieurs reprises, vous obtiendrez p-valeurs comprise entre 0,0 et 1,0, mais la moyenne des valeurs p sera 3 / (3 + 1) = 0,75. Cela signifie que les valeurs p entre 0,90 et 1.00 seront les plus courants ; p-valeurs comprises entre 0,80 et 0,90 sera un peu moins courants. et ainsi de suite jusqu'à très peu de valeurs p entre 0,00 et 0,10. Graphique de Figure 2 montre les résultats de 10 000 exemples à partir de la distribution bêta avec une = 3 et b = 1.
.png "Échantillonnage de la Distribution Beta(3,1)")
Échantillonnage de la figure 2 à partir de la Distribution Beta(3,1)
La connexion entre la distribution bêta et d’un problème de bandit Bernoulli est très subtile. En bref, la distribution bêta est le conjugué préalable pour la fonction de probabilité de Bernoulli. Bien que le calcul sous-jacent est très profond, implémentation de l’algorithme Thompson est Heureusement, simple (relativement).
Le programme de démonstration
Pour créer le programme de démonstration, je lancer Visual Studio et créé une nouvelle application console nommée Thompson. La démonstration n’a aucune dépendance significative de .NET Framework, par conséquent, n’importe quelle version de Visual Studio est correctement. Une fois le code du modèle chargé dans la fenêtre d’éditeur, je cliqué sur le fichier Program.cs renommé en la ThompsonProgram.cs légèrement plus descriptifs et autorisé Visual Studio afin de renommer automatiquement la classe Program pour moi. En haut du code du modèle, j’ai supprimé toutes les références aux espaces de noms inutiles, en laissant uniquement la référence à l’espace de noms système niveau supérieur.
La structure générale du programme, avec quelques modifications mineures pour économiser l’espace, est présentée dans Figure 3. La logique de contrôle est dans la méthode Main. Échantillonnage de la distribution bêta est implémentée à l’aide de la classe BetaSampler défini par le programme. Vérification de toutes les erreurs normalement est supprimé pour économiser de l’espace.
Structure de programme de démonstration figure 3 Thompson d’échantillonnage
using System;
namespace Thompson
{
class ThompsonProgram
{
static void Main(string[] args)
{
Console.WriteLine("Begin Thompson sampling demo");
int N = 3;
double[] means = new double[] { 0.3, 0.5, 0.7 };
double[] probs = new double[N];
int[] S = new int[N];
int[] F = new int[N];
Random rnd = new Random(4);
BetaSampler bs = new BetaSampler(2);
for (int trial = 0; trial < 10; ++trial)
{
Console.WriteLine("Trial " + trial);
for (int i = 0; i < N; ++i)
probs[i] = bs.Sample(S[i] + 1.0, F[i] + 1.0);
Console.Write("sampling probs = ");
for (int i= 0; i < N; ++i)
Console.Write(probs[i].ToString("F4") + " ");
Console.WriteLine("");
int machine = 0;
double highProb = 0.0;
for (int i = 0; i < N; ++i) {
if (probs[i] > highProb) {
highProb = probs[i];
machine = i;
}
}
Console.Write("Playing machine " + machine);
double p = rnd.NextDouble();
if (p < means[machine]) {
Console.WriteLine(" -- win");
++S[machine];
}
else {
Console.WriteLine(" -- lose");
++F[machine];
}
}
Console.WriteLine("Final estimates of means: ");
for (int i = 0; i < N; ++i) {
double u = (S[i] * 1.0) / (S[i] + F[i]);
Console.WriteLine(u.ToString("F4") + " ");
}
Console.WriteLine("Number times machine played:");
for (int i = 0; i < N; ++i) {
int ct = S[i] + F[i];
Console.WriteLine(ct + " ");
}
Console.WriteLine("End demo ");
Console.ReadLine();
}
}
public class BetaSampler
{
// ...
}
}
La démonstration commence en configurant des quatre tableaux :
Console.WriteLine("Begin Thompson sampling demo");
int N = 3;
double[] means = new double[] { 0.3, 0.5, 0.7 };
double[] probs = new double[N];
int[] S = new int[N];
int[] F = new int[N];
La démonstration utilise trois ordinateurs, mais Thompson échantillonnage peut fonctionner avec n’importe quel nombre d’ordinateurs. Les probabilités moyennes de paiements sont codées en dur. Les probabilités moyennes sont proches entre elles, la plus difficile le problème. Le tableau nommé probs contient les probabilités à partir d’un échantillonnage de la distribution bêta, qui déterminent quel ordinateur à lire. Les tableaux nommés S (« réussite ») et F (« échec ») contiennent le nombre cumulatif de fois où chaque ordinateur payée et n’a pas été paiement lors de la lecture.
La démonstration utilise deux objets de génération de nombres aléatoires :
Random rnd = new Random(4);
BetaSampler bs = new BetaSampler(2);
L’objet rnd est utilisée pour déterminer si un wins de l’ordinateur sélectionné ou perd. Notez que j’utiliser le termes du contrat win et perdre, paiement et paie pas et de réussite et d’échec, indifféremment. L’objet bs sert à échantillonner la distribution bêta. Les valeurs de départ utilisées, 2 et 4, ont été spécifiés uniquement, car elles fournies à une exécution de démonstration représentative.
La boucle principale simulation commence :
for (int trial = 0; trial < 10; ++trial) {
Console.WriteLine("Trial " + trial);
for (int i = 0; i < N; ++i)
probs[i] = bs.Sample(S[i] + 1.0, F[i] + 1.0);
...
Vous souhaiterez peut-être définir le nombre d’essais vers un grand nombre, tels que 1 000, pour observer la rapidité avec laquelle Thompson d’échantillonnage de zéros à droite dans sur une machine optimale. La clé pour la démonstration entière est l’appel à la méthode d’échantillonnage. Le nombre de réussites et les échecs est passé à la méthode. Une constante 1.0 est ajoutée en tant que quelque chose compliqué, car la distribution bêta nécessite l’une et les paramètres de b est supérieure à 0. Si vous avez une connaissance préalable des probabilités de paiement les ordinateurs, vous pourriez ajuster la constante pour refléter ces informations.
Après avoir affiché les probabilités d’échantillonnage mis à jour, la démonstration sélectionne l’ordinateur avec le plus de chances d’échantillonnage :
int machine = 0;
double highProb = 0.0;
for (int i = 0; i < N; ++i) {
if (probs[i] > highProb) {
highProb = probs[i];
machine = i;
}
}
Étant donné que les probabilités sont échantillonnées, même si un ordinateur possède zéro wins et nombreuses défaillances, il peut néanmoins être sélectionné pour la lecture. Ce mécanisme améliore les capacités d’exploration de l’algorithme.
La boucle principale d’itération se termine par la lecture de l’ordinateur sélectionné :
...
Console.Write("Playing machine " + machine);
double p = rnd.NextDouble();
if (p < means[machine]) {
Console.WriteLine("win"); ++S[machine];
}
else {
Console.WriteLine("lose"); ++F[machine];
}
}
La méthode NextDouble retourne une valeur aléatoire de manière uniforme entre 0,0 et 1,0 et est utilisée pour implémenter un processus de Bernoulli. La démonstration se termine en affichant les probabilités estimées de paiement pour chaque ordinateur (ne pas déranger à vérifier pour possible de division par zéro) et le nombre de lectures effectuées sur chaque ordinateur.
Implémentation de la Distribution bêta
Quelque peu étonnamment, à ma connaissance du .NET Framework n’est une méthode de bibliothèque exemple à partir de la distribution bêta. Au lieu d’effectuer une dépendance sur une bibliothèque externe, j’ai décidé de mettre en œuvre une nouvelle. Il existe de nombreux algorithmes pour générer un exemple de la version bêta. J’ai utilisé l’algorithme « BA », développé par R. C. Cheng H. en 1978. L’ensemble du code est présenté dans Figure 4.
Figure 4 défini par le programme de bêta Distribution échantillonneur
public class BetaSampler
{
public Random rnd;
public BetaSampler(int seed)
{
this.rnd = new Random(seed);
}
public double Sample(double a, double b)
{
double alpha = a + b;
double beta = 0.0;
double u1, u2, w, v = 0.0;
if (Math.Min(a, b) <= 1.0)
beta = Math.Max(1 / a, 1 / b);
else
beta = Math.Sqrt((alpha - 2.0) /
(2 * a * b - alpha));
double gamma = a + 1 / beta;
while (true) {
u1 = this.rnd.NextDouble();
u2 = this.rnd.NextDouble();
v = beta * Math.Log(u1 / (1 - u1));
w = a * Math.Exp(v);
double tmp = Math.Log(alpha / (b + w));
if (alpha * tmp + (gamma * v) - 1.3862944 >=
Math.Log(u1 * u1 * u2))
break;
}
double x = w / (b + w);
return x;
}
}
L’échantillonnage à partir de la distribution bêta est une rubrique fascinante à part entière. Une analyse rapide du code vous convaincre de quelques calculs intelligent, non une version d’évaluation est impliqué. L’implémentation suit le document de recherche source près : les variables de mêmes nom et ainsi de suite. Notez que la boucle infinie, ce qui est courante dans le pseudo-code de recherche, mais un no-no définie dans le code de production. Vous pouvez souhaiter ajouter une variable de compteur de boucle et de lever une exception si la valeur dépasse un seuil.
Pour résumer
Cet article et son code doivent vous fournir toutes les informations que vous devez faire des essais avec Thompson d’échantillonnage pour les problèmes de Bernoulli armées multiples. Il doit également permettre vous permettent d’Explorer les problèmes bandit avec d’autres types de fonctions de paiement. Par exemple, si vous avez des ordinateurs paiement selon une fonction de probabilité de Poisson, au lieu d’utiliser la distribution bêta vous serez exemples à partir de la distribution gamma, qui est le conjugué préalable de Poisson.
Le problème bandit armées multiples est un exemple de ce qu’on appelle renforcement d’apprentissage (RL). Dans l’apprentissage RL, au lieu de créer un système de prédiction à l’aide des données étiquetées a connu des réponses correctes, vous générez une prédiction modèle à la volée, à l’aide de la fonction de récompense quelconque. RL est à la pointe de la recherche d’apprentissage.
Récupération d’urgence. James McCaffreyfonctionne pour Microsoft Research à Redmond, Washington Il a travaillé sur plusieurs produits Microsoft, y compris Internet Explorer et Bing. Dr. McCaffrey peut être atteint à jamccaff@microsoft.com.
Grâce aux experts techniques Microsoft suivants ayant révisé cet article : Chris Lee, Ricky Loynd, Adith Swaminathan