---

Febbraio 2018

Volume 33 Numero 2

Il presente articolo è stato tradotto automaticamente.

Esecuzione dei test - Campionamento Thompson con C#

Da James McCaffrey

Thompson il campionamento è un algoritmo che può essere usato per trovare una soluzione a un problema più armate bandit, un termine che derivano dal fatto che azzardo macchine slot sono informale chiamato "one-armed bandits".

Si supponga che sta permanente davanti a tre computer slot. Quando è effettuare il pull di arm in uno dei computer, pagamento è zero dollari o Dollaro uno in base alla distribuzione di probabilità alcuni che è sconosciuto. Ad esempio, la macchina può pagare con una probabilità media pari a 0,5, pertanto se si inseriscono l'handle su tale macchina 100 volte, è necessario prevedere di essere a pagamento zero circa 50 volte dollari, mentre un euro circa 50 volte.

L'obiettivo consiste nell'identificare la migliore macchina, con la massima efficacia. Il problema descritto in precedenza è un esempio di un problema di Bernoulli bandit perché il risultato è 0 o 1. Sono disponibili altri tipi di problemi di bandit. Ad esempio, ogni macchina effettuati da un valore, in genere compreso tra zero e un dollaro (ad esempio i centesimi 55,0), in base a una distribuzione di Gauss a campana, è necessario un problema di bandit processo gaussiana. Questo articolo riguarda solo il problema di bandit Bernoulli.

Esistono diversi algoritmi che possono essere usati per tentare di individuare la migliore macchina. Si supponga che l'utente è limitato a un totale di 100 esegue il pull nei tre computer. È possibile provare 10 pull in ogni computer, tenere traccia di grado di eseguire ogni macchina. È possibile usare il pull di 70 rimanenti in un computer che versato la maggior parte dei money durante la fase di esplorazione 30 pull. Il rischio che con questo approccio è che è possibile identificare in modo non corretto della migliore macchina. E, se si utilizza molti pull durante la fase di esplorazione, non sarà possibile sinistra molti durante la fase di exploit.

Thompson campionamento è un algoritmo appositamente continuamente vengono adattate le probabilità stimate di pagamenti di ogni computer. Come si vedrà a breve, la chiave per Thompson campionamento per un problema di Bernoulli bandit è la distribuzione beta matematica.

È improbabile verrà chiesto da capo per analizzare macchine slot, ma più armate bandit problemi vengono visualizzati in molti scenari importanti e pratici. Si supponga, ad esempio, che si lavora per un produttore somministrato il farmaco. Quattro farmaci sperimentali nuovo per cancer appena creato e si desidera stabilire quali le quattro droghe è più efficace, con un minimo di test su argomenti trattati in tempo reale. O forse si lavora per una società di e-commerce e si desidera determinare quale delle diverse nuove campagne pubblicitarie è più efficace.  

