---

Februar 2018

Band 33, Nummer 2

Test Run: Thompson Sampling mit C#

Von James McCaffrey

Thompson Sampling ist ein Algorithmus, der verwendet werden kann, um eine Lösung für ein mehrarmiges Banditenproblem zu finden, ein Begriff, der sich aus der Tatsache ableitet, dass Glücksspielautomaten informell „einarmige Banditen“ genannt werden.

Angenommen, Sie stehen vor drei Spielautomaten. Wenn Sie den Hebel an einem der Automaten ziehen, zahlt er Ihnen entweder null Dollar oder einen Dollar entsprechend einer Wahrscheinlichkeitsverteilung aus, die Ihnen unbekannt ist. Der Automat könnte z.B. mit einer mittleren Wahrscheinlichkeit von 0,5 auszahlen. Wenn Sie also den Hebel dieses Automaten 100 Mal ziehen würden, würden Sie erwarten, null Dollar ungefähr 50 Mal und einen Dollar ungefähr 50 Mal ausgezahlt zu bekommen.

Ihr Ziel ist es, den besten Automaten so effizient wie möglich zu identifizieren. Das soeben beschriebene Problem ist ein Beispiel für ein Bernoulli-Banditenproblem, da das Ergebnis entweder 0 oder 1 ist. Es gibt such andere Arten von Banditenproblemen. Wenn jeder Automat einen Wert (normalerweise zwischen null und einem Dollar, z.B. 55,0 Cent) entsprechend einer glockenförmigen Gauß-Verteilung auszahlen würde, würde ein Gauß'sches Prozessbanditenproblem vorliegen. Dieser Artikel behandelt nur das Bernoulli-Banditenproblem.

Es gibt mehrere Algorithmen, die zum Bestimmen des besten Automaten verwendet werden können. Angenommen, Sie sind auf insgesamt 100 Versuche bei den drei Automaten beschränkt. Sie könnten 10 Versuche pro Automat ausführen, um zu ermitteln, wie gut jeder Automat funktioniert. Dann könnten Sie Ihre verbleibenden 70 Versuche auf dem einen Automaten ausführen, der das meiste Geld während Ihrer Erkundungsphase mit 30 Versuchen ausgezahlt hat. Die Gefahr bei dieser Vorgehensweise besteht darin, dass Sie den besten Automaten fälschlicherweise identifizieren. Und wenn Sie während der Erkundungsphase viele Versuche ausführen, bleiben während der Nutzungsphase nicht mehr viele übrig.

Thompson Sampling ist ein ausgeklügelter Algorithmus, der kontinuierlich die geschätzten Wahrscheinlichkeiten der Auszahlungen der einzelnen Automaten anpasst. Wie Sie in Kürze sehen werden, ist der Schlüssel zum Thompson Sampling für ein Bernoulli-Banditenproblem die mathematische Betaverteilung.

Es ist unwahrscheinlich, dass Sie von Ihrem Vorgesetzten gebeten werden, Spielautomaten zu analysieren, aber mehrarmige Banditenprobleme treten in vielen wichtigen praktischen Szenarien auf. Angenommen, Sie arbeiten für einen Arzneimittelhersteller. Sie haben gerade vier neue experimentelle Medikamente gegen Krebs entwickelt und möchten herausfinden, welches der vier Medikamente am effektivsten ist, mit einem Minimum an Tests an lebenden Probanden. Oder vielleicht arbeiten Sie für ein E-Commerce-Unternehmen und möchten herausfinden, welche von mehreren neuen Werbekampagnen die erfolgreichste ist.  

Ich empfehle Ihnen, sich das Demoprogramm in Abbildung 1 anzusehen. Dort erfahren Sie, um was es bei diesem Artikel geht. Die Demo richtet drei Bernoulli-Automaten mit Auszahlungswahrscheinlichkeiten von (0,3, 0,5, 0,7) ein. In einem Nicht-Demoszenario sind Ihnen die Wahrscheinlichkeiten natürlich unbekannt. Es sind insgesamt 10 Versuche zulässig. Ziel ist es, den besten Automaten (Automat Nr. 3) zu ermitteln und dessen Hebel am häufigsten zu betätigen.

