Febrero de 2018

Volumen 33, número 2

Serie de pruebas: muestreo de Thompson con C#

Por James McCaffrey

El muestreo de Thompson es un algoritmo que se puede usar para encontrar una solución a un problema Multi-Armed Bandit, un término derivado del hecho de que las máquinas tragaperras se denominan de manera informal "one-armed bandits".

Supongamos que está de pie enfrente de tres máquinas tragaperras. Cuando tire del brazo de una de las máquinas, esta no dará ningún euro o desembolsará uno, en función de alguna distribución de probabilidad que le resulta desconocida. Por ejemplo, la máquina podría desembolsar dinero con una probabilidad media de 0,5, por lo que si tiró de la palanca de esa máquina 100 veces, debería esperar no recibir ningún dólar unas 50 veces y un dólar las otras 50.

Su objetivo es identificar la mejor máquina de la manera más eficiente posible. El problema que acabamos de describir es un ejemplo del problema de los bandidos de Bernoulli, ya que el resultado es 0 o 1. Existen otros tipos de problemas de bandidos. Por ejemplo, si cada máquina desembolsara un valor, generalmente entre cero y un dólar (por ejemplo, 55,0 céntimos), de acuerdo con una distribución de campana de Gauss, tendría un problema de bandidos de proceso gaussiano. En este artículo solo se aborda el problema de los bandidos de Bernoulli.

Existen varios algoritmos que se pueden usar para buscar la mejor máquina. Supongamos que tiene una restricción de 100 tiradas en las tres máquinas. Podría intentar 10 tiradas en cada máquina y realizar un seguimiento del rendimiento de cada una. A continuación, podría usar las 70 tiradas restantes en la máquina que le proporcionó más dinero durante la fase de exploración de 30 tiradas. El peligro de este enfoque es que podría identificar erróneamente la mejor máquina. Asimismo, si usa muchas tiradas durante la fase de exploración, le quedarán pocas para la fase de explotación.

El muestreo de Thompson es un algoritmo inteligente que ajusta continuamente las probabilidades estimadas de desembolso de cada máquina. Como verá en breve, la clave del muestreo de Thompson para un problema de bandidos de Bernoulli es la distribución beta matemática.

Es poco probable que su jefe le pida que analice máquinas tragaperras, pero los problemas Multi-Armed Bandit aparecen en muchos escenarios prácticos importantes. Por ejemplo, supongamos que trabaja para una compañía farmacéutica. Acaba de crear cuatro nuevos fármacos experimentales para el cáncer y quiere determinar cuál de los cuatro es más eficaz, con las mínimas pruebas en sujetos vivos. O quizás trabaja para una compañía de comercio electrónico y quiere determinar, entre varias campañas publicitarias nuevas, cuál tendrá el mayor éxito.  

Una buena manera de ver hacia dónde se dirige este artículo es echar un vistazo al programa de demostración de la figura 1. En la demo se configuran tres máquinas de Bernoulli con probabilidades de desembolso de (0,3, 0,5 y 0,7), respectivamente. En un escenario que no es de demostración, las probabilidades son obviamente desconocidas para usted. Se le permite un total de 10 tiradas. El objetivo es determinar la mejor máquina (n.⁰ 3) y tirar de su palanca la mayoría de las veces.

Figura 1 Demo del muestreo de Thompson

En la primera prueba, se supone que las tres máquinas tienen una probabilidad de pago de 0,5. En la demo se usa la distribución beta para generar tres probabilidades de acuerdo con ese supuesto. Estas probabilidades aleatorias son (0,7711, 0,1660 y 0,1090). Dado que la probabilidad asociada a la máquina n.⁰ 1 es más alta, se tira de su brazo. En este caso, la máquina n.⁰ 1 no desembolsa nada.

En la segunda prueba, en segundo plano, la demostración supone que la primera máquina tiene ahora una probabilidad de desembolso inferior a 0,5. Se usa el muestreo beta y esta vez las probabilidades son (0,6696, 0,2250 y 0,7654), por lo que se selecciona y usa la máquina n.⁰ 3. Su probabilidad estimada de desembolso se ajusta según si la máquina da dinero o no.

Con el tiempo, dado que la máquina n.⁰ 3 tiene la probabilidad de desembolso más alta, ganará más a menudo que las otras dos. Cada vez que la máquina n.⁰ 3 desembolsa dinero, aumenta la probabilidad de que se seleccione.

Después de las 10 pruebas, la máquina n.⁰ 1 se accionó tres veces y solo desembolsó dinero una vez, por lo que la simulación augura que su probabilidad real de desembolso es de aproximadamente 1/3 = 0,33. La máquina n.⁰ 2 se accionó tres veces y desembolsó dinero dos (probabilidad estimada de 2/3 = 0,6667). La máquina n.⁰ 3 se accionó cuatro veces y desembolsó dinero tres (probabilidad estimada de 3/4 = 0,7500). Por tanto, al menos en este ejemplo, se identificó la mejor máquina, que se accionó con más frecuencia.