È un buon metodo per visualizzare in questo articolo è a due punte per dare un'occhiata il programma demo in figura 1. La dimostrazione imposta tre macchine di Bernoulli con probabilità di pagamento (0,3, 0,5, 0,7), rispettivamente. In uno scenario non demo, le probabilità sono noti, ovviamente. È consentito un totale di 10 esegue il pull. L'obiettivo è determinare la migliore macchina (computer #3) e il relativo handle di pull la maggior parte dei casi.

Figura 1 Thompson campionamento Demo

Al primo tentativo, si supponga che tutte le tre macchine una probabilità di pagamenti di 0,5. La dimostrazione utilizza la distribuzione beta per generare tre probabilità in base a questo presupposto. Queste probabilità casuale sono (0.7711, 0.1660, 0.1090). Poiché la probabilità associata alla macchina #1 è più alta, viene effettuato il pull relativo arm. In questo caso, il computer 1 # non pagare.

Il secondo tentativo, dietro le quinte, demo ritiene che la prima macchina include ora una probabilità di pagamento che è minore di 0,5. Viene utilizzato il campionamento Beta e in questa fase le probabilità sono (0.6696, 0.2250, 0.7654), in modo macchina #3 è selezionata e riprodotto e alla probabilità stimata di pagamento viene regolata in base che la macchina paga o non.

Nel corso del tempo, perché macchina #3 è la più elevata probabilità di pagamento, avrà la precedenza più spesso degli altri due computer e ogni macchina di ora #3 pagato, la probabilità che sarà selezionato aumenta.

Dopo il 10 prove macchina #1 è stato riprodotto tre volte e versata una sola volta in modo la simulazione dedotta alla probabilità true di pagamento è di circa 1/3 = 0,33. Macchina #2 è stato riprodotto tre volte e versato due volte (stimato p = 2/3 =.6667). Computer #3 è stato riprodotto quattro volte e a pagamento tre volte (stimato p = 3/4 = 0.7500). In tal caso, in questo esempio, almeno la migliore macchina è stata identificata ed è stato riprodotto più di frequente.

Questo articolo si presuppone è migliore delle competenze di programmazione o intermedia, ma non si supponga che si conosca Thompson campionamento o la distribuzione beta. Il programma demo è codificato tramite c#, ma non dovrebbe essere troppo difficile refactoring del codice in un altro linguaggio, ad esempio Visual Basic o Python, se si desidera. Il codice per il programma demo viene presentato nella sua interezza in questo articolo ed è anche disponibile nel download di file allegati.

Le informazioni sulla distribuzione di Beta

Thompson campionamento per un problema di Bernoulli bandit dipende la distribuzione beta. Per comprendere la distribuzione beta è necessario comprendere in generale le distribuzioni di probabilità. Esistono molti tipi di distribuzioni di probabilità, ognuno dei quali presenta le variazioni che dipendono da uno o due parametri.

Familiarità con la distribuzione uniforme, che presenta due parametri, denominato min e max, o solo in alcuni casi potrebbe essere un a e b. Una distribuzione uniforme con min = 0,0 e max = 1.0 verrà restituito un valore di p compreso tra 0,0 e 1,0 in cui ogni valore è ugualmente probabile. Pertanto, se sampled 1.000 volte dalla distribuzione uniforme, previsto ottenere sui valori di p 100 compreso tra 0,00 e 0,10, sui valori di p 100 tra 0,10 e 0,20 e così via, sui valori di p 100 tra 0,90 e 1.00. Se è stato creato un grafico i risultati, si vedrà un grafico a barre con le barre di 10, tutti sulla stessa altezza.

È anche possibile familiarità con la distribuzione normale (anche denominato gaussiana). La distribuzione normale è inoltre caratterizzata da due parametri, la media e la deviazione standard. Se campionati 1.000 volte dalla distribuzione normale con Media = 0,0 e deviazione standard = 1.0, è previsto per ottenere informazioni 380 z-valori compresi tra -0.5 e 0,5; circa 240 valori z tra 0,5 e più di 1,5 (e anche tra -0.5 e -1.5); circa 60-i valori z tra più di 1,5 e + 2,5 (e anche tra -1.5 e -2,5); e 10 valori z maggiori di + 2,5 (e 10 minore di -2,5). Se è stato creato un grafico i risultati visualizzati un grafico a barre a campana.

La distribuzione beta è caratterizzata da due parametri, in genere chiamato alfa e beta, o solo in alcuni casi un a e b. Si noti la possibile confusione tra che rappresenta l'intera distribuzione di "beta" e "beta", che rappresenta il secondo dei parametri di distribuzione di due.

Se si esegue un campionamento da una distribuzione di beta con un = 1 e b = 1, si ottiene esattamente stesso generato dalla distribuzione uniforme con Media = 0,5. Se un e b hanno valori diversi, quando si ottengono valori p che medio per la distribuzione di beta si campiona un / (a + b). Ad esempio, se un = 3 a e b = 1 e si ripetutamente di esempio, si otterranno p-valori compresi tra 0,0 e 1,0, ma la media dei valori di p sarà 3 / (3 + 1) = 0,75. Ciò significa che p-valori compresi tra 0,90 e 1,00 siano i più comuni; p-valori compresi tra 0,80 e 0,90 sarà un po' meno comuni; e così via, fino a pochi valori p compreso tra 0,00 e 0,10. Il grafico in figura 2 Mostra i risultati di 10.000 esempi dalla distribuzione beta con un = 3 a e b = 1.

Figura 2 campionamento dalla distribuzione Beta(3,1)

La connessione tra la distribuzione beta e di un problema di Bernoulli bandit è piuttosto sottile. In breve, la distribuzione beta è coniugata precedente per la funzione di probabilità di Bernoulli. Anche se l'espressione sottostante è molto profonda, implementazione dell'algoritmo Thompson è, per fortuna, () semplice.

Il programma Demo

Per creare il programma demo avviato Visual Studio e creare una nuova applicazione console denominata Thompson. La dimostrazione senza dipendenze significativo .NET Framework, in modo da qualsiasi versione di Visual Studio è appropriato. Dopo che il codice del modello caricato nella finestra dell'editor, I pulsante destro del mouse sul file Program.cs e rinominato il ThompsonProgram.cs leggermente più descrittivo e Visual Studio rinominare automaticamente classe Program per me è consentito. Nella parte superiore del codice del modello, è stato eliminato tutti i riferimenti agli spazi dei nomi non necessari, lasciando solo il riferimento allo spazio dei nomi di sistema principale.

La struttura complessiva di programma, con poche modifiche secondarie per risparmiare spazio, viene visualizzata figura 3. Tutta la logica di controllo è nel metodo Main. Campionamento dalla distribuzione beta viene implementato utilizzando la classe BetaSampler definito dal programma. Tutti i normali errori viene rimosso per risparmiare spazio.

Struttura del programma Demo campionamento Thompson figura 3

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 dimostrazione inizia impostando i quattro matrici:

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 dimostrazione utilizza tre computer, ma Thompson campionamento può funzionare con qualsiasi numero di macchine. Le probabilità medie di pagamenti sono hardcoded. Più vicini le probabilità medie sono tra loro, la più difficile il problema. La matrice denominata probs contiene le probabilità di un campionamento della distribuzione beta, che determinano quali computer per la riproduzione. Le matrici denominate S ("esito positivo") che F ("errore") contengono il numero cumulativo di volte in cui ogni macchina versato e non è stato pagato durante la riproduzione.

La dimostrazione utilizza i due oggetti di generazione numero casuale:

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

L'oggetto rnd viene utilizzato per determinare se un server wins macchina selezionata o perde. Si noti che utilizzare win i termini e perdere, pagare e non pagare e l'esito positivo e negativo, in modo intercambiabile. L'oggetto bs viene utilizzato per la distribuzione beta di esempio. I valori di inizializzazione utilizzati, 2 e 4, sono stati specificati solo perché fornite un'esecuzione della dimostrazione rappresentativa. 

Inizia il ciclo di simulazione principale:

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

Si potrebbe voler impostare il numero di versioni di valutazione per un numero elevato, ad esempio 1.000, in modo da osservare la rapidità Thompson zeri in un computer ottimale di campionamento. La chiave per la dimostrazione intera è la chiamata al metodo di esempio. Il numero di operazioni riuscite e non viene passato al metodo. Una costante 1.0 viene aggiunto come un elemento di un hack perché richiede la distribuzione beta di un e parametri b devono essere maggiori di 0. Se si dispone di conoscenza della probabilità di pagamento dei computer, è possibile regolare la costante per riflettere tali informazioni.

Dopo aver visualizzato le probabilità di campionamento aggiornata, demo consente di selezionare la macchina con la maggiore probabilità di campionamento:

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

Poiché le probabilità vengono campionate, anche se dispone di una macchina zero wins e molti errori, potrebbe ancora selezionato per la riproduzione. Questo meccanismo migliora le funzionalità di esplorazione dell'algoritmo.

Il ciclo di iterazione principale si conclude con la riproduzione di computer selezionato:

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

Il metodo NextDouble restituisce un valore in modo uniforme casuale compreso tra 0,0 e 1,0 e viene utilizzato per implementare un processo di Bernoulli. La dimostrazione si conclude con la visualizzazione le probabilità stimate di pagamento per ogni computer (non richiedere l'intervento per cercare possibili divisione per zero) e il numero di volte in cui che ogni computer è stato riprodotto.

Implementa la distribuzione Beta

Con la migliore conoscenza del .NET Framework non è un metodo della libreria esempio dalla distribuzione beta. Anziché creare una dipendenza da una libreria esterna, ho deciso di implementare uno da zero. Sono disponibili molti algoritmi per generare un campione beta. Dopo aver utilizzato l'algoritmo "BA", sviluppato da R. C. H. Cheng nel 1978. Tutto il codice verrà presentato in figura 4.

Figura 4 definito dal programma Beta distribuzione campionatore

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

Il campionamento dalla distribuzione beta è un argomento utili in sé. Un'analisi veloce del codice deve convincere l'utente è coinvolto alcuni calcoli matematici intelligenti, non di valutazione. L'implementazione conforme il documento di ricerca origine strettamente, nomi delle stesse variabili e così via. Si noti il ciclo potenzialmente infinito, che è comune nelle ricerche pseudo-codice, ma un no-no definita nel codice di produzione. È possibile aggiungere una variabile contatore del ciclo e generare un'eccezione se il valore supera una determinata soglia.

Conclusioni

In questo articolo e il codice viene fornito tutte le informazioni necessarie per sperimentare Thompson campionamento per i problemi più armati di Bernoulli. Deve consentono inoltre di esaminare problemi bandit con altri tipi di funzioni di pagamento. Ad esempio, se si hanno macchine che pagano secondo una funzione di probabilità di Poisson, anziché utilizzare la distribuzione beta sarebbe di esempio dalla distribuzione gamma, ovvero il coniugato precedente Poisson.

Il problema più armate bandit è riportato un esempio di ciò che viene denominata amplificazione learning (RL). In RL machine learning anziché creare un sistema di stima utilizzando i dati con etichette che costituisce un risposte corrette, si genera un stima modello di volo, utilizzando un tipo di funzione benefici. RL è sempre all'avanguardia di machine learning research.

---

Dr. James McCaffreyfunziona per Microsoft Research Redmond, WA Ha lavorato su diversi prodotti Microsoft, tra cui Internet Explorer e Bing. Dr. McCaffrey può essere raggiunto al jamccaff@microsoft.com.

Grazie per i seguenti esperti Microsoft che ha revisionato in questo articolo: Chris Lee, Ricky Loynd, Adith Swaminathan

---

Viene illustrato in questo articolo nel forum di MSDN Magazine