Abbildung 1: Thompson Sampling-Demo

Im ersten Versuch gehen Sie davon aus, dass alle drei Automaten eine Auszahlungswahrscheinlichkeit von 0,5 aufweisen. Die Demo verwendet die Betaverteilung, um drei Wahrscheinlichkeiten zu generieren, die auf dieser Annahme basieren. Diese Zufallswahrscheinlichkeiten sind (0,7711, 0,1660, 0,1090). Weil die Wahrscheinlichkeit, die Automat Nr. 1 zugeordnet ist, am höchsten ist, wird sein Hebel betätigt. In diesem Fall zahlt Automat Nr. 1 nicht aus.

Im zweiten Versuch glaubt die Demo hinter den Kulissen, dass der erste Automat nun eine Auszahlungswahrscheinlichkeit von weniger als 0,5 aufweist. Betasampling wird verwendet, und dieses Mal sind die Wahrscheinlichkeiten (0,6696, 0,2250, 0,7654), sodass Automat Nr. 3 ausgewählt und gespielt wird, und seine geschätzte Auszahlungswahrscheinlichkeit wird abhängig davon angepasst, ob der Automat auszahlt oder nicht.

Im Lauf der Zeit wird Automat Nr. 3 häufiger gewinnen als die anderen beiden Automaten, weil er die höchste Auszahlungswahrscheinlichkeit aufweist, und jedes Mal, wenn Automat Nr. 3 auszahlt, steigt die Wahrscheinlichkeit, dass er ausgewählt wird.

Nach den 10 Versuchen wurde Automat Nr. 1 drei Mal gespielt und zahlte nur ein Mal aus, sodass die Simulation die echte Wahrscheinlichkeit einer Auszahlung auf etwa 1/3 = 0,33 schätzt. Automat Nr. 2 wurde drei Mal gespielt und zahlte zwei Mal aus (geschätzt p = 2/3 = 0,6667). Automat Nr. 3 wurde vier Mal gespielt und zahlte drei Mal aus (geschätzt p = 3/4 = 0,7500). So wurde zumindest in diesem Beispiel der beste Automat identifiziert und am häufigsten gespielt.

Dieser Artikel geht davon aus, dass Sie über mittlere bis fortgeschrittene Programmierkenntnisse verfügen, er setzt aber nicht voraus, dass Sie mit Thompson Sampling oder Betaverteilungen vertraut sind. Das Demoprogramm wurde mit C# programmiert. Sie sollten ein Refactoring des Codes in eine andere Sprache (z.B. Visual Basic oder Python) jedoch relativ leicht ausführen können. Der Code für das Demoprogramm wird in diesem Artikel in seiner Gesamtheit vorgestellt und ist auch im begleitenden Dateidownload verfügbar.

Grundlagen der Betaverteilung

Thompson Sampling für ein Bernoulli-Banditenproblem hängt von der Betaverteilung ab. Um die Betaverteilung zu verstehen, müssen Sie Wahrscheinlichkeitsverteilungen im Allgemeinen verstehen. Es gibt viele Arten von Wahrscheinlichkeitsverteilungen, von denen jede Variationen aufweist, die von einem oder zwei Parametern abhängen.

