Thompson抽样算法-Python

楔子：
伯努利试验：
就是一次实验只有两种可能的结果
n次伯努利试验：
一次实验只有两种可能的结果，并且每次的实验之间相互独立
二项分布：
就是n次伯努利实验所遵守的分布，并且每次实验成功的概率是已知的
beta分布：
n次伯努利试验，但是每次实验成功的概率是未知的，我们得到的分布就是该事件成功的概率的可能性分布，可以说是概率的概率分布，其中第一个参数代表先验中成功的次数，第二个参数代表先验中失败的次数。
beta分布和二项分布都具有共轭性。

Thompson抽样算法.PNG 贝叶斯推理.PNG

这里我们可以看出对于广告的投放每次只有两种结果，并且每次投放的结果是相互独立的，投放的成功率也是未知的，遵循beta分布。
我们随机在beta分布中抽取的随机数代表广告成功的概率，选取最大的，在一定程度上就代表每次抽取成功概率最大的那个广告。

1、数据预处理

代码：

import matplotlib.pyplot as plt
import pandas as pd

# Importing the dataset
dataset = pd.read_csv('Ads_CTR_Optimisation.csv')

2、初始化

代码：

import random
N = 10000
d = 10
ads_selected = []
numbers_of_rewards_1 = [0] * d
numbers_of_rewards_0 = [0] * d
total_reward = 0

3、做出选择

代码：

for n in range(0, N):
    ad = 0
    max_random = 0
    for i in range(0, d):
        random_beta = random.betavariate(numbers_of_rewards_1[i] + 1, numbers_of_rewards_0[i] + 1)
        if random_beta > max_random:
            max_random = random_beta
            ad = i
    ads_selected.append(ad)
    reward = dataset.values[n, ad]
    if reward == 1:
        numbers_of_rewards_1[ad] = numbers_of_rewards_1[ad] + 1
    else:
        numbers_of_rewards_0[ad] = numbers_of_rewards_0[ad] + 1
    total_reward = total_reward + reward

4、可视化

代码：

# Visualising the results - Histogram
plt.hist(ads_selected)
plt.title('Histogram of ads selections')
plt.xlabel('Ads')
plt.ylabel('Number of times each ad was selected')
plt.show()

5、运行结果

点击次数.PNG 很快找到最佳广告.PNG

我们可以看出Thompson抽样算法的效果比UCB算法的效果更好，它们俩的区别仅在于选取下一次抽样对象的方法不同，一个是基于以前的实验结果计算出上界，一个是基于beta分布随机抽取最可能被点击的广告。