|
|
# 069 | 推荐的Exploit和Explore算法之三：汤普森采样算法
|
|
|
|
|
|
周三的分享里，我们讨论了一种叫作UCB（Upper Confidence Bound）的算法。这种算法的核心是使用均值和标准差组成对物品的估计，并且利用这种估计达到EE的效果。同时，我们也提到，UCB的最大问题就是并没有真正达到随机的效果。
|
|
|
|
|
|
今天，我们来看一种不太一样的算法，叫“**汤普森采样**”（Thompson Sampling）。
|
|
|
|
|
|
## 为什么需要随机采样？
|
|
|
|
|
|
在讨论汤普森采样之前，我们先来看一看什么是**随机采样**。随机采样的技术和概率分布密不可分，也和计算机产生随机数有很大的联系。
|
|
|
|
|
|
我们这里主要是关心如何从一个概率分布中产生一个随机变量的样本。因为是随机变量的样本，因此不可能每一次产生的结果都一样。然而，对于大量的样本来说，其均值往往是对概率分布均值的一个比较好的估计。因此，样本其实可以用来刻画一个概率分布。
|
|
|
|
|
|
比如，我们用参数是0.5的伯努利分布来表达抛硬币这个事件。那么，从这个伯努利分布中产生的样本，也就是0和1，象征了硬币是正面还是反面这两个事件。很显然，因为是随机样本，所以如果我们的抽样次数足够多，每个事件发生的概率会趋向于0.5。
|
|
|
|
|
|
然而，有一点需要注意，并不是所有的分布都能够这样容易地抽取样本。实际上，即便是伯努利分布，也是因为有一定的程序，才能够确定从中抽样。而能够抽样的，往往是标准的分布，诸如伯努利分布、高斯分布或者其他简单分布。从抽样的角度来说，对于绝大多数的模型，从中抽取样本都不是一件完全直观自然的事情。
|
|
|
|
|
|
回到我们讨论的场景。在进行EE策略中，为什么需要引入随机采样呢？
|
|
|
|
|
|
我们之前介绍过EG算法。EG算法在实施过程中，P%的人群看到按照点击率排序的物品。这一部分，是没有随机性的。也就是说这些人会“确定性”地看见按照点击率排序的物品，每一次都会看见一模一样的东西。而在(1-P)%的人群中，每一次看到的又完全是随机的内容，一点都没有规律。很明显，EG算法的缺点是，有一部分过于确定，而有一部分过于随机。
|
|
|
|
|
|
再来说一说我们上一次分享的UCB算法。这个算法最大的问题在于它是一个“确定”的算法。也就是说，在参数已经确定了的情况下，UCB展示给用户看的内容也是一样的。
|
|
|
|
|
|
这里面的一个核心问题是，如果展示给用户的内容是一样的，也就是我们说的确定性算法，那么，也就丧失了“探索”（Explore）的机会。试想，一个用户在同一天内访问一个网站多次，看到的结果都是一样的，而用户一定不希望每次访问都看到同样的内容。这对于用户体验来说很不友好。
|
|
|
|
|
|
那怎么才能带来随机性呢？
|
|
|
|
|
|
我们刚才谈了抛硬币的例子，很显然，如果能够通过采样来对物品进行排序或者展示，那就能够解决随机性的问题，也就能够每次都给用户不一样的体验。
|
|
|
|
|
|
## 汤普森采样基本原理
|
|
|
|
|
|
有了希望通过采样来获得结果这个思路以后，下面的事情就变得慢慢清晰起来。
|
|
|
|
|
|
首先，我们提到了，采样需要对应的概率分布。因此，**第一步就是要构建场景的概率分布，来描绘我们的应用**。
|
|
|
|
|
|
回到物品点击率的场景下，和抛硬币类似，物品的点击其实可以用**伯努利分布**来进行建模。这里需要注意的是，我们究竟应该从什么分布中去采样呢？汤普森采样的原理是，从模型的**后验分布**中去采样。什么意思？这其实是借用了贝叶斯统计的思路，也就是说，我们希望对参数的后验概率分布进行建模。关于贝叶斯统计的思路，这里限于篇幅不做展开。大体上来说，后验概率分布是在已经有了数据的情况下，结合我们的先验概率，对参数的一种估计。
|
|
|
|
|
|
再回到用伯努利分布来对点击进行建模的例子中，如果我们希望得到后验概率分布，需要设置怎样的先验概率分布呢？如果我们希望后验概率分布是一个相对比较简单的分布，那我们可以设置所谓的“**共轭先验**”（Conjugate Prior）。对于伯努利分布来说，共轭先验就是**Beta分布**。在设置了Beta分布这个先验之后，我们其实就可以解析得到后验概率的分布，也是一个Beta分布，只不过后验概率分布的参数与先验的参数不同。
|
|
|
|
|
|
**在构造好后验概率分布之后，我们就可以选择从中进行抽样了**。注意，在当前的情况下，已经不是从伯努利分布中抽样，而是从Beta分布中抽样了。关于如何从Beta分布中抽样，这不在今天讨论的范畴。很多通用的数值计算库，比如MATLAB、NumPy等都有这方面的过程可以直接使用。
|
|
|
|
|
|
汤普森采样的流程是这样的，从后验分布中抽取一个参数的样本，然后选取所有物品中参数数值最大的那个，进行展示。
|
|
|
|
|
|
我们来分析一下汤普森采样的整体情况。
|
|
|
|
|
|
1. 每一轮，汤普森采样都有一个**参数采样**的动作。这个流程决定了汤普森采样本质上是一个随机的流程，不是一个确定的流程。
|
|
|
|
|
|
2. 汤普森是从后验概率分布中进行抽样的。这有什么好处呢？后验概率分布中抽样，当样本数足够大的时候，样本的均值也是趋近于分布的均值的。什么意思？如果某一个物品的点击率高，那么其后验概率的均值也就大，反复从中抽样，平均下来，基本上还是在这个点击率的数值范围周边，不会偏离很远。也就是说，我们从后验概率分布中抽样的结果，当样本比较多的时候，是会尊重点击率的数值大小的。这其实就是EG中P%的用户，以及UCB中为什么要使用均值这些步骤的核心所在。我们并不希望让物品最后显示的结果与真正的估计值偏离太远。
|
|
|
|
|
|
3. 汤普森采样因为使用了贝叶斯统计，我们对参数有先验的设置，因此针对当前点击率估计还不准确甚至还没有数据的物品来说，有天然的优势。
|
|
|
|
|
|
4. 因为是采样，即便是在参数一样的情况下，两个物品的采样数值都有很大可能是不一样的，一举解决了我们之前提到的UCB的问题。
|
|
|
|
|
|
|
|
|
## 小结
|
|
|
|
|
|
今天我为你介绍了一个很重要的算法叫作汤普森采样，可以解决UCB的“确定性”问题，真正实现随机的效果。结束了我们今天的分享，EE这个话题也就告一段落了。
|
|
|
|
|
|
一起来回顾下要点：第一，我们聊了聊为什么需要引入采样的机制；第二，我们介绍了汤普森采样的基本原理。
|
|
|
|
|
|
最后，给你留一个思考题，汤普森采样有没有什么问题，或者说有没有什么劣势呢？
|
|
|
|
|
|
欢迎你给我留言，和我一起讨论。
|
|
|
|