En este artículo se supone que tiene conocimientos intermedios o altos de programación, pero no se supone que sepa nada acerca del muestreo de Thompson o las distribuciones beta. El programa de demostración está codificado con C#, pero no debería tener demasiados problemas para refactorizar el código a otro lenguaje, como Visual Basic o Python, si lo desea. El código del programa de demostración se presenta en su totalidad en este artículo, y también está disponible en la descarga del archivo que lo acompaña.

Explicación de la distribución beta

El muestreo de Thompson para el problema de los bandidos de Bernoulli depende de la distribución beta. Para poder comprender la distribución beta, debe entender las distribuciones de probabilidad en general. Existen muchos tipos de distribuciones de probabilidad, cada una de las cuales tiene variaciones que dependen de uno o dos parámetros.

Es posible que esté familiarizado con la distribución uniforme, que tiene dos parámetros denominados mínimo y máximo o, en ocasiones, simplemente a y b. Una distribución uniforme con unos valores mínimo = 0,0 y máximo = 1,0 devolverá un valor p de entre 0,0 y 1,0, donde cada valor es igual de probable. Por lo tanto, si muestreó 1000 veces desde la distribución uniforme, debería obtener unos 100 valores de p de entre 0,00 y 0,10, unos 100 valores de p de entre 0,10 y 0,20, y así sucesivamente hasta obtener unos 100 valores de p de entre 0,90 y 1,00. Si creó un gráfico con los resultados, debería ver un gráfico de barras con unas 10 barras, todas ellas de la misma altura aproximadamente.

Es posible que también le resulte familiar la distribución normal (también denominada "de Gauss"). La distribución normal también se caracteriza por tener dos parámetros, la media y la desviación estándar. Si muestreó 1000 veces desde la distribución normal con media = 0,0 y desviación estándar = 1,0, debería obtener unos 380 valores de z de entre -0,5 y +0,5; unos 240 valores de z de entre +0,5 y +1,5 (y también de entre -0,5 y -1,5); unos 60 valores de z de entre +1,5 y +2,5 (y también de entre -1,5 y -2,5); y 10 valores de z mayores de +2,5 (y 10 menores que -2,5). Si creó un gráfico con los resultados, debería ver un gráfico de barras en forma de campana.

La distribución beta se caracteriza por dos parámetros, normalmente denominados alfa y beta o, en ocasiones, simplemente a y b. Tenga en cuenta la posible confusión entre el término "beta" que representa toda la distribución y que representa el segundo de los dos parámetros de distribución.

Si realiza el muestreo desde una distribución beta con a = 1 y b = 1, obtiene exactamente los mismos resultados que con la distribución uniforme con media = 0,5. Si a y b tienen valores diferentes, al realizar el muestreo desde la distribución beta se obtienen valores de p que promedian en a/(a+b). Por ejemplo, si a = 3 y b = 1, y realiza el muestreo repetidamente, obtendrá valores de p de entre 0,0 y 1,0, pero la media de los valores de p será de 3/(3+1) = 0,75. Esto significa que los valores de p de entre 0,90 y 1,00 serán los más comunes; los valores de p de entre 0,80 y 0,90 serán un poco menos frecuentes; y así sucesivamente hasta llegar a unos pocos valores de p de entre 0,00 y 0,10. El gráfico de la Figura 2 muestra los resultados de 10 000 muestras de la distribución beta con a = 3 y b = 1.

Figura 2 Muestreo de la distribución beta(3,1)

La conexión entre la distribución beta y el problema de los bandidos de Bernoulli es bastante sutil. Brevemente, la distribución beta es el conjugado previo de la función de probabilidad de Bernoulli. Aunque la matemática subyacente es muy profunda, la implementación del algoritmo de Thompson es, por fortuna, (relativamente) simple.

El programa de demostración

Para crear el programa de demostración, inicié Visual Studio y creé una nueva aplicación de consola denominada Thompson. La demo no tiene ninguna dependencia significativa de .NET Framework, por lo que funcionará con cualquier versión de Visual Studio. Después de cargar el código de plantilla en la ventana del editor, hice clic con el botón derecho en el archivo Program.cs, le cambié el nombre por otro más descriptivo, ThompsonProgram.cs, y permití que Visual Studio cambiase automáticamente el nombre de la clase Program. En la parte superior del código de plantilla, eliminé todas las referencias a los espacios de nombres innecesarios y dejé solo la referencia al espacio de nombres System de nivel superior.

La estructura del programa general, con algunos cambios menores para ahorrar espacio, se presenta en la Figura 3. Toda la lógica de control se encuentra en el método Main. El muestreo de la distribución beta se implementa mediante la clase BetaSampler definida por el programa. Todas las comprobaciones de errores normales se quitan para ahorrar espacio.