Sie sind vielleicht mit der gleichmäßigen Verteilung vertraut, die zwei Parameter besitzt, die als „min“ und „max“ oder manchmal auch nur als „a“ und „b“ bezeichnet werden. Eine gleichmäßige Verteilung mit min = 0,0 und max = 1,0 ergibt einen p-Wert zwischen 0,0 und 1,0, wobei jeder Wert gleich wahrscheinlich ist. Wenn Sie bei einer gleichmäßigen Verteilung also 1.000 Versuche ausführen, erwarten Sie, dass Sie etwa 100 p-Werte zwischen 0,00 und 0,10, etwa 100 p-Werte zwischen 0,10 und 0,20 usw. und etwa 100 p-Werte zwischen 0,90 und 1,00 erhalten. Wenn Sie die Ergebnisse grafisch darstellen würden, würden Sie ein Balkendiagramm mit 10 Balken erhalten, die alle ungefähr die gleiche Höhe aufweisen.

Vielleicht sind Sie auch mit der Normalverteilung (auch als Gauß-Verteilung bezeichnet) vertraut. Die Normalverteilung wird auch durch zwei Parameter charakterisiert, den Mittelwert und die Standardabweichung. Wenn Sie 1.000 Versuche in der Normalverteilung mit dem Mittelwert = 0,0 und der Standardabweichung = 1,0 ausführen würden, könnten Sie etwa 380 z-Werte zwischen -0,5 und +0,5, etwa 240 z-Werte zwischen +0,5 und +1,5 (und auch zwischen -0,5 und -1,5), etwa 60 z-Werte zwischen +1,5 and +2,5 (und auch zwischen -1,5 und -2,5) und 10 z-Werte erwarten, die größer als +2,5 (und 10 Werte, die kleiner als -2,5) sind. Wenn Sie die Ergebnisse grafisch darstellen würden, würde sich ein glockenförmiges Balkendiagramm ergeben.

Die Betaverteilung wird durch zwei Parameter charakterisiert, die gewöhnlich „Alpha“ und „Beta“ genannt werden oder manchmal auch nur „a“ und „b“. Beachten Sie die mögliche Verwechslung zwischen „Beta“ für die gesamte Verteilung und „Beta“ für den zweiten der beiden Verteilungsparameter.

Wenn Sie aus einer Betaverteilung mit a = 1 und b = 1 testen, erhalten Sie genau die gleichen Ergebnisse wie bei der gleichmäßigen Verteilung mit dem Mittelwert = 0,5. Wenn „a“ und „b“ unterschiedliche Werte aufweisen, erhalten Sie bei einem Test aus der Betaverteilung p-Werte, die im Mittel a / (a+b) ergeben. Wenn z.B. a = 3 und b = 1 ist und Sie wiederholt testen, erhalten Sie p-Werte zwischen 0,0 und 1,0, aber der Mittelwert der p-Werte ist 3 / (3+1) = 0,75. Dies bedeutet, dass p-Werte zwischen 0,90 und 1,00 am häufigsten vorkommen, p-Werte zwischen 0,80 und 0,90 etwas weniger häufig sind und so weiter, bis hinunter zu sehr wenigen p-Werten zwischen 0,00 und 0,10. Das Diagramm in Abbildung 2 zeigt die Ergebnisse von 10.000 Tests aus der Betaverteilung mit a = 3 und b = 1.

Abbildung 2: Sampling aus der Beta(3,1)-Verteilung

Der Zusammenhang zwischen der Betaverteilung und einem Bernoulli-Banditenproblem ist recht subtil. Kurz gesagt ist die Betaverteilung die komplex-konjugierte A-priori-Wahrscheinlichkeit der Bernoulli-Wahrscheinlichkeitsfunktion. Obwohl die zugrunde liegende Mathematik sehr komplex ist, ist die Implementierung des Thompson-Algorithmus glücklicherweise (relativ) einfach.

Das Demoprogramm

Um das Demoprogramm zu erstellen, habe ich Visual Studio gestartet und eine neue Konsolenanwendung mit dem Namen „Thompson“ erstellt. Das Demoprogramm weist keine nennenswerten .NET Framework-Abhängigkeiten auf, sodass jede Version von Visual Studio funktionieren sollte. Nach dem Laden des Vorlagencodes habe ich im Editor-Fenster mit der rechten Maustaste auf die Datei „Program.cs“ geklickt, die Datei in „ThompsonProgram.cs“ umbenannt und Visual Studio die automatische Umbenennung der Klasse „Program“ gestattet. Am Anfang des Vorlagencodes habe ich alle Verweise auf nicht benötigte Namespaces gelöscht und nur den Verweis auf den obersten Namespace „System“ beibehalten.

