Fevereiro de 2018
Volume 33 – Número 2
Execução de teste - Amostragem de Thompson usando a C#
Por James McCaffrey
.jpg "James McCaffrey")
A amostragem de Thompson é um algoritmo que pode ser usado para encontrar uma solução para um problema “multi-armed bandit” (com várias probabilidades), um termo que deriva das máquinas caça-níqueis que são informalmente chamadas de “one-armed bandits”.
Vamos supor que você esteja em frente a três máquinas caça-níqueis. Quando puxa a alavanca de uma das máquinas, ela lhe paga um dólar ou nada, de acordo com alguma probabilidade de distribuição desconhecida para você. Por exemplo, a máquina pode pagar com uma probabilidade média de 0,5; portanto, se você puxar a alavanca da máquina cem vezes, o esperado é que você não ganhe nada em 50 vezes e ganhe um dólar nas outras 50.
Seu objetivo é identificar a melhor máquina da maneira mais eficiente possível. O problema recém-descrito é um exemplo de um problema com várias probabilidades de Bernoulli, pois o resultado é 0 ou 1. Existem outros tipos de problemas com várias probabilidades. Por exemplo, se cada máquina pagou um valor, geralmente entre zero e um dólar (como 55 centavos), de acordo com a distribuição gaussiana em forma de sino, você teria um problema com várias probabilidades de processo gaussiano. Este artigo aborda somente o problema com várias probabilidades de Bernoulli.
Há vários algoritmos que podem ser usados para tentar encontrar a melhor máquina. Vamos supor que você só possa puxar a alavanca cem vezes nas três máquinas. Você poderia tentar dez vezes em cada máquina, anotando o desempenho de cada uma. Depois, poderia usar suas 70 chances na máquina que pagou a quantia mais alta durante a fase de exploração, ou seja, nas primeiras 30 vezes. O perigo dessa abordagem é que você pode identificar incorretamente a melhor máquina. E, se você puxar a alavanca muitas vezes na fase de exploração, não terá muitas chances sobrando depois.
A amostragem de Thompson é um algoritmo inteligente que ajusta continuamente as probabilidades estimadas de cada pagamento da máquina. Como você verá em breve, a chave da amostragem de Thompson para um problema com várias probabilidades de Bernoulli é a distribuição beta matemática.
É improvável que seu chefe lhe peça para analisar máquinas caça-níqueis, mas problemas com várias probabilidades surgem em muitas situações práticas importantes. Por exemplo, vamos supor que você trabalhe para um laboratório fabricante de medicamentos. Você acabou de criar novos medicamentos experimentais contra o câncer e deseja saber qual dos quatro é mais eficiente, com o menor número possível de testes em seres vivos. Ou talvez você trabalhe para uma empresa de comércio eletrônico e deseje descobrir qual das diversas campanhas publicitárias é a mais bem-sucedida.
A melhor maneira de saber o rumo que este artigo tomará é examinar o programa de demonstração na Figura 1. A demonstração configura três máquinas Bernoulli com probabilidades de pagamento de (0,0; 0,5; 0,7), respectivamente. Em um cenário que não seja o da demonstração, as probabilidades são desconhecidas para você, é claro. Você tem permissão para puxar a alavanca dez vezes. O objetivo é determinar a melhor máquina (máquina nº3) e puxar sua alavanca na maioria das vezes.
.png "Demonstração de amostragem de Thompson")
Figura 1 - Demonstração de amostragem de Thompson
Na primeira tentativa, vamos supor que todas as três máquinas têm uma probabilidade de pagamento de 0,5. A demonstração usa a distribuição beta para gerar três probabilidades baseadas nesta hipótese. Essas probabilidades aleatórias são (0,7711; 0,1660; 0,1090). Como a probabilidade associada à máquina nº1 é a maior, sua alavanca é puxada. Nesse caso, a máquina nº1 não paga nada.
Na segunda tentativa, nos bastidores, a demonstração acredita que a primeira máquina agora tem uma probabilidade de pagamento inferior a 0,5. A amostragem beta é usada e, desta vez, as probabilidades são (0,6696; 0,2250; 0,7654); portanto, a máquina nº3 é selecionada e acionada, e sua probabilidade de pagamento estimada é ajustada de acordo com o fato de a máquina realizar ou não o pagamento.
Com o tempo, como a máquina nº3 tem a maior probabilidade de realizar o pagamento, ela ganhará com mais frequência do que as outras duas máquina, e cada vez que a máquina nº3 fizer o pagamento, a probabilidade de que será selecionada aumenta.
Após dez tentativas, a máquina nº1 foi acionada três vezes e pagou somente uma; portanto, a simulação pressupõe que sua verdadeira probabilidade de pagamento é de cerca de 1/3 = 0,33. A máquina nº2 foi acionada três vezes e pagou duas vezes (p estimado = 2/3 = 0,6667). A máquina nº3 foi acionada quatro vezes e pagou três (p estimado = 3/4 = 0,7500). Assim, neste exemplo pelo menos, a melhor máquina foi identificada e acionada com mais frequência.
Este artigo pressupõe que você tenha habilidades de programação intermediárias ou avançadas, mesmo que não tenha familiaridade alguma com a amostragem de Thompson ou distribuições beta. O programa de demonstração é codificado usando a linguagem C#, mas você não deve ter muita dificuldade para refatorar o código em outra linguagem, como Visual Basic ou Python, se desejar. O código do programa de demonstração é apresentado em sua totalidade neste artigo, e também está disponível no download do arquivo fornecido com ele.
Entendendo a distribuição beta
A amostragem de Thompson de um problema com várias probabilidades de Bernoulli depende da distribuição beta. Para entender a distribuição beta, você deve entender as distribuições de probabilidade em geral. Existem vários tipos de distribuição de probabilidades, cada uma com variações que dependem de um ou dois parâmetros.
Você pode estar familiarizado com a distribuição uniforme, que tem dois parâmetros, chamados de mín. e máx., ou, às vezes, somente a e b. Uma distribuição uniforme com mín. = 0,0 e máx. = 1,0 retornará um valor p entre 0,0 e 1,0, em que cada valor é igualmente provável. Portanto, se você fez uma amostragem de mil vezes usando a distribuição uniforme, espera receber cerca de cem valores p entre 0,00 e 0,10, cerca de cem valores de p entre 0,10 e 0,20, e assim por diante, até cerca de cem valores de p entre 0,90 e 1,00. Se tiver criado um gráfico dos resultados, verá um gráfico de barras com dez barras, todas com mais ou menos a mesma altura.
Talvez você já esteja familiarizado com a distribuição normal (também chamada de gaussiana). A distribuição normal também é caracterizada por dois parâmetros: a média e o desvio padrão. Se você tiver feito uma amostra de mil vezes com base na distribuição normal com média = 0,0 e desvio padrão = 1,0, espera obter cerca de 380 valores z entre -0,5 e +0,5; cerca de 240 valores z entre +0,5 e +1,5 (e também entre -0,5 e -1,5); cerca de 60 valores z entre +1,5 e +2,5 (e também entre -1,5 e -2,5); e 10 valores z superiores a +2,5 (e 10 menos de -2,5). Se criar um gráfico dos resultados, verá um gráfico de barras com o formato de sino.
A distribuição beta se caracteriza por dois parâmetros, geralmente chamados de alfa e beta ou, às vezes, somente a e b. Observe a possível confusão entre “beta” que pode representar toda a distribuição, mas também o segundo dos dois parâmetros de distribuição.
Se você fizer uma amostragem usando uma distribuição beta com a = 1 e b = 2, obterá os mesmos resultados da distribuição uniforme com média = 0,5. Se a e b tiverem valores diferentes, quando você fizer a amostragem da distribuição beta, obterá valores p com média a / (a+b). Por exemplo, se a = 3 e b = 1, e você fizer a amostragem várias vezes, obterá valores p entre 0,0 e 1,0, mas a média dos valores p será 3 / (3+1) = 0,75. Isso significa que os valores p entre 0,90 e 1,00 serão os mais comuns; os valores p entre 0,80 e 0,90 serão um pouco menos comuns, e assim sucessivamente, até bem poucos valores p entre 0,00 e 0,10. O gráfico na Figura 2 mostra os resultados de dez mil amostras da distribuição beta com a = 3 e b = 1.
.png "Amostragem da distribuição beta (3,1)")
Figura 2 - Amostragem da distribuição beta (3,1)
A conexão entre a distribuição beta e um problema com várias probabilidades de Bernoulli é bem sutil. Em resumo, a distribuição beta é o cognato anterior à função de probabilidade de Bernoulli. Apesar de a matemática subjacente ser muito profunda, a implementação do algoritmo de Thompson é, felizmente, (relativamente) simples.
O programa de demonstração
Para criar o programa de demonstração, iniciei o Visual Studio e criei um novo aplicativo do console chamado Thompson. A demonstração não tem dependências significativas do .NET Framework, portanto, funcionará em qualquer versão do Visual Studio. Depois de carregar o código do modelo na janela do editor, cliquei com o botão direito do mouse no arquivo Program.cs, atribuí um nome mais descritivo a ele, ThompsonProgram.cs, e permiti que o Visual Studio renomeasse automaticamente a classe Program. Na parte superior do código do modelo, excluí todas as referências de namespaces desnecessários, deixando somente a referência ao namespace do System de nível superior.
A estrutura geral do programa, com algumas edições secundárias para economizar espaço, é apresentada na Figura 3. Toda a lógica de controle está contida no método Principal. A amostragem da distribuição beta é implementada usando-se a classe BetaSampler definida pelo programa. Toda a verificação de erros normais é removida para poupar espaço.
Figura 3 - Estrutura do programa de demonstração de amostragens 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
{
// ...
}
}
A demonstração começa com a configuração de quatro matrizes:
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];
A demonstração usa três máquinas, mas a amostragem de Thompson pode funcionar com qualquer número de máquinas. As probabilidades médias de pagamentos são codificadas. Quanto mais próximas as probabilidades médias estiverem umas das outras, mais difícil será o problema. A matriz nomeada probs contém as probabilidades de uma amostragem da distribuição beta, que determina qual máquina deve ser acionada. As matrizes nomeadas como S (“success”) e F (“failure”) contêm o número cumulativo de vezes em que cada máquina fez ou não o pagamento quando acionada.
A demonstração usa dois objetos gerados por números aleatórios:
Random rnd = new Random(4);
BetaSampler bs = new BetaSampler(2);
O objeto rnd é usado para determinar se uma máquina selecionada ganha ou perde. Observe que eu alterno o uso dos termos vencer ou ganhar, fazer ou não o pagamento, e sucesso e falha. O objeto bs é usado para fazer uma amostragem da distribuição beta. As sementes usadas, 2 e 4, foram especificadas somente porque forneciam uma execução de demonstração representativa.
O principal loop de simulação começa:
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);
...
Talvez você deseje definir o número de tentativas para um número mais alto, como mil, a fim de observar a rapidez com que os zeros de amostragem de Thompson são inseridos em uma máquina ideal. A chave para toda a demonstração é a chamada para o Método de amostragem. O número de sucessos e falhas é passado ao método. A constante 1,0 é adicionada como teste, pois a distribuição beta requer que os parâmetros a e b sejam maiores do que zero. Se você tiver conhecimento prévio das probabilidades de pagamento das máquinas, pode ajustar a constante para refletir essa informação.
Após exibir as probabilidades de amostragem atualizadas, a demonstração seleciona a máquina com a maior probabilidade de amostragem:
int machine = 0;
double highProb = 0.0;
for (int i = 0; i < N; ++i) {
if (probs[i] > highProb) {
highProb = probs[i];
machine = i;
}
}
Como as probabilidades são amostragens, mesmo se a máquina não ganhar nunca e houver muitas falhas, ela ainda pode ser selecionada para ser acionada. O mecanismo aumenta a capacidade de exploração dos algoritmos.
O principal loop de iteração é concluído acionando-se a máquina selecionada:
...
Console.Write("Playing machine " + machine);
double p = rnd.NextDouble();
if (p < means[machine]) {
Console.WriteLine("win"); ++S[machine];
}
else {
Console.WriteLine("lose"); ++F[machine];
}
}
O método NextDouble retorna um valor aleatório de forma uniforme entre 0,0 e 1,0 e é usado para implementar um processo de Bernoulli. A demonstração é concluída exibindo as probabilidades estimadas de pagamento de cada máquina (sem verificar a possível divisão por zero) e o número de vezes em que cada máquina foi acionada.
Implementando a distribuição beta
Surpreendentemente, até onde eu sei, o .NET Framework não tem um método de biblioteca para fazer a amostragem da distribuição beta. Em vez de usar uma dependência de uma biblioteca externa, decidi implementar uma do zero. Existem muitos algoritmos para gerar uma amostra beta. Usei o algoritmo “BA”, desenvolvido por R. C. H. Cheng em 1978. O código todo é apresentado na Figura 4.
Figura 4 - Amostragem da distribuição beta definida por 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;
}
}
A amostragem da distribuição beta é um tópico fascinante por si só. Uma rápida análise do código deve convencê-lo de que há conceitos matemáticos inteligentes não experimentais envolvidos. A implementação segue quase fielmente a pesquisa original, os mesmos nomes de variável etc. Observe o loop potencialmente infinito, que é comum em pseudocódigos de pesquisa, mas definitivamente proibido no código de produção. Talvez você queira adicionar uma variável de contador de loops e fazer uma exceção se o valor exceder algum limite.
Conclusão
Este artigo e seu código fornecem todas as informações de que você precisa para experimentar a amostragem de Thompson para problemas com várias probabilidades. Ele também permite que você explore os problemas com várias probabilidades com outros tipos de funções de pagamento. Por exemplo, se você tiver máquinas que pagam de acordo com a função de probabilidade de Poisson, em vez de usar a distribuição beta, faça a amostra com base na distribuição gama, que é o cognato anterior ao de Poisson.
O problema com várias possibilidades é um exemplo do que chamamos de aprendizado por reforço (RL). No aprendizado de máquina RL, em vez de criar um sistema de previsão usando dados rotulados que têm respostas corretas conhecidas, você gera um modelo de previsão rápida, usando algum tipo de função de recompensa. O RL está na vanguarda em termos de pesquisa de aprendizado de máquinas.
Dr. James McCaffreytrabalha para a Microsoft Research em Redmond, Washington. Ele trabalhou em vários produtos da Microsoft, incluindo Internet Explorer e Bing. Entre em contato com o Dr. McCaffrey pelo email jamccaff@microsoft.com.
Agradecemos aos seguintes especialistas técnicos da Microsoft pela revisão deste artigo: Chris Lee, Ricky Loynd, Adith Swaminathan