Figura 3 Estructura del programa de demostración del muestreo de Thompson

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 demostración comienza con la configuración de cuatro matrices:

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

En la demostración se usan tres máquinas, pero el muestreo de Thompson puede funcionar con cualquier cantidad. Las probabilidades medias de los pagos están codificadas de forma rígida. Cuanto más se parezcan las probabilidades medias entre sí, más difícil será el problema. La matriz denominada probs contiene las probabilidades de un muestreo de la distribución beta, que determina en qué máquina se debe jugar. Las matrices denominadas S (acierto) y F (error) contienen el número de veces acumulado que cada máquina ha pagado y no ha pagado durante el juego.

La demo usa dos objetos de generación de números aleatorios:

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

El objeto rnd se usa para determinar si una máquina seleccionada gana o pierde. Observe que uso los términos "ganar" y "perder", "pagar" y "no pagar", y "acierto" y "error", de manera intercambiable. El objeto bs se usa para muestrear la distribución beta. Los valores de inicialización usados, 2 y 4, se especificaron solamente porque proporcionaban una ejecución de demostración representativa. 

El bucle de simulación principal comienza de la siguiente manera:

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

Es posible que quiera establecer un número de pruebas mayor, como 1000, para observar la rapidez con que el muestreo de Thompson se centra en una máquina óptima. La clave de toda la demostración es la llamada al método Sample. Los números de aciertos y errores se pasan al método. Una constante de 1,0 se agrega como una solución improvisada, ya que la distribución beta requiere que los parámetros a y b sean mayores que 0. Si tiene algunos conocimientos previos de las probabilidades de desembolso de las máquinas, puede ajustar la constante para reflejar esa información.

Después de mostrar las probabilidades de muestreo actualizadas, la demo selecciona la máquina con la probabilidad de muestreo más alta:

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

Dado que las probabilidades están muestreadas, aunque una máquina tenga cero aciertos y muchos errores, se podrá seleccionar para jugar igualmente. Este mecanismo mejora las funcionalidades de exploración del algoritmo.

El bucle de iteración principal concluye con el accionamiento de la máquina seleccionada:

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

El método NextDouble devuelve un valor aleatorio uniforme de entre 0,0 y 1,0, y se usa para implementar un proceso de Bernoulli. La demo termina mostrando las probabilidades estimadas de desembolso de cada máquina, sin preocuparse de comprobar la posible división entre cero, y el número de veces que se jugó a cada máquina.

Implementación de la distribución beta

De manera un poco sorprendente, por lo que sé, .NET Framework no tiene ningún método de biblioteca para el muestreo desde la distribución beta. En lugar de tomar una dependencia en una biblioteca externa, decidí implementar una desde cero. Existen muchos algoritmos para generar una muestra beta. Usé el algoritmo "BA", desarrollado por R. C. H. Cheng en 1978. El código completo se puede ver en la Figura 4.

Figura 4 Muestreador de distribución beta definida por el programa

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

El muestreo de la distribución beta es un tema fascinante por sí mismo. Un examen rápido del código debería convencerle de que existen matemáticas inteligentes, y no de evaluación implicadas. La implementación sigue estrictamente el artículo de investigación original, con los mismos nombres de variables, etc. Observe el bucle potencialmente infinito, común en el seudocódigo de investigación, pero inaceptable definitivamente en el código de producción. Es posible que quiera agregar una variable de contador de bucle e iniciar una excepción si su valor supera un umbral.

Resumen

Este artículo y su código deberían proporcionarle toda la información necesaria para experimentar con el muestreo de Thompson a fin de resolver problemas Multi-Armed Bandit de Bernoulli. También deberían permitirle explorar los problemas de bandidos con otros tipos de funciones de pago. Por ejemplo, si tiene máquinas que desembolsan dinero de acuerdo con una función de probabilidad de Poisson, en lugar de usar la distribución beta, probaría con la distribución gamma, que es el conjugado previo de Poisson.

El problema Multi-Armed Bandit es un ejemplo de lo que se conoce como aprendizaje de refuerzo (RL). En el área de Machine Learning de RL, en lugar de crear un sistema de predicción con datos etiquetados que tenga respuestas correctas conocidas, genera un modelo de predicción sobre la marca con algún tipo de función de recompensa. RL encabeza la investigación en el área de Machine Learning.

El Dr. James McCaffrey trabaja para Microsoft Research en Redmond, Washington. Ha colaborado en el desarrollo de varios productos de Microsoft como, por ejemplo, Internet Explorer y Bing. Puede ponerse en contacto con el Dr. McCaffrey en jamccaff@microsoft.com.

Gracias a los siguientes expertos técnicos de Microsoft por revisar este artículo: Chris Lee, Ricky Loynd y Adith Swaminathan

Discuta sobre este artículo en el foro de MSDN Magazine