Die Gesamtprogrammstruktur wird mit einigen kleinen platzsparenden Änderungen in Abbildung 3 dargestellt. Die gesamte Steuerungslogik ist in der Methode „Main“ enthalten. Das Sampling aus der Betaverteilung wird mithilfe der vom Programm definierten BetaSampler-Klasse implementiert. Die übliche Fehlerprüfung entfällt, um Platz zu sparen.

Abbildung 3: Struktur des Thompson Sampling-Demoprogramms

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
  {
    // ...
  }
}

Die Demo beginnt mit dem Einrichten von vier Arrays:

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];

Die Demo verwendet drei Automaten, aber Thompson Sampling kann mit beliebig vielen Automaten arbeiten. Die mittleren Auszahlungswahrscheinlichkeiten sind hartcodiert. Je näher die mittleren Wahrscheinlichkeiten beieinander liegen, desto schwieriger ist das Problem. Das Array namens „probs“ enthält die Wahrscheinlichkeiten aus einem Sampling der Betaverteilung, die bestimmen, welcher Automat gespielt werden soll. Die Arrays mit den Namen S („Success“) und F („Failure“) speichern die kumulative Anzahl der Auszahlungen bzw. Nichtauszahlungen pro Automat beim Spielen.

Die Demo verwendet zwei Zufallszahlen generierende Objekte:

Random rnd = new Random(4);
BetaSampler bs = new BetaSampler(2);

Das rnd-Objekt wird verwendet, um festzustellen, ob ein ausgewählter Automat gewinnt oder verliert. Beachten Sie, dass ich die Begriffe „win“ (gewinnen) und „lose“ (verlieren), „pay out“ (auszahlen) und „not pay out“ (nicht auszahlen) sowie „success“ (Erfolg) und „failure“ (Misserfolg) austauschbar verwende. Das bs-Objekt wird verwendet, um die Betaverteilung zu testen. Die verwendeten Startwerte (2 und 4) wurden nur deshalb angegeben, weil sie eine repräsentative Demoausführung bereitgestellt haben. 

Die Hauptsimulationsschleife beginnt:

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);
...

Sie können die Anzahl der Versuche auf eine große Zahl (z.B. auf 1.000) festlegen, um zu beobachten, wie schnell das Thompson Sampling auf einem optimalen Automaten auf Null geht. Der Schlüssel zur gesamten Demo ist der Aufruf der Sample-Methode. Die Anzahl der Erfolge und Misserfolge wird an die Methode übergeben. Eine Konstante mit dem Wert 1,0 wird als eine Art Hack hinzugefügt, da die Betaverteilung erfordert, dass die Parameter a und b größer als 0 sind. Wenn Sie einige Vorinformationen über die Auszahlungswahrscheinlichkeiten der Automaten haben, können Sie die Konstante anpassen, um diese Informationen widerzuspiegeln.

Nach Anzeige der aktualisierten Samplingwahrscheinlichkeiten wählt die Demo den Automaten mit der höchsten Samplingwahrscheinlichkeit aus:

int machine = 0;
double highProb = 0.0;
for (int i = 0; i < N; ++i) {
  if (probs[i] > highProb) {
    highProb = probs[i];
    machine = i;
  }
}

Weil Wahrscheinlichkeiten getestet werden, kann ein Automat selbst dann für das Spiel ausgewählt werden, wenn er null Gewinne und viele Misserfolge aufweist. Dieser Mechanismus verbessert die Explorationsfähigkeiten des Algorithmus.

Die Hauptiterationsschleife endet mit dem Spielen des ausgewählten Automaten:

...
  Console.Write("Playing machine " + machine);
  double p = rnd.NextDouble();
  if (p < means[machine]) {
    Console.WriteLine("win"); ++S[machine];
  }
  else {
    Console.WriteLine("lose"); ++F[machine];
  }
}

Die NextDouble-Methode gibt einen einheitlichen Zufallswert zwischen 0,0 und 1,0 zurück und wird verwendet, um einen Bernoulli-Prozess zu implementieren. Die Demo schließt mit der Anzeige der geschätzten Auszahlungswahrscheinlichkeiten für jeden Automaten (ohne sich die Mühe zu machen, nach einer möglichen Division durch Null zu suchen) und der Anzahl der Spielvorgänge jedes Automaten ab.

Implementieren der Betaverteilung

Etwas überraschend: Nach meinem besten Wissen verfügt .NET Framework über keine Bibliotheksmethode, um aus der Betaverteilung zu testen. Anstatt eine Abhängigkeit aus einer externen Bibliothek zu verwenden, habe ich mich entschieden, einen solchen Mechanismus von Grund auf neu zu implementieren. Es gibt viele Algorithmen, um ein Betasample zu generieren. Ich habe den BA-Algorithmus verwendet, der von R. C. H. Cheng im Jahr 1978 entwickelt wurde. Der gesamte Code wird in Abbildung 4 gezeigt.

Abbildung 4: Vom Programm definierter Betaverteilungssampler

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;
  }
}

Sampling aus der Betaverteilung ist schon für sich ein faszinierendes Thema. Ein schneller Blick auf den Code sollte Sie schon davon überzeugen, dass hier raffinierte, nicht versuchsorientierte Mathematik eine Rolle spielt. Die Implementierung ist eng an das Quellforschungspapier angelehnt: Es werden die gleichen Variablennamen usw verwendet. Beachten Sie die potenzielle Endlosschleife, die in Forschungspseudocode üblich ist, aber in Produktionscode definitiv nicht verwendet werden darf. Sie können eine Schleifenzählervariable hinzufügen und eine Ausnahme auslösen, wenn der Wert einen bestimmten Schwellenwert übersteigt.

Zusammenfassung

Dieser Artikel und sein Code sollte Ihnen alle Informationen zur Verfügung stellen, die Sie benötigen, um mit Thompson Sampling für mehrarmige Bernoulli-Probleme zu experimentieren. Er sollte es Ihnen auch ermöglichen, Banditenprobleme mit anderen Arten von Auszahlungsfunktionen zu untersuchen. Wenn Sie z.B. Automaten verwenden, die nach einer Poisson-Wahrscheinlichkeitsfunktion auszahlen, würden Sie anstatt aus der Betaverteilung aus der Gammaverteilung testen, die die komplex-konjugierte A-priori-Wahrscheinlichkeit für Poisson ist.

Das mehrarmige Banditenproblem ist ein Beispiel für das sogenannte „bestärkende Lernen“ (Reinforcement Learning, RL). Bei RL Machine Learning erstellen Sie nicht ein Vorhersagesystem mit bezeichneten Daten, für die richtige Antworten bekannt sind, sondern generieren spontan ein Vorhersagemodell, indem Sie eine Art Belohnungsfunktion verwenden. RL nimmt eine führende Stellung in der Forschung im Bereich von Machine Learning ein.

---

Dr. James McCaffreyist in Redmond (Washington) für Microsoft Research tätig. Er hat an verschiedenen Microsoft-Produkten mitgearbeitet, unter anderem an Internet Explorer und Bing. Dr. McCaffrey erreichen Sie unter jamccaff@microsoft.com.

Unser Dank gilt den folgenden technischen Experten von Microsoft für die Durchsicht dieses Artikels: Chris Lee, Ricky Loynd, Adith Swaminathan

---

Diesen Artikel im MSDN Magazine-Forum diskutieren